SEAL (криптографический алгоритм)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Схема алгоритма SEAL

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

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

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

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

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

Эта структура состояла из четырёх регистров, каждый из которых изменял своего «соседа» в зависимости от таблицы, полученной из ключа. После некоторого количества таких модификаций значения регистров добавляются в ключевую последовательность, которая растет с каждой итерацией до тех пор, пока не достигнет определённой длины.

При разработке почти все внимание уделялось внутреннему циклу алгоритма, так как процедура инициализации регистров и метод генерации таблиц из ключа оказывали незначительное влияние на его защищенность. В окончательном виде проект SEAL 1.0 появился только в декабре 1993 года.

В 1996 году Хелен Хандшух и Henri Gilbert[англ.] описали атаки на упрощенную версию SEAL 1.0 и на сам SEAL 1.0. Им потребовалось текстов, каждый длиной в четыре 32-битных слова, чтобы найти зависимость псевдослучайной функции от ключа. В результате, в следующих версиях алгоритма SEAL 3.0 и SEAL 2.0 были сделаны некоторые доработки и изменения. Например, в версии 1.0 каждая итерация с ключевой последовательностью завершалась модификацией только двух регистров, а в версии 3.0 — модифицировались все четыре. Ещё SEAL 3.0 и SEAL 2.0 использовали для генерации таблиц алгоритм SHA-1 (англ. Secure Hash Algorithm-1) вместо первоначального SHA, что сделало их более устойчивыми к криптоанализу.

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

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

[править | править код]

Чтобы избежать потери скорости шифрования на медленных операциях алгоритм использует три таблицы: 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 МГц и является одним из самых быстрых шифров.

Примечания

[править | править код]
  1. P.Rogaway, D.Coppersmith. A Software-Optimized Encryption Algorithm. — 1998. Архивировано 5 декабря 2013 года.
  2. U.S. Patent 5 454 039 «Software-efficient pseudorandom function and the use thereof for encryption»
  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 446—448. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  • P.Rogaway, D.Coppersmith. A Software-Optimized Encryption Algorithm. — 1998.
  • Хелен Хандшух, H.Gilbert[англ.]. -Cryptanalysis of the SEAL Encryption Algorithm. — 1997.