17. Примеры поточных шифров, использующих аддитивные генераторы:

• очень эффективны - их результатом являются слова, а не случайные биты.

• Сами по себе они небезопасны, но могут использоваться в качестве составных блоков для безопасных генераторов.

• Начальное состояние генератора представляет из собой массив n-битовых слов:

X(1),X(2),....,X(m).

• Первоначальное состояние и является ключом.

• i-e слово генератора:

X(i)=(X(i-a)+X(i-b)+X(i-c)+...+X(i-m)) mod 2n.

• При правильном выборе a, b, c, ...,m период этого генератора не меньше 2n-1.

Примеры потоковых шифров Mush

• представляет собой взаимно прореживающий генератор.

Пусть A, B - аддитивные генераторы.

• Если бит переноса А установлен тактируется B.

• Если бит переноса B установлен тактируется A.

• Тактируем A и при переполнении устанавливаем бит переноса.

• Тактируем B и при переполнении устанавливаем бит переноса.

• Окончательным выходом является XOR выходов A и B.

• Можно использовать следующие генераторы:

A(i)=(A(i-55)+ A(i-24)) mod 232 ;

B(i)=(B(i-52)+ B(i-19)) mod 232.

• В среднем, для генерации одного выходного слова нужно три итерации генератора.

Gifford

• Алгоритм использует единственный 8-байтовый регистр:

b0, b1,...., b7.

• Ключом является начальное состояние регистра.

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

• Перемножим полученные числа, получая 32-битовое число.

• Третьим слева байтом и будет k.

• Для обновления регистра возьмем b1 и сдвинем вправо ''с приклеиванием'' на 1 бит следующим образом: крайний левый бит одновременно и сдвигается, и остается на месте.

• Возьмем b7 и сдвинем его на один бит влево, в крайней правой позиции должен появиться 0.

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

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

PKZIP

• Использует три 32-битовых переменных:

• К0 = 305419896; К1 = 591751049; К2 = 878082192.

• Используется 8-битовый ключ К3, полученный из К2.

Алгоритм (в стандартной нотации С):

Сi=Рi^K3;

K0=сrc32 (K0,Pi);

K1=K1+ (K0 & 0х000000ff);

K1= K1*134775813 + 1;

K2 = сrc32 (K2, K1 >> 24);

K3 = ((K2|2)*((K2 | 2)^1))>>8.

Функция crc32 берёт своё предыдущее значение и байт, выполняет их XOR и вычисляет следующее значение с помощью многочлена CRC, определённого 0xcdb88320.

На практике 256-элементная таблица может быть рассчитана заранее, и вычисление crc32 превращается в

crc32(a,b)=(a<<8)^ table [(a& 0xff) xor b].

Для шифрования потока открытого текста сначала для обновления ключей зациклим байты ключа в алгоритме шифрования.

Полученный шифротекст на этом этапе игнорируется.

Затем побайтно зашифруем открытый текст. Открытому тексту предшествуют 12 случайных байт, но это не важно.

Безопасность этого алгоритма не слишком велика. Для вскрытия нужно от 40 до 2000 байтов известного открытого текста.Если в сжатом файле используются стандартные заголовки, то вскрытие становится ещё прощё.