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?dinghaoli.github.io 推薦閱讀: 相关文章 {{#data}} {{title}} {{/data}}