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

Question

Я реализовал модель атаки 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}
}

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

Answer 1

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

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

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