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

      y^k = (х² + 10х + 12) ²¹³⁴  (mod f(x)) = 3х² =(3  0  0)

      δ = m1 · y^k = (3 8 8 11)· (3  0  0)=  6х² + 3х + 8 = (6 3 8).

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

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

1. Пользуясь своим секретным ключом a, адресат В вычисляет следующие элементы группы

γ ^a = (3 0 0)² = (3х²)²  (mod f(x)) = 3х² = (3  0  0),

γ ^{– a} = (γ ^a ) ^{– 1} = (3  12) .

2. Вычислить m1 = (γ ^{– a} · δ) == 11х² + 17х + 9 = (9 8 7)
3. Чтобы получить текст t по элементу m, адресат В производит следующие вычисления.

m1 = (9 8 7)₃₁ = 5*35² + 76*32 + 3 = 8778₁₀ = (5  76  3)₂₇  , откуда текст

t =KAL. 
 

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

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

m = 3. Неприводимый полином над _р взять из задачи 27. В качестве исходного текста взять слова своего полного имени: фамилия, имя, отчество.

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

Решение:

     Схема электронной цифровой подписи  ЭльГамаля, основанная на мультипликативной группе ^*_р , может быть обобщена на любую конечную абелеву группу G. Алгоритм подписи использует криптографическую хэш – функцию h: {0, 1}*→ _n , где n есть число элементов в G. Предполагается, что каждый элемент r из G может быть представлен в бинарной записи f(r) c тем, чтобы можно было вычислить значение хэш – функции h(f(r)).

     Алгоритм вычисления хэш – функции публикуется.

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

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

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

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

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

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

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

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

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

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

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

     3.  Вычислить целое число  k ^{– 1} (mod (n)).

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

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

     6.  Вычислить число m = k ^{– 1} (h(t) – ar(r)) (mod (n)).

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

 

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

23. Вычислить значение хэш – функции h(t).
24. Получить открытый ключ (α, y) для адресата А.
25. Вычислить значение хэш – функции h(r).
26. Вычислить в группе G элементы: v₁ = y^h(r) r^m, v₂ = α^h(t).
27. Принять подпись, если v₁ = v₂ и опровергнуть в противном случае.

 

     Схема электронной (цифровой) подписи  ЭльГамаля с мультипликативной группой конечного поля |F_p^m , р = 31, m = 3. Пусть для удобства элемент поля а₂ х² + а₁ х + а₀  представляется р – ричной стрингом (а₂ а₁ а₀). 

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

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

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

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

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

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

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

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

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

2. Вычисляет значение хэш – функции h(t). Пусть для примера h(t) =1550.

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

     3.  Вычисляет целое число  k ^{– 1} (mod (n)) = 1579 ^{– 1} (mod 923520) = 5869.

     4.  Вычисляет в группе G элемент r = α^k = (0 1 5)¹⁵⁷⁹ = (х + 5)¹⁵⁷⁹ (mod f(x)) = = (2  0  10).

     5.  Вычисляет значение хэш – функции h(r), например, следующим образом. По r = (2  0  10) вычисляет в _n 10-ричное число (2  0  10)₃₁ = 2х² + 0х + 10 = 2*31² + 0*31 + 10 = 3552₁₀. Пусть для примера h(r) = 1932₁₀.

     6.  Вычисляет в  _n число m = k ^{– 1} (h(t) – ah(r)) (mod (n)) = 1579 ^{– 1} · (1550 – - 2*3552) (mod (n)) = 23624.

    7.  Подпись адресата А под его текстом t есть пара(r=(3 21 18), m=23624₁₀). 

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

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

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

   3.  Вычислить значение хэш – функции h(r). Если вектор r не менялся, то h(r) = 1932₁₀.

4. Вычислить в группе G элементы:

v₁ = y^h(r) r^m  = (28 15 26)³⁵⁵² ∙ (2 0 10)²³⁶²⁴ =(28х² + 15х +26)³⁵⁵² · (2х² + 0х + 10)²³⁶²⁴   (mod (f(x))) = (21  8  12),

v₂ = α^h(t) = (0  1  5)¹⁵⁵⁰  = (x + 5)¹⁵⁵⁰  (mod (f(x))) = (21  6  27).

5. Так как v₁ = v₂ , то В принимает подпись адресата А.

4. КРИПТОГРАФИЧЕСКАЯ СИСТЕМА DSA
1. Электронная цифровая подпись DSA

DSA (Digital Signature Algorithm) — алгоритм с использованием открытого ключа для создания электронной подписи, но не для шифрования (в отличие от RSA и схемы Эль-Гамаля). Подпись создается секретно, но может быть публично проверена. Это означает, что только один субъект может создать подпись сообщения, но любой может проверить её корректность. Алгоритм основан на вычислительной сложности взятия логарифмов в конечных полях.

(Задача  29.6)

     Вычислить и проверить подпись  под сообщением с помощью криптосистемы  DSA (Digital Signature Algorithm) для электронной подписи. Простые числа p и q определяются вариантом задания. В качестве исходного текста взять слова своего полного имени: фамилия, имя, отчество.

     р = 324733,     q = 27061,     t = KAL 

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

1. Выбрать простое число q, 2¹⁵⁹  < q < 2¹⁶⁰ .
2. Выбрать число t, 0 ≤ t ≤ 8, и простое число р, 2^{511 + 64 t}  < p < 2^{512 + 64 t}  такое, что q делит p – 1.
3. Найти генератор α ^*_р для циклической подгруппы порядка q в группе ^*_р . Для этого адресат должен выполнить следующее.
1. Выбрать элемент g ^*_р и найти α = g^{(p – 1)/q} (mod p).
2. Если α = 1, то перейти к шагу 3.1 с другим g.
4. Выбрать произвольное число а, 1 ≤ а ≤ q – 1.
5. Вычислить y = α ^a (mod p).
6. Открытый ключ адресата есть (p, q, α, y); секретный ключ адресата есть число а.

 

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