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

     2.  Выбрать произвольное число  a, 1 ≤ a ≤ р – 1.

     3.  Вычислить y = α^a (mod p).

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

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

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

     2. Выбрать случайное секретное  целое число k из [1, p – 2] такое, что нод(k, p – 1) = 1.

     3.  Вычислить k ^{– 1} (mod (p – 1)).

     4.  Вычислить r = α^k (mod p).

     5.  Вычислить s = k ^{– 1} (h(t) – ar) (mod (p – 1)).

     6.  Подпись адресата А под его текстом t есть пара (r, s). 

     Проверка подписи. Чтобы проверить подпись (r, s) адресата A под его текстом t, адресат B должен выполнить следующее.

14. Вычислить значение хэш – функции h(t).
15. Получить открытый ключ (p, α, y) адресата А.
16. Проверить, что r [1, p – 1]; если нет, отвергнуть подпись.
17. Вычислить v₁ = y^r r^s (mod p).
18. Вычислить v₂ = α^h(m)(mod p).
19. Принять подпись, если v₁ = v₂ и опровергнуть в противном случае.

 

Решение:

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

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

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

     2.  Выбрать случайное целое  a = 3564, 1 ≤ a ≤ р – 1.

     3.  Вычисляет y = α^a (mod p) = 7³⁵⁶⁴ (mod 5783) = 1366.

     4. Открытый ключ адресата A есть тройка чисел (p = 5783, α = 7, y = 1366). Секретный ключ адресата A есть число a =3564. 

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

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

     2. Выбрать случайное секретное  целое число k = 1577 из [1, p – 2] такое, что нод(k, p – 1) = 1.

     3.  Вычислят k ^{– 1} (mod (p – 1)) = 1577 ^{– 1} (mod 5783) = 111.

     4.  Вычисляет r = α^k (mod p) = 7¹⁵⁷⁷ (mod 5783) = 605.

     5.  Вычисляет s = k ^{– 1} (h(t) – ar) (mod (p – 1)) = 1252

    6.  Подпись адресата А есть пара (r = 605, s = 1252). 

     Проверка подписи. Чтобы проверить подпись (r = 605, s = 1252) адресата A под его текстом t, адресат B должен выполнить следующее.

1. Вычисляет значение хэш – функции h(t). Если текст t не изменялся, то h(t) =8058.
2. Получает открытый ключ ((p = 5783, α = 7, y = 1366)адресата А.
3. Проверяет, что r  = 605 [1, p – 1] = [1, 5783].
4. Вычисляет число v₁ = y^r r^s (mod p) = 1366⁵⁰³² ∙ 605³⁸²⁵ (mod 5783) = 2311.
5. Вычисляет число v₂ = α^h(t)(mod p) = 7⁸⁰⁵⁸  (mod 5783) = 2311.
6. Принимает подпись, ибо если v₁ = v₂ .

 

     Для Криптографической стойкости  рекомендуется брать р длиной между 512 бит (лучше 768) и 1024 бит включительно.

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

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

Зашифровать и расшифровать сообщение с помощью (обобщенной) криптосистемы ЭльГамаля над (конечным) полем Галуа GF(p^m). Взять простое число р = 31, натуральное m = 3. Неприводимый полином над _р определяется номером варианта. В качестве исходного текста взять три первые латинские буквы своей фамилии.

   23х³ + 6,   р = 31,     m = 3,    t =KAL. 

Решение:

     Числовая схема шифрования ЭльГамаля может быть обобщена для работы в любой конечной циклической группе G . Криптографическая стойкость схемы ЭльГамеля в группе G основана на трудности решения проблемы дискретного логарифма в G. Группа G должна удовлетворять следующим условиям.

1. Эффективность, то есть групповые операции в G должны вычисляться относительно просто. 
2. криптографическая стойкость, то есть решение проблемы дискретного логарифма в G должно быть практически неосуществимой.

     Ниже следуют удовлетворяющие  этим двум условиям группы, из  которых первые три наиболее  употребительны.

     1.  Мультипликативная группа  ^*_р целых чисел по модулю простого числа р.

     2.  Мультипликативная группа  ^*_2^s конечного поля  _2^s характеристики два.

     3.  Группа точек эллиптической  кривой над конечным полем.

     4.  Мультипликативная группа  ^*_q конечного поля |F_q , где q = p ^s , р есть простое число, s есть положительное простое число.

     5.  Группа обратимых элементов  ^*_n , где n есть составное целое число. 

     6.  Якобиан гиперэллиптической  кривой над конечным полем.

     7.  Класс групп мнимого квадратичного  числового поля (imaginary quadratic number field). 

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

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

     1. Выбрать подходящую (мультипликативную)  циклическую группу G порядка n.

     2.  Найти генератор α группы G.

     3.  Выбрать случайное целое  число a, 1 ≤ a ≤ n – 1.

     4.  Вычислить элемент y = α^a группы G.

     5. Открытый ключ адресата есть  пара чисел (α, y) элементов группы G. Открыто также описание умножения элементов в G. Секретный ключ адресата есть число a. 

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

     1. С помощью какого – либо  метода М, который публикуется, представить свое письмо t как элемент m группы G.

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

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

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

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

 

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

20. Взять свой секретный ключ a и вычислить целое число γ ^{– a} и найти γ ^{– a} = (γ ^a ) ^{– 1}.
21. Вычислить m = (γ ^{– a} · δ).
22. Вычислить исходный текст t от А с помощью метода M.

 

Замечание. Все адресаты могут выбрать одну и ту же циклическую группу G и ее генератор α. 
 

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

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

     1. Выбирает мультипликативную группу  G конечного поля (Е³₃₁ , {+, ∙}), элементы которого представляются полиномами из ₃₁ [х] над ₃₁  степени меньше 3 и умножение в котором выполняется по модулю неприводимого полинома f(x) = (23  0  0  6) = 23х³ + 6 из ₃₅ [х]. Группа G имеет порядок

n = p^m – 1 = 31³ – 1 = 2196.

     2.  Находит генератор α = х + 5 = (0  1  5) группы G.

     3.  Выбрать случайное целое  число a = 2, 1 ≤ a ≤ n – 1.

     4.  Вычислить элемент y = α^a (mod f(x)) = (х + 5)² (mod f(x)) = х² + 10х + 12 = (1  10  12) группы G.

     5. Открытый ключ адресата для В есть пара чисел (α = (0  1  5),

y = (1  10  12)) вместе с полиномом f(x), который определяет умножение в G, если f(x) и α не есть параметры, общие всем адресатам. Секретный ключ для В есть число a = 2. 

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

     1. Представляет свой текст  t = KAL как элемент m1 группы G. Чтобы зашифровать письмо t, адресат А кодирует текст t каким – либо способом, например, в 27 – ричной системе счисления 10 – ричным числом

u = 5 * 27² + 76 * 27 + 3 = 8778₁₀ , а затем вычисляет 31 – ричное представление числа u в виде сообщения m1 = (3 8 8 11)₃₁ , рассматриваемом как полином 5х² + 76х + 3из ₃₁ [х].

     2. Получить открытый ключ (α = (0  1  5), y = (1  10  12)) адресата В.

     3. Выбрать случайное целое число  k = 2134, 1 ≤ k ≤ n – 1.

     4. Вычислить γ = α^k = (х + 5) ²¹³⁴ (mod f(x)) = 12х² + 7х + 3 = (12  6  3),