c++ - C++ 中的 mantin wep 实现

Question

我已经用 C++ 实现了 2005 年发布的 WEP 攻击的 Mantin 模型。为了检查实现是否正确，我从 RC4 PRG 生成 2^48 个 IV 和它们对应的第 257 个密钥流字节。该算法的复杂度为o(n)。基本上代码的结构如下：

for(loop through n times){
    for(loop through 3 times){}
    for(loop through 256 times){ some code}
    for(loop through 257 times){some code}
}

所以在输入 n = 2^48 时需要很长时间。是正常的还是我错过了什么？我正在使用英特尔 i3 处理器。

Answer 1

是的，这需要一段时间。

考虑一下从 0 计数到 2^48-1 需要什么。这大约是 281 万亿次操作。我的电脑（使用 Intel Core i5-2500K）大约需要 9 秒来运行从 0 到 2^32-1 计数的单线程循环；基于此，计算到 2^48-1 大约需要 164 个 CPU 核心小时，或者在单个 CPU 核心上大约需要一周时间。这还不包括用那个计数器做任何有用的事情所花费的时间。

幸运的是，这个问题很容易并行化。将搜索空间分成块并在不同的 CPU 内核上运行每个块，然后在完成后合并结果。