← COMP5521 全部讲次
Q02

2025 Final 真题解析(上)|Q16-Q18 RSA、DH 与签名

COMP5521 2025 年期末卷 Part 3 前三题的非官方参考解答:RSA 陷门与 φ(n)、Diffie-Hellman、RSA 签名与 ElGamal 签名计算。

手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。

非官方参考解答,不是讲师给的标准答案;今年的考试安排与范围以讲师通知为准。 先自己在纸上做一遍,再展开对照。

范围与作答约定

题目来自 2025/26 学年第一学期的期末卷(闭卷、3 小时、共 24 题)和期末复习讲义里的题面截图。卷面结构:Q1–10 判断题共 10 分,Q11–15 选择题共 10 分,Part 3 简答与计算题 Q16–24 共 80 分。Q1–15 卷面未提供,扫描件略去了那两页,这里不补也不猜。

Part 3 分三页:本页 Q16–18(数论、RSA、DH、签名),中篇 Q19–21(ECDSA、比特币共识、三明治攻击),下篇 Q22–24(gas、比特币交易截图、稳定币)。卷面结构和讲师点名的要点见期末复习(上)。

计算题都用 python 独立验算过。题面用中文转述,关键术语保留英文;解析里的「回讲义」指向对应讲次的笔记页。

题目与解析

Q16 · RSA and number-theoretic foundations

7 分,两问。

  1. 给出 trap-door one-way function 的定义,并简要说明 RSA 里的「trap-door」从哪里来。(3 分)
  2. RSA 中 n = pq,写出 φ(n) 的表达式,并解释为什么求私钥 d 需要 gcd(e, φ(n)) = 1。(4 分)
Q16 · 查看答案与解析

参考解答,非官方答案。

(1) 陷门单向函数是一族可逆函数 f_k,满足三条:

  • 知道 k 和 X,算 Y = f_k(X) 容易;
  • 知道 k 和 Y,算 X = f_k⁻¹(Y) 容易;
  • 只知道 Y、不知道 k,求 X 计算上不可行。

RSA 的正向函数是 C = M^e mod n,用公钥谁都能算;逆向 M = C^d mod n 要私钥 d。陷门就是 d,它来自 n 的分解 p、q:有了 p、q 就能算 φ(n),再用扩展欧几里得求出 d。不知道分解,就卡在第一步,这就是 Factoring Problem。答题时 d 和 p、q 两样都写上,二者等价。

(2) φ(n) = (p − 1)(q − 1)。

d 是 e 在模 φ(n) 下的逆元,要满足 ed ≡ 1 (mod φ(n))。模逆存在的充要条件是 gcd(e, φ(n)) = 1。反过来看:如果 gcd = g > 1,ed − tφ(n) 永远是 g 的倍数,不可能等于 1,d 根本不存在。

有了 ed = 1 + tφ(n),欧拉定理给出 M^(ed) ≡ M (mod n),解密才能还原明文。顺带一句:φ(n) 总是偶数,所以 e 不能取偶数。

回讲义:公钥密码原理与陷门函数(L03 p.42–44)· RSA(L03 p.18–20)· 模逆(L02 p.22)· 费马与欧拉(L02 p.35、p.37)

Q17 · Diffie–Hellman key exchange

7 分。Alice 和 Bob 约定素数 p = 23、原根 g = 5。

  1. Alice 选 a = 6,Bob 选 b = 15,计算 A = g^a mod p 和 B = g^b mod p。(3 分)
  2. 写出双方各自怎样算出共享密钥 K,并给出 K 的值。(4 分)
Q17 · 查看答案与解析

参考解答,非官方答案。

先备好几个幂(mod 23):5² = 25 ≡ 2,5⁴ ≡ 4,5⁸ ≡ 16。

(1)

  • A = 5⁶ = 5⁴ · 5² ≡ 4 · 2 = 8
  • B = 5¹⁵ = 5⁸ · 5⁴ · 5² · 5 ≡ 16 · 4 · 2 · 5 = 640 ≡ 19(640 − 621 = 19)

(2)

  • Alice 收到 B,算 K = B^a mod p = 19⁶ mod 23。19 ≡ −4,(−4)⁶ = 4096,4096 − 4094 = 2,所以 K = 2。
  • Bob 收到 A,算 K = A^b mod p = 8¹⁵ mod 23 = 2⁴⁵ mod 23。2¹¹ = 2048 ≡ 1,所以 2⁴⁵ = (2¹¹)⁴ · 2 ≡ 2,K = 2。
  • 两边相等,因为 B^a = g^(ab) = A^b。窃听者只看到 p、g、A、B,要从 A 求 a 就得解离散对数。

验算:python 得 A = 8、B = 19、两边 K 都是 2;5 模 23 的阶为 22,确实是原根。

回讲义:Diffie-Hellman(L03 p.27–29;p.32 Exercise-3 用的是同一组 p 和 g)

Q18 · Digital signatures (RSA and ElGamal)

10 分。RSA 签名的流程:签名者用私钥对 H(M)「解密」得到 S,验证者用公钥对 S「加密」,再和 H(M) 比较。

  1. 解释数字签名怎样提供 authentication 和 non-repudiation。(2 分)
  2. 接收方拿到的是被改过的 M′,用它算 H(M′),而 S 是对 M 算的。解释验证为什么失败,这体现哪项安全属性。(2 分)
  3. ElGamal 签名:p = 23,g = 5,私钥 x = 3,公钥 y = g^x mod p,H(M) = 10(作为模 p − 1 的整数),k = 7 且 gcd(k, p − 1) = 1。
    • (a) 计算 r = g^k mod p。(3 分)
    • (b) 计算 k⁻¹ mod (p − 1),再算 s ≡ k⁻¹(H(M) − x·r) mod (p − 1),给出签名 (r, s)。(3 分)
Q18 · 查看答案与解析

参考解答,非官方答案。

(1) Authentication:S = H(M)^d mod n 只有持有私钥 d 的人造得出来,任何人用公开的 (e, n) 算 S^e mod n,等于 H(M) 就说明消息出自这把私钥的主人。Non-repudiation:私钥只在签名者手里,第三方也能独立验证,签名者事后无法否认签过。

(2) 验证者算出 S^e mod n = H(M)。M′ ≠ M 时,哈希的抗碰撞性让 H(M′) ≠ H(M),比较不相等,验证失败。这体现 integrity(完整性):签名之后消息哪怕改一个 bit 都会被发现。

(3) 先算公钥:y = 5³ mod 23 = 125 − 115 = 10。它和 H(M) = 10 数值碰巧相同,两者无关,后面别混用。

  • (a) r = 5⁷ = 5⁴ · 5² · 5 ≡ 4 · 2 · 5 = 40 ≡ 17(mod 23)
  • (b) 模数是 p − 1 = 22。
    • k⁻¹ = 7⁻¹ mod 22 = 19,因为 7 × 19 = 133 = 6 × 22 + 1。
    • H(M) − x·r = 10 − 3 × 17 = −41,−41 + 44 = 3。
    • s = 19 × 3 = 57 ≡ 13(mod 22)。
    • 签名 (r, s) = (17, 13)。
  • 自查验证式 g^H(M) ≡ y^r · r^s (mod p):左边 5¹⁰ mod 23 = 9,右边 10¹⁷ · 17¹³ mod 23 = 9,相等。

易错点:s 的运算模的是 p − 1,r 的运算模的是 p,两处别混。

回讲义:RSA 签名(L04 p.6–10)· 离散对数与 ElGamal(L04 p.21–23)

下一页 →
Q03 2025 Final 真题解析(中)|Q19-Q21 ECDSA、比特币共识与三明治攻击

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