Русская Википедия:Halka
Шаблон:Карточка блочного шифра
Halka — блочный шифр с размером блока 64 бита, длиной ключа 80 бит и количеством раундов 24. В данном шифре используются в качестве нелинейных элементов 8-битные S-блоки. Главной особенностью является вычисление Шаблон:Не переведено 5 на основе LFSRШаблон:Sfn, требующего 138 логических элементовШаблон:Sfn, что делает данный шифр применимым в облегчённой криптографии, несмотря на использование 8-битного S-блока. Развёртывание ключа осуществляется по схеме, аналогичной той, что используется для блочного шифра PRESENTШаблон:Sfn. Данный шифр был представлен в 2014 году.
История
Несмотря на существование широко используемых блочных шифров, таких как AES, который был создан еще в 1998 году, область разработки новых блочных шифров является активной и в настоящее время. В 2014 году был разработан шифр Halka. По заявлению автора, шифр стал уникальным во многих отношенияхШаблон:Sfn:
- это первое использование 8-битного S-блока в облегчённой криптографии;
- традиционно LFSR был использован только в потоковых шифрах, в то время как Halka — блочный;
- Halka сочетает в себе сильные стороны как AES, так и PRESENT.
Возможное применение
Применение шифра возможно в повсеместных вычислениях, включающих RFID, сенсорных сетях и устройствах, для которых достаточно 80-битного размера ключаШаблон:Sfn.
Алгоритм
Halka состоит из 24 раундов. Ниже приведён алгоритм шифраШаблон:Sfn.
Обозначим в <math>i</math>-м раунде состояние 64-битного блока как <math>V_i=(v^i_0 ... v^i_{63})</math> и раундовый ключ, т.е. ключ, используемый в одном раунде и получаемый из первоначального ключа, как <math>K_i=(k^i_0 ... k^i_{63})</math>.
- На вход принимаются значение ключа <math>K</math> и незашифрованный текст <math>P</math>.
- Значение блока <math>V_1</math> в первом раунде равняется <math>P</math>.
- Генерируются раундовые ключи на основе ключа <math>K</math>.
- Далее циклически для 24 раундов выполняются:
- Трансформация при шифровании, при которой к состоянию <math>V_i</math> применяется XOR с раундовым ключом <math>K_i</math>,
- AES-подобное нелинейное преобразование (S-блок), построение которого состоит из взятия мультипликативной инверсии с использованием LFSR в поле Галуа <math>GF(2^8)</math>, причем предварительно <math>V_i</math> разделяется на восемь равных 8-битных частей, над которыми и производятся данные операции, после чего результаты конкатенируются.
- Перестановка битов в блоке <math>V_i</math> случайным образом, однако с условием, что все биты одной 8-битной части текущего блока <math>V_i</math> переходят в биты различных 8-битных частей блока следующего уровня.
- Цикл завершается.
- Выполняется последняя операция XOR для <math>V_{25}</math> и <math>K_{25}</math>.
Мультипликативная инверсия с использованием LFSR
Главной особенностью Halka является реализация мультипликативного инвертирования для нелинейного преобразования (S-блок) с использованием LFSR, использующего в качестве функции обратной связи примитивный многочлен <math>x^8+x^4+x^3+x^2+1</math> и требующего на 8-битный S-блок всего 138 логических элементов. В то время как для ранее известных реализаций требуется не менее 253Шаблон:SfnШаблон:Sfn. Реализация шифра Halka малоресурсна, но несмотря на это, она удобна в использовании по отношению к программному обеспечениюШаблон:Sfn.
В данном разделе описывается вычисление мультипликативной инверсии при помощи регистра сдвига с обратной связью (LFSR)Шаблон:Sfn.
Математическое описание
Преобразование LFSR для <math>m</math> циклов может быть записано какШаблон:Sfn:
<math>W(t+m)=A^{m} \cdot W(t)</math>, где <math>A</math> — матрица преобразования LFSR, <math>W(t)</math> — состояние LFSR в <math>t</math>-й отсчёт времени или начальное состояние, а <math>W(t+m)</math> — состояние LFSR в <math>(t+m)</math>-й отсчёт времени, то есть после запуска <math>m</math> тактовых циклов.
Так как в качестве функции обратной связи используется примитивный многочлен, LFSR будет генерировать последовательность с максимальным периодом. Поэтому если <math>n</math> — длина LFSR, то выполнение <math>2^{n} - 1</math> циклов возвращает начальное состояние, при этом все промежуточные значения будут различными:
<math>\forall t : W(t+2^{n} - 1)=A^{2^{n} - 1} \cdot W(t) = W(t) \Rightarrow A^{2^{n} - 1} = E</math>.
Для вычисления мультипликативной инверсии заданного входного вектора <math>W(t+m)</math> необходимо определить новое состояние LFSR <math>W(t+m')</math> такое, что <math>m +m' = 2^{n} - 1</math>:
<math>W(t + m + m') = W ( t + 2^{n} - 1) = W(t)</math>, что равносильно <math>A^{m} \cdot A^{m'} = A^{2^{n} -1}</math>.
Для 8-битного LFSR это означает следующее:
<math>W(t+m')=W(t+255-m)</math>
Последнее равенство используется в реализации алгоритма мультипликативной инверсии с использованием LFSRШаблон:Sfn. Произвольный выбор начального состояния <math>W(t)</math> позволяет не выделять аффинное преобразование после взятия мультипликативной инверсии в отдельный шаг, как это сделано в AES, так как <math>W(t+m')</math> уже является результатом применения к мультипликативной инверсии <math>W(t+m)</math> некоторого преобразования, однозначно определяемого по <math>W(t)</math>. Такой подход позволяет избежать трудоёмких операций вроде матричного умножения. При этом выбор конкретного начального значения не оказывает существенного влияния на криптографические свойства шифраШаблон:Sfn.
Реализуемый алгоритм
Следующий алгоритм выполняется в аппаратной реализации мультипликативной инверсии:
- Имеются: 8-битный LFSR, начальное состояние initial_seed = <math>W(t)</math> и первоначальный S-box_input = <math>W(t+m)</math>.
- Преобразование LFSR инициализируется как lfsr_state = S-box_input = <math>W(t+m)</math>.
- Преобразование LFSR запускается до тех пор, пока не будет выполнено равенство: lfsr_state = initial_seed = <math>W(t)</math>.
- Затем запускается обратное преобразование LFSR до тех пор, пока не будет совершенно в сумме 255 преобразований (то есть если прямое преобразование было выполнено <math>k</math> раз, то обратное <math>255-k</math> раз).
- На выходе принимается lfsr_state = <math>W(t+m')</math>.
Данный алгоритм даёт на выходе мультипликативную инверсию входного 8-битного блока S-box_input Шаблон:Sfn.
Аппаратная реализация
Аппаратная реализация осуществляется следующим образомШаблон:Sfn:
- Конструируется LFSR из восьми триггеров с двумя входами (например, D-триггеры).
- Конструируются необходимые логические элементы, обеспечивающие на входе LFSR функцию обратной связи.
- Конструируется логическая схема, подключающаяся ко входам триггеров, обеспечивающая обратное преобразование LFSR для того же примитивного многочлена.
- Выход LFSR подключается к 8-входному вентилю NAND (через несколько вентилей NOT), выход которого подключён ко входам триггеров так, чтобы организовать логику управления LFSR в обратном направлении.
- Используется 8-битный счётчик LFSR. Выходной сигнал счётчика подключается к 8-входному вентилю NAND (через несколько вентилей NOT), чтобы сигнализировать о завершении 255 циклов. Конечное состояние LFSR содержит мультипликативную инверсию поданного начального значения.
Криптоанализ
Дифференциальный и линейный криптоанализ
Для 8-битных S-блоков, используемых в Halka, вероятность дифференциальной характеристики составляет <math>2^{-6}</math>Шаблон:Sfn. За раунд дифференциальная вероятность равняется <math>(2^{-6})^{2} = 2^{-12}</math> Шаблон:Sfn. После 24 раундов общая вероятность любой дифференциальной характеристики составит <math>(2^{-12})^{24} = 2^{-228}</math>Шаблон:Sfn. Также существуют исследования, которые доказывают, что шифр Halka не так устойчив к дифференциальному анализу, как утверждает автор шифраШаблон:Sfn.
Линейное смещение мультипликативной инверсии равно <math>2^{-4}</math>. Тогда полное линейное смещение Halka составит после 24 раундов <math>((2^{-4})^2)^{24} = 2^{-192}</math>Шаблон:Sfn.
Алгебраическая атака
Для Halka не требуется анализ против алгебраических атак, потому что AES-подобное нелинейное преобразование(S-блок) не может быть описано квадратными уравнениямиШаблон:Sfn.
Анализ на связанных ключах и сдвиговая атака
Нет никаких доказательств того, что алгоритм планирования ключей PRESENT, используемый в Halka, может быть подвержен атаке на связанных ключах и сдвиговой атаке. Кроме того, 8-битный S-блок, используемый в Halka, усиливает данный алгоритм развёртывания ключейШаблон:Sfn.
Кубическая атака
Так как AES невосприимчив к Шаблон:Не переведено 5, то и Halka устойчив к подобным атакамШаблон:Sfn.
Структурные атаки
В силу побитовой перестановки Halka получение словоподобных структур, используемых в интегральных и коллизионных атаках, невозможно, что делает его невосприимчивым к подобным атакамШаблон:Sfn.
Примечания
Литература
- Книги
- Статьи
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
Ссылки
Шаблон:Симметричные криптоалгоритмы Шаблон:Добротная статья