Глава 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, а перестановка является функцией ключа переменной длины . В алгоритме применяются два счетчика, i и j, с нулевыми начальными значениями.

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

i = (i + 1) mod 256

j = (j + S) mod 256

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

t = (Si + Sj) mod 256

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

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

for i = 0 to 255:

j = (j + Si + K) mod 256 поменять местами Si и Sj

И это все. RSADSI утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу , что, по-видимому, в нем нет никаких коротких циклов, и что он в высокой степени нелинеен . (Опубликованных криптоаналических результатов нет. RC4 может находиться в примерно 21700 (256! * 2562) возможных состояний: невероятное число.) 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].

17.2 SEAL

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

Семейство псевдо случайных функций

Особенностью SEAL является то, что он в действительности является не традиционным потоковым шифром, а представляет собой семейство псевдослучайных функций. При 160-битовом ключе k и 32-битовом n SEAL растягивает n в L-битовую строку k(n). L может принимать любое значение, меньшее 64 Кбайт. SEAL, по видимому, использует следующее свойство: если k выбирается случайным образом , то k(n) должно быть вычислительно неотличимо от случайной L-битовой функции n.

Практический эффект того, что SEAL является семейством псевдослучайных функций, состоит в том, что он удобен в ряде приложений, где неприменимы традиционные потоковые шифры . Используя большинство потоковых шифров, вы создаете однонаправленную последовательность битов : единственным способом определить i-ый бит, зная ключ и позицию i, является генерирование всех битов вплоть до i-ого. Отличие семейства псевдослучайных функций состоит в том, что вы можете легко получить доступ к любой позиции потока ключей . Это очень полезно.

Представим себе, что вам нужно "закрыть" жесткий диск. Вы хотите зашифровать каждый 512-байтовый сектор. Используя семейство псевдослучайных функций, подобное SEAL, содержимое сектора n можно зашифровать, выполнив его XOR с k(n). Это то же самое, как если бы была выполнена операция XOR всего диска с длинной псевдослучайной функцией , и любая часть этой длинной строки может быть независимо вычислена без всяких проблем.

Семейство псевдослучайных функций также упрощает проблему синхронизации, встречающуюся в ста н-дартных потоковых шифрах. Предположим, что вы посылаете шифрованные сообщения по каналу, в котором данные иногда теряются. С помощью семейства псевдослучайных функций можно зашифровать ключом k n-ое передаваемое сообщение, xn, выполнив XOR xn and k(n). Получателю не нужно хранить состояние шифра для восстановления xn, ему не приходится беспокоиться и о потерянных сообщениях, влияющих на процесс деши ф-рирования.

Описание SEAL

Внутренний цикл SEAL показан на 16th. Алгоритм управляется тремя полученными из ключа таблицами: R, S и T. Предварительная обработка отображает ключ k на эти таблицы с помощью процедуры, основанной на SHA (см. раздел 18.7). 2-килобайтная таблица T представляет собой S-блок 9*32 битов.

Рис. 17-1. Внутренний цикл SEAL.

SEAL также использует четыре 32-битовых регистра, A, B, C и D, начальные значения которых определяются n и полученными по k таблицами R и T. Эти регистры изменяются в ходе итераций, каждая из которых с о-стоит из восьми этапов. На каждом этапе 9 битов первого регистра (все равно A, B, C или D) используются в качестве индекса таблицы T. Затем выбранное из T значение складывается со вторым регистром (снова одному из A, B, C или D) или объединяется с его содержимым с помощью XOR. Потом первый регистр циклически сдвигается на 9 позиций. На некоторых этапах второй регистр далее модифицируется с помощью сложения или XOR с содержимым первого регистра (уже сдвинутым) . После 8 таких этапов A, B, C и D добавляются к потоку ключей, при этом каждый из них маскируется сложением или XOR с определенным словом из S. Итерация завершается прибавлением к A и C дополнительных значений, зависящих от n, n1, n2, n3, n4, выбор конкретного значения определяется четностью номера итерации . По видимому, при разработке этой схемы главными были следующие идеи:

1.Использование большого, секретного, получаемого из ключа S-блока (7).

2.Чередующиеся некоммутируемые арифметические операции (сложение и XOR).

3.Использование внутреннего состояния, поддерживаемого шифром, которое не проявляется явно в п о-токе данных (значения ni, которые модифицируют A и C в конце каждой итерации).

4.Изменение функции этапа в соответствии с номером этапа и изменение функции итерации в соотве т-ствии с номером итерации.

Для шифрования каждого байта текста SEAL требует около пяти элементарных операций. На 50-мегагерцовом процессоре i486 он работает со скоростью 58 Мбит/с. SEAL возможно является самым быстрым из описанных в этой книге .

С другой стороны SEAL должен выполнить предварительную обработку, заполняя внутренние таблицы . Размер этих таблиц составляет примерно 3 Кбайт, а для их расчета нужно примерно 200 вычислений SHA. Таким образом, SEAL не подходит для тех случаев, когда не хватает времени для обработки ключа или памяти для хранения таблиц.

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

SEAL достаточно новый алгоритм, ему еще предстоит пройти через горнило открытого криптоанализа . Это вызывает определенную настороженность. Однако SEAL кажется хорошо продуманным алгоритмом. Его особенности, в конечном счете, наполнены смыслом . К тому же Дон Копперсмит считается лучшим криптоанал и-тиком в мире.

Патенты и лицензии

SEAL запатентован [380]. По поводу лицензирования нужно обращаться к Управляющему по лицензиям IBM ( Director of Licenses, IBM Corporation, 500 Columbus Ave., Thurnwood, NY, 10594 ).