3. Алгоритмы цифровой подписи

   1. RSA

Описание алгоритма взято из [2].

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

s=m^dmodn.

Процедура проверки подписи s, соответствующей сообщениюm:

m’ =s^emodn.

Если m’=m, то сообщениеmпризнается подписанным пользователем, который предоставил ранее открытый ключe.

2. DSA

Описание алгоритма взято из [6].

Открытый ключ:

p– простое число, которое может быть общим для группы пользователей

q– простое число, которое делитp-1 и может быть общим для группы пользователей

g=h^(p-1)/qmodp, гдеh<p-1 иh^(p-1)/qmodp>1.gможет быть общим для группы пользователей

y=g^xmodp

Закрытый ключ:

x<q

Алгоритм генерации подписи:

1. выбрать случайным образом число k:k<q

2. подписью сообщения Mбудет пара чисел:

r= (g^k mod p) mod q

s= (k^-1(H(m)+xr))modq

где H(m) – результат применения хеш-функции к сообщениюm

Алгоритм проверки подписи:

1. w=s^-1 mod q

2. u₁=(H(m)*w) mod q

3. u₂=(rw) mod q

4. v=((g^u1*y^u2) mod p) mod q

5. если v=r, то сообщениеmпризнается подписанным пользователем, который предоставил ранее открытый ключy

В стандарте цифровой подписи DSS[6] определено, что длина числаpдолжна составлять от 512 бит до 1024 бит, длина числаq– 160 бит. Эти требования связаны с тем, что при таких длинах достигается достаточная вычислительная стойкость. Но алгоритм цифровой подписи будет работать, даже если используются числаpиqдругой длины.

Стандарт DSSопределяет, что в качестве хеш-функции надо использоватьSHA.

3. Схема подписи Эль-Гамаля

Описание алгоритма взято из [2]. Открытые и секретные ключи те же, что и в схеме шифрования Эль-Гамаля. Перед формирование подписи надо представить сообщение в виде числа, меньшего чем p. Если сообщение слишком большое, то надо либо разбить его на части, либо, что гораздо эффективнее, подписывать дайджест сообщения.

Алгоритм формирования подписи числа m:

Выбрать k– случайное число, взаимно простое сp-1.

Вычислить числа aиb, которые и будут подписью:

a = g^k mod p

b – такое что m=(xa + kb) mod (p-1).

Проверка подписи:

Если y^aa^bmodp=g^mmodp, то признается что сообщениеmподписано пользователем, который предоставил открытый ключy.

4. Алгоритм гост

Это российский стандарт цифровой подписи ГОСТ 34.10-94 [5].

Открытый ключ:

p– простое число

q– простое число, которое делитp-1

a– число меньшее, чемp-1, такое чтоa^qmodp=1

y=a^xmodp

Секретный ключ:

x– число, меньшее чемq

Алгоритм генерации подписи:

1. выбрать случайным образом число k:k<q

2. подписью сообщения mбудет пара чисел:

r=(a^k mod p) mod q

s=(xr+k*H(m))modq

Алгоритм проверки подписи:

1. v=H(m)^q-2 mod q

2. z₁=(sv) mod q

3. z₂=((q-r)*v) mod q

4. u=((a^z1*y^z2)mod p) mod q

5. если u=r, то признается что сообщениеmподписано пользователем, который предоставил открытый ключy.

В стандарте определено, что длина числа pдолжна составлять от 509 до 512 бит или от 1020 до 1024 бит, длина числаq– от 254 до 256 бит. Эти требования связаны с тем, что при таких длинах достигается достаточная вычислительная стойкость. Но алгоритм цифровой подписи будет работать, даже если используются числаpиqдругой длины.

5. Хеш-функцияSHA

Для использования в криптографических приложениях любая хеш-функция h=H(M) должна удовлетворять следующим требованиям [3]:

1. Для заданного сообщения Mлегко вычислитьH(M).

2. Для заданного hвычислительно трудно найтиM, такое чтоH(M)=h.

3. Для заданного Mвычислительно трудно найти другое сообщениеM₁, такое чтоH(M)=H(M₁).

4. Вычислительно трудно найти два случайных сообщения MиM₁, таких чтоH(M)=H(M₁).

В SHA-1 [7] используются функцииf(t,B,C,D), где 0t79;B,CиD– 32-битовые слова.

f(t,B,C,D) = (BC)((B)D) при 0t19

f(t,B,C,D) =BCDпри 20t39

f(t,B,C,D) = (BC)(BD)(CD) при 40t59

f(t,B,C,D) =BCDпри 60t79

При этом используются логические побитовые операции.

Используется также набор констант:

K_t= 5A827999 при 0t19

K_t= 6ED9EBA1 при 20t39

K_t= 8F1BBCDCпри 40t59

K_t=CA62C1D6 при 40t79

Алгоритм вычисления хеш-функции SHA-1

Вход: сообщение длиной <2⁶⁴бит.

1. Дополнить сообщение: добавить в конец сообщения 1, затем 0 или более нулей, а затем 64-битовое представление длины сообщения до дополнения. Количество добавленных нулевых битов должно быть таким, чтобы длина дополненного сообщения в битах была кратна 512. Дополненное сообщение состоит из блоков M₁,M₂, … ,M_n, длиной по 512 бит.

2. Инициализировать переменные

H0 := 67452301, H1 := EFCDAB89, H2 := 98BADCFE,

H3 := 10325476, H4:= C3D2E1F0

3. i := 1

4. Разделить блок M_iна 16 32-битовых словw₀,w₁, …,w₁₅.

5. Для всех t: 16t79w_t:= (w_t-3w_t-8w_t-14w_t-16)1, где «n» - циклический сдвиг влево наnбит.

6. A := H0, B := H1, C := H2, D := H3, E := H4.

7. Для всех tот 0 до 79

TEMP := (A  5 + f(t, B, C, D) + E + w_t + K_t) mod 2³²;

E := D; D := C; C := B  30; B := A; A := TEMP.

8. H0 := H0 + A, H1 := H1+B, H2 := H2 + C, H3 := H3 + D, H4 := H4 + E,

где все сложения производятся по модулю 2³².

9. Если i<n, тоi:=i+1 и перейти к шагу 4.

Выход: дайджест длиной 160 бит – конкатенация 32-битовых слов H0 |H1 |H2 |H3 |H4.