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 不加密数据,也不阻止别人看到数据,它只保证数据没被篡改。
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 根怎样算出,一共要几次父节点哈希。
-
叶子是 6 个,不是 2 的幂。不超过 6 的最大 2 的幂 reduced_size = 4,补 2 × 4 − 6 = 2 个空串,凑成 8 个。
-
每个叶子先算 SHA-256。相邻两个叶子的十六进制哈希串拼起来,作为父节点的值再哈希一次,得到 4 个父节点。
-
4 个父节点再两两合并,得到 2 个。
-
最后 2 个合成根 ed0afab9…。三层共算 4 + 2 + 1 = 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。
-
手里有 L4,课件给出两个兄弟哈希 Hash 1-0 和 Hash 0,再加上已知的根 Top Hash。
-
算 H(L4),得到 Hash 1-1。
-
Hash 1-0 在左、Hash 1-1 在右,拼接后哈希得 Hash 1,即 H(Hash 1-0 ‖ Hash 1-1),‖ 表示前后拼接。
-
Hash 0 在左、Hash 1 在右,再哈希一次,和 Top Hash 比较,相等就证明 L4 在树里。
课件里的坑
- [课件有误] 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 分钟怎么用:先默写必背,再不看代码做完整例题,最后做变式题,答完回到上面逐题拆解对答案。
必背
- 哈希把任意长度映射成固定长度,确定、不可逆、抗碰撞;比特币用 SHA-256,以太坊用 Keccak。
- 输出长度:MD5 128 位、SHA-1 160 位、SHA-256 256 位;课件 p.7 标成 SHA-1 的那一行实际调用 sha224。
- AES 加解密用同一把钥匙;示例是 AES-256-OFB,32 字节 key、16 字节随机 IV,解密要用同一个 IV。
- RSA 用接收方公钥加密、接收方私钥解密;RSA-2048 配 OAEP-SHA256,密文 256 字节,明文最多 190 字节。
- 签名用签名者私钥、验证用签名者公钥;签名保证数据没被篡改,不负责保密。
- PoW 成功条件是 hash < 2²⁵⁶⁻ᵇⁱᵗˢ,即二进制开头至少 bits 个 0,平均尝试 2ᵇⁱᵗˢ 次。
- 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 位呢?
- target = 2²⁴⁶,平均 2¹⁰ = 1024 次。
- nonce 从 0 开始,510 成功,共试了 511 次,比平均少,属于运气好。
- 前 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 可以带进场。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。