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

Производится обмен  открытыми ключами.

Пользователь  А вычисляет  общий секретный сеансовый ключ

K= (Y_B) ^X_Amodp.

Пользователь B вычисляет общий секретный сеансовый ключ

K = (Y_A) ^X_Bmodp.

Эти последние  формулы дают одинаковые результаты:

K=(Y_B)^X_Amodp=(a^X_Вmodp)^X_Amodp=(a^X_В)^X_Amodp=a^X_В^X_Amodp= (a^X_A)^X_Bmodp= (a^X_Amodp)^X_Bmodp= (Y_A) ^X_Bmodp.

Злоумышленнику  могут быть известны величины p, a, Y_A и Y_B.

Злоумышленнику  для определения секретного ключа  пользователя В необходимо вычислить 

X_В = Ind_{a, p} (Y_B), иначеY_В = a ^X_В mod p.

Только  после этого он может определить общий секретный ключ K. Вычисление X_В из последнего соотношения (дискретного логарифма) является, вообще говоря, очень непростой задачей.

Взаимный  обмен сообщениями с использованием метода обмена ключами Диффи-Хеллмана при определенных условиях (использовании  централизованного каталога хранения параметров) обеспечивает как конфиденциальность, так и определенную степень аутентификацию.

Рассмотрим  использование данного метода на конкретном примере.

Пример: Произвести обмен ключами между двумя пользователями А и В и сгенерировать общий сеансовый секретный ключ по схеме Диффи-Хеллмана.

1. Определение  общих открытых элементов (в  начале данный пункт задания  выполняется пользователем А (условно) и полученные результаты в открытом виде передаются (условно) пользователю В). Для экономии времени одновременно пользователь В аналогичную работу выполняет с другими значениями p и a.

Это простое  число p и его первообразный корень a. Рекомендуется в качестве p выбрать двухразрядное число, равное или меньшее по значению 97. Для рассматриваемого примера, ради обеспечения простоты, мы выберем p=19.

Первообразный корень для выбранногоpможет быть определен двояко.

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

Во втором случае первообразный корень для  выбранного p подбирается из условия, что целыми числами с первообразными корнями могут быть только числа 2, 4, n^a и 2n^a(где n- любое нечетное простое число). Естественно, выбранный в данном случае первообразный корень a<p.

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

Для нашего примера p=19 и a=10 (см. таблица 3.1).

2. Выбор секретных ключей пользователей  А и В (соответственно X_A и X_B).

В соответствии с выбранным значением pопределяются секретные ключи по условиям X_A<p и X_B<p. Выбираем X_A=5 и X_B=7.

3. Вычисление в соответствии  с найденным a и выбранному p открытых ключей Y_A и Y_B(соответственно пользователями А и В) для пользователей А и В на основе X_A и X_B(при этом используется ниже указанная программа)

Y_A=a^XA mod p = 10⁵mod 19.

Y_B=a^XBmod p = 10⁷mod 19.

В действительности целые числа, используемые в приведенных  соотношениях очень большие и  выполнить данные расчеты не так  легко. Поэтому необходимо эти расчеты  производить в соответствии с  пунктом «Быстрое возведение в степень для a^bmod n при больших значениях b». В нашем примере Y_A=a^XAmodp= 10⁵mod19 = 3, то есть . Y_A= 3.

Y_B=a^XBmodp= 10⁷mod19 = 15, то есть, Y_B= 15.

4. Выполнение процесса обмена  открытыми ключами (условно).

Пользователь А получает в свое распоряжение открытый ключ пользователя В-Y_B.

Пользователь B получает в свое распоряжение открытый ключ пользователя A-Y_A.

5. Вычисление каждой стороной  значения своего сеансового ключа  (эти ключи K будут одинаковыми и используются пользователями как общий сеансовый ключ) на базе полученных открытых ключей противоположных сторон.

Пользователь A вычисляет свой сеансовый секретный ключ K

K = (Y_B)^XAmodp.

Пользователь B вычисляет свой сеансовый секретный ключ K

K= (Y_A)^XBmodp.

Для нашего примера 

Пользователь A:K= (Y_B)^XAmodp= 15⁵mod19 = 2; K= 2.

Пользователь B:K= (Y_A)^XBmodp=3⁷mod19 = 2; K= 2.

6. Посылка (условно) определенного  сообщения пользователем A пользователю B.

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

Сообщение (А) -....ЗВЕЗДА

Шестнадцатиричный (таблица 2 приложения)

 код  866 (A).…...878285878480

Двоичный  код.1000 0111 1000 0010 1000 0101 1000 0111 1000 0100 1000 0000

Гамма K (A).…1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010

Åmod 2………0010 1101 0010 1000 0010 1111 0010 1101 0010 1110 0010 1010

Гамма К (B).....1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010

Двоичный  код 1000 0111 1000 0010 1000 0101 1000 0111 1000 0100 1000 0000

Шестнадцатиричный

 код  866 (B)…..……878285878480

Сообщение (B) -....ЗВЕЗДА

7. С целью проверки совместной  работы пользователей необходимо  расшифрованное пользователем В  сообщение переслать (условно)  в открытом виде пользователю  А. 

8. Необходимо такую же работу, одновременно с пользователем  А, произвести и пользователю  В (условно) согласно п. 1 для  передачи другого слова пользователем  В пользователю А. 

1. Алгоритм Диффи-Хеллмана. Алгоритм Диффи-Хеллмана основывается на трудностях вычисления дискретных логарифмов. Злоумышленнику могут быть известны величины Q (простое число), a (первообразный корень простого числа Q), Y_A и Y_B (открытые ключи, соответственно абонентов А и В). Злоумышленнику для определения, например, секретного ключа пользователя В необходимо вычислить X_В = Inda,Q (Y_B), иначе Y_В = a^XВmod Q.
2. Асимметричная криптографическая система (система с двумя ключами, схема шифрования с открытым ключом). Отправитель и получатель используют разные ключи. Здесь ключи зашифровывания и расшифровывания различны и секретность сообщения основана на сложности вычисления ключа по некоторой производной от него информации, которая в открытом виде передается по каналу связи.
3. Закрытый ключ. Это закрытая (секретная) половина криптографической пары, используемая при шифровании с применением открытых ключей. Закрытые ключи обычно используются при расшифровке симметричных ключей сеансов, создании цифровых подписей и расшифровке данных, зашифрованных соответствующим открытым ключом.
4. Индекс b по основанию a, рассматриваемому по модулю p (иначе дискретный логарифм). Inda, p (b) или показатель степени i, при котором b = aⁱmod p, где 0 £ i £ (p-1).

 

4. Метод зашифровывания с открытым ключом RSA

 

Алгоритмы шифрования с открытым ключом зависят  от двух ключей: одного ключа для  зашифровывания и другого ключа, связанного с первым, для расшифровывания. С точки зрения вычислений, нереально определить ключ расшифровывания, зная только используемый криптографический алгоритм и ключ зашифровывания. В некоторых алгоритмах любой из этих ключей может применяться для зашифровывания, а другой - для расшифровывания.

Криптографические системы с открытым ключом зависят  от некоторой обратимой математической функции со специальными свойствами. Сложность вычисления такого рода функций  может зависеть не линейно от числа  битов в ключе, а расти более  быстро. Поэтому длина ключа должна быть достаточно большой. Однако чем  длиннее ключи, тем больше времени  требуется для выполнения процессов  зашифровывания/расшифровывания. Поэтому алгоритмы криптографии с открытым ключом в настоящее время, в основном, применяются в управлении ключами и приложениями цифровой подписи. Однако схема Райвеста-Шамира-Адлемана (RSA) стала единственной получившей широкое признание и практически применяемой схемой шифрования с открытым ключом [1]. Эта схема представляет собой блочный шифр, в котором и открытый текст, и шифрованный текст представляются целыми числами из диапазона от 0 до (n-1) для некоторого n.

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

Работа  состоит из трех частей:

• RSA-0 - подготовка к выполнению алгоритма зашифровывания открытого сообщения открытым ключом RSA-1;
• RSA-1 - выполнение алгоритма зашифровывания открытого сообщения открытым ключом RSA-1;
• RSA-2 - выполнение алгоритма расшифровывания зашифрованного сообщения секретным ключом RSA-1.

 

Операции  зашифровывания открытого текста и расшифровывания закрытого текста в RSA состоят из операций возведения большого целого числа в большую целую степень по модулю n.

Обобщенная  блок-схема генерации ключей, необходимых  для алгоритма RSA приводится на рис. 4.1.

 

Рис. 4.1. Генерация ключей для RSA

На рис. 4.2 приводится блок-схема алгоритмов зашифровывания и расшифровывания для RSA.

 

Рис. 3.2. Блок-схема алгоритмов зашифровки и  расшифровки для RSA

 

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

1. Алгоритм RSA. Алгоритм RSA основан на выражениях со степенями. Эта система основана на трудностях разложения очень больших целых чисел по степеням простых чисел.
2. Канал связи. Естественный или искусственный материальный объект (среда), обеспечивающий передачу сигнала от передатчика к приемнику. Основными каналами распространения информации в настоящее время являются, в первую очередь, Интернет, а также другие специализированные системы государственного и межгосударственного уровня.  
   В перспективе на эту роль претендуют цифровые информационно-телекоммуникационные сети интегрального обслуживания.
3. Ключ. Это конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования данных, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразований; последовательность символов, управляющая операциями шифрования и дешифрования.

 

Пример RSA-0. Выбор целого e, взаимно простого с f(n) и меньшего, чем f(n). А также определение такого d, что de = 1 modf(n) и d<f(n).

Это подготовительный этап для выполнения алгоритма RSA.

Из таблицы 1 приложения выбираем два простых  числа p= 7 и q= 17.

Вычисляем n=p´q= 7 ´ 17 = 119.

Вычисляем f(n) =(p-1)´(q-1)= 6 ´16 = 96.

Выбираем e по условию, что gcd (e, f(n)) = 1 и 1<e<f(n) Для этого будем пользоваться расширенным алгоритмом Евклида для нахождения наибольшего общего делителя двух чисел, который при определении и уточнении, что таким делителем является 1, выдает и мультипликативное обратное для e по модулю f(n).

gcd (d, f) =gcd (e=5, f(n) = 96) = 1.

Выполняем алгоритм:

X1 = 1, X2 = 0, X3 = 96.

Y1 = 0, Y2 = 1, Y3 = 5.

Y3¹ 0,

Y3¹ 1.

Q = ëX3/Y3û= ë96/5û = 19.

T1 = X1 – Q´Y1 = 1 – 19 ´ 0 = 1,

T2 = X2 – Q´Y2 = 0 – 19 ´ 1 = -19,

T3 = X3 – Q ´Y3 = 96 – 19 ´ 5 = 1.

X1 = Y1 = 0,

X2 = Y2 = 1,

X3 = Y3 = 5.

Y1 = T1 = 1,

Y2 = T2 = -19,

Y3 = T3 = 1.

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

f ´T1 + d ´ T2 = 96 ´ 1 + 5 ´ (-19) = 1 = T3,

f ´X1 + d ´ X2 = 96 ´ 0 + 5 ´ 1 = 5 = X3,

f ´Y1 + d ´ Y2 = 96 ´ 1 + 5 ´ (-19) = 1 = Y3.

Так как Y3 = 1, то Y3 gcd(5, 96) = 1 наибольший общий делитель.

Тогда Y2 =d^-1mod96 = -19. Так как Y2 отрицательное целое, то мультипликативное обратное будет 96-19 = 77.

Таким образом, для нашего примераe= 5 и d= 77.

Пример RSA-1: Вычислить a^bmodn, где a = M = 19, b =e = 5 (открытый ключ) и n = (p´q) = 119, С - зашифрованный текст.

Иначе

19⁵ mod 119 = C?

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.

Ответ:C= 19⁵mod119 = 66.

Далее рассмотрим пример для обратного преобразования