Криптография с открытым ключом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?димо вручную (или с использованием составленной студентом программы) вычислить для всех положительных целых a<p степени по модулю p. В результате получим последовательности (см. таблицу 2.1) Необходимо из них выделить последовательности с длиной f(p) = p-1. В таком случае говорят, что каждое целое число a гененрирует (своими степенями) множество всех ненулевых вычетов по модулю p. Эти соответствующие целые a и являются первообразными корнями по модулю p. Таблицу можно построить, используя возможности программы. Так, введя значение целого числа а в одноименное поле ввода, степени числа а по модулю p можно вычислить, нажав соответствующую кнопку. При этом, если при данном значении числа а число итераций на единицу меньше модуля р, то данное простое число а - первообразный корень, иначе - нет.
Ввести полученные результаты (первообразные корни) и исходные данные в программу (ПРОГРАММА 4 - вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю f(p), - первообразных корней по модулю p).
Если Ваши результаты совпадут с результатами программы, то они будут зачтены. Иначе все задание 1 необходимо будет выполнить повторно с подбором новых исходных данных. Далее приводится более подробное описание действий.
Подобранные значения исходных данных вводятся в поля ввода с соответствующими названиями Целое число (а) и Взаимно простой с a модуль (p). Найти все степени числа a по модулю p и выделить первообразные корни. Полученные ответы ввести в большое поле Первообразные корни по модулю p. Каждое число необходимо записать на новой строке. Начинать следует с первой строки. Если на следующей строке после пустой строки введены какие-либо значения, то это будет расценено программой как ошибка вводящего. Для проверки программой расчетов студента необходимо нажать кнопку с надписью Проверка корректности. В ходе проверки программой верности расчетов студента все верные расчеты будут выведены в большом текстовом поле, находящимся в левой части экрана. Если студент ввел хотя бы один неверный ответ, то ему придется выполнить задание с новыми входными данными.
В случае верного решения студентом поставленной задачи информация об этом будет выведена в большом текстовом поле, и студенту станут, доступны для ввода поля ввода задания 2 данной лабораторной работы. При выполнении данной работы, при необходимости, рекомендуется использовать доступные возможности программ из предыдущих лабораторных работ.
Ответы и исходные данные фиксируются в соответствующем МАССИВЕ РЕЗУЛЬТАТОВ.
2.2 Задание 2. Генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети
2.2.1 Теория
Эффективность алгоритма Диффи-Хеллмана опирается на трудностях вычисления дискрет-ных логарифмов. В общем виде
y gx mod p,
вычисление y при заданных g, x и p является относительно простой задачей даже при очень больших значениях x (имеются соответствующие эффективные алгоритмы). Однако если заданы y, g и p, то вычисление x (дискретное логорифмирование) является, вообще говоря, очень непростой задачей. Согласно [1], до недавного времени сложность асимптотически наиболее быстрого из известных алгоритмов вычисления дискретных логарифмов по модулю простого числа оценивалась величиной порядка
ez, где z = ((ln p)1/3ln (ln p))2/3.
Теперь рассмотрим схему Диффи-Хеллмана по обмену ключами [1, 2] (рис. 2.2, слайд 2.4).
Рис. 2.2. Обмен ключами по схеме Диффи-Хеллмана
Глобальные открытые элементы:
простое число p;
первообразный корень простого числа p a, где a < p.
Вычисление ключа пользователем А:
Пользователь А выбирает случайное целое число XA < p и вычисляет YA = aXA mod p.
XA < p - секретная величина (закрытый ключ пользователя А);
YA - открытая величина (открытый ключ пользователя А).
Вычисление ключа пользователем В:
Пользователь В выбирает случайное целое число XВ < p и вычисляет YВ = a XВ mod p.
XВ < p - секретная величина (закрытый ключ пользователя В);
YВ - открытая величина (открытый ключ пользователя B).
Производится обмен открытыми ключами.
Пользователь А вычисляет общий секретный сеансовый ключ
K = (YB) XA mod p.
Пользователь B вычисляет общий секретный сеансовый ключ
K = (YA) XB mod p.
Эти последние формулы дают одинаковые результаты:
K = (YB )XA mod p = (a XВ mod p) XA mod p = (a XВ) XA mod p = a XВ XA mod p = (aXA) XB mod p = (aXA mod p) XB mod p = (YA) XB mod p.
Злоумышленнику могут быть известны величины p, a, YA и YB.
Злоумышленнику для определения секретного ключа пользователя В необходимо вычислить
X