SEAL ( англ. S oftware-optimized E ncryption Al gorithm , программно-оптимизированный алгоритм шифрования) — симметричный поточный алгоритм шифрования данных , оптимизированный для программной реализации.

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

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

История

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

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

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

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

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

Описание

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

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

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

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

Введем следующие функции и переменные в зависимости от индекса ${\displaystyle t}$ :

• для ${\displaystyle 0\leq t\leq 19}$ установим ${\displaystyle K_{t}={\mbox{0x}}5a827999}$ и ${\displaystyle f_{t}(B,C,D)=(B\And C)\lor ({\bar {B}}\And D);}$
• для ${\displaystyle 20\leq t\leq 39}$ установим ${\displaystyle K_{t}={\mbox{0x}}6ed9eba1}$ и ${\displaystyle f_{t}(B,C,D)=B\oplus C\oplus D;}$
• для ${\displaystyle 40\leq t\leq 59}$ установим ${\displaystyle K_{t}={\mbox{0x}}8f1bbcdc}$ и ${\displaystyle f_{t}(B,C,D)=(B\And C)\lor (B\And D)\lor (C\And D);}$
• для ${\displaystyle 60\leq t\leq 79}$ установим ${\displaystyle K_{t}={\mbox{0x}}ca62c1d6}$ и ${\displaystyle f_{t}(B,C,D)=B\oplus C\oplus D.}$

Затем 160-битная строка ${\displaystyle a}$ разбивается на пять 32-битных слов так, что ${\displaystyle a=H_{0}\lVert H_{1}\lVert H_{2}\lVert H_{3}\lVert H_{4}.}$

Также создается шестнадцать 32-битных слов ${\displaystyle W_{0}=i,~~W_{1}=W_{2}=...=W_{15}=0^{32}.}$

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

1. ${\displaystyle {\mbox{For}}~t=16~{\mbox{to}}~79~{\mbox{do}}~W_{t}=(W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16})\lll 1;}$
2. ${\displaystyle A=H_{0};~B=H_{1};~C=H_{2};~D=H_{3};~E=H_{4};}$
3. ${\displaystyle {\mbox{For}}~t=0~{\mbox{to}}~79~{\mbox{do}}}$

   ${\displaystyle {\mbox{TEMP}}=A\lll 5+f_{t}(B,C,D)+E+W_{t}+K_{t};}$

   ${\displaystyle E=D;~D=C;~C=B\lll 30;~B=A;~A=TEMP;}$

4. ${\displaystyle H_{0}=H_{0}+A;~H_{1}=H_{1}+B;~H_{2}=H_{2}+C;~H_{3}=H_{3}+D;H_{4}=H_{4}+E;}$
5. ${\displaystyle G_{a}(i)=H_{0}\lVert H_{1}\lVert H_{2}\lVert H_{3}\lVert H_{4}.}$

Введем функцию ${\displaystyle \Gamma _{a}(i)=H_{i~mod~5}^{i}}$ где ${\displaystyle H_{0}^{5j}\lVert H_{1}^{5j+1}\lVert H_{2}^{5j+2}\lVert H_{3}^{5j+3}\lVert H_{4}^{5j+4}=G_{a}(j)}$ для ${\displaystyle j={\mathcal {b}}i/5{\mathcal {c}}.}$

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

${\displaystyle T[i]=\Gamma _{a}(i),~~0\leq i<512;}$

${\displaystyle S[j]=\Gamma _{a}({\mbox{0x}}1000+j),~~0\leq j<256;}$

${\displaystyle R[k]=\Gamma _{a}({\mbox{0x}}2000+k),~~0\leq k<256.}$

Далее ключ ${\displaystyle a}$ в алгоритме не используется.

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

Перед генерацией псевдослучайной функции нужно подготовить четыре 32-битовых служебных регистра ( ${\displaystyle A}$ , ${\displaystyle B}$ , ${\displaystyle C}$ и ${\displaystyle D}$ ) и четыре 32-битовых слова ( ${\displaystyle n_{1}}$ , ${\displaystyle n_{2}}$ , ${\displaystyle n_{3}}$ и ${\displaystyle n_{4}}$ ). Их значения определяются из таблиц ${\displaystyle R}$ и ${\displaystyle T}$ , 32-битового числа ${\displaystyle n}$ и некоторого числа ${\displaystyle l}$ в следующей процедуре.

${\displaystyle {\mbox{procedure}}~{\mbox{Initialize}}~(n,l,A,B,C,D,n_{1},n_{2},n_{3},n_{4})}$

${\displaystyle A\leftarrow n\oplus R[4l];}$

${\displaystyle B\leftarrow (n\ggg 8)\oplus R[4l+1];}$

${\displaystyle C\leftarrow (n\ggg 16)\oplus R[4l+2];}$

${\displaystyle D\leftarrow (n\ggg 24)\oplus R[4l+3];}$

${\displaystyle {\mbox{for}}~j\leftarrow 1~{\mbox{to}}~2~{\mbox{do}}}$

${\displaystyle P\leftarrow A\And {\mbox{0x}}7fc;~~B\leftarrow B+T[P/4];~~A\leftarrow A\ggg 9;}$

${\displaystyle P\leftarrow B\And {\mbox{0x}}7fc;~~C\leftarrow C+T[P/4];~~B\leftarrow B\ggg 9;}$

${\displaystyle P\leftarrow C\And {\mbox{0x}}7fc;~~D\leftarrow D+T[P/4];~~C\leftarrow C\ggg 9;}$

${\displaystyle P\leftarrow D\And {\mbox{0x}}7fc;~~A\leftarrow A+T[P/4];~~D\leftarrow D\ggg 9;}$

${\displaystyle (n_{1},n_{2},n_{3},n_{4})\leftarrow (D,B,A,C);}$

${\displaystyle P\leftarrow A\And {\mbox{0x}}7fc;~~B\leftarrow B+T[P/4];~~A\leftarrow A\ggg 9;}$

${\displaystyle P\leftarrow B\And {\mbox{0x}}7fc;~~C\leftarrow C+T[P/4];~~B\leftarrow B\ggg 9;}$

${\displaystyle P\leftarrow C\And {\mbox{0x}}7fc;~~D\leftarrow D+T[P/4];~~C\leftarrow C\ggg 9;}$

${\displaystyle P\leftarrow D\And {\mbox{0x}}7fc;~~A\leftarrow A+T[P/4];~~D\leftarrow D\ggg 9;}$

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

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

${\displaystyle {\mbox{function}}~{\mbox{SEAL}}~(a,n,L)}$

${\displaystyle y=0^{L};}$

${\displaystyle {\mbox{for}}~l\leftarrow 0~{\mbox{to}}~\infty ~{\mbox{do}}}$

${\displaystyle {\mbox{Initialize}}~(n,l,A,B,C,D,n_{1},n_{2},n_{3},n_{4});}$

${\displaystyle {\mbox{for}}~i\leftarrow 1~{\mbox{to}}~64~{\mbox{do}}}$

${\displaystyle P\leftarrow A\And {\mbox{0x}}7fc;~~B\leftarrow B+T[P/4];~~A\leftarrow A\ggg 9;~~B\leftarrow B\oplus A;}$

${\displaystyle Q\leftarrow B\And {\mbox{0x}}7fc;~~C\leftarrow C\oplus T[Q/4];~~B\leftarrow B\ggg 9;~~C\leftarrow C+B;}$

${\displaystyle P\leftarrow (P+C)\And {\mbox{0x}}7fc;~~D\leftarrow D+T[P/4];~~C\leftarrow C\ggg 9;~~D\leftarrow D\oplus C;}$

${\displaystyle Q\leftarrow (Q+D)\And {\mbox{0x}}7fc;~~A\leftarrow A\oplus T[Q/4];~~D\leftarrow D\ggg 9;~~A\leftarrow A+D;}$

${\displaystyle P\leftarrow (P+A)\And {\mbox{0x}}7fc;~~B\leftarrow B\oplus T[P/4];~~A\leftarrow A\ggg 9;}$

${\displaystyle Q\leftarrow (Q+B)\And {\mbox{0x}}7fc;~~C\leftarrow C+T[Q/4];~~B\leftarrow B\ggg 9;}$

${\displaystyle P\leftarrow (P+C)\And {\mbox{0x}}7fc;~~D\leftarrow D\oplus T[P/4];~~C\leftarrow C\ggg 9;}$

${\displaystyle Q\leftarrow (Q+D)\And {\mbox{0x}}7fc;~~A\leftarrow A+T[Q/4];~~D\leftarrow D\ggg 9;}$

${\displaystyle y\leftarrow y~\lVert ~B+S[4i-4]~\lVert ~C\oplus S[4i-3]~\lVert ~D+S[4i-2]~\lVert ~A\oplus S[4i-1];}$

${\displaystyle {\mbox{if}}~|y|\geq L~{\mbox{then}}~{\mbox{return}}~~y_{0}y_{1}...y_{L-1};}$

${\displaystyle {\mbox{if}}~odd(i)~{\mbox{then}}~(A,B,C,D)\leftarrow (A+n_{1},B+n_{2},C\oplus n_{1},D\oplus n_{2});}$

${\displaystyle {\mbox{else}}~(A,B,C,D)\leftarrow (A+n_{3},B+n_{4},C\oplus n_{3},D\oplus n_{4});}$

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

Примечания

Источники

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М. : Триумф, 2002. — С. 446—448. — 816 с. — 3000 экз. — ISBN 5-89392-055-4 .
• , D.Coppersmith . . — 1998.
• Хелен Хандшух , . ${\displaystyle X^{2}}$ -Cryptanalysis of the SEAL Encryption Algorithm. — 1997.

Ссылки

• «Computer readable device implementing a software-efficient pseudorandom function encryption»
• от 5 марта 2016 на Wayback Machine
• от 4 марта 2016 на Wayback Machine