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

Особенностью 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-ое передаваемое сообщение, x_n, выполнив XOR x_n and k(n). Получателю не нужно хранить состояние шифра для восстановления x_n, ему не приходится беспокоиться и о потерянных сообщениях, влияющих на процесс дешифрирования.

Описание SEAL

Внутренний цикл SEAL показан на Рис. 17-1. Алгоритм управляется тремя полученными из ключа таблицами: 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, n₁, n₂, n₃, n₄, выбор конкретного значения определяется четностью номера итерации. По видимому, при разработке этой схемы главными были следующие идеи:

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

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).

WAKE

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

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

Сначала по ключу сгенерируем элементы S-блока, S_i. Затем проинициализируем четыре регистра с использованием того же или иного ключа: a₀, b₀, c₀ и d₀. Для генерации 32-битового слова потока ключей K_i.

K_i= d_i

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

a_i+1 = M(a_i,d_i)

b_i+1 = M(b_i,a_i+1)

c_i+1 = M(c_i,b_i+1)

d_i+1 = M(d_i,c_i+1)

Функция M представляет собой

M(x,y) = (x + y) >> 8 Å S_{(x + y)^255}

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

Рис. 17-2. WAKE.

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