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

1. Вычисляет значение хэш – функции h(t).
2. Выбрать произвольное секретное число k, 0 < k < q.
3. Вычислить k ^{– 1} (mod q).
4. Вычислить r = (α^k (mod p)) (mod q).
5. Вычислить s = k ^{– 1} (h(t) + ar) (mod q).
6. Подпись адресата А есть пара чисел (r, s).

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

1. Вычислить значение хэш – функции h(t).
2. Взять открытый ключ (p, q, α, y) адресата А.
3. Проверить, что 0 < r < q  и 0 < s < q. Если нет, то отвергнуть подпись.
4. Вычислить w = s ^{– 1} (mod q)  и h(m).
5. Вычислить u₁ = w · h(m) (mod q)  и  u₂ = r w (mod q).
6. Вычислить v = (α ^u₁  y ^u₂ (mod p)) (mod q).
7. Принять подпись, если v = r и отвергнуть в противном случае.

Решение:

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

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

1.  Выбрать  простое число q = 27061.

2. Выбрать простое число р = 324733, для которого q делит (p – 1). Пусть (p – 1)/ q = 12.
3. Выбрает случайное число g=2012 ^*_р и вычисляет α = g^{(p – 1)/q} (mod p) = 2012¹² (mod 324733) = 84103. Так как α ≠ 1, то α есть генератор для единственной циклической подгруппы порядка q в группе ^*_р . (Если α = 1, то следует выбрать другое g).
4. Выбрать случайное число а = 115 [1, q – 1].
5. Вычислить y = α ^a (mod p) = 84103¹¹⁵ (mod 324733) = 97053.
6. Открытый ключ адресата есть (p = 324733, q = 270619, α = 84103,

y = 97053); секретный ключ адресата А есть число а = 115.

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

1. Вычисляет значение хэш – функции h(t). Пусть для примера h(t) =8058.
2. Выбирает случайное секретное число k = 57 [0, q].
3. Вычисляет k ^{– 1} (mod q) = 25162.
4. Вычисляет r = (α^k (mod p)) (mod q) = (84103⁵⁷ (mod 324733))

(mod 27061)=16682.

5. Вычисляет s = k ^{– 1} ∙ (h(t) + ar) (mod q) = 16682 ∙ (8058 + 115 ∙ 25061)

(mod 12) = 2939.

6. Подпись адресата А под его текстом t есть пара чисел (r = 16682,

s = 2939).

1. Проверка подписи. Чтобы проверить подпись (r = 16682, s = 2939)

адресата А под его текстом t, адресат В должен выполнить следующее.

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

h(t) = 8058.

2. Берет открытый ключ адресата А: (p = 324733, q = 270619, α = 84103,   y = 97053).
3. Проверяет, что r = 16682 [0, q] = [0, 27061] и s = 2939 [0, q] =

= [0, 27061]. Если проверка не проходит, то  подпись отвергнут.

4. Вычисляет w = s ^{– 1} (mod q) = 26573.
5. Вычисляет u₁ = w · h(t) (mod q) = 26573 ∙ 8058(mod 27061) = 18602,  

                         u₂ = r w (mod q) = 16682 ∙ 26573 (mod 27061) = 4545.

6. Вычисляет v = (α ^u₁  y ^u₂ (mod p)) (mod q) = (459706¹⁸⁶⁰² ∙ 169635⁴⁵⁴⁵

(mod 324733))(mod 27061) = 16682.

7. Так как v = 16682 = r , то В принимает подпись А.

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

 

5. MATHCAD ПРОГРАММНЫЙ ПРОЦЕССОР

PACKET OF MATHCAD PROGRAMS FOR CRYPTOGRAPHY WITH PUBLIC KEY 

Polynoms are given by the vector of coefficients with the decreasing order of exponents: P(x) =   =

Factoring n

 

Representation of 10-based natural numbers as h-based ones

 Modular exponentiation m^e mod n

 

Extended Euclidean algorithm to find d=gcd(a,b)

and u, v  for integers such that d=au+bv

 

The quotient and the remaider at division of product polynomials P(x),Q(x)

in Zp[x] modulo irreducible polynomial F(x) in Zp[x]

 
 
 
 
 
 
 
 

6. ПРИМЕРЫ ИСПОЛЬЗУЕМЫХ MATHCAD-ПРОГРАММ
1. Криптосистема RSA

 

CRYPTOSYSTEM RSA

Key generation

Public key for B is the pair of numbers (n, e)

Private key for B is the number a,

where

Encryption

The text t=KAL

Decryption

The text t = KAL

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

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

7. DIGITAL SIGNATURE RSA with recovering the message

8. Key generation

20. Public key for B is the pair of numbers (n, e)
21. Private key for B is the number a

22. where

26. Signature generation

27. The text t=KAL

33. Signature verification

34. Signature is accepted

40. The text t = KAL

 
 
 
 
 
 
 
 
 
 
 
 

 

3. Электронная цифровая подпись RSA с hash-функцией

DIGITAL SIGNATURE RSA with hash-function h(t)

Key generation

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Public key for A is the pair of numbers (n, e)

Private key for A is the number a,

where

Signature generation

The text t=KAL

Hash function

Signature is the number

_S=8058

Signature verification

t = KAL

If text t is changed, then m1 is other number. For instance,

 

4. Шифросистема Эль-Гамаля с простым полем Галуа

ELGAMAL CRYPTOSYSTEM IN SIMPLE GALOIS FIELD 

Key generation

Public key for B is three numbers (p,,y),

Private key for B is the number a,

where

Encryption

The text t=KAL