本节对应原书 PDF 第 301–304 页。定义、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

13.1.1 恺撒密码

数论在密码学中起着重要的作用. 早在公元前罗马皇帝恺撒(J. Caesar)就已经使用密码传递作战命令. 他的加密方法是把每个字母按字母表的顺序向后移动 3 位，最后 3 个字母依次变成前 3 个字母. 例如，“SEE YOU TOMORROW”，经过加密变成“VHHBRXWRPRUURZ”(忽略掉空格).

所谓密码，简单地说就是一组含有参数 k 的变换 E. 信息 m 通过变换 E 得到 c=E(m). 原始信息 m 称作明文，经过变换得到的信息 c 称作密文. 从明文得到密文的过程称作加密，变换 E 称作加密算法，参数 k 称作密钥. 同一个加密算法，可以取不同密钥，给出不同的加密结果.

恺撒的加密算法是把字母按字母表的顺序循环移动 k 位. 取 k=3 就是前面所说的加密算法. 用数字 0\sim 25 分别表示 26 个字母，这个算法可表示成

E(i)=(i+k)\bmod 26 \quad i=0,1,\cdots,25

其中密钥 k 是任意的整数. 仍用前面的例子，“SEE YOU TOMORROW” 数字化后为

18\ 4\ 4\ 24\ 14\ 20\ 19\ 14\ 12\ 14\ 17\ 17\ 14\ 22

取 k=3，加密后得到密文

21\ 7\ 7\ 1\ 17\ 23\ 22\ 17\ 15\ 17\ 20\ 20\ 17\ 25

即 VHHBRXWRPRUURZ.

从密文 c 恢复明文 m 的过程称作解密. 解密算法 D 是加密算法 E 的逆运算. 解密算法也含有参数，称为解密算法的密钥. 解密算法的密钥与加密算法的密钥有关，传统密码的解密算法的密钥可以由加密算法的密钥推出. 恺撒密码的解密算法是

D(i)=(i-k)\bmod 26 \quad i=0,1,\cdots,25

它的解密算法的密钥与加密算法的密钥相同.

密码要求加密算法 E 是容易计算的. 只要知道密钥，解密算法的计算也是容易的. 关键之处是要求，如果不知道密钥，就不可能(至少是很难)从密文 c 恢复明文 m. 万一密文落入第三者手中，只要第三者得不到密钥就无法知道明文的内容. 可见保证密钥的安全是至关重要的.

解读：加密与解密这一对算法是互逆的，但"难易"并不对称——设计密码时，合法用户拿着密钥必须在瞬间完成运算，而攻击者没有密钥时必须无从下手。密码学的全部难度都来自这道不对称的鸿沟。

恺撒密码的加密算法太简单. 如果有足够长的密文，通过统计各个字母以及字母之间关联出现的频率可以破解出密钥，因此恺撒密码是不安全的. 这种类型的稍微复杂一点的加密算法是

E(i)=(ai+b)\bmod 26 \quad i=0,1,\cdots,25

其中 a 和 b 是整数. 为了保证 E 是双射，a 应满足一定的条件(见习题 13.3).

解读：E(i)=(ai+b)\bmod 26 只是在字母表上做了一次"整体缩放加平移"。它仍属于单表代换，频率分布的形状原封不动地被搬过去，所以统计破译法照样有效。

用一个字母代替另一个字母的密码很容易被分析字母频率的方法破译. 更复杂一些的加密算法是用一段字母代替另一段字母. 例如，维吉利亚(Vigenere)密码先把明文分成若干段，每一段有 n 个数字，密钥 k=k_1k_2\cdots k_n，加密算法

E(m_1m_2\cdots m_n)=c_1c_2\cdots c_n

其中 c_i=(m_i+k_i)\bmod 26，m_i=0,1,\cdots,25，i=1,2,\cdots,n.

解读：维吉利亚密码对第 i 位用第 i 个密钥分量移位，同一个明文字母在不同位置会被移成不同的密文字母，于是单个字母的频率被"抹平"，统计破译随之失效。

13.1.2 RSA 公钥密码

传统密码的密钥是对称的，只要知道加密密钥就能推算出解密密钥. 通信双方分别持有加密密钥和解密密钥，密钥对外是绝对保密的，必须通过秘密渠道传送. 这种密码称作私钥密码.

随着计算机网络的迅速发展，私钥密码已不能适应计算机网络通信的保密需要. 第一，私钥密码的密钥不能用网络传送. 为了确保安全，应定期更新密钥，密钥的传送需要使用另外的秘密渠道，极不方便. 第二，一对密钥只能供一对通信的双方使用，而不能多方共用. 即使是一个集团内部(假设无须保密)也不能共用密钥，因为这样是极不安全的. 只要有一个人不慎或故意泄密，就会使整个保密系统崩溃，造成灾难性的后果. 假设某人要和 n 个用户进行保密通信，就需要保存 n 个加密密钥和 n 个解密密钥. n 个用户之间进行保密通信需要 \binom{n}{2} 对密钥，保管如此多的密钥是件很麻烦和不很安全的事情，何况还要经常更新.

解读：私钥体制的痛点可以归结为"密钥数量随用户数平方增长"和"密钥必须走另一条保密信道"两条；公钥体制正是为了一次性消除这两条而设计的。

迪菲(W. Diffie)和海尔门(M. Hellman)于 1976 年提出公钥密码的思想. 这种密码的密钥是非对称的，也就是说，不能从加密密钥推算出解密密钥，因而加密密钥不需要保密，可以公开，而只需保存解密密钥的秘密. 若甲将他的加密密钥公布，任何想与甲通信的人都可以使用这个加密密钥将要传送的信息(明文)加密成密文发送给甲. 只有甲自己知道解密密钥，能够把密文还原为明文. 任何第三方即使截获到密文也不可能知道密文所传送的信息.

RSA 公钥密码是瑞弗斯特(Ron Rivest)，沙米尔(Adi Shamir)和阿德来门(Len Adleeman)于 1978 年提出的，也是最有希望的一种公钥密码. 它的基础是欧拉定理(定理 11.12)，它的安全性依赖于大数因子分解的困难性.

取两个大素数 p 和 q(p\neq q)，记 n=pq，\phi(n)=(p-1)(q-1)（见习题 11.53）. 选择正整数 w，w 与 \phi(n) 互素，设 d 是 w 的模 \phi(n) 逆，即 dw\equiv 1(\bmod \phi(n)).

RSA 密码算法如下：首先将明文数字化，然后把明文分成若干段，每一个明文段的值小于 n. 对每一个明文段 m，

\text{加密算法}\quad c=E(m)=m^w \bmod n
\text{解密算法}\quad D(c)=c^d \bmod n

其中，加密密钥 w 和 n 是公开的，p、q、\phi(n) 和 d 是保密的.

解读：公开的是 (w,n)，保密的是 (p,q,\phi(n),d)。攻击者若能把 n 分解成 p 与 q，就能算出 \phi(n) 进而求出 d，所以 RSA 的安全性等价于大整数分解的困难性。

下面证明解密算法是正确的，即 m=c^d \bmod n. 由于 m<n，故只需证明 c^d\equiv m(\bmod n)，亦即 m^{dw}\equiv m(\bmod n). 因为 dw\equiv 1(\bmod \phi(n))，所以存在整数 k 使得 dw=k\phi(n)+1. 分两种可能讨论如下.

(1) m 与 n 互素. 由欧拉定理

m^{\phi(n)}\equiv 1(\bmod n)

即可得到

m^{dw}\equiv m^{k\phi(n)+1}\equiv m(\bmod n)

(2) m 与 n 不互素. 由于 m<n，n=pq，p 和 q 是素数且 p\neq q，故 m 必含 p 和 q 中的一个为因子，且只含其中的一个为因子. 不妨设 m=cp 且 q\nmid m. 由费马小定理

m^{q-1}\equiv 1(\bmod q)

于是，

m^{k\phi(n)}\equiv m^{k(p-1)(q-1)}\equiv 1^{k(p-1)}\equiv 1(\bmod q)

从而存在整数 h 使得

m^{k\phi(n)}=hq+1

两边同乘以 m，并注意到 m=cp，

m^{k\phi(n)+1}=hcpq+m=hcn+m

得证

m^{k\phi(n)+1}\equiv m(\bmod n)

即

m^{dw}\equiv m(\bmod n)

解读：这里必须分"互素"与"不互素"两支，是因为欧拉定理只在 \gcd(m,n)=1 时可用。第二支改用费马小定理在模 q 下作推导，再借 m=cp 把 hcn+m 中的 hcn 消掉，两个模的结论合起来才覆盖 m 的全部取值。

RSA 公钥密码的加密算法和解密算法都要作模乘幂运算 a^b(\bmod n). 设 b 的二进制表示为 b_{r-1}\cdots b_1b_0，即

b=b_0+b_1\times 2+\cdots+b_{r-1}\times 2^{r-1}

于是，

a^b\equiv a^{b_0}\times(a^2)^{b_1}\times\cdots\times(a^{2^{r-1}})^{b_{r-1}}(\bmod n)

令 A_0=a，A_i\equiv(A_{i-1})^2(\bmod n)，i=1,2,\cdots,r-1，则有

a^b\equiv A_0^{b_0}\times A_1^{b_1}\times\cdots\times A_{r-1}^{b_{r-1}}(\bmod n)

这里

A_i^{b_i}= \begin{cases} A_i & \text{若 } b_i=1 \\ 1 & \text{若 } b_i=0 \end{cases} \quad i=0,1,\cdots,r-1

解读：这就是"平方-乘"快速幂：先逐次平方得到 a,a^2,a^4,\cdots 共 r 个模 n 的中间值，再按 b 的二进制位挑出该乘的那些相乘。原本要做 b 次乘法的运算被压到约 2r 次，b 有几百位时这是唯一可行的做法。

例 13.1 取 p=43，q=59，n=43\times 59=2537，\phi(n)=42\times 58=2436，w=13. A，B，\cdots，Z 依次用 00，01，\cdots，25 表示，各占 2 位. 说明明文段 m=2106，即 VG. 密文 c=2106^{13}\bmod 2537. 计算如下：13 的二进制表示为 1101，即 13=1+2^2+2^3.

A_0=2106\equiv -431(\bmod 2537)
A_1\equiv(-431)^2\equiv 560(\bmod 2537)
A_2\equiv 560^2\equiv -988(\bmod 2537)
A_3\equiv(-988)^2\equiv -601(\bmod 2537)
2106^{13}\equiv(-431)\times(-988)\times(-601)\equiv 2321(\bmod 2537)

得密文 c=2321.

又设收到密文 0981，要把它恢复成明文. 计算 13^{-1}\equiv 937(\bmod 2436)，得 d=937. 明文 m'=981^{937}\bmod 2537. 计算如下：937 的二进制表示为 1110101001，即 937=1+2^3+2^5+2^7+2^8+2^9.

A_0=981
A_1\equiv 981^2\equiv 838(\bmod 2537)
A_2\equiv 838^2\equiv -505(\bmod 2537)
A_3\equiv(-505)^2\equiv 1325(\bmod 2537)
A_4\equiv 1325^2\equiv 21(\bmod 2537)
A_5\equiv 21^2\equiv 441(\bmod 2537)
A_6\equiv 441^2\equiv -868(\bmod 2537)
A_7\equiv(-868)^2\equiv -65(\bmod 2537)
A_8\equiv(-65)^2\equiv -849(\bmod 2537)
A_9\equiv(-849)^2\equiv 293(\bmod 2537)
981^{937}\equiv 981\times 1325\times 441\times(-65)\times(-849)\times 293\equiv 704(\bmod 2537)

得明文 m'=0704，即 HE.

解读：例中把中间结果都取成绝对值最小的同余数(如 2106\equiv-431)，是为了让平方后的数字小一些、便于手算；-431、-988、-601 三个底数的指数 b_0,b_2,b_3 均为 1，故三者相乘，A_1 对应的位为 0 不参与。

RSA 公钥密码的安全性依赖于大整数分解的困难性. 如果已知分解式 n=pq，容易计算出 w 的模 \phi(n)=(p-1)(q-1) 逆 d. 现在还没有在不知道分解式 n=pq 的情况下解密的方法. 按照现在的能力分解一个 400 位的整数需要上亿年的时间，因此当 p 和 q 是 200 位的素数时，就目前的水平而言，RSA 密码是安全的. 随着因子分解能力的提高，可能需要使用更大的素数.