RSA演算法原理
本文參考：
RSA演算法原理（一）
RSA演算法原理（二）
輕鬆學習RSA加密演算法原理
（阮老師的原文RSA演算法原理（二） 中的的RSA私鑰解密證明中有一小部分不嚴謹的地方，本文用了另一種證明方法，但是結論一致）
RSA演算法常用於非對稱加密，非對稱加密流程如下：
- （1）乙方生成兩把密鑰(公鑰和私鑰)。公鑰是公開的，任何人都可以獲得，私鑰則是保密的。
- （2）甲方獲取乙方的公鑰，然後用它對信息加密。
- （3）乙方得到加密後的信息，用私鑰解密。
數論基礎
一、素數
素數又稱質數，指在一個大於1的自然數中，除了1和此整數自身外，不能被其他自然數整除的數。這個概念，我們在上初中，甚至小學的時候都學過了，這裡就不再過多解釋了。
二、模運算
模運算即求余運算。「模」是「Mod」的音譯。和模運算緊密相關的一個概念是「同餘」。數學上，當兩個整數除以同一個正整數，若得相同餘數，則二整數同餘。
兩個整數a，b，若它們除以正整數m所得的餘數相等，則稱a，b對於模m同餘，記作: a ≡ b (mod m)；讀作：a同餘於b模m，或者，a與b關於模m同餘。例如：26 ≡ 14 (mod 12)。
三、互質關係
如果兩個正整數，除了1以外，沒有其他公因子，我們就稱這兩個數是互質關係（coprime）。比如，15和32沒有公因子，所以它們是互質關係。這說明，不是質數也可以構成互質關係。
關於互質關係，不難得到以下結論：
- 任意兩個質數構成互質關係，比如13和61。
- 一個數是質數，另一個數只要不是前者的倍數，兩者就構成互質關係，比如3和10。
- 如果兩個數之中，較大的那個數是質數，則兩者構成互質關係，比如97和57。
- 1和任意一個自然數是都是互質關係，比如1和99。
- p是大於1的整數，則p和p-1構成互質關係，比如57和56。
- p是大於1的奇數，則p和p-2構成互質關係，比如17和15。
四、歐拉函數
請思考以下問題：
任意給定正整數n，請問在小於等於n的正整數之中，有多少個與n構成互質關係？（比如，在1到8之中，有多少個數與8構成互質關係？）
計算這個值的方法就叫做歐拉函數，以φ(n)表示。在1到8之中，與8形成互質關係的是1、3、5、7，所以 φ(n) = 4。
φ(n)的計算方法並不複雜，但是為了得到最後那個公式，需要一步步討論。
第一種情況
如果n=1，則 φ(1) = 1 。因為1與任何數（包括自身）都構成互質關係。
第二種情況
如果n是質數，則 φ(n)=n-1 。因為質數與小於它的每一個數，都構成互質關係。比如5與1、2、3、4都構成互質關係。
第三種情況
如果n是質數的某一個次方，即 n = p^k (p為質數，k為大於等於1的整數)，則
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
這是因為只有當一個數不包含質數p，才可能與n互質。而包含質數p的數一共有p^(k-1)個，即1×p、2×p、3×p、…、p^(k-1)×p，把它們去除，剩下的就是與n互質的數。
上面的式子還可以寫成下面的形式：
可以看出，上面的第二種情況是 k=1 時的特例。
第四種情況
如果n可以分解成兩個互質的整數之積，
n = p1 × p2
則
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即積的歐拉函數等於各個因子的歐拉函數之積。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
這一條的證明要用到「中國剩餘定理」，這裡就不展開了，只簡單說一下思路：如果a與p1互質(a < p1)，b與p2互質(b < p2)，c與p1p2互質(c < p1p2)，則c與數對 (a,b) 是一一對應關係。由於a的值有φ(p1)種可能，b的值有φ(p2)種可能，則數對 (a,b) 有φ(p1)φ(p2)種可能，而c的值有φ(p1p2)種可能，所以φ(p1p2)就等於φ(p1)φ(p2)。
第五種情況
因為任意一個大於1的正整數，都可以寫成一系列質數的積。
根據第4條的結論，得到
再根據第3條的結論，得到
也就等於
這就是歐拉函數的通用計算公式。比如，1323的歐拉函數，計算過程如下：
五、歐拉定理
歐拉函數的用處，在於歐拉定理。」歐拉定理」指的是：
如果兩個正整數a和n互質，則n的歐拉函數 φ(n) 可以讓下面的等式成立:
也就是說，a的φ(n)次方被n除的餘數為1。或者說，a的φ(n)次方減去1，可以被n整除。比如，3和7互質，而7的歐拉函數φ(7)等於6，所以3的6次方（729）減去1，可以被7整除（728/7=104）。
歐拉定理的證明比較複雜，這裡就省略了。我們只要記住它的結論就行了。
歐拉定理可以大大簡化某些運算。比如，7和10互質，根據歐拉定理，
已知 φ(10) 等於4，所以馬上得到7的4倍數次方的個位數肯定是1。
因此，7的任意次方的個位數（例如7的222次方），心算就可以算出來。
歐拉定理有一個特殊情況。
假設正整數a與質數p互質，因為質數p的φ(p)等於p-1，則歐拉定理可以寫成
這就是著名的費馬小定理。它是歐拉定理的特例。
歐拉定理是RSA演算法的核心。理解了這個定理，就可以理解RSA。
六、模反元素
還剩下最後一個概念：
如果兩個正整數a和n互質，那麼一定可以找到整數b，使得ab-1被n整除，或者說ab被n除的餘數是1。
這時，b就叫做a的「模反元素」。
比如，3和11互質，那麼3的模反元素就是4，因為 (3 × 4)-1 可以被11整除。顯然，模反元素不止一個， 4加減11的整數倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，則 b+kn 都是a的模反元素。
歐拉定理可以用來證明模反元素必然存在。
可以看到，a的 φ(n)-1 次方，就是a的模反元素。
RSA演算法
密鑰生成的步驟
我們通過一個例子，來理解RSA演算法。假設愛麗絲要與鮑勃進行加密通信，她該怎麼生成公鑰和私鑰呢？
第一步，隨機選擇兩個不相等的質數p和q。
愛麗絲選擇了61和53。（實際應用中，這兩個質數越大，就越難破解。）
第二步，計算p和q的乘積n。
愛麗絲就把61和53相乘。
n = 61×53 = 3233
n的長度就是密鑰長度。3233寫成二進位是110010100001，一共有12位，所以這個密鑰就是12位。實際應用中，RSA密鑰一般是1024位，重要場合則為2048位。
第三步，計算n的歐拉函數φ(n)。
n是質數，則 φ(n)=n-1
n = p1 × p2 φ(n) = φ(p1p2) = φ(p1)φ(p2)=> φ(n) = (p-1)(q-1)
愛麗絲算出φ(3233)等於60×52，即3120。
第四步，隨機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質。
愛麗絲就在1到3120之間，隨機選擇了17。（實際應用中，常常選擇65537。）
第五步，計算e對於φ(n)的模反元素d。
所謂」模反元素」就是指有一個整數d，可以使得ed被φ(n)除的餘數為1。
ed ≡ 1 (mod φ(n))
這個式子等價於
ed - 1 = kφ(n)
於是，找到模反元素d，實質上就是對下面這個二元一次方程求解。(-k = y)
ex + φ(n)y = 1
已知 e=17, φ(n)=3120，
17x + 3120y = 1
這個方程可以用「擴展歐幾里得演算法」(又叫輾轉相除法)求解，此處省略具體過程。總之，愛麗絲算出一組整數解為 (x,y)=(2753,-15)，即 d=2753。
至此所有計算完成。
第六步，將n和e封裝成公鑰，n和d封裝成私鑰。
在愛麗絲的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。
實際應用中，公鑰和私鑰的數據都採用ASN.1格式表達。
RSA演算法的可靠性
回顧上面的密鑰生成步驟，一共出現六個數字：
p
q n φ(n) e d
這六個數字之中，公鑰用到了兩個（n和e），其餘四個數字都是不公開的。其中最關鍵的是d，因為n和d組成了私鑰，一旦d泄漏，就等於私鑰泄漏。
那麼，有無可能在已知n和e的情況下，推導出d？
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。 （3）n=pq。只有將n因數分解，才能算出p和q。
結論：如果n可以被因數分解，d就可以算出，也就意味著私鑰被破解。
可是，大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。維基百科這樣寫道：
「對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。
假如有人找到一種快速因數分解的演算法，那麼RSA的可靠性就會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。」
舉例來說，你可以對3233進行因數分解（61×53），但是你沒法對下面這個整數進行因數分解。
12301866845301177551304949 58384962720772853569595334 79219732245215172640050726 36575187452021997864693899 56474942774063845925192557 32630345373154826850791702 61221429134616704292143116 02221240479274737794080665 351419597459856902143413
它等於這樣兩個質數的乘積：
33478071698956898786044169
84821269081770479498371376 85689124313889828837938780 02287614711652531743087737 814467999489 × 36746043666799590428244633 79962795263227915816434308 76426760322838157396665112 79233373417143396810270092 798736308917
事實上，這大概是人類已經分解的最大整數（232個十進位位，768個二進位位）。比它更大的因數分解，還沒有被報道過，因此目前被破解的最長RSA密鑰就是768位。
RSA演算法的加密和解密
有了公鑰和密鑰，就能進行加密和解密了。
(1)加密要用公鑰(n,e)
假設鮑勃要向愛麗絲髮送加密信息m，他就要用愛麗絲的公鑰 (n,e) 對m進行加密。這裡需要注意，m必須是整數（字元串可以取ascii值或unicode值），且m必須小於n。
所謂」加密」，就是算出下式的c：
me ≡ c (mod n)
愛麗絲的公鑰是 (3233, 17)，鮑勃的m假設是65，那麼可以算出下面的等式：
65^17 ≡ 2790 (mod 3233)
於是，c等於2790，鮑勃就把2790發給了愛麗絲。
(2)解密要用私鑰(n,d)
愛麗絲拿到鮑勃發來的2790以後，就用自己的私鑰(3233, 2753) 進行解密。可以證明，下面的等式一定成立：
cd ≡ m (mod n)
也就是說，c的d次方除以n的餘數為m。現在，c等於2790，私鑰是(3233, 2753)，那麼，愛麗絲算出
2790^2753 ≡ 65 (mod 3233)
因此，愛麗絲知道了鮑勃加密前的原文就是65。
至此，」加密–解密」的整個過程全部完成。
我們可以看到，如果不知道d，就沒有辦法從c求出m。而前面已經說過，要知道d就必須分解n，這是極難做到的，所以RSA演算法保證了通信安全。
你可能會問，公鑰(n,e) 只能加密小於n的整數m，那麼如果要加密大於n的整數，該怎麼辦？有兩種解決方法：一種是把長信息分割成若干段短消息，每段分別加密；另一種是先選擇一種」對稱性加密演算法」（比如DES），用這種演算法的密鑰加密信息，再用RSA公鑰加密DES密鑰。
私鑰解密的證明
最後，我們來證明，為什麼用私鑰解密，一定可以正確地得到m。也就是證明下面這個式子：
因為，根據加密規則
由於於是，c可以寫成下面的形式：
將c代入要我們要證明的那個解密規則：
觀察可知，等式左邊的多項式拆開以後，只要是有kn的項都能被n整除，所以可以去掉所有含有kn的項，即等同於求證
由於
所以
將ed代入：
接下來，分成兩種情況證明上面這個式子。
m與n互質
根據歐拉定理，此時
根據加密規則我們有m < n，所以給等式同時乘m，得到
原式得到證明。
m與n不是互質關係
當m與n不互質時(m < n)，由於n=p * q, 那麼 gcd(m,n) = p 或者 gcd(m,n)=q，跟阮老師在這裡假設的一樣
此時，m必然與q互質.
(1)根據費馬小定理，當m與q互質時，我們可以得到
(2)類似之前的式子，我們可以推導出
(3)根據之前的式子我們可以進行如下推倒
(4)改寫這個等式到
兩邊乘上 m,得到
(5)最後一步
原式得證！
應用
取質數13和7.它們的結果給我們的最大值為91.我們取5為公鑰。然後用我們已知的事實7和13是91的因子並且運用拓展歐幾里得演算法（輾轉相除法），我們得到私鑰是29。
這些參數（max:91,pub:5,priv:29）定義一個充分實用型RSA系統。你能取一個數字並且用它乘以它自己5次來加密它，然後取那個數字並且用它乘以它自己29次然後你得回了原來的數字。所以公鑰就是 (91, 5)，私鑰就是（91, 29）。
用這些標準來加密信息「CLOUD」。
為了用數字表示這個信息，我們要把字母轉換成數字。拉丁字母表的通常代表是UTF-8.每個字母相當於一個數字。
在這次編碼下，CLOUD是67,76,79,85,68。每個這些數字小於我們的最大值91，所以我們可以單獨地加密它們。讓我們開始第一個字母。
這意味著67（或C）的加密值是58.
對每個字母重複這個過程，我們得到加密信息CLOUD變成：58,20,53,50,87
根據公式解密
希望能和對區塊鏈感興趣的朋友多多交流，我的blog地址：
DinghaoLI
推薦閱讀：
