作者：小傅哥
博客：https://

?

沉淀、分享、成長，讓自己和他人都能有所收獲！??

?

• 一、什么是素數

• 二、對稱加密和非對稱加密

• 三、算法公式推導

• 四、關于RSA算法

• 五、實現RSA算法

• 1. 互為質數的p、q

• 2. 乘積n

• 3.  歐拉公式 φ(n)

• 4. 選取公鑰e

• 5. 選取私鑰d

• 6. 加密

• 7. 解密

• 8. 測試

• 六、RSA數學原理

• 1. 模運算

• 2. 最大公約數

• 3. 線性同余方程

• 4. 中國余數定理

• 5. 費馬小定理

• 6. 算法證明

• 七、常見面試題

記得那是我畢業(yè)??后的第一個秋天，申請了域名，搭建了論壇?？上Ш镁安婚L，沒多久進入論壇后就出現各種亂七八糟的廣告，而這些廣告壓根都不是我加的。

這是怎么回事？后來我才知道，原來我的論壇沒有加 HTTPS 也就是沒有 SSL 證書。那這和數學中的素數有啥關系呢？這是因為每一個 SSL 的生成都用到了 RSA 非對稱加密，而 RSA 的加解密就是使用了兩個互為質數的大素數生成公鑰和私鑰的。

這就是我們今天要分享的，關于素數在 RSA 算法中的應用。

一、什么是素數

素數（或質數）指的是大于1的且不能通過兩個較小的自然數乘積得來的自然數。而大于1的自然數如果不是素數，則稱之為合數。例如：7是素數，因為它的成績只能寫成 1 * 7 或者 7 * 1 這樣。而像自然數 8 可以寫成 2 * 4，因為它是兩個較小數字的乘積。

通常在 Java 程序中，我們可以使用下面的代碼判斷一個數字是否為素數；

boolean isPrime = number > 0;
// 計算number的平方根為k，可以減少一半的計算量
int k = (int) Math.sqrt(number);
for (int i = 2; i <= k; i++) {
    if (number % i == 0) {
        isPrime = false;
        break;
    }
}
return isPrime;

二、對稱加密和非對稱加密

假如 Alice 時而需要給北漂搬磚的 Bob 發(fā)一些信息，為了安全起見兩個人相互協(xié)商了一個加密的方式。比如 Alice 發(fā)送了一個銀行卡密碼 142857 給 Bob，Alice 會按照與 Bob 的協(xié)商方式，把 142857 * 2 = 285714 的結果傳遞給 Bob，之后 Bob 再通過把信息除以2拿到結果。

但一來二去，Alice 發(fā)的密碼、生日、衣服尺寸、鞋子大小，都是乘以2的規(guī)律被別人發(fā)現。這下這個加密方式就不安全了。而如果每次都給不同的信息維護不同的秘鑰又十分麻煩，且這樣的秘鑰為了安全也得線下溝通，人力成本又非常高。

所以有沒有另外一種方式，使用不同的秘鑰對信息的加密和解密。當 Bob 想從 Alice 那獲取信息，那么 Bob 就給 Alice 一個公鑰，讓她使用公鑰對信息進行加密，而加密后的信息只有 Bob 手里有私鑰才能解開。那么這樣的信息傳遞就變得非常安全了。如圖所示。

對稱加密	非對稱加密

三、算法公式推導

如果 Alice 希望更安全的給 Bob 發(fā)送的信息，那么就需要保證經過公鑰加密的信息不那么容易被反推出來。所以這里的信息加密，會需用到求模運算。像計算機中的散列算法，偽隨機數都是求模運算的典型應用。

例如；5^3 mod 7 = 6 —— 5的3次冪模7余6

• 5相當于 Alice 要傳遞給 Bob 的信息
• 3相當于是秘鑰
• 6相當于是加密后的信息

經過求模計算的結果6，很難被推到出秘鑰信息，只能一個個去驗證；

5^1 mod 7 = 5
5^2 mod 7 = 3
5^3 mod 7 = 6
5^4 mod 7 = 2
...

但如果求模的值特別大，例如這樣：5^3 mod 78913949018093809389018903794894898493... = 6 那么再想一個個計算就有不靠譜了。所以這也是為什么會使用模運算進行加密，因為對于大數來說對模運算求逆根本沒法搞。

根據求模的計算方式，我們得到加密和解密公式；—— 關于加密和解密的公式推到，后文中會給出數學計算公式。

對于兩個公式我們做一下更簡單的轉換；

從轉換后的公式可以得知，m 的 ed 次冪，除以 N 求求?？梢缘玫?m 本身。那么 ed 就成了計算公鑰加密的重要因素。為此這里需要提到數學中一個非常重要的定理，歐拉定理?！?1763年，歐拉發(fā)現。

歐拉定理：m^φ(n) ≡ 1 (mod n)  對于任何一個與 n 互質的正整數 m，的 φ(n) 次冪并除以 n 去模，結果永遠等于1。φ(n)  代表著在小于等于 n 的正整數中，有多少個與 n 互質的數。

例如：φ(8) 小于等于8的正整數中 1、2、3、4、5、6、7、8 有 1、3、5、7 與數字 8 互為質數。所以 φ(8) = 4 但如果是 n 是質數，那么 φ(n) = n - 1 比如 φ(7) 與7互為質數有1、2、3、4、5、6 所有 φ(7) = 6

接下來我們對歐拉公式做一些簡單的變換，用于看出ed的作用；

四、關于RSA算法

RSA加密算法是一種非對稱加密算法，在公開秘鑰加密和電子商業(yè)中被廣泛使用。

于1977年，三位數學家；羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）設計了一種算法，可以實現非對稱加密。這種算法用他們三個人的名字命名，叫做RSA算法。

1973年，在英國政府通訊總部工作的數學家克利福德·柯克斯（Clifford Cocks）在一個內部文件中提出了一個與之等效的算法，但該算法被列入機密，直到1997年才得到公開。

RSA 的算法核心在于取了2個素數做乘積求和、歐拉計算等一系列方式算得公鑰和私鑰，但想通過公鑰和加密信息，反推出來私鑰就會非常復雜，因為這是相當于對極大整數的因數分解。所以秘鑰越長做因數分解越困難，這也就決定了 RSA 算法的可靠性。—— PS：可能以上這段話還不是很好理解，程序員???????還是要看代碼才能悟。接下來我們就來編寫一下 RSA 加密代碼。

五、實現RSA算法

RSA 的秘鑰生成首先需要兩個質數p、q，之后根據這兩個質數算出公鑰和私鑰，在根據公鑰來對要傳遞的信息進行加密。接下來我們就要代碼實現一下 RSA 算法，讀者也可以根據代碼的調試去反向理解 RSA 的算法過程，一般這樣的學習方式更有抓手的感覺。嘿嘿 抓手

1. 互為質數的p、q

兩個互為質數p、q是選擇出來的，越大越安全。因為大整數的質因數分解是非常困難的，直到2020年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被破解的?！?不知道量子計算機出來以后會不會改變。如果改變，那么程序員又有的忙了。

2. 乘積n

n = p * q 的乘積。

public long n(long p, long q) {
    return p * q;
}

3.  歐拉公式 φ(n)

φ(n) = (p - 1) * (q - 1)

public long euler(long p, long q) {
    return (p - 1) * (q - 1);
}

4. 選取公鑰e

e 的值范圍在 1 < e < φ(n)

public long e(long euler){
    long e = euler / 10;
    while (gcd(e, euler) != 1){
        e ++;
    }
    return e;
}

5. 選取私鑰d

d = (kφ(n) + 1) / e

public long inverse(long e, long euler) {
    return (euler + 1) / e;
}

6. 加密

c = m^e mod n

public long encrypt(long m, long e, long n) {
    BigInteger bM = new BigInteger(String.valueOf(m));
    BigInteger bE = new BigInteger(String.valueOf(e));
    BigInteger bN = new BigInteger(String.valueOf(n));
    return Long.parseLong(bM.modPow(bE, bN).toString());
}

7. 解密

m = c^d mod n

public long decrypt(long c, long d, long n) {
    BigInteger bC = new BigInteger(String.valueOf(c));
    BigInteger bD = new BigInteger(String.valueOf(d));
    BigInteger bN = new BigInteger(String.valueOf(n));
    return Long.parseLong(bC.modPow(bD, bN).toString());
}

8. 測試

@Test
public void test_rsa() {
    RSA rsa = new RSA();
    long p = 3,                         // 選取2個互為質數的p、q
            q = 11,                     // 選取2個互為質數的p、q
            n = rsa.n(p, q),            // n = p * q
            euler = rsa.euler(p, q),    // euler = (p-1)*(q-1)
            e = rsa.e(euler),           // 互為素數的小整數e | 1 < e < euler
            d = rsa.inverse(e, euler),  // ed = φ(n) + 1 | d = (φ(n) + 1)/e
            msg = 5;                    // 傳遞消息 5
            
    System.out.println("消息：" + msg);
    System.out.println("公鑰(n,e)：" + "(" + n + "," + e + ")");
    System.out.println("私鑰(n,d)：" + "(" + n + "," + d + ")");
    
    long encrypt = rsa.encrypt(msg, e, n);
    System.out.println("加密（消息）：" + encrypt);
    
    long decrypt = rsa.decrypt(encrypt, d, n);
    System.out.println("解密（消息）：" + decrypt);
}

測試結果

消息：5
公鑰(n,e)：(33,3)
私鑰(n,d)：(33,7)
加密（消息）：26
解密（消息）：5

• 通過選取3、11作為兩個互質數，計算出公鑰和私鑰，分別進行消息的加密和解密。如測試結果消息5的加密后的信息是26，解密后獲得原始信息5

六、RSA數學原理

整個 RSA 的加解密是有一套數學基礎可以推導驗證的，這里小傅哥把學習整理的資料分享給讀者，如果感興趣可以嘗試驗證。這里的數學公式會涉及到；求模運算、最大公約數、貝祖定理、線性同于方程、中國余數定理、費馬小定理。當然還有一些很基礎的數論概念；素數、互質數等。以下推理數學內容來自博客：https:///2019/10/24/mathematics-principle-of-rsa-algorithm.html

1. 模運算

1.1 整數除法

定理 1 令 a 為整數, d 為正整數, 則存在唯一的整數 q 和 r, 滿足 0?r<d0?r<d, 使得 a=dq+ra=dq+r.

當 r=0r=0 時, 我們稱 d 整除 a, 記作 d∣ad∣a; 否則稱 d 不整除 a, 記作 d?ad?a

整除有以下基本性質:

定理 2 令 a, b, c 為整數, 其中 a≠0a≠0. 則:

• 如果 a∣ba∣b 且 a∣ca∣c, 則 a∣(b+c)a∣(b+c)
• 如果 a∣ba∣b, 則對于所有整數 c 都有 a∣bca∣bc
• 如果 a∣ba∣b 且 b∣cb∣c, 則 a∣ca∣c

1.2 模算術

在數論中我們特別關心一個整數被一個正整數除時的余數. 我們用 a mod m = b a mod m = b 表示整數 a 除以正整數 m 的余數是 b. 為了表示兩個整數被一個正整數除時的余數相同, 人們又提出了同余式(congruence).

定義 1 如果 a 和 b 是整數而 m 是正整數, 則當 m 整除 a - b 時稱 a 模 m 同余 b. 記作 a ≡ b(mod m)

a ≡ b(mod m) 和 a mod m= b 很相似. 事實上, 如果 a mod m = b, 則 a≡b(mod m). 但他們本質上是兩個不同的概念. a mod m = b 表達的是一個函數, 而 a≡b(mod m) 表達的是兩個整數之間的關系.

模算術有下列性質:

定理 3 如果 m 是正整數, a, b 是整數, 則有

(a+b)mod m=((a mod m)+(b mod m)) mod m

ab mod m=(a mod m)(b mod m) mod m

根據定理3, 可得以下推論

推論 1 設 m 是正整數, a, b, c 是整數; 如果 a ≡ b(mod m), 則 ac ≡ bc(mod m)

證明 ∵ a ≡ b(mod m), ∴ (a?b) mod m=0 . 那么

(ac?bc) mod m=c(a?b) mod m=(c mod m?(a?b) mod m) mod m=0

∴ ac ≡ bc(mod m)

需要注意的是, 推論1反之不成立. 來看推論2:

推論 2 設 m 是正整數, a, b 是整數, c 是不能被 m 整除的整數; 如果 ac ≡ bc(mod m) , 則 a ≡ b(mod m)

證明 ∵ ac ≡ bc(mod m)  , 所以有

(ac?bc)mod m=c(a?b)mod m=(c mod m?(a?b)mod m) mod m=0

∵ c mod m≠0 ,

∴ (a?b) mod m=0,

∴a ≡ b(mod m) .

2. 最大公約數

如果一個整數 d 能夠整除另一個整數 a, 則稱 d 是 a 的一個約數(divisor); 如果 d 既能整除 a 又能整除 b, 則稱 d 是 a 和 b 的一個公約數(common divisor). 能整除兩個整數的最大整數稱為這兩個整數的最大公約數(greatest common divisor).

定義 2 令 a 和 b 是不全為零的兩個整數, 能使 d∣ad∣a 和 d∣bd∣b 的最大整數 d 稱為 a 和 b 的最大公約數. 記作 gcd(a,b)

2.1 求最大公約數

如何求兩個已知整數的最大公約數呢? 這里我們討論一個高效的求最大公約數的算法, 稱為輾轉相除法. 因為這個算法是歐幾里得發(fā)明的, 所以也稱為歐幾里得算法. 輾轉相除法基于以下定理:

引理 1 令 a=bq+r, 其中 a, b, q 和 r 均為整數. 則有 gcd(a,b)=gcd(b,r)

證明 我們假設 d 是 a 和 b 的公約數, 即 d∣a且 d∣b, 那么根據定理2, d 也能整除 a?bq=r 所以 a 和 b 的任何公約數也是 b 和 r 的公約數;

類似地, 假設 d 是 b 和 r 的公約數, 即 d∣bd∣b 且 d∣rd∣r, 那么根據定理2, d 也能整除 a=bq+r. 所以 b 和 r 的任何公約數也是 a 和 b 的公約數;

因此, a 與 b 和 b 與 r 擁有相同的公約數. 所以 gcd(a,b)=gcd(b,r).

輾轉相除法就是利用引理1, 把大數轉換成小數. 例如, 求 gcd(287,91) 我們就把用較大的數除以較小的數. 首先用 287 除以 91, 得

287=91?3+14

我們有 gcd(287,91)=gcd(91,14) . 問題轉換成求 gcd(91,14). 同樣地, 用 91 除以 14, 得

91=14?6+7

有 gcd(91,14)=gcd(14,7) . 繼續(xù)用 14 除以 7, 得

14=7?2+0

因為 7 整除 14, 所以 gcd(14,7)=7. 所以 gcd(287,91)=gcd(91,14)=gcd(14,7)=7.

我們可以很快寫出輾轉相除法的代碼:

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

2.2 貝祖定理

現在我們討論最大公約數的一個重要性質:

定理 4 貝祖定理 如果整數 a, b 不全為零, 則 gcd(a,b)是 a 和 b 的線性組合集 {ax+by∣x,y∈Z}中最小的元素. 這里的 x 和 y 被稱為貝祖系數

證明 令 A={ax+by∣x,y∈Z}. 設存在 x0x0, y0y0 使 d0d0 是 A 中的最小正元素, d0=ax0+by0 現在用 d0去除 a, 這就得到唯一的整數 q(商) 和 r(余數) 滿足

又 0?r<d0, d0 是 A 中最小正元素

∴ r=0 , d0∣a.

同理, 用 d0d0 去除 b, 可得 d0∣b. 所以說 d0 是 a 和 b 的公約數.

設 a 和 b 的最大公約數是 d, 那么 d∣(ax0+by0)即 d∣d0

∴∴ d0 是 a 和 b 的最大公約數.

我們可以對輾轉相除法稍作修改, 讓它在計算出最大公約數的同時計算出貝祖系數.

def gcd(a, b):
    if b == 0: return a, 1, 0
    d, x, y = gcd(b, a % b)
    return d, y, x - (a / b) * y

3. 線性同余方程

現在我們來討論求解形如 ax≡b(modm)a 的線性同余方程. 求解這樣的線性同余方程是數論研究及其應用中的一項基本任務. 如何求解這樣的方程呢? 我們要介紹的一個方法是通過求使得方程 ˉaa≡1(modm) 成立的整數 ˉaaˉ. 我們稱 ˉa 為 a 模 m 的逆. 下面的定理指出, 當 a 和 m 互素時, a 模 m 的逆必然存在.

定理 5 如果 a 和 m 為互素的整數且 m>1m>1, 則 a 模 m 的逆存在, 并且是唯一的.

證明 由貝祖定理可知, ∵ gcd(a,m)=1gcd(a,m)=1 , ∴ 存在整數 x 和 y 使得 ax+my=1 這蘊含著 ax+my≡1(modm) ∵ my≡0(modm), 所以有 ax≡1(modm)

∴ x 為 a 模 m 的逆.

這樣我們就可以調用輾轉相除法 gcd(a, m) 求得 a 模 m 的逆.

a 模 m 的逆也被稱為 a 在模m乘法群 Z?mZm? 中的逆元. 這里我并不想引入群論, 有興趣的同學可參閱算法導論

求得了 a 模 m 的逆 ˉa 現在我們可以來解線性同余方程了. 具體的做法是這樣的: 對于方程 ax≡b(modm)a , 我們在方程兩邊同時乘上 ˉa, 得 ˉaax≡ˉab(modm)

把 ˉaa≡1(modm) 帶入上式, 得 x≡ˉab(modm)

x≡ˉab(modm) 就是方程的解. 注意同余方程會有無數個整數解, 所以我們用同余式來表示同余方程的解.

4. 中國余數定理

中國南北朝時期數學著作 孫子算經 中提出了這樣一個問題:

有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

用現代的數學語言表述就是: 下列同余方程組的解釋多少?

孫子算經 中首次提到了同余方程組問題及其具體解法. 因此中國剩余定理稱為孫子定理.

定理 6 中國余數定理 令 m1,m2,…,mn 為大于 1 且兩兩互素的正整數, a1,a2,…,an 是任意整數. 則同余方程組

有唯一的模 m=m1m2…mn 的解.

證明 我們使用構造證明法, 構造出這個方程組的解. 首先對于 i=1,2,…,n, 令

即, MiMi 是除了 mimi 之外所有模數的積. ∵ m1,m2,…,mn 兩兩互素, ∴ gcd(mi,Mi)=1. 由定理 5 可知, 存在整數 yi 是 Mi 模 mi 的逆. 即

上式等號兩邊同時乘 ai 得

就是第 i 個方程的一個解; 那么怎么構造出方程組的解呢? 我們注意到, 根據 Mi 的定義可得, 對所有的 j≠i, 都有 aiMiyi≡0(modmj). 因此我們令

就是方程組的解.

有了這個結論, 我們可以解答 孫子算經 中的問題了: 對方程組的每個方程, 求出 Mi , 然后調用 gcd(M_i, m_i) 求出 yi:

最后求出 x=?2?35+3?21+2?15=23≡23(mod105)

5. 費馬小定理

現在我們來看數論中另外一個重要的定理, 費馬小定理(Fermat's little theorem)

定理 7 費馬小定理 如果 a 是一個整數, p 是一個素數, 那么

當 n 不為 p 或 0 時, 由于分子有質數p, 但分母不含p; 故分子的p能保留, 不被約分而除去. 即 p∣(np).

令 b 為任意整數, 根據二項式定理, 我們有

令 a=b+1, 即得 a^p ≡ a(mod p)

當 p 不整除 a 時, 根據推論 2, 有 a^p?1 ≡ 1(mod p)

6. 算法證明

我們終于可以來看 RSA 算法了. 先來看 RSA 算法是怎么運作的:

RSA 算法按照以下過程創(chuàng)建公鑰和私鑰:

1. 隨機選取兩個大素數 p 和 q, p≠qp≠q;
2. 計算 n=pq
3. 選取一個與 (p?1)(q?1) 互素的小整數 e;
4. 求 e 模 (p?1)(q?1) 的逆, 記作 d;
5. 將 P=(e,n)公開, 是為公鑰;
6. 將 S=(d,n)保密, 是為私鑰.

(1) 式表明, 不僅可以用公鑰加密, 私鑰解密, 還可以用私鑰加密, 公鑰解密. 即加密計算 C=M^d mod n, 解密計算 M=C^e mod n

RSA 算法的安全性基于大整數的質因數分解的困難性. 由于目前沒有能在多項式時間內對整數作質因數分解的算法, 因此無法在可行的時間內把 n 分解成 p 和 q 的乘積. 因此就無法求得 e 模 (p?1)(q?1)的逆, 也就無法根據公鑰計算出私鑰.

七、常見面試題

• 質數的用途
• RSA 算法描述
• RSA 算法加解密的過程
• RSA 算法使用場景
• 你了解多少關于 RSA 的數學數論知識

• RSA加密算法：https://zh./wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
• RSA算法原理：https://www./blog/2013/07/rsa_algorithm_part_two.html
• RSA算法背后的數學原理：https:///2019/10/24/mathematics-principle-of-rsa-algorithm.html
• 萊昂哈德·歐拉：https://en./wiki/Leonhard_Euler