← COMP5521 全部讲次
L03a-3 · 第 3 周

L03a-3 RSA:谁都能锁、只有你能开

从公钥思想讲起,一步步走完 RSA 的密钥生成、用扩展欧几里得求 d、用平方-乘手算大次幂,再讲长消息为什么要分块。

一句话版

RSA 给每个人造一对钥匙:公钥谁都能拿,用来加密;私钥只有主人有,用来解密。想给你发密信的人不用先跟你见面,拿你的公钥一锁就行。

对称加密和一次一密都卡在「钥匙怎么送」,见上一页 L03a-2。这一页用上一讲的模运算、模逆和欧拉函数 φ(n),从零搭出 RSA。

先认识这几个词

词 全称 / 读法 一句人话
公钥 / 私钥 public key / private key 一对钥匙:公钥谁都能拿,私钥只有主人有
φ(n) 欧拉函数,读「fai n」 1 到 n 里和 n 互素的数有几个;n = pq 时等于 (p−1)(q−1)
互素 coprime 两个数的最大公约数是 1
模逆 e⁻¹ modular inverse 和 e 相乘后模 φ(n) 余 1 的那个数
扩展欧几里得 extended Euclidean algorithm 辗转相除再倒推回去,求出模逆
平方-乘 square-and-multiply 反复平方、挑几项相乘,手算大次幂的办法

一个类比:把打开的挂锁发给所有人

对称加密是一把挂锁配两把一样的钥匙,钥匙得先当面交给对方。

公钥密码换了个做法。你买一大批同款挂锁,全部打开,挂在门口任人取用,钥匙只有一把,留在你自己兜里。想给你寄东西的人,取一把锁「咔哒」扣上箱子寄出来。路上谁截到都打不开,扣锁的人自己也打不开,只有你能开。

门口挂着的那排开着的锁,课件叫公钥环(public-key ring)。

送钥匙这一步没了:锁可以公开送,钥匙从来不用离开你。

类比在哪里失效:

  • 你取到的那把锁,真的是收件人挂出来的吗?挂锁不管这件事,现实里要另外核实公钥属于谁。
  • 锁难撬只是安全的一个依据。数字取得太小、编码方式不当、私钥泄漏,照样失守。

从零讲起

1. 公钥思想:加密和解密用不同的钥匙

它解决什么问题

对称加密要求收发双方先共享同一把钥匙,这一步只能靠安全通道,又慢又贵。人一多更麻烦:一百个人两两通信,要准备几千把钥匙。公钥密码要做到:从没见过面的两个人,也能马上开始保密通信。

直觉

把一把钥匙拆成两半:一半只能锁,一半只能开。能锁的那一半公开出去,谁拿到都没关系,因为它开不了锁。能开的那一半自己留着。

关键要求是:从能锁的那一半,推不出能开的那一半。

一步一步看

目标:跟着 Alice 和 Bob 走一次公钥加密,看出 Bob 不用事先见过 Alice,没有私钥的人拿到密文也解不开。

  1. Alice 生成一对钥匙:公钥 {e, n} 挂出去,私钥 {d, n} 自己留着。

  2. Bob 想给 Alice 发消息 M,取 Alice 的公钥,算出密文 C = Mᵉ mod n。Bob 不用事先见过 Alice。

  3. 密文 C 走公开线路,谁都看得到,但没有 d 解不开。

  4. Alice 用自己的私钥算 M = Cᵈ mod n,拿回原文。

    公钥思想四步:一,Alice 生成一对钥匙,公钥 {e, n} 挂出去,私钥 {d, n} 自己留着;二,Bob 取 Alice 的公钥算 C 等于 M 的 e 次方 mod n,不用先和 Alice 见面;三,密文走公开线路,谁都看得到 C,没有 d 解不开;四,用青绿色标出,Alice 用私钥算 M 等于 C 的 d 次方 mod n,只有她做得到。底部注明对称加密要先走安全通道送 K,这里公钥可以走明线

怎么判断

拿到一种加密方案,问两句:

  1. 加密和解密用的是不是同一把钥匙?是,就是对称;不是,就是公钥(非对称)。
  2. 用来加密的那把钥匙能不能公开?公钥方案里能,而且必须做到「知道公钥也推不出私钥」。

意思是:公钥密码的安全,全压在「从公钥推私钥很难」这一条上。RSA 靠的是大数难分解,后面一页会细讲。

常见误解

以为公钥密码可以完全取代对称加密

公钥运算比对称加密慢得多。实际系统里常常用公钥加密一把对称密钥,正文仍然交给对称算法。两者是搭配用的。

以为用别人的公钥加密完,自己还能解开看看

解不开。加密用的是收件人的公钥,能解的只有收件人的私钥。发出去之后,发件人自己手里也没有能打开的钥匙。

试一下

Carol 想给 Dave 发密信。她该用谁的哪把钥匙加密?Dave 用什么解密?

Carol 用 Dave 的公钥加密,Dave 用自己的私钥解密。Carol 自己的钥匙在这件事里用不上。

2. RSA 密钥生成:六步造出一对钥匙

它解决什么问题

公钥思想只说了「要有这样一对钥匙」。RSA 给出具体造法:用两个素数造出 n,再造出一对互为模逆的 e 和 d,让 e 能公开、d 推不出来。

从哪来(补充)

RSA 由 Ron Rivest、Adi Shamir、Leonard Adleman 三人 1977 年在 MIT 公开发表,名字取三人姓氏首字母。英国情报机构 GCHQ 的 Clifford Cocks 在 1973 年已经想出等价方案,但属于机密,1997 年才公开。

出处:Wikipedia: RSA (cryptosystem)

直觉

两个素数相乘很容易,把乘积拆回两个素数很难。RSA 把 n = pq 公开,p 和 q 藏起来。

d 要靠 φ(n) 才能算出来,而 φ(n) 要靠 p、q 才能算出来。别人只有 n,卡在第一步。

一步一步看

目标:用 p = 17、q = 11 走完六步,看出公钥和私钥各由哪些量算出,哪些中间量必须藏好。

  1. 选两个不同的素数:p = 17,q = 11。

  2. 算 n = p × q = 17 × 11 = 187。n 会公开。

  3. 算 φ(n) = (p − 1)(q − 1) = 16 × 10 = 160。

  4. 选 e,要求 1 < e < φ(n) 且和 φ(n) 互素:取 e = 7,gcd(7, 160) = 1。

  5. 求 d = e⁻¹ mod φ(n),也就是满足 7 × d ≡ 1 (mod 160) 的 d。用扩展欧几里得:先正向辗转相除,160 = 22 × 7 + 6,7 = 1 × 6 + 1,余数到 1 停;再回代,1 = 7 − 6 = 7 − (160 − 22 × 7) = 23 × 7 − 160,所以 d = 23。

    扩展欧几里得求 d 的两栏:左栏正向,160 = 22 × 7 + 6,7 = 1 × 6 + 1,余数到 1 说明 gcd 是 1;右栏回代,1 = 7 − 6,代入 6 = 160 − 22 × 7,得到 1 = 23 × 7 − 160,最后一行用青绿色标出,读出 d = 23

  6. 发布公钥 {e, n} = {7, 187},私钥 {d, n} = {23, 187} 自己留着。p、q、φ(n) 用完销毁或藏好。

    RSA 密钥生成六步与 88 → 11 → 88 的一来一回:上排五个框依次是选素数 p = 17、q = 11,n = 187,φ(n) = 160,选 e = 7,求 d = 23;它们汇成两把钥匙,公钥 {7, 187} 谁都能拿,私钥 {23, 187} 只有我有;下排明文 88 用公钥算 88 的 7 次方 mod 187 得密文 11,再用私钥算 11 的 23 次方 mod 187 回到 88

怎么算

核心式子:e × d ≡ 1 (mod φ(n))。

意思是:e 乘 d 以后除以 φ(n),余数正好是 1。d 是 e 在模 φ(n) 下的「倒数」。

扩展欧几里得的回代结果总长这样:1 = s × e + t × φ(n)。模 φ(n) 之后 t × φ(n) 消失,剩下 s × e ≡ 1,s 就是 d。

s 是负数时要加 φ(n) 折回正数。例如 e = 5、φ(n) = 96:96 = 19 × 5 + 1,回代 1 = 96 − 19 × 5,s = −19,d = −19 + 96 = 77。验算 5 × 77 = 385 = 4 × 96 + 1。

常见误解

以为 n 是秘密

n 印在公钥上,人人可见。秘密是 d,以及任何能推出 d 的东西:p、q、φ(n)。

以为 e 随便选一个数就行

e 必须和 φ(n) 互素,否则模逆不存在,d 求不出来。比如 φ(n) = 160 时选 e = 5,gcd(5, 160) = 5,不合法。

试一下

p = 5、q = 11、e = 3,求 n、φ(n)、d。

n = 5 × 11 = 55,φ(n) = 4 × 10 = 40。40 = 13 × 3 + 1,回代 1 = 40 − 13 × 3,s = −13,d = −13 + 40 = 27。验算 3 × 27 = 81 = 2 × 40 + 1。

3. 加密、解密与平方-乘

它解决什么问题

钥匙造好了,接下来要真的算 C = Mᵉ mod n 和 M = Cᵈ mod n。指数稍大一点,比如 88 的 7 次方,直接展开就是一个 14 位数;真实系统里指数有几百位,根本没法展开。需要一种每一步都不让数变大的算法。

从哪来(补充)

这类算法叫模幂(modular exponentiation)。标准做法是把指数写成二进制,反复平方、遇到 1 就乘进结果,每一步都取模,乘法次数只和指数的位数同量级。Bruce Schneier 的《Applied Cryptography》里给过这段伪代码。

出处:Wikipedia: Modular exponentiation

直觉

想算 88⁷,不用乘 6 次。先平方:88²,再平方:88⁴。7 = 4 + 2 + 1,所以 88⁷ = 88⁴ × 88² × 88¹。

每算一步就 mod 187,所有中间数都压在 187 以内,手算也不会爆。

一步一步看

目标:用平方-乘把 88 加密成 11 再解回来,看出大指数怎样拆成几次平方和乘法,每步取模让数保持小。

  1. 目标:加密 M = 88,算 88⁷ mod 187。

  2. 反复平方,每步取模:88¹ = 88;88² = 7744,7744 mod 187 = 77;88⁴ = 77² = 5929,5929 mod 187 = 132。

  3. 把指数拆成 2 的幂相加:7 = 4 + 2 + 1。

  4. 挑出对应三项相乘,每乘一次就取模:132 × 77 = 10164,mod 187 = 66;66 × 88 = 5808,mod 187 = 11。

    平方-乘两步:第一步反复平方,88 的 1 次方是 88,88 的 2 次方是 7744 mod 187 = 77,88 的 4 次方是 77 的平方 5929 mod 187 = 132;第二步把 7 拆成 4 + 2 + 1,132 × 77 = 10164,mod 187 = 66,66 × 88 = 5808,最后一格用青绿色标出 mod 187 = 11;底部注明只做了 2 次平方、2 次乘法

  5. 密文 C = 11。

  6. 解密 11²³ mod 187:23 = 16 + 4 + 2 + 1。平方链 11² = 121,11⁴ = 121² mod 187 = 55,11⁸ = 55² mod 187 = 33,11¹⁶ = 33² mod 187 = 154。

  7. 相乘:154 × 55 mod 187 = 55,55 × 121 mod 187 = 110,110 × 11 mod 187 = 88。回到了明文。

怎么算

加密 C = Mᵉ mod n,解密 M = Cᵈ mod n。

意思是:明文自乘 e 次取余数得到密文;密文自乘 d 次取余数,又变回明文。

为什么一定回得来:Cᵈ = (Mᵉ)ᵈ = M^(ed),而 ed = kφ(n) + 1。M 和 n 互素时,欧拉定理给出 M^φ(n) ≡ 1,所以 M^(ed) = (M^φ(n))ᵏ × M ≡ M。M 和 n 不互素时,要分别在模 p、模 q 下证明,再用中国剩余定理(CRT)合并,结论照样成立。

手算还有一个省力技巧:平方链里一旦出现 ≡ 1,后面的幂都可以直接降下来。例如 43⁸ ≡ 1 (mod 119),那么 43⁷⁷ = 43^(9 × 8 + 5) ≡ 43⁵。

常见误解

以为解密正确性只能用欧拉定理证

欧拉定理要求 M 和 n 互素。标准例子里的 88 = 8 × 11,和 187 有公因子 11,并不互素,解密照样回到 88。完整证明要分别模 p、模 q,再用 CRT 合并。

以为最后一次取模就够了

每乘一次都要取模。等到最后才取模,中间数会变成几十位、几百位,手算算不下去,也容易出错。

试一下

n = 55、e = 7,加密 M = 6。

6² = 36,6⁴ = 36² = 1296,1296 mod 55 = 31。7 = 4 + 2 + 1,31 × 36 = 1116 mod 55 = 16,16 × 6 = 96 mod 55 = 41。C = 41。

4. 分块:长消息怎么加密

它解决什么问题

C = Mᵉ mod n 这条式子里,M 只是一个数。一封信很长,编成数字以后远远大于 n。直接整封代进去,取模之后信息就丢了。需要把消息切成一块一块,每块单独加密。

直觉

模 n 的余数只有 0 到 n − 1 这么多种。如果一块明文本身就 ≥ n,取模以后它和另一个较小的数落在同一个余数上,解密只能拿回那个较小的数,原文回不来。

所以规则只有一条:每一块的数值都要小于 n。

一步一步看

目标:把 “How are you?” 编成数字按四位分块,看出每块为什么要小于 n,各块怎样单独加解密。

  1. 明文 “How are you?” 按字符编成两位数字,连成一长串。

  2. 取 p = 73、q = 151,n = 73 × 151 = 11023。

  3. 四位数最大 9999,小于 11023,所以四位一组:3314、2262、0017、0462、2414、2066。

  4. 每块单独算 P¹¹ mod 11023:第一块 3314 加密成 10260,依次得到 10260、9489、1782、727、10032、2253。

    RSA 分块示意:明文 How are you 编成数字后四位一组,六块 3314、2262、0017、0462、2414、2066 各自用箭头指向下方的密文块 10260、9489、1782、727、10032、2253,第一块用青绿色标出;底部写 n = 73 × 151 = 11023,四位数最大 9999 比 n 小,每块都能原样解回来;块要是大于等于 n,取模后几个明文会落到同一个余数上

  5. 解密时每块单独算 C⁵⁸⁹¹ mod 11023,再拼回原文。

怎么判断

每块位数怎么定:找最大的 k,使 k 位数的最大值(k 个 9)仍小于 n。

意思是:n = 11023 时,四位数最大 9999 < 11023,可以;五位数最大 99999 > 11023,不行。所以四位一组。

常见误解

以为块越大越省事,块等于 n 也行

块必须严格小于 n。等于 n 的那块取模得 0,和明文 0 撞在一起,解不回来。

试一下

n = 187 时,明文按十进制分块,每块最多几位?

两位。两位数最大 99 < 187;三位数最大 999 > 187,三位块里像 500 这样的数会超过 n。

把它们串起来

公钥思想把一把钥匙拆成两半:能锁的那一半公开,能开的那一半自留。RSA 用数论把这个想法做实。

密钥生成里,上一讲的零件各归各位:n = pq 公开,φ(n) = (p−1)(q−1) 只有知道 p、q 才算得出,扩展欧几里得从 e 求出 d。别人只有 n 和 e,求 d 就要先分解 n。

加密和解密是同一种运算:模 n 下的大次幂。平方-乘让它在手算和计算机里都可行,每一步取模,数永远不会大过 n 的平方。

最后是工程上的约束:消息太长要分块,每块小于 n。

RSA 解决了送钥匙,但它慢。下一页看另一条路:两个人不寄任何钥匙,在公开线路上各自算出同一把,这就是 Diffie-Hellman。

课件里的坑

  • [课件已订正] p.20 密钥生成流程图取自 Stallings,原图把 d 那一行写成 “Public Key”,课件用红字改成了 Private → 记订正后的版本:{d, n} 是私钥(p.20)
  • [非互素的明文] p.21 的 88 和 187 有公因子 11,不能直接套欧拉定理证明解密正确,要分模 p、模 q 再用 CRT 合并(p.21)
  • [历史参数] p.17 说 n 典型长度 1024 bit,这是课件举例用的历史长度,不应用作新部署参数;参考 NIST SP 800-131A Rev.2(p.17)
  • [裸 RSA] 课件只展示教材 RSA 的算术,真实使用还需要规范的填充(如 OAEP)和足够长的参数(补充)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写密钥生成六步;再把例 8 的加密和解密用平方-乘重算一遍;最后做例 11,注意 43⁸ ≡ 1 那一下能省多少步。

必背

  1. RSA 密钥生成六步:选 p、q → n = pq → φ(n) = (p−1)(q−1) → 选 e 与 φ 互素 → d = e⁻¹ mod φ → 发布 {e, n};私钥是 {d, n},n 从来不是秘密
  2. 教材 RSA 用 C = Mᵉ mod n、M = Cᵈ mod n;互素时可用欧拉定理证明,一般情形用 CRT;手算用平方-乘法并逐步取模
  3. d 用扩展欧几里得求:正向辗转相除到余数 1,再回代成 1 = d·e − k·φ(n);系数为负要加 φ(n) 折回
  4. 标准例子 p = 17、q = 11、e = 7:n = 187,φ = 160,d = 23,88 加密得 11,11 解密回 88
  5. 分块加密时每块数值必须小于 n;p = 73、q = 151 时 n = 11023,所以四位一组

课件例题

例 8(课件 p.21):RSA 标准例子,加密 88 再解回来

题面:p = 17、q = 11、e = 7,明文 M = 88。求 n、φ(n)、d,算出密文并解密。

提示

d 用 7 × d = 160 + 1 去凑;加密时 7 = 4 + 2 + 1,解密时 23 = 16 + 4 + 2 + 1。

解答

n = 17 × 11 = 187,φ(n) = 16 × 10 = 160。d = 23,因为 7 × 23 = 161 = 160 + 1。

加密 88⁷ mod 187,用平方-乘:

88² = 7744 mod 187 = 77
88⁴ = 77² = 5929 mod 187 = 132
88⁷ = 132 × 77 × 88 → 10164 mod 187 = 66 → 66 × 88 = 5808 mod 187 = 11

解密 11²³ mod 187,23 = 16 + 4 + 2 + 1:

11² = 121,11⁴ = 55,11⁸ = 33,11¹⁶ = 154
154 × 55 = 8470 mod 187 = 55 → 55 × 121 = 6655 mod 187 = 110 → 110 × 11 = 1210 mod 187 = 88

密文 11,解回 88。

例 9(课件 p.22):用扩展欧几里得从 e 求 d

题面:e = 7、φ(n) = 160,求 d。

提示

先正向除到余数是 1,再从最后一行往回代。

解答
正向:160 = 22 × 7 + 6
        7 = 1 × 6 + 1      ← gcd = 1,e 合法
回代:  1 = 7 − 1 × 6
          = 7 − (160 − 22 × 7)
          = 23 × 7 − 1 × 160

所以 7 × 23 ≡ 1 (mod 160),d = 23,和例 8 一致。系数已经是正数,不用再折回。

例 10(课件 p.23):多块明文的 RSA 处理

题面:明文 “How are you?” 按字符编成两位数字,四位一组得 3314 2262 0017 0462 2414 2066。密钥取 p = 73、q = 151、e = 11。求 n、φ(n)、d,说明为什么四位一组。逐块加密后的密文是 10260 9489 1782 727 10032 2253。

提示

先算 n,再比一比四位数和五位数的最大值哪个小于 n。

解答

n = 73 × 151 = 11023,φ(n) = 72 × 150 = 10800。d = 5891,验算 11 × 5891 = 64801 = 6 × 10800 + 1。

每块数值必须小于 n,否则取模会丢信息。四位数最大 9999,小于 11023,所以按四位分块。每块独立算 P¹¹ mod 11023 得到上面六块密文,解密逐块算 C⁵⁸⁹¹ mod 11023。这页记住分块规则即可,字符编码表课件没给,不会要求复原。

例 11(课件 p.24–25):Exercise-2,求 d、加密、再解回来

题面:p = 7、q = 17、e = 5、M = 8。求 d 和密文 C,并从 C 还原 M。

提示

求 d 时系数会是负数,记得加 96。解密时盯住平方链,出现 1 就降指数。

解答

n = 119,φ(n) = 6 × 16 = 96。

求 d:96 = 19 × 5 + 1,所以 1 = 96 − 19 × 5,5⁻¹ ≡ −19 ≡ 77 (mod 96)。负数要加 96 折回。验算 5 × 77 = 385 = 4 × 96 + 1。

加密:8² = 64,8⁴ = 4096 mod 119 = 50,8⁵ = 50 × 8 = 400 mod 119 = 43,C = 43。

解密 43⁷⁷ mod 119:43² = 1849 mod 119 = 64,43⁴ = 50,43⁸ = 2500 mod 119 = 1。既然 43⁸ ≡ 1,77 = 9 × 8 + 5,就有 43⁷⁷ ≡ 43⁵ = 50 × 43 = 2150 mod 119 = 8。遇到某个幂 ≡ 1 立刻降指数,这是考场省时间的关键。

课堂批注(课件 p.25):Exercise-2 的解密换一条路,用 CRT 拆开算

课堂上讲师补充了另一种解法:解密方知道 119 = 7 × 17,可以把 43⁷⁷ mod 119 拆成模 7 和模 17 两个小问题,算完再合并。

提示

先把底数 43 分别对 7、17 取余。模 17 时指数可以按 16 降,因为 17 是素数。最后找小于 119、同时满足两个余数的那个数。

解答

模 7:43 = 6 × 7 + 1,43 ≡ 1,所以 43⁷⁷ ≡ 1 (mod 7)。

模 17:43 = 2 × 17 + 9,43 ≡ 9。由费马小定理 9¹⁶ ≡ 1,77 = 4 × 16 + 13,所以 43⁷⁷ ≡ 9¹³ (mod 17)。平方链:9² = 81 ≡ 13,9⁴ = 169 ≡ 16 ≡ −1,9⁸ ≡ 1。9¹³ = 9⁸ × 9⁴ × 9 ≡ 1 × (−1) × 9 = −9 ≡ 8。

合并:要找 m ≡ 1 (mod 7)、m ≡ 8 (mod 17),且 0 ≤ m < 119。8 本身就满足,8 mod 7 = 1。由 CRT 这个数唯一,M = 8,和上面的平方链结果一致。

这条路的好处是每一步只碰两位数。只有手里有 p、q 的解密方才能这样拆。

例 12(课件 p.49):Exercise-4,p = 11、q = 5、e = 7、M = 6 的完整 RSA

见下方完整例题。

完整例题

题面(课件 p.49 Exercise-4):p = 11、q = 5、e = 7、M = 6。求密钥、密文,并把密文解回去。

约定:d 必须用扩展欧几里得求,并展示回代;幂运算用平方-乘,每步取模。

解法:

  1. n = 11 × 5 = 55,φ(n) = 10 × 4 = 40。
  2. 正向辗转相除:40 = 5 × 7 + 5,7 = 1 × 5 + 2,5 = 2 × 2 + 1。
  3. 回代:1 = 5 − 2 × 2 = 5 − 2 × (7 − 5) = 3 × 5 − 2 × 7 = 3 × (40 − 5 × 7) − 2 × 7 = 3 × 40 − 17 × 7。系数 −17,加 40 折回,d = 23。验算 7 × 23 = 161 = 4 × 40 + 1 ✓。
  4. 加密 C = 6⁷ mod 55:6² = 36,6⁴ = 1296 mod 55 = 31。7 = 4 + 2 + 1,31 × 36 = 1116 mod 55 = 16,16 × 6 = 96 mod 55 = 41。C = 41。
  5. 解密 41²³ mod 55,23 = 16 + 4 + 2 + 1:41² = 1681 mod 55 = 31,41⁴ = 31² = 961 mod 55 = 26,41⁸ = 26² = 676 mod 55 = 16,41¹⁶ = 16² = 256 mod 55 = 36。
  6. 相乘:36 × 26 = 936 mod 55 = 1;1 × 31 = 31;31 × 41 = 1271 mod 55 = 6 = M ✓。

要点:第 6 步 36 × 26 ≡ 1 是可以借力的地方,遇到 ≡ 1 立刻划掉。d 的回代一定要写出来,只写 d = 23 拿不到过程分。

答题格式:分四段写:n 与 φ(n);d 的正向与回代;加密的平方链和乘法;解密的平方链和乘法,最后一行写「= M ✓」。

变式题(先自己做)

(1) 改编自课件 p.49:p = 13、q = 7、e = 5、M = 9。求 n、φ(n)、d、密文 C,并把 C 解回 M。 (2) 改编自课件 p.22:e = 3、φ(n) = 20,用扩展欧几里得求 d。 (3) 改编自课件 p.23:p = 61、q = 53,明文按十进制分块,每块最多几位?

提示

(1) 算 9 的幂时注意 9⁴ mod 91 会回到一个很眼熟的数。(2) 20 = 6 × 3 + 2,3 = 1 × 2 + 1。(3) 先算 n,再比最大的 k 位数。

判分点与答案(非官方评分标准)

判分点:① (1) d 必须给出回代过程并验算 ed ≡ 1;② (1) 加解密要写平方-乘链;③ (3) 要写出 n 并比较两个边界。

(1) n = 91,φ(n) = 12 × 6 = 72。72 = 14 × 5 + 2,5 = 2 × 2 + 1,回代 1 = 5 − 2 × 2 = 5 − 2 × (72 − 14 × 5) = 29 × 5 − 2 × 72,d = 29,验算 5 × 29 = 145 = 2 × 72 + 1 ✓。加密:9² = 81,9⁴ = 81² = 6561 mod 91 = 9,9⁵ = 9 × 9 = 81 = C。解密 81²⁹:81² ≡ 9,81⁴ ≡ 81,81⁸ ≡ 9,81¹⁶ ≡ 81;29 = 16 + 8 + 4 + 1 → 81 × 9 × 81 × 81,其中 81 × 9 = 729 mod 91 = 1,剩下 81 × 81 = 6561 mod 91 = 9 = M ✓。

(2) 回代 1 = 3 − 2 = 3 − (20 − 6 × 3) = 7 × 3 − 20,d = 7。验算 3 × 7 = 21 = 20 + 1 ✓。

(3) n = 61 × 53 = 3233。三位数最大 999 < 3233,四位数最大 9999 > 3233,每块最多三位。

闪卡自测

1. 公钥密码相比对称加密,省掉了哪一步?

省掉了事先通过安全通道送钥匙。公钥可以公开发,私钥从不离开主人(p.16、p.34)。

2. RSA 密钥生成六步各是什么?哪些量是秘密?

选 p、q → n = pq → φ = (p−1)(q−1) → 选 e 与 φ 互素 → d = e⁻¹ mod φ → 发布 {e, n}。秘密是 d,以及能推出 d 的 p、q、φ;n 和 e 公开(p.19–20)。

3. e = 7、φ = 160 时 d 是多少?怎么来的?

23。160 = 22 × 7 + 6,7 = 6 + 1,回代 1 = 23 × 7 − 160(p.22)。

4. 为什么 Cᵈ mod n 一定回得到 M?

ed = kφ(n) + 1。互素时欧拉定理给 M^(ed) ≡ M;不互素时分模 p、模 q 证明再用 CRT 合并(补充)。

5. 平方-乘法怎么算 88⁷ mod 187?

88² ≡ 77,88⁴ ≡ 132;7 = 4 + 2 + 1;132 × 77 ≡ 66,66 × 88 ≡ 11(p.21)。

6. RSA 分块加密时每块有什么限制?

每块数值必须小于 n,否则取模后还原不回来。n = 11023 时四位一组(p.23)。

下一讲

RSA 靠「谁都能锁、只有我能开」解决送钥匙。下一页换一条路:Diffie-Hellman 让两个人在公开线路上各自算出同一把密钥,什么都不用寄,见 L03b。

下一讲 →
L03b L03b Diffie-Hellman:不寄钥匙,各自算出同一把

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。