非對稱加密算法RSA 學習

2020 年 3 月 2 日
筆記

非對稱加密算法RSA 學習

RSA加密算法是一種非對稱加密算法。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

1973年，在英國政府通訊總部工作的數學家克利福德·柯克斯（Clifford Cocks）在一個內部文件中提出了一個相同的算法，但他的發現被列入機密，一直到1997年才被發表。

對極大整數做因數分解的難度決定了RSA算法的可靠性。 換言之，對一極大整數做因數分解愈困難，RSA算法愈可靠。假如有人找到一種快速因數分解的算法的話，那麼用RSA加密的信息的可靠性就肯定會極度下降。 但找到這樣的算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強力方式解破。到目前為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。

一、舉一個通俗易懂的例子

看一個數學小魔術：

讓A寫下一個任意3位數，並將這個數和91相乘；然後將積的最後三位數告訴B，這樣B就可以計算出A寫下的是什麼數字了。

比如A寫下的是123，並且A計算出123 * 91等於11193，並把結果的末三位193告訴B ；
B只需要把193再乘以11，193 * 11 = 2123 末三位就是A寫下的數字了；

道理很簡單，91乘以11等於1001，而任何一個三位數乘以1001後，末三位顯然都不變（例如123乘以1001就等於123123）。

知道原理後，可以構造一個定義域和值域更大的加密解密系統。
例如：

任意一個數乘以400000001後，末8位都不變，而400000001 = 19801 * 20201。於是A來乘以19801，B來乘以20201，又一個加密解密不對稱的系統就構造好了；
甚至可以構造得更大一些 4000000000000000000000000000001 = 1199481995446957 * 3334772856269093，這樣我們就成功構造了一個30位的加密系統；

如果僅僅按照上面的思路，如果對方知道原理，非常容易窮舉出400000001這個目標值；RSA算法使用的是指數和取模運算，本質上就是上面這套思想。

此段落轉載自：
如何用通俗易懂的話來解釋非對稱加密?

二、一句話：

對極大整數做因數分解的難度決定了RSA算法的可靠性。

三、RSA加密算法

3.1、維基百科——RSA加密算法

先看一下維基百科的算法描述：

公鑰與私鑰的產生

1、隨意選擇兩個大的質數 p和 q，p不等於 q，計算 N=pq
2、根據歐拉函數，求得 r

r = φ(N) = φ(p)φ(q) = (p-1)(q-1)

3、選擇一個小於r並與r互質的整數e，求得e關於r的模反元素，命名為d （ ed ≡ 1(mod r) 模反元素存在，當且僅當e與r互質）；
4、銷毀p和q，此時 (N , e)是公鑰，(N, d)為私鑰；

加密消息

假設Bob想給Alice發送一個消息 n，他知道Alice產生的 N和 e ；用下面這個公式他可以將 n加密為 c ：

c ≡ n^e (mod N)

計算 c並不複雜。Bob算出 c後就可以將它傳遞給Alice。

解密消息

Alice得到Bob的消息 c後就可以利用她的密鑰d來解碼。可以用以下這個公式來將 c轉換為 n：

n ≡ c^d (mod N)

此段落轉載自：
維基百科——RSA加密算法

3.2、依照算法公式舉個例子

依照算法公式來舉個例子

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

質數定義：

除了1和該數自身外，無法被其他自然數整除的數。

舉例：

p = 3；  q = 5;  N = 3*5 = 15;

2、根據歐拉函數，求得 r

r = φ(N) = φ(p)φ(q) = (p-1)(q-1)。

歐拉函數 定義：

歐拉函數 φ(n)是小於或等於n的正整數中與n互質的數的數目。    例如：φ(8) = 4，因為1,3,5,7均和8互質。

舉例：

r = φ(N) = φ(p)φ(q) = (p-1)(q-1) ;    r = φ(15) = φ(3)φ(5) = (3-1)(5-1) ;  r = 8

3、選擇一個小於r並與r互質的整數e，求得e關於r的模反元素，命名為d （ ed ≡ 1(mod r) 模反元素存在，當且僅當e與r互質）；

互質定義：

如果兩個或兩個以上的整數的最大公約數是 1，則稱它們為互質    例如：1,3,5,7均和8互質

模反元素 定義：

如果兩個正整數a和n互質，那麼一定可以找到整數b，使得 ab-1 被n整除，或者說ab被n除的餘數是1。    例如：比如3和5互質，3關於5的模反元素就可能是2，因為 (3*2)%5=1 。

舉例：

// 選擇一個小於r並與r互質的整數e (1,3,5,7均和8互質)：  e = 7;  // 求得e關於r的模反元素，命名為d （    ed ≡ 1(mod r)     )    ed ≡ 1(mod r) ;    7*d ≡ 1(mod 8) ;  7*d%8 = 1;  // 這裡取d = 15  d = 15；

4、銷毀p和q，此時 (N , e)是公鑰，(N, d)為私鑰

// 公鑰  (N , e)  ( 15,7 )  // 私鑰 (N, d)  ( 15,15 )

5、加密

假設Bob想給Alice發送一個消息 n，他知道Alice產生的 N和 e ；用下面這個公式他可以將 n加密為 c

舉例：

// 假設  n = 2;  // 計算c  c ≡ n^e (mod N) ;    (c^-1 * n^e)%N = 1 ;  (c^-1 * 2^7)%15 = 1 ;  //  c = 8；

6、解密

Alice得到Bob的消息 c後就可以利用她的密鑰d來解碼。可以用以下這個公式來將 c轉換為 n：

舉例：

// 計算n  n ≡ c^d (mod N)    n ≡ 8^15 (mod 15) ；  (n^-1 * 8^15)%15 = 1 ;  //  n = 2;

參考

如何用通俗易懂的話來解釋非對稱加密?
維基百科——RSA加密算法
 RSA算法詳解