← COMP5521 全部讲次
R03

期末复习(下)|必背、必会算与闪卡自测

按讲师期末复习讲义划的要点,逐讲列出必背结论和必会的计算,附提示与解答两层折叠的闪卡。非官方。

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

2026-11-18 · 期末复习下篇 · 必背清单与闪卡,范围和卷面结构见上篇

先说清楚

非官方整理。 清单按讲师期末复习讲义列的要点排,数字和例子取自各讲讲义页,闪卡里的数值都用 python 验算过。考试范围和形式以讲师通知为准;2025 年卷面结构见上篇,逐题解答见 2025 真题解析。

用法:先看「必背 / 必会算」,自己能复述出来再往下做闪卡。闪卡先只看题,卡住了点开「提示」,做完再点开「解答」对答案。

必背与必会算

必背:支付协议线(L1、L5、L6)

  • L1:电子支付的几类形式(网上银行、信用卡、智能卡、电子钱包、加密货币),能各举一个例子。
  • L5:SET 的双重签名把订单信息和支付信息分别哈希再拼接签名,商家只看订单、银行只看支付,两者仍能绑定在一起。
  • L5:购买六步的报文顺序是 PReq → AuthReq → AuthRes → PRes → CapReq → CapRes。
  • L5:证书注册(持卡人、商户)在复习讲义里标为 optional。
  • L6:3-D Secure 分三个域,五段 SSL 连接,支付走 12 步;CAVV 长 20 个八位组;付款人认证分四个阶段。

必背:密码学概念(L3、L4)

  • 陷门单向函数:正着算容易,反着算很难,掌握陷门后反算变容易。RSA 的陷门是私钥 d,算 d 要先知道 p、q。
  • 求 d 需要 gcd(e, φ(n)) 为 1,否则 e 在模 φ(n) 下没有逆元。
  • 数字签名提供三种性质:authentication、non-repudiation、integrity。签名用私钥签、公钥验,不负责保密。
  • Elgamal 和 DSA 的安全性依赖离散对数难题;Elgamal 的 s 要模 p − 1 算,随机数 k 必须和 p − 1 互素。
  • Chaum 盲签名:用户先用随机因子把消息盲化,签名者签完,用户再去盲,签名者始终看不到原消息。

必背:群与曲线(L7、L8)

  • 群的四条公理:封闭、结合、单位元、逆元。
  • 判断 a 是不是 Z_p* 的生成元:当 p 写成 2p₁ + 1(p₁ 为素数)时,只要 a 的平方和 a 的 p₁ 次方模 p 都不是 1,a 就是生成元。
  • 曲线非奇异的条件是判别式 4a³ + 27b² 不为 0。
  • 比特币用 secp256k1 曲线,签名算法是 ECDSA。

必背:区块链(L9、L10、L11)

  • L9:手续费等于输入总额减输出总额;TXID 是交易的双重 SHA-256;没被花掉的输出留在 UTXO 集合里;区块奖励已减半到 3.125 BTC。
  • L10:手续费按 Gas Used 乘 Gas Price 计;out of gas 时这笔交易的状态改动全部回滚,已经消耗的 gas 不退;交易是原子的。
  • L10:账户分外部账户(EOA)和合约账户;合约可以用 SELFDESTRUCT 自毁。
  • L11:稳定币分法币抵押、加密抵押、算法三类。法币型靠储备和赎回稳价,HKMA 要求 100% 储备,MiCA 要求 72 小时内赎回;加密抵押型靠超额抵押和清算,DAI 是代表;算法型靠供应调节,AMPL 用 rebase,UST/LUNA 用双币铸销,后者已经崩盘。

必会算

讲次 要会的计算 讲义页
L2 欧几里得求 GCD,扩展欧几里得求模逆,欧拉定理降幂,CRT 拆模数 L02c、L02d、L02e
L3 RSA 从 p、q 到 d 再到加解密;DH 的公开值与共享密钥 L03a-3、L03b
L4 RSA 签名与验证;Elgamal 签名 (r, s) 与验证 L04a、L04c
L7 用判定法找生成元,列子群 L07b
L8 点加与倍点;ECDSA 签名与验证 L08a、L08b-2
L9 从交易的输入输出算手续费,判断输出是否已花 L09b、L09d
L10 最高手续费、实际手续费、退款 L10b
L11 加密抵押的最多可铸量、抵押率、清算后剩余 L11

ECDSA 的公式要背熟。签名:r 取 kG 的横坐标再模 n,s = k⁻¹(H + d·r) mod n。验证:w = s⁻¹,u1 = H·w,u2 = r·w,算 u1G + u2Q,横坐标模 n 等于 r 就接受。

闪卡自测

数论(L2)

卡 1:求 911⁻¹ mod 999。

提示

对 999 和 911 做扩展欧几里得,把余数 1 倒推回去,写成 999 和 911 的线性组合。

解答

806。验算:911 × 806 除以 999 余 1。

卡 2:求 7¹³⁴ mod 26。

提示

7 和 26 互素,φ(26) = 12,指数先模 12。

解答

134 除以 12 余 2,所以等于 7² mod 26,49 − 26 = 23,答案 23。

卡 3:求 20³⁷ mod 77。

提示

77 = 7 × 11,分别模 7 和模 11 算,再用 CRT 合并。

解答

模 7:20 ≡ 6,37 模 6 余 1,结果 6。模 11:20 ≡ 9,37 模 10 余 7,9⁷ ≡ 4。找同时满足模 7 余 6、模 11 余 4 的数,得 48。

RSA 与 DH(L3)

卡 4:RSA 取 p = 17、q = 11、e = 7。求 n、φ(n)、d,并加密 M = 88。

提示

φ(n) = (p − 1)(q − 1);d 是 e 模 φ(n) 的逆元;C = Mᵉ mod n。

解答

n = 187,φ(n) = 160,d = 23(7 × 23 = 161,模 160 余 1),C = 88⁷ mod 187 = 11。解密 11²³ mod 187 回到 88。

卡 5:DH 取 p = 23、g = 5,双方私钥 a = 4、b = 3。求双方公开值和共享密钥。

提示

A = gᵃ mod p,B = gᵇ mod p,K = Bᵃ mod p,也等于 Aᵇ mod p。

解答

A = 5⁴ mod 23 = 4,B = 5³ mod 23 = 10,K = 10⁴ mod 23 = 18。用 4³ mod 23 验算,同样是 18。

卡 6:讲义里另一个 DH 例子用 p = 23、G = 9,这个参数有什么问题?

提示

数一数 9 的幂模 23 要多少次才回到 1。

解答

9 的阶是 11,达不到 22,所以 9 不是 23 的原根,它只能生成一个 11 个元素的子群,可选的共享密钥变少。DH 的生成元应当选原根。

卡 7:什么叫陷门单向函数?RSA 的陷门是什么?

提示

分「没有陷门」和「有陷门」两种情况说反算的难易。

解答

单向函数正算容易、反算困难;陷门单向函数在掌握某个秘密信息后反算变得容易。RSA 中这个秘密是私钥 d,它要从 p、q 算出,而从 n 分解出 p、q 是困难问题。

签名(L4)

卡 8:RSA 签名取 n = 3337、e = 1019、d = 79,对 M = 688 签名并验证。

提示

签名用私钥:S = Mᵈ mod n;验证用公钥:Sᵉ mod n 应回到 M。

解答

S = 688⁷⁹ mod 3337 = 1570;验证 1570¹⁰¹⁹ mod 3337 = 688,通过。

卡 9:Elgamal 取 p = 11、g = 2、私钥 x = 3、消息 X = 9、k = 7。求公钥 y 和签名 (r, s),并验证。

提示

y = gˣ mod p,r = gᵏ mod p,s = k⁻¹(X − xr) mod (p − 1);验证比较 gˣ 与 yʳrˢ,这里指数上的 X 是消息。

解答

y = 8,r = 7,k⁻¹ = 7⁻¹ mod 10 = 3,s = 3 × (9 − 21) mod 10 = −36 mod 10 = 4。验证:2⁹ mod 11 = 6,8⁷ × 7⁴ mod 11 = 6,两边相等,接受。负数取模是这题最容易错的地方。

卡 10:消息被改成 M′ 后再用原签名验证,为什么会失败?体现签名的哪种性质?

提示

签名绑定的是原消息(或它的哈希),验证时会重新拿收到的消息去比。

解答

公钥解出来的值对应原消息,和 M′ 对不上,验证失败。这体现完整性(integrity):内容只要被改动就能被发现。

群与曲线(L7、L8)

卡 11:找出 Z₁₁* 的全部生成元。

提示

11 = 2 × 5 + 1,只需检查 a² 和 a⁵ 模 11 是否为 1。

解答

2、6、7、8。其余元素要么平方为 1(只有 10),要么五次方为 1(3、4、5、9,它们和 1 一起组成子群 {1,3,4,5,9})。

卡 12:曲线 y² = x³ + x + 6 mod 11 上一共有多少个点?

提示

对 x 从 0 到 10 逐个算右边,看是不是模 11 的平方数;别忘了无穷远点。

解答

12 个有限点加上无穷远点,共 13 个。13 是素数,所以除无穷远点外任一点都是生成元,讲义用 α = (2,7),2α = (5,2)。

区块链(L9、L10、L11)

卡 13:一笔比特币交易有 1 个输入 5.34200381 BTC,2 个输出合计 5.34199517 BTC,手续费是多少?输入等于输出吗?

提示

手续费不单独作为一个输出出现。

解答

手续费 0.00000864 BTC。输入不等于输出,差额就是矿工拿走的手续费。

卡 14:Gas Limit 200,000,Gas Price 50 Gwei,实际用量 150,000。求最高手续费、实际手续费和退款(1 ETH 为 10⁹ Gwei)。

提示

最高按 Gas Limit 算,实际按实际用量算,退款是两者之差。

解答

最高 200,000 × 50 = 10⁷ Gwei = 0.01 ETH;实际 150,000 × 50 Gwei = 0.0075 ETH;退款 0.0025 ETH。

卡 15:交易执行到一半 out of gas,会发生什么?

提示

分两件事回答:状态改动怎么办,已用的 gas 怎么办。

解答

交易失败,它做过的状态改动全部回滚,等于没执行;已经消耗的 gas 照样付给矿工,不退。

卡 16:Alice 存 2 ETH,价格 $3,500,最低抵押率 150%,最多能铸多少 DAI?她铸了 4,000 DAI 后 ETH 跌到 $2,500,会怎样?

提示

最多可铸量 = 抵押价值 ÷ 最低抵押率;跌价后重算抵押率,低于 150% 就被清算,罚金 13%。

解答

最多约 4,666 DAI(7000 ÷ 1.5)。跌价后抵押价值 5000,抵押率 5000 ÷ 4000 = 125%,低于 150%,进入清算。罚金 4000 × 13% = 520,共需偿付 4,520,按 $2,500 折合 1.808 ETH,Alice 剩 0.192 ETH。

卡 17:比较三类稳定币的稳价方式和主要风险。

提示

每类答「靠什么维持 1 美元」和「什么情况下会脱锚」。

解答

法币抵押型(如 USDT)靠发行方持有的储备和一比一赎回,风险在发行方是否真有足额储备。加密抵押型(如 DAI)靠超额抵押和自动清算,风险在抵押资产急跌、清算来不及。算法型(如 AMPL、UST)靠调节供应量,没有足额抵押,信心一旦崩溃会陷入死亡螺旋,UST/LUNA 就是例子。

复习完一轮,回上篇对照 2025 卷面的分值分布,把计算大题对应的讲次再过一遍。

这组材料已读完,可以回课程页选择配套资料或练习:COMP5521 课程页。

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