RSA加密演算法是一種非對稱加密演算法,在公開金鑰加密和電子商業中被廣泛使用。
RSA是由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)在1977年一起提出的。當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。
RSA 基於數學難題所設計出來的演算法,對極大整數無法進行因數分解的難題,證實 RSA 演算法的可靠性。
有些幾個觀念和名詞大家小時候就念過了(?) 這邊複習一下
大於1的自然数中,除了1和該数自身外,無法被其他自然数整除的数(也可定義為只有1與該數本身两个正因数的数)。
p.s 大於1的自然數若不是質數,則稱之為合數
5是質數,其正因數只有1與5。
6是個合數,除了1與6外,2與3也是其正因數
如果兩個或兩個以上的整數的最大公因數是 1,則稱它們為互質
8 與 10 的最大公因數是 2,不是 1,因此它們並不互質
又例如 7, 10, 13 的最大公因數是 1,因此它們互質
注意一點,並不需要兩個或兩個以上的數互質,但本身卻不一定是質數;上述例子 10 不是質數,但依然與 13 互質
就是先做指數在做模除
又稱為指數運算、冪運算(Exponentiation)
表達式為 讀作「的 次方」或「的次冪」。
其中, b稱為底數,而稱為指數,等同於自乘次。
又稱模數、取模操作、取模運算等(modulo / modulus),口語稱為除餘
讓m去被n整除,只取所得的餘數作為結果。
以表達式為 『 5 mod 2 』 得到 1 同理 26 mod 6 =2; 28 mod 2 = 0 等等
先做指數運算在做模除運算
b底數 = 4 , n指數為3 m模除 = 3 求 c 運算如下
是小於或等於n的正整數中與n互質的數的數目
又稱為φ函數
例子:,因為1,3,5,7 有四個質數和8互質。
歐拉定理表明,若 n,a 為正整數,且 n,a 互質,則
即 與1在模n下同餘 , 為歐拉函數。
用簡單的例子。令,,此兩數為互質正整數。
小於等於5的正整數中與5互質的數有4個(1、2、3和4)
所以(詳情見歐拉函數)
計算: (詳情請看同餘)
兩個整數,,若它們除以正整數所得的餘數相等,則稱,對於模同餘
記作
讀作同餘於模,或讀作與關於模同餘。
比如
複習一下前面的章節,公開金鑰密碼系統 (Public-key cryptosystem) 加密跟解密使用不同的金鑰 ,又稱『非對稱式加密系統』(asymmeric cryptosystem )
接收者先產生公鑰(Public-key)及私鑰 (Private-key 或 Secret-key)
非對稱式加密 特性就是 公鑰 加密上鎖後,無法在用公鑰解開,只能用**私鑰
** 解鎖
選出兩個較大的質數 p 和 q
計算兩個質數的乘積 n = p × q
計算出小於 n 且與 n 互質的整數個數
= (p - 1)(q - 1)
選出一個整數 e (拿來當做公鑰)
計算 d (私鑰)
可得
我們找到了通過隨機選擇的互質的 p和q 計算得到 n、m、e、d,我們把這些數字分為兩組
分別為公鑰組{e, n}和私鑰組 {d, n}
e是公鑰{e, n} = (17,3233)
d 是私鑰 {d, n}==(2753,3233)
由於RSA 演算法式數值的運算,所以開始需要把資料字串化,使用ascii code、unicode code、utf-8編碼等將字串轉換為數字
轉換後數字X 需要小於密鑰組中 n 的長度,如長度大於n則需要進行拆分
就是會常聽到的欲要加密資料太大需要先切割,分組處理就是因為這個原因
x 的 e 次方 除以 n 求餘數 y ,c 為加密的密文
可寫為
x 為明文轉化後的數字,
e為公鑰
,n 為整數(p * q),y 為密文,mod 模除
y 的 e 次方 除以 n 求餘數 x
可寫為
因此計算出的餘數就可還原 x 明文
y 為密文,
d 為私鑰
,n 為整數(p * q),x 為密文,mod 模除
傳遞的資料 (公開場合傳遞資料)
解密需要資料
由於沒有 d (私鑰)
因此無法解密
這時候可能會提問說,那我用 e 去計算出 d 不行嗎?
我們來看看要怎麼反推
假如有人找到一種快速因數分解的演算法的話,那麼用 RSA 加密的訊息就會被破解。
但找到這樣的演算法的可能性是非常小的。至今只有過短的 RSA 金鑰才可能被暴力破解
到目前為止,世界上還沒有任何可靠的攻擊RSA演算法的方式可以破解 1024bit 的金鑰。
因此現今只金鑰長度超過1024bit,即是安全的,但因為 768 bits 被破解威脅到 1024bit 的金鑰
建議至少使用 2048 bit 的金鑰
寫出這篇,讓我重新複習,RSA 有用到演算法
歐拉定理跟歐拉函數那邊確實讓我小卡了一陣子
整理完,也讓我重新對RSA 有更清新個認識,希望這篇有幫助到讀者
https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
https://zh.wikipedia.org/wiki/%E4%BA%92%E8%B3%AA
https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4
https://zh.wikipedia.org/wiki/%E5%86%AA
https://kknews.cc/zh-tw/news/88nx8l.html
https://cloud.tencent.com/developer/article/1693368
https://www.itread01.com/content/1544974928.html
http://mslab.csie.asia.edu.tw/~jackjow/courses/992_InfoSecurity/ppts/IS_RSA.pdf
https://www.youtube.com/watch?v=G8ZU6vGymnI&ab_channel=PN777
https://www.codecogs.com/latex/eqneditor.php
https://www.youtube.com/watch?v=D_kMadCtKp8&ab_channel=%E6%9D%8E%E6%B0%B8%E4%B9%90%E8%80%81%E5%B8%88
https://www.youtube.com/watch?v=3xgBnD_VsM8&ab_channel=%E5%BC%B5%E5%A4%A7%E5%93%A5
感謝羊小咩的分享,學到不少!
不過這邊有小錯誤:
解密
y 的 e 次方 除以 n 求餘數 x
這裡應該是 y 的 d 次方喔~
公式:
xᵉ(mod n) = y
yᵈ(mod n) = x
例子 (x 代 98):
98¹⁷(mod 3233) = 2570
2570²⁷⁵³(mod 3233) = 98