Разработка аппаратной реализации блочного шифра

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

Введение

Исходные данные

1. Общий раздел

1.1 Основные требования к блочным шифрам

1.2 Блочные шифры на основе SP-сети

1.3 Основные операции, используемые в блочных шифрах

2 Разработка аппаратной реализации блочного шифра

2.1 Синтез логической схемы таблицы подстановки

2.2 Синтез схемы логического устройства, реализующего операцию перестановки

2.3 Разработка структурной схемы одного раунда шифрования

2.4 Синтез логической схемы блока управления

Заключение

Список используемой литератур

Приложение А. Чертёж логической схемы таблицы подстановки

Приложение B. Чертёж логической схемы функции перестановки

Приложение C. Чертёж логической схемы блока управления

Введение

Шифрование с использованием блочного шифра обеспечивает конфиденциальность информации путём преобразования открытых сообщений в безопасные шифрованные сообщения, где конкретное преобразование, реализуемое блочным шифром, определяется секретным ключом. Этот секретный ключ (или набор ключей) известен только законным пользователям. Тогда как поточные шифры имеют память, заключенную в их внутреннем состоянии, блочные шифры не имеют памяти вне конкретного блока и таким образом не имеют внутреннего состояния.

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

Шифрование при помощи блочного шифра является одной из наиболее известных форм симметричного шифрования - слово симметричный отражает тот факт, что отправитель и получатель шифрованных сообщений должны знать секретный ключ. Множество идей, которые предшествовали созданию современных блочных шифров, были представлены в работе К.Шеннона в 1949 году. Он первый предложил концепции запутывания (confusion) и перемешивания (diffusion), которые являются основным критерием проектирования для любого разрабатываемого блочного шифра. За последние тридцать лет получили значительное развитие криптография и теория информации, в результате чего появилось множество правил разработки блочных шифров, которые опробованы и приняты в криптографическом сообществе. Тем не менее, в настоящее время не существует доказуемо стойких блочных шифров.

Исходные данные

Исходные данные:

длина блока - 64 бит;

количество раундов - 8 ;

тип структуры блочного шифра - SP-сеть;

размерность таблиц подстановок - 4 бита .

1. Общий раздел

1.1 Основные требования к блочным шифрам

Целью шифрования является обеспечение того, чтобы было практически невозможным получение открытой информации из шифрованной без знания секретного K-битного ключа. Расшифровывание возможно только если функция шифрования является обратимой (т.е., бийективной - bijection).

Теоретически, с точки зрения безопасности, идеальный блочный шифр должен представлять собой одну, очень большую и хорошо выбранную N-битную таблицу подстановки, зависящую от K-битного ключа. В идеале, должно быть невозможным осуществить декомпозицию этой таблицы подстановки на более маленькие составные части. Однако это сразу приводит к большой сложности его реализации. В отличие от этого, современные блочные шифры используют комбинирование относительно маленьких составных частей, обеспечивающих запутывание (confuse) и диффузию (diffuse).

1.2 Блочные шифры на основе SP-сети

SP-сеть представляет собой структуру, в которой для преобразования данных (шифрования) поочередно используются операции подстановки (S - substitution) и перестановки (P - permutation). На рисунке 1 приведен пример блочного шифра на базе SP-сети.

В данном примере входное сообщение M длиной 8 бит разбивается на отдельные слова длиной 2 бита. Эти слова смешиваются с подключами при помощи операции XOR (исключающего ИЛИ) и далее подаются на соответствующие таблицы подстановки. С выхода таблиц подстановок преобразованные слова поступают на вход 8-и битной операции перестановки. После этого полученные данные поступают на следующий раунд шифрования.

Таблицы подстановки S обеспечивают нелинейность (сложность) преобразования данных, т.е. вносят путаницу (confusion) в процесс преобразования данных. Функции перестановки P обеспечивают перемешивание (diffusion) бит внутри блока данных, вследствие этого в следующем раунде шифрования на вход одной таблицы подстановки будут подаваться значения с выходов нескольких таблиц подстановок предыдущего раунда шифрования.

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



Рисунок 1 - Пример блочного криптоалгоритма на базе SP-сети

1.3 Основные операции, используемые в блочных шифрах

Перестановки (Permutations)

Операция перестановки (permutation) заключается в изменении позиции бит внутри обрабатываемого сообщения по заданному закону. На рисунке 2 приведено обозначение и пример операции перестановки. В данном случае введены следующие обозначения: M - открытое сообщение; M' - преобразованное сообщение; n - длина сообщения в битах; - соответствующие биты входного и выходного сообщений. Частным случаем операции перестановки являются операции циклического сдвига.

а) обозначение операции перестановки

б) пример операции перестановки

Рисунок 2 - Функция (операция) перестановки

Перестановка может быть как фиксированной, так и задаваться ключом (рисунок 3). Рассмотрим пример определения структуры неизвестной операции перестановки, задаваемой ключом. Для этого на вход функции перестановки подаются специально подобранные входные сообщения, которые затем анализируются. В данном случае (рисунок 3а) на вход подается сообщение 0001 и отслеживается выход, на котором появляется единица. Соответственно определяется часть операции перестановки (рисунок 3б). Далее на вход подается сообщение 0010 и отслеживается выход, на котором появляется единица (рисунок 3в) и т.д. Таким образом, для полного определения структуры неизвестной перестановки требуется максимум 4-е специально подобранные сообщения и выполнение 4-х операций перестановки.

Из этого следует, что сама по себе операция перестановки не является криптографически стойкой. Для сравнения, полное определение неизвестной булевой функции от 4-х переменных требует подачи на вход функции 16 кодовых комбинаций () и считывания 16-и выходных значений.

Рисунок 3 - Функция (операция) перестановки, задающаяся ключом

Рисунок 4 - Принцип определения структуры неизвестной операции перестановки

Однако, данную операцию легко реализовать для обработки блоков данных произвольной размерности (например, 128 или 256 бит). В совокупности с операциями подстановки, размерность которых в современных криптоалгоритмах не превышает 9-и бит, операция перестановки позволяет создавать криптографически стойкие шифры.

Подстановки (Substitutions)

Операция подстановки (substitution) заключается в замене входного значения (кодовой комбинации) на соответствующее выходное значение. Соответствие задаётся таблицей подстановки. Обычно реализация таблицы подстановки является общеизвестной и входит в спецификацию криптографического алгоритма. На рисунке 4 приведено обозначение и пример операции подстановки. В данном случае введены следующие обозначения: M - открытое сообщение; M' - преобразованное сообщение; n - длина сообщения в битах.

а) обозначение операции подстановки

Вход	Выход
(0) 00	(2) 10
(1) 01	(1) 01
(2) 10	(0) 00
(3) 11	(3) 11

б) пример 2-х битовой операции подстановки

Рисунок 5 - Функция (операция) подстановки

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

В идеальном случае весь блочный шифр можно представить одной большой таблицей подстановки, сформированной случайным образом. Однако здесь встаёт вопрос о затрачиваемых аппаратных ресурсах. Например, для хранения таблицы подстановки размерностью 8 бит требуется бит, т.е. 2048 бит. Для таблицы подстановки размерностью 16 бит это значение будет равным , т.е. 1048576 бит. Для минимизации аппаратных затрат размерность функции подстановки в современных криптоалгоритмах обычно составляет 4 или 8 бит.

Использование только таблиц подстановки, имеющих небольшую размерность, позволяет применить принцип «разделяй и властвуй». Например, определить используемые подключи для структуры, приведенной на рисунке 5. не составляет труда. Для этого необходимо формировать входные сообщения, подобранные для анализа отдельных таблиц подстановок. Например, для анализа S0 формируются сообщения вида

00.00.00.00

01.00.00.00

10.00.00.00

11.00.00.00

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

10.01.10.10

01.01.10.10

11.01.10.10

00.01.10.10

Как видно, для определения одной таблицы подстановки требуется знать 4 пары «открытое сообщение - зашифрованное сообщение». Для полного определения указанного шифра необходимо всего или 16 подобранных входных сообщений (вне зависимости от количества раундов шифрования). В противовес этому, для определения стойкого преобразования необходимо знать , или 256 пар «открытое сообщение - зашифрованное сообщение».

Рисунок 6 - Структура шифра при использовании только операций подстановки

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

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

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

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

2. Разработка аппаратной реализации блочного шифра

2.1 Синтез логической схемы таблицы подстановки

Сформируем случайным образом 4-х битную таблицу подстановки, используя для этого программу «GeneratorSboxes». Для этого зададим параметры формирования: разрядность таблицы в битах - 4, количество перестановок - 1000. После нажатия кнопки «Generate random Sbox» во вкладке «Таблица подстановки» получаем искомые выходные значения, рисунок 7.

Рисунок 7- Искомые выходные значения

Получена таблица 1. подстановки следующего вида (в скобках указаны десятичные эквиваленты):

Таблица 1.

Вход (4 бит)	Выход (4 бит)
X0	X1	X2	X3	F0(x)	F1(x)	F2(x)	F3(x)
(0) 0	0	0	0	0	0	0	0 (0)
(1) 0	0	0	1	0	0	0	1 (1)
(2) 0	0	1	0	0	0	1	0 (2)
(3) 0	0	1	1	0	1	1	0 (6)
(4) 0	1	0	0	0	1	0	0 (4)
(5) 0	1	0	1	1	1	0	1 (13)
(6) 0	1	1	0	0	0	1	1 (3)
(7) 0	1	1	1	0	1	1	1 (7)
(8) 1	0	0	0	1	0	0	0 (8)
(9) 1	0	0	1	1	0	0	1 (9)
(10) 1	0	1	0	0	1	0	1 (5)
(11) 1	0	1	1	1	1	1	1 (15)
(12) 1	1	0	0	1	1	0	0 (12)
(13) 1	1	0	1	1	0	1	0 (10)
(14) 1	1	1	0	1	1	1	0 (14)
(15) 1	1	1	1	1	0	1	1 (11)

Минимизируем логические выражения для функций , , , , используя метод карт Карно.

Карта Карно для имеет вид:

X2X3
X0X1		00	01	11	10
	00	0	0	0	0
	01	0	1	0	0
	11	1	1	1	1
	10	1	1	1	0

В соответствии с выбранными контурами выписываем элементарные конъюнкции:

1100	1100	0101
1101	1101	0101
1111	1111
1000	1110
1001
1011
x0|x2x3	x0x1- -	|x0x1|x2x3

Суммируя элементарные конъюнкции получаем минимизированное логическое выражение:

F0(X)=x0|x2x3+x0x1+|x0x1|x2x3

Карта Карно для имеет вид:

X2X3
X0X1		00	01	11	10
	00	0	0	1	0
	01	1	1	1	0
	11	1	0	0	1
	10	0	0	1	1

В соответствии с выбранными контурами выписываем элементарные конъюнкции:

0100	0100	0011	1011	1110
0101	1100	0111	1010	1010
|x0x1|x2 -	- x1|x2|x3	|x0 - x2x3	x0|x1x2 -	x0 - x2|x3

Суммируя элементарные конъюнкции получаем минимизированное логическое выражение:

F1(X)= |x0x1|x2+ x1|x2|x3+|x0x2x3+ x0|x1x2+ x0x2|x3

Карта Карно для имеет вид:

X2X3
X0X1		00	01	11	10
	00	0	0	1	1
	01	0	0	1	1
	11	0	1	1	1
	10	0	0	1	0

В соответствии с выбранными контурами выписываем элементарные конъюнкции:

блочный шифр логистический

0011	0011	1101
0010	0111	1111
0111	1111
0110	1011
1111
1110
|x0x1x2 -	- -x2x3	x0x1-x3

Суммируя элементарные конъюнкции получаем минимизированное логическое выражение:

F2(X)= |x0x1x2+ x2x3+ x0x1x3

Карта Карно для имеет вид:

X2X3
X0X1		00	01	11	10
	00	0	1	0	0
	01	0	1	1	1
	11	0	0	1	0
	10	0	1	1	1

В соответствии с выбранными контурами выписываем элементарные конъюнкции:

0001	0111	1111	1001	1011
0101	0110	1011	1011	1010
|x0-|x2x3	|x0x1x2	x0-x2x3	x0|x1-x3	x0|x1x2-

Суммируя элементарные конъюнкции получаем минимизированное логическое выражение:

F3(X)= |x0|x2x3+|x0x1x2+x0x2x3+x0|x1x3+x0|x1x2

Для составления схемы логического устройства используем следующую последовательность действий:

1) с левой стороны схемы зададим все переменные, входящие в логическое выражение;

2) при помощи логических элементов НЕ зададим инверсии заданных переменных;

3) логическими элементами И зададим элементарные конъюнкции заданной булевой функции;

4) выходы логических элементов И подключим ко входам логического элемента ИЛИ. При этом выход логического элемента ИЛИ будет служить выходом всей схемы, реализующей заданную логическую функцию.

В соответствии с приведенным алгоритмом составим схемы логических устройств, реализующих выходы заданной таблицы подстановки.

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



Рисунок 8 - Схема логического устройства, реализующего таблицу подстановки S

2.2 Синтез схемы логического устройства, реализующего операцию перестановки

Операция перестановки (permutation) заключается в изменении позиции бит внутри обрабатываемого сообщения по заданному закону.

В нашем случае необходимо получить функцию перестановки, имеющую размерность входа и выхода, равную 64 бит. Данную функцию также можно сформировать использовав программу «GeneratorSboxes». Для этого необходимо задать параметры формирования: разрядность таблицы в битах - 6, количество перестановок - 1000. После нажатия кнопки «Generate random Sbox» во вкладке «Таблица подстановки» получаем искомые выходные значения.

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

Таблица 2.

00 -> 63 01 -> 15 02 -> 18 03 -> 5 04 -> 52 05 -> 43 06 -> 47 07 -> 27 08 -> 46 09 -> 13 10 -> 33 11 -> 8 12 -> 7	13 -> 45 14 -> 55 15 -> 34 16 -> 20 17 -> 57 18 -> 10 19 -> 33 20 -> 40 21 -> 11 22 -> 60 23 -> 61 24 -> 21 25 -> 49	26 -> 51 27 -> 31 28 -> 42 29 -> 29 30 -> 38 31 -> 0 32 -> 50 33 -> 3 34 -> 54 35 -> 2 36 -> 30 37 -> 16 38 -> 36	39 -> 9 40 -> 35 41 -> 28 42 -> 58 43 -> 62 44 -> 44 45 -> 1 46 -> 17 47 -> 24 48 -> 53 49 -> 56 50 -> 59 51 -> 25	52 -> 19 53 -> 26 54 -> 41 55 -> 4 56 -> 12 57 -> 37 58 -> 22 59 -> 32 60 -> 39 61 -> 14 62 -> 23 63 -> 48

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

Рисунок 9 - Схема логического устройства, реализующего операцию перестановки

2.3 Разработка структурной схемы одного раунда шифрования

В соответствии с заданием имеем следующие параметры одного раунда шифрования:

· размер обрабатываемого блока информации - 64 бит;

· длина слова (размерность таблицы подстановки) - 4 бит;

· количество слов в блоке - 16.

На основании этих данных и в соответствии с рисунок 1 получаем структурную схему одного раунда шифрования на основе SP-сети (рисунок 10).

Рисунок 10 - Структурная схема одного раунда шифрования

Данная схема работает следующим образом. Входное сообщение M длиной 64 бит разбивается на 16 слов , по 4 бит каждое. Эти слова смешиваются с требуемыми раундовыми подключами при помощи операции XOR (исключающего ИЛИ) и далее подаются на соответствующие 4-х битные таблицы подстановки. С выхода таблиц подстановок преобразованные 4-х битные слова поступают на вход 64-х битной операции перестановки. После этого полученные данные поступают на следующий раунд шифрования или, если последний раунд, на выход блочного шифра.

Входное сообщение	Раундовые ключи	Операция XOR	Данные после таблицы перестановки
M0	0001	K15	0110	0111	s	0110
M1	0101	K14	1101	1000	s	0100
M2	0111	K13	0000	0111	s	0110
M3	0100	K12	0010	0110	s	1110
M4	0010	K11	0100	0110	s	1110
M5	1010	K10	0101	1111	s	1010
M6	1000	K9	0111	1111	s	1010
M7	0011	K8	1011	1000	s	0100
M8	1001	K7	1110	0111	s	0110
M9	1101	K6	0001	1100	s	1011
M10	1111	K5	1001	0110	s	1110
M11	1110	K4	1000	0110	s	1110
M12	1100	K3	1111	0011	s	1100
M13	0000	K2	1010	1010	s	0001
M14	1011	K1	0011	1000	s	0100
M15	0110	K0	1100	1010	s	0001

2.4 Разработка схемы логического устройства, реализующего блок управления

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



Рисунок 11 - Состав и назначение функций схемы управления

В соответствии с логикой работы схемы шифрования зададим эти сигналы следующим образом:

· - по этому сигналу производиться перезапись информации с Регистра 1 на вход раунда шифрования (через Мультиплексор 1). Пусть этот сигнал будет активным при выполнении всех раундов шифрования, в остальных случаях будет пассивным;

· - этим сигналом осуществляется управление Мультиплексором 1, который обеспечивает циклическую работу схемы шифрования. Пусть в первом раунде шифрования этот сигнал будет активным, а в остальных - пассивным;

· - по данному сигналу Регистр 2 осуществляет перезапись результатов шифрования текущего раунда на вход следующего раунда шифрования (через Мультиплексор 1). Если принять, что один раунд преобразования осуществляется за один тактовый импульс, то пусть сигнал будет активным каждый импульс тактирования;

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

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

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

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

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

Пусть нам задан блочный шифр, имеющий 8 раундов шифрования (с 0 по 7). Следовательно, нам необходим 4-х разрядный счётчик () с управляемым сбросом. Пусть - выходы счётчика (старший бит ), а - тактовый импульсы (импульсы синхронизации). Сброс счётчика осуществляется при пассивном сигнале . При счётчик должен начать свою работу.

При появлении на выходе счетчика комбинации (что соответствует первому раунду шифрования) должны формироваться сигналы , в остальных случаях . В этом случае, в соответствии с ДНФ . Для данного выражения имеем следующую логическую схему:

Сигнал по своей сути повторяет сигнал , т.е. .

При появлении на выходе счетчика комбинации (что соответствует последнему раунду шифрования, т.к. число 8 в двоичной системе счисления имеет вид 1000) должны формироваться сигналы , в остальных случаях .В этом случае, в соответствии с ДНФ .Для данного выражения имеем следующую логическую схему:

Дополнительно необходимо предусмотреть возможность останова счётчика при осуществлении всех раундов шифрования, а также его запуска после подачи сигнала запуска .

Выберем типовую схему счётчика, например, на основе D-триггера с динамическим управлением (рис . 12 ).



Рисунок 12 - Логическая схема 3-х разрядного счётчика на основе D-триггера с динамическим управлением

В данной схеме каждый D-триггер выступает в роли делителя на два. В результате первый триггер делит частоту (увеличивает период) тактовых импульсов на два, второй триггер на четыре, третий триггер на восемь. Таким способом можно построить счётчик произвольной разрядности.

Для того, чтобы счётчик работал в режиме прямого счёта, необходимо в качестве выходных сигналов брать сигналы с инверсных выходов D-триггеров.

На основании всего вышеуказанного составим логическую схему блока управления , которая представлена на чертеже приложение С .

Заключение

В ходе выполнения данной курсовой работы была сформированна случайным образом 4-х битная таблица подстановки, используя для этого программу «GeneratorSboxes». А также была получена функцию перестановки, имеющая размерность входа и выхода, равную 64 бит. В результате этого, после осуществления требуемого количества раундов шифрования каждый бит получившейся криптограммы С становится зависимым сложным образом от каждого бита входного сообщения. В данном примере входное сообщение M длиной 8 бит разбивается на отдельные слова длиной 2 бита. Эти слова смешиваются с подключами при помощи операции XOR (исключающего ИЛИ) и далее подаются на соответствующие таблицы подстановки. С выхода таблиц подстановок преобразованные слова поступают на вход 8-и битной операции перестановки. После этого полученные данные поступают на следующий раунд шифрования. И таким образом было произведено шифрование кодового слова методом блочного криптоалгоритма . Также была разработан схема логического устройства , реализующего блок управления .

Список используемой литературы

1 Опадчий Ю.Ф. и др. Аналоговая и цифровая электроника (Полный курс): Учебник для вузов. М.: Горячая Линия - Телеком, 2002. с. 553-570.

2 Семерников Е.А., Трунов И.Л. Цифровые устройства в телекоммуникационных системах. Часть 1. Таганрог: Изд-во ТРТУ, 2003. (№3422)

3 Логачев О.А., Сальников А.А., Ященко В.В. Криптографические свойства дискретных функций.

4 Методические указания по выполнению курсового проекта «Аппаратная реализация блочных шифров», составил: доцент каф. РЭС ЗиС к.т.н., Поликарпов С.В., Таганрог 2006 г.

Приложение А Чертёж логической схемы таблицы подстановки

Приложение Б Чертёж логической схемы функции перестановки

Приложение С Чертёж логической схемы блока управления

Размещено на Allbest.ru