[OpenSSL] RSA非對稱型加解密演算法

RSA為目前在電子商業網路上很常用的加解密演算法，其安全性依靠因數分解，因為對極大整數做因數分解是很困難且花時間的，一般都會採用RSA numbers來產生公鑰(Public Key)和私鑰(Private Key)，目前大多採用1024bits或2048bits。

公鑰和私鑰的產生

1.      隨意選擇兩個大的質數p和q，p不等於q，計算N=p*q。

2.      根據歐拉函式，求得r= φ(N) = φ(p)φ(q) = (p-1)*(q-1)。

3.      選擇一個小於r的整數e，且與r互質。

4.      用以下公式計算d : d*e≡1 (mod(p-1)*(q-1))。

5.      則(N, e)為私鑰，(N, d)則為公鑰。’

加密消息

假設A想傳訊消息(n)給B，則A要利用私鑰(N, e)來把n加密成c，再送出給B。

解密消息

B收到加密消息(c)後，利用公鑰(N, d)可以把原本的加密消息c，解密還原成n。

例如：

1.      選擇(p, q) = (5, 11)，N=5*11=55。

2.      r=4*10=40。

3.      選擇e為7。

4.      則計算出d為23(7*23=161 mod 40 = 1)

5.      欲加密的消息n=2，則c為18。

6.      解密c^23=74347713614021927913318776832 mod 55為2。

RSA整個原理關鍵在歐拉函式，由歐拉定理提到

如果n與a互質，則a的n歐拉函式值次方除以n會餘1，歐拉函數是指小於(p, q)且與(p, q)互質的數總共有幾個，意思是因為我們挑選(p, q)都為質數，質數無法因數分解，小於質數的數都會與質數互質，也就是歐拉函數值為(p-1)和(q-1)，因此得到下列式子

然後可以推得

兩邊乘上a

整個式子的意思是，挑選兩個數字(d, e)乘起來除以r餘1，可以使得a的(r+1)次方除以N餘a。換句話說，從加密解密消息的式子來看，n的e次方得到c，c的d次方得到n，也就是n的(d*e)次方會得到n本身。

破解加密的關鍵在於所選擇的N是不是能夠被快速容易地因數分解，只要知道N是有哪兩個質數相乘，就可以推得r為多少，這樣就可以利用手上的公鑰d，推得私鑰e為多少了！