RSA主要原理，數學基礎

一些關于RSA的了解

RSA是第一個實用的公鑰密碼系統

關于RSA加密算法的一些講解，以及自己的了解

RSA自從研發到現在已經經曆了20餘年的攻擊考驗，充分

展示了RSA算法的巧妙安全。

最近學校有講到，了解到RSA，其實許多計算機專業的同學在大一上就有了些了解，為什麼RSA能經曆如此多的考驗，以至于現在為人們廣為接受呢？

那麼，WHY RSA?

RSA簡介

RSA是第一個實用的公鑰密碼系統，是目前應用最為廣泛的公鑰密碼系統，三位發明者，R.rivest, A.shamir,L.aderman.之後獲得了2002年的ACM圖靈獎 ，計算機界的最高榮譽，足以看出RSA的強大與巧妙。WHY RSA?

最大的特點是非對稱加密，可以在下面了解到非對稱加密的特點。

HOW？ RSA的步驟

這段内容，網上已經多到爆了QAQ稍微用表格表示一下步驟

稍微用表格表示一下步驟：

先找兩個素數	p=3,q=11
1.尋找歐拉函數φ(n)	φ(n)=(p-1)(q-1)=2*10=20
2.求公鑰E	1<E<φ(n), 且與φ(n)互質，故取3
3.求公共模數N	N=p*q
4.求私鑰D	(D*E)%φ(n)=1,公鑰私鑰相乘模φ(n)取餘為1
私鑰為7
5.加密公式	密文=明文^公鑰(mod公共模數)
密文C(ciphertext)	C=P^E(mod N)
6.解密公式	明文=密文^私鑰(mod公共模數)
明文P(plaintext)	P=C^D(mod N)

表中有好幾個重要的量，一共6個步驟，可以十厘清楚的看懂RSA的加密步驟，确實，抛開數論的公式，看起來隻是簡單的數學運算，像求模運算等。RSA加密的步驟顯然是沒有那麼複雜的。

在說下詳細的操作，可以跳開，先取兩個質數，這裡要提到，沒
了解的同學，可以看看基礎,挨個看看其組成
           

1.兩個質數 與 公共模數

首先尋找兩個質數，先命名為p和q，核心也就是質數，接下來想講
一講
           

(1)

p與q的乘積為 公共模數 N。N十分重要，因為明文和密文

在經過加密解密時必須要模公共模數，(mod N)。

同時

(2)：

經過p與q的計算可以生成公鑰(歐拉公式說)

(3):

p與q相乘得到的公共模數N，轉化為二進制數即為其RSA長度位數，

表格中選取的p與q為3與11,33轉化為二進制為100001，其長度為6

位實際上，一般場合軟體加密需要1024位，重要場合加密要2048位

。

可以算算2的1024次方是多少，數字是十分巨大的。當然越大也越安全，說到安全之後也會說到，數字大加密起來，自然也存在時間問題，之後在優缺點也會講到。

2.歐拉公式

p =3; q=11                       //兩個大的質數
  
 φ(n) = (p-1)(q-1)      
           

即為歐拉函數，實際上，這隻是歐拉函數推導的一部分，歐拉公式，φ(n) 這裡用于推導1到p和q之内有多少個數與其互質。

其也指出0到p（一個質數）之間,與其互質的數有p-1個。

即，0~5之間與其互質的數字就有（5-1），4個，為1,2,3,4.

同時兩個質數其互質數，滿足乘法法則。

φ(p*q)=(p-1)(q-1)
           

該步驟用于尋找，1到 φ(n)之間合适的一個質數。篩選出的質數為公鑰E，同時， φ(n)與E的模反函數為私鑰。即為：

(E*D)% φ(n)=1
           

得到公鑰和私鑰。

為什麼要滿足這樣的條件呢？？？？

3,公鑰與密鑰

公鑰與密鑰可以進行解密，加密。

公鑰具體構成為（E,N）其為上文表格中的（公鑰，公共模數）

同理。私鑰的形式為（私鑰，公共模數），加密需要知道公鑰和公共模數。同時，隻要把公共模數和私鑰告訴對方，即可進行解密。

密文=明文^公鑰(mod公共模數)
 明文=密文^私鑰(mod公共模數) 
           

公鑰可以放出來，讓大家知道，也可以用來考驗密碼系統的能力。而私鑰不能洩露，兩個質數p,q也是十分重要的，不能洩露。

RSA的安全性

基本步驟已經放了出來，細看還是比較容易了解，即使不知道數論的知識也能很容易弄懂。

為什麼RSA熱門，作為密碼肯定有其安全性強這一關鍵因素。

RSA的安全性原理？

看到上面的解密，如果有人獲得了密文，他如果想通過密文竊取情報消息，當他把很多數字串，分揀開，并發現是RSA時，他會怎麼做呢？首先他會想找密鑰，一旦有了密鑰，就可以用解密公式解密，如果再輕松一點，連公共模數N也知道了，

該怎麼求呢？

他想知道私鑰D，由上文的表格很容易找到：

(E*D)%φ(n)=1
           

即私鑰與公鑰想乘之後，對φ(n)取餘餘1.

公鑰E已知的話，求出φ(n)就可以很容易得到答案。

φ(n)為前文的歐拉函數，表格中也有：

φ(n)=(p-1)(q-1)=2*10=20
=pq-p-q+1
           

想知道φ(n)，就必須對一個很大的質數，即為p與q的乘積進行因素分解，而大數字的因素分解極為困難，将一個幾百位的質數進行分解很難辦到，超過1024位的因素分解，更是至今未有人公開聲明能辦到。這裡就構成了其難破解性。

RSA的數學原理與正确性

接下來開始說RSA的正确性，也是數學原理。到現在，大家對RSA已經有了大部分的了解，知道怎麼找私鑰和公鑰以及加解密。

這個太複雜了，想看的人看吧，但過程還是擺在這裡，畢竟要說RSA得正确性。

比如這兩個公式，為什麼可以實作加密以及還原呢？

  密文=明文^公鑰(mod公共模數)
  明文=密文^私鑰(mod公共模數) 
           

網上有很多證明方法，這裡說教材上一種比較全面的（我認為。。）

有幾個上面提到的重要變量:

明文：        P      （Plaintext）
  密文:         C      （Cyphertext）
  兩個質數:     p與q
  公共模數:     N    =  p * q
  gcd():       求最大公約數
           

由加密公式：

C ≡  P^E(mod N)
       取出  P^E(mod N)
           

由同餘式性質：

P^E mod N    ≡     C^ED mod N   ≡    C^(kφ(n)+1) mod N  --------- (0）
           

這裡推出公式（0）

在第二項直接将P轉化為C的D次方

因為P=C^D mod N,可轉換。劃為C的ED次方。由之前的表格中：（由公鑰計算私鑰的公式得出）

(D*E)%φ(n)=1
           

即D與E的乘積模歐拉函數餘1.故DE寫為k(φ(n)+1)

現在從（1）式開始推導：

P^E mod N   =    C^(kφ(n)+1) mod N   --------- (1)
           

在這裡分兩種情況讨論：

（一）第一種情況：

C與N互質，即為密文（編碼為數字後）與公共模數互質。

這裡開始湊一個函數：使用了歐拉定理

C^φ(n)  =  1 mod N  
 C^kφ(n)  =  1 mod N
 C^(kφ(n) +1) = C  mod N
 于是得出結論：
 P^E mod N = C mod N    -------------(2)
           

先說前三行，n的x次方模一個數，不論是多少次方其模出的數都不會變。比如2的平方除以3餘1, 2的3次方，4次方除以3都餘1.不管取多少次方，模數不變。

利用這個特性，湊出 C^kφ(n) = 1 mod N，兩邊乘C，得到：

C ^ (kφ(n) +1) = C  mod N，
           

再看看上面推出的公式（1）

P^E mod N   =    C^(kφ(n)+1) mod N   --------- (1)
           

聯立得：

P^Emod N = C mod N    -------------(2)
           

（二）第二種情況：

C與N不互質。

N等于兩個質數p與q的乘積，既然C與N不互質，那麼其兩數必有公因數，即C與N之間有共同的因數，然而N為兩個質數的乘積，是以公因數必為P或Q。

在此，設公因數就為p, 令C為sp,則s在1到q之間。

由費馬定理得到：

C^(q-1) = 1 mod q
   C^k(q-1)(p-1)= 1 mod q
   C^kφ(n)=1 mod q     -------------(3)
           

另外，由于p為C的因數，則p必整除于C，由q整除于C，

由 C^kφ(n)=1 mod q -------------(3)，兩邊乘C，得到

C^(kφ(n)+1)=C mod q
           

由于前面提到，p,q為C的因數，是以

C mod q =0        ----------------(4)
 C^(kφ(n)+1)=C ^ED   ------- (由（0）式可得）
 C^ED = 0        -------------------(5)
           

由于p整除于C。是以，推出（4）（5）式

C^ED=0   ---------------(5)
   C mod p=0  --------------(4)
           

聯立得出：

C^ED = C  mod  p = 0 --------(6)
           

由中國剩餘定理，以及之前的1,2,3,6式得出：

C^ED = C mod N
   P^D mod N = C mod N
   C mod N = C----------(7)
           

好了，到（7）式這裡，已經完成了一切的證明，如果你有心從頭看到尾的話，這就是最後一步。

将最開始的第（2）式與第（7）式聯立：

P^E mod N = C mod N    -------------(2)
   C mod N = C----------(7)
           

聯立得解密公式:

P^E mod N = C  --------------推出加密公式
   明文^公鑰(mod公共模數）=密文
           

好，推出了結論，不過教材上的實在太複雜了，沒基礎的人應該看不到這裡，其實不知不覺就寫了這麼多了。。。就當解題步驟可看可不看吧，網上好像有簡單的，複雜的證明好像更可靠，但，上面的證明可能有問題，畢竟太多了QAQ。

結尾

RSA的基本有關的都講完了，本來還有很多能說，但篇幅有限，上述證明用到了歐拉公式，費馬定理，以及中國剩餘定理，網上很容易搜到和了解。請自己去了解，這是RSA的一小部分知識。感謝閱讀。