«Открытое распространение ключей»

Учреждение образования
 «БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»
 
 
Кафедра интеллектуальных информационных технологий
 





 
 
Лабораторная работа №5 по курсу «Криптографические методы защиты информации» на тему:
«Открытое распространение ключей»


 
 

Выполнили студенты
группы 921731:
Проверил:
Эргашев А. М.
Асроров М. Ф.
Ерназарова С. Р.

Шалёв Е. Г.


 


 
МИНСК
2022 
Задание:

• 
  Реализуйте алгоритм дискретного возведения в степень для 32-ух разрядных чисел;
  
• 
  Реализовать алгоритм Диффи-Хеллмана для двух пользователей при p = 340412687, а = 5. (сгенерировать два случайных 32-ух разрядных числа и воспользоваться имеющимся алгоритмом);
  
• 
  Напишите программу дискретного логарифмирования 32-ух разрядных чисел и воспользуйтесь ею для определения одного из значений Xi по известному Yi = aXi(mod p);
  
• 
  Оформите отчет. В отчете приведите сгенерированные секретные числа Xi, полученные значения Yi = aXi(mod p), i =1, 2 и результаты вычисления общего секрета (Y1)X2(mod p), (Y2)X1(mod p).
  

Выполнение задания:

• 
  Реализуйте алгоритм дискретного возведения в степень для 32-ух разрядных чисел.
  

1. 
   Реализовать алгоритм Диффи-Хеллмана для двух пользователей при p = 340412687, а = 5. (сгенерировать два случайных 32-ух разрядных числа и воспользоваться имеющимся алгоритмом).
   

1. 
   Напишите программу дискретного логарифмирования 32-ух разрядных чисел и воспользуйтесь ею для определения одного из значений Xi по известному Yi = aXi(mod p).
   

Результат выполнения:

Выше приведены выходные данные при следующих входных: а = 5, р = 340412687.

Вывод:
В ходе лабораторной была рассмотрена и программно реализована операция дискретного возведения в степень, лежащая в основе алгоритма Диффи-Хеллмана, который позволяет осуществлять передачу с открытым ключом. Также был программно реализован сам алгоритм передачи данных по незащищенному каналу для 2 пользователей. Для этого использовался язык C++.
В реализованной структуре для работы с большими числами за основание системы счисления был использован тип long (целое число в диапазоне от −2 147 483 648 до 2 147 483 647). При выполнении арифметических операций действия над элементами данного массива выполняются по отдельности. 
Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Идея, лежащая в основе подобных систем, опирается на высокую вычислительную сложность обращения некоторых числовых функций. В данном случае, операция дискретного логарифмирования является обратной к степенной функции. Последняя вычисляется достаточно просто, в то время как даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители.
Классическими криптографическими схемами, базирующимися на сложности задачи дискретного логарифмирования, являются схема выработки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений.
Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в -ую степень за O(log n) умножений (вместо умножений при обычном подходе).
Задача дискретного логарифмирования заключается в том, чтобы по данным целым , , решить уравнение: , работающее за время за .