Сброс

Рис. 16-17. Gifford.

Для генерации байта ключа k, объединим b0 и b1, а также объединим b4 и b7. Перемножим полученные числа, получая 32-битовое число. Третьим слева байтом и будет k,.

Для обновления регистра возьмем b1 и сдвинем вправо "с приклеиванием" на 1 бит следующим образом: крайний левый бит одновременно и сдвигается, и остается на месте . Возьмем b7 и сдвинем его на один бит влево, в крайней правой позиции должен появиться 0 . Выполним XOR измененного b1, измененного b7 и b0. Сдвинем первоначальный байт регистра на 1 бит вправо и поместим этот байт в крайнюю левую позицию .

В течение всего времени использования этот алгоритм оставался безопасным, но он был взломан в 1994 году [287]. Оказалось, что многочлен обратной связи не был примитивным и, таким образом, мог быть вскрыт .

16.11 Алгоритм M

Это название дано Кнутом [863]. Алгоритм представляет собой способ объединить несколько псевдослучайных потоков, увеличивая их безопасность. Выход одного генератора используется для выбора отстающего в ы-хода другого генератора [996, 1003]. На языке C:

#define ARR SIZE (8192) /* например - чем больше, тем лучше */ static unsigned char delay[ ARRSIZE ] ; unsigned char prngA( void ) long prngB( void ) ; void init algM( void ) { long i ;

for ( i = 0 ; i < ARR SIZE ; i++ ) delay[i] = prngA() ; } /* lnlt algM */ unsigned char alglM( void ) {

long j,v ;

j = prngB() % ARR SIZE ; /* получить индекс delay[]*/ v = delay[j] ; /* получить возврашаемое значение */ delay[j] = prngA() ; /* заменить его */ return ( v ) ; } /* algM */

Смысл состоит в том, что если prngA - действительно случайно, невозможно ничего узнать о prngB (и, следовательно, невозможно выполнить криптоанализ ). Если prngA имеет такой вид, что его криптоанализ может быть выполнен только, если его выход доступен в свою очередь (т.е., только если сначала был выполнен крип-

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

16.12 PKZIP

Алгоритм шифрования, встроенный в программу сжатия данных PKZIP, был разработан Роджером Щлафлы (Roger Schlafly). Это потоковый шифр, шифрующий данные побайтно . По крайней мере этот алгоритм используется в версии 2.04g. Я не могу ничего сказать о более поздних версиях, но если не было сделано никаких з а-явлений об обратном, можно считать с большой вероятностью, что алгоритм не изменился . Алгоритм использует три 32-битовых переменных, инициализированных следующим образом :

K0 = 305419896

K1 =591751049

K2 = 878082192

Используется 8-битовый ключ K3, полученный из K2. Вот этот алгоритм (в стандартной нотации C):

Ko= crc32 (Ko, Pi)

Ki= Ki+ (Ko & 0x000000ff)

K1 = K1*134775813 + 1

K2 = crc32 (K2, Ki >> 24)

K3 = ((K2 2)* ((K2 2)1)) >> 8

Функция crc32 берет свое предыдущее значение и байт, выполняет их XOR и вычисляет следующее значение с помощью многочлена CRC, определенного 0xedb88320. На практике 256-элементная таблица может быть рассчитана заранее, и вычисление crc32 превращается в:

crc32 (a, b) = (a >> 8) table [(a & 0xff) е b ]

Таблица рассчитывается в соответствии с первоначальным определением crc32: table [i] = crc32 (i, 0)

Для шифрования потока открытого текста сначала для обновления ключей зациклим байты ключа в алг о-ритме шифрования. Полученный шифротекст на этом этапе игнорируется. Затем побайтно зашифруем открытый текст. Открытому тексту предшествуют двенадцать случайных байтов, но это на самом деле неважно . Дешифрирование похоже на шифрование за исключением того, что во втором действии алгоритма вместо Pi используется Ci.

Безопасность PKZIP

К сожалению она не слишком велика . Для вскрытия нужно от 40 до 2000 байтов известного открытого те к-ста, временная сложность вскрытия составит около 227 [166]. На вашем персональном компьютере это можно сделать за несколько часов. Если в сжатом файле используются какие-нибудь стандартные заголовки, получ е-ние известного открытого текста не представляет собой проблемы . Не используйте встроенное в PKZIP шифрование.

Глава 17

Другие потоковые шифры и генераторы настоящих случайных последовательностей

17.1 RC4

RC4 - это потоковый шифр с переменным размером ключа, разработанный в 1987 году Роном Ривестом для RSA Data Security, Inc. В течение семи лет он находился в частной собственности, и подробное описание алгоритма предоставлялось только после подписания соглашения о неразглашении .

В сентябре 1994 кто-то анонимно опубликовал исходный код в списке рассылки "Киберпанки" (Cypherpunks). Он быстро распространился в телеконференнции Usenet sci.crypt и через Internet по различным ftp-серверам во всем мире. Обладатели легальных копий RC4 достоверность этого кода. RSA Data Security, Inc. попыталась загнать джинна обратно в бутылку, утверждая, что несмотря на опубликование алгоритм остается торговым секретом, было слишком поздно . С тех пор алгоритм обсуждался и изучался в Usenet, распространялся на конференциях и служил в качестве учебного пособия на курсах по криптографии .

Описывать RC4 просто. Алгоритм работает в режиме OFB: поток ключей не зависит от открытого текста. Используется S-блок размером 8*8: S0, S1, . . . , S255. Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины . В алгоритме применяются два счетчика, , и j, с нулевыми начальными значениями.

Для генерации случайного байта выполняется следующее :

= + 1) mod 256

j = (j + Si) mod 256

поменять местами Si и Sj

t = (Si + Sj) mod 256

K = St

Байт K используется в операции XOR с открытым текстом для получения шифротекста или в операции XOR с шифротекстом для получения открытого текста. Шифрование выполняется примерно в 10 раз быстрее, чем

DES.

Также несложна и инициализация S-блока. Сначала заполним его линейно: S0 = 0, S1 = 1, . . . , S255 = 25 5. Затем заполним ключом другой 256-байтовый массив, при необходимости для заполнения всего массива повторяя ключ: K0, K1, . . . , K255. Установим значение индекса j равным 0. Затем:

for , = 0 to 255:

j = (/ + S, + K,) mod 256

поменять местами S, и Sj

И это все. RSADSI утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу , что, по-видимому, в нем нет никаких коротких циклов, и что он в высокой степени нелинеен . (Опубликованных криптоаналических результатов нет. RC4 может находиться в примерно 21700 (256! * 2562) возможных состояний: невероятное число.) S-блок медленно изменяется при использовании: , обеспечивает изменение каждого элемента, а j - что элементы изменяются случайным образом. Алгоритм настолько несложен, что большинство программистов могут закодировать его просто по памяти .

Эту идею можно обобщить на S-блоки и слова больших размеров. Выше была описана 8-битовая версия RC4. Нет причин, по которым нельзя бы было определить 16-битовый RC4 с 16*16 S-блоком (100 K памяти) и 16-битовым словом. Начальная итерация займет намного больше времени - для сохранения приведенной схемы нужно заполнить 65536-элементный массив - но получившийся алгоритм должен быть быстрее .

RC4 с ключом длиной не более 40 битов обладает специальным экспортным статусом (см. раздел 13.8). Этот специальный статус никак не влияет на безопасность алгоритма, хотя в течение многих лет RSA Data Security, Inc. намекало на обратное. Название алгоритма является торговой маркой, поэтому каждый, кто напишет собс т-венный код, должен назвать его как-то иначе . Различные внутренние документы RSA Data Security, Inc. до сих пор не были опубликованы [1320, 1337].

Итак, какова же ситуация вокруг алгоритма RC4? Он больше не является торговым секретом, поэтому кто угодно имеет возможность воспользоваться им . Однако RSA Data Security, Inc. почти наверняка возбудит дело против каждого, кто применит нелицензированный RC4 в коммерческом продукте. Возможно им и не удастся