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

Особенностью 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 не подходит для тех случаев, когда не хватает времени для обработки ключа или памяти для хранения таблиц.