RSA原理其實沒有想象的那么難。對于這篇文章，有數(shù)論的基礎(chǔ)更好，沒有的話只要不糾結(jié)具體的數(shù)學(xué)定理如何證明，應(yīng)該也可以看懂。
一、數(shù)學(xué)準(zhǔn)備
首先要準(zhǔn)備一下如下數(shù)學(xué)概念和原理。
1.質(zhì)數(shù)：只能分解成1和它自身乘積的，大于1的自然數(shù)。
2.互質(zhì)：最大公因數(shù)是1的多個自然數(shù)之間就是互質(zhì)關(guān)系。注意，互質(zhì)的整數(shù)不一定都是質(zhì)數(shù)。
3.模運算：mod，即計算余數(shù)的運算，如x mod yn，表示x除以y的余數(shù)是n。
上述數(shù)學(xué)概念都是中學(xué)學(xué)過的，下面的定理就進入數(shù)論部分了。
4.歐拉函數(shù)：對于自然數(shù)n，計算在小于等于n的自然數(shù)中，與n互質(zhì)的數(shù)字的個數(shù)的函數(shù)。歐拉函數(shù)一般寫成φ(n)。歐拉函數(shù)的計算公式：φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),其中p1, p2……pn為n的所有質(zhì)因數(shù)，n是不為0的整數(shù)。另外，定義 φ(1)=1。
歐拉函數(shù)有以下重要特性：
如果n是質(zhì)數(shù)p的k次方，即n=p^k，則φ(n)=p^k-p^(k-1)。這個定理不難理解，因為在1到n這n個數(shù)里，是p的倍數(shù)有1*p，2*p，3*p直到(p^(k-1))*p，一共p^(k-1)個，其他數(shù)都和p^k互質(zhì)。比如n=8時，8=2^3，φ(8)=2^3-2^(3-1)=8-4=4.如果n是質(zhì)數(shù)，則 φ(n)=n-1。因為質(zhì)數(shù)與小于它的每一個數(shù)，都構(gòu)成互質(zhì)關(guān)系。比如φ(7)=6。如果n可以分解成兩個互質(zhì)的整數(shù)之積，即 n = p * k ，則 φ(n)=φ(p*k)=φ(p) *φ(k)，這個定理也可以從上面的歐拉函數(shù)計算公式得出。5.歐拉定理
這個定理是RSA算法的核心：如果兩個正整數(shù)m和n互質(zhì)，則有如下公式：
m^(φ(n))≡1(mod n)或
m^(φ(n)) mod n≡1
即m^(φ(n))除以n，得到余數(shù)1.
歐拉定理的證明這里就不展開了，有興趣的同學(xué)自行百度即可。如果n為質(zhì)數(shù)，則 φ(n)=n-1，上述歐拉定理公式可改為：
m^(n-1)≡1(mod n)或
m^(n-1) mod n ≡1
這就是著名的費馬小定理。
6. 模反元素：如果兩個正整數(shù)e和x互質(zhì)，那么一定可以找到整數(shù)d，滿足下列公式：
e*d≡1(mod x)或
e*d mod x ≡1
那么d就是e相對于x的模反元素。
7.模運算規(guī)則：根據(jù)模運算規(guī)則有如下公式
(a*b) mod n =(a mod n * b mod n) mod n
以及
若a≡b (mod p)，則對于b*c<p，都有(a * c) ≡ (b * c) (mod p)
二、算法推演
1.根據(jù)模運算規(guī)則，在歐拉定理公式上拓展，先將m^(φ(n))進行k次方：
m^(k*φ(n)) mod n=(m^(φ(n)))^k mod n=(m^φ(n) mod n)^k mod n=1^k mod n≡1
等式兩邊再乘以m(m<n)：
m^(k*φ(n)+1) mod n=(m^(k*φ(n))*m) mod n ≡1*m =m
2.根據(jù)模反元素定義，如果找到一個與φ(n)互斥的自然數(shù)e，則一定存在e相對于φ(n)的模反元素d，使得e*d=k*φ(n)+1，代入上面的公式，我們終于得到了RSA加密的雛形：
m^(e*d) mod n≡m
3.根據(jù)模運算性質(zhì)，上述公式可以做如下變換：
m^(e*d) mod n=(m^e)^d mod n=(m^e mod n)^d mod n≡m
然后拿出來m^e mod n，令它等于c，則最終得到：
m^e mod n=c （加密）
c^d mod n=m （解密）
至此，已經(jīng)很明顯了，第一個公式 就是加密，把明文m加密成密文c，第二個公式就是解密，把c解密回m，e和n組成公鑰，d和n組成私鑰。
4.公私鑰計算過程
計算公私鑰就是求出e，d和n，計算的依據(jù)就是模反元素公式e*d=k*φ(n)+1。
首先n的長度就是我們平常說的RSA密鑰長度，在實際應(yīng)用中，為了快速計算，n都會由兩個大質(zhì)數(shù)相乘而得。比如這里我們隨機選擇兩個質(zhì)數(shù)：79和97，即n=79*97=7663，則根據(jù)歐拉函數(shù)性質(zhì)，φ(n)=(79-1)*(97-1)=78*96=7488；e要與n互質(zhì)，并小于n，這里選擇了17（實際應(yīng)用中，e被稱為公鑰指數(shù)，常常選擇3或65537），代入到模反元素公式：17*d=7488*k+1，這是 個二元一次方程，有多個解，這里面取d=881，k=2這一組解。這樣，我們就得到了私鑰(881,7663)，公鑰(17,7663)。
用上述密鑰驗算一遍。m取值62，則密文c=62^17 mod 7663=7602，解密時7602^881 mod 7663=62=m。
三、幾點說明
1.算法推演中 m^(e*d) mod n≡m的公式是當(dāng)m與n互質(zhì)時直接用歐拉定理公式轉(zhuǎn)換過來的。實際上，如果n取值為兩個質(zhì)數(shù)的乘積，則只要m小于n， m^(e*d) mod n≡m一樣成立。證明過程自行搜索，并不難。
2.e和d的完全對等，可以互換。將上述加解密過程中的e和d位置互換，即加密用(d,n)，解密用(e,n)，整個過程依然正確。
3.n的取值是整個算法的安全保證。攻擊者如果想計算出私鑰中的d，他需要先計算出，而n是兩個質(zhì)數(shù)的乘積，攻擊者如果不想一個個數(shù)出與n互質(zhì)的數(shù)，那他就需要分解出這兩個質(zhì)數(shù)。這個分解過程是相當(dāng)相當(dāng)相當(dāng)困難的，而且是數(shù)字越大越困難（當(dāng)然，在量子計算面前，可能這些都不是事），但分解的結(jié)果又是存在且只有一個的。上面的例子79*97是很小的，實際應(yīng)用中RSA密鑰長度至少要從1024位起（國內(nèi)要求2048位起），因此1024位及其以上的密鑰，實際上是一個大整數(shù)。
4. RSA只能加密小于n的整數(shù)m，那么如果要加密大于n的整數(shù)，有兩種解決方法：一種是把明文分割成若干段短消息，每段分別加密；另一種是就是數(shù)字信封，即RSA算法加密用來加密明文的對稱密鑰，而非明文本身。
