Криптография с открытым ключом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
м производятся зашифрование определенного открытого текста и его расшифрование с использованием этого общего сеансового ключа.
Работа состоит из двух заданий.
Задание 1. Алгоритм вычисления степеней целого числа am по модулю p и целых чисел, принадлежащих показателю f(p) - первообразных корней по модулю p.
Задание 2. Генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети.
2.1 Задание 1. Алгоритм вычисления степеней целого числа am
по модулю p и целых чисел, принадлежащих показателю
f(p) - первообразных корней по модулю p
2.1.1 Теория
В начале напомним некоторые важные понятия из теории чисел.
Число положительных целых значений, которые меньше n и являются взаимно простыми с n, обозначается через f(n) и называется функцией Эйлера. Для простого числа p
f(p) = p - 1.
Если имеется два простых числа p и q, тогда для n = pq получим f(n) = f(pq) = f(p) f(q) = (p-1) (q-1).
Теорема Эйлера утверждает, что для любых взаимно простых чисел a и n af(n) 1 mod n. Пример: a = 3, n = 10, f(n) = f(pq) = f(p) f(q) = (p-1) (q-1) = (5-1) (2-1) = 4. Следовательно, 34 = 81 1 mod 10.
Важным является следующее.
Если a и n являются взаимно простыми, то существует, по крайней мере, одно целое число m, удовлетворяющее соотношению am 1 mod n, где m = f(n). Для наименьшего из положительных m, при которых выполняется указанное условие, используются следующие названия:
порядок числа a по модулю n;
показатель, которому принадлежит a по модулю n;
длина периода последовательности, генерируемой степенями a.
Пример СТЕП 1. Рассмотрим степени числа 5 по модулю 19:
Поэтому в нашем примере, любые две степени числа 5, показатели которых отличаются на 9 (или на число, кратное 9), сравнимы по модулю 19. Иначе, последовательность является периодической с периодом, равным наименьшему положительному показателю m, при котором 5m = 1 mod 19.
В общем случае можно сказать, что наивысшим из показателей, которому может принадлежать число a по модулю n, является f(n). Числа, принадлежащие показателю f(n), называются первообразными корнями по модулю n.
В таблице (табл. 2.1), в продолжение примера, приводятся степени целых чисел по модулю 19 (первая выделенная строка соответствует степеням; затемненные части строк соответствуют конкретным периодам).
Как видно, все последовательности заканчиваются числом 1.
В нашем примере длина последовательности является делителем f(19) = 18. Некоторые последовательности для a < 19 будут иметь длину 18. В таком случае говорят, что целое число a генерирует (своими степенями) множество всех ненулевых вычетов по модулю 19.
Любое из этих чисел называют первообразным корнем по модулю 19.
Важность этого понятия подтверждается тем, что если a является первообразным корнем n, его степени a1, a2,…,af(n) оказываются различными по модулю n и взаимно простыми с n.
В частности, для простого числа p, если a является первообразным корнем p, то a1, a2,…,ap-1 оказываются различными по модулю n и взаимно простыми с n.
Как видно из таблицы, для простого числа 19 его первообразными корнями являются числа 2, 3, 10, 13, 14 и 15.
Не все целые числа имеют первообразные корни. Этими числами могут быть числа 2, 4, pa и 2pa, где p - любое нечетное простое число.
Таблица 2.1 Степени целых чисел по модулю 19
2.1.2 Алгоритм определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней
На рисунке 2.1, слайд 2.3 приводится общая блок-схема алгоритма определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней.
Рис. 2.1. Блок-схема алгоритма вычисления степеней целого числа am
по модулю p и целых чисел, принадлежащих показателю f(p)
2.1.3 Инструкция по выполнению задания 1
Проанализировать приведенный пример СТЕП 1 совместно с данными таблицы 2.1.
С использованием ПРОГРАММЫ 1 -алгоритм Евклида нахождения наибольшего общего делителя, подобрать два взаимно простых числа a<50, p<40 (должно быть gcd (a, p) = 1).
С использованием ПРОГРАММЫ 2 - расширенный алгоритм Евклида для вычисления мультипликативного обратного, проверить подобранные числа - действительно ли они являются взаимно простыми? Если они взаимно простые, то имеется мультипликативное обратное.
2.1.4 Алгоритм выполнения задания 1. Вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю f(p)
(первообразных корней по модулю p)
В соответствии с подобранными взаимно простыми числами a и p необх?/p>