Практическая. Алгоритм БерлекэмпаМесси для нахождения коэффициентов обратной связи

• Название: Алгоритм БерлекэмпаМесси для нахождения коэффициентов обратной связи
• Анкор: Практическая
• Дата: 18.11.2019
• Размер: 153.48 Kb.
• Имя файла: pr23.docx
• Тип: Литература; #95760
• страница: 3 из 3

4 АСИММЕТРИЧНЫЕ АЛГОРИТМЫ
Для симметричной криптосистемы характерно применение одного и того же ключа, как при шифровании, так и при шифровании сообщений. В асимметричных криптосистемах для дешифрования данных используется один (общедоступный) ключ, а для дешифрования – другой (секретный) ключ.
4.1 Алгоритм Диффи-Хелмана
Этот алгоритм предполагает, что два абонента дистанционно будут генерировать ключ для шифрования в дальнейшем, например, каким либо симметричным алгоритмом. Алгоритм Диффи-Хелмана (1976 год) использует функцию дискретного возведения в степень.

Последовательность действий в алгоритме Диффи-Хелмана:

1 Сначала генерируются два больших простых числа n и q. Эти два числа не обязательно хранить в секрете.

2 Далее один из партнеров P1 генерирует случайное число x и посылает другому участнику будущих обменов P2 значение A = q^x mod n.

3 По получении А партнер P2 генерирует случайное число у и посылает P2 вычисленное значение B = q^y mod n.

4 Партнер P1, получив В, вычисляет K_x = B^x mod n.

5Партнер P2, получивAвычисляет K_y = A^y mod n.

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

Как видно из алгоритма, даже «перехватив» числа А и В, вычислить K_x или K_y невозможно.
Пример.Представим итерации алгоритма в виде последовательности действий партнеров в табличной форме (табл. 4.1).
Таблица 4.1



Совместным ключом для шифрования будет 5.
4.2 Алгоритм шифрования данных RSA
Алгоритм предложен в 1978 году авторами Rivest, Shamir и Aldeman и основан на трудности разложения больших целых чисел на простые множители. В результате реализации алгоритма имеем пару ключей: первый в дальнейшем используется только для шифрования (открытый ключ), второй для дешифрования (закрытый ключ). При этом, знание одного из ключей не позволяет определить другой ключ. Сгенерированные ключи могут многократно использоваться для шифрования информации.

Последовательность действий пользователя для получения ключей:

1 Получатель выбирает 2 больших простых целых числа p и q, на основе которых вычисляет N = p q; M = (p-1) (q-1).

2 Получатель выбирает целое случайное число d, которое является взаимно простым со значением М.

3 Вычисляем значение е из условия (ed) mod M = 1.

4 d и N публикуются как открытый ключ, е и М являются закрытым ключом.

Действия по шифрованию сообщения.

5 Если S – сообщениеи его длина: 1 < Len(S) < N, то оно шифруется выполнением операции S_ш = S^e mod N (то есть, закрытым ключом).

Действия по дешифрованию сообщения.

6 Получатель дешифровывает с помощью открытого ключа выполнением операции S = S_ш^dmod N.

Если длина сообщения превышает N, то сообщение делится на фрагменты длины, не превосходящие N.

Рассмотрим реализацию алгоритма на примере. Заметим, что в реальных алгоритмах в качестве простых чисел выбираются отстоящие друг от друга большие числа, порядка 2¹²⁸ – 2¹⁰²⁴, поиск которых, вообще говоря, и определяют сложность алгоритма для криптоанализа.

Пример.Далее представлены шаги алгоритма:

1 p = 19, q = 13, N = p q = 247, M = (p – 1) (q – 1) = 18х 12 = 216.

2 Выбираем целое случайное число d, которое взаимно простое сM. d = 35. (Действительно,d и M не имеют общих делителей 35 = 7 х 5, 216 = 2 х 2 х 2 х 3 х 3 х 3).

3 Вычисляем e такое, что (e d) mod M = 1, e = 179.

4(d,N)открытый ключ, т.е.(35,247), (e,N) –закрытый ключ (179, 247).

5Шифрование сообщения2 3 5 , используя закрытый ключ (179, 247) и формулуS_ш = S^emod N:



Таким образом, шифрованное сообщение имеет вид 124 165 99.

6 Дешифровка сообщения 124 165 99, используя открытый ключ(35, 247) и формулу S = S_ш^dmodN



Расшифрованное сообщение 2 3 5.
4.3 Задания для выполнения
4.3.1 Используя алгоритм Диффи-Хелмана сгенерируйте ключ для симметричного алгоритма криптографии.

4.3.2 Сгенерировать открытый и закрытый ключи для алгоритма RSA. Передать открытый ключ следующему по списку студенту.

Таблица простых чисел в интервале [1; 200] приведена в таблице 4.2.

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

Передать шифрограмму адресату (следующему по списку студенту).

4.3.4 Произвести дешифрование полученного сообщения от другого студента, используя полученный от него открытый ключ.

Замечание: Некоторые простейшие ключи для алгоритма RSA представлены в таблице 4.4.
Таблица 4.2

Таблица простых чисел от 1 до 200

1	2	3	5	7	11	13	17	19	23
29	31	37	41	43	47	53	59	61	67
71	73	79	83	89	97	101	103	107	109
113	127	131	137	139	149	151	157	163	167
173	179	181	191	193	197	199

Таблица 4.3

Последовательность цифр для шифрования

Варианты заданий (последняя цифра номера варианта)
1	2	3	4	5	6	7	8	9	0
4 7 8 9 5 6	5 9 8 2 7 4	8 5 4 9 7 3	9 7 2 8 5 6	7 2 6 5 9 3	6 4 8 9 3 7	2 7 5 3 8 4	7 6 5 2 4 3	4 7 5 9 3 8	8 1 5 6 3 4

Таблица 4.4

Простейшие ключи для алгоритма RSA

№ пп	Открытый ключ	Закрытый ключ	№ пп	Открытый ключ	Закрытый ключ	№ пп	Открытый ключ	Закрытый ключ
1	(35,21)	(11,21)	8	(35,35)	(11,35)	15	(35,221)	(11,221)
2	(15,15)	(7,15)	9	(77,77)	(53,77)	16	(35,247)	(179,247)
3	(35,119)	(11,119)	10	(35,91)	(35,91)	17	(35,323)	(107,323)
4	(21,33)	(21,33)	11	(35,161)	(83,161)	18	(35,437)	(215,437)
5	(15,85)	(47,85)	12	(35,133)	(71,133)	19	(15,391)	(47,391)
6	(35,65)	(11,65)	13	(77,209)	(173,209)	20	(35,299)	(83,299)
7	(21,55)	(21,55)	14	(21,187)	(61,187)	21	(15,69)	(3,69)

Форма отчета по практическому занятию: Отчет оформляется в электронномвиде (текстовый или html- документ)по шаблону и должен включать:

1. 
   Название работы.
   
2. 
   Цель работы.
   
3. 
   Формулировку индивидуального задания и результат его выполнения.
   
4. 
   Краткие выводы по результатам выполнения работы.