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

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: S₀, S₁, . . . , S₂₅₅. Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины. В алгоритме применяются два счетчика, iи j, с нулевыми начальными значениями.

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

i = (i + 1) mod 256

j = (j + S_i) mod 256

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

t= (S_i + S_j) mod 256

K= S_t

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

Также несложна и инициализация S-блока. Сначала заполним его линейно: S₀= 0, S₁= 1, . . . , S₂₅₅= 255. Затем заполним ключом другой 256-байтовый массив, при необходимости для заполнения всего массива повторяя ключ: K₀, K₁, . . . , K₂₅₅.Установим значение индекса j равным 0. Затем:

for i= 0 to 255:

j= (j + S_i+ K_i) mod 256

поменять местами S_iи S_j

И это все. RSADSI утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу, что, по-видимому, в нем нет никаких коротких циклов, и что он в высокой степени нелинеен. (Опубликованных криптоаналических результатов нет. RC4 может находиться в примерно 2¹⁷⁰⁰ (256! * 256²) возможных состояний: невероятное число.) S-блок медленно изменяется при использовании: iобеспечивает изменение каждого элемента, а 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 в коммерческом продукте. Возможно им и не удастся выиграть процесс, но почти наверняка для другой компании дешевле купить лицензию, чем судиться.

RC4 входит в десятки коммерческих продуктов, включая Lotus Notes, AOCE компании Apple Computer и and Oracle Secure SQL. Этот алгоритм также является частью спецификации Сотовой цифровой пакетной передачи данных (Cellular Digital Packet Data) [37].

SEAL

SEAL - это программно эффективный потоковый шифр, разработанный в IBM Филом Рогэвэем (Phil Rogaway) и Доном Копперсмитом (Don Coppersmith) [1340]. Алгоритм оптимизирован для 32-битовых процессоров: Для нормальной работы ему нужно восемь 32-битовых регистров и кэш-память на несколько килобайт. Чтобы избежать влияния использования медленных операций SEAL выполняет ряд предварительных действий с ключом, сохраняя результаты в нескольких таблицах. Эти таблицы используются для ускорения шифрования и дешифрирования.