Криптография с открытым ключом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
i>- Q Y1 = 5 - 1 (-9) = 14; = X2 - Q Y2 = (-16) - 1 29 = -45;= X3 - Q Y3 = 45 - 1 29 = 16.= Y1 = -9;= Y2 = 29;= Y3 = 29.= T1 = 14;= T2 = -45;= T3 = 16.
Соотношения: T1 + d T2 = 1769 14 + 550 (-45) = 24766 - 24750 = 16 = T3; X1 + d X2 = 1769 (-9) + 550 29 = -15921 + 15950 = 29 = X3; Y1+ d Y2= 1769 14 + 550 (-45) = 24766 - 24750 = 16 = Y3.
6. Y3 0; Y3 1.= X3/Y3 = 29/16 = 1.= X1 - Q Y1 = (-9) - 1 14 = -23;
T2 = X2 - Q Y2 = 29 - 1 (-45) = 74;= X3 - Q Y3 = 29 - 1 16 = 13.
X1 = Y1 = 14;= Y2 = -45;= Y3 = 16.= T1 = -23;= T2 = 74;= T3 = 13.
Соотношения: T1 + d T2 = 1769 (-23) + 550 74 = -40687 + 40700= 13 = T3; X1 + d X2 = 1769 14 + 550 (-45) = 24766 - 24750 = 16 = X3; Y1+ d Y2= 1769 (-29) + 550 74 = -40687 + 40700 = 13 = Y3.
7. Y3 0; Y3 1.= X3/Y3 = 16/13 = 1.= X1 - Q Y1 = 14 - 1 (-23) = 37; = X2 - Q Y2 = (-45) - 1 74 = -119;= X3 - Q Y3 = 16 - 1 13 = 3.= Y1 = -23;= Y2 = 74;= Y3 = 13.= T1 = 37;= T2 = -119;= T3 = 3.
Соотношения: T1 + d T2 = 1769 37 + 550 (-119) = 65453 - 65450= 3 = T3; X1 + d X2 = 1769 (-23) + 550 74 = -40687 + 40700 = 13 = X3; Y1+ d Y2= 1769 37 + 550 (-119) = 65453 - 65450 = 3 = Y3.
8. Y3 0; Y3 1.= X3/Y3 = 13/3 = 4.= X1 - Q Y1 = (-23) - 4 37 = -171;
T2 = X2 - Q Y2 = 74 - 4 (-119) = 550;= X3 - Q Y3 = 13 - 4 3 = 1.= Y1 = 37;= Y2 = -119;= Y3 = 3.= T1 = -171;= T2 = 550;= T3 = 1.
Соотношения: T1 + d T2 = 1769 (-171) + 550 550 = -302499 + 302500= 1 = T3; X1 + d X2 = 1769 37 + 550 (-119) = 65453 - 65450 = 3 = X3; Y1+ d Y2= 1769 (-171) + 550 550 = -302499 + 302500 = 1 = Y3.
9. Y3 = 1.
Q = X3/Y3 = 1/1 = 1.= X1 - Q Y1 = -171 - 1 (-171) = 0; = X2 - Q Y2 = 550 - 1 550 = 0;= X3 - Q Y3 = 1 - 1 1 = 0.= Y1 = -171;
X2 = Y2 = 550;= Y3 = 1.
Y1 = T1 = 0;= T2 = 0;= T3 = 0.
Соотношения: T1 + d T2 = 1769 0 + 550 0 = 0 = T3; X1 + d X2 = 1769 (-171) + 550 550 = - 302499 + 302500= 1 = X3; Y1+ d Y2= 1769 0 + 550 0 = 0 = Y3.
Так как на предыдущем (на восьмом) этапе
f Y1+ d Y2= 1769 (-171) + 550 550 = -302499 + 302500 = 1 = Y3,
и d Y2 = 1 + f (-Y1), то d Y2 1 mod 1769.
Основные параметры вычислений занесены в таблицу (табл. 1.1).
Таблица 1.1 Параметры вычислений gcd (550, 1769) = 1
ЭтапыQX1X2X3Y1Y2Y30-1017690155013015501-3119241-3119-4137431-413745-1645415-1645-9292951-9292914-45166114-4516-23741371-23741337111938437-1193-171550191-1175501000
Ответ: gcd (550, 1769) = 1 и 550 550 1 mod 1769.
1.2.3 Инструкция по выполнению задания 2
Проанализировать пример МОБ. Из таблицы простых чисел (табл. 1) подобрать пару взаимно простых чисел d и f, таких, что d < f. С использованием программы предыдущего задания (ПРОГРАММА 1 - алгоритм Евклида нахождение наибольшего общего делителя) проверить - действительно ли подобранные числа являются взаимно простыми?
ВРУЧНУЮ, С ИСПОЛЬЗОВАНИЕМ КАЛЬКУЛЯТОРА, определить мультипликативное обратное для d по модулю f (то есть такое d -1< f, что ff -1 = 1).
(Здесь также может быть использована студенческая программа на основаниях, указанных в предыдущем задании 1).
Ввести в компьютер полученный ответ и выбранные числа d и f и запустить ПРОГРАММУ 2 - расширенный алгоритм Евклида для вычисления мультипликативного обратного.
Если результат окажется верным, то программа зачтет Вашу работу, зафиксирует исходные данные и значение ответа в специальном массиве аналогично предыдущему заданию и позволит перейти к выполнению следующего задания 3. В противном случае придется повторно выполнить данное задание 2 с испытанием новой пары чисел (введенные предыдущие исходные данные программой не воспринимаются).
1.2.4 Алгоритм выполнения задания 2
Задание 2 - расширенный алгоритм Евклида для вычисления мультипликативного обратного. Выбираются два числа - d и f (взаимно простые). Они вводятся соответственно в поля ввода Число(d) и Модуль(f). С использованием алгоритма Евклида необходимо подтвердить тот факт, что данные числа являются взаимно простыми. Для этого переходим в окно задания 1, вводим исходные числа в соответствующие поля окна задания 1 и проверяем эти числа - являются ли они взаимно простыми (их наибольший общий делитель должен быть равен 1). При этом исходные данные окна задания 2 не должны меняться.
Возвращаемся к окну задания 2, вручную (или с использованием составленной студентом программы) вычисляем значение требуемого мультипликативного обратного.
Полученный ответ необходимо ввести в поле ввода под названием Мультипликативное обратное числа d по модулю f. Для проверки программой расчетов студента нажать кнопку с надписью Проверка корректности. Поля ввода со значениями чисел d и f для редактирования уже недоступны. В ходе проверки программой верности расчетов студента все верные расчеты будут выведены в большом текстовом поле, которое находится под выше названными полями ввода.
Анализируя весь ход выполнения алгоритма в этом поле, студент может закрепить полученные знания и одновременно обнаружить пропущенные им оши