FPGA implementation of the Zakrevskij's cipher based on reconfigurable FSM

全文:

В настоящее время существует высокая потребность в создании быстродействующих компактных криптопроцессоров, которые используются для снижения вычислительной нагрузки основного процессора, в средствах автоматического регулирования и управления техпроцессами, в телекоммуникационном оборудовании, так же как аппаратные модули доверенной загрузки операционной системы и пр. Криптопроцессоры, как правило, являются устройствами, в которых реализованы криптографические алгоритмы различного назначения (симметричное/ асимметричное шифрование, электронная цифровая 16 Вестник СибГАУ. № 1(53). 2014 подпись, хэширование). Часто разнородность криптоалгоритмов не позволяет использовать единый объединяющий все алгоритмы подход при проектировании криптопроцессора, что может дать существенный выигрыш по быстродействию, энергопотреблению, компактности и др. Как вариант объединяющего подхода предлагается использование автоматной модели при задании криптоалгоритмов. Конечно-автоматные шифрсистемы давно известны криптографам [1], но мало изучены. В частности, в литературе не встречаются исследования на пригодность их к практическому использованию. В данной работе в качестве представителя класса автоматных шифров выбран шифр Закревского на основе перестраиваемого автомата [2]. Исследуются характеристики данного шифра при реализации его на базе программируемой логической интегральной схемы (ПЛИС). Необходимые определения. Определение 1. Конечным автоматом А называется пятёрка (X, S, Y, у, ф), где S - конечное непустое множество состояний; X и Y - конечные входной и выходной алфавиты соответственно; у : X х S - S и ф: X х S -- Y - функции переходов и выходов соответственно. Автомат А при фиксированном состоянии s реализует отображение fs : X * - Y *, для которого fa) = р, где PeY* - реакция автомата A на входное слово a eX*. Определение 2. Автомат А называется сильносвязным, если для любых состояний s и s' существует входное слово, которое переводит автомат из состояния s в состояние s'. Определение 3. Автомат A"1 = (Y, S, X, у', ф') называется обратным к автомату A = (X, S, Y, у, ф), реализующему {f : se S}, еслиA"1 реализует {f"1 : se S}. Определение 4. Шифром Закревского называется автоматный шифр, в котором множества открытых и шифрованных сообщений являются множествами слов в некоторых алфавитах, алгоритмы шифрования и расшифрования задаются взаимно обратными сильносвязными инициальными автоматами А и A-1 с биективными в каждом состоянии функциями выходов. Для практического использования шифра Закрев-ского требуется задать процедуру генерации автоматов А и A" по ключу. В работе [2] предлагается использовать для этих целей так называемый перестраиваемый автомат, т. е. автомат, функция переходов которого строится «на лету» с помощью блока управления. Структура перестраиваемого автомата. Структура перестраиваемого автомата представлена на рисунке. Компонента Key управляет работой мультиплексора MUX, который из двух состояний s1 = y1(s,x) и s2 = y2(s,x) выбирает одно. Компонента Reg (регистр памяти) предназначена для хранения текущего состояния автомата. Компонента Key реализует булеву функцию, вектор значений которой является секретом (ключом) и «загружается» (вместе с начальным состоянием) в шифрсистему при инициализации. Таким образом, схема на рисунке задает шифрующий автомат A = (X, S, Y, у, ф), в котором для любой пары (x,s) из X х S выполняется, что у(х^) = у^,х), когда Key(x,s) = 0, либо у(х^) = у2^,х), когда Key(x,s) = 1. Чтобы шифрующий автомат А был сильносвязным, одна из функций у^,х) или у2^,х) (пусть у1) задаёт сильносвязный граф переходов. Пусть S = (s,: I = 1, ..., m}. Тогда существует х из Х такой, что у1^,х) = s,+1, когда i<m и у^^х) = s1, причём Key(x,s) = 0 для любого s из S. Для расшифрования в схеме на рисунке вместо функции выходов ф^,х) нужно использовать функцию ф' (s,y) = х такую, что для любого s из S выполняется ф'^(у) = ф-1Ху). Также значение функции ф' (s,y) должно подаваться на вход компонентам Key, у^,х) и у2^,х). Реализация на ПЛИС. В настоящей работе исследуется перестраиваемый автомат, у которого X = = |Y| = 16 (4 бита при кодировании), |S| = 8 (3 бита при кодировании). Таким образом, длина ключа равна 16-8-8+3 = 128-8+3=123 бита (128 бит - вектор состояний булевой функции Key, 8-бит - для реализации сильносвязности, 3 бита - начальное состояние). Таблицы переходов у^,х) и у2^,х) и таблица выходов ф^,х) задавались случайным образом, но с обеспечением требуемых свойств (сильносвязность и биектив-ность в каждом состоянии соответственно). Исследуемая автоматная шифрсистема была описана на языке VHDL и промоделирована в САПР Xilinx Webpack ISE 14.1 при реализации на ПЛИС Spartan-3 XC3S50, при этом состояния автомата кодировались разными методами, что не влияло на конечные результаты. Оказалось, что процедура расшифрования имеет несколько более низкую производительность, чем процедура шифрования, но при этом также требует несколько меньшего числа ресурсов микросхемы. Критерием оценки практической пригодности криптосистемы является эффективность её ПЛИС-реализации в сравнении с реализациями современных блочных и поточных шифров на ПЛИС того же типа. В таблице сравниваются результаты реализации шифра Закревского на основе перестраиваемого автомата и современных блочных (представленных шифром AES) и поточных (представленных шифрами - финалистами конкурса eSTREAM, рекомендованными для аппаратной реализации: Grain, MICKEY и Trivium) шифров. Результаты реализации AES взяты из работы [3], шифров - финалистов eSTREAM - из работы [4]. Сравнение ПЛИС-реализаций шифра Закревского на основе перестраиваемого автомата и современных блочных и поточных шифров Шифр Ресурсоёмкость (S), Slices Производительность (T), Мбит/с T/S Закревского (шифрование) 370 298 0,805 Закревского (расшифрование) 365 269 0,737 AES 163 208 1,276 Grain 50 196 3,920 MICKEY 115 233 2,026 Trivium 50 240 4,800 17 Математика, механика, информатика Структура перестраиваемого автомата Таким образом, шифр Закревского на основе перестраиваемого автомата имеет более высокую производительность, чем блочный шифр AES и аппаратноориентированные поточные шифры - финалисты eSTREAM, однако уступает им в ресурсоёмкости. В данной работе предлагается решать задачу проектирования криптопроцессора с набором различного вида криптоалгоритмов на базе автоматной модели. Проводятся исследования шифра Закревского на основе перестраиваемого автомата как представителя симметричных автоматных шифров. Указанный шифр реализован на ПЛИС Spartan-3, проведено сравнение ПЛИС-реализаций шифра Закревского на основе перестраиваемого автомата, шифров AES, Grain, MICKEY, Trivium. Проведённые исследования показывают, что автоматное симметричное шифрование пригодно к использованию на практике.

作者简介

Dmitry Kovalev

National Research Tomsk State University; JSC “Information satellite system” named after academician M. F. Reshetnev”

Email: dmisk@hotmail.com
software engineer, JSC “Information satellite system” named after academician M. F. Reshetnev”, graduate student of the Information Security and Cryptography Department, National Research Tomsk State University.

参考

补充文件