C01 Crypto Foundation：一本给数据按指纹的册子

一句话版

哈希用可信摘要核对内容，签名再证明密钥授权；两者都不等于加密。

新手入口：先分清数据、摘要和密钥。学完应能解释：为何哈希对得上仍不足以证明来源。英文提示贴在概念旁；先理解，再用一句英文复述。

一个类比：档案室的指纹册

档案室给每份进来的材料按一枚指纹，指纹另册登记。按材料取指纹很快，拿着一枚指纹造不出材料，这就是单向性；两份不同材料按出同一枚指纹叫碰撞，而「指定这份材料，去造另一份指纹相同的」比「随便造两份指纹相同的」难得多，前者是弱抗碰撞要防的第二原像攻击，后者是强抗碰撞要防的碰撞攻击。

册子越用越像整讲的骨架。登记常用密码时，攻击者把常见词各按一次指纹，一次计算就能对着全册比对，于是给每人的指印先叠一层各不相同的随机编号（盐）。按顺序装订时，每页开头抄一遍上一页的指纹，改中间一页后面全对不上。册子太厚要抽查某页时，只需沿路几枚旁支指纹就能一层层算回封面那枚（Merkle 证明）。

类比在哪里失效：真指纹长在人身上天然唯一；哈希是算出来的，碰撞不是「不存在」而是「目前没人找得到」，MD5 和 SHA-1 就已经被找到了。更要紧的一处：指纹册只记录「材料和指纹对得上」，说明不了是谁把那份材料放进来的，攻击者可以把材料和指纹一起换掉——这个洞得靠签名补。册子本身也不保密，材料只有三种可能时，一枚指纹和明文没区别。

概念卡

1. 三条安全性质（One-Way / Weak / Strong Collision-Resistant）

人话定义：单向性是给定 h 难以找到 x 使 H(x) = h；第二原像是给定 x，难以找到不同的 y 使 H(y) = H(x)；抗碰撞是难以找到任意一对不同输入，使它们的哈希相等。「难以」指计算上不可行，不是数学上不存在。

英文注意｜preimage / second preimage / collision：先圈出题目的 given（给定）。给定摘要、给定消息、自由选两条消息，是三种任务。resistance 是名词，resistant 是形容词。 答题句：Second-preimage resistance makes it computationally infeasible to find a different message with the same hash as a given message.

例子：三条性质分别出现在 p.4、p.6、p.7 三页，只背 p.4 会漏掉中间那条。区分判据是课件原话——攻击者控制几个输入（p.7）：

常见误解

以为「强」说的是攻击强度 → 强和弱说的是性质的强度，恰恰相反：强性质防的是更容易的那种攻击。逻辑关系是强抗碰撞 ⇒ 弱抗碰撞，反过来不成立（p.7）。另外 MD5 和 SHA-1 被攻破的是碰撞，不是单向性，MD5 至今没有实用的原像攻击（p.9）。

2. 加盐（Password Salting）

人话定义：课件的定义是「盐是对原始数据的污染物，让相同的数据也能产出两个不同的哈希」，存的东西从 Hash(Password) 变成 Hash(Password + Salt)（p.22）。

英文注意｜salt / secret key：salt 是盐，不是秘密密钥。搭配是 salt a password、store the salt。 答题句：A salt need not be secret; it prevents attackers from reusing precomputed hashes across users with different salts.

例子：一次哈希计算能打击几个人，加盐前后完全不同（p.21、p.23）：

攻击 Bob 得换他的盐把整本字典重跑一遍，成本从「与用户数无关」变成「乘以用户数」。

常见误解

以为盐要保密、以为加盐让单个密码更难破 → 盐不是密钥，它和哈希一起明文存在同一张表里，脱库时一起被拿走；攻击者知道 Alice 的盐照样能对着她一个人跑字典。它改变的是规模经济：摧毁预计算的彩虹表，把批量攻击打回逐个攻击。要求只有两条，每用户唯一 + 足够随机（p.22、p.23）。

3. 哈希做不到的两件事

人话定义：哈希不提供机密性，也不提供来源真实性。

英文注意｜integrity / authenticity / confidentiality：分别问「是否被改」「来源是否可信」「别人能否读到」。不要把三者都翻成“安全”。 答题句：A matching hash supports an integrity check only when the reference digest is trusted.

例子：石头剪刀布先公布出招的哈希再揭晓，看起来能防偷看，但原像空间只有三个，对手把 rock / paper / scissors 各算一遍就知道你出了什么——课件原话是他根本不需要 undo 哈希函数（p.25）。修法是承诺时拼一个随机 nonce，原像空间从 3 变成 3 × 2²⁵⁶。来源那一条更朴素：任何人都能算哈希，攻击者把数据和哈希一起替换，验证照样通过（p.26）。

常见误解

以为「哈希对得上」就等于「这份东西是他发的」→ 必须先有可信的参照摘要；数据和摘要一起被替换，仍能对上（p.26）。低熵输入可被正向枚举，攻击者不必反转哈希；盐防跨用户复用猜测，秘密随机 nonce 防出招被枚举（p.5、p.21、p.25）。

4. 哈希链（Hash Chains）

人话定义：每一块除了自己的数据，还装着前一块的整块哈希。课件先拿普通单链表做反例——指针和它指向的数据相互独立，可以在保持链表结构完整的前提下改掉数据（p.29）。

英文注意｜hash / encrypt：hash 是计算摘要，encrypt 是加密；不要写 decrypt a hash。哈希链能暴露修改，不会单凭自己阻止攻击者重算整条链。 答题句：Changing a block changes its hash and invalidates the stored reference in the next block.

例子：B2 装 H(B1) + d2，B3 装 H(B2) + d3，B4 装 H(B3) + d4（p.30）。改了 d2，B2 的哈希就变，B3 里存的旧值对不上，必须重算 B3；B3 一改 B4 又对不上，一路传到链尾（p.31）。

常见误解

以为哈希链和指针链表只是换了个存法 → 差别在 independent 这个词：指针只是地址，改了数据地址不变，结构看起来毫发无损；哈希把引用和内容绑死，结构本身反映内容是否被动过（p.29、p.30）。

5. Merkle 树与 Merkle 证明

人话定义：叶子节点存 H(数据)，内部节点存 H(左孩子标签 + 右孩子标签)，顶端是根 RT。内部节点不接触原始数据，只对下层的哈希再哈希（p.32）。

英文注意｜sibling / parent / root：sibling 是兄弟节点，parent 是父节点，root 是根；verify a proof 是验证证明。 答题句：The verifier combines the leaf hash with sibling hashes in the correct order and compares the result with the trusted root.

例子：p.33 那棵八叶子树的数据是 A B C D E F G I（刻意跳过 H，因为 H() 已被用作哈希函数的符号），h_AB = H(h_A + h_B)，RT = H(h_ABCD + h_EFGI)。要证某条数据在树里只需展开一部分哈希，课件的说法是 some but not all（p.34）。要证 Data I，展开的就是下图标青的那三个：

常见误解

证明给的是路径上每层的兄弟节点哈希，验证方从目标叶子向上重算；本例 8 叶子平衡树需 3 个兄弟哈希。+ 是字节拼接，不是算术加法；左右次序必须按树的位置确定，并把结果与可信根比较（p.36）。

6. 数字签名（Digital Signatures）

人话定义：由 Diffie–Hellman 于 1976 年提出，同时保证消息完整性和发送方真实性。用私钥签，用公钥验——私钥永远做「只有我能做」的事，公钥永远做「谁都能做」的事（p.38、p.40）。

英文注意｜sign / signature / verify：sign 是动词，signature 是名词；搭配 sign with a private key / verify with a public key。签名有效不等于消息保密。 答题句：A digital signature authenticates a message under a public key; it does not encrypt the message.

例子：σ = Sign(sk; m)，Verify(pk; m, σ) → True / False，True 表示消息应当被接受，三个输入缺一不可（p.42）。课件给的反例很直白：在邮件末尾粘上你的名字，证明不了是你发的——数字签名必须依赖整条消息（p.41）。

常见误解

以为签名顺便把消息也保护住不给人看 → 传的是 (m, σ)，m 是明文，任何截获的人都能读（p.44）。这一讲从头到尾没有任何一个工具提供机密性。另外实践中不直接对整条消息做签名运算，而是先哈希再签 σ = Sign(sk, H(m))，所以强抗碰撞是签名安全的前提：能找到 H(m₁) = H(m₂)，m₁ 的签名就能当 m₂ 的签名用（p.41 补充）。

把它们串起来

这一讲的结构是「一个工具 + 它的两条边界 + 补边界的第二个工具」。前半段把哈希的能力铺开：三条性质定义它安全在哪里，密码存储演示怎么用（明文 → 哈希 → 字典攻击 → 加盐，每一步补上一步的洞），哈希链和 Merkle 树演示怎么搭成数据结构。

转折点是 p.25 和 p.26：哈希不保密，也不证明来源。前者往原像里拼随机字节就能解决，后者哈希无论如何补不上，于是引出签名。最后两半合回一处——签名实践中签的是 H(m) 而不是 m，哈希提供「依赖整条消息」的定长摘要，签名提供「只有我能生成」。哈希和签名进同一份课件，原因在这里。

课件里的坑

• [输入条件] p.21 的摘要前缀可由 SHA-256(“abandon\n”) 复现，而不带换行得到 df864c05…。原图未明确算法和编码，不能据此断言老师算错或一定使用了 shell echo（p.21）。
• [显示提醒] 同一页的 Login Table 实际有三列（ID / Salt / Hash），导出成 PDF 后 Salt 那列被一个深蓝色动画色块盖住，看起来只有两列，下一页才露出来（p.21）
• [课件有误] p.21 / p.22 / p.23 三页的哈希列互相矛盾：p.23 标「加盐后」，值却退回了 p.21 的未加盐版本；Evan 那行三页完全相同，违背 p.22 自己给的定义。按 p.22 那版理解即可（p.21–23）
• [记号提醒] p.33 的 h_GI 印成 H(h_G h_I)，中间漏了 +，同图另外七个内部节点全都写了（p.33）
• [题设区别] p.35 的文字问「怎么证明 Data G 在树里」，p.36 的图演示的却是 Data I——两页选的目标数据不一致，两个方向都要会算（p.35、p.36）

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——三条安全性质各自防什么、Merkle 证明给的是哪几个哈希、私钥签公钥验；再把下面的「变式题」做一遍；最后回查两个最容易错的地方——以为「强抗碰撞」说的是攻击强度、以为证明里要给自己那条路径上的哈希。三步做完再往下看答案。

必背

1. 三条性质：单向（给 h 找不出 x）、弱抗碰撞即第二原像（给定 x 找不出另一个 y）、强抗碰撞（任意一对 x,y）；区分判据是攻击者控制几个输入；强抗碰撞蕴含弱抗碰撞，反之不成立。
2. 输出 n bit 时暴力找原像要 2ⁿ 次，找碰撞只要约 2^(n/2) 次（生日攻击），这是 SHA-1 被压到 2⁶⁹ 的来源。
3. Bitcoin = SHA2-256 + RIPEMD-160，Ethereum = Keccak（Keccak 与标准 SHA3 填充规则不同，同一输入结果不同）；Hash160 = RIPEMD160(SHA256(x))，输出 160 bit。
4. 加盐的作用是摧毁预计算、把批量攻击打回逐用户攻击；盐公开存储、每用户唯一、随机，它不让单个密码更难破。
5. 哈希既不提供机密性（低熵输入枚举即可还原）也不提供来源真实性（任何人都能算，数据和哈希可被一起替换）。
6. 哈希链每块装前一块的哈希，改中间任何一块必须重算它之后的所有块。
7. Merkle 证明给的是路径上每层的兄弟节点哈希，共 log₂(n) 个，8 叶子树是 3 个；拼接顺序不可交换。
8. 私钥签、公钥验；σ = Sign(sk; m)，Verify(pk; m, σ) → True/False，三个输入缺一不可；实践中先哈希再签。

完整例题

题面（课件 p.33 的八叶子树，数据依次为 A B C D E F G I）：给定根哈希 RT，要向一个只知道 RT 的人证明 Data I 确实在这棵树的叶子里，需要给他哪几个哈希？他怎么验？

1. 先定位 I 的位置：I 是最右边的叶子，它的兄弟是 G，父节点是 h_GI；h_GI 的兄弟是 h_EF，父节点是 h_EFGI；h_EFGI 的兄弟是 h_ABCD，父节点就是根。
2. 所以证明里要给的是这三层的兄弟：{h_G, h_EF, h_ABCD}，一共 3 个，正好等于 log₂(8) = 3。
3. 验证方手上有 Data I，第一步自己算 h_I = H(I)。
4. 第二步 h_GI = H(h_G + h_I)——注意 G 在左、I 在右，顺序不能颠倒。
5. 第三步 h_EFGI = H(h_EF + h_GI)。
6. 第四步 RT’ = H(h_ABCD + h_EFGI)。
7. 比对 RT’ 是否等于已知的 RT，相等则 Data I 确实在树中。
8. 对照题（p.35 文字问的那版）：要证 Data G，需要的是 {h_I, h_EF, h_ABCD}，步骤完全一样，只是第 2 步里 h_G 由自己算、h_I 由证明提供。两版只差最底下那一层给谁。
9. 对照「所有数据直接哈希在一起」：证明一条要把 8 条全给出去；Merkle 树只要 3 个哈希（p.34）。

变式题（先自己做）

English question（自编练习）：Given the same eight-leaf tree (A B C D E F G I), list the sibling hashes needed to prove the inclusion of Data C. Explain the verification order. How many sibling hashes are needed for a complete 16-leaf tree?

提示

读题：list 要列清单，explain 要说明步骤。题目问 C 的成员证明与 16 叶子树的证明长度。沿 C 往根走，每层记下兄弟，并保留左右次序。

建议得分点与答案（非官方评分细则）

Suggested answer: Provide h_D, h_AB and h_EFGI, together with their left/right positions. Recompute the root from C and compare it with the trusted root. A complete 16-leaf tree requires four sibling hashes.

自检点：给兄弟哈希、保留左右次序、说明 log₂ 的关系。以下中文推导用于核对。

(1) 证明 = {h_D, h_AB, h_EFGI}，3 个。验证方：

1. 自己算 h_C = H(C)；
2. h_CD = H(h_C + h_D)——C 在左、D 在右；
3. h_ABCD = H(h_AB + h_CD)——这次自己算出来的那半边在右；
4. RT’ = H(h_ABCD + h_EFGI)，与已知 RT 比对。

顺序是证明的一部分：把 H(h_C + h_D) 写成 H(h_D + h_C) 通常会得到不同根，不能随意交换。但两侧哈希相同则交换不变；哈希抗碰撞是安全假设，不是数学上的绝不碰撞。验证失败也不能直接证明 Data C 不在树里。

(2) 16 个叶子 → 树高 log₂(16) = 4，证明给 4 个哈希。每翻一倍叶子只多一个哈希，这正是 Merkle 树比”把全部数据交出去”省的地方。

闪卡自测

1. 第二原像攻击和碰撞攻击，哪个更难？为什么？

第二原像更难。判据是攻击者控制几个输入：第二原像里攻击者只控制一个，另一个是给定的；碰撞攻击里两个都由他自由挑（p.6、p.7）。

2. 为什么说「强抗碰撞蕴含弱抗碰撞」，反过来不成立？

能防住「自由挑两个」的函数，自然也防住「指定一个再找另一个」这种更受限的情形。反向不成立，因为防住受限情形不代表能防住更宽松的情形（p.7）。

3. Keccak 和 SHA3 是一回事吗？

不是。Keccak 是 SHA-3 竞赛的获胜算法，NIST 标准化时改了填充规则，所以标准 SHA3-256 和以太坊用的 Keccak-256 对同一输入给出完全不同的结果。以太坊在 SHA3 定稿前上线，一直沿用原版 Keccak（p.8）。

4. 为什么有人要一个「故意很慢」的哈希函数？

密码哈希场景下慢能拖垮暴力破解。合法用户登录时多花几十毫秒无感，攻击者跑整本字典的成本却被拉开几个数量级。注意这和「哈希要快」不矛盾，是两个场景：区块链每秒要算几百万次，密码只在登录时算一次（p.3、p.11、p.12）。

5. 不加盐时攻击者算一次哈希能比对多少人？加盐后呢？

不加盐时一次计算可比对全表所有用户，成本与用户数无关；加盐后一次计算只能比对一个人，攻击 N 个用户的总成本变成字典长度乘以 N，预计算的彩虹表完全失效（p.21、p.23）。

6. 石头剪刀布那个 commit-reveal 协议错在哪？怎么修？

原像空间只有三个，对手把三种出招各算一遍哈希对照即可，不需要「破解」。修法是承诺 H(choice ‖ nonce)，nonce 取随机 32 字节，揭晓时一并公布，原像空间扩到 3 × 2²⁵⁶（p.25）。

7. 「数据和哈希对得上」能证明什么、不能证明什么？

有可信参照摘要时，可用来核对完整性；若摘要也由攻击者提供，只能说明两者匹配。它不能单独证明来源，因为数据和哈希可被一起替换。签名还需要可信的公钥关联（p.26、p.40）。

8. 哈希链里改了中间一块会怎样？

那一块的哈希变了，下一块里存的旧值对不上，必须重算改写；改了下一块它的哈希又变，再下一块又对不上，一路传到链尾。结论是改中间任何一块必须重算它之后的所有块（p.31）。

9. 为什么实践中签的是 H(m) 而不是 m？这带来什么前提？

非对称运算慢、消息可能很长，所以先哈希成定长摘要再签。代价是抗碰撞变成签名安全的前提：一旦能找到 H(m₁) = H(m₂)，m₁ 的签名就能直接当 m₂ 的签名用（p.41 补充）。

下一讲

下一讲把这套工具装进一个真实平台：地址是公钥哈希出来的、状态用一棵树组织、每笔交易都要验签。带着「这里的哈希和签名分别落到了以太坊的哪个字段上」这个问题去听。