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



RC4 (2-я часть)


Теперь рассмотрим "перетасовку" байт в массиве M, используя входной ключ.

Здесь получается такая картина - на обработку одного байта массива M необходимо минимум 7 команд, покажем это на примере одной итерации:

xor eax,eax ;в AL будем хранить индекс A

mov ebp,offset Key

mov edi,offset M

...

add al,byte ptr[ebp+i] ;A += Key[i % 16]

mov dl,byte ptr [edi+i] ;Считываем M[i]

add al,dl ;A += M[i]

movzx esi,al

mov bl,byte ptr [edi+esi] ;Считываем M[A]

mov byte ptr [edi+esi],dl

mov byte ptr [edi+i],bl

...


Причем такая конструкция имеет ряд особенностей:

  1. Использование команды MOVZX ESI,AL устраняет следующий конфликт на процессорах Intel: обращение к 32-битному регистру сразу после модификации его младшей (16- или 8-битной) части. В этом случае ко времени выполнения команды добавляется несколько тактов штрафа. Кстати, на процессорах от AMD таких штрафов нет. :)
  2. Конфликты по чтению/записи в одну кэш-линейку процессора.

    Известно, что при обращении к ячейке памяти процессор считывает из памяти (или кэша 2-го уровня) не одну эту ячейку, а целую строку (например, 32 байта), которую и размещает в кэше 1-го уровня. При этом ВСЯ эта строка помечается как доступная либо только для чтения, либо для записи. Поэтому, если прочитать байт по адресу X, а потом записать байт по адресу (X + 1), то несмотря на то, что байт по адресу (X + 1) уже в кэше(!), процессор после выполнения первой команды должен сначала "освободить" всю строку, а лишь потом снова ее загрузить, но уже для записи в нее, что, естественно, приводит к штрафам. Но, т.к. алгоритм формирует равномерное распределение байт, то такие конфликты возникают нечасто.

  3. Возможно, есть еще ряд конфликтов именно по работе с памятью, т.к. такие алгоритмы - это для процессоров не самый "удобный" код :)
  4. В итоге такая конструкция выполняется в среднем за 5 тактов, т.к. все эти команды простые и на процессорах P-II/III от Intel могут декодироваться всеми 3-мя декодерами. Таким образом, декодирование может происходить по 3 команды за такт, что частично компенсирует вышеописанные штрафы.




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