Начальная и завершающая перестановки

На вход алгоритма поступает 8-битовый блок открытого текста, к которому применяется начальная перестановка, заданная функцией IP (Таблица 3).

 

Таблица 3. Начальная перестановка

IP
2	6	3	1	4	8	5	7

 

Все 8 битов открытого текста сохраняют свои значения, но меняется порядок их следования. На завершающей стадии алгоритма выполняется обратная перестановка (Таблица 4).

 

Таблица 4. Обратная перестановка

IP
4	1	3	5	7	2	8	6

 

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

IР^-1(IP(X))  = X.

Функция f _к

Самым сложным компонентом S-DES является функция f_к , представляющая собой комбинацию перестановки и подстановки. Пусть L и R означают соответственно первые 4 бита и последние 4 бита 8-битовой последовательности, подаваемой на вход f_к, и пусть F — некоторое отображение пространства 4-битовых строк в себя, не обязательно являющееся взаимно однозначным. Тогда

 

f_к(L, R) = (L Å F(R, SK), R) ,

 

где SK обозначает подключ, а Å — операцию XOR (побитовое исключающее "ИЛИ"). Например, если в результате применения функции IP получено значение (10111101) и F(1101, SK) = (1110) для некоторого ключа SK, то f_к(10111101) = (01011101), так как (1011) Å (1110)= (0101).

Теперь опишем отображение F. На входе этого отображения имеем 4-битовое значение (n₁ n₂ n₃ n₄) . Первой операцией является операция расширения/перестановки (Таблица 5).

 

Таблица 5 Операция расширения/перестановки.

Е/Р
4	1	2	3	2	3	4	1

 

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

n4	n1	n2	n3
n2	n3	n4	n1

 

К этому значению с помощью операции XOR добавляется 8-битовый подключ, К₁(k₁₁ , k₁₂, k₁₃, k₁₄, k₁₅, k₁₆, k₁₇, k₁₈, k₁₉, k₂₀)

n4 +k11	n1+k12	n2+k13	n3+k14
n2+k15	n3+k16	n4+k17	n1+k18

 

Переименуем полученные в результате 8 битов:

р4	р1	р2	р3
р2	р3	р4	р1

 

Первые четыре бита (первая строка приведенной выше матрицы) поступают на вход модуля S0, на выходе которого получается 2-битовая последователь­ность, а оставшиеся четыре бита (вторая строка матрицы) — на вход модуля S1, на выходе которого получается другая 2-битовая последовательность. Модули S0 и S1 можно определить так:

 

S0 =		0	1	2	3		S1 =		0	1	2	3
	0	1	0	3	2			0	1	1	2	3
	1	3	2	1	0			1	2	0	1	3
	2	0	2	1	3			2	3	0	1	0
	3	3	1	3	1			3	2	1	0	3

 

Эти S-модули (матрицы кодирования) работают следующим образом. Первый и четвертый биты входной последовательности рассматриваются как 2-битовые числа, определяющие строку, а второй и третий — как числа, определяющие столбец S-матрицы. Элементы, находящиеся на пересечении соответствующих строки и столбца, задают 2-битовые выходные значения. Например, если (р_0,0 р_0,3) = (00) и (р_0,1 р_0,2) = (10), то выходные 2 бита задаются значением, кото­рое находится на пересечении строки 0 и столбца 2 матрицы S0 (оно равно 3 или (11) в двоичном представлении). Точно так же (р_1,0 р_1,3) и (р_1,1 р_1,2) служат для определения строки и столбца матрицы S1, на пересечении которых стоит зна­чение, задающее вторые 2 бита.

Теперь 4 бита, полученные на выходе модулей S0 и S1, преобразуются с помощью перестановки следующим образом.

 

Р4
2	4	3	1

 

Результат применения перестановки Р4 и является результатом функции F.

 

Функция-переключатель

Функция f_к изменяет только четыре левых бита. Поэтому следующей операцией в алгоритме шифрования является использование функции SW, которая меняет местами первые и последние четыре бита последовательности, чтобы при следующем вызове функции f_к последняя работала уже с другой четверкой битов. При втором вызове f_к функции Е/Р, S0, SI и Р4 остаются теми же, что и при первом, но вместо ключа К₁ используется ключ К₂.

Задания

В лабораторную работу входят 2 задания. Вариант задания определяется последней цифрой номера зачетной книжки (0 соответствует 10 варианту).

 

Используя алгоритм S-DES и ключ зашифруйте строку открытого текста, при этом покажите промежуточные результаты, получаемые на выходе каждой функции (IP, Fk, SW, Fk, IP-1).

 

№ варианта	Задание
	Текст	Ключ
1	10110110	0111111110
2	10011101	1111001111
3	11001111	1000011110
4	11101111	1000000010
5	10111011	1000011111
6	10111101	0001110001
7	11000111	0111011101
8	11111011	1000100010
9	11111101	1000000111
10	10101010	1111100011

 

Используя алгоритм S-DES и ключ расшифруйте строку, при этом покажите промежуточные результаты, получаемые на выходе каждой функции (IP, Fk, SW, Fk, IP-1). Затем преобразуйте как первые, так и вторые 4 бита полученной строки открытого текста в буквы, исходя из того, что буквы от А до Р представлены в виде двоичных кодов (т.е. А = 0000, В = 0001, …, Р = 1111).

 

№ варианта	Задание
	Текст	Ключ
1	00011111	1011011000
2	01110001	1001110101
3	11011101	1100111110
4	00100010	1110111111
5	00000111	1011101100
6	11100011	1011110101
7	11011101	1100011101
8	00100010	1111101110
9	00000111	1111110111
10	11100011	1010101000

 

Содержание отчёта

Отчёт должен содержать:

1. задание к работе;

2. программу.

3. результаты работы программы

4. решение задач.

 

Контрольные вопросы

1. Дайте понятие криптоаналитической стойкости алгоритма шифрования.

2. Перечислите типы атак (нарушений нормального потока информации).

3. Какие нарушения зашиты называются пассивными?

4. Какие нарушения зашиты называются активными?

5. Дайте понятия конфиденциальности, аутентификации.

6. Дайте понятия целостности, доступности.

7. Что такое управление доступом и невозможность отречения?

Лабораторная работа № 8

Тема: Шифрование DES.

Цель работы: Изучить современные методы традиционного шифрования, принципы блочного шифрования, алгоритм шифрования DES.

В результате выполнения работы студент должен:

Знать:

– методы традиционного шифрования;

– принципы блочного шифрования.

Уметь :

– вычислять ключи;

– шифровать и расшифровывать сообщения шифром DES.

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Шифр DES

Общая схема процесса шифрования DES показана на рисунке 1. На вход функции шифрования подается два типа данных — открытый текст, который требуется зашифровать, и ключ. В данном случае длина открытого текста предполагается равной 64 битам, а длина ключа — 56 битам (на самом деле функция требует ввода 64-битового ключа, но в качестве ключа шифрования используется только 56 битов. Остальные 8 битов могут быть битами четности или вообще какими-то произвольными).

Из левой части рисунка 1 видно, что процесс преобразования открытого текста состоит из трех этапов. Сначала 64-битовый блок открытого текста поступает для обработки на вход начальной перестановки (IP), в результате чего получаются переставленные входные данные. Затем следует этап, состоящий из 16 раундов применения одной и той же функции, в которой используются как операции перестановки, так и подстановки. На выходе последнего (16-го) раунда получаются 64-битовая последовательность, являющаяся некоторой функцией открытого текста и ключа. Левая и правая половины полученной последовательности данных меняются местами, образуя предрезультат (preoutput). Предрезультат проходит через перестановку IP^-1, обратную начальной, в результате чего получается 64-битовый блок шифрованного текста.

В правой части рисунка 1 показано, каким образом используется 56-битовый ключ. Сначала к ключу тоже применяется функция перестановки. Затем с помощью циклического сдвига влево и некоторой перестановки из полученного результата для каждого из 16 раундов генерируется подключ (К_i). Функция перестановки одна и та же для всех раундов, но генерируемые подключи оказываются разными из-за того, что в результате циклического сдвига на ее вход поступают разные биты ключа.

 

 

 

                                                              

 

 

                                                                                                                                         

 

Рисунок 1 – Общая схема алгоритма шифрования DES

 

 

Таблица 1 - Таблицы перестановок, используемых в DES

 

(а) начальная перестановка (IP)

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

 

(б) перестановка, обратная начальной (IP^-1)

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

 

 (в) перестановка с расширением (Е)

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

 

(г) перестановка (Р)

16	7	20	21	29	12	28	17
1	15	23	26	5	18	31	10
2	8	24	14	32	27	3	9
19	13	30	6	22	11	4	25

 

Детали алгоритма шифрования

На рисунке 2 показана внутренняя структура алгоритма, используемого при итерациях. Начнем рассмотрение с левой части рисунка. Левая (L) и правая (R) половины каждого 64-битового значения рассматриваются как независимые 32-битовые величины. Операции, выполняемые на каждой итерации, можно записать в виде следующих формул:

L_i = R_i-1 ,

 

R_i =L_i-1 Å F(R_i-1,K_i).

 

Для любого раунда длина ключа К_i равна 48 битам, а длина элемента входных данных R — 32 битам. Сначала входное значение R расширяется до 48 битов с помощью таблицы, задающей перестановку с расширением (см. таблицу 1(в)), заключающемся в повторении 16 битов значения R. Полученное 48-битовое значение складывается с К_i с помощью операции XOR (исключающее "ИЛИ"). Результат, длина которого тоже равна 48 битам, передается функции подстановки, которая генерирует 32-битовое значение, определяемое по таблице 1(г).

Роль S-матриц в функции F раскрывается иллюстрацией на рисунке 3. Механизм подстановки определяется набором из восьми S-матриц, каждая из которых получает на вход 6 битов данных и выдает 4-битовый результат. Преобразования определяются по таблице 2 по следующему правилу. Первый и последний биты входного значения для матрицы S, представляют 2-битовое двоичное число, задающее одну из четырех подстановок, определяемых четырьмя строками таблицы для S_i. Остальные четыре бита определяют столбец. Десятичное значение, находящееся на пересечении заданных таким образом столбца и строки, в 4-битовом представлении будет результатом. Например, если на вход S_i поступает значение 011001, оно задает строку 01 (десятичное 1) и столбец 1100 (десятичное 12). На пересечении строки 1 и столбца 12 находится значение 9. поэтому результат в двоичном представлении будет иметь вид 1001.

 

Таблица2 - определение S-матриц алгоритма DES

S1	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

 

S2	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9

 

S3	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12

 

S4	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14

 

S5	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

 

S6	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13

 

S7	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12

 

 

S8	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

 

 

 

Рисунок 2 - Один раунд шифрования алгоритма DES

 

 

 

Рисунок 3 - Вычисление F(R, К)

 

Вычисление ключей

Возвращаясь к рисункам 2 и 3, заметим, что 56-битовые ключи, используемые в качестве входных данных алгоритма, сначала преобразуются с помощью перестановки, задаваемой таблицей первой перестановки с выбором (РС-1), таблица 3(а). Полученное в результате 56-битовое значение рассматривается как комбинация двух 28-битовых значений, для которых используются обозначения С₀ и D₀. В каждом раунде шифрования к значениям С_i-1 и D_i-1 по отдельности применяются операции циклического сдвига влево (вращения) на 1 или 2 бита в соответствии с таблицей 3(в). Полученные после сдвига значения поступают на вход следующего раунда шифрования. Те же значения подаются на вход второй перестановки с выбором (РС-2) (см. таблицу 3(6)), с помощью которой получается 48-битовое выходное значение К_i, требуемое для выполнения функции

F(R_i-1,K_i).

 

 

Таблица 3 - Вычисление ключей в алгоритме DES

(а) первая перестановка с выбором (РС-1)

57	49	41	33	25	17	9
1	58	50	42	34	26	18
10	2	59	51	43	35	27
19	11	3	60	52	44	36
63	55	47	39	31	23	15
7	62	54	46	38	30	22
14	6	61	53	45	37	29
21	13	5	28	20	12	4

 

(б) вторая перестановка с выбором (РС-2)

14	17	11	24	1	5	3	28
15	6	21	10	23	19	12	4
26	8	16	7	27	20	13	2
41	52	31	37	47	55	30	40
51	45	33	48	44	49	39	56
34	53	46	42	50	36	29	32

 

(в) таблица сдвигов влево

Номер раунда	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Число сдвигов	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

 

Дешифрование DES

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

 

Задание

1. Покажите, что дешифрование DES является операцией, представляющей собой обращение операции шифрования DES.

2. При иcпользовании алгоритма DES для дешифрования 16 ключей (К₁, К₂, … ,К₁₆) используются в обратном порядке. Таким образом, правая часть рисунка 2 не соответствует действительности. Разработайте схему вычисления ключей с соответствующим графиком сдвигов (аналогичным табл.4(в)) для такого процесса дешифрования.

3. Покажите, что в DES первые 24 бита каждого подключа выбираются из одного 28-битового подмножества битов исходного ключа, а вторые 24 бита – из другого, не пересекающегося с первым 28-битового подмножества битов этого ключа.

4. В алгоритме DES 32-битовый обмен после шестнадцатого раунда шифрования требуется для того, чтобы превратить обращение процесса шифрования в повторный прогон шифрованного текста через тот же алгоритм с обратным порядком следования ключей. (следует из задания1). Пусть

5. А║В – конкатенация битовых строк А и В,

6. T_i(R║L) – преобразование определенной i-й итерацией алгоритма шифрования, 1<=i<=16,

7. TD_i(R║L) - преобразование определенной i-й итерацией алгоритма дешифрования, 1<=i<=16,

8. T₁₇(R║L) = L║R, т.е. это преобразование, выполняющееся после шестнадцатой итерации алгоритма шифрования.

_9. Докажите, что композиция TD_i(IP(IP^-1(T₁₇(T₁₆(L₁₅║ R₁₅))))) эквивалентна преобразованию, которое меняет местами 32-битовые половинки L₁₅ и R_15. иными слова, требуется показать, что TD₁ (IP(IP^-1(T₁₇(T₁₆(L₁₅ ║R₁₅))))) = R₁₅ ║L_15.

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

11. TD₁ (IP(IP^-1(T₁₇(T₁₆(L₁₅ R₁₅))))) = L₁₅ ║R₁₅

12. Выполняется ли оно?

Содержание отчёта

Отчёт должен содержать:

1. задание к работе;

2. программу.

3. результаты работы программы

4. решение задач.

 

Контрольные вопросы

1. Стандарт шифрования данных (DES).

2. Шифрование DES.

3. Вычисление ключей.

4. Дешифрование DES.

5. Лавинный эффект.

6. Принципы построения блочных шифров.

Лабораторная работа № 9

Тема: Алгоритм RSA.

Цель работы: Изучить алгоритмы шифрования с открытым ключом. Алгоритм RSA.

В результате выполнения работы студент должен:

Знать:

– методы криптографии с открытым ключом.

Уметь:

– применять алгоритм RSA.

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Алгоритм RSA

Схема RSA представляет собой блочный шифр, в котором и открытый текст, и шифрованный текст представляются целыми числами из диапазона от 0 до n - 1 для некоторого n.

Открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа n. Это значит, что длина блока должна быть меньше или равна log₂(n). На практике длина блока выбирается равной 2^k битам, где 2^k < n < 2^k+l. Шифрование и дешифрование для блока открытого текста М и блока шифрованного текста С можно представить в виде следующих формул:

С = М^е mod n,

М = C^d mod n = (М.^e)^d mod n = M^ed mod n.

Как отправитель, так и получатель должны знать значение n. Отправитель знает значение е, и только получателю известно значение d. Таким образом, данная схема является алгоритмом шифрования с открытым ключом KU = (е, n) и личным ключом KR = (d, n). Чтобы этот алгоритм мог использоваться для шифрования с открытым ключом, должны быть выполнены следующие требования.

1. Должны существовать такие значения е, d и n, что M^ed = M mod n для всех М < n.

2. Должны относительно легко вычисляться М^е и C^d для всех значений М < n.

3. Должно быть практически невозможно определить d по имеющимся e и n.

Сфокусируем внимание на первом требовании. Необходимо найти соотношение вида

М^ed =M mod n.

Здесь как нельзя лучше подойдет следствие теоремы Эйлера:

для таких любых двух простых чисел p и q и та­ких любых двух целых чисел n и m, что n=pq и 0 < m < n, и произвольного целого числа k выполняются следующие соотношения:

 

m^kj(n)+1 = m^{k(p-1)(q-1)+1} º m mod n,

 

где j(n) является функцией Эйлера, значение которой равно числу положительных целых чисел, меньших n и взаимно простых с n. В случае простых p и q имеем:

j(pq) = (р - 1)(q - 1).

Поэтому требуемое отношение получается при условии ed = kj (n) + 1.

Это эквивалентно следующим соотношениям:

ed º 1 mod j (n),

d º e^-1 mod j (n),

т.е. е и d являются взаимно обратными по модулю j(n). Это может иметь место только тогда, когда d (а следовательно, и e) является взаимно простым с j(n) (в соответствии с правилами арифметики в классах вычетов). В эквивалентной записи gcd(j(n), d) = 1.

Теперь представим схему RSA. Компонентами схемы являются:

p и q – два простых числа (секретные, выбираются),

n = pq (открытое, вычисляется),

такое e, что gcd(j(n),e) = 1, 1 <e< j(n), (открытое, выбирается),

d º e^-1mod j(n) (секретное, вычисляется).

 

Личный ключ складывается из (d, n), а открытый — из (е, n). Предположим, что пользователь А опубликовал свой открытый ключ и теперь пользователь В собирается переслать ему сообщение М. Тогда пользователь В вычисляет С = M^e(mod n) и пересылает С. Получив этот шифрованный текст, пользователь А дешифрует его, вычисляя М = С^d (mod n).

Обоснование алгоритма:

мы выбрали е и d такие, что d º е^-1 mod j (n).

Таким образом, ed º 1 mod j (n).

Значит, ed имеет вид kj (n)+1. По следствию теоремы Эйлера, для таких любых двух простых чисел р и q и целых чисел n = pq и М, что 0 < М < n, выполняются соотношения

M^kj(n)+1 = M^{k(p-1)(q-1)+1} º M mod n

 

Поэтому M^ed º М mod n. Теперь мы имеем

С = М^е mod n,

М = С^dmod n º (M^e)^d mod n = M^ed mod n = M mod n.

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

1. Выбирается два простых числа, р = 7 и q = 17.

2. Вычисляется n = pq = 7 * 17 = 119.

3. Вычисляется j (n) = (p-1)(q-1) = 96.

4. Выбирается e, взаимно простое с = 96 и меньшее, чем j (n): в данном случае e = 5.

5. определяется такое d, что de = 1 mod 96 и d < 96. Соответствующим значением будет d = 77, так как 77*5 = 385 = 4*96 +1.

 

В результате получаются открытый ключ KU = (5, 119) и личный ключ KR = (77, 119). В примере показано использование этих ключей с вводимым открытым текстом M = 19. При шифровании 19 возводится в пятую степень, что в результате дает 2476099. В результате деления на 119 определяется остаток, равный 66. Для дешифрования выясняется, что 66⁷⁷º 19 mod119.

 

Таблица 1 - алгоритм RSA

Вычисление ключей Выбор p, q p и q должны быть простыми Вычисление n = p*q Вычисление j (n) = (p-1)(q-1) Выбор целого e     gcd(j(n),e) = 1, 1 <e< j(n), Вычисление d      d º e-1mod j(n) Открытый ключ KU = (e, n) Личный ключ KR = (d, n).

Шифрование Открытый текст: M < n Шифрованный текст: C = Me(mod n)

Дешифрование Открытый текст: С Шифрованный текст: М = Сd(mod n)

 

Рисунок 1 – Пример применения алгоритма RSA

 

Открытый текст 19→19⁵ = =20807 с остатком 66→Шифрованный текст 66→

66⁷⁷= =1.06…*10¹³⁸ с остатком 19→открытый текст 19

KU = 5, 119                KR = 77, 119

 

Рассмотрим вопросы сложности вычислений, необходимых при использовании RSA:

1. вычисление ключей

2. шифрование/дешифрование.

 

Шифрование и дешифрование

Как шифрование, так и дешифрование в RSA предполагает использование операции возведения целого числа в целую степень по модулю n. Если возведение в степень выполнять непосредственно с целыми числами и только потом проводить сравнение по модулю n, то промежуточные значения окажутся просто огромными. Поэтому воспользуемся свойствами арифметики в классах вычетов:

 

[(a mod n) * (b mod n)] mod n = (а * b) mod n.

 

Таким образом, мы можем рассматривать промежуточные результаты по модулю n. Это делает вычисления практически возможными.

Другой проблемой является эффективная реализация операции возведения в степень, так как в случае применения RSA мы должны иметь дело с потенциально большими показателями. Чтобы продемонстрировать, насколько здесь можно увеличить эффективность вычислений, предположим, что необходимо вычислить x¹⁶. Прямолинейный подход потребует 15 умножений, как показано ниже.

 

Х¹⁶=х*х*х*х*х*х*х*х*х*х*х*х*х*х*х*х

 

Однако такого же конечного результата можно достичь и с помощью всего четырех умножений, если повторно возводить в квадрат промежуточные результаты, получая при этом х², х⁴, х⁸, х¹⁶.

В общем случае предположим, что нам нужно найти значение a^m, где а и m являются положительными целыми числами. Если представить m в виде двоичного числа b_kb_k-1…b₀, то

M = ,

и поэтому

 

a^m = = ,

 

a^m mod n = = .

 

Таким образом, для вычисления a^b mod n можно использовать алгоритм, показанный на рисунке 2. В таблице 2 показан пример последовательности значений, получаемых в результате выполнения этого алгоритма. Обратите внимание на то, что переменная с, вообще говоря, не нужна — она включена в алгоритм только с целью обеспечения наглядности. Конечное значение с будет значением показателя вычисляемой степени.

 

c←0; d←1

for i←k downto 0

do c←2*c

d←(d*d) mod n

if b_i = 1

then c← c+1

d← (d*a) mod n

return d

 

Рисунок 2 - Алгоритм вычисления а^b mod n

 

Таблица 2 - Результаты выполнения алгоритма быстрого возведения в степень для а^b mod n при а = 7, b = 560 = 1000110000, n = 561.

i	9	8	7	6	5	4	3	2	1	0
bi	1	0	0	0	1	1	0	0	0	0
с	1	2	4	8	17	35	70	140	280	560
d	7	49	157	526	160	241	298	166	67	1

 

Вычисление ключей

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

1. определение двух простых чисел р и q;

2. выбор одного из чисел е или d и вычисление второго.

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

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

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

Процедуру выбора простого числа можно представить в следующем виде.

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

2. Выберите целое число а < n некоторым случайным образом.

3. Выполните вероятностный тест на простоту. Если n не выдерживает тестирования, отбросьте данное значение n и перейдите к пункту 1.

4. Если n выдерживает достаточное число повторных тестов, примите данное значение n как подходящее, в противном случае перейдите к пункту 2.

Это процедура несколько утомительна. Однако не забывайте о том, что этот процесс выполняется относительно нечасто — только тогда, когда требуется новая пара (KU, KR).

При этом неплохо знать, как много чисел, скорее всего, окажутся отброшенными прежде, чем обнаружится простое число. Одна из теорем теории чисел, известная под названием теоремы о простых числах, утверждает, что простые числа около N распределяются в среднем по одному на каждые ln(N) целых чисел. Таким образом, в среднем придется протестировать порядка ln(N) целых чисел прежде, чем найдется простое число. В действительности из-за того, что все четные целые числа можно отбросить сразу же, истинный порядок задается числом ln(N)/2. Например, если искать простые числа в области величин порядка 2²⁰⁰, то для нахождения простого числа потребуется около ln(2²⁰⁰)/2 = 70 попыток.

После определения простых чисел р и q процесс вычисления ключей заверша­ется выбором значения е и вычислением d или, наоборот, выбором значения d и вычислением е. В первом случае необходимо сначала выбрать такое е, что gcd(j(n), е) = 1, а потом вычислить d º e^-1mod j(n). К счастью, имеется один ал­горитм, который в одно и то же время вычисляет наибольший общий делитель двух целых чисел и, если наибольший общий делитель оказывается равным 1, определяет обратное для одного из целых чисел по модулю другого. Этот алгоритм называется обобщенным алгоритмом Евклида. Процедура заключается в генерировании случайных чисел и сравнении их с j (n) до тех пор, пока не будет найдено число, взаимно простое с j (n). Теперь мы снова можем спросить, как много случайных чисел придется проверить прежде, чем будет найдено подходящее число, т.е. число, взаимно простое с j (n)? Легко показать, что вероятность того, что два выбранных случайно числа окажутся взаимно простыми, равна примерно 0,6 — это значит, что для нахождения подходящего целого значения понадобится всего несколько проверок.

 

Задание

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

Программа может быть реализована в любой среде программирования и должна предоставлять возможность:

1. Выбирать любой файл для шифрования.

2. Шифровать выбранный файл и записывать в каталог, указанный пользователем, под любым именем.

3. Дешифровать файл и результат записывать в указанный пользователем файл.

 

Последняя цифра номера зачетной книжки	P	Q	D
1	61	71	9577
2	349	521	377467
3	251	331	165131
4	571	1153	1531453
5	37	47	295
6	97	67	5977
7	137	43	11395
8	113	443	33819
9	317	41	21241
10	571	521	9577

Опишите шифрование и дешифрование с помощью алгоритма RSA подобно тому, как показано на рисунке 1, для следующих значений параметров.

– р = 3; q = 11, d = 7; М = 5.

– р = 5; q = 11, е = 3; М = 9.

– р= 7; q = 11, е= 17; М = 8.

– р = 11; q= 13, е = 11; М = 7.

– р = 17, q = 31, е= 7; М = 2.

Указание. Дешифрование здесь является не столь сложным, как вы думаете. Используйте некоторую хитрость.

В криптосистеме с открытым ключом, использующей RSA, вы перехватили шифрованный текст С = 10, посылаемый пользователю, открытым ключом которого является е = 5, n = 35. Что в данном случае является открытым текстом М?

В использующей RSA системе открытым ключом некоторого пользователя является е = 31, n = 3599. Что будет личным ключом этого пользователя?

Если при использовании алгоритма RSA после выполнения небольшого
числа операций повторного шифрования снова получается исходный от­крытый текст, что может быть наиболее вероятный причиной этого?

Предположим, имеется набор блоков, зашифрованных с помощью алго­ритма RSA, но нет соответствующего им личного ключа. Пусть n = pq, е является открытым ключом. Предположим также, что кто-то утверждает, что ему известно, что один из блоков открытого текста и n имеют общий делитель. Дает ли это какую-либо реальную помощь в данном случае?

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

Рассмотрите следующую схему.

- Выбирается нечетное число Е.

- Выбирается два простых числа Р и Q так, чтобы (Р - l)(Q - 1) - 1 делилось на Е.

- Значение Р умножается на Q, чтобы в результате получить N.

- Вычисляется D = .

Является ли эта схема эквивалентной RSA? Обоснуйте свой ответ.

Рассмотрите следующую схему, с помощью которой В шифрует свое сообщение для А.

- Сторона А выбирает два больших простых числа Р и Q, которые должны быть также взаимно простыми с (Р - 1) и (Q - 1).

- Сторона А объявляет N = PQ своим открытым ключом.

- Сторона А вычисляет такие Р' и Q', что РР' = 1 (mod Q -1) и QQ' = 1 (mod Р -1).

- Сторона В шифрует сообщение М как С = M^N (mod N).

- Сторона А находит М с помощью решения М = C^p’(mod Q) и М = С^Q’ (mod Р).

- Объясните, как работает эта схема.

- Чем она отличается от RSA?

- Есть ли реальные преимущества у RSA по сравнению с этой схемой?

Содержание отчёта

Отчёт должен содержать:

1. задание к работе;

2. программу;

3. результаты работы программы;

4. решение задач.

Контрольные вопросы

1. От чего зависят алгоритмы шифрования с открытым ключом?

2. Сравните традиционное шифрование и шифрование с открытым ключом.

3. Как использовать шифрование с открытым ключом для аутентификации?

4. Как можно обеспечить аутентификацию и конфиденциальность в схеме шифрования с открытым ключом?

5. В результате чего получается цифровая подпись?

6. Шифрование и дешифрование RSA.

7. Вычисление ключей в алгоритме RSA.

8. Защищенность алгоритма RSA.

Лабораторная работа № 10

Тема: Обмен ключами по схеме Деффи-Хеллмана

Цель работы: Изучить обмен ключами по схеме Деффи-Хеллмана

В результате выполнения работы студент должен:

Знать:

- методы распределения открытых ключей;

Уметь:

- осуществлять обмен открытыми ключами по схемеДеффи-Хеллмана

 

 

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

---

Дата добавления: 2019-09-13; просмотров: 1070; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!