RSA公鑰與私鑰運算之演算過程

RSA源起

RSA加密演算法是一種非對稱加密演算法,在現代公開密鑰加密系統中被廣泛使用。RSA是1977年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之,對一極大整數做因數分解愈困難,RSA演算法愈可靠。以上訊息截錄自WiKi

RSA同時也是SSL通訊中很重要的一個演算法,沒有了RSA的話,SSL就不可能得以運行。RSA的觀念是每個人都必須有一把公鑰與一把私鑰,公鑰可以放在網路上傳輸(就算被竊取、監聽也無妨)以及被拿去當加密鑰匙,私鑰要自己好好的保存著,如果不見了那一切都完了。這樣的加密、解密方式,被稱為「非對稱加密演算法」。下圖為:Ron Rivest、Adi Shamir、Leonard Adleman三人的照片。

一家專門研究RSA技術的公司RSA Security提出了8個巨大合成數(RSA-640、RSA-704、RSA-768、RSA-896、RSA-1024、RSA-1536、RSA-2048)讓數學家(電腦)作質因數分解,用來驗證RSA在某個時期的安全性,這些合成數為兩個巨量的質數之相乘積,一般的電腦根本無法進行因數分解。在2009年12月12日,編號為RSA-768宣告分解成功,因此這代表下一個威脅RSA-1024的時代來臨。RSA-768因數分解資訊如下:

1230186684530117755130494958384962720772853569595334792197
3224521517264005072636575187452021997864693899564749427740
6384592519255732630345373154826850791702612214291346167042
9214311602221240479274737794080665351419597459856902143413
=
3347807169895689878604416984821269081770479498371376856891
2431388982883793878002287614711652531743087737814467999489
×
3674604366679959042824463379962795263227915816434308764267
6032283815739666511279233373417143396810270092798736308917

歐拉函數

RSA運算的核心起源於歐拉函數,歐拉函數的定義是在數論中,對正整數n,小於或等於n的正整數中與n互質的總個數(互質的定義請參考WiKi 互質)。此函數以其首名研究者歐拉命名,它又稱為φ函數。舉例來說:

φ(8) = 4; 因為1, 3, 5, 7均和8互質。

在歐拉函數中,有一個特別的狀況,就是如果有兩個整數互為質數時,他們相乘後的積如果恰為n值,那麼可以透過過下列的公式快速的算出互質個數。

n = p \* q;  //令p與q互質
φ(n) = φ(p\*q) = φ(p)\*φ(q) = (p-1)\*(q-1);

假設我們選定p=11, q=13,並確定p與q互為質數,那麼我們可以套用上面的歐拉函數算出下列的結論。

n = 11 \* 13 = 143;
φ(143) = φ(11\*13) = φ(11)\*φ(13) = (11-1)\*(13-1) = 120;

這裡會出現一個重要的結論,我們可以發現n是120,化成2進制就是「1111000」,那也就是說這一個密鑰的基礎長度就是7 bits,這只是實驗性的參數,真正要運用的話,請使用1024 bits或2048 bits。

另外請挑選出一個「隨機整數」e,並套用到1 < e < φ(n),並且挑選到的e與φ(n)必須互質。所以我們挑選e=23,23與120為互質沒錯。

模反元素

又稱為同餘式,例如:23 ≡ 2 (mod 3);這邊純就模反元素應用於RSA演算來討論,也就是:如果有兩個正整數e, n互為「質數」,那麼一定可以找到一個整數d,讓ed被n除的餘數是1,換個方式來說就是ed-1可以被n整除。數學表示式如下:

ed ≡ 1 (mod φ(n))

已經e=23、φ(n)=120,接著我們進行ed ≡ 1 (mod φ(n))的化簡可得到一個二元一次方程式為等價式「eX + φ(n)Y = 1」。二元一次方程式的求解通常需要兩個運算式來代入,但我們可以知道最大公因數的定理:「給予二整數a、b,必存在有整數X、Y使得aX + bY = gcd(a,b)」。因此下面我們將進行擴展式歐幾里得演算法(Extended Euclidean Algorithm)來進行推算。

Extended Euclidean Algorithm Strat
--------------
47X + 30Y =  1 (舉用WiKi - http://goo.gl/WQij6F的例子)
--------------
先利用輾轉相除法運算
--------------
47 = 1 \* 30 + 17
30 = 1 \* 17 + 13
17 = 1 \* 13 +  4
13 = 3 \*  4 +  1 
--------------
換算成餘數等式
--------------
47 - 1 \* 30 = 17
30 - 1 \* 17 = 13
17 - 1 \* 13 =  4
13 - 3 \*  4 =  1
--------------
逆運算
--------------
 1 \* 13 - 3 \*  4 =  1 (抄上面最後一行)
 1 \* 13 - 3 \* (17 - 1 \* 13) = 1 (記住一個觀念,千萬不可以把項式乘開)
 1 \* 13 - 3 \* 17 + (3 \* 13) = 1
-3 \* 17 + 4 \* 13 = 1
-3 \* 17 + 4 \* (30 - 1 \* 17) = 1
-3 \* 17 + (4 \* 30) - (4 \* 17) = 1
 4 \* 30 - (7 \* 17) = 1
 4 \* 30 - 7 \* (47 - 1 \* 30) = 1
 4 \* 30 - (7 \* 47) + (7 \* 30) = 1
-7 \* 47 + (11 \* 30) = 1
--------------
結論:X = -7, Y = 11
--------------

--------------
套用在我們假設的7 bits密鑰範例上:
23X + 120Y = 1
--------------
120 = 5 \* 23 + 5
 23 = 4 \*  5 + 3
  5 = 1 \*  3 + 2
  3 = 1 \*  2 + 1
--------------
換算成餘數等式
--------------
120 - 5 \* 23 = 5
 23 - 4 \*  5 = 3
  5 - 1 \*  3 = 2
  3 - 1 \*  2 = 1
--------------
逆運算
--------------
 1 \*  3 - 1 \* 2 = 1
 1 \*  3 - 1 \* (5 - 1 \*  3) = 1
 1 \*  3 - 1 \* 5 + 1 \* 3 = 1
-1 \*  5 + 2 \* 3 = 1
-1 \*  5 + 2 \* (23 - 4 \*  5) = 1
-1 \*  5 + 2 \* 23 - 8 \* 5 = 1
 2 \* 23 - 9 \* 5 = 1
 2 \* 23 - 9 \* (120 - 5 \* 23) = 1
 2 \* 23 - 9 \* 120 + 45 \* 23 = 1
47 \* 23 - 9 \* 120 = 1
--------------
結論:X = 47, Y = -9
--------------

上述例子算出一個整數解為(47, -3),因此我們得出私鑰就是d=47。

公鑰與私鑰的封裝

在文章中舉的例子,我們可以得到下列參數,這將會是在我們運行RSA時的重要依據。

p = 11 (產生完馬上丟棄)
q = 13 (產生完馬上丟棄)
n = p \* q = 143
φ(n) = 120
e = 23  //encode
d = 27  //decode
公鑰為 (n, e) = (143, 23)
私鑰為 (n, d) = (143, 47)

公鑰與私鑰的驗證

假設A產生出上述的公鑰(143, 23)以及私鑰(143, 47),透過一般純文字的方式將公鑰送給B,B取得到公鑰後,要將訊息文字"X"透過RSA演算法進行公鑰加密運算「m^e ≡ c (mod n)」。

因為 m^e ≡ c (mod n) //message,而X的ASCII是88(10進制)
88^23 ≡ c (mod 143)
c = 121  //RSA加密後的文字

P.S Windows 7之後的小算盤可以開起工程模式進行計算,千萬不要笨到自己用手去算88的23次方,除非你很無聊,詳見下圖。另外我們也可以在圖中發現與明白,我們用超簡單的兩位數質數產生的運算就有多龐大了,可見RSA演算法消耗的CPU運算是很恐怖的。

A收到由B送過來的資料「121」,取出自己的私鑰(143, 47),套用RSA的解密公式進行運算「c^d ≡ m (mod n)」。

因為 c^d ≡ m (mod n) //content
121^47 ≡ c (mod 143)
c = 88  //RSA解密後的文字,即為X的ASCII碼88(10進制),故證明之。

寫在最後

除非n=p*q中的這個n,可以利用某種運算被快速的因數分解,例如這個例子中的n是143,否則RSA演算法要被破解的難度非常之高。在寫這篇文章的此刻,全世界並沒有一個有效率的方式可以進行大型質數的因數分解。如果你很有自信的話,請解一下RSA-1024合成數的因數分解吧,別忘了解開是有大獎的喔!一定會上全世界的頭條新聞!!

RSA-1024 =
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
RSA Algorithm Prime