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

       

RC4 (1-я часть)


1. Сразу же бросается в глаза инициализация массива значениями от 0 до 255, которое происходит при каждом новом значении ключа (т.е. фактически при каждом новом пароле). Как же можно сделать ее более эффективной?

Выход есть - инициализировать массив не побайтно (256 команд), а, например, используя 32-битные регистры процессора, по 4 байта за 64 команды - и действительно, выигрыш по времени будет в 4 раза (конечно же, если массив M выровнен минимум по границе DWORD'a). А есть ли еще более "широкие" регистры, чтобы за одну команду "махом" записывать бОльшее кол-во байт? Регистры FPU отпадают, т.к. операции с ними выполняются очень долго, остаются, конечно же, MMX-регистры:

.DATA

qwInit DQ 0706050403020100h

qwAdd DQ 0808080808080808h

...

.CODE

mov edi,offset M+128

movq mm0,qword ptr [qwInit]

movq mm1,qword ptr [qwAdd]

movq [qword ptr edi-128],mm0

paddb mm0,mm1

movq [qword ptr edi-120],mm0



paddb mm0,mm1

movq [qword ptr edi-112],mm0

...

paddb mm0,mm1

movq [qword ptr edi+112],mm0

paddb mm0,mm1

movq [qword ptr edi+120],mm0

Чтобы не писать 31 одинаковый фрагмент кода, гораздо проще использовать зарезервированный макрос Ассемблера IRP, тогда последние строки кода можно заменить на следующую конструкцию:

IRP i,<-15,-14, ... ,14,15>

paddb mm0,mm1

   movq [qword ptr edi+(i*8)],mm0

ENDM

Итого получаем - на инициализацию массива из 256 байт затрачиваем 66 команд процессора, которые выполняются за ~35-40 тактов, т.к. команды PADDB и MOVQ выполняются синхронно.

Нетрудно догадаться, ЧТО наворотил бы на месте этого цикла любой компилятор С, если этот код писать не на Асме. ;)

У читателя, наверное, возник вопрос - почему мы инициализируем EDI не на начало массива M, а на его середину?

Просто дело в том, что при таком варианте программы дополнительное смещение к EDI будет приводить к увеличению длины команды MOVQ всего на один байт (знаковый диапазон -128...+127) и команда получает длину в 4 байта. А если, к примеру, прибавить к EDI +256, то смещение будет расширено до DWORD'a и длина команды увеличится до 7 байт. Использование же более коротких команд является предпочтительным, т.к. идет более "плотное" заполнение буфера предвыборки команд и более оптимальное их декодирование процессорами.

И еще - вдумчивый читатель скажет, что есть ведь еще более "широкие" XMM-регистры - те, которые используются в наборах команд SSE (которые, кстати, поддерживают и Athlon'ы) и SSE2 от Intel. Используя их, можно оперировать с памятью блоками по 16 байт за такт!

Действительно, это так. В PWLInside не была включена поддержка SSE только по причине недостаточного распространения таких процессоров в то время, когда создавалась программа. Вполне возможно, что в следующей версии программы поддержка SSE будет присутствовать.



Содержание раздела