密碼學(xué)基礎(chǔ)1：RSA算法原理全面解析

網(wǎng)上寫 RSA 算法原理的文章不少，但是基本上要么忽略了數(shù)學(xué)原理的說明，要么缺少實(shí)際的可運(yùn)行的例子，為此特寫了此文皮官，將 RSA 需要用到的數(shù)學(xué)概念和定理都總結(jié)了一番，并基于算法原理使用 python 實(shí)現(xiàn)了 RSA 密鑰生成和加解密的demo实辑，希望對(duì)大家深入了解 RSA 算法有所幫助捺氢。本文第 1 節(jié)為 RSA 相關(guān)的數(shù)論基礎(chǔ)，第 2 節(jié)是 RSA 算法原理描述和證明剪撬，第 3 節(jié)通過 openssl 生成 RSA 密鑰來分析實(shí)際應(yīng)用中的密鑰格式摄乒。可以直接從第 2 節(jié)開始，遇到相關(guān)定理可以轉(zhuǎn)到第 1 節(jié)處查閱即可馍佑。本文所有代碼都在 shishujuan:rsa-algrithm斋否，如有錯(cuò)誤，也懇請(qǐng)指正拭荤。

1 數(shù)論基礎(chǔ)

本節(jié)內(nèi)容中可能用到的符號(hào)說明如下：

$\Bbb Z$ : 指代整數(shù)集合茵臭，包括正負(fù)整數(shù)和0。
$\Bbb Z_n$ : 指代 0 到 n-1 之間的整數(shù)集合舅世。
$|a|$ ：數(shù) a 的絕對(duì)值旦委。
$?a/n?$ : 指代小于等于 a/n 的最大整數(shù)，比如 ?5/3? = 1歇终，?8/3? = 2 等社证。
質(zhì)數(shù)：質(zhì)數(shù)在有些地方又翻譯為素?cái)?shù)，本文統(tǒng)一用質(zhì)數(shù)表述评凝。
$p^{-1}_q$ ：p 對(duì)模數(shù) q 的模逆元素追葡，即 $\small p^{-1}_q p \equiv 1(mod ~q)$
乘法符號(hào)：文中可能在證明和示例中用了不同的乘法符號(hào)如 $\times$ ， $\cdot$ 奕短，意義一致宜肉。

1.1 質(zhì)數(shù)和合數(shù)

質(zhì)數(shù)和合數(shù)： 質(zhì)數(shù)是指除了平凡約數(shù)1和自身之外，沒有其他約數(shù)的大于1的正整數(shù)翎碑。大于1的正整數(shù)中不是素?cái)?shù)的則為合數(shù)谬返。如 7、11 是質(zhì)數(shù)日杈，而 4遣铝、9 是合數(shù)。在 RSA 算法中主要用到了質(zhì)數(shù)相關(guān)性質(zhì)莉擒，質(zhì)數(shù)可能是上帝留給人類的一把鑰匙酿炸，許多數(shù)學(xué)定理和猜想都跟質(zhì)數(shù)有關(guān)。

1.2 除法定理

[定理1] 除法定理： 對(duì)任意整數(shù) a 和任意正整數(shù) n涨冀，存在唯一的整數(shù) q 和 r填硕，滿足 $0<=r<n，a = qn + r$ 鹿鳖。其中扁眯， $q = ?a/n?$ 稱為除法的商，而 $r = a ~mod ~ n$ 稱為除法的余數(shù)翅帜。

[證明] 除法定理

存在性證明
設(shè)集合 $S=\{a - xn姻檀，x \in \Bbb Z\}$ ，則可以知道集合 S 中一定存在非負(fù)元素涝滴，設(shè)這個(gè)非負(fù)整數(shù)集合為 T施敢，根據(jù)自然數(shù)的良序法則周荐，非空自然數(shù)集合中必然存在最小元素。設(shè) $r = a-qn$ 為集合 T 中的最小元素僵娃，因?yàn)榧?T 是非負(fù)整數(shù)集合概作，因此 $r >= 0$ 。而 r 必然滿足 $r < n$ 默怨，因?yàn)? $r >= n \implies r-n>=0$ 讯榕，則可以推出元素 $r - n \in T$ 。但是 $r - n < r$ 匙睹，這與我們定義的 r 是集合 T 中最小的元素矛盾愚屁，因此 $r < n$ 。這也就證明了 q 和 r 的存在性痕檬，即一定存在 q 和 r霎槐，且 $0 <= r < n$ 。

唯一性證明
假設(shè)有兩組不同的整數(shù) $q_1, r_1$ 和 $q_2, r_2$ 滿足條件梦谜，則有 $a = q_1n + r_1丘跌，a = q_2n + r_2( 0 <= r_1, r_2 < n)$
兩個(gè)式子相減可得
$r_2 - r_1 = n(q_1 - q_2)$
左邊絕對(duì)值 $|r_2 - r_1| < n$ ，但是右邊絕對(duì)值 $|n(q_1-q_2)|$ 顯然是 n 的整數(shù)倍唁桩，因此只能 $q_1 = q_2$ 闭树，繼而可得 $r_1 = r_2$ ，由此唯一性得證荒澡。

整除： 在除法定理中报辱，當(dāng)余數(shù) $r = 0$ 時(shí)，表示 a 能被 n 整除单山，或者說 a 是 n 的倍數(shù)碍现，用符號(hào) $n\ |\ a$ 表示。

1.3 約數(shù)米奸、公約數(shù)和最大公約數(shù)

約數(shù)和倍數(shù)：對(duì)于整數(shù) d 和 a昼接，如果 $d\ |\ a$ ，且 $d >= 0$ 躏升，則我們說 d 是 a 的約數(shù)辩棒，a 是 d 的倍數(shù)狼忱。

公約數(shù)： 對(duì)于整數(shù) d膨疏，a，b钻弄，如果 d 是 a 的約數(shù)且 d 也是 b 的約數(shù)佃却，則 d 是 a 和 b 的公約數(shù)。如 30 的約數(shù)有 1窘俺，2饲帅，3复凳，5，6灶泵，10育八，15，30赦邻，而 24 的約數(shù)有 1髓棋，2，3惶洲，4按声，6，8恬吕，12签则，24，則 30 和 24 的公約數(shù)有 1铐料，2渐裂，3，6余赢。其中 1 是任意兩個(gè)整數(shù)的公約數(shù)芯义。

公約數(shù)的性質(zhì)：

若 $d | a$ ，且 $d | b => d | (a+b)$ 且 $d | (a-b)$ 妻柒。更一般的扛拨，對(duì)任意整數(shù) x 和 y，有： $d | a$ 举塔，且 $d | b => d | (ax + by)绑警。$ $(1.1)$
若 $a | b$ ，則要么 $b = 0$ 央渣，要么 $|a| <= |b|$ 计盒，即 $a | b$ 且 $b | a$ 可以推出 $|a| = |b|。$ $(1.2)$

最大公約數(shù)： 兩個(gè)整數(shù)最大的公約數(shù)稱為最大公約數(shù)芽丹，用 $gcd(a,b)$ 來表示北启，如 30 和 24 的最大公約數(shù)是 6。 $gcd(a, b)$ 有一些顯而易見的性質(zhì)：

$gcd(a, b) = gcd(b, a) \quad(1.3)$
$gcd(a, 0) = |a| \quad(1.4)$
$gcd(ka, a) = |a| \quad(1.5)$

[定理2] 最大公約數(shù)定理： 如果 a 和 b 是不為0的整數(shù)拔第，則 $gcd(a, b)$ 是 a 和 b 的線性組合集合 ${\lbrace ax + by: x, y \in \mathbb{Z} \rbrace}$ 中的最小正元素咕村。

[證明] $gcd(a, b)$ 是 a 和 b 線性組合集合最小正元素。

設(shè) s 是 a 和 b 的線性組合集合中最小正元素蚊俺，且對(duì)某個(gè) $x懈涛，y$ ，有 $s = ax + by$ 泳猬，設(shè) $q = ?a/s?$ 批钠，則 $a\ mod\ s = a - qs = a - q(ax + by) = a(1-qx) + b(-qy)$ 宇植，因此 $a\ mod\ s$ 也是 a 和 b 的一種線性組合。由于 $0 <= a\ mod\ s < s$ 埋心，所以只能 $a\ mod\ s = 0$ 指郁，不然就與我們假設(shè)矛盾了。由 $a\ mod\ s = 0$ 拷呆，于是 $s | a$ 坡氯，類似可以得到 $s | b$ ，于是 s 是 a 和 b 的公約數(shù)洋腮，于是根據(jù)定義箫柳， $gcd(a, b) >= s$ 。

另一方面啥供，因?yàn)? $gcd(a, b)$ 可以同時(shí)被 a 和 b 整除悯恍，而 s 是 a 和 b 的一個(gè)線性組合，由性質(zhì) 1.1 可得 $gcd(a, b) | s$ 伙狐，另外 $s > 0$ 涮毫，由性質(zhì) 1.2 可知 $gcd(a, b) <= s$ 。結(jié)合前面的 $gcd(a, b) >= s$ 贷屎，可證得 $s = gcd(a,b)$ 罢防。

由定理2可以得到一個(gè)推論：

[推論1] 對(duì)任意整數(shù) a 和 b，如果 $d\ |\ a$ 且 $d\ |\ b$ 唉侄，則 $d\ |\ gcd(a, b)$ 咒吐。

推論1的證明比較簡(jiǎn)單，由定理2可知 $gcd(a,b)$ 是 a 和 b 的一個(gè)線性組合属划，故由性質(zhì) 1.1 可得證 $d\ |\ gcd(a,b)$ 恬叹。

1.4 互質(zhì)數(shù)

互質(zhì)數(shù)： 如果兩個(gè)整數(shù) a 和 b 只有公因數(shù) 1，即 $gcd(a, b) = 1$ 同眯，則我們就稱這兩個(gè)數(shù)是互質(zhì)數(shù)(coprime）绽昼。比如 4 和 9 是互質(zhì)數(shù)，但是 15 和 25 不是互質(zhì)數(shù)须蜗。

互質(zhì)數(shù)的性質(zhì)：

1與任何正整數(shù)都是互質(zhì)數(shù)硅确。 $(1.6)$
任何兩個(gè)質(zhì)數(shù)都是互質(zhì)數(shù)。 $(1.7)$
質(zhì)數(shù)與小于它的每一個(gè)數(shù)都是互質(zhì)數(shù)明肮。 $(1.8)$

1.5 歐幾里得算法

歐幾里得算法分為樸素歐幾里得算法和擴(kuò)展歐幾里得算法菱农，樸素法用于求兩個(gè)數(shù)的最大公約數(shù)，而擴(kuò)展的歐幾里得算法則有更多廣泛應(yīng)用晤愧，如后面要提到的求一個(gè)數(shù)對(duì)特定模數(shù)的模逆元素等驴一。

1.5.1 樸素歐幾里得算法

求兩個(gè)非負(fù)整數(shù)的最大公約數(shù)最有名的是輾轉(zhuǎn)相除法叁征，最早出現(xiàn)在偉大的數(shù)學(xué)家歐幾里得在他的經(jīng)典巨作《幾何原本》中敷硅。輾轉(zhuǎn)相除法算法求兩個(gè)非負(fù)整數(shù)的最大公約數(shù)描述如下：

$gcd(a, 0) = a$
$gcd(a, b) = gcd(b, a\ mod\ b)(a, b \in \mathbb{Z}，a,b >= 0)$

例如抚芦， $gcd(252, 105) = gcd(105, 42) = gcd(42, 21) = gcd(21, 0) = 21$ ，在求解過程中套硼，較大的數(shù)縮小兵钮，持續(xù)進(jìn)行同樣的計(jì)算可以不斷縮小這兩個(gè)數(shù)直至其中一個(gè)變成零。

[證明] 歐幾里得輾轉(zhuǎn)相除法求GCD

由條件知 $a >= b >= 0$ 钠右，令 $r = a % b赋元，a = bt + r$ ，則需要證明 $gcd(a, b) = gcd(b, r)$ 飒房。

首先搁凸，令 $d = gcd(a, b)$ ，則根據(jù) gcd 定義狠毯， $d | a$ 且 $d | b$ 护糖。即 $d | (bt + r)$ 且 $d | b$ ，由此可得 $d | r$ 嚼松，則 $d | gcd(b, r)$ 嫡良。即 $gcd(a, b) | gcd(b, r)$ 。

其次献酗，令 $c = gcd(b, r)$ 寝受，則根據(jù) gcd 定義， $c | b罕偎，c | r$ 很澄。因?yàn)? $a = bt + r$ ，因此颜及， $c | a$ 痴怨。于是 $c | a，c | b$ 器予，可得 $c | gcd(a,b)$ 浪藻，即 $gcd(b,r) | gcd(a,b)$ 。

由此可得 $gcd(a, b) | gcd(b, r)$ 且 $gcd(b, r) | gcd(a, b)$ 乾翔，由性質(zhì)1.2 可得 $gcd(a, b) = gcd(b, r)$ 爱葵。

歐幾里得算法的python實(shí)現(xiàn)如下：

gcd = lambda a, b: (gcd(b, a % b) if a % b else b)

1.5.2 擴(kuò)展歐幾里得算法

擴(kuò)展歐幾里得算法在 RSA 算法中求模反元素有很重要的應(yīng)用，定義如下：

定義： 對(duì)于不全為 0 的非負(fù)整數(shù) $a反浓，b$ 萌丈，則必然存在整數(shù)對(duì) $x，y$ 雷则，使得

$ax + by = gcd(a, b)$

例如辆雾，a 為 3，b 為 8月劈，則 $gcd(a, b) = 1$ 度迂。那么藤乙，必然存在整數(shù)對(duì) $x, y$ ，滿足 $3x + 8y = 1$ 惭墓。簡(jiǎn)單計(jì)算可以得到 $x = 3, y = -1$ 滿足要求坛梁。

[證明] 擴(kuò)展歐幾里得算法

設(shè) $a > b$ ，則當(dāng) $b = 0$ 時(shí)腊凶， $gcd(a, 0) = a$ 划咐，則 $x = 1，y = 0$ 就是一組解钧萍。

$a褐缠，b$ 都不為 0 時(shí)，令 $r = a\ mod\ b = a - ?a/b?b$ 风瘦，由定理2送丰，設(shè) $ax_1 + by_1 = gcd(a, b)$ 。此外弛秋，由定理2器躏，設(shè) $bx_2 + ry_2 = gcd(b, r)$ ，根據(jù) r 的定義改寫此等式蟹略，可以得到 $bx_2 + (a - ?a/b?b)y_2 = gcd(b, r)$ 登失，即 $gcd(b, r) = ay_2 + b(x_2-?a/b?y_2)$ ，根據(jù)歐幾里得算法挖炬， $gcd(a, b) = gcd(b, r)$ 揽浙，則令 $x_1 = y_2，y_1 = x_2-?a/b?y_2$ 即可意敛。由此可以得到求解 $x馅巷，y$ 的遞歸解法。

擴(kuò)展歐幾里得算法的python實(shí)現(xiàn)如下：

# 擴(kuò)展歐幾里得算法實(shí)現(xiàn)草姻，參數(shù)為 a 和 b钓猬，返回最大公約數(shù) d 和 線性組合中的參數(shù) x，y撩独。
def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0

    d2, x2, y2 = ext_gcd(b, a % b)
    d, x, y = d2, y2, x2-a/b*y2
    return d, x, y

1.6 同余和模運(yùn)算

同余： 對(duì)于正整數(shù) n 和整數(shù) a敞曹，b，如果滿足 $\small n | (a-b)$ 综膀，即 a-b 是 n 的倍數(shù)澳迫，則我們稱 a 和 b 對(duì)模 n 同余，記號(hào)如下： $a \equiv b (mod ~ n)$ 例如剧劝，因?yàn)? $\small 12 | (13-1)$ 橄登，于是有 $\small 13 \equiv 1 (mod\ 12)$ 。
對(duì)于正整數(shù) n，整數(shù) $\small a_1, a_2, b_1, b_2$ 拢锹，如果 $a_1 \equiv a_2~(mod ~ n)谣妻，b_1 \equiv b_2~(mod ~n)$ 則我們可以得到如下性質(zhì)：

$a_1 + b_1 \equiv a_2 + b_2 ~ (mod ~n) \quad（1.9）$ $a_1 \cdot b_1 \equiv a_2 \cdot b_2 ~ (mod ~n) \quad (1.10)$

譬如，因?yàn)? $\small 9 \equiv 4 ~ (mod ~ 5)面褐，8 \equiv 3 ~ (mod ~ 5)$ ，則可以推出 $\small 17 \equiv 7 ~ (mod ~ 5)取胎，72 \equiv 12 ~(mod ~5)$ 展哭。

[證明] 同余加法和乘法性質(zhì)
因?yàn)? $a_1 \equiv a_2 ~(mod ~n)，b_1 \equiv b_2 ~ (mod ~n)$ 闻蛀，則說明存在整數(shù) c 和 d匪傍，滿足 $a_2 = a_1 + cn，b_2 = b_1 + dn$ 觉痛，因此： $a_2 + b_2 = a_1 + b_1 + (c+d) n$ 加法性質(zhì)得證役衡，同理可得： $a_2b_2 = (a_1 + cn)(b_1 + dn)=a_1b_1 + (a_1d+b_1c+cdn)n$ 乘法性質(zhì)得證。

另外薪棒，若 p 和 q 互質(zhì)手蝎，且 $a ≡ b (mod ~ p)，a ≡ b (mod ~ q)$ 俐芯，則可推出：
$a ≡ b (mod ~pq) \quad (1.11)$

[證明] 因?yàn)? $a ≡ b (mod ~ p) \implies p|a-b棵介，a ≡ b (mod ~ q) \implies q|a-b$ 。而 p 和 q 互質(zhì)吧史，于是可得 $pq|a-b$ 邮辽，因此可得 $a ≡ b (mod ~ pq)$ 。

此外贸营，模的四則運(yùn)算還有如下一些性質(zhì)吨述，證明也比較簡(jiǎn)單，略去钞脂。

$(a+b) ~mod ~ n = (a ~mod~ n + b ~ mod ~n) ~mod~ n$
$(a-b) ~mod ~ n = (a ~mod~ n - b ~ mod ~n) ~mod~ n$
$(a \cdot b) ~mod ~ n = (a ~mod~ n \cdot b ~ mod ~n) ~mod~ n$
$a^b ~mod~ n = ((a ~mod ~ n)^b) ~mod~ n$

模逆元素： 對(duì)整數(shù) a 和正整數(shù) n揣云，a 對(duì)模數(shù) n 的模逆元素是指滿足以下條件的整數(shù) b。 $ab \equiv 1(mod\ n)$ a 對(duì) 模數(shù) n 的模逆元素不一定存在冰啃，a 對(duì) 模數(shù) n 的模逆元素存在的充分必要條件是 a 和 n 互質(zhì)灵再，這個(gè)在后面我們會(huì)有證明。若模逆元素存在亿笤，也不是唯一的翎迁。例如 a=3，n=4净薛，則 a 對(duì)模數(shù) n 的模逆元素為 7 + 4k汪榔，即 7，11，15痴腌，...都是整數(shù) 3 對(duì)模數(shù) 4 的模逆元素雌团。如果 a 和 n 不互質(zhì)，如 a = 2士聪，n = 4锦援，則不存在模逆元素。

[推論2] 模逆元素存在的充分必要條件是整數(shù) a 和模數(shù) n 互質(zhì)剥悟。

[證明] 模逆元素存在性證明

若 a 和 n 互質(zhì)灵寺，則 $gcd(a, n) = 1$ ，由擴(kuò)展歐幾里得算法知道区岗，必然存在 x, y 使得 $ax + ny = gcd(a, n) = 1$ 略板，則模除 n 可得 $ax ≡ 1(mod\ n)$ ，顯然 x 就是 a 對(duì) 模數(shù) n 的模逆元素慈缔。事實(shí)上叮称， $x + kn(k \in \mathbb{Z})$ 都是 a 對(duì)模 n 的模逆元素，取其中最小的就是 x藐鹤。

若 a 和 n 不互質(zhì)瓤檐，設(shè) $gcd(a, n) = g$ ，則 $ax + ny = g (1 < g <= n)$ 娱节，則在模除 n 時(shí)距帅， $ax ≡ g$ 不會(huì)同余為 1，故此時(shí)不存在模逆元素括堤。

1.7 唯一質(zhì)數(shù)分解定理

[定理3] 唯一質(zhì)數(shù)分解定理： 任何一個(gè)大于1的正整數(shù) n 都可以 唯一分解 為一組質(zhì)數(shù)的乘積碌秸，其中 $e_1，e_2... e_k$ 都是自然數(shù)(包括0)悄窃。比如 6000 可以唯一分解為 $\small 6000 = 2^4 \times 3 \times 5^3$ 讥电。

$n = 2^{e_1} \cdot 3^{e_2} \cdot 5^{e_3} ... = \prod_{k=1}^r p_k^{e_k}$

[證明] 唯一質(zhì)數(shù)分解定理

存在性證明

使用反證法來證明，假設(shè)存在大于1的自然數(shù)不能寫成質(zhì)數(shù)的乘積轧抗，把最小的那個(gè)稱為 n恩敌。自然數(shù)可以根據(jù)其可除性（是否能表示成兩個(gè)不是自身的自然數(shù)的乘積）分成3類：質(zhì)數(shù)、合數(shù)和 1横媚。首先纠炮，按照定義，n大于1灯蝴。其次恢口，n 不是質(zhì)數(shù)，因?yàn)橘|(zhì)數(shù) p 可以寫成質(zhì)數(shù)乘積： $p = p^1$ 穷躁，這與假設(shè)不相符合耕肩，因此n只能是合數(shù)。

但每個(gè)合數(shù)都可以分解成兩個(gè)嚴(yán)格小于自身而大于 1 的自然數(shù)的積。設(shè) $n = a \cdot b(1 < a, b < n)$ 猿诸，由假設(shè)可知婚被，a 和 b 都可以分解為質(zhì)數(shù)的乘積，因此 n 也可以分解為質(zhì)數(shù)的乘積梳虽，所以這與假設(shè)矛盾址芯。由此證明所有大于 1 的自然數(shù)都能分解為質(zhì)數(shù)的乘積。

唯一性證明

當(dāng) n=1 的時(shí)候窜觉，確實(shí)只有一種分解谷炸。

假設(shè)對(duì)于自然數(shù) n>1，存在兩種因式分解: $n=p_1...p_m = q_1...q_k(p_1<=...<=p_m竖螃，q_1<=...<=q_k)$ 淑廊，其中 p 和 q 都是質(zhì)數(shù)逗余，我們要證明 $p_1=q_1, ..., p_m=q_k$ 特咆。如果不相等，我們可以設(shè) $p_1 < q_1$ 录粱，從而 $p_1$ 小于所有的 $q$ 腻格。由于 $p_1$ 和 $q_1$ 是質(zhì)數(shù)，所以它們的最大公約數(shù)為1啥繁，由歐幾里德算法可知存在整數(shù) a 和 b 使得 $ap_1 + bq_1 = 1$ 菜职。因此
$a p_1 q_2...q_k + b q_1 q_2...q_k = q_2 ... q_k$ (等式1)。由于 $q_1...q_k = n$ 旗闽，因此等式1左邊是 $p_1$ 的整數(shù)倍酬核，從而等式1右邊的 $q_2...q_k$ 也必須是 $p_1$ 的整數(shù)倍，因此必然有 $p_1 = q_i(i > 1)$ 适室，而這與前面 $p_1$ 小于所有的 $q$ 矛盾嫡意。

由對(duì)稱性，對(duì) $p_1 > q_1$ 這種情況可以得到類似結(jié)論捣辆，故可以證明 $p_1 = q_1$ 蔬螟，同理可得 $p_2 = q_2, ..., p_m=q_k$ ，由此完成唯一性的證明汽畴。

由質(zhì)數(shù)唯一分解定理可以得到一個(gè)推論：質(zhì)數(shù)有無窮多個(gè)旧巾。

[證明] 質(zhì)數(shù)有無窮多個(gè)。

用反證法忍些。假設(shè)質(zhì)數(shù)有限鲁猩，為 $p_1, p_2, ..., p_k$ ，最大質(zhì)數(shù)為 $p_k$ 罢坝，則令 $N$ 為所有質(zhì)數(shù)之積+1绳匀，即 $N = p_1p_2...p_k + 1$ ，顯然 $N > p_k$ ，且 $N$ 不能被已有的任何一個(gè)質(zhì)數(shù)整除疾棵。

由質(zhì)數(shù)唯一分解定理知道戈钢， $N$ 可以分解為質(zhì)數(shù)的乘積，但是它無法分解為已有質(zhì)數(shù)的乘積是尔，那么要么 $N$ 自己是質(zhì)數(shù)殉了；要么 $N$ 是合數(shù)，但是存在比 $p_k$ 更大的質(zhì)數(shù)分解因子拟枚。不管哪種情況薪铜，都與假設(shè)的最大質(zhì)數(shù)為 $p_k$ 矛盾，故假設(shè)不成立恩溅，質(zhì)數(shù)有無窮多個(gè)隔箍。

1.8 中國(guó)剩余定理

[定理4] 中國(guó)剩余定理(Chinese remainder theorem，CRT)脚乡，最早見于《孫子算經(jīng)》(中國(guó)南北朝數(shù)學(xué)著作蜒滩，公元420-589年)属百，叫物不知數(shù)問題玫氢，也叫韓信點(diǎn)兵問題。

有物不知其數(shù)懂更，三三數(shù)之剩二锌订，五五數(shù)之剩三竹握，七七數(shù)之剩二。問物幾何辆飘？

翻譯過來就是已知一個(gè)一元線性同余方程組求 x 的解： $(S):\begin{cases} & x \equiv 3 \ (mod\ 2) \\ & x \equiv 5 \ (mod\ 3) \\ & x \equiv 7 \ (mod\ 2) \end{cases}$

宋朝著名數(shù)學(xué)家秦九韶在他的著作中給出了物不知數(shù)問題的解法啦辐，明朝的數(shù)學(xué)家程大位甚至編了一個(gè)《孫子歌訣》：

三人同行七十希，五樹梅花廿一支蜈项，七子團(tuán)圓正半月芹关，除百零五便得知。

意思就是：將除以 3 的余數(shù) 2 乘以 70战得，將除以 5 的余數(shù) 3 乘以 21充边，將除以 7 的余數(shù) 2 乘以 15，最終將這三個(gè)數(shù)相加得到 $\small 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233$ 常侦。再將 233 除以 3浇冰，5，7 的最小公倍數(shù) 105 得到的余數(shù) $\small 233 % 105 = 23$ 聋亡，即為符合要求的最小正整數(shù)肘习，實(shí)際上， $\small 233 + 105k(k \in \mathbb{Z})$ 都符合要求坡倔。

物不知數(shù)問題解法本質(zhì)

從 5 和 7 的公倍數(shù)找到一個(gè)除以 3 余 1 的 $n_1$ (如70)漂佩，從 3 和 7 的公倍數(shù)中找一個(gè)除以 5 余 1 的 $n_2$ (如21)脖含，從 3 和 5 的公倍數(shù)找一個(gè)除以 7 余 1 的 $n_3$ (如15)，則 $\small 2n_1+3n_2+2n_3=140+63+30=233$ 投蝉，模除 105养葵，得最小正整數(shù)解 23。
因?yàn)? $n_1$ 除以3 余1瘩缆， $n_2$ 和 $n_3$ 都是 3 的倍數(shù)关拒，則由性質(zhì) 1.9 知， $\small n_1+n_2+n_3 = 106$ 滿足除以 3 余 1庸娱，同理也可得它滿足除以 5 余 1着绊，除以 7 余 1的條件。而前面找的是余 1 的數(shù)熟尉，使用性質(zhì) 1.9 和 1.10 可知归露，乘以余數(shù)后 $\small 2n_1+3n_2+2n_3$ 正好滿足要求，即除以 3 余 2斤儿，除以 5 余 3剧包，除以 7 余 2。為什么要先找余 1 的數(shù)雇毫，然后再乘以余數(shù)呢玄捕？這個(gè)可以在后面的通項(xiàng)公式求解知道其中緣由踩蔚。

求解通項(xiàng)公式

中國(guó)剩余定理相當(dāng)于給出了以下的一元線性同余方程組的有解的判定條件棚放，并用構(gòu)造法給出了解的具體形式。

$(S): \begin{cases} & x \equiv a_1 \ (mod\ m_1) \\ & x \equiv a_2 \ (mod\ m_2) \\ & \vdots \\ & x \equiv a_n \ (mod\ m_n) \end{cases}$

模數(shù) $m_1馅闽，m_2飘蚯，...，m_n$ 兩兩互質(zhì)福也，則對(duì)任意的整數(shù)： $a_1局骤，a_2，...暴凑，a_n$ 峦甩，方程組 $(S)$ 有解，且解可以由如下構(gòu)造方法得到：

1）設(shè) M為所有模數(shù)的乘積

$M = m_1 \cdot m_2 \cdot ... m_n = \prod _{i=1}^n m_i$

并設(shè) $M_i$ 是除 $m_i$ 以外的其他 $n?1$ 個(gè)模數(shù)的乘積现喳。

$M_i = M / m_i, ~ \forall i\in \{ 1, 2, ... n \}$

2）設(shè) $t_i$ 為 $M_i$ 對(duì)模數(shù) $m_i$ 的模逆元素凯傲，即

$t_i M_i \equiv 1 ( mod ~ m_i), ~ \forall i \in \{ 1,2,...n\}$

3）則方程組 (S）的通解形式為：

$x = a_1t_1M_1 + a_2t_2M_2 + ... a_nt_nM_n + kM = kM + \sum _{i=1}^na_it_iM_i, ~ k \in \mathbb{Z}$

4）以物不知數(shù)問題為例，則由 $\small a_1 = 2, a_2 = 3, a_3 = 2嗦篱，m_1 = 3, m_2 = 5, m_3 = 7$ 冰单， $\small M = 3 \cdot 5 \cdot 7 = 105，M_1 = M/m_1 = 35$ 灸促，同理得 $\small M_2 = 21诫欠，M_3 = 15$ 涵卵。求 $\small M_1(35)$ 模除 $\small m_1(3)$ 的最小的模逆元素，可得 $\small t_1 = 2$ 荒叼，同理得 $\small t_2 = 1轿偎，t_3 = 1$ 。故而解為：

$\small x = a_1t_1M_1 + a_2t_2M_2 + a_3t_3M_3 + kM$
$\small = 2 \times 2 \times 35 + 3 \times 1 \times 21 + 2 \times 1 \times 15 + k \times 105$
$\small = 233 + k \times 105, \quad k \in \mathbb{Z}$

中國(guó)剩余定理通項(xiàng)公式證明

[證明] 中國(guó)剩余定理

1）先證明簡(jiǎn)單的情況被廓，假設(shè)只有兩個(gè)方程贴硫， $\small m_1, m_2$ 互質(zhì)，求解 x伊者。
$(S):\begin{cases} & x \equiv a_1 \ (mod\ m_1) \\ & x \equiv a_2 \ (mod\ m_2) \\ \end{cases}$
這里我們構(gòu)造一個(gè)解：
$x = a_1t_1m_2 + a_2t_2m_1 \quad (t_1m_2 \equiv 1 ~(mod ~ m_1)英遭，t_2m_1 \equiv 1 ~ (mod ~m_2))$ 即 $t_1$ 是對(duì)模數(shù) $m_2$ 的模逆元素， $t_2$ 是 $m_1$ 對(duì)模數(shù) $m_2$ 的模逆元素 (因?yàn)?m_1 和 m_2 互質(zhì)亦渗，則對(duì)應(yīng)的模逆元素一定存在)挖诸，則可以證明 x 是滿足條件的解，證明如下：
$x \equiv (a_1t_1m_2 + a_2t_2m_1) \equiv a_1t_1m_2 \equiv a_1 (mod ~ m_1)$
$x \equiv (a_1t_1m_2 + a_2t_2m_1) \equiv a_2t_2m_1 \equiv a_2 (mod ~ m_2)$

當(dāng)然法精，對(duì)于兩個(gè)方程的情況多律，我們也可以直接根據(jù)模運(yùn)算的定義來求解，這個(gè)方式也會(huì)在后面 RSA 算法優(yōu)化中用到搂蜓。因?yàn)? $x \equiv a_2 (mod ~ m_2)$ 狼荞，于是可以令：
$x = km_2 + a_2$ 代入到第一個(gè)方程有：
$km_2 + a_2 \equiv a_1 ~ (mod ~ m_1)$ 根據(jù)性質(zhì) 1.9，可得:
$a_1 - a_2 \equiv km_2 (mod ~ m_1)$ 因?yàn)? $m_1帮碰，m_2$ 互質(zhì)相味，所以 $m_2$ 對(duì)于 $m_1$ 必然存在模逆元素 $t_2$ ，滿足 $t_2m_2 \equiv 1~ (mod ~m_1)$ 殉挽，根據(jù)性質(zhì) 1.10 可得：
$t_2(a_1 - a_2) \equiv kt_2m_2 \equiv k ~(mod ~ m_1)$ 由此可以得到 $k = t_2(a_1-a_2) ~mod ~m_1$ 丰涉，從而得到 x 在 $[0, m_1m_2)$ 范圍內(nèi)的唯一解是:
$x = a_2 + km_2 = a_2 + (t_2(a_1-a_2) ~ mod ~ m_1) \cdot m_2 \quad (1.12)$

2）推廣到 n 個(gè)方程組，對(duì) $\forall i \in \{1, 2, ..., n \}$ 斯碌，則對(duì) $\forall j \in \{1, 2, ..., n \}一死，j \neq i$ ，因?yàn)? $m_i$ 與 $m_j$ 互質(zhì)傻唾，則可得 $gcd(m_i, m_j) = 1$ 投慈，且 $m_i$ 和 $M_i$ 互質(zhì)，則 $gcd(m_i, M_i) = 1$ 冠骄。因?yàn)? $gcd(m_i, M_i) = 1$ 伪煤，由推論2 知，必然存在整數(shù) $t_i$ 猴抹，滿足： $t_iM_i \equiv 1(mod\ m_i)$ 带族，即 $t_i$ 是 $M_i$ 模 $m_i$ 的模逆元素◇案考察乘積 $a_it_iM_i$ 可知：
$a_it_iM_i \equiv a_i (mod \ m_i)$ 而 $\forall j \in \{1, 2, ..., n\}蝙砌，j \neq i阳堕，a_it_iM_i \equiv 0 (mod \ m_j)$ ，故而 $x = a_1t_1M_1 + a_2t_2M_2 + ... a_nt_nM_n$ 滿足：
$x = a_it_iM_i + \sum_{j \neq i} a_jt_jM_j \equiv a_i + \sum_{j \neq i}0 \equiv a_i(mod \ m_i)$ 所以可以得出 x 就是方程組 $(S)$ 的一個(gè)解择克。

3）另外恬总，假設(shè) $x_1$ 和 $x_2$ 都是方程組的解，那么：

$\forall i \in \{1, 2, ..., n\}, \quad x_1-x_2 \equiv 0 \ (mod\ m_i)$ 肚邢，而 $m_1, m_2, ..., m_n$ 互質(zhì)壹堰，從而可得 $M\ |\ (x_1 -x_2)$ 。即兩個(gè)解必然相差 $M$ 的整數(shù)倍骡湖，故而方程組通解為：
$\{x = \sum_{i=1}^na_it_iM_i+ kM, \ k \in \mathbb{Z}\}$

1.9 歐拉函數(shù)贱纠、歐拉定理和費(fèi)馬定理

1.9.1 歐拉函數(shù)

歐拉函數(shù)定義：對(duì)正整數(shù) n，歐拉函數(shù) $φ(n)$ 是指小于或等于 n 的正整數(shù)中與 n 互質(zhì)的數(shù)的數(shù)目响蕴。比如 $φ(1)=1谆焊，φ(8) = 4$ （因?yàn)?1，3浦夷，5辖试，7 都與 8 互質(zhì)）。由唯一質(zhì)數(shù)分解定理可知劈狐，正整數(shù) n 可以分解為質(zhì)數(shù)乘積罐孝，據(jù)此可以得到歐拉函數(shù)的計(jì)算公式如下。

唯一質(zhì)數(shù)分解： $n = \prod_{k=1}^r p_k^{e_k}$
歐拉函數(shù)計(jì)算公式： $φ(n) = n \prod_{k=1}^r (1 - \frac {1}{p_k})$

如 $72 = 2^3 \times 3^2$ 肥缔，故 $φ(72) = 72 \times (1-1/2) \times (1-1/3)=24$ 莲兢。

歐拉函數(shù)計(jì)算公式推導(dǎo)：

1）若 n 為 1，顯然 $φ(1) = 1$ 辫继。

2）若 n 為質(zhì)數(shù)怒见，有性質(zhì) 1.8 可知俗慈，每個(gè)小于 n 的數(shù)都與 n 是互質(zhì)數(shù)姑宽。則 $φ(p) = p - 1$ 。

3）若 n 為質(zhì)數(shù)的冪闺阱，即 $n = p^k$ (p為質(zhì)數(shù)炮车，k為大于等于1的整數(shù)），則因?yàn)橹挥挟?dāng)一個(gè)數(shù)不包含質(zhì)數(shù) p酣溃，才可能與 n 互質(zhì)瘦穆。而包含質(zhì)數(shù) p 的數(shù)一共有 $p^{k-1}$ 個(gè)，故互質(zhì)數(shù)目為 $p^k - p^{k-1}$ 赊豌。
$φ(n) = p^k - p^{k-1} = p^k(1 - \frac{1}{p})$

4）若 n 為兩個(gè)互質(zhì)數(shù)的乘積扛或，即 $n = p \cdot p$ (p, q 為互質(zhì)數(shù))。則 $φ(n) = φ(p) \cdot φ(q)$ 碘饼，例如 $φ(56) = φ(8) \cdot φ(7) = 4 \cdot 6 = 24$ 熙兔。在證明之前悲伶，可以看個(gè)特例，即 p 和 q 都是質(zhì)數(shù)住涉，則 p 和 q 肯定是互質(zhì)數(shù)麸锉，這種情況下與 n 互質(zhì)的數(shù)不能包含質(zhì)因子 p 和 q，p 的倍數(shù)有 q 個(gè)舆声，q 的倍數(shù)有 p 個(gè)花沉，這里還多算了一個(gè)數(shù) n，它即是 p 的倍數(shù)也是 q 的倍數(shù)媳握，因此 1 到 n 中 p 和 q 的倍數(shù)的數(shù)一共有 $p+q-1$ 個(gè)碱屁，則可以推導(dǎo)如下：

$φ(n) = n - (p + q-1)$
$= pq - (p + q - 1) = (p-1)(q-1)$
$= p(1 - \frac{1}{p})q(1-\frac{1}{q})$
$= φ(p)φ(q)$

若 p 和 q 互質(zhì)，但是 p 和 q 不一定是質(zhì)數(shù)蛾找。則 $gcd(p, q) = 1$ 忽媒，設(shè)小于 p 的數(shù)中與 p 互質(zhì)的正整數(shù)有 $φ(p)$ 個(gè)，則這些數(shù)的集合為 $R = \{r_1, r_2, ..., r_{φ_p}\}$ 腋粥。而小于 q 且與 q 互質(zhì)的正整數(shù)有 $φ(s)$ 個(gè)晦雨，設(shè)這些數(shù)的集合為 $S = \{s_1, s_2, ..., s_{φ_q}\}$ 。從集合 R 和 S中分別選取一個(gè)數(shù) r 和 s隘冲，構(gòu)造方程組 $x \equiv r(mod\ p)$ 以及 $x \equiv s(mod \ q)$ 闹瞧，由中國(guó)剩余定理可知，則當(dāng) $x < pq$ 時(shí)方程組存在且僅存在一個(gè)正整數(shù)解展辞，即 $x ~ mod ~ pq$ 有唯一解奥邮。且該方程組在 p 和 q相同的情況下，如果 r 和 s 不同罗珍，則解 x 也一定不同洽腺。下面證明解 x 滿足 $gcd(x, pq) = 1$ 。

因?yàn)? $x\ \%\ p = r$ 覆旱，由歐幾里得算法可得 $gcd(x, p) = gcd(p, r)$ 蘸朋，當(dāng) $gcd(p, r) = 1$ 時(shí)，則可得 $gcd(x, p) = 1$ 扣唱，同理藕坯， $gcd(x, q) = 1$ 。由 $gcd(x, p) =1$ 和 $gcd(x, q) = 1$ 噪沙，且 $p炼彪、q$ 互質(zhì)，可得 $gcd(x, pq) = 1$ 正歼，即 x 是滿足歐拉函數(shù)的一個(gè)數(shù)辐马。而 $<r, s>$ 這樣的數(shù)對(duì)一共有 $φ(p) φ(q)$ 個(gè)，而 $x$ 一共有 $φ(pq)$ 個(gè)局义，故而得證 $φ(pq) = φ(p)φ(q)$ 喜爷。

看一個(gè)實(shí)際的例子膜楷，設(shè) $x= 15 = p \cdot q = 3 \cdot 5$ ，則對(duì)于 $x ~mod~ 3 = a, x ~mod~ 5 = b$ 贞奋，(a, b) 和 x 存在如下一一對(duì)應(yīng)關(guān)系赌厅。即若 p 和 q 為互質(zhì)數(shù)，則對(duì)于任意的數(shù)對(duì) $<a, b> \in \Bbb Z_p \times \Bbb Z_q$ 轿塔，存在唯一的 $x \in \Bbb Z_{n}$ (其中 $\Bbb Z_n$ 表示整數(shù)集合 $\{0, 1, ..., n-1\}$ )特愿。

(a, b)	x	(a, b)	x	(a, b)	x
(0, 0)	0	(1, 0)	10	(2, 0)	5
(0, 1)	6	(1, 1)	1	(2, 1)	11
(0, 2)	12	(1, 2)	7	(2, 2)	2
(0, 3)	3	(1, 3)	13	(2, 3)	8
(0, 4)	9	(1, 4)	4	(2, 4)	14

綜上，可以得到通項(xiàng)公式：

設(shè) $n = p_1^{e_1} \cdot p_2^{e_2} \cdot ... p_r^{e_r}$

$φ(n) = φ(p_1^{e_1} \cdot p_2^{e_2} \cdot ... p_r^{e_r})$
$= φ(p_1^{e_1}) \cdot φ(p_2^{e_2}) \cdot ... φ(p_r^{e_r})$ (由4可得)
$= p_1^{e_1} \cdot p_2^{e_2} ... p_r^{e_r}\cdot(1 - \frac{1} {p_1})\cdot(1-\frac{1}{p_2})...(1-\frac{1}{p_r})$ (由3可得)
$= n\cdot (1 - \frac{1}{p_1})\cdot(1-\frac{1}{p_2})...(1-\frac{1}{p_r})$ (由 n 分解式可得)

計(jì)算歐拉函數(shù)可以使用 python 的這個(gè)模塊： eulerlib勾缭，一個(gè)示例代碼如下：

import eulerlib
e = eulerlib.numtheory.Divisors(10000)
e.phi(21)

1.9.2 歐拉定理

歐拉定理基于歐拉函數(shù)而來揍障，它是 RSA 算法的核心。內(nèi)容如下：
歐拉定理： 如果兩個(gè)正整數(shù) a 和 n 互質(zhì)俩由，則 n 的歐拉函數(shù) $φ(n)$ 滿足下面的條件：

$a ^ {φ(n)} \equiv 1 (mod\ n)$

基于前面的知識(shí)毒嫡，我們來證明下歐拉定理。

[證明] 歐拉定理

根據(jù)歐拉函數(shù)定義幻梯，小于 $n$ 且與 $n$ 互質(zhì)的數(shù)有 $φ(n)$ 個(gè)兜畸，設(shè)這些數(shù)的集合為 $U = u_1, u_2, ..., u_{φ(n)}$ 。顯然對(duì)于 U 中的任意數(shù) $u_i$ 碘梢，都有 $u_i ~ mod ~ n = u_i$ 咬摇。若一個(gè)正整數(shù) a 與 n 互質(zhì)，且 a 比 n 大煞躬，同樣滿足 $a \ mod \ n$ 與 n 互質(zhì)肛鹏，即 $(a ~ mod ~ n) \in U$ 。證明如下：設(shè) $a = kn + r(k>=1, 0<r<n)$ 恩沛，由于 kn 不會(huì)與 n 互質(zhì)在扰，故 r 必須和 n 互質(zhì)，而 $r < n$ 雷客，故 $r \in U$ 芒珠，即 $(a ~ mod ~ n) \in U$ 。因此得到一個(gè)結(jié)論佛纫，只要正整數(shù) a 與 n 互質(zhì)妓局，則有 $(a ~mod ~ n) \in U$ 。

接著我們可以證明若 a 與 n 互質(zhì)呈宇，且 u 與 n 互質(zhì)，則 $au % n$ 與 n 互質(zhì)局雄，繼而可得到 $(au ~ mod ~ n) \in U$ 甥啄。這是為什么呢？因?yàn)楦鶕?jù)唯一質(zhì)數(shù)分解定理炬搭，a 和 u 都可以分解為質(zhì)數(shù)乘積蜈漓，如 $\small a = \prod_{i=1}^s p_i^{e_i}$ 穆桂，而 $\small u = \prod_{i=1}^t q_i^{f_i}$ ，同理融虽，n也可以分解為質(zhì)因數(shù)乘積 $\small n=\prod_{i=1}^m r_i^{g_i}$ 享完。而由 a 和 u都和 n 互質(zhì)，則 a 和 n 的質(zhì)因子沒有交集有额，且 u 和 n 的質(zhì)因子沒有交集般又，則 au 的質(zhì)因子與 n 沒有交集，故而 au 和 n 互質(zhì)巍佑，由前面的結(jié)論茴迁，可得到 $(au ~ mod ~ n) \in U$ 。

將集合 U 中的數(shù)都乘以 a萤衰，可以得到新的集合 $AU$ 堕义，即 $AU = \{a u_1, a u_2, ..., a u_{φ(n)}\}$ ，由前面分析可知 $AU$ 中的每個(gè)數(shù)都與 n 互質(zhì)。所以双肤，對(duì)于任意的 $u_i \neq u_j(i,~ j \in U钦听，i \neq j)$ ，可得到 $au_i ~ mod ~ n \neq au_j ~ mod ~ n$ 糖耸，即 $AU$ 中每個(gè)數(shù)除以 n 的余數(shù)各不相同。這個(gè)用反證法不難證明丘薛，若存在 $u_i \neq u_j(i,~ j \in U嘉竟，i \neq j)$ ，滿足 $au_i ~mod~ n = au_j ~mod ~n$ 洋侨，則可以設(shè) $au_i = sn + r, au_j = tn + r$ 舍扰，故可得 $a(u_i - u_j) = (s-t)n$ ，而 a 與 n 互質(zhì)希坚，則要滿足條件边苹，只能 $u_i - u_j$ 是 n 的倍數(shù)，而我們知道 $|u_i - u_j| < n$ 裁僧，與假設(shè)矛盾个束。由 $AU$ 中每個(gè)數(shù)與 n 互質(zhì)，且它們除以 n 的余數(shù)與 n 互質(zhì)且各不相同聊疲，故而 $AU$ 中每個(gè)數(shù)除以 n 得到的余數(shù)就是集合 $U$ 中的那 $φ(n)$ 個(gè)數(shù)茬底，當(dāng)然順序不一定是一一對(duì)應(yīng)。因此 $AU ~mod~ n = U$ 获洲。

有了上一步的結(jié)論阱表，再加上模除的性質(zhì)，就可以證明歐拉定理了：
$au_1 \cdot au_2...au_{φ(n)} \equiv u_1 \cdot u_2...u_{φ(n)}(mod ~n)$
$a^{φ(n)}\cdot u_1 \cdot u_2...u_{φ(n)} \equiv u_1 \cdot u_2...u_{φ(n)}(mod ~ n)$
$a^{φ(n)} \equiv 1(mod ~ n)$

1.9.3 費(fèi)馬小定理

費(fèi)馬小定理：給定整數(shù)a和質(zhì)數(shù)p，若a不是p的倍數(shù)最爬，那么：
$a^{p-1} \equiv 1(mod ~ p)$

費(fèi)馬小定理可以看做是歐拉定理的特例涉馁。因?yàn)楫?dāng) p 為質(zhì)數(shù)時(shí)，a 不是 p的倍數(shù)爱致，則 a與p互質(zhì)烤送，且 p 的歐拉函數(shù) $φ(p) = p-1$ ，代入歐拉定理即可得證糠悯。

2 RSA算法原理

RSA算法基于歐拉定理而來帮坚，如果只是為了證明RSA算法原理，只要明白歐拉定理即可逢防。當(dāng)然叶沛，歐拉定理的證明涉及數(shù)論中許多經(jīng)典的定理，有興趣的同學(xué)可以深入了解證明過程忘朝。話說回來灰署，即便不看歐拉定理的證明過程，只要明白歐拉定理內(nèi)容局嘁，看懂RSA算法原理也是沒有問題的溉箕。

2.1 RSA算法

1）生成兩個(gè)隨機(jī)的不相等的大質(zhì)數(shù) p 和 q，它們的積 $n = pq$ 的二進(jìn)制位數(shù)就是密鑰的位數(shù)悦昵，通常設(shè)置的位數(shù)有 1024肴茄，2048，3072但指，4096等寡痰。

[知識(shí)點(diǎn)] 大質(zhì)數(shù)生成算法

如何生成這兩個(gè)大質(zhì)數(shù)，這是個(gè)值得研究的問題棋凳。首先可以想到的是生成質(zhì)數(shù)序列拦坠，從中隨機(jī)選取2個(gè)大質(zhì)數(shù)即可。一種改進(jìn)的方法是: 除了 2 外的偶數(shù)肯定不是質(zhì)數(shù)剩岳，而奇數(shù)可能是質(zhì)數(shù)贞滨，可能不是，那就可以跳過2與3的倍數(shù)拍棕，即對(duì)于 6n晓铆，6n+1, 6n+2, 6n+3, 6n+4, 6n+5，我們只需要判斷 6n+1 與 6n+5 是否是質(zhì)數(shù)即可绰播。而判斷某個(gè)數(shù)m是否是質(zhì)數(shù)骄噪，最基本的方法就是對(duì) 2 到 m-1 之間的數(shù)除 m，如果有一個(gè)數(shù)能夠整除 m幅垮，則 m 就不是質(zhì)數(shù)腰池。判斷 m 是否是質(zhì)數(shù)還可以進(jìn)一步改進(jìn)尾组，只需要對(duì) 2 到 $\small \sqrt m$ 之間的數(shù)除 m 就可以忙芒。繼續(xù)優(yōu)化示弓，其實(shí)只用 2 到 $\small \sqrt m$ 之間的質(zhì)數(shù)去除即可。上面生成大質(zhì)數(shù)是很基礎(chǔ)的方法呵萨，效率比較低奏属，一般會(huì)采用更快的方式，比如隨機(jī)生成一個(gè) nbits 位的奇數(shù) p潮峦，然后從 p 開始遍歷之后的奇數(shù)囱皿，并通過 Miller–Rabin 質(zhì)數(shù)判定算法對(duì)遍歷到的數(shù)字進(jìn)行質(zhì)數(shù)判定，如果是質(zhì)數(shù)忱嘹，即可返回(當(dāng)然嘱腥，該算法有一定的誤判率，不過在判定次數(shù)設(shè)置夠大的情況下拘悦，誤判率基本可以忽略)齿兔。

2）計(jì)算 p 和 q 的積 $n=pq$ ，以及歐拉函數(shù) $φ(n) = (p-1)(q-1)$

3）選擇一個(gè)整數(shù) $e础米，1< e < φ(n)$ 分苇，且 $gcd(e, φ(n))$ = 1，即 $e$ 與 $φ(n)$ 互質(zhì)屁桑，在 openssl 中 $e$ 固定為 65537医寿。

[知識(shí)點(diǎn)]費(fèi)馬數(shù)
對(duì)于e，通衬⒏可選 3, 5, 17, 257 和 65537靖秩。因?yàn)樗鼈兌际琴|(zhì)數(shù)，且二進(jìn)制中只有2位是1竖瘾，可以加快 d 的計(jì)算沟突。這幾個(gè)e的可選值實(shí)際是費(fèi)馬數(shù)的前5個(gè)數(shù)，費(fèi)馬數(shù)定義是 $F_x = 2^{2^x} + 1$ 准浴， $F_0$ 到 $F_4$ 都是質(zhì)數(shù)事扭，但是從 $F_5$ 開始就不是質(zhì)數(shù)了。例如 $F_5 = 4294967297 = 641×6700417$ 乐横。實(shí)際應(yīng)用中通常選擇 $F_4 = 65537$ 作為 e求橄。

計(jì)算 e 對(duì)于 $φ(n)$ 的模反元素 d。即找到整數(shù)d葡公，1 < d < φ罐农，且滿足 $\small ed \equiv 1~(mod ~φ(n))$ 。

$ed ≡ 1~(mod~ φ(n))$
$\implies ed - 1 = kφ(n)$
$\implies ed + φ(n)k'= 1$

根據(jù)擴(kuò)展歐幾里得算法催什，e 和 φ(n) 為已知量涵亏，可以求得一組解 d, k'，其中 d 就是我們需要找的模反元素。

5）n 和 e 封裝為公鑰气筋，n 和 d 封裝為私鑰拆内。

n：通常稱為 modulus。
e：通常稱為 public exponent宠默。
d：通常稱為 secret exponent麸恍。

6）定義好了公私鑰，則對(duì)信息 $m(0 <= m < n)$ 搀矫，加密和解密函數(shù)如下：
$c = RsaPublic(m) = m^e ~ mod ~ n$ (公鑰 n, e 加密)
$m =RsaPrivate(c) = c^d ~ mod ~ n$ (私鑰 n, d 解密)

需要證明：
$m = RsaPrivate(RsaPublic(m))$ (1)
$m = RsaPublic(RsaPrivate(m))$ (2)

經(jīng)過分析可以發(fā)現(xiàn)這兩個(gè)式子證明是一樣的抹沪，這里證明（1）即可。（1）常用于客戶端公鑰加密數(shù)據(jù)然后服務(wù)端私鑰解密獲取原始數(shù)據(jù)瓤球，而（2）則常用于服務(wù)端私鑰加密簽名數(shù)據(jù)融欧，客戶端公鑰解密獲取簽名數(shù)據(jù)并校驗(yàn)簽名。

2.2 實(shí)例分析

在證明之前卦羡，先簡(jiǎn)單驗(yàn)證下噪馏。假定我們選擇 $p=13， q=15虹茶，e = 17$ 逝薪，則

$n = 13\times15 = 195$
$φ(n) = (13-1)(15-1) = 168$
$17d + 168y = 1$ ，可以求得一個(gè) $d=89, k=-9$ 蝴罪。

假定我們?cè)紨?shù)據(jù) m=16董济，則加密后數(shù)據(jù)為 61，對(duì) 61 解密要门，可以得到原始數(shù)據(jù) 16虏肾。

$c = m^e ~ \% n = 16 ^{17} ~ \% ~ 195 = 61$
$m = c^d ~ \% ~ n = 61^{89} ~ \% ~195 =16$

2.3 算法正確性證明

由上一節(jié)可知，我們要證明的是：
$((m^e ~mod ~ n) ^ d) ~mod~ n = m (0 <= m < n)$
由模運(yùn)算的冪性質(zhì)欢搜，等式左邊: $((m^e ~ mod ~ n) ^ d) ~mod ~n= m^{ed} ~mod~ n$ 封豪，即我們要證明的是：
$m^{ed} ~ mod ~ n = m \iff m^{ed} \equiv m (mod ~ n)$

由前面RSA算法構(gòu)造條件知道 $ed \equiv 1(mod ~ φ(n))$ ，據(jù)此可設(shè) $ed = 1 + kφ(n)$
先證明 m 和 n 互質(zhì)這種特殊情況炒瘟。因?yàn)?m 和 n 互質(zhì)吹埠，由歐拉定理有 $m^{φ(n)} \equiv 1(mod ~n)$ 。由此推導(dǎo)如下：
$m^{ed} \equiv m^{1 + kφ(n)}$
$\equiv (m \cdot ({m^{φ(n)}})^k)$
$\equiv (m \cdot 1^k)$ (由歐拉定理和模運(yùn)算的乘法結(jié)合律)
$\equiv m(mod ~n)$
下面證明的是 m 和 n 不互質(zhì)的情況疮装，因?yàn)?n = pq缘琅，且 p 和 q都是質(zhì)數(shù)，則 m 與 n 不互質(zhì)只能是 p 或者 q 的倍數(shù)廓推，不能同時(shí)為 p 和 q的倍數(shù)刷袍，因?yàn)?m < n。假設(shè) m 是 q 的倍數(shù)樊展，即 $q|m$ 呻纹，則 $m \equiv 0 ( mod ~ q)$ 堆生。可得 $m^{1 + kφ(n)} \equiv m \equiv 0 ~(mod ~ q)$ 雷酪。

而因?yàn)?p 是質(zhì)數(shù)淑仆，m 又不是 p 的倍數(shù)，故 p 和 m 互質(zhì)太闺。由費(fèi)馬小定理糯景，可得到 :
$m^{p-1} \equiv 1 (mod ~ p)$
$\implies m^{(p-1)(q-1)} \equiv 1^{q-1} \equiv 1 (mod ~ p)$ (兩邊 q-1 的冪次)
$\implies m^{φ(n)} \equiv 1 (mod ~ p)$ (因?yàn)? $\small(φ(n) = φ(pq) = (p-1)(q-1)$ )
$\implies m^{kφ(n)} \equiv 1^k \equiv 1(mod ~ p)$ (兩邊 k 次冪)
$\implies m^{1+kφ(n)} \equiv m(mod ~ p)$ (兩邊乘以 m)

由 $m^{1+kφ(n)} \equiv m(mod ~ p)$ 以及 $m^{1+kφ(n)} \equiv m(mod ~ q)$ 嘁圈，從而可得 $m^{1+kφ(n)} \equiv m(mod ~ pq)$ 省骂，因?yàn)? $n=pq$ ，故 $m^{1+kφ(n)} \equiv m(mod ~ n)$ 最住，因?yàn)? $ed = 1 + kφ(n)$ 钞澳，根據(jù)性質(zhì) 1.11，故而得證 $m^{ed} \equiv m(mod ~ n)$ 涨缚。
注意： 雖然定義中 $0 <= m < n$ 轧粟，但是實(shí)際上對(duì)于 $m = 0，1脓魏，n-1$ 加密并沒有效果兰吟，很容易從加密過程知道， $0茂翔，1混蔼，n-1$ 加密后都是它們自身。

2.4 RSA Key Pair的生成方法及代碼實(shí)現(xiàn)

RSA的Key Pair的生成方法的偽代碼如下：

INPUT: 模數(shù) (即前面提到的N珊燎，N=pq) 的二進(jìn)制位數(shù) k
OUTPUT: RSA的密鑰對(duì) ((N,e),d)惭嚣，其中 N 是模數(shù), N=pq，其二進(jìn)制長(zhǎng)度不超過 k bit悔政。 e 是選擇的 public exponent晚吞，d 是 secret exponent。

$\small Select ~ a ~ value ~ of ~ e ~ from ~ 3,5,17,257,65537$
$\small repeat$
$\small \quad p \leftarrow genprime(k/2)$
$\small until ~ (p~ mod ~ e) \neq 1$
$\small repeat$
$\small \quad q \leftarrow genprime(k - k/2)$
$\small until ~ (q ~ mod ~ e) \neq 1$
$\small N \leftarrow pq$
$\small L \leftarrow (p-1)(q-1)$
$\small d \leftarrow modinv(e, L)$
$\small return ~ (N,e,d)$

1）首先就是找兩個(gè)位數(shù)為 k/2 的大于0的大質(zhì)數(shù)谋国。在前面提到過槽地，最樸素的方法是遍歷正整數(shù)集，對(duì)于數(shù) n芦瘾，用 $\small2, 3, ..., \sqrt n$ 去除 n捌蚊，但是這個(gè)方法的時(shí)間復(fù)雜度為 $\small \Theta(\sqrt n)$ ，這是正整數(shù) n 的長(zhǎng)度的冪(因?yàn)?n 可以表示為 b 位的二進(jìn)制數(shù)旅急，則 $\small n = \lceil lg(n+1) \rceil$ 逢勾，故而 $\small \sqrt n = \Theta(2^{b/2})$ )。這個(gè)復(fù)雜度是比較高的藐吮，而我們不用遍歷所有的整數(shù)溺拱，完全可以隨機(jī)找一個(gè)大整數(shù)逃贝，然后判斷該數(shù)是不是質(zhì)數(shù)即可。令人高興的是迫摔，判斷一個(gè)數(shù)是不是質(zhì)數(shù)比對(duì)一個(gè)數(shù)進(jìn)行質(zhì)數(shù)因子分解要容易很多沐扳。

由費(fèi)馬小定理知道，如果 n 是質(zhì)數(shù)句占，則對(duì)于任意的數(shù) $\small 1 <= a <= n-1$ 沪摄，都滿足
$\small a^{n-1} \equiv 1(mod~ n)(2.4.1)$
則可以知道如果對(duì)于 $\small 1, 2, ..., n-1\$ 中如果有一個(gè)數(shù) a 和 n 不滿足 2.4.1，則 n 一定是合數(shù)纱烘。當(dāng)然我們?cè)趯?shí)際中也不會(huì)將所有小于 n 的正整數(shù)都遍歷來計(jì)算一遍杨拐，通常會(huì)隨機(jī)選取一個(gè) a 作為基數(shù)，比如選擇 a=2擂啥，則滿足費(fèi)馬小定理而又不是質(zhì)數(shù)的 n 哄陶，我們稱 n 為基于 a 的一個(gè)偽質(zhì)數(shù)。比如 341 滿足 $\small 2^{(341-1)} \equiv 1(mod ~ 341)$ 哺壶，但是 341 是一個(gè)合數(shù)屋吨。如果將基數(shù)a換成3，那也不能保證山宾，對(duì)于 $\small \forall a \in \{1, 2, ...n-1\}$ 至扰，總有些合數(shù)(這些數(shù)也被稱為 Carmichael數(shù))滿足2.4.1，如 561(a=2 滿足)资锰，1105(a=2和a=3都滿足)等敢课。

為此，我們可以使用 Miller-Rabin 算法來解決判斷質(zhì)數(shù)問題台妆。其主要思想就是選取 s 個(gè) a 的隨機(jī)數(shù)翎猛，然后判斷奇數(shù) n 是否是質(zhì)數(shù)(偶數(shù)可以直接排除)，如果其中任意一個(gè) a 對(duì)應(yīng)的 WITNESS(a, n) 為 true接剩，則表示 n 肯定是合數(shù)切厘。如果 s 次測(cè)試都通過，則可以近似判定 n 是質(zhì)數(shù)(誤判的概率最大為 $\small 1/2^s$ 懊缺，一般實(shí)際應(yīng)用中選s=50就可以了)疫稿。

INPUT: (n, s)，n > 2鹃两，n 是奇數(shù)遗座，s 是測(cè)試次數(shù)
OUTPUT: COMOSITE 表示為合數(shù)，PRIME 則表示極可能是質(zhì)數(shù)

$\small MILLER-RABIN(n, s)$
$\small \quad for ~ j ~ 1 \leftarrow to ~ s$
$\small \quad \quad do ~ a \leftarrow RANDOM(1, n-1)$
$\small \quad \quad \quad if ~ WITNESS(a, n)$
$\small \quad \quad \quad \quad then ~ return ~ COMPOSITE$ // 肯定不是質(zhì)數(shù)
$\small \quad return ~ PRIME$ // 極可能是質(zhì)數(shù)

INPUT: (a, n) 其中 a 為隨機(jī)選擇的基數(shù)俊扳，n為待判定的奇數(shù)
OUTPUT: TRUE 表示肯定是合數(shù)途蒋， FALSE 表示可能是質(zhì)數(shù)

$\small WITNESS(a, n)$
$\small \quad let ~ n-1 = 2^tu, where ~ t >=1 ~ and ~ u ~ is ~ odd$
$\small \quad x_0 = a^u ~ mod ~ n$
$\small \quad for ~ i \leftarrow 1~ to ~ t$
$\small \quad \quad do ~ x_i \leftarrow x_{i-1}^2 ~ mod ~ n$
$\small \quad \quad \quad if ~ x_i = 1 ~ and ~ x_{i-1} \neq 1 ~ and ~ x_{i-1} \neq n-1$
$\small \quad \quad \quad \quad then ~ return ~ TRUE$
$\small \quad if ~ x_i \neq 1$
$\small \quad \quad then ~ return ~ TRUE$
$\small \quad return ~ FALSE$

而 WITNESS 就是根據(jù) 2.4.1 來判斷 n 是否通過檢測(cè)，不過做了一些優(yōu)化馋记，因?yàn)?n 是奇數(shù)号坡，所以可以將 n-1分解為 $\small n-1 = 2^tu(t>=1, u為奇數(shù))$ 懊烤，設(shè) $\small x_0 = a^u ~ mod ~ n$ ，則對(duì) x 的結(jié)果平方 t 次宽堆，即可計(jì)算出 $\small a^{n-1} ~ mod ~ n$ 腌紧。所計(jì)算的序列 $x_0, x_1, ...x_t$ 滿足 $\small x_i \equiv a^{2^i}u(mod ~ n)(i = 0, 1, ...t)$ 。如果前一個(gè)值 $\small x_{i-1}$ 不等于 1 或者 n-1畜隶，但是當(dāng)前值 $\small x_{i} = 1$ 壁肋，則 n 一定是合數(shù)。證明如下：

$\small WITNESS$ 正確性證明：

首先可以證明這么一個(gè)結(jié)論：若 a 籽慢，n為正整數(shù)浸遗，且 n 為質(zhì)數(shù)， $\small a^2 \equiv 1 (mod ~n)$ 嗡综，則有 $\small a \equiv \pm1(mod ~ n)$ 乙帮。

這是因?yàn)?br> $\small a^2 \equiv 1(mod ~n) \implies a^2 - 1 \equiv 0(mod ~n)$
$\small \quad \implies (a+1)(a-1) \equiv 0(mod ~ n)$
$\small \quad \implies a + 1 \equiv 0(mod ~ n)$ 或者 $\small a - 1 \equiv 0(mod ~ n)$
$\small \quad \implies a \equiv \pm1(mod ~ n)$ (因?yàn)?a > 0)

下面就很容易證明 WITNESS了，因?yàn)? $\small n-1 = a^{2^i}u$ 极景，如果 n 是質(zhì)數(shù)的話，則由 $\small x_i = 1$ 驾茴，可以推出 $x_{i-1}$ 一定是1 或者 n-1盼樟，否則 n一定是合數(shù)。

2）第二步就是計(jì)算 N=pq锈至，然后計(jì)算歐拉函數(shù) L晨缴，最后根據(jù) e 和歐拉函數(shù) L 計(jì)算出 e 模除 L 的模擬元素 d 即可。

3）基于該算法峡捡，我寫了個(gè) RSA 密鑰生成的 python 實(shí)現(xiàn)供大家參考击碗，見 shishujuan:rsa-algrithm 。

2.5 提高 RSA 加解密效率

由前面分析知道 RSA 加解密效率嚴(yán)重依賴求冪和求模運(yùn)算效率们拙，為了減少大整數(shù)的求冪和求模的運(yùn)算稍途，可以對(duì) RSA 模冪算法(modular exponentiation)進(jìn)行一些優(yōu)化。主要包括兩方面砚婆，一是對(duì)模冪運(yùn)算本身進(jìn)行優(yōu)化械拍，提升運(yùn)算效率。而是對(duì)RSA算法進(jìn)行優(yōu)化装盯，基于中國(guó)剩余定理來提升RSA加解密效率坷虑。

加密： $c = m^e ~ mod ~ n$
解密： $m = c^d ~ mod ~ n$

2.5.1 提升模冪運(yùn)算性能

模冪運(yùn)算-樸素法

樸素法求模冪就是直接求冪然后模除，如下：

def pow_simple(a, e, n):
    """
    樸素法模冪運(yùn)算：a^e % n
    """
    ret = 1
    for _ in xrange(e):
        ret *= a
    return ret % n

當(dāng)冪 b 很大時(shí)埂奈，這個(gè)方法的模冪運(yùn)算就很慢迄损，在我的機(jī)器上 a=5, e=102400, n = 13284 大概需要1秒左右的時(shí)間。我們知道 RSA 私鑰中的 d 的值可是遠(yuǎn)大于 102400 的账磺，如果這么慢顯然效率上會(huì)有問題芹敌。

一種簡(jiǎn)單的優(yōu)化方法基于下面這個(gè)性質(zhì)共屈，可以很方便的迭代實(shí)現(xiàn)，而且每次計(jì)算會(huì)將參數(shù)減小党窜，優(yōu)化后的模冪運(yùn)算效率大概提升了100倍左右拗引。

$a \equiv c(mod ~ n) \implies ab \equiv bc(mod ~n)$
$\implies ab ~mod~n = (b(a ~ mod ~ n))(mod ~ n)$

代碼如下：

def pow_simple_optimized(a, e, n):
    """
    樸素法模冪運(yùn)算優(yōu)化：基于 a ≡ c(mod n) => ab ≡ bc(mod n)，
    即 ab mod n = (b*(a mod n)) mod m
    """
    ret = 1
    c = a % n
    for _ in xrange(e):
        ret = (ret * c) % n
    return ret

模冪運(yùn)算-二進(jìn)制法

雖然優(yōu)化過的樸素方法的效率已經(jīng)有了大幅提升幌衣，但是對(duì)于RSA私鑰的超大的d值矾削，仍然性能堪憂。比如當(dāng)冪級(jí)數(shù) e 大小為億級(jí)別時(shí)豁护，優(yōu)化過的樸素方法在我的機(jī)器需要接近10秒的時(shí)間求模般哼。一種廣為應(yīng)用的模冪方法就是二進(jìn)制法棚蓄，基于位運(yùn)算效率會(huì)有驚人的提升，e為億級(jí)別時(shí)模冪運(yùn)算也只需要零點(diǎn)幾毫秒。

對(duì)于一個(gè)n位的冪級(jí)數(shù) e也物，我們可以寫成如下二進(jìn)制形式：
$e = e_{n-1}e_{n-2}...e_1e_0 = \sum_{i=0}^{n-1} e_i2^i$ (其中 $e_{n-1}$ 是最高位， $e_0$ 是最低位)
$\implies a^e = a^{\sum_{i=0}^{n-1}e_i2^i} = \prod_{i=0}^{n-1}(a^{2^i})^{e_i}$
$\implies c \equiv \prod_{i=0}^{n-1}(a^{2^i})^{e_i} (~mod ~ n)$

從最低位 $e_0$ 開始遍歷 $e_i(i=0, 1, ...n-1)$ 原茅，如果 $e_i = 0$ 揣非，則不影響模除結(jié)果，設(shè)置base值达址，繼續(xù)處理下一位即可蔑祟。在掃描到 $e_i$ 時(shí)，有 $base = a^{2^i} ~mod~ n$ 沉唠，根據(jù)模除的乘法結(jié)合律 $(a * b) ~mod ~n = ((a ~mod~ n) * (b ~mod~ n)) ~mod ~ n$ 疆虚，可以知道下面算法是正確的。Python的內(nèi)建函數(shù) $pow(x, y, z)$ 就是使用了類似的算法满葛，因此在模冪運(yùn)算時(shí)径簿，使用 $pow(x, y, z)$ 函數(shù)比 $x**y ~\%~ z$ (直接冪運(yùn)算跟優(yōu)化過的樸素法性能相當(dāng))性能要高出幾個(gè)數(shù)量級(jí)。

def pow_binary(a, e, n):
    """
    right-to-left binary method:基于位運(yùn)算模冪運(yùn)算優(yōu)化嘀韧。
    """
    number = 1
    base = a
    while e:
        if e & 1:
            number = number * base % n
        e >>= 1
        base = base * base % n
    return number

完整的代碼見 pow.py篇亭。

2.5.2 分解大整數(shù)提升模冪運(yùn)算效率

從前面分析知道，通常使用過程中公鑰的冪級(jí)數(shù) e 的選取比較小乳蛾，而且選取的是費(fèi)馬數(shù)暗赶，只有2位是1，其他位是0肃叶。而私鑰的冪級(jí)數(shù) d 很大蹂随，它的位數(shù)與模數(shù) N 差不多，且有接近一半位是1因惭。為了提高私鑰 d 在模冪運(yùn)算中性能，可以基于中國(guó)剩余定理(CRT)進(jìn)行相關(guān)優(yōu)化蹦魔。

使用中國(guó)剩余定理提升私鑰模冪運(yùn)算效率(其中 $n^{-1} _m$ 代表 n 對(duì)模數(shù) m 的模逆元素激率，即 $n^{-1}_m n \equiv 1(mod ~m)$ )
$dP = e^{-1} ~ mod ~ (p-1) = d ~mod~ (p-1)$
$dQ = e^{-1} ~mod~ (q-1) = d ~mod ~ (q-1)$
$m1 = c^{dP} ~ mod ~ p$
$m2 = c^{dQ} ~ mod ~ q$
$qInv = q^{-1} _p$
$h = qInv \cdot (m1 - m2) ~mod~ p$
$m = m2 + h \cdot q$

這里多出來的 dP咳燕，dQ，qInv的值在使用 openssl 生成的 rsa 密鑰中也有乒躺，其目的就是為了加速私鑰模冪運(yùn)算招盲。以 2.2 中的例子為例，直接求 m 可得 $\small m = c^d ~mod ~n = 61^{89} ~mod~ 195 = 16$ 嘉冒，而使用中國(guó)剩余定理優(yōu)化后求解流程如下曹货，亦可得到正確的結(jié)果 m = 16。

$dP = d ~ mod~ (p-1) = 89 ~ mod~(13-1) = 5$
$dQ = d ~ mod ~ (q-1) = 89 ~ mod ~ (15-1) = 5$
$m1 = c^{dP} ~ mod ~ p = 61^5 ~ mod ~ 13 = 3$
$m2 = c^{dQ} ~ mod ~ q = 61^5 ~ mod ~ 15 = 1$
$qInv = q^{-1}_p = 15^{-1}_{13} = 7$
$h = qInv \cdot (m1-m2) ~ mod ~ p = 7 \cdot(3-1) ~ mod ~ 13 = 1$
$m = m2 + h \cdot q = 1 + 1 \cdot 15 = 16$

[證明]

由中國(guó)剩余定理知道讳推，對(duì)于 $x ~ mod ~ p = x_1, x ~ mod ~ q = x_2(0 <= x_1 < p, 0 <= x_2 < q)$ 這個(gè)方程組在 p 和 q互質(zhì)時(shí)顶籽，則必然存在一個(gè)唯一解 $0 =< x < pq$ 。因?yàn)? $n=pq$ 银觅，因此對(duì)于任意的 $0 <= x < n$ 礼饱，必然存在唯一的數(shù)對(duì) $<x_1, x_2>$ 使之滿足方程組。我們要計(jì)算的是 $m = c^d ~ mod ~ n=c^d ~mod~ pq$ 究驴，如果我們知道了 $<c^d ~ mod ~ p, ~ c^d ~ mod ~ q>$ 镊绪，則由中國(guó)剩余定理知，必然存在一個(gè)唯一的值 $c^d ~mod~ n$ 與之對(duì)應(yīng)纳胧。

由 1.12 中中國(guó)剩余定理的解的格式可知镰吆，若已知
$c^d ~ mod ~ p = m_1，c^d ~ mod ~ q = m_2跑慕，n=pq$ ，則有
$x = c^d ~ mod ~n = m_2 + h \cdot q$
$h = (q^{-1}_p(m_1 - m_2)) ~ mod ~ p$

可以發(fā)現(xiàn)這與前面計(jì)算 $m_1$ 并不是直接用的 $c^d ~ mod ~ p$ 摧找，而是 $c^{d ~mod ~(p-1)} ~mod~ p$ 核行，這是為何呢？為什么會(huì)有 $c^d \equiv c^{d ~ mod ~ (p-1)} ~ (mod ~p)$
這個(gè)可以用歐拉定理證明：設(shè) $d = kφ(p) + d ~mod~ φ(p)$ 蹬耘，則有
$c^d = c^{kφ(p) + d ~mod~ φ(p)} = (c^{φ(p)})^k \cdot c^{d ~mod ~φ(p)}$ 由歐拉定理知道
$c^{φ(p)} \equiv 1(mod ~ p)$ 于是有：
$c^d \equiv 1^k \cdot c^{d ~mod ~φ(p)} \equiv c^{d ~mod ~φ(p)} \equiv c^{d ~mod ~(p-1)} (mod ~ p)$ 得證芝雪。

使用剩余定理優(yōu)化的python實(shí)現(xiàn)參見 rsa.py 中的 decrypt_crt 函數(shù)。在我電腦上測(cè)試發(fā)現(xiàn)综苔，優(yōu)化后效率提升5倍左右惩系。

2.6 如何破解 RSA？

從RSA加解密原理可知如筛，如果要破解RSA堡牡，那就是知道 d 即可，由 $\small ed \equiv 1(mod ~ n)$ 可知杨刨，要知道 d晤柄，就需要 e 和 φ(n)，e 是公開的妖胀，而 $\small φ(n) = (p-1)(q-1)$ 是未知的芥颈，想知道 φ(n) 就要知道 p 和 q 這兩個(gè)大質(zhì)數(shù)的值惠勒。我們知道 n 也是公開的， $\small n=pq$ 爬坑，所以只要能將 n 進(jìn)行質(zhì)數(shù)因式分解即可破解RSA算法纠屋。如果 N 是個(gè)小整數(shù)，那很好辦盾计，比如 N = 25777售担，知道 $\small \sqrt[2]{25777} < 161$ ，則可以從 161 開始找比它小的質(zhì)數(shù)闯估，然后判斷是不是可以整除即可灼舍，很快可以得到 $\small 25777 = 149 * 173$ 。

不過不要擔(dān)心涨薪，大整數(shù)的質(zhì)數(shù)因式分解還是比較難的骑素。雖然除了暴力破解外，還有一些效率比較高的整數(shù)因式分解方法刚夺，如二次篩分算法和普通數(shù)域篩選法（GNFS）等献丑，當(dāng)你的RSA密鑰位數(shù)在4096位以上，使用常規(guī)運(yùn)算能力的電腦還是較難破解的侠姑。當(dāng)然不排除某一天创橄，數(shù)論研究出現(xiàn)了新的成果，若有一種通項(xiàng)公式可以分解大整數(shù)的話莽红，那現(xiàn)有基于 RSA 的加密體系都會(huì)崩塌妥畏。此外，RSA 加密用的 e 不能太小安吁，否則有潛在的風(fēng)險(xiǎn)醉蚁，實(shí)際應(yīng)用中常用 65537。

如果已知 N鬼店，e网棍，d，則可以很高效地對(duì) N 實(shí)現(xiàn)因式分解妇智，原理就不贅述了滥玷，實(shí)現(xiàn)代碼見 factor.py 。

在實(shí)際應(yīng)用如HTTPS中巍棱，RSA 密鑰因?yàn)樾阅茉蛞约皼]有前向安全性惑畴，通常并不直接用來加密數(shù)據(jù)，而是只用于在密鑰交換時(shí)用于簽名以認(rèn)證身份拉盾，加密通常會(huì)基于 ECDHE 等算法協(xié)商一個(gè)密鑰桨菜，然后再基于對(duì)稱加密算法如 AES 等對(duì)數(shù)據(jù)加密傳輸。

3 RSA 密鑰格式實(shí)例分析

本節(jié)對(duì)使用 openssl 等工具生成的 RSA 密鑰格式進(jìn)行簡(jiǎn)單分析，首先倒得，使用 openssl 生成一對(duì) RSA 密鑰泻红，如下：

# openssl genrsa -out rsa_demo.key 2048
# openssl rsa -in rsa_demo.key -pubout -out rsa_demo.pub

示例的私鑰文件 rsa_demo.key，公鑰文件 rsa_demo.pub霞掺。

最常用的 RSA 密鑰的模式是 PKCS#1 中規(guī)定的模式谊路，即公鑰包括 N, e，而私鑰包括 N, e, d, p, q, dP, dQ, qInv菩彬。查看公私鑰文件內(nèi)容缠劝，可以看到采用的是 DER(Distinguished Encoding Rules) 編碼的，公鑰解碼后內(nèi)容如下：

# grep -v '\-\-\-\-\-' rsa_demo.pub | tr -d '\n'|base64 -D|hexdump
0000000 30 82 01 22 30 0d 06 09 2a 86 48 86 f7 0d 01 01
0000010 01 05 00 03 82 01 0f 00 30 82 01 0a 02 82 01 01
0000020 00 bd e4 43 1a d0 02 1e e6 12 34 14 91 84 4d 65
......
0000120 b1 02 03 01 00 01                              
0000126

DER 編碼是一種type-length-value編碼骗灶，即包括：對(duì)象類型惨恭，數(shù)據(jù)長(zhǎng)度域，數(shù)據(jù)域耙旦。示例的 RSA 公鑰中脱羡， 0x30 是 Sequence 類型，0x03 是 Bit String 類型免都，而 0x02 是 Integer 類型锉罐，0x04是字符串類型，0x06是 Object ID類型绕娘，0x05 00表示NULL脓规。長(zhǎng)度如果>=128，則會(huì)先跟一個(gè) 0x81或0x82(0x81表示后面一個(gè)字節(jié)為長(zhǎng)度险领，0x82表示后面兩個(gè)字節(jié)為長(zhǎng)度)侨舆，然后是數(shù)據(jù)長(zhǎng)度的值，沒超過則就是長(zhǎng)度值绢陌。整個(gè)結(jié)構(gòu)是一個(gè)嵌套結(jié)構(gòu)态罪，公鑰的 n 和 e 兩個(gè)數(shù)值位于 BIT STRING 這塊數(shù)據(jù)中，可以分析知道從 00000020開始的 00bde4...b1是 n下面，而從 0000123開始的 010001 是 e，即 65537绩聘。另外沥割，Object ID是標(biāo)識(shí)密鑰的元信息的地方，對(duì)應(yīng)的是 2a 86 48 86 f7 0d 01 01 01 這 9 個(gè)字節(jié)凿菩，這個(gè)代表什么含義呢机杜？其實(shí)轉(zhuǎn)義過來是 1.2.840.113549.1.1.1，這個(gè) OID 表示的是 RSA 加密系統(tǒng)的公鑰衅谷。私鑰格式類似椒拗，這里不再贅述，openssl 生成的私鑰中包括了 p,q,dP,dQ,n,e,d,qInv數(shù)據(jù)。

如果不想了解公私鑰的格式蚀苛，直接通過 openssl 的工具即可解析出公私鑰的內(nèi)容在验，容易驗(yàn)證，這些值正是基于前面的 RSA 原理計(jì)算得來的堵未。

# openssl rsa -in rsa_demo.key -noout -text
Private-Key: (2048 bit)
modulus: # N
    00:bd:e4:43:1a:d0:02:1e:e6:12:34:14:91:84:4d:
    ...
publicExponent: 65537 (0x10001) # e
privateExponent: # d
    76:bb:8d:41:ec:a2:06:d3:f0:b9:e3:ca:81:21:2b:
    ...
prime1: # p
    00:fa:99:34:b8:b3:97:dc:09:37:29:dd:df:de:86:
    ...
prime2: # q
    00:c1:fc:13:f7:84:dd:f4:b5:05:2d:89:b9:a1:50:
    ...
exponent1: # dP
    00:c9:7d:61:cc:98:6a:23:bb:2d:25:76:86:47:cf:
    ...
exponent2: # dQ
    00:99:e8:43:7b:45:ea:c8:45:7b:57:37:07:95:ea:
    ...
coefficient: # qInv
    0c:53:5f:0c:a6:7b:33:69:32:b6:b9:65:f8:31:5f:
    ...
    
# openssl rsa -pubin -in rsa_demo.pub -noout -text
Public-Key: (2048 bit)
Modulus: # N
    00:bd:e4:43:1a:d0:02:1e:e6:12:34:14:91:84:4d:
    ...
Exponent: 65537 (0x10001) # e

參考資料

《算法導(dǎo)論》第31章
《具體數(shù)學(xué)》第4章
di-mgt:rsa_alg
di-mgt:rsa_theory
di-mgt:rsa_factorize_n
di-mgt:crt
di-mgt:RSA算法的C語(yǔ)言實(shí)現(xiàn)
wiki: 中國(guó)剩余定理
歐拉函數(shù)
關(guān)于歐拉函數(shù)及其一些性質(zhì)的美妙證明（2）
關(guān)于歐拉函數(shù)及其一些性質(zhì)的美妙證明(1)
wiki: Modular_exponentiation
pkcs--10-encoded-asn-1
how-is-oid-2a-86-48-86-f7-0d-parsed-as-1-2-840-113549
latex公式參考資料

最后編輯于：2021.03.07 07:20:48

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末腋舌，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子渗蟹，更是在濱河造成了極大的恐慌块饺，老刑警劉巖，帶你破解...
沈念sama閱讀 222,104評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件雌芽，死亡現(xiàn)場(chǎng)離奇詭異授艰，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)世落，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,816評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門淮腾，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人岛心，你說我怎么就攤上這事来破。” “怎么了忘古？”我有些...
開封第一講書人閱讀 168,697評(píng)論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵徘禁，是天一觀的道長(zhǎng)。經(jīng)常有香客問我髓堪，道長(zhǎng)送朱，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 59,836評(píng)論 1贊 298
?港島之戀（遺憾婚禮）
正文為了忘掉前任干旁，我火速辦了婚禮驶沼，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘争群。我一直安慰自己回怜，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 68,851評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布换薄。她就那樣靜靜地躺著玉雾，像睡著了一般。火紅的嫁衣襯著肌膚如雪轻要。梳的紋絲不亂的頭發(fā)上复旬，一...
開封第一講書人閱讀 52,441評(píng)論 1贊 310
城市分裂傳說
那天，我揣著相機(jī)與錄音冲泥，去河邊找鬼驹碍。笑死壁涎，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的志秃。我是一名探鬼主播怔球，決...
沈念sama閱讀 40,992評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼洽损！你這毒婦竟也來了庞溜？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,899評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤碑定，失蹤者是張志新（化名）和其女友劉穎流码，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體延刘，經(jīng)...
沈念sama閱讀 46,457評(píng)論 1贊 318
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡漫试，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,529評(píng)論 3贊 341
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了碘赖。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片驾荣。...
茶點(diǎn)故事閱讀 40,664評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖普泡，靈堂內(nèi)的尸體忽然破棺而出播掷，到底是詐尸還是另有隱情，我是刑警寧澤撼班，帶...
沈念sama閱讀 36,346評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布歧匈，位于F島的核電站，受9級(jí)特大地震影響砰嘁，放射性物質(zhì)發(fā)生泄漏件炉。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,025評(píng)論 3贊 334
男人毒藥：我在死后第九天來索命
文/蒙蒙一矮湘、第九天我趴在偏房一處隱蔽的房頂上張望斟冕。院中可真熱鬧，春花似錦缅阳、人聲如沸磕蛇。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,511評(píng)論 0贊 24
一樁弒父案十办，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)孤里。三九已至，卻和暖如春橘洞，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背说搅。一陣腳步聲響...
開封第一講書人閱讀 33,611評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來泰國(guó)打工炸枣，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人。一個(gè)月前我還...
沈念sama閱讀 49,081評(píng)論 3贊 377
代替公主和親
正文我出身青樓适肠，卻偏偏與公主長(zhǎng)得像霍衫，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子侯养，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,675評(píng)論 2贊 359