482.一个输出杂凑值长度为n比特的理想杂凑函数,碰撞攻击的复杂度是( )。

　O(2^n)

　O(2^(n/2))

　O(2^(3n/4))

　O(n)

答案解析

正确答案：B

解析：

好的，我们来详细解析这道题。 ### 题目背景题目讨论的是理想杂凑函数（哈希函数）在碰撞攻击中的复杂度。碰撞攻击是指找到两个不同的输入，使得它们通过哈希函数后得到相同的输出（即哈希值）。 ### 选项解析 1. **A. O(2^n)** - 这个复杂度表示需要尝试 \(2^n\) 次才能找到碰撞。这是最坏的情况，即完全随机地尝试所有可能的输入，直到找到一对碰撞。但实际上，由于生日悖论的存在，这个复杂度过高。 2. **B. O(2^(n/2))** - 这个复杂度是基于生日悖论的。生日悖论指出，在一个有 \(N\) 个可能结果的系统中，只需要大约 \(\sqrt{N}\) 次尝试就能找到一对碰撞。对于 \(n\) 比特的哈希值，总共有 \(2^n\) 种可能的输出，因此找到碰撞的复杂度是 \(O(2^{n/2})\)。 3. **C. O(2^(3n/4))** - 这个复杂度介于 \(O(2^n)\) 和 \(O(2^{n/2})\) 之间，但没有理论依据支持它作为碰撞攻击的复杂度。 4. **D. O(n)** - 这个复杂度表示线性时间复杂度，即随着输入长度的增加，复杂度线性增加。这显然不符合实际情况，因为碰撞攻击的复杂度与输出长度有关，而不是输入长度。 ### 为什么选择 B 根据生日悖论，对于一个输出长度为 \(n\) 比特的哈希函数，找到碰撞的复杂度是 \(O(2^{n/2})\)。这是因为在一个有 \(2^n\) 种可能输出的系统中，只需要大约 \(\sqrt{2^n} = 2^{n/2}\) 次尝试就能找到一对碰撞。 ### 示例假设我们有一个 16 比特的哈希函数，总共有 \(2^{16} = 65536\) 种可能的输出。根据生日悖论，找到碰撞的复杂度是 \(O(2^{16/2}) = O(2^8) = 256\)。这意味着我们只需要尝试大约 256 次就能找到一对碰撞，而不是 65536 次。

482.一个输出杂凑值长度为n比特的理想杂凑函数,碰撞攻击的复杂度是( )。

答案解析

相关知识点：

相关题目

482.一个输出杂凑值长度为n比特的理想杂凑函数,碰撞攻击的复杂度是( )。

答案解析

相关知识点：

相关题目

选择练习分段

选择练习章节

组卷设置

考试记录