期末复习(下)|必背、必会算与闪卡自测
按讲师期末复习讲义划的要点,逐讲列出必背结论和必会的计算,附提示与解答两层折叠的闪卡。非官方。
手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。
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 课程页。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。