WikiSort.ru - Не сортированное

Табличная замена ${\displaystyle \gamma }$

Алгоритм Crypton использует 4 таблицы замен. Каждая из которых замещает 8-битовое входное значение на выходное такого же размера.

Все таблицы ${\displaystyle S_{0}...S_{3}}$ являются производными от основной таблицы ${\displaystyle S}$ (см. рисунок - вычисление производных таблиц замен).

Ниже представлен пример таблиц:

Таблица ${\displaystyle S_{0}}$ :

Таблица ${\displaystyle S_{1}}$

Таблица ${\displaystyle S_{2}}$

Таблица ${\displaystyle S_{3}}$ :

В четных раундах используется операция ${\displaystyle \gamma _{e}}$ , в нечетных - ${\displaystyle \gamma _{o}}$ . Эти операции и таблицы замен обладают рядом свойств, которые важны, особенно для унификации операций шифрования и расшифрования. Свойства таблиц и операций:

${\displaystyle \gamma _{e}(\gamma _{o}(A))=\gamma _{o}(\gamma _{e}(A))=A;}$

${\displaystyle S^{-1}=S;}$

${\displaystyle S_{2}=S_{0}^{-1};}$

${\displaystyle S_{3}=S_{1}^{-1};}$

где ${\displaystyle A}$  — текущее значение блока шифруемых данных. Операции ${\displaystyle \gamma _{e}}$ и ${\displaystyle \gamma _{o}}$ можно определить следующим образом:

${\displaystyle \gamma _{e}:b_{ij}=S_{(j+2+imod4)}(a_{ij});}$

${\displaystyle \gamma _{o}:b_{ij}=S_{(j+imod4)}(a_{ij}).}$

где:

• ${\displaystyle a_{ij}}$  — текущее значение конкретного байта данных;
• ${\displaystyle b_{ij}}$  — значение байта данных после выполнения операции;

Линейное преобразование ${\displaystyle \pi }$

Здесь используется 4 специальных константы, шестнадцатеричные значения которых указаны ниже:

${\displaystyle m_{0}=FC;}$

${\displaystyle m_{1}=F3;}$

${\displaystyle m_{2}=CF;}$

${\displaystyle m_{3}=3F;}$

Эти константы объединены в маскирующие последовательности, перечисленные ниже:

${\displaystyle M_{0}=m_{3}\bullet m_{2}\bullet m_{1}\bullet m_{0};}$

${\displaystyle M_{1}=m_{0}\bullet m_{3}\bullet m_{2}\bullet m_{1};}$

${\displaystyle M_{2}=m_{1}\bullet m_{0}\bullet m_{3}\bullet m_{2};}$

${\displaystyle M_{3}=m_{2}\bullet m_{1}\bullet m_{0}\bullet m_{3};}$

где ${\displaystyle \bullet }$  — операция конкатенации.

Сама же операция ${\displaystyle \pi }$  — представляет собой битовую перестановку. В нечетных раундах используется операция ${\displaystyle \pi _{o}}$ :

${\displaystyle B[0]=(A[3]\&M_{3})\oplus (A[2]\&M_{2})\oplus (A[1]\&M_{1})\oplus (A[0]\&M_{0});}$

${\displaystyle B[1]=(A[3]\&M_{0})\oplus (A[2]\&M_{3})\oplus (A[1]\&M_{2})\oplus (A[0]\&M_{1});}$

${\displaystyle B[2]=(A[3]\&M_{1})\oplus (A[2]\&M_{0})\oplus (A[1]\&M_{3})\oplus (A[0]\&M_{2});}$

${\displaystyle B[3]=(A[3]\&M_{2})\oplus (A[2]\&M_{1})\oplus (A[1]\&M_{0})\oplus (A[0]\&M_{3});}$

где:

• ${\displaystyle \&}$  — логическая побитовая операция «и»;
• ${\displaystyle A[i]}$ и ${\displaystyle B[i]}$  — значение i-ой строки обрабатываемых данных до и после выполнения операции соответственно.

В четных раундах используется операция ${\displaystyle \pi _{e}}$ :

${\displaystyle B[0]=(A[3]\&M_{1})\oplus (A[2]\&M_{0})\oplus (A[1]\&M_{3})\oplus (A[0]\&M_{2});}$

${\displaystyle B[1]=(A[3]\&M_{2})\oplus (A[2]\&M_{1})\oplus (A[1]\&M_{0})\oplus (A[0]\&M_{3});}$

${\displaystyle B[2]=(A[3]\&M_{3})\oplus (A[2]\&M_{2})\oplus (A[1]\&M_{1})\oplus (A[0]\&M_{0});}$

${\displaystyle B[3]=(A[3]\&M_{0})\oplus (A[2]\&M_{3})\oplus (A[1]\&M_{2})\oplus (A[0]\&M_{1});}$

Фактически эта операция обеспечивает наличие в каждом результирующем байте каждого столбца двух битов каждого исходного байта того же столбца.

Байтовая перестановка ${\displaystyle \tau }$

Данная перестановка преобразует простейшим образом строку данных в столбец:

${\displaystyle \tau :b_{ij}=a_{ij}}$

Операция ${\displaystyle \sigma }$

Данная операция является побитовым сложением всего массива данных с ключом раунда:

${\displaystyle \sigma :B=A\oplus K_{r}}$

где: ${\displaystyle B}$  — новое значение блока шифруемых данных; ${\displaystyle K_{r}}$  — ключ текущего раунда ${\displaystyle r}$ .

Заметим, именно 12 раундов шифрования рекомендуется автором алгоритма Че Хун Лимой, однако строгое количество раундов не установлено. Кроме 12 раундов шифрования, перед первым раундом алгоритма выполняется предварительная операция ${\displaystyle \sigma }$ , а по завершении 12 раундов выполняется выходное преобразование ${\displaystyle \phi _{e}}$ , состоящее из последовательно выполняемых операций ${\displaystyle \tau }$ , ${\displaystyle \pi _{e}}$ и ${\displaystyle \tau }$ .

Краткое описание шифра

Crypton представляет собой блочный шифр. Длина ключа и длина блока 128 бит. Четыре преобразования работают с промежуточным результатом, называемым Состоянием (State). Состояние можно представить в виде прямоугольного массива из 16 байт:

${\displaystyle (A_{i,j})}$ где ${\displaystyle A\in \{0,...,3\}}$

Обозначим столбец из 4 байт как ${\displaystyle A_{j}=(A_{0j},A_{1j},A_{2j},A_{3j})}$

Так же представим ключ шифрования:

${\displaystyle (K_{i,j})}$ где ${\displaystyle K\in \{0,...,3\}}$ и ${\displaystyle K_{j}=(K_{0j},K_{1j},K_{2j},K_{3j})}$ .

В шифре определено поле Галуа ${\displaystyle GF(2^{8})}$ , элементами которого являются байты. Байты рассматриваются как многочлены над ${\displaystyle Z_{2}}$

${\displaystyle b\leftrightarrow b_{7}x^{7}+b_{6}x^{6}+b_{5}x^{5}+b_{4}x^{4}+b_{3}x^{3}+b_{2}x^{2}+b_{1}x^{1}+b_{0}}$

Операция сложения ${\displaystyle \oplus }$  — при сложении байт соответствующие им многочлены складываются над ${\displaystyle Z_{2}}$ .

Операция умножения — при умножении соответствующие им многочлены перемножаются над ${\displaystyle Z_{2}}$ и результирующий многочлен берется по модулю от простого многочлена

${\displaystyle m(x)=x^{8}+x^{4}+x^{3}+x^{1}+1}$

В процессе работы алгоритма, ключ ${\displaystyle (K_{i,j})}$ расширяется (Key Schedule, Key Expansion). Первые 4 столбца (по 4 байта) являются исходным ключом ${\displaystyle K^{0}}$ . Каждый последующий ${\displaystyle r}$ -й набор из 4 столбцов вычисляется из предыдущего набора и используется для ${\displaystyle r}$ -го раунда, обозначим его ${\displaystyle K^{r}=(K_{i,j}^{r})}$ . Раунд состоит из четырёх различных элементарных преобразований, которые преобразуют состояние ${\displaystyle A=(A_{i,j})}$ в состояние ${\displaystyle B=(B_{i,j})}$  :

• Замена байт — BS (Byte Substitution): применение перестановки ${\displaystyle S}$ или ${\displaystyle B_{i,j}=S(A_{i,j})}$
• Сдвиг строк — SR (Shift Rows): циклический сдвиг байт по правилу: ${\displaystyle B_{i,j}=A_{i,(j+1)mod4}}$
• Замешивание столбцов — MC (Mix Columns: каждый столбец состояния изменяется линейным преобразованием ${\displaystyle \mu :(0,1)^{32}\rightarrow (0,1)^{32}}$

Иначе говоря, это есть ничто иное, как умножение столбцов на матрицу слева: ${\displaystyle B=\mu (A)=E={\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}}}$

Операция ${\displaystyle \mu }$ обратима : ${\displaystyle A_{j}=\mu ^{-1}(B_{j})}$

• Добавление раундового ключа — KA (Key Addition): к текущему состоянию прибавляется раундовый ключ.

Финальный раунд не содержит операции MC. Формулы, связывающие состояния ${\displaystyle A^{r}}$ и ${\displaystyle A^{r-1}}$ :

${\displaystyle A^{r}=MC(SR(S(A^{r-1})))\oplus K^{r-1}}$ ;

${\displaystyle A^{r-1}=S^{-1}(SR^{-1}(MC^{-1}(A^{r}\oplus K^{r-1})))}$ ;

Алгоритм реализации интегральной атаки

Интегральная атака основана на возможности свободного подбора атакующим некоторого набора открытых текстов для последующего их зашифрования. Она эффективнее, чем полный перебор по всему ключевому пространству.

Введем определения.

${\displaystyle \Lambda }$  — набор из 256 входных блоков (массивов State), каждый из которых имеет байты (назовем их активными), значения которых различны для всех 256 блоков. Остальные байты (пассивные) остаются одинаковыми для всех 256 блоков из ${\displaystyle \Lambda }$ -набора. То есть для любых ${\displaystyle A,B\in \Lambda }$ то ${\displaystyle A_{ij}\neq B_{ij}}$ если байт с индексом (i, j) активный и иначе ${\displaystyle A_{ij}=B_{ij}}$ .

${\displaystyle \Lambda ^{r}}$  — ${\displaystyle \Lambda }$ c k активными байтами.

${\displaystyle P_{r}}$  — множество состояний в конце раунда r.

${\displaystyle \Lambda }$ -набор. После элементарных преобразований BS и KA блоки ${\displaystyle \Lambda }$ -набора дадут в результате другой ${\displaystyle \Lambda }$ -набор с активными байтами в тех же позициях, что и у исходного. Преобразование SR сместит эти байты соответственно заданным в ней смещениям. После преобразования MC ${\displaystyle \Lambda }$ -набора в общем случае необязательно останется ${\displaystyle \Lambda }$ -набором (результат операции может перестать удовлетворять определению ${\displaystyle \Lambda }$ -набора). Так как каждый байт ${\displaystyle B_{ij}}$ результата MC является линейной комбинацией (с обратимыми коэффициентами) четырёх входных байт того же столбца ${\displaystyle B_{ij}=2A_{ij}\oplus 3A_{i+1mod4j}\oplus A_{i+2mod4j}\oplus A_{i+3mod4j}}$ , то столбец с единственным активным байтом на входе даст в результате на выходе столбец со всеми четырьмя активными байтами.

Рассмотрим шифрование ${\displaystyle \Lambda ^{1}}$ -набора. Во всех блоках будет активен только один байт. Значение этого байта различно во всех 256 блоках, а остальные байты одинаковы. В первом раунде преобразование MC преобразует один активный байт в столбец из 4 активных байт, то есть ${\displaystyle P_{1}}$ является ${\displaystyle \Lambda ^{4}}$ . Во втором раунде эти 4 байта разойдутся по 4 различным столбцам в результате преобразования SR, ${\displaystyle P_{2}}$ является ${\displaystyle \Lambda ^{16}}$ -набором. Преобразование MC следующего, третьего раунда преобразует эти байты в 4 столбца, содержащие активные байты. Этот набор все ещё остается ${\displaystyle \Lambda }$ -набором до того момента, когда он поступает на вход MC третьего раунда.

Основное свойство ${\displaystyle \Lambda }$ -набора — поразрядная сумма по модулю 2 (${\displaystyle \oplus }$ ) всех байтов, находящихся на одних и тех же местах, по всему набору равна нулю (поразрядная сумма неактивных (с одинаковыми значениями) байт равна нулю по определению операции «${\displaystyle \oplus }$ », а активные байты, пробегая все 256 значений, также при поразрядном суммировании дадут нуль)

Результат преобразования MC в третьем раунде байтов входного массива данных ${\displaystyle A}$ в байты выходного массива данных ${\displaystyle B}$  — поразрядная сумма всех блоков выходного набора будет равна нулю:

${\displaystyle \oplus _{B=MC(A),A\in \Lambda ^{1}6}B_{ij}=\oplus _{A\in \Lambda ^{1}6}(2A_{ij}\oplus 3A_{i+1mod4j}\oplus A_{i+2mod4j}\oplus A_{i+3mod4j})=0}$

Таким образом ${\displaystyle P_{3}}$ есть ${\displaystyle \Lambda ^{16}}$ . Полная сумма данных на входе равна нулю. Это равнество нарушается последующим преобразованием BS.

Ключ ${\displaystyle K^{r}}$ однозначно задается в R представлении:

${\displaystyle L^{r}=SR^{-1}(MC^{-1}(K^{r}))}$

${\displaystyle K^{r}=MC(SR(L^{r}))}$

Для проведения атаки потребуется множество ${\displaystyle Q_{4}}$ , состоящее из 256 состояний. ${\displaystyle Q_{r}=SR^{-1}(MC^{-1}(A)),A\in P_{r}}$ Множество ${\displaystyle Q_{4}}$ можно получить применением 2 обратных преобразований SR и MC из входных данных шифра ${\displaystyle P_{4}}$ .

Схема базовой интегральной атаки на 4-раундовый Crypton:

Для всех ${\displaystyle i,j\in {0,1,2,3}}$

для ${\displaystyle k\ inGF(2^{8})}$

если ${\displaystyle \oplus _{Z\in Q}S^{-1}(Z_{ij}\oplus k)\neq 0}$ ,

то ${\displaystyle L_{ij}^{4}\neq k}$

В этой схеме инвертируется 4-й раунд шаг за шагом, чтобы получить байты ${\displaystyle P_{3}}$ , полная сумма которых равна 0. При ${\displaystyle L_{ij}^{4}=k}$ сумма ${\displaystyle \oplus _{Z\in Q}S^{-1}(Z_{ij}\oplus k)=0}$

Если предполагаемое значение байта ключа было верно, то оно будет включено в возможные варианты на место ${\displaystyle L^{4}}$ . Большая часть неверных значений байта будет отсеяно. За счет того, что поиск может производиться отдельно (параллельно) для каждого байта ключа, скорость подбора всего значения раундового ключа весьма велика. Далее по значению ${\displaystyle L^{4}}$ можно найти ${\displaystyle K^{4}}$ , а потом и ${\displaystyle K^{0}}$  — исходный ключ.