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

     p = 324733,   q = 27061,   t = KAL.

Алгоритм:

Вычисление  ключей. Каждый адресат создает открытый ключ и ему соответствующий секретный ключ. Адресат должен выполнить следующее.

     1. Выбрать два больших различных  случайных простых числа p и q примерно одного размера.

     2.  Найти n = p ∙ q и функцию Эйлера φ = φ(n) = (p − 1)(q − 1).

     3.  Взять случайное число  e, 1 < e < φ, такое, что нод(e, φ) = 1.

     4.  Найти такое целое a (1, φ), что ea ≡ 1 (mod φ). С помощью расширенного алгоритма Евклида найти то единственное целое a, 1 < d < φ, для которого ea ≡ 1 (mod φ).

     5. Открытый ключ адресата есть  пара чисел (n, e). Секретный ключ адресата есть число a. 

     Вычисление подписи. Адресат А подписывает свой текст t. Любой адресат B может проверить подпись A и извлечь из нее текст t. Адресат A должен выполнить следующее.

3. Каким – либо методом M (который публикуется) представить свой текст t в виде целого числа m, 1 < m < n – 1.
4. Найти число w = R(m) с помощью открытой функции

R : [0, n – 1] → M_R , где M_R есть некоторое числовое множество, например,

R(m) = m*m, где a*b есть результат приписывания слова b к слову a. Тогда M_R = {w = m*m: m [0, n – 1]}.

     3.  Найти число s = w ^a(mod n).

     4.  Отправить подписанный шифротекст s адресату В. 

     Проверка подписи и вычисление сообщения. Чтобы проверить подпись s адресата A и извлечь из нее сообщение m, адресат B должен выполнить следующее.

6. Получить открытый ключ (n, e) адресата A.
7. Найти число w = s ^e(mod n).
8. Проверить, что w M_R . Если нет, отвергнуть подпись s.
9. Найти число m = R^–1(w).
10. С помощью метода M найти отправленный текст t.

Решение:

   Адресат A подписывает свой текст t. Любой адресат B может проверить подпись A.

     Вычисление ключей. Адресат А выполняет следующее.

     1.  Выбирает разные простые  числа p = 324733,   q = 27061.

     2.  Находим n = p ∙ q = 324733 * 27061 = 8787599713 и функцию Эйлера

φ = φ(n) = (p − 1)(q − 1) = 324732 * 27060 = 8787247920.

     3.  Выбирает случайное число  e = 23, 1 < e < φ, с нод(e, φ) = 1.

     4. С помощью расширенного алгоритма  Евклида находит то единственное  целое a = 1910271287 (1, φ), которое удовлетворяет сравнению ea ≡ 1 (mod φ).

     5. Открытый ключ для А есть пара (n = 8787599713, e = 23). Секретный ключ для А есть число a = 1910271287.

     Вычисление подписи.  Вычисление подписи. Адресат А подписывает свой текст t произвольной длины. Любой адресат B может проверить подпись A под его текстом t. Адресат A должен выполнить следующее.

     1.  Вычислить значение хэш – функции h = h(t). Пусть текст

t = KAL, m = 11 * 27² +1 * 27 + 12 = 8058, h = h(m) = m = 8058.

2.  Вычислить s = h ^a (mod n) = 8058^1910271287 (mod 8787599713)= 5203015680. Число s есть подпись A под его текстом t.

     Проверка подписи  и вычисление сообщения. 

Чтобы проверить подпись s адресата A, адресат B должен выполнить следующее.

Получить  открытый ключ (n = 8787599713, e = 23) адресата A.

Вычислить значение хэш – функции h = h(t). Если текст t не изменялся, то h = 8058.

Вычислить h1 = s ^e(mod n) = 5203015680²³ (mod 8787599713)  = 8058.

Принять подпись, если h = h1, и отвергнуть в противном случае. Так как h = h1 = 8058, то подпись принимается.

Все вышеперечисленные  вычисления и рассуждения отражены в пункте 5.3, который представляет собой код соответствующей MathCAD – программы. 

2. КРИПТОГРАФИЧЕСКАЯ СИСТЕМА ЭЛЬ-ГАМАЛЯ С ПРОСТЫМ ПОЛЕМ  ГАЛУА
1. Шифросистема Эль-Гамаля с простым полем Галуа

Теоретическое введение:

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом,основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США и России .

Схема была предложена Тахером Эль-Гамалем в 1984 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию.

Задача 25.6

Зашифровать и расшифровать сообщение с помощью  криптосистемы ЭльГамаля. В качестве простого числа p взять большее число варианта из задачи 29. В качестве исходного текста взять три первые латинские буквы совей фамилии.

      p = 324733,       t = KAL 

Вычисление  ключей. Каждый адресат создает свой открытый ключ и ему соответствующий секретный ключ. Адресат должен выполнить следующее.

     1. Выбрать случайное простое число  p и найти генератор α мультипликативной группы ^*_р целых чисел по модулю p, используя алгоритм Гаусса.

     2.  Выбрать случайное число  a [1, p – 2] и найти y = α^a (mod p).

     3. Открытый ключ адресата есть  тройка чисел (p, α, y). Секретный ключ адресата есть число a. 

     Шифрование. Адресат А шифрует свой текст t и отправляет шифротекст адресату В. В дешифрует сообщение от А и получает исходный текст t. Адресат А должен выполнить следующее.

     1. Получить открытый ключ (p, α, y) адресата В.

     2. С помощью какого – либо  метода М, который публикуется, представить свое письмо t как сообщение в виде натурального числа m из сегмента [0,p–1]

     3. Выбрать случайное число  k, 1 ≤ k ≤ p – 2.

     4. Вычислить γ = α^k (mod p) и δ = m · y^k (mod p).

     5. Отправить свой шифротекст c = (γ, δ) адресату В. 

     Дешифрование. Чтобы получить исходный текст t по c = (γ, δ), адресат В должен выполнить следующее.

11. Взять свой секретный ключ a и вычислить целое число γ ^{p – 1 – a} (mod p).
12. Вычислить m = (γ ^{– a} · δ)(mod p), где γ ^{– a} = (γ ^{– 1} )^а , а число γ ^{– 1} есть решение сравнения х · γ ≡ 1(mod p) и вычисляется с помощью расширенного алгоритма Евклида.
13. Вычислить исходный текст t от А с помощью метода M.

 

Решение:

     Адресат А пишет письмо t = KAL адресату В.

     Вычисление ключей. Адресат В выполняет следующее.

1. Выбирает простое число p = 324733  и находит генератор α = 5 для мультипликативной группы  ^*₃₂₄₇₃₃ .
2. Выбирает случайное число а = 324715 1 ≤ а ≤ р – 2, и вычисляет

y = α^a (mod p) = 5³²⁴⁷¹⁵ (mod 324733) = 717.

     3.  Открытый ключ адресата В есть тройка (р = 324733, α = 5, у = 717). Секретный ключ адресата В есть число а = 324715. 

Шифрование. Адресат А шифрует свой текст t = KAL и выполняет следующее.

1. Получает открытый ключ (р = 324733, α = 5, у = 717) для В.
2. Представляет свой текст t = KAL в виде натурального числа m из

[0, p – 1], с помощью какого – либо метода, например, с помощью 27 – ричной системы счисления числом  m = 12*27² + 1*27 + 11 = 8058.

     3.  Выбирает случайное число  k = 201251, 1 ≤ k ≤ р – 2.

     4.  Вычисляет γ = α^k (mod p) = 6²⁰¹²⁵¹ (mod 324733) = 158123,

          δ = m · y^k (mod p) = 8058 · 158123²⁰¹²⁵¹ (mod 324733) = 193569.

     5.  Посылает шифротекст с = (γ = 158123, δ = 193569) адресату В. 

Дешифрование. Чтобы дешифровать шифротекст с = (γ = 158123, δ = 193569) от А, адресат В выполняет следующее.

1. Вычисляет

γ ^{p – 1 – a} (mod p) = 208275⁸⁵⁰⁸⁵ (mod 490663) = 15939

m = (γ ^{p -1 - a} · δ)(mod p) = ((γ ^{p -1 - a})(mod p) · δ)(mod p) = 8058

Представляет  число m 27– ричной системе счисления: m = (12  1  11)₂₇ и получает исходный текст KAL.

Замечание. Криптографическая стойкость криптосистемы ЭльГамаля основана на трудной практической осуществимости проблемы нахождения дискретного логарифма в группе ^*_р при больших простых числах р. На практике для криптографической стойкости простое число р задается двоичным числом с 1024 и более двоичными разрядами. 
 

2. Электронная цифровая подпись  Эль-Гамаля с простым полем Галуа

Теоретическое введение:

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

Задача 26.6

Вычислить и проверить подпись под сообщением с помощью криптосистемы ElGamal для электронной подписи. В качестве простого числа р взять большое число из задачи 23. В качестве исходного текста взять слова своего полного имени: фамилия, имя, отчество.

     p = 5783           t = KAL

     При использовании схемы цифровой  подписи ЭльГамаля по тексту письма t вычисляется значение хэш – функции h(t), которое затем используется при вычислении и проверке цифровой подписи под текстом сообщения. 

Вычисление  ключей. Каждый адресат создает открытый ключ и ему соответствующий секретный ключ. Далее адресат должен выполнить следующее.

          1. Выбрать случайное простое число  p и найти генератор α мультипликативной группы ^*_р .