SEAL (англ. Software-optimized Encryption Algorithm, программно-оптимизированный алгоритм шифрования) — симметричный поточный алгоритм шифрования данных, оптимизированный для программной реализации.

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

Алгоритм считается очень надёжным, очень быстрым^[1] и защищён патентом США № 5454039^[2] с декабря 1993 года.

История

В Ralph C. Merkle) описал рентабельность программно-ориентированных шифров. По его мнению, наиболее эффективными из них были Khufu, FEAL и RC4. Однако постоянно увеличивающиеся потребности клиентов в надежной криптографии требовали поиска новых и доработки старых решений.

Летом Ralph C. Merkle) Khufu, который показался им самым совершенным на тот момент. Они решили добиться лучших характеристик проекта (в основном скорости), сузив круг аппаратуры, на которой возможна его реализация. Выбор был сделан в пользу 32-битных машин минимум с восемью регистрами общего назначения и кэшем не менее 8 Кбайт. В марте 1993 года было принято решение создать блочный шифр, но структура из семейства псевдослучайных функций, разработанная к октябрю того же года, работала быстрее, что склонило разработчиков в к поточному шифрованию. Эта структура состояла из четырех регистров, каждый из которых изменял своего «соседа» в зависимости от таблицы, полученной из ключа. После некоторого количества таких модификаций значения регистров добавляются в ключевую последовательность, которая растет с каждой итерацией до тех пор, пока не достигнет определенной длины. При разработке почти все внимание уделялось внутреннему циклу алгоритма, так как процедуру инициализации регистров и метод генерации таблиц из ключа оказывали незначительное влияние на его защищенность. В окончательном виде проект SEAL 1.0 появился только в декабре 1993 года.

В 1996 году SHA, что сделало их более устойчивыми к криптоанализу.

Описание

При описании алгоритма используются следующие операции и обозначения:

• числа шестнадцатеричной системы счисления начинаются с символов «0x» и используют в записи кроме десятичных цифр символы «a», «b», «c», «d», «e» и «f», которые обозначают десятичные числа от 10 до 15 соответственно;
• под выражением Y t следует понимать циклический сдвиг регистра Y вправо на t бит;
• под выражением Y t следует понимать циклический сдвиг регистра Y влево на t бит;
• операция X Y означает побитовое AND) регистров X и Y;
• операция X Y означает побитовое OR) регистров X и Y;
• операция X Y означает побитовое XOR) регистров X и Y;
• под X Y следует понимать Concatenation) регистров X и Y;
• выражение odd (X) обозначает логическую функцию аргумента X, которая принимает значение ИСТИНА (англ. TRUE) только, если X — чётное число.

Создание таблиц шифрования из ключа

Чтобы избежать потери скорости шифрования на медленных операциях алгоритм использует три таблицы: R, S и T. Эти таблицы вычисляются с помощью процедуры из алгоритма SHA-1 и зависят только от ключа. Заполнение данных таблиц можно описать с помощью функции G, которая из 160-битной строки и 32-битного числа возвращает 160-битное значение .

Введем следующие функции и переменные в зависимости от индекса :

• для установим и
• для установим и
• для установим и
• для установим и

Затем 160-битную строка разбивается на пять 32-битных слов так, что

Также создается шестнадцать 32-битных слов

Затем выполняются финальные вычисления:

Введем функцию где для

Тогда таблицы:

Далее ключ в алгоритме не используется.

Инициализация служебных регистров

Перед генерацией псевдослучайной функции нужно подготовить четыре 32-битовых служебных регистра (, , и ) и четыре 32-битовых слова (, , и ). Их значения определяются из таблиц и , 32-битового числа и некоторого числа в следующей процедуре.

Создание псевдослучайной функции

Для шифрования текста необходимо создать псевдослучайную функцию.

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

Свойства и практическое применение

При разработке этого алгоритма главное внимание отводилось следующим свойствам и идеям:

• использование большой (примерно 2 Kбайта) таблицы T, получаемой из большого 160-битного ключа;
• чередование арифметических операций (сложение и побитовый XOR);
• использование внутреннего состояния системы, которое явно не проявляется в потоке данных (значения n1, n2, n3 и n4, которые изменяют регистры в конце каждой итерации);
• использование отличных друг от друга операций в зависимости от этапа итерации и ее номера.

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

Примечания