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

Question

我已经用 C++ 实现了 2005 年发布的 WEP 攻击的 Mantin 模型。为了检查实现是否正确，我从 RC4 PRG 生成了 2^48 个 IV 及其相应的第 257 个 key 流字节。该算法的复杂度为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 万亿次操作。我的电脑(使用英特尔酷睿 i5-2500K)运行一个从 0 到 2^32-1 的单线程循环需要大约 9 秒；基于此，计算到 2^48-1 大约需要 164 个 CPU 核心小时，或者在单个 CPU 核心上大约需要一周。这还不包括使用该计数器执行任何有用操作所需的时间。

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