лаб 15. Лаб раб 15. Лабораторные работы

• Название: Лабораторные работы
• Анкор: лаб 15
• Дата: 22.09.2022
• Размер: 0.6 Mb.
• Имя файла: Лаб раб 15.docx
• Тип: Документы; #690117
• страница: 21 из 26

Задание

1. 
   Реализовать приложение, позволяющее выполнять следующие действия:
   
   1. 
      Генерировать большие простые числа:
      

1. 
   программа по заданным (количество проверок в тесте Рабина-Миллера) и (количество бит) должна генерировать простое n-битное число, отображая при этом, сколько итераций алгоритма генерации простого числа потребовалось выполнить для его генерации и сколько времени было затрачено на это;
   
2. 
   программа по заданным границам диапазона должна выводить все простые числа из этого диапазона, отображая время, затраченное на генерацию всех чисел.
   

1. 
   Определять для заданного числа первые 100 первообразных корней, отображая при этом суммарное время, затраченное программой на их поиск.
   
2. 
   Моделировать обмен ключами между абонентами по схеме Диффи-Хеллмана. Программа должна получать большие простые числа 𝑋a , 𝑋b и n случайным образом с помощью алгоритма генерации простого числа, а также предоставлять пользователю возможность задавать их.
   
1. 
   С помощью реализованного приложения выполнить следующие задания:
   
   1. 
      Протестировать правильность работы разработанного приложения.
      
   2. 
      Сделать выводы о проделанной работе.
      

Вопросы

1. 
   Для чего нужно большое простое число? Как проверить, является число простым или нет? Как сгенерировать большое простое число?
   
2. 
   Алгоритм эффективной реализации возведения целого числа в целую степень по модулю .
   
3. 
   На чём основывается безопасность обмена ключа по схеме Диффи-Хеллмана?
   
4. 
   Как происходит обмен ключами по схеме Диффи-Хеллмана?
   
5. 
   Доказать, что в схеме Диффи-Хеллмана 𝐾a= 𝐾b .
   

Лабораторная работа №10 Асимметричный алгоритм шифрования RSA

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

Знать:

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

Уметь:

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

Алгоритм RSA

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

Открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа n. Это значит, что длина блока должна быть меньше ^{или равна log}2^{(n). На практике длина блока выбирается равной 2k битам, где 2k < n < 2k+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^k⁽ⁿ⁾⁺¹ _{= m}^{k(p-1)(q-1)+1} _{ m mod n,}

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

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

Поэтому требуемое отношение получается при условии ed = k (n) + 1. Это эквивалентно следующим соотношениям:

ed  1 mod  (n), d  e^-1 mod  (n),

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

Теперь представим схему RSA. Компонентами схемы являются: p и q – два простых числа (секретные, выбираются),

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

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

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

мы выбрали е и d такие, что d  е^-1 mod  (n). Таким образом, ed  1 mod  (n).

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

_M^k⁽ⁿ⁾⁺¹ _{= 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. Вычисляется  (n) = (p-1)(q-1) = 96.

4. 
   Выбирается e, взаимно простое с = 96 и меньшее, чем  (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 Вычисление  (n) = (p-1)(q-1) Выбор целого e gcd((n),e) = 1, 1 Вычисление d d  e-1mod (n) Открытый ключ KU = (e, n) Личный ключ KR = (d, n).

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

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

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

Открытый текст 19→19⁵ =

^2476099 =20807 с остатком 66→Шифрованный текст 66→

119

₇₇ 1.27...*10¹⁴⁰
138

66 =

119

=1.06…*10

с остатком 19→открытый текст 19

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

1. 
   вычисление ключей
   
2. 
   шифрование/дешифрование.