3863 字
19 分钟
第二章 密码学基础:哈希、Merkle 树与公钥密码

哈希函数把任意长度的消息压成固定长度的摘要,Merkle 树用这些摘要组织数据,公钥密码则把安全性建立在离散对数或大整数分解这类难题上。第二章的十道题分别落在这些构件上,涉及性质判断、生日概率、树高计算,以及 ElGamal、ECC 和 RSA 的具体运算。

一、哈希函数#

哈希函数把任意长度的输入映射为固定长度的输出,常见输出长度有 160 位和 256 位。它需要同时满足两类要求。

工程性质:

  1. 确定性:同一输入总得到同一输出。
  2. 固定长度:输出长度与输入长度无关。
  3. 计算高效:任意输入都能快速算出摘要。

安全性质:

  1. 抗原像性:给定摘要 hh,找不到 xx 使 H(x)=hH(x)=h。
  2. 抗第二原像性:给定 xx,找不到另一个 x′≠xx'\neq x 使 H(x′)=H(x)H(x')=H(x)。
  3. 抗碰撞性:找不到任意一对 x≠x′x\neq x',使它们的摘要相同。
  4. 雪崩效应:输入改变 1 比特,输出大约有一半比特翻转。

三条安全性的强度并不相同。抗碰撞是最强的要求,满足抗碰撞也就满足了抗第二原像;反过来的关系不成立。

哈希函数的常见用途包括完整性校验、数字签名(先对消息哈希再签名)、Merkle 树、口令存储(加盐后哈希)和工作量证明。

二、生日悖论与碰撞复杂度#

生日问题问的是 nn 个人里至少有两个人生日相同的概率。直接算“至少一对相同”很麻烦,通常先算“所有人的生日都不同”:

P0(n)=∏i=0n−1365−i365P_0(n)=\prod_{i=0}^{n-1}\frac{365-i}{365}

至少一对相同的概率是:

P(n)=1−P0(n)P(n)=1-P_0(n)

n=30n=30 时 P≈70.6%P\approx70.6\%;n=22n=22 时约 47.6%47.6\%,n=23n=23 时约 50.7%50.7\%。要让概率超过 50%,23 个人就够了,这就是生日悖论反直觉的地方。

把生日换成哈希值,结论更值得警惕:输出空间大小为 NN 时,随机取大约 N\sqrt{N} 个值就有一半以上的概率撞上碰撞,精确常数约为 1.18N1.18\sqrt{N}。对应到 mm 位的哈希,碰撞复杂度只有 2m/22^{m/2}。所以 160 位输出的哈希,抗碰撞强度只有 80 位;这也是抗碰撞比抗原像更容易被攻破的原因。

三、Merkle 树#

Merkle 树是一棵二叉树:叶子节点存放数据块的哈希,父节点存放左右两个子节点哈希拼接后的哈希,最顶上是根哈希 Merkle Root。任何一片叶子变化,根哈希都会变,所以根哈希就能代表整棵树的完整性。

叶子的个数通常补齐到 2 的幂,补出来的空位用约定的填充值。树高按下面计算:

h=⌈log⁡2n⌉h=\lceil\log_2 n\rceil

n=9n=9 时补齐到 16 个叶子,h=4h=4,也就是从根到叶子经过 4 条边。

验证一笔数据是否在树里,只需要从该叶子到根的兄弟哈希,路径长度等于树高,不必拿到全部数据。

比较两份数据的差异时,从根开始:根哈希相同,说明两份数据完全一致,整棵树跳过;根哈希不同,就递归比较两个子节点,只沿哈希不同的分支往下走。

以 9 个数据块、只有第 5 块不同为例,比较过程是:根不同 → 左半部分 1–8 不同(第 5 块在这一侧)→ 5–8 不同 → 5–6 不同 → 比较叶子 5。右半部分 9–16 因为哈希相同,整块跳过。比较次数与 log⁡n\log n 成正比,比逐个比较文件少得多。

四、密码体制的组成与分类#

一个密码体制由五部分组成:明文、密文、加密算法、解密算法和密钥。加密算法把明文和密钥映射为密文,解密算法把密文和密钥还原为明文。

按密钥的使用方式,密码体制分为两类:

类型密钥代表算法主要问题
对称密码加密与解密使用同一密钥AES、DES密钥如何安全分发
非对称密码公钥加密、私钥解密,或私钥签名、公钥验证RSA、ElGamal、ECC计算慢,密文比明文长

非对称密码解决了密钥分发问题,但代价是运算开销大、密文膨胀,所以实际系统通常两者配合:用非对称密码协商或加密会话密钥,再用对称密码传输数据。

密码体制的设计遵循 Kerckhoffs 原则:算法的安全性只依赖密钥保密,不依赖算法本身保密。

五、攻击形式#

按攻击者掌握的信息,密码攻击分为四类,能力依次增强:

  1. 唯密文攻击:攻击者只有密文,通过分析密文恢复明文或密钥。
  2. 已知明文攻击:攻击者掌握若干明文及其对应的密文,据此推导密钥。
  3. 选择明文攻击:攻击者可以选择明文,并得到对应的密文。
  4. 选择密文攻击:攻击者可以选择密文,并得到对应的明文。

选择密文攻击的能力最强,攻击者能直接观察解密结果。能抗住选择密文攻击的方案,自然也抗得住前三种。

六、流密码与分组密码#

对称密码按处理单位分为流密码和分组密码:

比较项目流密码分组密码
加密单位逐位或逐字节加密固定长度的数据块
加密方式明文与密钥流结合对整个数据块进行变换
速度通常较快取决于算法和实现
填充通常不需要某些工作模式需要
代表算法RC4、ChaCha20AES、DES

流密码用种子密钥生成一条与明文等长的密钥流,逐位或逐字节异或;分组密码把明文切成固定长度的块,逐块变换。分组密码处理长消息时还需要工作模式:ECB 对每个块独立加密,相同的明文块得到相同的密文块,暴露了数据规律;CBC 让每个明文块先与前一块的密文异或,并用初始向量处理第一块;CTR 把分组密码变成密钥流,用法接近流密码。CBC 和 CTR 都需要初始向量,初始向量不需要保密,但要保证不可预测或唯一。

七、ElGamal 密码体制#

ElGamal 的安全性建立在离散对数问题上。取大素数 pp 和生成元 gg,私钥为 xx,公钥为:

y=gx mod py=g^x\bmod p

加密时随机选 kk,密文是一对:

c1=gk mod p,c2=m⋅yk mod pc_1=g^k\bmod p,\qquad c_2=m\cdot y^k\bmod p

解密时用私钥消去 c1c_1 的指数部分:

m=c2⋅(c1x)−1 mod pm=c_2\cdot(c_1^x)^{-1}\bmod p

它属于概率加密:每次加密的随机 kk 不同,同一明文得到的密文也不同,因此攻击者无法通过比较密文判断两条消息是否相同。代价是密文长度是明文的两倍。kk 必须每次重新选取,重复使用同一个 kk 会让两条密文之间只剩明文之比,直接泄露消息。

八、椭圆曲线与 ECC#

椭圆曲线在有限域或有理数域上定义为:

y2=x3+ax+b,4a3+27b2≠0y^2=x^3+ax+b,\qquad 4a^3+27b^2\neq0

判别式不为 0 保证曲线光滑、没有重根。曲线上的点连同无穷远点构成一个群,群运算就是点加法。

两个不同点相加时,斜率为两点连线斜率:

λ=y2−y1x2−x1\lambda=\frac{y_2-y_1}{x_2-x_1}

同一个点倍乘时,斜率为切线斜率:

λ=3x12+a2y1\lambda=\frac{3x_1^2+a}{2y_1}

得到新点:

x3=λ2−x1−x2,y3=λ(x1−x3)−y1x_3=\lambda^2-x_1-x_2,\qquad y_3=\lambda(x_1-x_3)-y_1

倍点的情形把 x2x_2、y2y_2 换回 x1x_1、y1y_1,即 x3=λ2−2x1x_3=\lambda^2-2x_1。y1=0y_1=0 的点不能做倍点,因为切线垂直。

ECC 的困难问题是椭圆曲线离散对数:已知点 PP 和 kPkP,求标量 kk。与 RSA 和传统 ElGamal 相比,它的优势集中在效率上:

  1. 密钥长度短:相同安全强度下,ECC 的密钥比 RSA 短得多,256 位 ECC 大约相当于 3072 位 RSA。
  2. 计算效率高:相同安全强度下,签名和验签的运算量更小。
  3. 存储空间小:密钥和签名占用的字节数少。
  4. 通信开销小:传输公钥和签名所需的数据量少,适合带宽受限的环境。
  5. 适用范围广:移动设备、物联网和区块链这类资源受限的场景常用 ECC。

九、RSA 密码体制#

RSA 的密钥生成分四步:

  1. 选两个大素数 pp 和 qq,计算 n=pqn=pq。
  2. 计算欧拉函数 φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)。
  3. 选公钥指数 ee,要求 ee 与 φ(n)\varphi(n) 互素,常用 65537。
  4. 求私钥指数 dd,它是 ee 关于 φ(n)\varphi(n) 的模逆元:
ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}

加密和解密分别是 c=me mod nc=m^e\bmod n 与 m=cd mod nm=c^d\bmod n。数字签名把两个指数反过来用:私钥签名,公钥验证。

S=H(m)d mod n,H(m)=Se mod nS=H(m)^d\bmod n,\qquad H(m)=S^e\bmod n

签名时先对消息做哈希,再对哈希值做私钥运算;验证时用公钥还原出哈希值,与本地计算的哈希比对。实际方案还要对哈希值做填充(比如 PKCS#1 v1.5 或 PSS),否则教科书式的 RSA 签名存在伪造风险。

RSA 的安全性依赖大整数分解:知道 nn 但分解不出 pp、qq,就算不出 φ(n)\varphi(n),也就求不出 dd。这也解释了两条前提:pp、qq 必须是素数,且 ee 必须与 φ(n)\varphi(n) 互素,否则模逆元根本不存在。

十、重点公式#

知识点公式
哈希函数H(x)H(x)
生日悖论P=1−∏i=0n−1365−i365P=1-\prod_{i=0}^{n-1}\frac{365-i}{365}
Merkle 树高h=⌈log⁡2n⌉h=\lceil\log_2 n\rceil
ElGamal 公钥y=gx mod py=g^x\bmod p
ElGamal 加密c1=gk mod p, c2=m⋅yk mod pc_1=g^k\bmod p,\ c_2=m\cdot y^k\bmod p
ElGamal 解密m=c2(c1x)−1 mod pm=c_2(c_1^x)^{-1}\bmod p
椭圆曲线y2=x3+ax+by^2=x^3+ax+b
椭圆曲线倍点λ=3x12+a2y1, x3=λ2−2x1\lambda=\frac{3x_1^2+a}{2y_1},\ x_3=\lambda^2-2x_1
RSA 欧拉函数φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)
RSA 密钥关系ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}
RSA 签名S=H(m)d mod nS=H(m)^d\bmod n
RSA 验签H(m)=Se mod nH(m)=S^e\bmod n

复习题与参考答案#

1. 哈希函数的性质:分析 H(x)=ax mod pH(x)=a^x\bmod p

其中 pp 是素数,aa 是不能被 pp 整除的整数。这个函数满足:

  1. 确定性:相同输入总得到相同输出。
  2. 固定长度:输出是模 pp 的余数,范围在 00 到 p−1p-1。
  3. 计算高效:模幂运算可以快速完成。

但它不满足安全哈希的要求:

  1. 抗碰撞性不足:ax mod pa^x\bmod p 以 aa 在模 pp 下的阶为周期,存在正整数 kk 使 H(x)=H(x+k)H(x)=H(x+k),构造碰撞很容易。
  2. 抗第二原像性不足:已知一个输入 xx,取 x+kx+k 就得到哈希值相同的另一个输入。
  3. 雪崩效应不足:输入变化时,输出不一定产生足够随机、均匀的变化。

所以它只有确定性和固定长度这些工程性质,不具备抗碰撞等安全性质。

2. 异或哈希函数满足哪些性质

消息 mm 被分成 160 比特的块:

m=M1∥M2∥⋯∥Mtm=M_1\parallel M_2\parallel\cdots\parallel M_t

哈希函数为:

H(m)=M1⊕M2⊕⋯⊕MtH(m)=M_1\oplus M_2\oplus\cdots\oplus M_t

满足的性质:

  1. 确定性:相同的消息始终得到相同的哈希值。
  2. 固定长度:每块 160 比特,异或结果也是 160 比特。
  3. 计算高效:只需要按位异或。

不满足的性质:

  1. 抗碰撞性不足:异或满足交换律,交换数据块顺序不会改变结果。
  2. 抗第二原像性不足:调整数据块就能构造出不同消息,使异或结果保持不变。
  3. 抗原像性不足:已知目标哈希值 hh,可以任意选择前面的数据块,再令最后一块 Mt=h⊕M1⊕⋯⊕Mt−1M_t=h\oplus M_1\oplus\cdots\oplus M_{t-1},直接构造出对应消息。
  4. 雪崩效应不足:一个输入比特变化只影响输出对应的比特,缺乏扩散。

3. 生日悖论(一年按 365 天)

(1)30 个人中至少两人同生日的概率。

先算所有人生日都不同的概率:

P0=365365×364365×⋯×336365=365!335!×36530P_0=\frac{365}{365}\times\frac{364}{365}\times\cdots\times\frac{336}{365}=\frac{365!}{335!\times365^{30}}

至少两人同生日的概率:

P=1−P0≈70.6%P=1-P_0\approx70.6\%

(2)概率超过 50% 至少需要多少人。

P(n)=1−∏i=0n−1365−i365P(n)=1-\prod_{i=0}^{n-1}\frac{365-i}{365}

代入得 P(22)≈47.6%P(22)\approx47.6\%,P(23)≈50.7%P(23)\approx50.7\%,所以:

n=23n=23

至少需要 23 个人。

4. 9 个数据块的 Merkle 树

(1)树结构。叶子存放数据块哈希,父节点存放子节点哈希拼接后的哈希。9 个数据块补齐到 16 个叶子,空位用约定的填充值。

树高为:

h=⌈log⁡29⌉=4h=\lceil\log_2 9\rceil=4

即根到叶子有 4 条边。

(2)比较过程。两台机器目录相同,只有数据块 5 不同:

  1. 比较两台机器的根哈希,不同,继续向下。
  2. 比较两个子节点,左半部分 1–8 的哈希不同,右半部分 9–16 相同,跳过。
  3. 在 1–8 内继续,定位到 5–8 子树。
  4. 在 5–8 内继续,定位到 5–6。
  5. 比较叶子 5 和 6,确认叶子 5 不同。

Merkle 树逐层比较哈希,只沿不同的分支下降,不必逐一比较全部文件。

5. 密码体制的组成、分类、攻击形式与流/分组密码的区别

(1)组成:明文、密文、加密算法、解密算法、密钥。

(2)分类:对称密码体制加解密使用同一密钥,例如 AES、DES;非对称密码体制使用公钥和私钥,加解密使用不同密钥,例如 RSA、ECC。

(3)常见攻击形式:

  1. 唯密文攻击:攻击者只能获得密文,通过分析密文破解明文或密钥。
  2. 已知明文攻击:攻击者已知部分明文及其对应密文,尝试推导密钥。
  3. 选择明文攻击:攻击者可以选择明文,并获得对应密文。
  4. 选择密文攻击:攻击者可以选择密文,并获得对应明文。

(4)流密码与分组密码的区别:

比较项目流密码分组密码
加密单位逐位或逐字节加密固定长度的数据块
加密方式明文与密钥流结合对整个数据块进行变换
速度通常较快取决于算法和实现
填充通常不需要某些工作模式需要
代表算法RC4、ChaCha20AES、DES

流密码逐位或逐字节处理数据,分组密码以固定长度的数据块为单位加密。

6. ElGamal 解密:p=17p=17,g=3g=3,x=3x=3,密文 (7,6)(7,6)

p=17,g=3,x=3p=17,\quad g=3,\quad x=3

先算 Bob 的公钥:

y=gx mod p=33 mod 17=27 mod 17=10y=g^x\bmod p=3^3\bmod17=27\bmod17=10

解密公式:

m=c2(c1x)−1 mod pm=c_2(c_1^x)^{-1}\bmod p

代入密文 (c1,c2)=(7,6)(c_1,c_2)=(7,6):

m=6(73)−1 mod 17m=6(7^3)^{-1}\bmod17

其中 73=343≡3(mod17)7^3=343\equiv3\pmod{17}。求 3 在模 17 下的逆元,因为 3×6=18≡1(mod17)3\times6=18\equiv1\pmod{17},所以 3−1≡6(mod17)3^{-1}\equiv6\pmod{17}。

m=6×6 mod 17=36 mod 17=2m=6\times6\bmod17=36\bmod17=2

明文是 m=2m=2。

7. 椭圆曲线 E:y2=x3−2E:y^2=x^3-2,求另一点

取曲线上的点 P=(3,5)P=(3,5),验证 52=27−2=255^2=27-2=25,成立。

倍点斜率为:

λ=3x122y1=3×322×5=2710\lambda=\frac{3x_1^2}{2y_1}=\frac{3\times3^2}{2\times5}=\frac{27}{10}

新点的横坐标:

x3=λ2−2x1=(2710)2−6=729100−600100=129100x_3=\lambda^2-2x_1=\left(\frac{27}{10}\right)^2-6=\frac{729}{100}-\frac{600}{100}=\frac{129}{100}

新点的纵坐标:

y3=λ(x1−x3)−y1=2710×171100−5=46171000−5=−3831000y_3=\lambda(x_1-x_3)-y_1=\frac{27}{10}\times\frac{171}{100}-5=\frac{4617}{1000}-5=-\frac{383}{1000}

所以:

P+P=(129100,−3831000)P+P=\left(\frac{129}{100},-\frac{383}{1000}\right)

8. ECC 相对 RSA 和 ElGamal 的优势

  1. 密钥长度短:相同安全强度下,ECC 所需的密钥长度远小于 RSA 和传统 ElGamal。
  2. 计算效率高:相同安全强度下,ECC 的运算量更小。
  3. 存储空间小:密钥和数字签名占用的存储空间较少。
  4. 通信开销小:传输公钥和签名所需的数据量少,适合带宽受限的环境。
  5. 适用范围广:适合移动设备、物联网和区块链等场景。

最主要的优势是在相同安全强度下密钥短、存储小、通信开销低。

9. RSA 求 dd

RSA 中 φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1),d=e−1 mod φ(n)d=e^{-1}\bmod\varphi(n),即 ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}。

(1)p=1p=1,q=11q=11,e=3e=3。

φ(n)=(1−1)(11−1)=0\varphi(n)=(1-1)(11-1)=0

模数为 0,模逆元没有定义;而且 p=1p=1 不是素数,不满足 RSA 的基本要求。所以不存在有效的 dd。

(2)p=3p=3,q=41q=41,e=23e=23。

φ(n)=(3−1)(41−1)=2×40=80\varphi(n)=(3-1)(41-1)=2\times40=8023d≡1(mod80)23d\equiv1\pmod{80}

因为 23×7=161=2×80+123\times7=161=2\times80+1,所以:

d=7d=7

(3)p=5p=5,q=23q=23,e=59e=59。

φ(n)=(5−1)(23−1)=4×22=88\varphi(n)=(5-1)(23-1)=4\times22=8859d≡1(mod88)59d\equiv1\pmod{88}

因为 59×3=177=2×88+159\times3=177=2\times88+1,所以:

d=3d=3

(4)p=47p=47,q=59q=59,e=17e=17。

φ(n)=(47−1)(59−1)=46×58=2668\varphi(n)=(47-1)(59-1)=46\times58=266817d≡1(mod2668)17d\equiv1\pmod{2668}

因为 17×157=2669=2668+117\times157=2669=2668+1,所以:

d=157d=157

四种情况汇总:

情况φ(n)\varphi(n)dd
10不存在
2807
3883
42668157

10. RSA 数字签名:(d,n)=(13,51)(d,n)=(13,51),哈希值 4

已知 d=13d=13,n=51=3×17n=51=3\times17。

(1)欧拉函数:

φ(n)=(3−1)(17−1)=2×16=32\varphi(n)=(3-1)(17-1)=2\times16=32

(2)求公钥指数 ee:

13e≡1(mod32)13e\equiv1\pmod{32}

因为 13×5=65=2×32+113\times5=65=2\times32+1,所以 e=5e=5,公钥为:

(e,n)=(5,51)(e,n)=(5,51)

(3)计算签名:

S=H(m)d mod n=413 mod 51S=H(m)^d\bmod n=4^{13}\bmod51

利用 44=256≡1(mod51)4^4=256\equiv1\pmod{51},所以:

413=(44)3×4≡1×4=44^{13}=(4^4)^3\times4\equiv1\times4=4

即 S=4S=4。

(4)验证签名:

H(m)=Se mod n=45 mod 51H(m)=S^e\bmod n=4^5\bmod5145=44×4≡1×4=44^5=4^4\times4\equiv1\times4=4

还原出的哈希值与本地计算的 H(m)=4H(m)=4 相同,验证成功。

结果汇总:私钥 (13,51)(13,51),公钥 (5,51)(5,51),签名 S=4S=4,验证成功。

第二章 密码学基础:哈希、Merkle 树与公钥密码
https://blog.xqcherry.top/posts/blockchain/chapter-2-cryptography/
作者
xqcherry
发布于
2026-11-09
许可协议
CC BY-NC-SA 4.0