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

Схема алгоритма SEAL

SEAL (Шаблон:Lang-en, программно-оптимизированный алгоритм шифрования) — симметричный поточный алгоритм шифрования данных, оптимизированный для программной реализации.

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

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

История

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

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

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

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

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

Описание

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

• числа шестнадцатеричной системы счисления начинаются с символов «0x» и используют в записи кроме десятичных цифр символы «a», «b», «c», «d», «e» и «f», которые обозначают десятичные числа от 10 до 15 соответственно;
• под выражением Y $⋙$ t следует понимать циклический сдвиг регистра Y вправо на t бит;
• под выражением Y $⋘$ t следует понимать циклический сдвиг регистра Y влево на t бит;
• операция X $\mathrm{\&}$ Y означает побитовое логическое умножение (Шаблон:Lang-en) регистров X и Y;
• операция X $\vee$ Y означает побитовое логическое сложение (Шаблон:Lang-en) регистров X и Y;
• операция X $\oplus$ Y означает побитовое сложение по модулю 2 (Шаблон:Lang-en) регистров X и Y;
• под X $\Vert$ Y следует понимать конкатенацию (Шаблон:Lang-en) регистров X и Y;
• выражение odd (X) обозначает логическую функцию аргумента X, которая принимает значение ИСТИНА (Шаблон:Lang-en) только, если X — нечётное число.

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

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

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

• для $0\le t\le 19$ установим $K_t=\text{0x}5a827999$ и $f_t(B,C,D)=(B\mathrm{\&}C)\vee (\overline{B}\mathrm{\&}D);$
• для $20\le t\le 39$ установим $K_t=\text{0x}6ed9eba1$ и $f_t(B,C,D)=B\oplus C\oplus D;$
• для $40\le t\le 59$ установим $K_t=\text{0x}8f1bbcdc$ и $f_t(B,C,D)=(B\mathrm{\&}C)\vee (B\mathrm{\&}D)\vee (C\mathrm{\&}D);$
• для $60\le t\le 79$ установим $K_t=\text{0x}ca62c1d6$ и $f_t(B,C,D)=B\oplus C\oplus D.$

Затем 160-битная строка $a$ разбивается на пять 32-битных слов так, что $a=H_0\Vert H_1\Vert H_2\Vert H_3\Vert H_4.$

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

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

1. $\text{For}t=16\text{to}79\text{do}{W}_t=(W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16})⋘1;$
2. $A=H_0;B=H_1;C=H_2;D=H_3;E=H_4;$
3. $\text{For}t=0\text{to}79\text{do}$

   $\text{TEMP}=A⋘5+f_t(B,C,D)+E+W_t+K_t;$

   $E=D;D=C;C=B⋘30;B=A;A=TEMP;$

4. $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. $G_a(i)=H_0\Vert H_1\Vert H_2\Vert H_3\Vert H_4.$

Введем функцию ${\mathrm{\Gamma }}_a(i)=H_{imod5}^i$ где $H_0^{5j}\Vert H_1^{5j+1}\Vert H_2^{5j+2}\Vert H_3^{5j+3}\Vert H_4^{5j+4}=G_a(j)$ для $j=𝒷i/5𝒸.$

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

$T[i]={\mathrm{\Gamma }}_a(i),0\le i<512;$

$S[j]={\mathrm{\Gamma }}_a(\text{0x}1000+j),0\le j<256;$

$R[k]={\mathrm{\Gamma }}_a(\text{0x}2000+k),0\le k<256.$

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

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

Перед генерацией псевдослучайной функции нужно подготовить четыре 32-битовых служебных регистра ($A$, $B$, $C$ и $D$) и четыре 32-битовых слова ($n_1$, $n_2$, $n_3$ и $n_4$). Их значения определяются из таблиц $R$ и $T$, 32-битового числа $n$ и некоторого числа $l$ в следующей процедуре.

$\text{procedure}\text{Initialize}(n,l,A,B,C,D,n_1,n_2,n_3,n_4)$

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

$B\leftarrow (n⋙8)\oplus R[4l+1];$

$C\leftarrow (n⋙16)\oplus R[4l+2];$

$D\leftarrow (n⋙24)\oplus R[4l+3];$

$\text{for}j\leftarrow 1\text{to}2\text{do}$

$P\leftarrow A\mathrm{\&}\text{0x}7fc;B\leftarrow B+T[P/4];A\leftarrow A⋙9;$

$P\leftarrow B\mathrm{\&}\text{0x}7fc;C\leftarrow C+T[P/4];B\leftarrow B⋙9;$

$P\leftarrow C\mathrm{\&}\text{0x}7fc;D\leftarrow D+T[P/4];C\leftarrow C⋙9;$

$P\leftarrow D\mathrm{\&}\text{0x}7fc;A\leftarrow A+T[P/4];D\leftarrow D⋙9;$

$(n_1,n_2,n_3,n_4)\leftarrow (D,B,A,C);$

$P\leftarrow A\mathrm{\&}\text{0x}7fc;B\leftarrow B+T[P/4];A\leftarrow A⋙9;$

$P\leftarrow B\mathrm{\&}\text{0x}7fc;C\leftarrow C+T[P/4];B\leftarrow B⋙9;$

$P\leftarrow C\mathrm{\&}\text{0x}7fc;D\leftarrow D+T[P/4];C\leftarrow C⋙9;$

$P\leftarrow D\mathrm{\&}\text{0x}7fc;A\leftarrow A+T[P/4];D\leftarrow D⋙9;$

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

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

$\text{function}\text{SEAL}(a,n,L)$

$y=0^L;$

$\text{for}l\leftarrow 0\text{to}\mathrm{\infty }\text{do}$

      $\text{Initialize}(n,l,A,B,C,D,n_1,n_2,n_3,n_4);$

      $\text{for}i\leftarrow 1\text{to}64\text{do}$

            $P\leftarrow A\mathrm{\&}\text{0x}7fc;B\leftarrow B+T[P/4];A\leftarrow A⋙9;B\leftarrow B\oplus A;$

            $Q\leftarrow B\mathrm{\&}\text{0x}7fc;C\leftarrow C\oplus T[Q/4];B\leftarrow B⋙9;C\leftarrow C+B;$

            $P\leftarrow (P+C)\mathrm{\&}\text{0x}7fc;D\leftarrow D+T[P/4];C\leftarrow C⋙9;D\leftarrow D\oplus C;$

            $Q\leftarrow (Q+D)\mathrm{\&}\text{0x}7fc;A\leftarrow A\oplus T[Q/4];D\leftarrow D⋙9;A\leftarrow A+D;$

            $P\leftarrow (P+A)\mathrm{\&}\text{0x}7fc;B\leftarrow B\oplus T[P/4];A\leftarrow A⋙9;$

            $Q\leftarrow (Q+B)\mathrm{\&}\text{0x}7fc;C\leftarrow C+T[Q/4];B\leftarrow B⋙9;$

            $P\leftarrow (P+C)\mathrm{\&}\text{0x}7fc;D\leftarrow D\oplus T[P/4];C\leftarrow C⋙9;$

            $Q\leftarrow (Q+D)\mathrm{\&}\text{0x}7fc;A\leftarrow A+T[Q/4];D\leftarrow D⋙9;$

            $y\leftarrow y\Vert B+S[4i-4]\Vert C\oplus S[4i-3]\Vert D+S[4i-2]\Vert A\oplus S[4i-1];$

            $\text{if}|y|\ge L\text{then}\text{return}{y}_0{y}_1...y_{L-1};$

            $\text{if}odd(i)\text{then}(A,B,C,D)\leftarrow (A+n_1,B+n_2,C\oplus n_1,D\oplus n_2);$

                                $\text{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 МГц и является одним из самых быстрых шифров.

Источники

• Шаблон:Книга:Шнайер Б.: Прикладная криптография
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:US patent «Computer readable device implementing a software-efficient pseudorandom function encryption»
• Неофициальная реализация алгоритма SEAL 3.0 на языке C Шаблон:Wayback
• Неофициальная реализация алгоритма SEAL 3.0 на языке Delphi Шаблон:Wayback