Криптография с открытым ключом

f ´X1 + d ´X2 = 1769 ´ (-23) + 550 ´ 74 = -40687 + 40700 = 13 = X3;

f ´Y1+ d ´ Y2= 1769 ´ 37 + 550 ´ (-119) = 65453 - 65450 = 3 = Y3.

8. Y3 ¹ 0; Y3 ¹ 1.

Q =ëX3/Y3û= ë13/3û = 4.

T1 = X1 – Q ´ Y1 = (-23) – 4 ´ 37 = -171;

T2 = X2 – Q ´Y2 = 74 – 4 ´ (-119) = 550;

T3 = X3 – Q ´Y3 = 13 – 4 ´ 3 = 1.

X1 = Y1 = 37;

X2 = Y2 = -119;

X3 = Y3 = 3.

Y1 = T1 = -171;

Y2 = T2 = 550;

Y3 = T3 = 1.

Соотношения:

f ´T1 + d ´T2 = 1769 ´ (-171) + 550 ´ 550 = -302499 + 302500= 1 = T3;

f ´X1 + d ´X2 = 1769 ´ 37 + 550 ´ (-119) = 65453 - 65450 = 3 = X3;

f ´ Y1+ d ´ Y2= 1769 ´ (-171) + 550 ´ 550 = -302499 + 302500 = 1 = Y3.

9. Y3 = 1.

Q =ëX3/Y3û= ë1/1û = 1.

T1 = X1 – Q ´Y1 = -171 – 1 ´ (-171) = 0;

T2 = X2 – Q ´Y2 = 550 – 1 ´ 550 = 0;

T3 = X3 – Q ´ Y3 = 1 – 1 ´ 1 = 0.

X1 = Y1 = -171;

X2 = Y2 = 550;

X3 = Y3 = 1.

Y1 = T1 = 0;

Y2 = T2 = 0;

Y3 = T3 = 0.

Соотношения:

f ´T1 + d ´ T2 = 1769 ´ 0 + 550 ´ 0 = 0 = T3;

f ´X1 + d ´ X2 = 1769 ´ (-171) + 550 ´ 550 = - 302499 + 302500= 1 = X3;

f´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).

Таблица 2.1 Параметры вычислений gcd(550, 1769) = 1

Этапы	Q	X1	X2	X3	Y1	Y2	Y3
0	-	1	0	1769	0	1	550
1	3	0	1	550	1	-3	119
2	4	1	-3	119	-4	13	74
3	1	-4	13	74	5	-16	45
4	1	5	-16	45	-9	29	29
5	1	-9	29	29	14	-45	16
6	1	14	-45	16	-23	74	13
7	1	-23	74	13	37	1119	3
8	4	37	-119	3	-171	550	1
9	1	-117	550	1	0	0	0

 

Ответ:gcd (550, 1769) = 1 и 550 ´ 550 º 1 mod 1769.

2.3 Алгоритм быстрого возведения в степень для a^b mod n при больших значениях b

Во многих криптографических алгоритмах приходится выполнять операции возведения в  большую целую степень другого  целого числа (тоже большого) по модулю n. Если операцию возведения в степень выполнять непосредственно целыми числами и только потом проводить сравнение по модулю n, то промежуточные значения окажутся просто огромными.

Известно, что:

[(a₁ mod n) ´ (a₂ mod n)] mod n = (a₁´ a₂) mod n.

Тогда, мы можем рассматривать промежуточные результаты по модулю n. Это намного облегчает вычисления. Будем вычислять a^bmod n.

Будем пользоваться следующим алгоритмом.

Степень b представляется в двоичной системе счисления. Через k будем обозначать номера разрядов полученного двоичного числа, начиная с нуля справа налево. Через b_i будем обозначать значение i-го разряда двоичного числа. Значение c в конце выполнения алгоритма будет соответствовать значению вычисленной степени.

На рис. 1.4 приводится блок-схема алгоритма быстрого возведения в степень для a^bmod n при больших значениях b.

Далее приводятся два примера, поясняющие работу данного  алгоритма.

Рис. 2.2. Блок-схема алгоритма быстрого вычисления a^bmod n

 

Пример 1: Вычислить a^bmodn, где a= 19, b = 5 и n= 119. Иначе, 19⁵ mod 119 =?

b = 5₁₀ = 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;

b_k= b₂= 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;

b_k= b₁= 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;

b_k= b₀= 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.

Ответ: 19⁵ mod 119 = 66.

Пример 2: Вычислитьa^bmodn, гдеa= 66,b= 77иn= 119.Иначе, 66⁷⁷ mod 119=?

b = 77₁₀ = 1001101₂, 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;

b_k= b₆= 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; b₅= 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;

b_k= b₄= 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; b₃= 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; b₂= 1.

4.k> 0, k = 2; b₂= 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; b₁= 0.

5.k> 0, k = 1; b₁= 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;

b₁= 0;

6.k> 0, k = 0; b₀= 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, то получен следующий ответ.

Ответ: 66⁷⁷mod119 = 19.

 

 

3. Алгоритм вычисления степеней целого числа a^m по модулю p 
и целых чисел, принадлежащих показателю f(p),- первообразных корней по модулю p. Обмен ключами по схеме Диффи-Хеллмана

 

Для реализации данного метода необходимо вычислить первообразные корни по модулю, с частичным использованием уже освоенных математических методов и алгоритмов. Далее определяются и рассчитываются открытый и секретный ключи абонентов, производится обмен открытыми ключами абонентов, вычисляются каждой стороной общий секретный сеансовый ключ. Затем производятся зашифровывание определенного открытого текста и его расшифровывание с использованием этого общего сеансового ключа.

Этот  процесс состоит из двух частей:

• алгоритм вычисления степеней целого числа a^m по модулю p и целых чисел, принадлежащих показателю f(p)- первообразных корней по модулю p;
• генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети.

3.1  Алгоритм вычисления степеней целого числа a^m 
по модулю p и целых чисел, принадлежащих показателю  
f(p) - первообразных корней по модулю p

 

В дальнейшем нам понадобятся некоторые важные понятия из теории чисел.

Число положительных  целых значений, которые меньше 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 a^f(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.Следовательно,3⁴ = 81 º 1mod10.

Важным является следующее.

Если a и n являются взаимно простыми, то существует, по крайней мере, одно целое число m, удовлетворяющее соотношению a^mº 1 mod n, где m=f(n). Для наименьшего из положительных m, при которых выполняется указанное условие, используются следующие названия:

• порядок числа a по модулю n;
• показатель, которому принадлежит a по модулю n;
• длина периода последовательности, генерируемой степенями a.

Пример 1. Рассмотрим степени числа 5 по модулю 19:

 

Поэтому в нашем примере, любые две  степени числа 5, показатели которых  отличаются на 9 (или на число, кратное 9), сравнимы по модулю 19. Иначе, последовательность является периодической с периодом, равным наименьшему положительному показателю m, при котором 5^m= 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, его степени a¹, a²,…,a^f(n) оказываются различными по модулю n и взаимно простыми с n.

В частности, для простого числа p, если a является первообразным корнем p, то a¹, a²,…,a^p-1 оказываются различными по модулю n и взаимно простыми с n.

Как видно  из таблицы, для простого числа 19 его  первообразными корнями являются числа 2, 3, 10, 13, 14 и 15.

Не все целые числа  имеют первообразные корни. Этими  числами могут быть числа 2, 4, p^a и 2p^a, где p- любое нечетное простое число.

  Таблица 3.1 Степени целых чисел по модулю 19

На рисунке 3.1, приводится общая блок-схема алгоритма определения степеней целых чисел (a^m) по конкретно заданному модулю p и одновременно его первообразных корней.

Рис. 3.1. Блок-схема алгоритма вычисления степеней целого числа a^m 
по модулю p и целых чисел, принадлежащих показателю f(p)

 

3.2 Генерация и обмен секретными  ключами по схеме Диффи-Хеллмана  между пользователями сети

 

Эффективность алгоритма Диффи-Хеллмана опирается  на трудностях вычисления дискрет-ных  логарифмов. В общем виде

yºg^x modp,

вычисление y при заданных g, x и p является относительно простой задачей даже при очень больших значениях x (имеются соответствующие эффективные алгоритмы). Однако если заданыy, g и p, то вычисление x (дискретное логорифмирование) является, вообще говоря, очень непростой задачей. Согласно [1], до недавного времени сложность асимптотически наиболее быстрого из известных алгоритмов вычисления дискретных логарифмов по модулю простого числа оценивалась величиной порядка

e^z, где z = ((lnp)^1/3ln (lnp))^2/3.

Теперь  рассмотрим алгоритм открытого распределения ключей Диффи-Хеллмана [1, 2]

Алгоритм  Диффи-Хелмана основывается на трудностях вычисления дискретных логарифмов.

Глобальные открытые элементы:

простое число p;

первообразный корень простого числа pÞa, где a<p.

Вычисление ключа пользователем  А:

Пользователь А выбирает случайное целое число X_A<p и вычисляет      Y_A = a^X_A modp.

X_A<p- секретная величина (закрытый ключ пользователя А);

Y_A - открытая величина (открытый ключ пользователя А).

Вычисление ключа пользователем  В:

Пользователь В выбирает случайное целое число X_В<p и вычисляет      Y_В = a^X_Вmodp.

X_В<p- секретная величина (закрытый ключ пользователя В);

Y_В - открытая величина (открытый ключ пользователя B).