Криптография с открытым ключом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
бки.
Если студент ввел неверный ответ, то ему придется ввести новые входные данные.
В случае верного решения студентом поставленной задачи информация о верности решения будет выведена в большом текстовом поле, и студенту станут доступны для ввода поля ввода задания 3.
Студенту также станут доступны поля текущего задания, то есть задания 2. Иначе, если студент один раз выполнил данное задание верно, то отныне ему становятся доступны для ввода ВСЕ поля ввода окна этого задания. При этом при вводе в качестве ответа неверного значения, больше не придется выполнить все задание 2 данной лабораторной работы с начала (данная возможность в программе реализована с целью упрощения труда студента в ходе ряда последующих работ).
1.3 Задание 3. Алгоритм быстрого возведения в степень для ab mod n при больших значениях b
1.3.1 Теория
Во многих криптографических алгоритмах приходится выполнять операции возведения в большую целую степень другого целого числа (тоже большого) по модулю n. Если операцию возведения в степень выполнять непосредственно целыми числами и только потом проводить сравнение по модулю n, то промежуточные значения окажутся просто огромными.
Вспомним следующее свойство арифметики в классах вычетов:
[(a1 mod n) (a2 mod n)] mod n = (a1 a2) mod n.
Значит, мы можем рассматривать промежуточные результаты по модулю n. Это намного облегчает вычисления. Будем вычислять ab mod n.
Будем пользоваться следующим алгоритмом.
Степень b представляется в двоичной системе счисления. Через k будем обозначать номера разрядов полученного двоичного числа, начиная с нуля справа налево. Через bi будем обозначать значение i-го разряда двоичного числа. Значение c в конце выполнения алгоритма будет соответствовать значению вычисленной степени.
1.3.2 Алгоритм быстрого возведения в степень для ab mod n при больших значениях b
На рис. 1.4 (слайд 1. 5) приводится блок-схема алгоритма быстрого возведения в степень для ab mod n при больших значениях b.
Далее приводятся два примера, поясняющие работу данного алгоритма.
Рис. 1.4. Блок-схема алгоритма быстрого вычисления ab mod n
Пример БВОЗ 1: Вычислить ab mod n, где a = 19, b = 5 и n = 119. Иначе, 195 mod 119 = ?
b = 510 = 101, k = 2, c = 0, d = 1, a = 19, n = 119.
1. k > 0, k = 2;
c = 2 c = 2 0 = 0;= (d d) mod n = (1 1) mod 119 = 1 mod 119 = 1;k = b2 = 1;= c + 1 = 0 + 1 = 1; = (d a) mod n = (1 19) mod 119 = 19 mod 119 = 19 - 19 / 119 119 = 19 - 0 119 = 19.= k - 1 = 2 - 1 = 1.
2. k > 0, k = 1;= 2 c = 2 1 = 2;= (d d) mod n = (19 19) mod 119 = 361 mod 119 = 361 - 361 / 119 119 = 361 - 3 119 = 361 - 357 = 4;k = b1 = 0;= k - 1 = 1 - 1 = 0.
3. k > 0, k = 0;= 2 c = 2 2 = 4;= (d d) mod n = (4 4) mod 119 = 16 mod 119 = 16 - 16 / 119 119 = 16 - 0 119 = 16;k = b0= 1;= c + 1 = 4 + 1 = 5; = (d a) mod n = (16 19) mod 119 = 304 mod 119 = 304 - 304 / 119 119 = 304 - 2 119 = =66.= k - 1 = 0 - 1 = -1.
Ответ: 195 mod 119 = 66.
Пример БВОЗ 2: Вычислить ab mod n, где a = 66, b = 77 и n = 119. Иначе, 6677 mod 119 = ?= 7710 = 10011012, k = 6, c = 0, d = 1, a = 66, n = 119.
1. k > 0, k = 6;= 2 c = 2 0 = 0;= (d d) mod n = (1 1) mod 119 = 1 mod 119 = 1;k = b6 = 1;= c + 1 = 0 + 1 = 1; = (d a) mod n = (1 66) mod 119 = 66 mod 119 = 66 - 66 / 119 119 = 66 - 0 119 = 66.= k - 1 = 6 - 1 = 5.
2. k > 0, k = 5; b5 = 0;= 2 c = 2 1 = 2;= (d d) mod n = (66 66) mod 119 = 4356 mod 119 = 4356 - 4356 /119 119 = 4356 - (36 119) = 4356 - 4284 = 72;= k - 1 = 4;k = b4 = 0;= c 1 = 2 2 = 4; = (d d) mod n = (72 72) mod 119 = 5184 mod 119 = 5184 - 5184 / 119 119 = 5184 - (43119) = 5184 - 5117 = 67.= k - 1 = 4 - 1 = 3.
3. k > 0, k = 3; b3 = 1;= 2 c = 2 4 = 8;= (d d) mod n = (67 67) mod 119 = 4489 mod 119 = 4489 - 4489 /119 119 = 4489 - (37 119) = 4489 - 4403 = 86;= c + 1 = 8 + 1 = 9; = (d a) mod n = (86 66) mod 119 = 5676 mod 119 = 5676 - 5676 / 119 119 = 5676 - (47 119) = 5676 - 5593 = 83.= k - 1 = 3 - 1 = 2; b2 = 1.
4. k > 0, k = 2; b2 = 1;= 2 c = 2 9 = 18;= (d d) mod n = (83 83) mod 119 = 6889 mod 119 = 6889 - 6889 /119 119 = 6889 - (57 119) = 6889 - 6783 = 106;= c + 1 = 18 + 1 = 19; = (d a) mod n = (106 66) mod 119 = 6996 mod 119 = 6996 - 6996 / 119 119 = 6996 - (58 119) = 6996 - 6902 = 94.= k - 1 = 2 - 1 = 1; b1 = 0.
5. k > 0, k = 1; b1 = 0;= 2 c = 2 19 = 38;= (d d) mod n = (94 94) mod 119 = 8836 mod 119 = 8836 - 8836 /119 119 = 8836 - (74 119) = 8836 - 8806 = 30;1 = 0;
6. k > 0, k = 0; b0 = 1;= 2 c = 2 38 = 76;= (d d) mod n = (30 30) mod 119 = 900 mod 119 = 900 - 900 /119 119 = 900 - (7 119 = = 900 - 833 = 67; = c + 1 = 76 + 1 = 77; = (d a) mod n = (67 66) mod 119 = 4422 mod 119 = 4422 - 4422 / 119 119 = 4422 - (37 119) = 4422 - 4403 = 19. = k - 1 = 0 - 1 = -1.
Так как k < 0, то получен следующий ответ.
Ответ: 6677 mod 119 = 19.
1.3.3 Инструкция по выполнению задания 3
Проанализировать приведенный алгоритм быстрого вычисления ab mod n по рассмотренным выше примерам БВОЗ 1 и БВОЗ 2. Из таблицы простых