МОДЕЛИРОВАНИЕ ФОРМИРОВАТЕЛЯ ЧАСТИЧНЫХ ОСТАТКОВ УСТРОЙСТВА ПРИВЕДЕНИЯ ПО МОДУЛЮ
Әділбеккызы Сайран1
Айтхожаева Евгения Жамалхановна2
Тынымбаев Сахыбай3
1Магистр военного дела и безопасности, инженер
2Канд. техн. наук, ведущий научный сотрудник
3Канд. техн. наук, научный руководитель проекта
Алматинский Университет Энергетики и Связи, г.Алматы, Казахстан
АННОТАЦИЯ
Разрабатывается структура быстродействующего устройства приведения по модулю с оптимальными аппаратными затратами. Выполняется разработка принципиальной схемы устройства в САПР Quartus Prime Lite Edition. Приводятся результаты моделирования формирователя частичных остатков — основного блока устройства приведения по модулю. Временное моделирование устройства подтверждает его высокое быстродействие: FMAX=68,77МГц.
ABSTRACT
A structure for a high-speed modular reduction device, which has optimal hardware costs, is being developed. The schematic diagram of the device is implemented in CAD Quartus Prime Lite Edition. The simulation results of the partial remainder former that is the main unit of the device for modular reduction, are presented. The time modeling of the device confirms its speed: FMAX = 68.77 MHz.
Ключевые слова: асимметричный криптоалгоритм, приведение по модулю, моделирование.
Keywords: asymmetric cryptoalgorithm, modular reduction, simulation.
Введение. Аппаратное шифрование имеет ряд существенных преимуществ перед программным шифрованием, одним из которых является более высокое быстродействие. Проектирование и реализация оптимальных схемных решений одной из базовых операций асимметричного криптоалгоритма RSA – приведения чисел по модулю, является актуальной задачей в связи с широким применением на практике данного алгоритма и его низким быстродействием по сравнению с симметричными алгоритмами. Последнее обстоятельство сдерживает применение асимметричных криптосистем, несмотря на такое их преимущество, как отсутствие необходимости распространения секретных ключей, что является недостатком симметричных криптосистем.
Приведение по модулю является наиболее затратной операцией по времени по сравнению с другими используемыми операциями в алгоритме RSA, чем и объясняется повышенный интерес к созданию быстродействующих устройств приведения по модулю.
Основная часть. Имеется большое количество публикаций, в том числе и патентов, в которых предлагаются различные алгоритмы и устройства приведения по модулю [1-4]. Большинство предлагаемых решений является неприемлемыми при реализации алгоритма RSA, так как при его реализации необходимо выполнять сложные и громоздкие математические вычисления над очень большими (многоразрядными) числами, что приводит к большим аппаратным затратам. В [5] был предложен метод на основе модификации и адаптации машинного деления двоичных чисел и разработана структурно-функциональная схема нового быстродействующего устройства приведения 2n-разрядного числа А по n-разрядному модулю P (R=A mod P) с оптимальными аппаратными затратами. Повышение быстродействия устройства достигается путем сдвига остатков на два разряда влево для уменьшения тактов выполнения операции приведения по модулю. На рисунке 1 приведена структура данного устройства с выделением основных составляющих блоков.
На управляющий блок поступают сигналы Сброс, Пуск, тактовые импульсы (ТИ), K=n/2 (n – разрядность модуля P, n/2 — определяет число тактов, необходимых для выполнения операции приведения по модулю).
В блоке формирователя кратных модуля Р предварительно вычисляются прямые и обратные (для выполнения в дальнейшем операции вычитания) коды удвоенного и утроенного модуля (2р и 3р).
Рисунок 1. Структура устройства быстрого приведения чисел по модулю
Затем, в блоке формирователя частичных остатков (ФЧО), в первом такте определяются старшие разряды частичного остатка путем вычитания в дополнительном коде р или сформированных кратных модуля (2р или 3р) из сдвинутого на два разряда вправо приводимого числа А, т.е. увеличенного в 4 раза. Используются (n+2) старших разрядов (обозначено далее 4r0) сдвинутого на два разряда вправо 2n-разрядного числа А, которые подаются на ФЧО.
В состав ФЧО входят сумматор, логические элементы И и ИЛИ, мультиплексор и три схемы сравнения, которые используются для определения операции, которую необходимо выполнить на сумматоре, чтобы определить значение старших разрядов очередного остатка (ri): вычитание p, или 2p, или 3p.
Полученный очередной остаток ri, при наличии сигнала переноса П =1 из старшего разряда сумматора, записывается в старшие разряды регистра сдвига A (блок регистра сдвига). И в последующих тактах вычитание p, или 2p, или 3p выполняется из (n+2) старших разрядов сдвинутого на два разряда имеющегося числа в регистре сдвига A (полученного частичного остатка ri и следующих двух разрядов).
Пример работы устройства.
Пусть n=6, 2n=12, n+2=8, n/2=3.
Приводимое число А=63810=0010011111102 записывается в блоке регистра сдвига в РгА=00.0010011111102. Здесь, и в дальнейшем, точкой отделены 2 старших дополнительных разряда.
Значение модуля Р=3510=1000112 записывается в блоке формирователя кратных модуля Р в РгР в прямом коде [p]пр=00.1000112. В этом же блоке формируются кратные модуля Р: [2p]пр=01.0001102=7010, [3p]пр=01.1010012=10510. Здесь для обозначения прямого кода модуля р используется обозначение [p]пр, обратного кода модуля используется обозначение [p]обр, а для обозначения дополнительного кода используется обозначение [p]доп. При Р=3510=1000112: [p]обр=11.0111002, [2p]обр=10.1110012, [3p]обр=10.0101102 , [p]доп=11.0111012, [2p]доп=10.1110102, [3p]доп=10.0101112.
Вычисления по определению остатка R=A mod P приведены для наглядности в двоичной и десятичной системах счисления в таблице 1, в которой старшие разряды частичных остатков, получаемые в ФЧО, обозначены через ri . Нумерация разрядов регистров выполняется справа налево, начиная с нуля.
Для определения правильности работы устройства было выполнено моделирование разработанного устройства приведения по модулю. В качестве среды для проектирования и отладки проекта был использован программный продукт фирмы Altera – САПР Quartus Prime Lite Edition, который позволяет построить принципиальную и поведенческую модели устройства и проверить его работоспособность с иллюстрацией на временных диаграммах, а также получить временные характеристики моделируемого устройства. Среда проектирования позволяет запустить функциональное и временное моделирование. Функциональное моделирование проекта позволяет проверить правильность работы цифрового устройства с точки зрения логики и схемотехники. Временное моделирование проекта позволяет проверить не только правильность логического функционирования, но и работу с учетом задержки распространения сигналов в реальной программируемой логической интегральной схеме.
Таблица 1.
Порядок вычисления R = A mod P
| Тактовые импульсы | Выполняемые операции |
| ТИ1 | 4r0=00.1001112=3910 (после сдвига влево на 2 разряда старшие 8 разрядов РгА). Так как 35<39<70 (p<4r0<2p), схемами сравнения с помощью мультиплексора вырабатывается сигнал на вычитание p. На сумматоре в ФЧО выполняется операция:
[4r0]пр = 00.100111 [p]доп = 11.011101 r1= 00.000100 Сигнал переноса из старшего разряда сумматора П=1, поэтому r1 перезаписывается в старшие разряды РгA(13÷6):= 00.0001002 = 410 |
| ТИ2 | 4r1=00.0100112=1910 (после сдвига влево на 2 разряда старшие 8 разрядов РгА). Так как 4r1<p, схемами сравнения не вырабатывается сигнал на вычитание.
Сигнал переноса П=0, поэтому РгA(13÷6):= 00.0100112 = 1910 остается без изменения. |
| ТИ3 | 4r2=01.0011102=7810 (после сдвига влево на 2 разряда старшие 8 разрядов РгА). Так как 70<78<105 (2p<4r2<3p), схемами сравнения вырабатывается сигнал на вычитание 2p. На сумматоре ФЧО выполняется операция:
[4r2]пр = 01.001110 [2p]доп= 10.111010 r3= 00.0001000 Сигнал переноса из старшего разряда сумматора П=1, поэтому r3 перезаписывается в старшие разряды РгA(13÷6):=00.0010002 = 810. Конечный результат R=00.0010002 = 810 Проверка: |
Проектирование устройства было выполнено с ориентацией на низкобюджетную плату DE0-CV с программируемой логической интегральной схемой FPGA семейства Cyclone VE base, выпускаемой фирмой Altera – 5CEBA4F23C7.
Разработка принципиальной схемы устройства выполнялась поэтапно по блокам с проверкой их работы для разрядности n=6. Ниже показана реализация основного блока ФЧО, для которого первоначально были спроектированы его составляющие: сумматор, мультиплексор и три схемы сравнения. А также были использованы логические элементы И и ИЛИ.
Для реализации схем сравнения были использованы интегральные схемы серии 7400, включенные в библиотеку Altera Quartus Prime ‘/others/maxplus2/’ – 7485 (4-битный компаратор). Графический файл 8-разрядной схемы сравнения показан на рисунке 2.
Рисунок 2. Схема 8-разрядного компаратора (схемы сравнения)
Для создания сумматора был использован 4-битный сумматор – 74283 из серии интегральных схем 7400, включенных в библиотеку Altera Quartus II ‘/others/maxplus2/’. Графический файл 8-разрядного сумматора показан на рисунке 3. Были также спроектированы и другие компоненты ФЧО.
Были получены символ-модули разработанных компонентов ФЧО и с их использованием был собран блок ФЧО (FPR), принципиальная схема которого представлена на рисунке 4. В принципиальной схеме ФЧО были использованы:
символ модуля регистра РгР (1), символ модуля сумматора для получения 3р (2), символ модуля блока логических элементов И для подачи на вычитающий сумматор старших восьми разрядов из РгА (3), символ модуля схемы сравнения сдвинутого полученного остатка с р (4), символ модуля схемы сравнения сдвинутого полученного остатка с 2р (5), символ модуля схемы сравнения сдвинутого полученного остатка с 3р (6), символ модуля мультиплексора для подачи на вычитающий сумматор р или 2р или 3р (10), символ модуля вычитающего сумматора определения старших разрядов частичного остатка — ri (11). Логические элементы И (7,8) и логический элемент ИЛИ (9) используют результаты схем сравнения и служат для выработки управляющих сигналов, подаваемых на мультиплексор (10), которые определяют подачу на вычитающий сумматор или р, или 2р, или 3р.
Рисунок 3. Схема 8-разрядного сумматора
Рисунок 4. Схема 8-разрядного ФЧО с использованием символ-модулей
Были получены временные диаграммы работы ФЧО, фрагмент которых приведен на рисунке 5.
В качестве входных данных были использованы параметры из примера, приведенного в таблице 1: Р=3510=1000112, 4r0=3910=00.10001112. Как видно на временной диаграмме, результат сложения в вычитающем сумматоре (r1=410=00.000001002) соответствует значению r1 из примера.
Рисунок 5. Временные диаграммы работы 8-разрядного ФЧО
Заключение. Реализация устройства приведения по модулю была выполнена полностью в Quartus Prime Lite Edition и получены его временные характеристики.
Анализ временных характеристик показал, что принципиальная модель устройства будет работать медленнее в режиме Slow при напряжении 1100 mV и температуре 85℃ (модель работы в худших условиях). Максимальная тактовая частота при этом FMAX=32,91МГц. А в нормальных условиях работы максимальная тактовая частота составляет для принципиальной модели FMAX=68,77МГц. Тактовая частота существующих специальных процессоров RSA составляет от 5МГц до 30МГЦ, что намного меньше, чем тактовая частота разработанного устройства быстрого приведения чисел по модулю [6].
Список литературы:
1. Ковтун М., Ковтун В. Обзор и классификация алгоритмов деления и приведения по модулю больших целых чисел для криптографических приложений. [Электронный ресурс]. URL: https://docplayer.ru/30671408-Obzor-i-klassifikaciya-algoritmov-deleniya-i-privedeniya-po-modulyu-bolshih-celyh-chisel-dlya-kriptograficheskih-prilozheniy.html.
2. Устройство для формирования остатка по произвольному модулю от числа: пат. 2445730 Рос. Федерация: МПК H03M 7/18, G06F 7/72 / Копытов В.В., Петренко В.И., Сидорчук А.В.; заявитель и патентообладатель ГОУ ВПО Ставропольский государственный университет. – №2010106685/08; заявл.24.02.2010; опубл.27.08.2011, Бюл. №24 – 8 c.
3. Формирователь остатка по произвольному модулю от числа: пат. 30983 Рес. Казахстан: МПК G06F 7/72 H03M 7/18 /Айтхожаева Е.Ж., Тынымбаев С.Т.; заявитель и патентообладатель РГП на ПХВ «Казахский национальный технический университет им. К.И. Сатпаева» МОН РК . — №2014/1450.1; заявл. 05.11.2014; опубл. 15.03.2016, –5 c.
4. Adilbekkyzy S., Aitkhozhayeva E., Tynymbayev S. Analysis of devices structures for modular reduction. Proc. 16th International Scientific Conference «Information Technologies and Management» Riga, -2018. p. 97-98.
5. Tynymbayev S., Aitkhozhayeva Y. Zh., Adilbekkyzy S. High speed device for modular reduction: Bulletin of National Academy of Sciences of the Republic of Kazakhstan, №6 (2018). — Алматы: Наука, 2018. — с.147-152. ISSN: 1991-349421. DOI: 10.32014/2018.2518-1467.38.
6. Алгоритм шифрования RSA. Криптоанализ алгоритма RSA. Конспект лекций. [Электронный ресурс]. URL: https://en.ppt-online.org/97398.