Криптография с открытым ключом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
p>
Если ответ окажется правильным, то компьютер зачтет Вам введенный ответ, зафиксирует его (исходные данные d и f, и наибольший общий делитель) в специальном МАССИВЕ РЕЗУЛЬТАТОВ и разрешит перейти к выполнению следующего задания. При этом данный МАССИВ РЕЗУЛЬТАТОВ будет ЗАШИФРОВАН И НЕДОСТУПЕН для использования студентами. Он заполняется постепенно, по мере выполнения соответствующих заданий, остается неизменным и при определенных условиях используется программой для заполнения соответствующих полей окон соответствующих заданий.
Если ответ студента окажется неверным, то необходимо будет выполнить все расчеты заново, закрыв и повторно запустив программу.
1.1.4 Алгоритм выполнения задания 1
При запуске программы открыта вкладка задания 1 лабораторной работы 1.
Задание 1 - нахождение наибольшего общего делителя. В полях ввода Число 1 (d) и Число 2 (f) сгенерированы соответственно числа d и f. Требуется найти наибольший общий делитель этих чисел по алгоритму Евклида. Полученное значение надо ввести в поле ввода "Наибольший общий делитель (Euclid(d, f)).
Для проверки расчетов студента необходимо нажать кнопку с надписью Проверка корректности. Поля ввода со значениями чисел d и f для редактирования изначально недоступны. В ходе проверки программой верности расчетов студента все верные вычисления будут выведены в большом текстовом поле, которое находится под вышеназванными полями ввода.
Анализируя весь ход выполнения алгоритма, студент может закрепить полученные знания и одновременно обнаружить пропущенные им ошибки.
Если студент ввел неверный ответ, то ему придется ввести новые входные данные. В случае верного решения поставленной задачи соответствующая информация об этом будет выведена в большом текстовом поле, и студенту отныне станут доступны для ввода поля ввода задания 2 данной лабораторной работы. Студенту также станет доступно текущее задание, то есть поля окна задания 1. Иначе, если он один раз выполнил текущее задание правильно, то отныне ему становятся доступны для ввода ВСЕ поля ввода данного задания. При этом, в последствии, при вводе в качестве ответа неверного значения, студенту больше не придется выполнять все задание лабораторной работы с начала. Следовательно, возникает возможность коррекции вводимых данных при их подборе (данная возможность в программе реализована с целью упрощения труда студента, то есть создается условие для использования этой программы в дальнейшем в процессе выполнения ряда последующих работ). При выводе программой расчетов, она добавляет к ранее выполненным расчетам новые, не стирая первых.
1.2 Задание 2. Расширенный алгоритм Евклида для вычисления
мультипликативного обратного
1.2.1. Теория
Если gcd (d, f) = 1, то d имеет мультипликативное обратное по модулю f [1]. То есть, для положительного целого числа d < f существует такое d -1< f, что d d -1 = 1 mod f. По алгоритму Евклида нахождения наибольшего общего делителя чисел d и f, для случаев, когда делитель оказывается равным 1, естественно, можно получить и мультипликативное обратное d.
1.2.2 Расширенный алгоритм Евклида для вычисления мультипликативного обратного
На рис.1.3 (слайд 1.4) приводится общая блок-схема расширенного алгоритма Евклида.
Рис. 1.3. Расширенный алгоритм Евклида для вычисления мультипликативного обратного
Пример МОБ: gcd (d, f) = gcd (550, 1769). Вычислить мультипликативное обратное числа 550 по модулю 1769.
1. X1 = 1, X2 = 0, X3 = f = 1769;= 0, Y2 = 1, Y3 = d = 550.
Q = X3/Y3 = 1769/550 = 3.= X1 - Q Y1 = 1 - 3 0 = 1; = X2 - Q Y2 = 0 - 3 1 = - 3;= X3 - Q Y3 = 1769 - 3 550 = 119.= Y1 = 0;= Y2 = 1;= Y3 = 550.= T1 = 1;= T2 = -3;= T3 = 119.
Соотношения: T1 + d T2 = 1769 1 + 550 (-3) = 119 = T3; X1 + d X2 = 1769 0 + 550 1 =550 = X3; Y1+ d Y2= 1769 1+ 550 (-3) = 119 = Y3.
2. Y3 0; Y3 1.= X3/Y3 = 550/119 = 4.= X1 - Q Y1 = 0 - 4 1 = -4; = X2 - Q Y2 = 1 - 4 (-3) = 13;= X3 - Q Y3 = 550 - 4 119 = 74.= Y1 = 1;= Y2 = -3;= Y3 = 119.= T1 = -4;= T2 = 13;= T3 = 74.
Соотношения: T1 + d T2 = 1769 (-4) + 550 13 = 7070 + 7150 = 74 = T3; X1 + d X2 = 1769 1 + 550 (-3) = 1769 - 1650 = 119 = X3; Y1+ d Y2= 1769 1+ 550 (-3) = 1769 - 1650 = 119 = Y3.
3. Y3 0; Y3 1.= X3/Y3 = 119/74 = 1.= X1 - Q Y1 = 1 - 1 (-4) = 5; = X2 - Q Y2 = -3 - 1 (13) = -16;= X3 - Q Y3 = 119 - 1 74 = 45.= Y1 = -4;= Y2 = 13;= Y3 = 74.= T1 = 5;= T2 = -16;= T3 = 45.
Соотношения: T1 + d T2 = 1769 5 + 550 (-16) = 8845 + 8800 = 45 = T3; X1 + d X2 = 1769 (-4) + 550 (13) = -7076 + 7150 = 74 = X3; Y1+ d Y2= 1769 5+ 550 (-16) = 8845 - 8800 = 45 = Y3.
4. Y3 0; Y3 1.= X3/Y3 = 74/45 = 1. = X1 - Q Y1 = (-4) - 1 5 = -9; = X2 - Q Y2 = 13 - 1 (-16) = 29;= X3 - Q Y3 = 74 - 1 45 = 29.= Y1 = 5;= Y2 = -16;= Y3 = 45.= T1 = -9;= T2 = 29;= T3 = 29.
Соотношения: T1 + d T2 = 1769 (-9) + 550 29 = -15927 + 15950 = 29 = T3; X1 + d X2 = 1769 5 + 550 (-16) = 8845 - 8800 = 45 = X3; Y1+ d Y2= 1769 (-9)+ 550 29 = -15921 + 15950 = 29 = Y3.
5. Y3 0; Y3 1.= X3/Y3 = 45/29 = 1.= X1