Материал: Разработка аппаратно-программного комплекса для безопасной передачи сообщения, с использованием алгоритмов шифрования и электронно-цифровой подписи

Умножение на {0x02} производится по правилу: если умножаемое меньше {0x80}, оно сдвигается влево на 1 бит. Если больше или равно {80}, то сдвигается влево на 1 бит, а затем к результату применяется операция XOR со значением {0x1b}. Если результат выходит за границы одного байта (то есть значение больше {0xff}), то нужно вернуть остаток от деления на {0x100}.

Умножение на другие константы можно выразить через меньшие константы.

Теперь вернемся к трансформации. Как уже сказано выше, суть трансформации заключается в перемножении каждой колонки с многочленом 3x3 + x2 + x + 2. Данная операция имеет эквивалентную матричную запись (рис. 20). Новый трансформированный столбец получается путем перемножения неизмененного столбца State на матричную запись многочлена (рис. 21).

Рис. 20. Матричная запись перемножения колонки State и фиксированного многочлена.

Рис. 21. Элементы измененного столбца.

()() производит побитовый XOR каждого элемента State с соответствующим элементом RoundKey. RoundKey - это массив, совпадающий размерами с массивом State. Данный массив уникальный для каждого раунда и строится он вспомогательной процедурой KeyExpansion на основе ключа.()

Данная процедура формирует набор ключей для каждого раунда - KeySchedule. KeySchedule - таблица состоящая из Nb*(Nr + 1) столбцов, то есть Nr + 1 блоков, каждый из которых является раундовым ключом (включая ключ для раунда инициализации). Первый блок заполняется секретным ключом по правилу: KeySchedule[r][c] = SecretKey[r + 4c], где r = 0, 1 … 4; c = 0, 1 … Nk. Дальнейшее заполнение таблицы происходит по специальному алгоритму, для которого необходима еще одна константная таблица Rcon (рис. 22):

Так как колонки от 0 до Nk - 1 уже заполнены секретным ключом, работа алгоритма начинается с колонки Nk. Если номер текущей колонки Wiкратен Nk, то:

Выполняем циклический сдвиг влево колонки Wi-1 на один элемент.

Заменяем все элементы той же колонки на соответствующие значения из константной таблицы Sbox.

Выполняем операцию XOR между колонкой Wi-Nk, измененной колонкой Wi-1 и колонкой Rconi/Nk-1.

Результат записывается в колонку Wi.

Если номер текущей колонки не кратен Nk, то:

Выполняем операцию XOR между колонками Wi-Nk и Wi-1.

Записываем результат в колонку Wi.

Данная трансформация самая объемная в реализации. Ключ должен обязательно состоять из 16 элементов (4*Nk, так как ключ 128 бит), поэтому необходимо дополнительно реализовать функцию дозаполнения ключа до необходимого размера на случай, если на вход функции шифрования поступит ключ длиной меньше 16 символов.

Алгоритм шифрования (рис. 11) сообщения полностью состоит из этих трансформаций. За раз может шифроваться только один блок в 128 бит, поэтому, чтобы зашифровать сообщение, которое длиннее 128 бит, необходимо разбить входные данные по блокам в 128 бит и применить алгоритм шифрования к каждому из них.

Рис. 22. Алгоритм шифрования AES-128.

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

Существует такое понятие, как режим шифрования - это метод применения блочного алгоритма, преобразовывающий последовательность блоков исходных данных в блоки зашифрованных данных. Обычно режимы шифрования используются для того, чтобы результат шифрования каждого блока был уникальным. Существует несколько основных режимов. Один из них был описан выше: независимое шифрование каждого отдельного блока. Такой режим называется Electroniccodebook (ECB). Также существуют режимы:(CBC) - режимсцепленияблоков;(PCBC) - режимраспространяющегосясцепленияблоков;(CFB) - режим обратной связи по шифротексту;(OFB) - режим обратной связи по выходу;mode (CTR) - режимсчётчика.

Каждый режим имеет свои достоинства и недостатки. В данной работе будет использован режим шифрования CBC, так как он помогает избежать статических особенностей и скорость обработки блоков постоянна и определяется только эффективностью реализации шифра. Рассмотрим алгоритм работы (рис. 23) этого режима шифрования.

Рис. 23. Алгоритм работы режима шифрования CBC.

Для шифрования сообщения P необходимо выполнить следующие действия:

Сообщение разбивается на блоки одинакового размера. Для данной работы - 128 бит. Если последний блок меньше этой длины, то его необходимо дополнить до нужного размера. Дополнение проходит следующим образом: в конец добавляется единичный бит, а все остальное заполняется нулями. Таким образом возможно найти конец полезных данных.

Каждый Pi блок сообщения шифруется с использованием предыдущего зашифрованного блока Ci-1. Для блока P1 (первого) не существует зашифрованного блока, поэтому для первого блока C0 - это вектор инициализации IV. Вектор инициализации - это случайное число, размером совпадающее с размером блока. Таким образом, шифрование первого блока, будет производиться по правилу: C1 = Ek (P1 ÅIV, k), где Ek - это функция шифрования, а k - это ключ.

Шифрование следующих блоков производится по правилу: Ci = Ek (Pi Å Ci-1, k), где i - номер блока.

Расшифровка выполняется по правилу: Pi = Ci-1 Å Dk (Ci, k), где Dk - функция расшифровки.

Теперь опишем алгоритм шифрования сообщения, учитывая все дополнительные процедуры:

Получаем исходный текст, ключ, вектор инициализации.

Если ключ меньше 16 символов, то выполняем функцию дополнения ключа, если ключ необходимой длины, то переходим к пункту 3.

Разбиваем исходный текст на блоки по 128 бит.

Проверяем, что размер последнего блока 128 бит, если нет, то выполняем функцию дополнения блока.

Шифруем каждый блок исходного текста с учетом предыдущего по алгоритму шифрования AES.

Выводим результат шифрования: Output[r + 4c] = State[r][c], где r = 0, 1 … 4; c = 0, 1 … Nb.

Далее рассмотрим процедуру расшифровки. Чтобы расшифровать сообщение, необходимо использовать инверсные трансформации, от обычных трансформаций они отличаются незначительно.

Работа InvSubBytes() аналогична SubBytes(). Отличие в том, что для замены используется константная таблица InvSbox, представленная на рис. 24.

Рис. 24. Константная таблица InvSbox.

() производит циклический сдвиг вправо. Как и в ShiftRows(), нулевая строка не сдвигается, первая строка сдвигается на один элемент, вторая сдвигается на два элемента и третья строка сдвигается на три элемента.

В трансформации InvMixColumns() перемножение происходит с многочленом {0b}x3 + {0d}x2 + {09}x + {0e}. Матричная форма представлена на рис. 25, итоговые значения представлены на рис. 26.

Рис. 25. Матричная форма перемножения для трансформации InvMixColumns().

Рис. 26. Итоговые значения для InvMixColumns().

Для трансформации AddRoundKey() никаких изменений не требуется, так как трансформация обратна сама себе. Единственное отличие в том, что раундовые ключи необходимо подставлять в обратном порядке.

Рис. 27. Алгоритм расшифровки AES-128.

Выработка общего ключа для шифрования/расшифровки сообщения

Для решения поставленной задачи был выбран протокол распределения ключей Диффи-Хеллмана. Так как для шифрования и расшифровки сообщений выбран симметричный шифр, необходимо создание безопасного канала связи. Реализация данного протокола поможет двум пользователем безопасно получить общий ключ, не передавая между собой секретные данные.

Алгоритм обмена ключами основан на односторонней функции - вычисление по модулю. Основа алгоритма - функция Yx (modP). Обратное преобразование для такой функции почти невозможно. Далее поэтапно опишем алгоритм работы протокола для обеих сторон на примере Алисы и Боба:

Алиса и Боб договариваются о значениях Y и P, либо их вычисляет одна сторона и передает другой. P - простое число, Y - первообразный корень по модулю P.

Алиса выбирает случайное число A и хранит его в тайне. Также Боб выбирает случайное число B и хранит его в тайне.

Алиса подставляет число A в функцию и вычисляет a = YA (modP). Аналогично Боб вычисляет b = YB (modP).

Алиса и Боб обмениваются числами a и b. Это является публичной информацией и может передаваться по незащищенному каналу.

Алиса получает b и вычисляет key = bA (modP). Аналогично Боб вычисляет key = aB (modP).

Оба участника вычислили один и тот же ключ.

Чтобы продемонстрировать, что алгоритм работает и в итоге получается одно и то же число, приведем пример на небольших числах:= 7, P = 11. Функция принимает вид: 7x (mod 11).

A = 3, B = 6.= 73 (mod 11) = 2, b = 76 (mod 11) = 4.= 43 (mod 11) = 9.= 26 (mod 11) = 9.= AlicaKey = BobKey = 9.

Метод передачи данных

Для реализации передачи данных между двумя ПК был выбран протокол TCP. Для программной реализации было использовано пространство имен System.Net.Sockets, которое предоставляет управляемую реализацию сокетов Windows [16]. Из данного пространства имен были выбраны классы TcpListener, TcpClient и NetworkStream. TcpListener отвечает за прослушивание и подтверждение входящих подключений, TcpClient позволяет подключить клиента к удаленному узлу, NetworkStream необходим для организация потока данных.

Для повышения безопасности сессия между двумя ПК завершается сразу после отправки/получения сообщения. Непродолжительное время сессии уменьшает шансы того, что третье лицо успеет произвести вмешательство в обмен данными между двумя ПК.

Решение проблемы имплементации RSA на ПЛИС

Для программирования ПЛИС существует несколько языков программирования. Например, verilog или vhdl. Не все конструкции в Verilog являются синтезируемыми. Синтезируемой конструкцией называется такая конструкция, которую можно представить в виде логических элементов, триггеров, ячеек памяти и так далее. Пример синтеза сумматора с переносом показан на рис. 28.

Рис. 28. Сумматор с переносом.

Конструкция деления и взятия числа по модулю в Verilog не может быть синтезирована. Для этого применяются разнообразные математические алгоритмы. Для основного действия алгоритма RSA (возведение в степень по модулю) необходимо разбить задачу на несколько более простых. Для начала необходимо разобрать алгоритм умножения по модулю. Недостаток большинства алгоритмов в том, что они используют несинтезируемые конструкции Verilog хотя бы раз.

Алгоритм Монтгомери позволяет ускорить выполнение операций умножения и возведения в квадрат, которые необходимы для возведения в степень по модулю, когда модуль очень большой (около нескольких сотен бит). По введенным целым числам a,b<n, r, НОД(r, n) = 1 алгоритм Монтгомери вычисляет MonPro(a,b) = a * b * r-1modn. Положим r = 2k. Определим n-остаток числа a<nкак ā = a * r mod n. Алгоритм Монтгомери использует свойство, что множество {a * r mod n | 0 ≤ a ≤ n - 1} является полной системой вычетов, то есть содержит все числа от 0 до n-1. MonPro вычисляет . Результат является n-остатком от

, так как.

Определим n' так, что. r-1и n' можно вычислить с помощью расширенного алгоритма Евклида. Функция  показана на рис. 29. Операции умножения производятся довольно быстро, потому что при r = 2k они являются просто сдвигами регистров бит. Поэтому умножение по Монтгомери быстрее обычного вычисления умножения по модулю. Однако применять алгоритм для однократного произведения двух чисел является нерациональным.

Рис. 29. Умножение по Монтгомери.

Алгоритм Монтгомери для умножения по модулю оправдывает себя для возведения чисел в степень по модулю. Алгоритм показан на рис. 30.

Рис. 30. Возведение в степень по модулю по Монтгомери

Алгоритм Монтгомери для ПЛИС неоправдан, так как в промежуточные вычисления требуют синтезируемых конструкций взятия числа по модулю.

В данной работе использовался двоичный алгоритм умножения и взятия остатка. Он хорошо ложится на ПЛИС, так как состоит полностью из синтезируемых конструкций. Алгоритм показан на рис. 31. Для современных ЭВМ этот метод имеет недостаток. Недостаток заключается в том, что алгоритм не использует многобитовую арифметику. Но для ПЛИС это скорее преимущество, так как увеличивает частоту, с которой синтезируется проект.

Рис. 31. Алгоритм умножения и взятие остатка.

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

Рис. 32. Алгоритм возведения в степень по модулю.

Рис. 33. Пример работы алгоритма.

Универсальный асинхронный приемопередатчик

В данной работе для приема сообщений с ПК(1) был реализован прием из последовательного порта. Так как предполагается, что ПК(1) и ПЛИС стоят в одной комнате, то нужды в дополнительной реализации более сложного приемника, например Ethernet, нет. UART предназначен для связи между цифровыми устройствами, очень широко используется в системах на кристаллах, таких как микроконтроллеры, бмк, микропроцессоры, ПЛИС.

Передача по UART происходит последовательно по одному биту в одинаковые промежутки времени. Эти промежутки определяются заранее заданной скоростью и измеряется в бодах (количество передаваемых бит в секунду). Кроме битов данных, в UART используются стартовый и стоповый биты. Сначала передается стартовый бит (равен логическому нулю), затем передаются 8 бит данных, а затем передается стоповый бит (равен логической единице). Формат кадра UART показан на рис. 34.

Рис. 34. Форматкадра UART.

Ethernet MAC

Структура подключения ПЛИС с ПК по Ethernet

В данной работе связь ПК(2) и ПЛИС по Ethernet реализована через трансивер, который подключается оптоволоконным кабелем через патчкорд к медиаконвертеру, который, в свою очередь, подключается кабелем RJ-45 к сетевой плате компьютера, поддерживающей скорость, равной 1 Гбит в секунду.

Медиаконвертер - это устройство, которое преобразует информацию, поступающую из оптических кабелей в медные и наоборот. В данной работе использовался медиаконвертер D-LinkDMC-G01LC.

уровень в ПЛИС

Основной задачей являлось установить связь (линк) между ПЛИС и ПК. Для этого необходимо реализовать MAC уровень только в ПЛИС, так как в сетевых картах он уже реализован и готов к работе. Канальный уровень необходим для передачи данных между узлами локальной сети. Он отвечает за доставку кадров между различными сетевыми устройствами. Заголовок кадра, передаваемого между узлами локальной сети, содержит в себе аппаратные (MAC) адреса получателей и отправителей, что позволяет точно определить, какое устройство послало/приняло тот или иной кадр. Согласно стандарту IEEE 802 канальный уровень разделяется на два уровня: MAC уровень (регулировка доступа к физической среде), LLC уровень (обслуживание сетевого уровня).