Title: RSA 加密算法的基础数论、基本原理与 Python 实现

---

---

前言

1977 年美国 MIT 的三位数学家 Ronald L. Rivest、Adi Shamir 和 Leonard M. Adleman 一起提出了著名的非对称加密算法 —— RSA 算法. RSA 算法利用计算机无法快速实现大数的质因数分解这一事实 (当前也还成立), 确保该算法的安全性.

对 RSA 加密算法其中的数学原理感兴趣, 故整理并学习一下 (“copycat”) , 最后用 python 简单实现了该算法.

---

I. 数学原理

1. 整数环

RSA 算法全部建立在 Module Arithmetic (模运算)^[1]的基础上.

[I-1-1] 同余和模运算 Congruence and Module Arithmetic:

For a positive integer $m$ and integers $a$ and $b$, we follow Gauss and write
$$a\equiv b(\text{mod}m)$$
to mean that $a$ and $b$ have the same remainder upon division by $m$.

In words, the notation is read as $a$ is congruent to $b$ modulo $m$.

The expression $a\equiv b(\text{mod}m)$ is called a congruence, and $m$ is the modulus of the congruence.

[例]
$$12\equiv 26(\text{mod}7)$$

[I-1-2] 环 Ring:

A ring $R$ is a set equipped with binary operations $+$ and $\times$ and elements $0,1\in R$ such that $R$ is an abelian group under $+$, and for all $a,b,c\in R$ we have

Multiplicative identity: $1\times a=a\times 1=a$

Multiplicative associativity: $(a\times b)\times c=a\times (b\times c)$

Left distributivity: $a\times (b+c)=a\times b+a\times c$

[例]

集合 Z 3 = { 0 , 1 , 2 } \mathbb{Z}_3 = \{0,1,2\} Z3​={0,1,2}, 装备了 $+$ 和 $\times$ 运算
$$\begin{array}{cccc}+& 0& 1& 2\\ 0& 0& 1& 2\\ 1& 1& 2& 0\\ 2& 2& 0& 1\end{array}\begin{array}{cccc}\times & 0& 1& 2\\ 0& 0& 0& 0\\ 1& 0& 1& 2\\ 2& 0& 2& 1\end{array}$$
$0$ 是加法 ($+$) 恒等元. 集合中每个元素都有加法逆, $0+0=0$ 及 $1+2=2+1=0$. 加法满足交换律.

1 是乘法 ($\times$) 恒等元. 取数值可验证乘法结合律和左结合律.

故集合 ${\mathbb{Z}}_3$ 是环.

[I-1-3] 模算数环 Modular Arithmetic Rings^[2]:

Let $m\in \mathbb{Z}$: $m\ge 2$.

Let ${\mathbb{Z}}_m$ be the set of integers modulo $m$.

Let ${+}_m$ and ${\times }_m$ denote addition modulo $m$ and multiplication modulo $m$, respectively.

The algebraic structure $({\mathbb{Z}}_m,{+}_m,{\times }_m)$ is the ring of integers modulo $m$.

[例] 同上

现在在不引起歧义情况下, $a\times b$ 中乘法符号 $\times$ 可省略表示.

有时为了特别强调某一对象 $a$ 是环 ${\mathbb{Z}}_m$ 中的元素, 可记作 $[a{]}_m$, 如 ${\mathbb{Z}}_5$ 中的 $3$ 记作 $[3{]}_5$.

其实 ${\mathbb{Z}}_m$ 中的元素 $[a{]}_m$ 也可以看做是模运算等价类, 即 [ a ] m = { … , a − 2 m , a − m , a , a + m , a + 2 m , … } [a]_m = \{\ldots,a-2m,a-m,a,a+m, a+2m, \ldots\} [a]m​={…,a−2m,a−m,a,a+m,a+2m,…}.

---

2. 单位元

[I-2-1] 环中的单位元 Ring Units:

A multiplicative inverse of a number $n$ is a number $m$ with the property that $n\times m=1$.

A number in a ring is called a unit in that ring if it has a multiplicative inverse in the ring.

[例] 整数环 ${\mathbf{Z}}_6$ 中含元素 { 0 , 1 , 2 , 3 , 4 , 5 } \{0,1,2,3,4,5\} {0,1,2,3,4,5}, 构建乘法表
$$\begin{array}{ccccccc}\times & 0& 1& 2& 3& 4& 5\\ 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 2& 3& 4& 5\\ 2& 0& 2& 4& 0& 2& 4\\ 3& 0& 3& 0& 3& 0& 3\\ 4& 0& 4& 2& 0& 4& 2\\ 5& 0& 5& 4& 3& 2& 1\end{array}$$
其中 1 的乘法逆是 1 本身, 而 5 的乘法逆是 5 本身. 故 1 和 5 都是该整数环中的 unit.

[例] 整数环 ${\mathbf{Z}}_7$ 中含元素 { 0 , 1 , 2 , 3 , 4 , 5 , 6 } \{0,1,2,3,4,5, 6\} {0,1,2,3,4,5,6}, 构建乘法表
$$\begin{array}{cccccccc}\times & 0& 1& 2& 3& 4& 5& 6\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 2& 3& 4& 5& 6\\ 2& 0& 2& 4& 6& 1& 3& 5\\ 3& 0& 3& 6& 2& 5& 1& 4\\ 4& 0& 4& 1& 5& 2& 6& 3\\ 5& 0& 5& 3& 1& 6& 4& 2\\ 6& 0& 6& 5& 4& 3& 2& 1\end{array}$$
其中 1 的乘法逆是 1 本身, 2 的乘法逆是 4, 3 的乘法逆是 5, 4 的乘法逆是 2, 5 的乘法逆是 3, 6 的乘法逆是 6 本身. 故 { 1 , 2 , 3 , 4 , 5 , 6 } \{1,2,3,4,5,6\} {1,2,3,4,5,6} 都是该整数环中的 units.

[I-2-2] 单位元性质 A Property of Units:

Let $a$ and $m$ be positive integers with $a<m$. The element $[a{]}_m$ is a unit in ${\mathbb{Z}}_m$ if and only if $\gcd (a,m)=1$.

[证明]

充分性. 已知 $[a{]}_m$ 是 ${\mathbb{Z}}_m$ 的 unit, 并假设 $\gcd (a,m)=d$.

因为 $[a{]}_m$ 是单位元, 故存在 $[b{]}_m\in {\mathbb{Z}}_m$, 使得 $ab=1(\text{mod}m)$.

等价地, 存在 $k\in \mathbb{Z}$ 使得
$$ab=1+mk\Rightarrow ab-mk=1$$
又因为 $\gcd (a,m)=d$, 故 $d|a$ 及 $d|m$. 可以推得 $d|(ab-mk)$, 进一步可知 $d|1$.

得到结论 $\gcd (a,m)=1$ (即 $a$ 与 $m$ 互质).

必要性. 已知 $\gcd (a,m)=1$, 根据裴蜀定理 ( Bézout’s Lemma) 可知存在整数 $r,s\in \mathbb{Z}$ 使得
$$\begin{gathered} ar+ms=1 \\ \Rightarrow ar\equiv 1(\text{mod}m) \end{gathered}$$
又 $\exists r_m\in {\mathbb{Z}}_m$, 使得 $r\equiv r_m(\text{mod}m)$, 即 $r=r_m+lm$. 上式有
$$\begin{gathered} a(r_m+lm)\equiv 1(\text{mod}m) \\ \Rightarrow a{r}_m\equiv 1(\text{mod}m) \end{gathered}$$
得到条件 $[a{]}_m$ 是环 ${\mathbb{Z}}_m$ 中的单位元 unit.

充要条件证明完毕.

[I-2-3] 相消性 Cancellation:

Let $a$ and $m$ be relatively prime integers, with $m>1$. If $b$ and $c$ are integers for which
$$ab\equiv ac(\text{mod}m)$$
then $b\equiv c(\text{mod}m)$.

In other words:

Suppose $a$ is a unit in a ring ${\mathbb{Z}}_m$, and suppose that $b$ and $c$ are also in ${\mathbb{Z}}_m$. If $ab=ac$, then $b=c$.

[证明]
$$\begin{array}{cc}& ab=ac(\text{mod}m)\\ \Rightarrow & ab-ac=0(\text{mod}m)\\ \Rightarrow & m|ab-ac\\ \Rightarrow & m|a(b-c)\\ \because & \gcd (a,m)=1\\ \therefore & m|b-c\\ \therefore & b\equiv c(\text{mod}m)\end{array}$$

---

3. 欧拉定理

[I-3-1] 欧拉函数 Euler $\varphi$-Function

If $m$ is a positive integer, set $\varphi (m)$ equal to the number of integers in the range from $1$ to $m$ that are relatively prime to $m$. That is
ϕ ( m ) = # { a ∈ Z   ∣   1 ≤ a ≤ m  and  gcd ⁡ ( a , m ) = 1 } \phi(m)= \#\{a \in \mathbb{Z}\ \vert\ 1\leq a \leq m \ \text{and}\ \gcd(a,m)=1 \} ϕ(m)=#{a∈Z ∣ 1≤a≤m and gcd(a,m)=1}
In the case that $m$ is prime, obtaining the value $\varphi (m)=m-1$. That is
ϕ ( m ) = # { 1 , 2 , … , m − 1 } = m − 1 \phi(m)= \#\{1,2,\ldots, m-1\} = m-1 ϕ(m)=#{1,2,…,m−1}=m−1
The value of $\varphi (m)$ for $m>1$ can also be described as the number of units in ${\mathbb{Z}}_m$. If the number of units in ${\mathbb{Z}}_m$ is noted as $|U_m|$, then
$$\varphi (m)=|U_m|$$

[例]

$\varphi (1)=1$, 因为 1 和任何正整数 (包括 1 本身) 都互质.

$\varphi (2)=1$, 因为只有 1 与 2 互质, 大于 1 的整数与自身不互质.

$\varphi (3)=2$, 因为有 { 1 , 2 } \{1,2\} {1,2} 与 3 互质.

$\varphi (4)=2$, 因为有 { 1 , 3 } \{1,3\} {1,3} 与 4 互质.

$\varphi (5)=4$, 因为有 { 1 , 2 , 3 , 4 } \{1,2,3,4\} {1,2,3,4} 与 5 互质.

$\varphi (6)=2$, 因为有 { 1 , 5 } \{1,5\} {1,5} 与 6 互质.

$\varphi (7)=6$, 因为有 { 1 , 2 , 3 , 4 , 5 , 6 } \{1,2,3,4,5,6\} {1,2,3,4,5,6} 与 7 互质.

[说明]

事实上, ${\mathbb{Z}}_m$ 中的所有 units 组成的集合 $U_m$ 关于 $\times$ 运算构成群. 因为

二元运算: 群乘法就是原来环中的乘法 (即模运算下的乘法)

单位元: 1

逆元: units 定义要求

封闭性: 已知 $u{u}^{{}^{\prime }}\equiv 1(\text{mod}1)$, $v{v}^{{}^{\prime }}\equiv 1(\text{mod}1)$ $\Rightarrow$ $(uv)(v^{{}^{\prime }}{u}^{{}^{\prime }})\equiv 1(\text{mod}1)$

结合律: 沿袭模运算中乘法结合律

群中元素的个数即为群的阶. 利用 “[I-2-2] 单位元性质 A property of Units” 就可以将欧拉函数和群中元素个数联系起来.

另外, $\varphi (m)$ 也称为 Totient Function (不知其翻译).

[I-3-2] 可乘性 Multiplicative Property

Let $a$ and $b$ be relatively prime positive integers. Then
$$\varphi (ab)=\varphi (a)\varphi (b)$$

[非完全证明]

上述定理的完全和严格证明需要采用中国剩余定理与双射性质, 此处不展开.

此处只证明在 RSA 加密算法中用到的 “$a$ 和 $b$ 为不同质数” 的情况.

全集 U = { m ∈ Z   ∣   1 ≤ m ≤ a b } U = \{m\in \mathbb{Z}\ \vert\ 1\leq m\leq ab\} U={m∈Z ∣ 1≤m≤ab}, 元素个数 $|U|=ab$.

$U$ 中能被 $a$ 整除的元素集合 A = { x ∈ U   ∣   ( a ∣ x ) } A= \{x\in U\ \vert\ (a|x)\} A={x∈U ∣ (a∣x)}, 即 { a , 2 a , … , ( b − 1 ) a , b a } \{a,2a,\ldots,(b-1)a,ba\} {a,2a,…,(b−1)a,ba}. 元素个数 $|A|=b$.

$U$ 中能被 $b$ 整除的元素集合 B = { x ∈ U   ∣   ( b ∣ x ) } B = \{x\in U \ \vert\ (b|x)\} B={x∈U ∣ (b∣x)}, 即 { b , 2 b , … , ( a − 1 ) b , a b } \{b,2b,\ldots,(a-1)b,ab\} {b,2b,…,(a−1)b,ab}. 元素个数 $|B|=a$.

$U$ 中能被 $a$ 和 $b$ 都整除 (即能被$ab$ 整除) 的元素集合 C = { x ∈ U   ∣   ( a b ∣ x ) } C = \{x\in U \ \vert\ (ab|x)\} C={x∈U ∣ (ab∣x)}, 只有一个元素 { a b } \{ab\} {ab}. 故 $|C|=1$.

使用集合容斥原理可知, $U$ 中既不能被 $a$ 整除也不能被 $b$ 整除的元素集合 $D=U-A-B+C$, 各集合之间的关系如图.

根据 “[I-3-1] 欧拉函数 Euler $\varphi$-function” 中定义, $\varphi (ab)$ 是要找与 $ab$ 互质的整数的个数.

“$a$ 和 $b$ 为不同质数” 时, $\varphi (ab)$ 就是找既不能被 $a$ 整除又不能被 $b$ 整除的整数个数.
$$\begin{array}{rl}\varphi (ab)& =|D|\\ & =|U|-|A|-|B|+|C|\\ & =ab-b-a+1\\ & =(a-1)(b-1)\\ & =\varphi (a)\varphi (b)\end{array}$$
这样就证明了 “当 $a$ 和 $b$ 是不同的质数时, $\varphi (ab)=\varphi (a)\varphi (b)$”.

[I-3-3] 欧拉定理 Euler’s Theorem

Let $m$ be an integer greater than $1$. In the ring ${\mathbb{Z}}_m$ , every unit $u$ satisfies
$$u^{\varphi (m)}=1$$
Equivalently, every integer $a$ relatively prime to $m$ satisfies
$$a^{\varphi (m)}=1(\text{mod}m)$$

[证明]

第一部分的证明

已知环 ${\mathbb{Z}}_m$ 中有 $t=\varphi (m)$ 个单位元.

单位元集合 (其实构成群) U m = { u 1 , u 2 , … , u t } U_m = \{u_1, u_2, \ldots, u_t\} Um​={u1​,u2​,…,ut​}, 任意选择其中一个 $u_i$ ($1\le i\le t$).

用 $u_i$ 乘以集合 $U_m$ 中的每一个元素得到模 $m$ 乘积系列 $u_i{u}_1,u_i{u}_2,\dots ,u_i{u}_t$.

假设上述模 $m$ 乘积得到相同元素, 则可推导如下
$$\begin{gathered} u_i{u}_p\equiv u_i{u}_q(\text{mod}m) \\ \Rightarrow u_i(u_p-u_q)\equiv 0(\text{mod}m) \end{gathered}$$
根据 “[I-2-3] 相消性 Cancellation”, 可得 $u_p-u_q\equiv 0(\text{mod}m)$ $\Rightarrow$ $u_p\equiv u_q(\text{mod}m)$. 与单位元 units 是各自不同元素矛盾.

所以模 $m$ 乘积系列是各自不同的值.

又根据 “${\mathbb{Z}}_m$ 中的所有 units 组成的集合 $U_m$ 关于 $\times$ 运算构成群”, 及群中运算的封闭性可知, 模 $m$ 乘积系列 $u_i{u}_1,u_i{u}_2,\dots ,u_i{u}_t$ 仍然是群 $U_m$ 中元素的完整列表, 与 $u_1,u_2,\dots ,u_t$ 之间可能只是排列顺序的差别.

那么就有
$$\begin{gathered} u_1{u}_2\dots u_t\equiv (u_i{u}_1)(u_i{u}_2)\dots (u_i{u}_t)(\text{mod}m) \\ \Rightarrow u_1{u}_2\dots u_t=u_i^t(u_1{u}_2\dots u_t)(\text{mod}m) \end{gathered}$$
由 units 群中逆元性质可知, $u_1{u}_2\dots u_t$ 仍环 ${\mathbb{Z}}_m$ 中的 unit. 利用 “[I-2-3] 相消性 Cancellation” 可得
$$u_i^t\equiv 1(\text{mod}m)\Rightarrow u_i^{\varphi (m)}\equiv 1(\text{mod}m)$$
第二部分的证明

利用 “[I-2-2] 单位元性质 A property of units” 可知, 当 $0\le a<m$ 情况下, $\gcd (a,m)=1$ 可以推得 $a$ 是 ${\mathbb{Z}}_m$ 中的 unit, 故结论成立.

当 $a\ge m$ 情况下, 存在 $0\le a^{\prime }<m$ 使得 $a=a^{\prime }(\text{mod}m)$, 即 $a=a^{\prime }+km$ ($k\in \mathbb{Z}$). 假设 $\gcd (a^{\prime },m)=d$, 则有
$$\begin{array}{cc}& d|a^{\prime },d|m\\ \Rightarrow & d|(a^{\prime }+km)\\ \Rightarrow & d|a,d|m\\ \Rightarrow & \gcd (a,m)=d\\ \Rightarrow & d=1\\ \Rightarrow & \gcd (a^{\prime },m)=1\end{array}$$
根据已证明的第一部分内容可得
$$\begin{gathered} {a^{\prime }}^{\varphi (m)}\equiv 1(\text{mod}m) \\ \Rightarrow (a-km{)}^{\varphi (m)}\equiv 1(\text{mod}m) \end{gathered}$$
因为 $\varphi (m)$ 是正整数,
$$\begin{gathered} (a-km{)}^{\varphi (m)}=a^{\varphi (m)}+km(\ast ) \\ \Rightarrow (a-km{)}^{\varphi (m)}\equiv a^{\varphi (m)}(\text{mod}m) \end{gathered}$$
最后得到 $a^{\varphi (m)}\equiv 1(\text{mod}m)$.

当 $a<0$ 情况下, 存在 $0\le a^{\prime \prime }<m$, 满足 $a^{\prime \prime }=a+lm$ ($l\in \mathbb{Z}$). 类似 “当 $a\ge m$ 情况下” 的证明, 可以得到 $a^{\varphi (m)}\equiv 1(\text{mod}m)$.

这样就完成了整个欧拉定理的证明. 欧拉定理是 RSA 非对称加密算法的基础理论.

---

II. 算法原理

1. 扩展欧几里得算法

[II-1-1] 裴蜀定理 Bézout’s Theorem

Let $a$ and $b$ be integers with greatest common divisor $d$. Then there exist integers $x$ and $y$ such that
$$d=ax+by$$
Thus, the greatest common divisor of $a$ and $b$ is an integer linear combination of $a$ and $b$. Moreover, the data of the Euclidean algorithm can be used to determine an explicit pair of integers $x$ and $y$ such that $d=ax+by$.

[证明]^[3]

已知 $d=\gcd (a,b)$, 故 $d|ax+by$ 对任意的 $x,y$.

$ax+by$ 随 $x$ 和 $y$ 变化, 必存在 $x=x^{\prime }$ 和 $y=y^{\prime }$ 时使得 $ax+by$ 取得最小正值 $d^{\prime }$, 即 $d^{\prime }=a{x}^{\prime }+b{y}^{\prime }$. 此时同样满足 $d|d^{\prime }$.

下面就是要证明 $d^{\prime }$ 等于最大公因数 $d$.

由除法定理 (Devision theorem) 存在 $q_a,r_a\in \mathbb{Z}$ 满足 $a=d^{\prime }{q}_a+r_a$, 其中 $0\le q_a,0\le r_a<d^{\prime }$ ($a$ 被除数, $d^{\prime }$ 除数, $q$ 商, $r$ 余数), 移项得到 $r_a=a-q_a(a{x}^{\prime }+b{y}^{\prime })=a(1-q_a{x}^{\prime })+b(-q_a{y}^{\prime })$.

可知 $r_a$ 也是 $a,b$ 的线性组合, 且非负. 已经假设了 $d^{\prime }$ 是 $a,b$ 线性组合得到的最小正值, 但由除法定理已知 $r_a<d^{\prime }$, 所以只能 $r_a=0$.

这样我们得到了 $d^{\prime }|a$.

同样地, 存在 $q_b,r_b\in \mathbb{Z}$ 满足 $b=d^{\prime }{q}_b+r_b$, $0\le q_b,0\le r_b<d^{\prime }$, 移项得 $r_b=b-q_b(a{x}^{\prime }+b{y}^{\prime })=a(-q_b{x}^{\prime })+b(1-q_b{y}^{\prime })$ $\Rightarrow$ $r_b=0$ $\Rightarrow$ $d^{\prime }|b$.

自然可知 $d^{\prime }$ 是 $a,b$ 的公约数 (公因数). 而 $d$ 是 $a,b$ 的最大公约数, 故 $d\ge d^{\prime }$. 又由于 $d|d^{\prime }$, 故 $d\le d^{\prime }$.

最后得到 $d=d^{\prime }$. 如此不定方程 $d=ax+by$ 解的存在性就证明完毕了.

[11-1-2] 欧几里得算法 Euclidean Algorithm^[4]

Given positive integers $a,b$ with $a>b\ge 0$ find $d=\gcd (a,b)$.

[Step 1] Given $a,b$, use the division theorem to write $a=bq+r$, $0\le r<b$.

[Step 2] If $r=0$, stop and output $b$; this is the gcd.

[Step 3] If $r\ne 0$, replace $(a,b)$ by $(b,r)$. Go to [Step 1].

[例] 求 756, 123 的 gcd
$$\begin{array}{lc}\text{Steps}& \text{Calculation}\\ \text{[Step 1]}& 756=123\times 6+18,r=18\\ \text{[Step 3]}& r\ne 0,(a,b)=(123,18)\\ \text{[Step 1]}& 123=18\times 6+15,r=15\\ \text{[Step 3]}& r\ne 0,(a,b)=(18,15)\\ \text{[Step 1]}& 18=15\times 1+3,r=3\\ \text{[Step 3]}& r\ne 0,(a,b)=(15,3)\\ \text{[Step 1]}& 15=3\times 5+0,r=0\\ \text{[Step 2]}& r=0,\gcd (756,123)=3\end{array}$$

[证明]

已知 $d=\gcd (a,b)$, 结合 $r=a-bq$, 可以推得 $d|r$. 也就是说 $d|b$ 且 $d|r$, 故 $d$ 是 $b,r$ 的公约数. 两个正整数 $b,r$ 的公约数自然 “小于等于” 对应的最大公约数 $e=\gcd (b,r)$, 即 $d\le e=\gcd (b,r)$.

另一方面, 由 $e=\gcd (b,r)$ $\Rightarrow$ $e|b,e|r$ $\Rightarrow$ $e|r+bq$ $\Rightarrow$ $e|a$, 可知 $e$ 是 $a,b$ 的公因数, 那么有 $e\le d=\gcd (a,b)$.

这样就可以得到 $d=e$, 也就是说每一步计算不改变迭代变化的计算数据之间的最大公因数的值.

最后需要说明算法将在有限步计算后结束. 因为在一步除法计算中需要满足 $0\le r<b$, 而在不同迭代步的计算中余数需要满足 $a>b>r_1>r_2>\dots >r_n=0$, 只要 $a,b$ 是有限正整数, 计算步就是有限的.

这样就证明了通过有限步计算的欧几里得算法得到的最大公因数 (使得 $r=0$ 时所得) 就是初始数据的最大公因数.

[II-1-3] 扩展欧几里得算法 Extended Euclidean Algorithm

Suppose $a$ and $b$ are integers and let $d=\gcd (a,b)$. This algorithm finds $d$, $x$ and $y$ such that $ax+by=d$. (We describe only the steps when $a>b\ge 0$, since one can easily reduce to this case.)

[Step 1] Set $r_0=a$, $x_0=1$, $y_0=0$; $r_1=b,x_1=0,y_1=1$.

[Step 2] If $r_1=0$, set $d=r_0$ and terminate.

[Step 3] Use the division theorem to write $r_0=r_1{q}_2+r_2$ with $0\le r_2<r_1$.

[Step 4] Set $(r_0,r_1,x_1,y_1,x_0,y_0)=(r_1,r_2,x_0-q_2{x}_1,y_0-q_2{y}_1,x_1,y_1)$ and go to [Step 2].

[说明]

最大公约数 gcd 可以用欧几里得算法获得, 是欧几里得算法的最后一个非零余数.

在应用欧几里得算法时, 每一步计算非零余数由 $a,b$ 线性组合的系数, 直到最后一个非零余数 (= gcd) 的 $a,b$ 线性组合系数.

这就是扩展欧几里得算法求不定方程 (丢番图方程) $ax+by=d$ 的思路.

我们分步推导如下:

	Euclidean Algorithm	Extended	Results
1	$r_0=a$	$r_0=x_{0}a+y_{0}b=1\cdot a+0\cdot b$	$x_0=1,y_0=0$
2	$r_1=b$	$r_1=x_{1}a+y_{1}b=0\cdot a+1\cdot b$	$x_1=0,y_1=1$
3	$r_0÷r_1=q_2\dots r_2$	$\begin{array}{rl}{r}_2& =r_0-r_1{q}_2\\ & =(x_{0}a+y_{0}b)-(x_{1}a+y_{1}b)q_2\\ & =\underset{\triangleq x_2}{\underline{(x_0-x_1{q}_2)}}a+\underset{\triangleq y_2}{\underline{(y_0-y_1{q}_2)}}b\end{array}$	$\begin{array}{rl}{x}_2& =x_0-x_1{q}_2\\ y_2& =y_0-y_1{q}_2\end{array}$
$⋮$
i	$r_{i-2}÷r_{i-1}=q_i\dots r_i$	$\begin{array}{rl}{r}_i& =r_{i-2}-r_{i-1}{q}_i\\ & =(x_{i-2}a+y_{i-2}b)-(x_{i-1}a+y_{i-1}b)q_i\\ & =\underset{\triangleq x_i}{\underline{(x_{i-2}-x_{i-1}{q}_i)}}a+\underset{\triangleq y_i}{\underline{(y_{i-2}-y_{i-1}{q}_i)}}b\end{array}$	$\begin{array}{rl}{x}_i& =x_{i-2}-x_{i-1}{q}_i\\ y_i& =y_{i-2}-y_{i-1}{q}_i\end{array}$
$⋮$
n-1	$r_{n-3}÷r_{n-2}=q_{n-1}\dots r_{n-1}$	$\begin{array}{rl}{r}_{n-1}& =r_{n-3}-r_{n-2}{q}_{n-1}\\ & =(x_{n-3}a+y_{n-3}b)-(x_{n-2}a+y_{n-2}b)q_{n-1}\\ & =\underset{\triangleq x_{n-1}}{\underline{(x_{n-3}-x_{n-2}{q}_{n-1})}}a+\underset{\triangleq y_{n-1}}{\underline{(y_{n-3}-y_{n-2}{q}_{n-1})}}b\end{array}$	$\begin{array}{rl}{x}_{n-1}& =x_{n-3}-x_{n-2}{q}_{n-1}\\ y_{n-1}& =y_{n-3}-y_{n-2}{q}_{n-1}\end{array}$
n	$\begin{array}{rl}{r}_{n-2}÷r_{n-1}& =q_n\\ r_n& =0\end{array}$	$\begin{array}{rl}0& =r_{n-2}-r_{n-1}{q}_n\\ & =(x_{n-2}a+y_{n-2}b)-(x_{n-1}a+y_{n-1}b)q_n\\ & =\underset{\triangleq x_n}{\underline{(x_{n-2}-x_{n-1}{q}_n)}}a+\underset{\triangleq y_n}{\underline{(y_{n-2}-y_{n-1}{q}_n)}}b\end{array}$	$\begin{array}{rl}{x}_n& =x_{n-2}-x_{n-1}{q}_n\\ y_n& =y_{n-2}-y_{n-1}{q}_n\end{array}$

最后的结果为

$$\{\begin{array}{rl}d& =r_{n-1}\\ x& =x_{n-1}\\ y& =y_{n-1}\end{array}$$
需要明确, $\gcd (a,b)=d=r_{n-1}$ 是唯一确定的, 但 $ax+by=d$ 为不定方程, 有无穷多组解.

每一组具体的解都只能称为特解, 有下式成立
$$a{x}_{n-1}+b{y}_{n-1}=d\text{\hspace{1em}(II-1-1)}$$
上述表格中第 n 步计算提供了获得通解的线索, 因为知道
$$a{x}_n+b{y}_n=0\text{\hspace{1em}(II-1-2)}$$
式 (II-1-1) 和 (II-1-2) 结合可得
$$\begin{gathered} (a{x}_{n-1}+b{y}_{n-1})+k(a{x}_n+b{y}_n)=d \\ \Rightarrow a(x_{n-1}+k{x}_n)+b(y_{n-1}+k{y}_n)=d \end{gathered}$$
其中 $k$ 为任意整数. 最后不定方程 $ax+by=d$ 的通解为
$$\{\begin{array}{rl}x& =x_{n-1}+k{x}_n\\ y& =y_{n-1}+k{y}_n\end{array}\text{\hspace{1em}(II-1-3)}$$

利用扩展欧几里得算法计算得到的特解可能为正值也可为负值, 我们实际计算中多用到正整数, 通解公式 (II-1-3) 就可以将解适配到合适的区域.

---

2. RSA 非对称加密算法

[II-2-1] RSA algorithm^[5]

[I-Genertaing Keys-Receiver]

[Step 1] Choose $p,q$, two large prime numbers

[Step 2] Calculate $n=pq$, and calculate $\varphi (n)=(p-1)(q-1)$

[Step 3] Choose $e$ such that $\gcd (\varphi (n),e)=1$ and $1<e<\varphi (n)$

[Step 4] Choose a positive integer $d$, such that $ed\equiv 1(\text{mod}\varphi (n))$

[Step 5] The private key is { d , n } \{d,n\} {d,n} and the public key is { e , n } \{e,n\} {e,n}, release the public key

[II-Encrypting Message-Sender]

[Step 6] Encrypt a message $M$ ($<n$) by using the public key { e , n } \{e,n\} {e,n}: $C=M^e(\text{mod}n)$

[III-Decrypting Message-Receiver]

[Step 7] Decrypt the message $C$ by using the private key { d , n } \{d,n\} {d,n}: $M^{\prime }=C^d(\text{mod}n)$

[说明]

RSA 算法的安全性依赖于大数的质因数分解, 给定一个大的合数 $n$ 很难在短时间内质因数分解为 $p,q$.

根据 “[I-3-1] 欧拉函数 Euler $\varphi$-Function” 及其 “[I-3-2] 可乘性 Multiplicative Property”, 可知 [Step 2] 中
$$\varphi (n)=\varphi (p)\varphi (q)=(p-1)(q-1)\text{\hspace{1em}(II-2-1)}$$
就是 $n$ 的欧拉函数.

[Step 3] 中就是选择一个和欧拉函数 $\varphi (n)$ 互质的数值 $e$. (最简单的实现, 选择一个小于 $\varphi (n)$ 的质数作为 $e$.)

已知 $\gcd (\varphi (n),e)\equiv 1$, 由 “[II-1-1] 裴蜀定理 Bézout’s Theorem”, 存在 $x,y$ 使得 $\varphi (n)x+ey=1$ 成立. [Step 4] 中 $ed\equiv 1(\text{mod}\varphi (n))$ 等价于 $\varphi (n)x+ed=1$ ($x\in \mathbb{Z}$). 这里的 $d$ 就是裴蜀定理中的 $y$, 直接可以利用 “[II-1-2] 扩展欧几里得算法 Extended Euclidean Algorithm” 计算获得 $d$ 的特解.

又因为我们的推导都在正整数范围内展开, 利用通解计算式 (II-1-3), 使得 $d$ 适配到正整数范围.

[Step 5] 中获得的公钥需要公布给信息发送者, 而私钥由接受者严格保密保存. 即使第三方知道公钥也无法破解获知私钥.

[Step 6] 中信息发送者利用公钥加密信息, 并发送加密后的信息给到信息接收者.

[Step 7] 中信息接收者利用私钥解密已加密的信息, 获得信息原文. 如何证明解密后的信息一定是原始信息呢 ? 由加密和解密过程可知
$$M^{\prime }\equiv C^d(\text{mod}n)\equiv (M^e{)}^d(\text{mod}n)\text{\hspace{1em}(II-2-2)}$$
又 $\varphi (n)x+ed=1$ $\Rightarrow$ $ed=1-\varphi (n)x$, 代入上式得到
$$\begin{array}{rl}{M}^{\prime }& \equiv (M^e{)}^d(\text{mod}n)\\ & \equiv M^{1-\varphi (n)x}(\text{mod}n)\\ & \equiv M\cdot {\left(M^{\varphi (n)}\right)}^{-x}(\text{mod}n)\end{array}\text{\hspace{1em}(II-2-3)}$$
需知要传送的信息数值 $M$ 是不受加密算法限制的, 故下面根据 $M$ 与 $n$ 两者之间互质关系分类讨论.

由算数基本定理可知信息数值 $M$ 可以分解为
$$M=m{p}^{k_1}{q}^{k_2}\text{\hspace{1em}(II-2-4)}$$
其中 $m$ 中不含 $p,q$ 因子, 即 $\gcd (m,pq)=1$. 根据信息数值 $M$ 中是否含有 $p,q$ 因子分解为以下四类情况
$$\{\begin{array}{rl}\text{Case I}& :k_1=0,k_2=0\\ \text{Case II}& :k_1\ge 1,k_2\ge 1\\ \text{Case III}& :k_1\ge 1,k_2=0\\ \text{Case IV}& :k_1=0,k_2\ge 1\end{array}$$
[Case 1] $M$ 中不含有 $p,q$ 因子. 一般 $p$ 和 $q$ 这两个不同质数的取值大于信息元素的编码值, 即 $p,q>M\ge 0$, 这样可以确保 [Case I] 的发生, 此时 $M$ 与 $n=pq$ 互质. 满足 “[I-3-3] 欧拉定理 Euler’s Theorem” 的条件, 可得 $M^{\varphi (n)}\equiv 1(\text{mod}n)$, 代入式 (II-2-3) 得到
$$\begin{array}{rl}{M}^{\prime }& \equiv M\cdot {\left(M^{\varphi (n)}\right)}^{-x}(\text{mod}n)\\ & \equiv M\cdot 1^{-x}(\text{mod}n)\\ & \equiv M(\text{mod}n)\end{array}\text{\hspace{1em}(II-2-5)}$$
这样就证明了 “在 $M$ 和 $n$ 互质情况下, 解密后的信息一定是原始信息”.

下面的三种情况, $M$ 与 $n=pq$ 都不互质.

[Case II] 此时 $M$ 含有 $p$ 和 $q$ 因子, 即 $M$ 是 $n$ ($=pq$) 的倍数, 也就是说 $M\equiv 0(\text{mod}n)$. 代入加密公式 (II-2-2)
$$M^{\prime }\equiv (M^e{)}^d\equiv 0(\text{mod}n)$$
这种情况下, 任何信息都加密输出为 $0$, 实际应用中是没有意义的, 故排除此种情况. 故算法中要求 $M<n$.

[Case III] 此时 $M$ 中含有 $p$ 因子, 即 $M\equiv 0(\text{mod}p)$. 但是 $M$ 中不含有 $q$ 因子, 即 $\gcd (M,q)=1$. 由欧拉定理可知
$$M^{\varphi (q)}\equiv 1(\text{mod}q)\text{\hspace{1em}(II-2-6)}$$
由模运算的性质继续推得
$$\begin{gathered} {\left(M^{\varphi (q)}\right)}^{-x\varphi (p)}\equiv 1^{-x\varphi (p)}\equiv 1(\text{mod}q) \\ \Rightarrow {\left(M^{\varphi (q)}\right)}^{-x\varphi (p)}=1+k_{q}q(k_q\in \mathbb{Z})\text{\hspace{1em}(II-2-7)} \end{gathered}$$
上式结合 $\varphi (n)=\varphi (p)\varphi (q)$, 得到
$${\left(M^{\varphi (n)}\right)}^{-x}=1+k_{q}q\text{\hspace{1em}(II-2-8)}$$
另外已知$M$ 中含有 $p$ 因子, $Mq$ 中含有 $n$ ($=pq$) 因子, 即 $n|Mq$.

将式 (II-2-8) 代入式 (II-2-3)
$$\begin{array}{rl}{M}^{\prime }& \equiv M\cdot {\left(M^{\varphi (n)}\right)}^{-x}(\text{mod}n)\\ & \equiv M\cdot (1+k_{q}q)(\text{mod}n)\\ & \equiv M+k_{q}Mq(\text{mod}n)\\ & \equiv M(\text{mod}n)\end{array}$$
这样就证明了 “在 $M$ 是 $p$ 的倍数但 $M$ 不是 $q$ 的倍数情况下, 解密后的信息一定是原始信息”.

[Case IV] 同上, 可以证明了 “在 $M$ 是 $q$ 的倍数但 $M$ 不是 $p$ 的倍数情况下, 解密后的信息一定是原始信息”.

这样证明了 [II-2-1] RSA algorithm 的有效性.

实际情况下 $p$ 和 $q$ 都选得足够大, 使得信息数值 $M$ 与 $p,q$ 都互质.

---

III. 算法实现

1. 源代码

### RSA Encryption
### wzf@robotics_notes 
### https://blog.csdn.net/woyaomaishu2

import math

def find_integer_prime_phi_n(phi_n):
## 寻找和 phi_n 互质的整数
## 此处实现为: 寻找最小的质数, 该质数不能整除 phi_n
    candidate_e = 1
    prime_flag = False
    candidate_flag = False
    while not candidate_flag:
        while not prime_flag:
            prime_flag = True
            candidate_e = candidate_e + 1
            # 尝试判断下一个整数是否为质数
            for i in range(2, int(math.sqrt(candidate_e))+1):
                if candidate_e % i == 0:
                    # 如果被任何 [2, sqrt(candidate_e)] 区间内的整数乘除
                    # 则 candidate_e 不是质数 
                    prime_flag = False
                    break
        if phi_n % candidate_e == 0:
            candidate_flag = False
            prime_flag = False
            # 如果寻找到的质数 candiate_e 整除 欧拉 phi-函数
            # 则舍弃该 candidate_e, 继续寻找下一个
        else:
            candidate_flag = True
            # 找到不能整除 欧拉 phi-函数的整数(质数)
    return candidate_e


def extended_eculidean_algorithm(a, b):
## 扩展欧几里得算法 extended euclidean algorithm
    x_new = 0
    x_old = 1
    y_new = 1
    y_old = 0
    r_new = b
    r_old = a 
    while r_new != 0:  # 余数不等于 0, 执行以下更新
        quotient = r_old // r_new # 新商
        temp_r_old = r_new        
        r_new = r_old - quotient * r_new  # 更新新的余数
        r_old = temp_r_old

        temp_x_old = x_new
        x_new = x_old - quotient * x_new  # 扩展欧几里得算法的分步推导表
        x_old = temp_x_old

        temp_y_old = y_new
        y_new = y_old - quotient * y_new  # 扩展欧几里得算法的分步推导表
        y_old = temp_y_old
    
    print("[a]: {0}, [b]:{1}, [x_old]:{2}, [x_old]:{3}, [r_old]:{4}, [x_new]:{5}, [y_new]:{6}, [r_new]:{6}"
          .format(a, b, x_old, y_old, r_old, x_new, y_new, r_new))
    if y_old <= 0:
        y_old += y_new  # 通解公式 (II-1-3) 将 d 适配为正整数

    return y_old


def generate_keys(p, q):
## 产生公钥和私钥
    n = p*q         # 两个的“大质数”的乘积
    phi_n = (p-1)*(q-1) 
    # Euler phi-Function of n: phi_n = (p-1)*(q-1)
    
    e = find_integer_prime_phi_n(phi_n)
    # 选择一个一个正整数 e, 使得  
    # 1 < e < phi_n, 
    # 且 e 与 phi(n) 互质, 即 gcd(e, phi_n) = 1

    d =  extended_eculidean_algorithm(phi_n, e) 
    # 利用 extended euclidean algorithm 计算正整数 d, 满足 d*e ≡ 1 (mod phi_n)

    public_key = (e,n)
    private_key = (d,n)
    return public_key, private_key


def encrypt_message(message, public_key):
## 利用公钥 (e,n) 对原始信息进行加密
    e,n = public_key
    message_integer = []
    for character in message:
        message_integer.append(ord(character))
    # ascii values of message

    print("message_integer:", message_integer)
    # for illustrative purpose only

    ciphertext = []
    for a in message_integer:
        cipher = pow(a, e) % n  #[Step 6] Encrypt a message
        ciphertext.append(cipher)
    # b ≡ a^e (mod n)

    return ciphertext   # 返回密文


def decrypt_message(ciphertext, private_key):
## 利用私钥对秘文进行解密
    d,n = private_key   
    decrypted_message_integer = []
    for b in ciphertext:
        decrypted = pow(b, d) % n    #[Step 7] Decrypt the message
        decrypted_message_integer.append(decrypted)

    print("decrypted_message_integer:", decrypted_message_integer)
    decrypted_message = ""
    for i in decrypted_message_integer:
        decrypted_message += chr(i)
    
    return decrypted_message


if __name__ == '__main__':
    # p = 811 # 选择两个的“大质数”
    # q = 929
    p = 691 # 选择两个的“大质数”, 会使 d 的特解为负, 会利用通解公式 (II-1-3) 适配
    q = 701
    message = "Hello_world -> RSA algorithm. [1#$%*&^]! ~~~"    
    # 原始信息
    print("message (ascii):", message)

    ##  Stage I REceiver 制作秘钥 ##
    public_key, private_key = generate_keys(p, q)
    e,n = public_key    # public key 公钥
    d,n = private_key   # private key 私钥
    print("Public key: ({0},{1})".format(e, n) )
    print("Private key: ({0},{1})".format(d, n) )

    ## Stage II Sender 加密信息 ##
    ciphertext = encrypt_message(message, public_key)
    print("ciphertext:", ciphertext)
    # # -- for illustrative purpose only
    encrypted = ""
    for cipher in ciphertext:
        encrypted = encrypted + chr(cipher)
    print("Encrypted (ascii):", encrypted)
    # # --

    ## Stage III Receiver 解密信息 ##
    decrypted_message = decrypt_message(ciphertext, private_key)
    print("decrypted_message (ascii):", decrypted_message)
    

---

2. 测试结果

---

总结

从初等数论基础开始, 推导算法数学原理 (欧拉定理)、扩展欧几里得算法、RSA 算法原理, 最后 Python 实现了 RSA 算法 demo.

---

参考文献

[1] Ronald S. Irving, “Integers, Polynomials, and Rings: A Course in Algebra”, 2003, Springer

[2] “Definition:Ring of Integers Modulo m”, https://proofwiki.org/wiki/Definition:Ring_of_Integers_Modulo_m

[3] 百度百科, “裴蜀定理”, https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593

[4] Brilliant.org, “Euclidean Algorithm”, https://brilliant.org/wiki/euclidean-algorithm/

[5] “Asymmetric Cryptography: The RSA algorithm (with examples)”, https://justcryptography.com/rsa-algorithm/