8 Лекция. Основы криптографии. Криптография с асимметричными ключами.

Алгоритм Диффи — Хеллмана

http://ru.wikipedia.org/wiki/Алгоритм_Диффи-Хеллмана

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

Рис. Получение симметричного ключа на алгоритме Диффи — Хеллмана

Алгоритм:

1. генерируются закрытые ключи a и b (случайное натуральное число)
2. генерируются открытые параметры p и g и передаются другой стороне

   p - случайное простое число

   g - первообразный корень по модулю p (находится из условия g^φ(p) mod p ≡1  где φ(p) функция Эйлера, существует множество корней)

3. вычисление открытых ключей A и B

   A = g^a mod p

   B = g^b mod p

4. обмен открытыми ключами
5. вычисляется общий секретный ключ K

K = B^a mod p

K = A^b mod p

 

ключ К равный с обеих сторон, потому что:

B^a mod p = (g^b mod p)^a mod p = g^ab mod p = (g^a mod p)^b mod p = A^b mod p

Пример:

Ева - криптоаналитик. Она читает пересылку Боба и Алисы, но не изменяет содержимого их сообщений.

открытая - закрытая

• K = секретный ключ. K = 2
• g = открытое простое число. g = 5
• p = открытое простое число. p = 23
• a = секретный ключ Алисы. a = 6
• A = открытый ключ Алисы. A = g^a mod p = 8
• b = секретный ключ Боба. b = 15
• B = открытый ключ Боба. B = g^b mod p = 19 

В случае (5⁶ mod 23 = 8) , 8-это остаток деления 5⁶/23

 Получив симметричные ключи шифруются сообщения симметричным алгоритмом.

Рис. Получение симметричных ключей из ассиметричных

Алгоритм RSA

http://ru.wikipedia.org/wiki/RSA

Алгоритм генерации пары ассиметричных ключей RSA:

1. генерируются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое).
2. вычисляется их произведение n=pq , которое называется модулем.
3. вычисляется значение функции Эйлера от числа n:
   φ(n)=(p-1)(q-1)
4. p и q уничтожаются.
5. выбирается целое число (открытая экспонента) e(1<e<φ(n)) , взаимно простое со значением функции φ(n).

6. вычисляется число (закрытая экспонента) d,
   d это первообразный корень по модулю φ(n)   e·d mod φ(n) ≡1 .
   d находится с помощью расширенного алгоритма Евклида (http://ru.wikipedia.org/wiki/Расширенный_алгоритм_Евклида)
   как коэффициент уравнения φ(n)·s+e·d=1
   Расширенный алгоритм Евклида для нахождения НОД и коэффициентов s и d. 
   r₁ = φ(n) − q₀e
   r₂ = e − q₁ r₁ = e − q₁ (φ(n) − q₀ e) = −q₁ φ(n) + (1 + q₁ q₀ )e
   r₃ = r₁ − q₂ r₂ = φ(n) − q₀ e − q₂ (−q₁ φ(n) + (1 + q₁ q₀ )e) = (1 + q₁ q₂ )φ(n) − (q₀ + q₂ (1 + q₁ q₀ ))e

   ..........................................................................................................................
   
   r_i - остатки от деления.
   В случае если r₂=1 (найден НОД), получим

   d=(1 + q₁ q₀ )

   В случае если r₃=1 (коэффициент со знаком "-"), получим
   

   d=− (q₀ + q₂ (1 + q₁ q₀ )+φ(n)

7. число φ(n) - уничтожается.
8. пара e, n публикуется в качестве открытого ключа RSA
9. пара d, n играет роль секретного ключа RSA

Предположим, сторона B хочет послать стороне A сообщение M.

Алгоритм шифрования:

• взять открытый ключ (e,n) стороны A
• взять открытый текст M
• зашифровать сообщение P_A(M)=M^emod n .

Алгоритм расшифровки:

• принять зашифрованное сообщение  С=P_A(M)
• применить свой секретный ключ (d,n) для расшифровки сообщения S_A(C)=C^dmod n .

 Рис. Шифрование и расшифровка RSA

Пример:

• генерируем два числа p и q
  p=61 и q=53.
• вычислим n=pq 
  n = 61 · 53 = 3233.
• вычислим φ(n)
  φ(3233)=φ(n)=(p-1)(q-1)=(61-1)(53-1)=3120.
• выберем число из 1<e<3120
  e=17.
• вычислим d 
  r₁ = φ(n) − q₀e= 3120-183*17=9
  r₂ = e − q₁ r₁ = e − q₁ (φ(n) − q₀ e) = −q₁ φ(n) + (1 + q₁ q₀ )e=17-9*1=-3120*1+(183*1+1)*17=8
  r₃ = r₁ − q₂ r₂ = φ(n) − q₀ e − q₂ (−q₁ φ(n) + (1 + q₁ q₀ )e) = (1 + q₁ q₂ )φ(n) − (q₀ + q₂ (1 + q₁ q₀ ))e=9-8*1=3120*(1+1*1)-(183+1*(1+1*183))*17=3120*2-367*17=1
  
  коэффициенты уравнения φ(n)·s+e·d=1
  s=2 и d=-357
  
  d = -367+φ(n)=-367+3120= 2753
• открытый ключ (n=3233, e=17) 
• закрытый ключ  (n=3233, d=2753)
• зашифруем текст m=65
• зашифруем C=P_A(M)=M^emod n=65¹⁷mod 3233=2790 .
• расшифруем  S_A(C)=C^dmod n=2790²⁷⁵³mod 3233=65