哈希函数把任意长度的消息压成固定长度的摘要,Merkle 树用这些摘要组织数据,公钥密码则把安全性建立在离散对数或大整数分解这类难题上。第二章的十道题分别落在这些构件上,涉及性质判断、生日概率、树高计算,以及 ElGamal、ECC 和 RSA 的具体运算。
一、哈希函数#
哈希函数把任意长度的输入映射为固定长度的输出,常见输出长度有 160 位和 256 位。它需要同时满足两类要求。
工程性质:
- 确定性:同一输入总得到同一输出。
- 固定长度:输出长度与输入长度无关。
- 计算高效:任意输入都能快速算出摘要。
安全性质:
- 抗原像性:给定摘要 h,找不到 x 使 H(x)=h。
- 抗第二原像性:给定 x,找不到另一个 x′=x 使 H(x′)=H(x)。
- 抗碰撞性:找不到任意一对 x=x′,使它们的摘要相同。
- 雪崩效应:输入改变 1 比特,输出大约有一半比特翻转。
三条安全性的强度并不相同。抗碰撞是最强的要求,满足抗碰撞也就满足了抗第二原像;反过来的关系不成立。
哈希函数的常见用途包括完整性校验、数字签名(先对消息哈希再签名)、Merkle 树、口令存储(加盐后哈希)和工作量证明。
二、生日悖论与碰撞复杂度#
生日问题问的是 n 个人里至少有两个人生日相同的概率。直接算“至少一对相同”很麻烦,通常先算“所有人的生日都不同”:
P0(n)=i=0∏n−1365365−i至少一对相同的概率是:
P(n)=1−P0(n)n=30 时 P≈70.6%;n=22 时约 47.6%,n=23 时约 50.7%。要让概率超过 50%,23 个人就够了,这就是生日悖论反直觉的地方。
把生日换成哈希值,结论更值得警惕:输出空间大小为 N 时,随机取大约 N 个值就有一半以上的概率撞上碰撞,精确常数约为 1.18N。对应到 m 位的哈希,碰撞复杂度只有 2m/2。所以 160 位输出的哈希,抗碰撞强度只有 80 位;这也是抗碰撞比抗原像更容易被攻破的原因。
三、Merkle 树#
Merkle 树是一棵二叉树:叶子节点存放数据块的哈希,父节点存放左右两个子节点哈希拼接后的哈希,最顶上是根哈希 Merkle Root。任何一片叶子变化,根哈希都会变,所以根哈希就能代表整棵树的完整性。
叶子的个数通常补齐到 2 的幂,补出来的空位用约定的填充值。树高按下面计算:
h=⌈log2n⌉n=9 时补齐到 16 个叶子,h=4,也就是从根到叶子经过 4 条边。
验证一笔数据是否在树里,只需要从该叶子到根的兄弟哈希,路径长度等于树高,不必拿到全部数据。
比较两份数据的差异时,从根开始:根哈希相同,说明两份数据完全一致,整棵树跳过;根哈希不同,就递归比较两个子节点,只沿哈希不同的分支往下走。
以 9 个数据块、只有第 5 块不同为例,比较过程是:根不同 → 左半部分 1–8 不同(第 5 块在这一侧)→ 5–8 不同 → 5–6 不同 → 比较叶子 5。右半部分 9–16 因为哈希相同,整块跳过。比较次数与 logn 成正比,比逐个比较文件少得多。
四、密码体制的组成与分类#
一个密码体制由五部分组成:明文、密文、加密算法、解密算法和密钥。加密算法把明文和密钥映射为密文,解密算法把密文和密钥还原为明文。
按密钥的使用方式,密码体制分为两类:
| 类型 | 密钥 | 代表算法 | 主要问题 |
|---|
| 对称密码 | 加密与解密使用同一密钥 | AES、DES | 密钥如何安全分发 |
| 非对称密码 | 公钥加密、私钥解密,或私钥签名、公钥验证 | RSA、ElGamal、ECC | 计算慢,密文比明文长 |
非对称密码解决了密钥分发问题,但代价是运算开销大、密文膨胀,所以实际系统通常两者配合:用非对称密码协商或加密会话密钥,再用对称密码传输数据。
密码体制的设计遵循 Kerckhoffs 原则:算法的安全性只依赖密钥保密,不依赖算法本身保密。
五、攻击形式#
按攻击者掌握的信息,密码攻击分为四类,能力依次增强:
- 唯密文攻击:攻击者只有密文,通过分析密文恢复明文或密钥。
- 已知明文攻击:攻击者掌握若干明文及其对应的密文,据此推导密钥。
- 选择明文攻击:攻击者可以选择明文,并得到对应的密文。
- 选择密文攻击:攻击者可以选择密文,并得到对应的明文。
选择密文攻击的能力最强,攻击者能直接观察解密结果。能抗住选择密文攻击的方案,自然也抗得住前三种。
六、流密码与分组密码#
对称密码按处理单位分为流密码和分组密码:
| 比较项目 | 流密码 | 分组密码 |
|---|
| 加密单位 | 逐位或逐字节加密 | 固定长度的数据块 |
| 加密方式 | 明文与密钥流结合 | 对整个数据块进行变换 |
| 速度 | 通常较快 | 取决于算法和实现 |
| 填充 | 通常不需要 | 某些工作模式需要 |
| 代表算法 | RC4、ChaCha20 | AES、DES |
流密码用种子密钥生成一条与明文等长的密钥流,逐位或逐字节异或;分组密码把明文切成固定长度的块,逐块变换。分组密码处理长消息时还需要工作模式:ECB 对每个块独立加密,相同的明文块得到相同的密文块,暴露了数据规律;CBC 让每个明文块先与前一块的密文异或,并用初始向量处理第一块;CTR 把分组密码变成密钥流,用法接近流密码。CBC 和 CTR 都需要初始向量,初始向量不需要保密,但要保证不可预测或唯一。
七、ElGamal 密码体制#
ElGamal 的安全性建立在离散对数问题上。取大素数 p 和生成元 g,私钥为 x,公钥为:
y=gxmodp加密时随机选 k,密文是一对:
c1=gkmodp,c2=m⋅ykmodp解密时用私钥消去 c1 的指数部分:
m=c2⋅(c1x)−1modp它属于概率加密:每次加密的随机 k 不同,同一明文得到的密文也不同,因此攻击者无法通过比较密文判断两条消息是否相同。代价是密文长度是明文的两倍。k 必须每次重新选取,重复使用同一个 k 会让两条密文之间只剩明文之比,直接泄露消息。
八、椭圆曲线与 ECC#
椭圆曲线在有限域或有理数域上定义为:
y2=x3+ax+b,4a3+27b2=0判别式不为 0 保证曲线光滑、没有重根。曲线上的点连同无穷远点构成一个群,群运算就是点加法。
两个不同点相加时,斜率为两点连线斜率:
λ=x2−x1y2−y1同一个点倍乘时,斜率为切线斜率:
λ=2y13x12+a得到新点:
x3=λ2−x1−x2,y3=λ(x1−x3)−y1倍点的情形把 x2、y2 换回 x1、y1,即 x3=λ2−2x1。y1=0 的点不能做倍点,因为切线垂直。
ECC 的困难问题是椭圆曲线离散对数:已知点 P 和 kP,求标量 k。与 RSA 和传统 ElGamal 相比,它的优势集中在效率上:
- 密钥长度短:相同安全强度下,ECC 的密钥比 RSA 短得多,256 位 ECC 大约相当于 3072 位 RSA。
- 计算效率高:相同安全强度下,签名和验签的运算量更小。
- 存储空间小:密钥和签名占用的字节数少。
- 通信开销小:传输公钥和签名所需的数据量少,适合带宽受限的环境。
- 适用范围广:移动设备、物联网和区块链这类资源受限的场景常用 ECC。
九、RSA 密码体制#
RSA 的密钥生成分四步:
- 选两个大素数 p 和 q,计算 n=pq。
- 计算欧拉函数 φ(n)=(p−1)(q−1)。
- 选公钥指数 e,要求 e 与 φ(n) 互素,常用 65537。
- 求私钥指数 d,它是 e 关于 φ(n) 的模逆元:
ed≡1(modφ(n))加密和解密分别是 c=memodn 与 m=cdmodn。数字签名把两个指数反过来用:私钥签名,公钥验证。
S=H(m)dmodn,H(m)=Semodn签名时先对消息做哈希,再对哈希值做私钥运算;验证时用公钥还原出哈希值,与本地计算的哈希比对。实际方案还要对哈希值做填充(比如 PKCS#1 v1.5 或 PSS),否则教科书式的 RSA 签名存在伪造风险。
RSA 的安全性依赖大整数分解:知道 n 但分解不出 p、q,就算不出 φ(n),也就求不出 d。这也解释了两条前提:p、q 必须是素数,且 e 必须与 φ(n) 互素,否则模逆元根本不存在。
十、重点公式#
| 知识点 | 公式 |
|---|
| 哈希函数 | H(x) |
| 生日悖论 | P=1−∏i=0n−1365365−i |
| Merkle 树高 | h=⌈log2n⌉ |
| ElGamal 公钥 | y=gxmodp |
| ElGamal 加密 | c1=gkmodp, c2=m⋅ykmodp |
| ElGamal 解密 | m=c2(c1x)−1modp |
| 椭圆曲线 | y2=x3+ax+b |
| 椭圆曲线倍点 | λ=2y13x12+a, x3=λ2−2x1 |
| RSA 欧拉函数 | φ(n)=(p−1)(q−1) |
| RSA 密钥关系 | ed≡1(modφ(n)) |
| RSA 签名 | S=H(m)dmodn |
| RSA 验签 | H(m)=Semodn |
复习题与参考答案#
1. 哈希函数的性质:分析 H(x)=axmodp
其中 p 是素数,a 是不能被 p 整除的整数。这个函数满足:
- 确定性:相同输入总得到相同输出。
- 固定长度:输出是模 p 的余数,范围在 0 到 p−1。
- 计算高效:模幂运算可以快速完成。
但它不满足安全哈希的要求:
- 抗碰撞性不足:axmodp 以 a 在模 p 下的阶为周期,存在正整数 k 使 H(x)=H(x+k),构造碰撞很容易。
- 抗第二原像性不足:已知一个输入 x,取 x+k 就得到哈希值相同的另一个输入。
- 雪崩效应不足:输入变化时,输出不一定产生足够随机、均匀的变化。
所以它只有确定性和固定长度这些工程性质,不具备抗碰撞等安全性质。
2. 异或哈希函数满足哪些性质
消息 m 被分成 160 比特的块:
m=M1∥M2∥⋯∥Mt哈希函数为:
H(m)=M1⊕M2⊕⋯⊕Mt满足的性质:
- 确定性:相同的消息始终得到相同的哈希值。
- 固定长度:每块 160 比特,异或结果也是 160 比特。
- 计算高效:只需要按位异或。
不满足的性质:
- 抗碰撞性不足:异或满足交换律,交换数据块顺序不会改变结果。
- 抗第二原像性不足:调整数据块就能构造出不同消息,使异或结果保持不变。
- 抗原像性不足:已知目标哈希值 h,可以任意选择前面的数据块,再令最后一块 Mt=h⊕M1⊕⋯⊕Mt−1,直接构造出对应消息。
- 雪崩效应不足:一个输入比特变化只影响输出对应的比特,缺乏扩散。
3. 生日悖论(一年按 365 天)
(1)30 个人中至少两人同生日的概率。
先算所有人生日都不同的概率:
P0=365365×365364×⋯×365336=335!×36530365!至少两人同生日的概率:
P=1−P0≈70.6%(2)概率超过 50% 至少需要多少人。
P(n)=1−i=0∏n−1365365−i代入得 P(22)≈47.6%,P(23)≈50.7%,所以:
n=23至少需要 23 个人。
4. 9 个数据块的 Merkle 树
(1)树结构。叶子存放数据块哈希,父节点存放子节点哈希拼接后的哈希。9 个数据块补齐到 16 个叶子,空位用约定的填充值。
树高为:
h=⌈log29⌉=4即根到叶子有 4 条边。
(2)比较过程。两台机器目录相同,只有数据块 5 不同:
- 比较两台机器的根哈希,不同,继续向下。
- 比较两个子节点,左半部分 1–8 的哈希不同,右半部分 9–16 相同,跳过。
- 在 1–8 内继续,定位到 5–8 子树。
- 在 5–8 内继续,定位到 5–6。
- 比较叶子 5 和 6,确认叶子 5 不同。
Merkle 树逐层比较哈希,只沿不同的分支下降,不必逐一比较全部文件。
5. 密码体制的组成、分类、攻击形式与流/分组密码的区别
(1)组成:明文、密文、加密算法、解密算法、密钥。
(2)分类:对称密码体制加解密使用同一密钥,例如 AES、DES;非对称密码体制使用公钥和私钥,加解密使用不同密钥,例如 RSA、ECC。
(3)常见攻击形式:
- 唯密文攻击:攻击者只能获得密文,通过分析密文破解明文或密钥。
- 已知明文攻击:攻击者已知部分明文及其对应密文,尝试推导密钥。
- 选择明文攻击:攻击者可以选择明文,并获得对应密文。
- 选择密文攻击:攻击者可以选择密文,并获得对应明文。
(4)流密码与分组密码的区别:
| 比较项目 | 流密码 | 分组密码 |
|---|
| 加密单位 | 逐位或逐字节加密 | 固定长度的数据块 |
| 加密方式 | 明文与密钥流结合 | 对整个数据块进行变换 |
| 速度 | 通常较快 | 取决于算法和实现 |
| 填充 | 通常不需要 | 某些工作模式需要 |
| 代表算法 | RC4、ChaCha20 | AES、DES |
流密码逐位或逐字节处理数据,分组密码以固定长度的数据块为单位加密。
6. ElGamal 解密:p=17,g=3,x=3,密文 (7,6)
p=17,g=3,x=3先算 Bob 的公钥:
y=gxmodp=33mod17=27mod17=10解密公式:
m=c2(c1x)−1modp代入密文 (c1,c2)=(7,6):
m=6(73)−1mod17其中 73=343≡3(mod17)。求 3 在模 17 下的逆元,因为 3×6=18≡1(mod17),所以 3−1≡6(mod17)。
m=6×6mod17=36mod17=2明文是 m=2。
7. 椭圆曲线 E:y2=x3−2,求另一点
取曲线上的点 P=(3,5),验证 52=27−2=25,成立。
倍点斜率为:
λ=2y13x12=2×53×32=1027新点的横坐标:
x3=λ2−2x1=(1027)2−6=100729−100600=100129新点的纵坐标:
y3=λ(x1−x3)−y1=1027×100171−5=10004617−5=−1000383所以:
P+P=(100129,−1000383)8. ECC 相对 RSA 和 ElGamal 的优势
- 密钥长度短:相同安全强度下,ECC 所需的密钥长度远小于 RSA 和传统 ElGamal。
- 计算效率高:相同安全强度下,ECC 的运算量更小。
- 存储空间小:密钥和数字签名占用的存储空间较少。
- 通信开销小:传输公钥和签名所需的数据量少,适合带宽受限的环境。
- 适用范围广:适合移动设备、物联网和区块链等场景。
最主要的优势是在相同安全强度下密钥短、存储小、通信开销低。
9. RSA 求 d
RSA 中 φ(n)=(p−1)(q−1),d=e−1modφ(n),即 ed≡1(modφ(n))。
(1)p=1,q=11,e=3。
φ(n)=(1−1)(11−1)=0模数为 0,模逆元没有定义;而且 p=1 不是素数,不满足 RSA 的基本要求。所以不存在有效的 d。
(2)p=3,q=41,e=23。
φ(n)=(3−1)(41−1)=2×40=8023d≡1(mod80)因为 23×7=161=2×80+1,所以:
d=7(3)p=5,q=23,e=59。
φ(n)=(5−1)(23−1)=4×22=8859d≡1(mod88)因为 59×3=177=2×88+1,所以:
d=3(4)p=47,q=59,e=17。
φ(n)=(47−1)(59−1)=46×58=266817d≡1(mod2668)因为 17×157=2669=2668+1,所以:
d=157四种情况汇总:
| 情况 | φ(n) | d |
|---|
| 1 | 0 | 不存在 |
| 2 | 80 | 7 |
| 3 | 88 | 3 |
| 4 | 2668 | 157 |
10. RSA 数字签名:(d,n)=(13,51),哈希值 4
已知 d=13,n=51=3×17。
(1)欧拉函数:
φ(n)=(3−1)(17−1)=2×16=32(2)求公钥指数 e:
13e≡1(mod32)因为 13×5=65=2×32+1,所以 e=5,公钥为:
(e,n)=(5,51)(3)计算签名:
S=H(m)dmodn=413mod51利用 44=256≡1(mod51),所以:
413=(44)3×4≡1×4=4即 S=4。
(4)验证签名:
H(m)=Semodn=45mod5145=44×4≡1×4=4还原出的哈希值与本地计算的 H(m)=4 相同,验证成功。
结果汇总:私钥 (13,51),公钥 (5,51),签名 S=4,验证成功。