алгоритм — реализация wentin в переполнении стека
Я реализовал модель атаки 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.
Решение
Да, это займет некоторое время.
Посмотрим, что нужно, чтобы просто сосчитать от 0 до 2 ^ 48-1. Это примерно 281 триллион операций. Моему компьютеру (использующему Intel Core i5-2500K) потребовалось около 9 секунд, чтобы запустить однопоточный цикл с числом от 0 до 2 ^ 32-1; Исходя из этого, подсчет до 2 ^ 48-1 занял бы приблизительно 164 процессорных часа процессора или около недели на одном ядре процессора. Это не считает время, которое потребуется, чтобы сделать что-нибудь полезное с этим счетчиком.
К счастью, проблема легко распараллеливается. Разделите пространство поиска на куски и запустите каждый кусочек на отдельном ядре ЦП, а затем объедините результаты, когда закончите.
Другие решения