本文結(jié)構(gòu)：

• 一些基本的數(shù)學(xué)知識(shí)
• RSA的具體過程
• 為什么RSA的私鑰解密一定能得到明文
• RSA算法可靠嗎
• RSA算法的一些其他特征

假設(shè)alice想要通過rsa算法在公網(wǎng)上，將消息加密傳遞給bob，他們應(yīng)該怎么做呢？
分為以下幾個(gè)步驟：
1.bob生成一堆共私鑰，將公鑰在網(wǎng)上公開，私鑰自己保存
2.alice通過bob的公鑰加密明文消息m，得到密文c，并將密文c傳遞給bob
3.bob用自己的私鑰解密密文c，得到明文m

一些基本的數(shù)學(xué)知識(shí)

• 質(zhì)數(shù)（素?cái)?shù)）p：只有1和他本身能被自己整除。
• 互質(zhì)：如果兩個(gè)正整數(shù)，除了1以外，沒有其他公因子，我們就稱這兩個(gè)數(shù)是互質(zhì)關(guān)系
  比如，15和32沒有公因子，所以它們是互質(zhì)關(guān)系。這說明，不是質(zhì)數(shù)也可以構(gòu)成互質(zhì)關(guān)系。
• 歐拉函數(shù)φ(n)：小于n的正整數(shù)中，與n互質(zhì)的整數(shù)的個(gè)數(shù)。例如φ(8)=4（因?yàn)樾∮?的正整數(shù)中只有1,3,5,7與8互質(zhì)）
• 若n為質(zhì)數(shù)，則φ(n)=n-1
• n如果可以分為兩個(gè)質(zhì)數(shù)（p,q）的乘積，則φ(n)=φ(p*q)=φ(p)φ(q)=(p-1)(q-1)
• 歐拉定理：如果兩個(gè)正整數(shù)a和n互質(zhì)，則：

a^φ(n)≡1 mod n。

特別的，當(dāng)n為質(zhì)數(shù)時(shí)： a^(n-1)≡1 mod n

• 模反元素: 如果兩個(gè)正整數(shù)a和n互質(zhì)，那么一定可以找到整數(shù)b，滿足：

a×b≡1 mod n

（ab-1 被n整除，或者說ab被n除的余數(shù)是1）
這時(shí)，b就叫做a的"模反元素"。

RSA的具體過程：

秘鑰的產(chǎn)生

• bob選擇兩個(gè)保密的大質(zhì)數(shù)p和q（這里假設(shè)是p=61,q=53）
• 計(jì)算n=p×q=61×53=3233，φ(n)=φ(p*q)=φ(p)φ(q)=(p-1)(q-1)=60×52=3120
  這里 n的長度就是秘鑰的長度 。3233寫成二進(jìn)制是110010100001，一共有12位，所以這個(gè)密鑰就是12位。
• 選一個(gè)整數(shù)e，滿足1< e < φ(n)，且e與φ(n) 互質(zhì)。
  bob就在1到3120之間，隨機(jī)選擇了17。（實(shí)際應(yīng)用中，常常選擇65537。）
• 求解e關(guān)于φ(n)的模反元素d（由于e與φ(n)互質(zhì)，所以d一定存在）

ed ≡ 1 (mod φ(n)) 等價(jià)于 ed - 1 = kφ(n)，這里就是17d-1 =3120k
很容易求得(d,k)=(2753,-15)，即 d=2753。

• n和e封裝成公鑰，n和d封裝成私鑰
  這個(gè)例子中 n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。

加密

假設(shè)alice要向bob發(fā)送明文信息m，則用bob的公鑰 (n,e) 對(duì)m進(jìn)行加密。
并且加密時(shí)必須將明文進(jìn)行比特串分組，保證每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，即保證m<n。

c ≡ m^e (mod n)

這里m假設(shè)是65，那么可以算出下面的等式：65^17 ≡ 2790 (mod 3233)
于是，c等于2790，alice就把2790發(fā)給了bob。

解密

bob拿到2790以后，就用自己的私鑰(n=3233, d=2753) 進(jìn)行解密。

m ≡ c^d (mod n)

現(xiàn)在，c等于2790，私鑰是(3233, 2753)，那么，bob算出
2790^2753 ≡ 65 (mod 3233)
因此，bob知道了alice加密前的原文就是65。

為什么RSA的私鑰解密一定能得到明文

對(duì)于密文的解密運(yùn)算為：

m ≡ c^d (mod n)

現(xiàn)在來證明上面的公式恒成立。將c ≡ m^e (mod n)代入右邊，可得

右邊=c^d (mod n)=(m^e )^d(mod n) = m^(ed)(mod n)

又由于ed ≡ 1 (mod φ(n))可知必有ed=kφ(n)+1，故有

右邊=m^(ed)(mod n) = m^(kφ(n)+1)(mod n)

下面分兩種情況證明 m^(kφ(n)+1)(mod n) = m：
1）明文m與n互質(zhì)。那么由歐拉定理知

m^φ(n) ≡ 1 mod n
于是 m^( kφ(n) ) ≡ 1 mod n
于是 m^( kφ(n) + 1 ) ≡ m mod n = m

2）明文m與n不互質(zhì)：
m與n不互質(zhì)，說明m與n有公因子。
又因?yàn)閚=pq，且p和q都為質(zhì)數(shù)，所以n的因子只有p,q，那么m與n的公因子只能是p或者q。所以m為p或q的倍數(shù)。
假設(shè)m=tp,(t為一正整數(shù)),且t與q互質(zhì)（若t與q不互質(zhì)，假設(shè)t=kq，則m=tp=kpq=kn，違反了m<n）
因?yàn)閙=tp與q互質(zhì)，由歐拉定理知

m^φ(q)≡ 1 mod q

兩邊同時(shí)取kφ(p)次方，得

[m^φ(q) ]^(kφ(p)) ≡ 1 mod q
==> m^[kφ(q)φ(p)] ≡ 1 mod q
==> m^(kφ(n)) ≡ 1 mod q
==> m^(kφ(n)) = 1 + rq (r為一正整數(shù))
==> m^(kφ(n)+1) = tp(1 + rq) = tp + tprq = m + trn (兩邊同時(shí)乘上m=tp)
==> m^(kφ(n)+1) ≡ m mod n

m ≡ c^d (mod n) 得證。

RSA算法可靠嗎

回顧上面的密鑰生成步驟，一共出現(xiàn)六個(gè)數(shù)字：

　　p(保密)
　　q(保密)
　　n(公開)
　　φ(n)(保密)
　　e(公開)
　　d(保密)

公鑰用到了兩個(gè)（n和e），私鑰用到了兩個(gè)（n和d）。
那么，有無可能在已知n和e的情況下，推導(dǎo)出d？

（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有將n因數(shù)分解，才能算出p和q。

結(jié)論：如果n可以被因數(shù)分解，d就可以算出，也就意味著私鑰被破解
但是大整數(shù)的因數(shù)分解是非常困難的，n越大，算法約安全，目前推薦用的rsa秘鑰長度為2018及上。

"對(duì)極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之，對(duì)一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。

RSA算法的一些其他特征

同秘鑰RSA有乘法同態(tài)。
簡單來說：

假設(shè)：明文m=m1 * m2 , 且c1位m1對(duì)應(yīng)的密文，c2位m2對(duì)應(yīng)密文。
則：m對(duì)應(yīng)的密文m=c1 * c2

原理：

若： A * B = C mod n
則 ：A^d ? B^d=Cd mod n

同價(jià)加密的一些相關(guān)知識(shí)：https://yeasy.gitbooks.io/blockchain_guide/content/crypto/homoencryption.html