RSA公鑰私鑰加密演算法

1 數論

1. 一個大於1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數。質數如2、3、5、7
2. 每一個合數都可以以唯一形式被寫成質數的乘積，即分解質因數。
3. 對於大數而言，目前來說沒有很好的分解質因數方法，一般而言，計算機從2開始一個個測試來判斷是否為質因數。
4. 歐拉函數O(n)是小於或等於n的正整數中與n互質的數的數目。
5. 模反元素：如果兩個正整數a和n互質，那麼一定可以找到整數b，使得 ab-1 被n整除，或者說ab被n除的餘數是1。這時，b就叫做a的「模反元素」。比如a=3，n=11;則b=4。實際上4加減11的整數倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即b+kn都是a的模反元素
6. 歐拉定理：即a的O(n)次方與1在模n下同餘；O(n)為歐拉函數。如上n=11，O(n)=10，a的O(n)次方為3的10次方等於=59049=（5368*11 + 1）。（同餘：兩個整數a，b，若它們除以正整數m所得的餘數相等，則稱a， b對於模m同餘，如26等於14(mod12)）

2 RSA演算法

RSA加密演算法是一種非對稱加密技術，即加密時候用的密鑰（公鑰）和解密時用的密鑰（私鑰）不是同一把。

基本原理是將兩個很大的質數相乘很容易得到乘積，但是該乘積分解質因數卻很困難。

也就是說對就計算機來說997210243分解質因數很困難，只能從2、3、5一個個測試。而計算9973 * 99991 = 997210243卻很容易。

3 公鑰與私鑰的產生

1. 隨意選擇兩個大質數p和q，p不等於q，計算出N=p*q
2. 根據歐拉函數，任何質數p的互質數目為p-1，另r=O(N)=O(p)O(q)=(p-1)(q-1)
3. 選擇一個小於r的整數e，另r和e互質，求e關於r的模反元素為d。
4. 將p和q的記錄消除
5. (N, e)為公鑰；（N，d）為私鑰。

如p=11, q=2; 則N=22, r=10。 選擇e=3, d可以為7,17,27（7+10k）

公鑰為(22, 3)， 私鑰為(22, 7)

4 加密消息

原始信息為n，加密動作為：

c = n的e次方 (mod N)

如上例，原始數據6，6的3次方為216， (mod 22) 後為18

註：原始數據n必須小於N，當p和q足夠大的時候是沒問題的

5 解密消息

現在要通過c和私鑰(N,d)將c解密出n。

c的d次方 = n （mod N）

如上例 18的7次方=612220032，(mod 22)後為6； 18的17次方2185911559738696531968，(mod 22)後22也為6

6 安全性

假設偷聽者乙獲得了甲的公鑰N和e以及丙的加密消息c，但她無法直接獲得甲的密鑰d。

根據公式 e*d = 1 (mod (p-1)(q-1))，那麼最簡單的方式就是分解N的質因數p和q。

但至今為止還沒有人找到一個多項式時間的演算法來分解一個大的整數的因子，同時也還沒有人能夠證明這種演算法不存在。

7 參考

維基百科：質因數分解

維基百科：模反元素

維基百科：歐拉函數

維基百科：歐拉定理

維基百科：RSA加密解密演算法

推薦閱讀：