реализация mantin wep в C++

Question

Я реализовал модель Mantin WEP-атаки, опубликованную в 2005 году в C++. Чтобы проверить, правильно ли реализована реализация, я генерирую 2^48 IV и их соответствующий 257-й байтовый поток от RC4 PRG. Сложность алгоритма - 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} 
} 

так, а положить п = 2^48, что оно принимает очень много времени. Является ли это нормальным я или что-то упускаю? Я использую процессор Intel i3.

Answer 1

Да, это займет некоторое время.

Рассмотрите, что нужно, чтобы просто посчитать от 0 до 2^48-1. Это примерно 281 трлн операций. Мой компьютер (с использованием Intel Core i5-2500K) занял около 9 секунд для запуска однопоточного цикла, который насчитывает от 0 до 2^32-1; на основе этого, считая до 2^48-1, потребуется примерно 164 ядра процессора или около недели на одном ядре процессора. Это не учитывает время, которое потребуется, чтобы сделать что-нибудь полезное для этого счетчика.

К счастью, проблема легко распараллеливается. Разделите пространство поиска на куски и запустите каждый кусок на другом ядре ЦП, затем слейте результаты, когда закончите.