← COMP5521 全部讲次
Lab5 · 第 7 周

Lab5 把密码原语跑一遍:哈希、AES、RSA、ECDSA、PoW 与 Merkle 树

补全课件六段 Python 示例代码并逐个实测,讲清每段在算什么、输出该长什么样,以及照抄课件会踩的两个坑。

一句话版

这节 lab 把四类密码原语各写成十几行 Python 跑一遍,再用哈希搭出比特币的两个零件。

先认识这几个词

词 全称 / 读法 一句人话
密码原语 cryptographic primitive 哈希、加密、签名这类最基础的密码积木
SHA-256 / MD5 Secure Hash Algorithm / Message Digest 5 两种哈希算法,输出长度不同
AES Advanced Encryption Standard,高级加密标准 加密和解密用同一把钥匙的算法
RSA 三位发明者姓氏首字母 公钥加密、私钥解密的算法
ECDSA Elliptic Curve Digital Signature Algorithm,椭圆曲线数字签名算法 用私钥签名、公钥验证的算法
PoW Proof of Work,工作量证明 靠反复试数字直到哈希够小,证明自己花了算力
nonce number used once,一次性数字 挖矿时不断换着试的那个数
Merkle 树 读「默克尔树」 把一堆数据两两哈希、层层合并成一个根的树

题目地图

每类原语在课件里都是一页概念、一页代码。代码只印了片段,下面把六段补成完整程序。实测环境是 Python 3.15 + cryptography 50.0.2,输出照实贴出。第 11 周的 Lab Test 开卷,这六段代码是最可能被要求改写的素材。

段落 跑什么 主要失分点
准备 装 cryptography,clone 课程仓库 以为 hashlib 也要装
哈希 MD5、SHA-1、SHA-256 照抄得到的 “SHA-1” 是 SHA-224
AES AES-256-OFB 加解密 解密时换了 IV
RSA RSA-2048 + OAEP 公钥私钥方向弄反
ECDSA 签名、验证、篡改 把返回值 0 当失败
PoW 改难度找 nonce 说不清 target 和前导 0 的关系
Merkle 树 补齐叶子、算根 照抄报 SyntaxError
课后题 八道问答 证明路径漏了拼接顺序

概念卡

1. 哈希函数

人话定义:它解决「怎么用一小串字符代表一大块数据」。哈希把任意长度的数据压成固定长度的「指纹」。同样输入永远同样输出,从指纹倒推不回原文,也找不到两份数据撞出同一个指纹。

例子:‘We are PolyU, Together We Excel!’ 的 SHA-256 是 64 个十六进制字符。只把最后的 ! 改成 ?,256 位里有 125 位翻转,接近一半。比特币用 SHA-256,以太坊用 Keccak。Lab3、Lab4 里 HTLC 用的 keccak256 就属于后者。

常见误解

以为 Python 的 hashlib.sha3_256 就是 Solidity 的 keccak256 → 两者填充规则不同,同一输入结果不一样(补充)。

回讲义:L09a 比特币交易长什么样:钱住在输出里,输入只是指针

2. 对称加密与非对称加密

人话定义:它解决「怎么让只有对方读得懂」。对称加密两边用同一把钥匙,快,但钥匙得事先安全地交给对方。非对称加密有一对钥匙:公钥公开,用来加密;私钥自己留着,用来解密。

例子:对称加密的示意图里,Alice 和 Bob 握着同一把 AES key。非对称加密的图里,Alice 用 Bob 的公钥加密,只有 Bob 的私钥能解。RSA 的安全性靠的是两个大素数的乘积很难分解。

常见误解

以为用 RSA 加密大文件更安全 → RSA-2048 配 OAEP-SHA256 一次最多加密 190 字节。实际做法是用 RSA 加密一把 AES 密钥,再用 AES 加密数据(课后第 6 题)。

回讲义:L03b-2 公钥体系:三种用法、三易两难与分解难题

3. 数字签名

人话定义:它解决「怎么证明消息是我发的、没被改过」。签名者用自己的私钥给消息盖章,任何人用签名者的公钥都能核对,消息改了一个字节就核对不上。

例子:示例的 ECDSA 用 SECP384R1 曲线签名。实测把消息里的 PolyU 改成 PolyX,验证失败;换另一把公钥去验,也失败。同一消息签两次,签名也不同,因为每次用新的随机数。

常见误解

以为签过名的消息就保密了 → 课件原话是 ECDSA 不加密数据,也不阻止别人看到数据,它只保证数据没被篡改。

回讲义:L08b-2 ECDSA:比特币怎样用椭圆曲线签名

4. 工作量证明的目标值

人话定义:它解决「怎么让出块必须花真算力」。把区块头和一个 nonce 拼起来算哈希,从 0 开始一个个试,直到哈希值小于目标值 2²⁵⁶⁻ᵇⁱᵗˢ。意思是:哈希写成二进制后,开头至少有 bits 个 0。

例子:每多要求一个 0,成功概率减半,平均尝试次数翻倍。实测每种难度重复 300 次取平均:4 位 14.7 次(理论 16),8 位 267.4 次(256),12 位 4035.4 次(4096)。验证者只要算一次哈希比大小,所以难解易验。

常见误解

以为前导 0 数的是十六进制字符 → 课件的例子数的都是二进制位,十六进制一个 0 等于四个二进制 0。

回讲义:L01d 加密货币:电子支付的四条弱点,比特币、以太坊和稳定币

逐题拆解

准备。hashlib 是 Python 标准库,只需装 cryptography:

python3 -m venv venv
source venv/bin/activate
python3 -m pip install cryptography
git clone https://github.com/AnthonyXuan/Lab5-Comp5521-2026

仓库 primitives/ 和 applications/ 下的六个文件对应课件六段代码。

哈希。三段写法相同:新建对象、update 消息、hexdigest 取十六进制。代码不缺 import,实测输出与课件截图一致:

MD5 hash: 		9694368f2a1aa0ca0e12bb8baa91e378
SHA-1 hash: 	36ee0f61695065ace8b902e2509cc54603275f2512b0c974ad8fd186
SHA-256 hash: 	badfaf8bfbe698a8744c5c1357c84da707e6ba41cb50f2e0e3b933fa5fdf9b1e

数一下第二行:56 个字符,乘 4 得 224 位,所以它是 SHA-224(见「课件里的坑」)。

AES。代码原样可跑。key 用 os.urandom(32) 生成,是 AES-256。每次加密再随机生成 16 字节 IV(初始向量,让同一明文每次加密结果不同)。实测密文 64 个十六进制字符,正好 32 字节,与明文等长,因为 OFB 模式不需要填充。同一 key 加密两次密文不同。换错 key 或 IV 解密得到乱码,程序不报错。新版 cryptography 会打两行 OFB 已迁移的警告,不影响结果。

RSA。课件没印 import,补这三行:

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.backends import default_backend as crypto_default_backend

实测密文 512 个十六进制字符,即 256 字节,每次运行都不同,最后一行解回原句。把明文换成 191 字节会报 ValueError: Encryption failed,190 字节以内正常。

ECDSA。原样可跑。验证函数在异常时返回 1、成功时返回 0,main 再把 0 翻成 “true”。实测签名以 30 开头,长度在 102 到 104 字节之间变化。这是 DER 编码(一种标准打包格式)给 r、s 补前导 00 的结果,不代表出错。

PoW。补上 import 和入口,难度从命令行传入:

import hashlib, time, random   # 课件未印
# ……中间与课件相同……
if __name__ == '__main__':
    import sys
    main(int(sys.argv[1]) if len(sys.argv) > 1 else 10)

运行 python3 pow.py 20,实测关键输出:

success with nonce 4704306
hash is:		 00000a84f061d485172236258dfd1f3d53a339f1f4e00c6446395279dae337cb
elapsed time:	 1.5196 seconds

20 位要求前 5 个十六进制字符为 0,结果正好满足。同一台机器上 10 位不到千分之一秒,24 位约 12.9 秒,耗时随难度指数增长。区块头带随机后缀,每次的 nonce 不同。

Merkle 树

照抄会报语法错误,先把 main 里那一行改成:

leaves = ['We', 'are', 'PolyU', 'Together', 'We', 'Excel']

再补 import hashlib, math。6 个叶子会被补两个空串凑成 8 个,三层共算 7 次父节点哈希。实测最后两行:

['We', 'are', 'PolyU', 'Together', 'We', 'Excel', '', '']
merkle root: ed0afab99bbafd5d8c63dc10842b389a47cd8058909b0e429dbf6abbd89e9610

课程仓库版跑出同一个根。

一步一步看

目标:把 6 个叶子补齐到 8 个再逐层哈希,看出 Merkle 根怎样算出,一共要几次父节点哈希。

  1. 叶子是 6 个,不是 2 的幂。不超过 6 的最大 2 的幂 reduced_size = 4,补 2 × 4 − 6 = 2 个空串,凑成 8 个。

    Merkle 第 1 帧:最底一排八个叶子 We、are、PolyU、Together、We、Excel 和两个空串,补上的两个空串青绿标出,上面三层都还是虚线

  2. 每个叶子先算 SHA-256。相邻两个叶子的十六进制哈希串拼起来,作为父节点的值再哈希一次,得到 4 个父节点。

    Merkle 第 2 帧:八个叶子两两连线,第一层四个父节点青绿标出,各由一对叶子的哈希拼接后再哈希得到

  3. 4 个父节点再两两合并,得到 2 个。

    Merkle 第 3 帧:第二层左半和右半两个节点青绿标出,各由两个第一层父节点合并而来

  4. 最后 2 个合成根 ed0afab9…。三层共算 4 + 2 + 1 = 7 次父节点哈希。

    Merkle 第 4 帧:根节点青绿标出,值以 ed0afab9 开头,三层一共做了 7 次父节点哈希

课后题

第 1 至 3 题直接对应上面的概念卡 2、3。第 1 题:非对称加密不需要事先共享秘密钥匙,公钥可以公开分发,解决了密钥分发问题,还能做数字签名。第 2 题:签名用签名者的私钥,验证用签名者的公钥。第 3 题:签名绑定了消息的哈希,消息改一个字节,用原签名验证就失败;不知道私钥,也造不出改过的消息的新签名。第 4 题证明 L4,给出的是 Hash 1-0 和 Hash 0。先算 H(L4) 得 Hash 1-1,和 Hash 1-0 拼接再哈希得 Hash 1。再和 Hash 0 拼接哈希,与给定根比较。实测兄弟左右顺序弄反就对不上。第 5 题 MD5、SHA-1 不再推荐,是因为已有实际碰撞。原像抵抗是给定哈希找不到原文,碰撞抵抗是找不到任意两条撞车的消息,后者要求更强。第 6 题:RSA 慢,单次能加密的长度也受限,上面实测 190 字节就是上限;AES 快且长度不限。混合加密用 RSA 加密一把随机生成的 AES 密钥,再用这把 AES 密钥加密数据,钥匙交换交给公钥,数据加密交给对称。第 7 题:ECC 用更短的密钥达到和 RSA 相当的安全级别,签名和公钥更短,节省链上存储和带宽;secp256k1 是比特币用的曲线,以太坊也用它。第 8 题见概念卡 4:矿工从 0 开始逐个试 nonce,直到区块头哈希小于目标值;难解是因为只能穷举,易验是因为验证者只算一次哈希。最后一张图把区块头四个字段拼起来做两次 SHA-256。

一步一步看

目标:用两个兄弟哈希从 L4 一路算回根,看结果和 Top Hash 对不对得上,从而证明 L4 在树里。

第 4 题的树有四个叶子 L1 到 L4,要证明的是 L4。

  1. 手里有 L4,课件给出两个兄弟哈希 Hash 1-0 和 Hash 0,再加上已知的根 Top Hash。

    证明第 1 帧:四层树,L4 青绿标出,Hash 1-0、Hash 0 和 Top Hash 是已知的近黑框,其余节点是虚线

  2. 算 H(L4),得到 Hash 1-1。

    证明第 2 帧:Hash 1-1 青绿标出,由 L4 哈希得到,旁边的 Hash 1-0 是给定的兄弟

  3. Hash 1-0 在左、Hash 1-1 在右,拼接后哈希得 Hash 1,即 H(Hash 1-0 ‖ Hash 1-1),‖ 表示前后拼接。

    证明第 3 帧:Hash 1 青绿标出,由 Hash 1-0 和 Hash 1-1 按左右顺序拼接后哈希得到

  4. Hash 0 在左、Hash 1 在右,再哈希一次,和 Top Hash 比较,相等就证明 L4 在树里。

    证明第 4 帧:Top Hash 青绿标出,由 Hash 0 和 Hash 1 拼接哈希后与给定根比较,相等即证明成功

课件里的坑

  • [课件有误] p.7:变量名和打印标签都写 SHA-1,调用的却是 hashlib.sha224(),输出 56 个字符。真 SHA-1 是 40 个字符,改成 hashlib.sha1() 实测得 a3222314e71bdfceb3546d1d832ae30c63d841a2。课程仓库也是同样写法。
  • [课件有误] p.19:‘Excel’ 前面印成了中文左弯引号,Python 报 SyntaxError: invalid character;‘Together’ 也少了一个 r。
  • [读图提醒] p.17:截图里的 nonce 510、标签 “hash in hex is:” 来自课程仓库版,那一版区块头固定、难度 10 位,所以每次都是 510;课件印的代码区块头带随机数,每次不同。参数名 differentyBits 是拼写错误,不影响运行。
  • [读图提醒] p.13:verify 返回 0 才是验证通过,改题时别把判断写反;仓库版改成返回字符串。
  • [读图提醒] p.22:图里是双重 SHA-256,p.17 代码只做一次,属于教学简化。Hash Output 那串是比特币创世区块的哈希(补充,已按真实区块头实测复现),图里前一块哈希 000000…a7b2 只是示意。

课后 10 分钟:考点复习

这 10 分钟怎么用:先默写必背,再不看代码做完整例题,最后做变式题,答完回到上面逐题拆解对答案。

必背

  1. 哈希把任意长度映射成固定长度,确定、不可逆、抗碰撞;比特币用 SHA-256,以太坊用 Keccak。
  2. 输出长度:MD5 128 位、SHA-1 160 位、SHA-256 256 位;课件 p.7 标成 SHA-1 的那一行实际调用 sha224。
  3. AES 加解密用同一把钥匙;示例是 AES-256-OFB,32 字节 key、16 字节随机 IV,解密要用同一个 IV。
  4. RSA 用接收方公钥加密、接收方私钥解密;RSA-2048 配 OAEP-SHA256,密文 256 字节,明文最多 190 字节。
  5. 签名用签名者私钥、验证用签名者公钥;签名保证数据没被篡改,不负责保密。
  6. PoW 成功条件是 hash < 2²⁵⁶⁻ᵇⁱᵗˢ,即二进制开头至少 bits 个 0,平均尝试 2ᵇⁱᵗˢ 次。
  7. Merkle 树证明一个叶子只需每层一个兄弟哈希,共 O(log n) 个;p.21 证明 L4 需要 Hash 1-0 和 Hash 0。

完整例题

课件 p.17 截图里,难度 10 位,找到的 nonce 是 510,哈希是 00001cd9711489af…。问:(1) target 是多少,平均要试几次?(2) 这一次实际试了几次?(3) 这个哈希开头有几个二进制 0?它能满足 16 位难度吗?20 位呢?

  1. target = 2²⁴⁶,平均 2¹⁰ = 1024 次。
  2. nonce 从 0 开始,510 成功,共试了 511 次,比平均少,属于运气好。
  3. 前 4 个十六进制 0 是 16 个二进制 0;下一个字符 1 写成二进制是 0001,再贡献 3 个 0,共 19 个。满足 16 位,不满足 20 位。

变式题(先自己做)

把 p.19 的叶子换成 [‘We’, ‘are’, ‘PolyU’, ‘Together’, ‘Excel’] 五个。(1) padding 之后有几个叶子,补了几个空串?(2) 要向只知道根哈希的人证明 ‘are’ 在树里,需要提供哪几个哈希?(3) 如果有人把 ‘are’ 改成 ‘Are’,验证在哪一步失败?

提示

先找不超过 5 的最大的 2 的幂,再按 2 × reduced_size − size 算补几个;证明路径是每层一个兄弟。

判分点与答案

(1) reduced_size = 4,补 2 × 4 − 5 = 3 个空串,共 8 个叶子。(2) 三个:‘We’ 的叶子哈希(在左)、PolyU 与 Together 合成的父哈希(在右)、右半棵树的根(在右),并注明左右顺序。(3) 第一步 H(‘Are’) 就和原叶子哈希不同,之后每层结果都变,最后与根比较时不相等。

闪卡自测

1. 怎样一眼看出 p.7 那一行不是 SHA-1?

数长度:56 个十六进制字符是 224 位,SHA-1 只有 40 个。

2. AES 示例为什么同一明文每次密文不同?

每次加密都随机生成新的 16 字节 IV;解密必须拿到同一个 IV。

3. Alice 给 Bob 发加密消息并签名,各用哪把钥匙?

加密用 Bob 的公钥,签名用 Alice 的私钥;Bob 用自己的私钥解密,用 Alice 的公钥验签。

4. 为什么 PoW 难解易验?

哈希不可逆,只能逐个试 nonce;验证者拿到 nonce 只需算一次哈希和 target 比大小。

下一步

先把六段代码各改一处再跑:hash 改成真 sha1,AES 用错 IV 解密,RSA 加密 191 字节,ECDSA 改消息后验证,PoW 跑 16、20、24 位,Merkle 写出 p.21 第 4 题的证明函数。下周讲群与椭圆曲线(L07a 群:一个集合配一种运算,守四条规矩,L08b 椭圆曲线密码:单向的 kP、倍加法、secp256k1 和 ECDH),Lab 6 是 Bitcoin(Lab6 笔记),p.12 的「ECC 密钥更短」和 p.22 的区块头会在那里接上。六段完整代码建议存好,第 11 周开卷 Lab Test 可以带进场。

下一讲 →
L07a L07a 群:一个集合配一种运算,守四条规矩

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