2020-2021:teams:alchemist:weekly_digest_12
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:alchemist:weekly_digest_12 [2020/08/28 17:25] hardict [龙鹏宇 Hardict] |
2020-2021:teams:alchemist:weekly_digest_12 [2020/08/28 17:26] (当前版本) hardict [龙鹏宇 Hardict] |
||
|---|---|---|---|
| 行 126: | 行 126: | ||
| 那么$x_1=x_2$可以理解为对$x_1$的$Hash$在${x_2}$中寻找一次$原像碰撞$ | 那么$x_1=x_2$可以理解为对$x_1$的$Hash$在${x_2}$中寻找一次$原像碰撞$ | ||
| - | 将设我们对$x_1$进行哈希了$D$次，我们可以利用*生日攻击*知道$D=2^{\frac{N}{2}}$最优（或者利用期望耗费为$D+\frac{2^N}{D}$分析） | + | 将设我们对$x_1$进行哈希了$D$次，我们可以利用//生日攻击//知道$D=2^{\frac{N}{2}}$最优（或者利用期望耗费为$D+\frac{2^N}{D}$分析） |
| 于是对于原题我们得到一种想法：对${x_1}$构建大小为$2^{\frac{N}{2}}$的哈希表，$x_3,x_4$随便生成，遍历${x_2}$寻找碰撞$x_1=x_2 \oplus x_3 \oplus x_4$，复杂度为$O(2^{\frac{N}{2}})$，会$TLE$ | 于是对于原题我们得到一种想法：对${x_1}$构建大小为$2^{\frac{N}{2}}$的哈希表，$x_3,x_4$随便生成，遍历${x_2}$寻找碰撞$x_1=x_2 \oplus x_3 \oplus x_4$，复杂度为$O(2^{\frac{N}{2}})$，会$TLE$ | ||
2020-2021/teams/alchemist/weekly_digest_12.1598606732.txt.gz · 最后更改: 2020/08/28 17:25 由 hardict
