Компактная и Эффективная реализация алгоритма DES на FPGA.
Аннотация . В этой работе мы представляем эффективную и компактную аппаратную реализацию алгоритма DES. Наш проект реализуется на устройстве VIRTEXE XCV400e. Для того чтобы сократить критический путь проекта, мы использовали параллельную структуру, которая позволяла нам считать все восемь s-блоков одновременно. Наша реализация алгоритма DES позволила достичь скорости шифрования/дешифрования данных 274 Мб/с, и занимает 117 блоков CLB. Эти результаты абсолютно конкурентоспособны, в сравнение с другими аппаратными реализациями алгоритма DES.
Ключевые слова : DES, FPGA, Параллельная структура.
Введение
Криптография - основной механизм обеспечения безопасности цифровых данных. В последние годы из-за возрастания объёма данных, для борьбы с угрозами безопасности, были разработаны безопасные и быстрые криптографические алгоритмы, как полагали, меры безопасности были необходимы везде где осуществлялась работа с цифровыми данными. Разнообразие приложений безопасности, изложило дополнительный требования, так как очень безопасные алгоритмы не были единственным требованием, для некоторых приложений требовалась большая производительность, а для других меньший объём. В этом случае, разработчики алгоритмов исследовали не только программную реализацию, но также реализацию на классических аппаратных средствах или реконфигурируемых аппаратных средствах.
Реализация алгоритмов шифрования на реконфигурируемых аппаратных средствах обеспечивает главные достоинства VLSI (очень больших интегральные схемы) и программной реализации, так как это предлагает высокую скорость, подобную VLSI и высокую гибкости, подобною программному обеспечению. VLSI реализация – быстрая, но должна быть разработана полностью, от поведенческого описания до физического размещения. Необходимо следить за дорогим и трудоёмким процессом изготовления. Программная реализация предлагает высокую гибкость, но она недостаточна быстрая для случаев, где фактор времени жизненно важен. С другой стороны, реконфигурируемые устройства привлекательны по времени и по затратам проекта VLSI. Кроме того, они позволяют повторно программировать и экспериментировать на разнообразной архитектуре или нескольких вариантах одной архитектуры.
Среди различных криптографических алгоритмов, самым популярных симметричным алгоритмом является Data Encryption Standard (DES) [1, 2], разработанный IBM в середине семидесятых годов. Алгоритм DES основан на повторяющихся раундах, состоящих из нескольких битовых операций, таких как логические операции, перестановки, замены, |сдвиги и т.п. Хотя эти особенности естественно удовлетворяются для эффективного выполнений на повторно конфигурируемом устройстве FPGA, реализацию DES можно найти |оказывается|на всех платформах: программное обеспечение [1-5], VLSI [6-8] и реконфигурируемые аппаратные реализации на FPGA [9-13,8,14].
В этой статье мы представляем эффективную и компактную DES архитектуру, специально спроектированную для реконфигурируемых элементов. Реализация DES, представленная в этой статье, отличается от других предыдущих работ следующим аспектом: она использует параллельно восемь S-блоков, что приводит к существенному сокращению|снижению| критического пути|дорожки| для шифрования/дешифровки.
Содержание статьи: в пункте 2 описывается алгоритм DES. Предложенная нами архитектура DES и её реализация на реконфигурируемых элементах представлена в пункте 3. В пункте 4 сравниваются достигнутые результаты с предыдущими реализациями DES. Заключение и будущая работа представлены в секции 5.
2 Алгоритм DES
В августе 1974г., IBM представила кандидата (под именем ЛЮЦИФЕР) для криптографического алгоритма в ответ на второе предложение от Национального Бюро Стандартов (НБС), сейчас Национальный Институт Стандартов и Технологии (NIST)[15], для защитить данные во время передачи и хранения. НБС начало|запустил| процесс оценки с помощью Агентства национальной безопасности и в июле 1977 окончательно приняло модификацию алгоритма ЛЮЦИФЕРА как новый Стандарт Шифрования Данных (DES). Стандарт Шифрования Данных [16], известный, как Алгоритм Шифрования Данных(DEA) согласно ANSI [17] и DEA-1 согласно ISO [18] сохранялся как всемирный стандарт долго и был заменен новым Передовым Стандартом Кодирования (AES) в октябре 2000г. Однако, ожидается, что DES будет использоваться в течении множества лет. Это даёт основу для сравнения новых алгоритмов. DES также используется в протоколом IPSec,в кодировании ячейки банкомата, в протоколах SSL и TRIPLEDES. Детальное описание алгоритма DES может быть найдено [19-21].
DES – это блочный шифр: он кодирует/декодирует данные 64-битыми блоками, используя 64-разрядный ключ (хотя его эффективная длина ключа составляет фактически только 56 бит). DES - симметричный алгоритм: тот же алгоритм и ключ используются как для кодирования, так и декодирования. DES - повторный шифр: базовый блок (замена, следующая за перестановкой), называемый этапом, повторяется 16 раз. Для каждого раунда DES, под-ключ получается из оригинального ключа, используя алгоритм ключевого списка. Ключевой список для кодирования и декодирования один и тот же за исключением незначительной разницы в порядке(обратом) под-ключей для расшифровки. Основной поток алгоритма для кодирования/декодирования одного блока данных приведен на рисунке 1. Кодирование начинается с начальной перестановки (IP).
Рисунок 1. Алгоритм шифрования DES
Результат начальной перестановки передаётся двум 32-разрядным регистрам, под названием правый регистр и левый регистр. Эти регистры сохраняют две половины промежуточных результатов между 16 повторениями. Содержимое половины правого регистра изменяется (перестановка E) и отправляется на исключающее-или наряду с под-ключом для каждого повторения. Отметим, что некоторые биты выбираются дважды, позволяя 32-разрядному регистру расшириться к 48-разрядному. 48-бит, после исключающего-или разбивается на восемь групп (по 6-бит каждый), чтобы обратиться к восьми блокам замены (S-блоки). Перестановка Р применяется к 32-разрядному выходу S-блоков, после чего данные объединяются с помощью исключающего-или с содержимым левого регистра. Выход этого блока записывается во временный регистр, завершая первое повторение.
В следующем цикле, содержимое временных регистраторов переписывается в регистр правой половины и содержимое регистр правой половины переписывается в регистр левой половины. Этот процесс повторяется в 16 циклах DES. После 16 повторений, содержимое правой половины и левой половины регистра подвергаются заключительной перестановке , которая является инверсией начального перестановка. Результат – 64-битовый зашифрованный текст.
3 реализация DES на реконфигурируемых элементах
16 этапов одинаковых действий названы функцией f(R, K). DES содержит первую перестановку, функцию f(R, K), вторую перестановку, и список ключей , для кодировки, как показано на рисунке 2. Как было упомянуто ранее , этапы шифрования и дешифрования DES те же. Изменяется только список под-ключей в случае дешифрования.
Рисунок 2. Схема алгоритма шифрования DES
Алгоритм генерации ключевого списка простой и требующий мало время. Кроме того ключи сгенерированные однажды, используются для целой сессии. Однако, в нашей FPGA реализации, предварительно сгенерированные под-ключи запоминаются в памяти.
В оставшейся части этой статьи представлены особенности архитектурной реализации DES на FPGA
3.1 Архитектура раунда DES
На рисунке 3 представлена архитектура для этапа алгоритма DES. Эта архитектура была оптимизирована для её эффективной реализации на плис.
Рисунок 3. Реализация алгоритма DES на FPGA
Алгоритм DES в основном основан на двух действиях: перестановка и замена. Оба действия могут быть умело реализованы на FPGA|. DES использует 8 S-блоков (каждый по 64х4), занимающих всего 2Kbits. Этот относительно небольшой объём памяти может быть реализована на распределенных ресурсов памяти FPGA. Перестановки фактически не занимают|оккупируют| ресурсы FPGA. Эти полезные особенности использовались, чтобы получить эффективную|эффектное| реализацию DES, как показано на рисунке 3.
Три входа|вклада|: выборка схемы (СЕ), синхронизация (CLK), входные данные (IN) и только один выход (OUT) – четыре разъема DES. Выборка схемы (СЕ) активизирует временную логику также как и остальную часть схемы, в низком уровне. Внешняя синхронизация CLK| используется для выработки всех контрольных сигналов для синхронизации потока данных.
Когда СЕ разрешает работу, 64 бита на входе изменяют порядок и делится на два половины RIN и LIN. По переднему фронту синхросигнала, обе половины перемещаются на выходы регистров REGA и REGB. Правая половина (регистр REGA) проходят через ряд действий: перестановка E; сложение с под-ключом; замена|подстановка| (с помощью S-блоков); перестановка P и сложение с оригинальной|первоначальной| левой половиной (регистр REGB). Перед тем, как следующие часы прибудут, старая правая половина (RIGHT) поступает на вход|вклад| регистра REGB и новая левая половина (LEFT)поступает на вход регистр REGA. Затем выполняется 16 повторений. После 16-ого цикла правая и левая половины конкатенированы и результирующий блок проходит через обратную перестановку (), завершающею шифрование 64-разрядного блока. Заметим, что параллельное использование восемь S-блоков DES, приводит к существенному сокращению критического пути для шифрования/дешифрования.
3.2 Резюме выполнения
Алгоритм DES выполнена на VIRTEXE device XCV400e-8-bg560, с использованием Xilinx Foundation Series F4.1i в качестве инструмента синтеза. Проект был написан на языке VHDL. Он занял 165 (3%) CLB|, 117 (1%) триггеров и 129 (41%) выходов. Проект достигает частоты 68.05 МГц (14.7 nS). Он требует 16 циклов , чтобы закодировать один блок данных (64-бита). Поэтому, достигнутая производительность - (68.05 х 64) /16=274Mbits/s.
4 Сравнение работ
В таблице 1 представлено сравнение некоторых аппаратных реализация алгоритма DES. Заметим, что достигнутые результаты конкурентоспособны с существующими выполнениями.
VLSI реализация DES по технологии CMOS 0,6 микрона[8] - самая быстрая выполнение DES, сообщенный в литературе. Используя подход трубопровода, кодирование|шифрование| можно выполнять со скорость ? 6.7 Gbs. FPGA реализации DES, о которых сообщается в литературе достигают пропускной способности от 26 до 10752 Mbits/s использование различного стратегии проекта.
Таблица 1. Параметры реализация алгоритма DES
| Автор | используемая схема | CLB | Частота(MHz) | Скрость(Mbits/s)T |
| Wong et al.[10] | XC4020E | 438 | 10 | 26.7 |
| Kaps and Paar[11] | XC4028EX | 741 | 25.18 | 402.7 |
| Free-DES[12] | XCV400 | 5263 | 47.7 | 3052 |
| McLoony, McCanny [13] | XCV1000 | 6446 | 59.5 | 3808 |
| Sandia Laboratories [8] | ASIC | - | - | 9280 |
| Patterson (Jbits) [14] | XCV150 | 1584 | 168 | 10752 |
| данная работа | XCV400E | 117 | 68.05 | 274 |
Реализация DES| в [12] - бесплатное ядро DES, которое использует подход трубопровода в методе ECB|, достигает скорости передач данных 3052 Mbits/s. Основанная на Java (Jbits) реализация DES [14] достигает самой быстрой скорости кодирования 10752 Mbits/s. Реализация DES в [11] реализует 2-этапный и 4-этапный подходы трубопровода, получая пропускную способность 183.8 Mbits/s и 402.7 Mbits/s соответственно. Почти все FPGA архитектуры DES используют частичный или полный подходы трубопровода. Только проект в [10] содержит один раунд DES в FPGAs. Справедливое сравнение возможно только с этим проектом. Проект осуществлялся на XC4020E, занимающий|оккупирует| 438 блоков CLB. Он требует 24 такта, чтобы завершить кодирование одного блока данных, достигая производительности 26.7 Mbits/s. Коэффициент пропускная способность/площадь равняется 0.06. Наша реализация DES улучшает как площадь, так и пропускную способность, только 165 блоков CLB| на XCV400 и пропускная способность 274 Mbits/s. Коэффициент пропускная способность/площадь для нашего проекта составляет 2.34. Сравнивая нашу архитектуру с проектом в [10], мы получаем увеличение скорости почти в 10 раз, при уменьшенни количества CLB в четыре раза.
5 Заключение
В этой работе, было представлено эффективная и компактная реализация DES на реконфигурируемых элементах. VLSI или выполнение FPGA достигают крайние высокие пропускные способности в зависимости от стратегии проекта. Из Таблицы 1, можно видеться, что наш проект конкурентоспособен, в сравнении с другими представленными аппаратными реализациями алгоритма DES.
Наша архитектура может быть усовершенствована, для получения более высоких результатов производительности. Самое очевидное продолжение, для более высокой производительности, использовать подход трубопровода.