8.4 构建一个小型 RSA 系统

第 8.3 节建立了三件工具：

模幂运算可以在有限剩余系统中计算幂；

扩展欧几里得算法可以寻找模逆元；

中国剩余定理可以连接不同互素因子下的计算。

RSA 把这些工具组装成一个公钥密码系统。

本节故意使用很小的数字，让每一步都能看清。这种密钥只能用于教学，不具备任何实际安全性。

公钥系统的基本思想

在传统的共享密钥系统中，发送方与接收方必须事先持有同一份秘密密钥。

公钥系统改用一对相互关联的密钥：

公钥可以公开分发，本节用它加密；

私钥必须保密，本节用它解密。

当实际参数足够大时，即使知道公钥，也不应当能够在可接受时间内重建私钥操作。

RSA 把一段消息表示为整数 $m$ ，并要求

0\le m<n,

其中 $n$ 是公钥的一部分。

欧拉函数统计可逆剩余

生成密钥之前，还需要定义一个新函数。

对正整数 $n$ ，欧拉函数 $\varphi(n)$ 统计集合

\{1,2,\ldots,n-1\}

中与 $n$ 互素的整数个数。

例如，小于 $10$ 且与 $10$ 互素的正整数为

1,3,7,9,

所以

\varphi(10)=4.

如果 $p$ 是素数，那么从 $1$ 到 $p-1$ 的每个整数都与 $p$ 互素。因此

\varphi(p)=p-1.

若 $p,q$ 是两个不同的素数，则

\varphi(pq)=(p-1)(q-1).

可以从 $1$ 到 $pq$ 开始计数，再排除 $p$ 或 $q$ 的倍数。使用容斥原理得到

pq-q-p+1=(p-1)(q-1).

欧拉定理解释指数循环

欧拉定理说明，若 $\gcd(m,n)=1$ ，则

m^{\varphi(n)}\equiv1\pmod n.

也就是说，一个与 $n$ 互素的剩余经过 $\varphi(n)$ 次幂后会回到 $1$ 。

RSA 会选择两个指数，使它们的乘积模 $\varphi(n)$ 同余于 $1$ 。欧拉定理随后保证其中一个指数可以撤销另一个指数。

逐步生成 RSA 密钥

第 1 步：选择两个不同素数

选择

p=5,qquad q=11.

真实 RSA 会使用大得多、并且随机生成的素数。

第 2 步：构造模数

把两个素数相乘：

n=pq=5\cdot11=55.

模数 $n$ 同时属于公钥与私钥系统。

第 3 步：计算欧拉函数

因为 $p,q$ 是不同素数，

\varphi(n)=(p-1)(q-1)=4\cdot10=40.

第 4 步：选择公钥指数

选择整数 $e$ ，满足

1<e<\varphi(n)

以及

\gcd(e,\varphi(n))=1.

这里选择

e=3.

因为 $\gcd(3,40)=1$ ，所以它是有效选择。

第 5 步：计算私钥指数

令 $d$ 为 $e$ 模 $\varphi(n)$ 的逆元：

ed\equiv1\pmod{\varphi(n)}.

这里

3\cdot27=81=2\cdot40+1,

所以

d=27.

最终得到

\text{公钥 }(n,e)=(55,3)

以及

\text{私钥指数 }d=27.

在真实系统中，素数与欧拉函数也必须保密，因为知道它们就能轻易重建 $d$ 。

正在加载交互实验...

把素数芯片装入小型 RSA 密钥机。工作台会拒绝重复素数或合数输入，把每个候选公钥指数与欧拉函数的关系显示出来，并让扩展欧几里得齿轮只在逆元证书有效时生成私钥指数。

正在加载概念检查...

正在加载本节练习...

加密一段消息

给定公钥 $(n,e)$ ，通过

c\equiv m^e\pmod n

加密消息整数 $m$ ，其中 $c$ 叫作密文。

令

m=7.

因为 $0\le7<55$ ，所以它是有效消息块。使用公钥 $(55,3)$ 加密：

c\equiv7^3=343\equiv13\pmod{55}.

实际发送的密文为

c=13.

使用私钥指数解密

通过

m'\equiv c^d\pmod n

解密。

对当前玩具密钥，

m'\equiv13^{27}\pmod{55}.

直接计算 $13^{27}$ 会产生没有必要的巨大整数。更好的方法是重复平方。

计算指数不断翻倍的幂：

\begin{aligned} 13^1&\equiv13\pmod{55},\\ 13^2&\equiv4\pmod{55},\\ 13^4&\equiv16\pmod{55},\\ 13^8&\equiv36\pmod{55},\\ 13^{16}&\equiv31\pmod{55}. \end{aligned}

因为

27=16+8+2+1,

组合对应的各行：

13^{27} \equiv31\cdot36\cdot4\cdot13 \equiv7\pmod{55}.

所以

m'=7,

原消息成功恢复。

两个指数为什么能够互相撤销

密钥等式

ed\equiv1\pmod{\varphi(n)}

表示存在整数 $k$ ，使得

ed=1+k\varphi(n).

当消息 $m$ 与 $n$ 互素时，欧拉定理给出

\begin{aligned} m^{ed} &=m^{1+k\varphi(n)}\\ &=m\left(m^{\varphi(n)}\right)^k\\ &\equiv m\cdot1^k\\ &\equiv m\pmod n. \end{aligned}

先加密再解密相当于把 $m$ 提升到指数 $ed$ ，所以最终会回到原来的剩余。

上面的证明假设 $\gcd(m,n)=1$ 。RSA 对两个不同素数乘积模数下的全部剩余也成立；完整证明会分别在模 $p$ 和模 $q$ 下检查同余，再通过中国剩余定理合并。本节的互素情况已经呈现了最核心的指数循环机制。

重复平方是一种算法

任何指数都可以写成若干个 $2$ 的幂之和。重复平方只计算

m,m^2,m^4,m^8,m^{16},\ldots

这些必要的幂，并在每次乘法后模 $n$ 取余。

对于指数 $e$ ，这种方法只需 $O(\log e)$ 个平方与乘法阶段，而不必把 $m$ 连乘 $e-1$ 次。这把模运算重新连接到了第 5 章的对数增长分析。

正在加载交互实验...

让数字消息依次通过公钥加密站与私钥解密站。实时指数阶梯会显示每一次平方与乘法得到的剩余；修改密文或替换私钥指数后，还能直接观察消息在哪一步无法恢复。

正在加载概念检查...

正在加载本节练习...

为什么课堂系统并不安全

模数 $55$ 可以立刻分解成 $5\cdot11$ 。任何能分解 $n$ 的人都可以计算 $\varphi(n)$ ，再利用公开指数 $e$ 重建 $d$ 。

真实 RSA 的安全性依赖经过严格生成的大素数和成熟的密码学实现。未经处理的教科书 RSA 具有确定性，并且容易受到多种攻击。安全应用会使用标准化的随机填充，例如用于加密的 RSA-OAEP，并依赖经过审查的密码库。

绝不能照搬本节的玩具算术来设计生产密码系统。本节的目标是展示数学机制，而不是给出安全软件规范。

注意

RSA 密钥生成连接了素因数分解、欧拉函数、最大公约数与模逆元；加密和解密都是模幂运算，并通过重复平方变得可计算。

本章衔接

第 8 章建立了整数的算术结构：整除导向唯一素因数分解，欧几里得算法产生最大公约数与贝祖系数，同余构造有限剩余系统，中国剩余定理对齐多个系统，而 RSA 又把它们组合成公钥机制。

第 9 章将介绍离散概率。第 6 章的计数方法会用来定义概率，而模运算与密码学中的例子也会引出随机选择与不确定性。

8.4 构建一个小型 RSA 系统

第 8.3 节建立了三件工具：

模幂运算可以在有限剩余系统中计算幂；

扩展欧几里得算法可以寻找模逆元；

中国剩余定理可以连接不同互素因子下的计算。

RSA 把这些工具组装成一个公钥密码系统。

本节故意使用很小的数字，让每一步都能看清。这种密钥只能用于教学，不具备任何实际安全性。

公钥系统的基本思想

在传统的共享密钥系统中，发送方与接收方必须事先持有同一份秘密密钥。

公钥系统改用一对相互关联的密钥：

公钥可以公开分发，本节用它加密；

私钥必须保密，本节用它解密。

当实际参数足够大时，即使知道公钥，也不应当能够在可接受时间内重建私钥操作。

RSA 把一段消息表示为整数 $m$ ，并要求

0\le m<n,

其中 $n$ 是公钥的一部分。

欧拉函数统计可逆剩余

生成密钥之前，还需要定义一个新函数。

对正整数 $n$ ，欧拉函数 $\varphi(n)$ 统计集合

\{1,2,\ldots,n-1\}

中与 $n$ 互素的整数个数。

例如，小于 $10$ 且与 $10$ 互素的正整数为

1,3,7,9,

所以

\varphi(10)=4.

如果 $p$ 是素数，那么从 $1$ 到 $p-1$ 的每个整数都与 $p$ 互素。因此

\varphi(p)=p-1.

若 $p,q$ 是两个不同的素数，则

\varphi(pq)=(p-1)(q-1).

可以从 $1$ 到 $pq$ 开始计数，再排除 $p$ 或 $q$ 的倍数。使用容斥原理得到

pq-q-p+1=(p-1)(q-1).

欧拉定理解释指数循环

欧拉定理说明，若 $\gcd(m,n)=1$ ，则

m^{\varphi(n)}\equiv1\pmod n.

也就是说，一个与 $n$ 互素的剩余经过 $\varphi(n)$ 次幂后会回到 $1$ 。

RSA 会选择两个指数，使它们的乘积模 $\varphi(n)$ 同余于 $1$ 。欧拉定理随后保证其中一个指数可以撤销另一个指数。

逐步生成 RSA 密钥

第 1 步：选择两个不同素数

选择

p=5,qquad q=11.

真实 RSA 会使用大得多、并且随机生成的素数。

第 2 步：构造模数

把两个素数相乘：

n=pq=5\cdot11=55.

模数 $n$ 同时属于公钥与私钥系统。

第 3 步：计算欧拉函数

因为 $p,q$ 是不同素数，

\varphi(n)=(p-1)(q-1)=4\cdot10=40.

第 4 步：选择公钥指数

选择整数 $e$ ，满足

1<e<\varphi(n)

以及

\gcd(e,\varphi(n))=1.

这里选择

e=3.

因为 $\gcd(3,40)=1$ ，所以它是有效选择。

第 5 步：计算私钥指数

令 $d$ 为 $e$ 模 $\varphi(n)$ 的逆元：

ed\equiv1\pmod{\varphi(n)}.

这里

3\cdot27=81=2\cdot40+1,

所以

d=27.

最终得到

\text{公钥 }(n,e)=(55,3)

以及

\text{私钥指数 }d=27.

在真实系统中，素数与欧拉函数也必须保密，因为知道它们就能轻易重建 $d$ 。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

加密一段消息

给定公钥 $(n,e)$ ，通过

c\equiv m^e\pmod n

加密消息整数 $m$ ，其中 $c$ 叫作密文。

令

m=7.

因为 $0\le7<55$ ，所以它是有效消息块。使用公钥 $(55,3)$ 加密：

c\equiv7^3=343\equiv13\pmod{55}.

实际发送的密文为

c=13.

使用私钥指数解密

通过

m'\equiv c^d\pmod n

解密。

对当前玩具密钥，

m'\equiv13^{27}\pmod{55}.

直接计算 $13^{27}$ 会产生没有必要的巨大整数。更好的方法是重复平方。

计算指数不断翻倍的幂：

\begin{aligned} 13^1&\equiv13\pmod{55},\\ 13^2&\equiv4\pmod{55},\\ 13^4&\equiv16\pmod{55},\\ 13^8&\equiv36\pmod{55},\\ 13^{16}&\equiv31\pmod{55}. \end{aligned}

因为

27=16+8+2+1,

组合对应的各行：

13^{27} \equiv31\cdot36\cdot4\cdot13 \equiv7\pmod{55}.

所以

m'=7,

原消息成功恢复。

两个指数为什么能够互相撤销

密钥等式

ed\equiv1\pmod{\varphi(n)}

表示存在整数 $k$ ，使得

ed=1+k\varphi(n).

当消息 $m$ 与 $n$ 互素时，欧拉定理给出

\begin{aligned} m^{ed} &=m^{1+k\varphi(n)}\\ &=m\left(m^{\varphi(n)}\right)^k\\ &\equiv m\cdot1^k\\ &\equiv m\pmod n. \end{aligned}

先加密再解密相当于把 $m$ 提升到指数 $ed$ ，所以最终会回到原来的剩余。

重复平方是一种算法

任何指数都可以写成若干个 $2$ 的幂之和。重复平方只计算

m,m^2,m^4,m^8,m^{16},\ldots

这些必要的幂，并在每次乘法后模 $n$ 取余。

对于指数 $e$ ，这种方法只需 $O(\log e)$ 个平方与乘法阶段，而不必把 $m$ 连乘 $e-1$ 次。这把模运算重新连接到了第 5 章的对数增长分析。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

为什么课堂系统并不安全

模数 $55$ 可以立刻分解成 $5\cdot11$ 。任何能分解 $n$ 的人都可以计算 $\varphi(n)$ ，再利用公开指数 $e$ 重建 $d$ 。

绝不能照搬本节的玩具算术来设计生产密码系统。本节的目标是展示数学机制，而不是给出安全软件规范。

注意

RSA 密钥生成连接了素因数分解、欧拉函数、最大公约数与模逆元；加密和解密都是模幂运算，并通过重复平方变得可计算。

本章衔接

第 9 章将介绍离散概率。第 6 章的计数方法会用来定义概率，而模运算与密码学中的例子也会引出随机选择与不确定性。