Криптография - статьи



RC4 (2-я часть) - часть 2


А на процессорах от AMD цифра в 5 тактов получается из-за того, что некоторые из этих команд не зависят друг от друга и после декодирования следующая команда начинает выполняться, когда предыдущая еще заканчивает свое исполнение в конвейере.

Итого на весь алгоритм RC4 уходит: 5 x 256 = примерно 1280-1300 тактов.

Конечно же, подразумевается, что никаких циклов нет и код весь "развернут".

Вроде бы ничего с эти поделать уже нельзя, но пытливый ум подсказывает, что и здесь можно "рыбку половить". ;)

И действительно - рассмотрим ту часть кода, где вычисляемый индекс A суммируется с байтом из массива Key.

Индекс - это же один байт(!), который суммируется с текущим байтом M[i].

А затем суммируется с байтом из массива Key.

А если сразу суммировать два байта (одной командой) для 2-х разных ключей и, соответственно, 2-х разных паролей не в 8-битном регистре, а в 16-битном? Сказано - сделано.

В результате скорость упала.

Да-а-а, значит прирост от этого не перекрыл увеличение "накладных расходов" из-за того, что теперь в программе формируется два массива Z, два массива M и пр. Плюс штрафы от использования 16-битных команд в 32-битном коде.

Ну что ж, а если одновременно 4 байта для 4-х паролей? ;)

Та-а-ак, здесь уже относительно начального (однопарольного) варианта есть прирост производительности на 3-5%.

А если еще "шире"? :)

"Конечно же, MMX!" - скажете Вы и будете правы! :))

И вот мы приходим к тому варианту, который и был реализован в PWLInside

и дал прирост скорости относительно начального варианта на 20-25%. Все просто:

  • Формируем 8 массивов M, которые располагаются в памяти таким образом:

    - 0-й байт 1-го массива

    - 0-й байт 2-го массива

    ...

    - 0-й байт 8-го массива

    - 1-й байт 1-го массива

    - 1-й байт 2-го массива

    ...

    - 1-й байт 8-го массива

    и так далее.

  • Формируем 8 паролей, идущих "подряд" при переборе выбранным алфавитом.

  • На основе этих восьми паролей через вызов MD5 формируем 8 массивов Key в таком же порядке:




    Содержание  Назад  Вперед