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稍微用表格表示一下步驟
稍微用表格表示一下步驟：

表中有好幾個重要的量，一共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的一小部分知識，感謝閱讀，