Криптография с открытым ключом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
> T1 + d T2 = 96 1 + 5 (-19) = 1 = T3, X1 + d X2 = 96 0 + 5 1 = 5 = X3, Y1 + d Y2 = 96 1 + 5 (-19) = 1 = Y3.
Так как Y3 = 1, то Y3 gcd (5, 96) = 1 наибольший общий делитель.
Тогда Y2 = d-1 mod 96 = -19. Так как Y2 отрицательное целое, то мультипликативное обратное будет 96-19 = 77.
Таким образом, для нашего примера e = 5 и d = 77.
Пример RSA-1: Вычислить ab mod n (см. раздел 1.4. - Алгоритм быстрого возведения в степень для ab mod n при больших значениях b, рис. 1.5. и слайд 7), где a = M = 19, b = e = 5 (открытый ключ) и n = (p q) = 119, С - зашифрованный текст.
Иначе
195 mod 119 = C ?
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 d) mod n = (1 1) mod 119 = 1 mod 119 = 1;
bk = b2 = 1;
c = c + 1 = 0 + 1 = 1;
d = (d a) mod n = (1 19) mod 119 = 19 mod 119 = 19 - 19 / 119 119 = 19 - 0 119 = 19.
k = k - 1 = 2 - 1 = 1.
2. k > 0, k = 1;
c = 2 c = 2 1 = 2;
d = (d d) mod n = (19 19) mod 119 = 361 mod 119 = 361 - 361 / 119 119 = 361 - 3 119 = = 361 - 357 = 4;
bk = b1 = 0;
k = k - 1 = 1 - 1 = 0.
3. k > 0, k = 0;
c = 2 c = 2 2 = 4;
d = (d d) mod n = (4 4) mod 119 = 16 mod 119 = 16 - 16 / 119 119 = 16 - 0 119 = 16;
bk = b0= 1;
c = c + 1 = 4 + 1 = 5;
d = (d a) mod n = (16 19) mod 119 = 304 mod 119 = 304 - 304 / 119 119 = 304 - 2 119 = 66.
k = k - 1 = 0 - 1 = -1.
Ответ: C = 195 mod 119 = 66.
Далее рассмотрим пример для обратного преобразования
Пример RSA-2: Вычислить ab mod n, где a = C = 66, b = d = 77 (закрытый ключ) и n = 119.
Иначе
M = 6677 mod 119 = ?
b = 7710 = 10011012, k = 6, c = 0, d = 1, a = 66, n = 119.
1. k > 0, k = 6;
c = 2 c = 2 0 = 0;
d = (d d) mod n = (1 1) mod 119 = 1 mod 119 = 1;
bk = b6 = 1;
c = c + 1 = 0 + 1 = 1;
d = (d a) mod n = (1 66) mod 119 = 66 mod 119 = 66 - 66 / 119 119 = 66 - 0 119 = 66.
k = k - 1 = 6 - 1 = 5.
2. k > 0, k = 5; b5 = 0;
c = 2 c = 2 1 = 2;
d = (d d) mod n = (66 66) mod 119 = 4356 mod 119 = 4356 - 4356 /119 119 = 4356 - (36 119) = 4356 - 4284 = 72;
k = k - 1 = 4
bk = b4 = 0;
c = c 1 = 2 2 = 4;
d = (d d) mod n = (72 72) mod 119 = 5184 mod 119 = 5184 - 5184 / 119 119 = 5184 - (43 119) = 5184 - 5117 = 67.
k = k - 1 = 4 - 1 = 3.
3. k > 0, k = 3; b3 = 1;
c = 2 c = 2 4 = 8;
d = (d d) mod n = (67 67) mod 119 = 4489 mod 119 = 4489 - 4489 /119 119 = 4489 - (37 119) = 4489 - 4403 = 86;
c = c + 1 = 8 + 1 = 9;
d = (d a) mod n = (86 66) mod 119 = 5676 mod 119 = 5676 - 5676 / 119 119 = 5676 - (47 119) = =5676 - 5593 = 83.
k = k - 1 = 3 - 1 = 2; b2 = 1.
4. k > 0, k = 2; b2 = 1;
c = 2 c = 2 9 = 18;
d = (d d) mod n = (83 83) mod 119 = 6889 mod 119 = 6889 - 6889 /119 119 = 6889 - (57 119) = 6889 - 6783 = 106;
c = c + 1 = 18 + 1 = 19;
d = (d a) mod n = (106 66) mod 119 = 6996 mod 119 = 6996 - 6996 / 119 119 = 6996 - (58 119) = 6996 - 6902 = 94.
k = k - 1 = 2 - 1 = 1; b1 = 0.
5. k > 0, k = 1; b1 = 0;
c = 2 c = 2 19 = 38;
d = (d d) mod n = (94 94) mod 119 = 8836 mod 119 = 8836 - 8836 /119 119 = 8836 - (74 119) = 8836 - 8806 = 30;
b1 = 0;
6. k > 0, k = 0; b0 = 1; c = 2 c = 2 38 = 76;
d = (d d) mod n = (30 30) mod 119 = 900 mod 119 = 900 - 900 /119 119 = 900 - (7 119) = = 900 - 833 = 67;
c = c + 1 = 76 + 1 = 77;
d = (d a) mod n = (67 66) mod 119 = 4422 mod 119 = 4422 - 4422 / 119 119 = 4422 - (37 119) = 4422 - 4403 = 19.
k = k - 1 = 0 - 1 = -1.
Так как k < 0, то получен следующий ответ.
Ответ: M = 6677 mod 119 = 19.
3.3 Общее положение по выполнению лабораторной работы. Метод зашифрования RSA
Необходимо выбрать из таблицы 1 приложения новые значения простых чисел p и q, и выполнить все примеры аналогично RSA-0, RSA-1 и RSA-2.
С целью облегчения выполнения заданий вручную (для освоения соответствующих алгоритмов) p и q выбираются двухразрядными. В качестве открытого исходного сообщения берется также двухразрядное десятичное число. Его необходимо зашифровать. В программе предусматривается автоматический контроль правильности.
3.3.1 Задание 1 - RSA-0 - подготовка для выполнения алгоритма зашифрования открытого сообщения открытым ключом RSA-1
1. Выбираем из таблицы 1 приложения два взаимно простых числа p и q. 2. С использованием вкладки Лабораторная работа 1, задание 1 испытываем выбранные числа на взаимную простату. Вводим эти числа в поля Число 1 (d) и Число 2 (f). В качестве ответа должны получить значение наибольшего общего делителя 1. 3. Вводим выбранные числа в поля Простое число 1 (p) и Простое число 2 (q), взаимно простое с числом p окна RSA-0 данной лабораторной работы. 4. Рассчитываем значение n = p q. Нажав кнопку Расчет f(n) вычислим f(n) = (p-1) (q-1).
. Для подбора соответствующего значения открытого ключа e (взаимно простого с f(n)) используем вкладку Лабораторная работа 1, задание 1