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

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

17.2 SEAL

SEAL - это программно эффективный потоковый шифр, разработанный в IBM Филом Рогэвэем (Phil Rogaway) и Доном Копперсмитом (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 и Г. Предварительная обработка отображает ключ k на эти таблицы с помощью процедуры, основанной на SHA (см. раздел 18.7). 2-килобайтная таблица T представляет собой S-блок 9*32 битов.

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

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

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

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

3. Использование внутреннего состояния, поддерживаемого шифром, которое не проявляется явно в п о-токе данных (значения n,, которые модифицируют А и 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 ).

17.3 WAKE

WAKE - сокращение от Word Auto Key Encryption (Автоматическое шифрование слов ключом)- это алгоритм, придуманный Дэвидом Уилером (David Wheeler) [1589]. Он выдает поток 32-битовых слов, которые с помощью XOR могут быть использованы для получения шифротекста из открытого текста или открытого текста из шифротекста. Это быстрый алгоритм.

WAKE работает в режиме CFB, для генерации следующего слова ключа используется предыдущее слово шифротекста. Алгоритм также использует S-блок из 256 32-битовых значений. Этот S-блок обладает одним особым свойством: Старший байт всех элементов представляет собой перестановку всех возможных байтов, а 3 младших байта случайны.

Сначала по ключу сгенерируем элементы S-блока, Si. Затем проинициализируем четыре регистра с использованием того же или иного ключа: а0, b0, c0 и d0. Для генерации 32-битового слова потока ключей Ki.

Ki = di

Слово шифротекста Ci представляет собой XOR слова открытого текста Pi с Ki. Затем обновим четыре регистра:

ai+1 = M(ai,di)

= M(bi,ai+1) Ci+1 = M(Ci,bi+1)

= M(di,Ci+1) Функция M представляет собой

M(xy) = (x + y) >> 8 е S(x + у)л255

Схема алгоритма показана на 15-й. Знак >> обозначает обычный, не циклический сдвиг вправо . Младшие 8 битов x+y являются входом S-блока. Уилер приводит процедуру генерации S-блока, но на самом деле она неполна. Будет работать любой алгоритм генерации случайных байтов и случайной перестановки .

Рис. 17-2. WAKE.

Самым ценным качеством WAKE является его скорость. Однако он чувствителен к вскрытию с выбранным открытым текстом или выбранным шифротекстом . Этот алгоритм использовался в предыдущей версии антив и-русной программы д-ра Соломона.

17.4 Сдвиговые регистры с обратной связью по переносу

Сдвиговый регистр с обратной связью по переносу, или FCSR (feedback with carry shift register), похож на LFSR. В обоих есть сдвиговый регистр и функция обратной связи, разница в том, что в FCSR есть также регистр переноса (см. 14-й). Вместо выполнения XOR над всеми битами отводной последовательности эти биты скла-