3. Алгоритмы шифрования с открытым ключом

Для демонстрации особенностей алгоритмов шифрования с открытым ключом выбраны два алгоритма: алгоритм шифрования RSAи схема шифрования Эль-Гамаля. Оба эти алгоритма, особенно первый, распространены очень широко. Цель демонстрации - показать учащемуся, что стойкость асимметричных алгоритмов основана на вычислительной сложности решения какой-либо задачи [3]. Стойкость алгоритмаRSAоснована на вычислительной сложности разложения числа на два больших простых множителя, а стойкость алгоритма Эль-Гамаля – на вычислительно сложной задаче дискретного логарифмирования. Последняя заключается в том, чтобы для заданных целых чиселgиMи простого числаpнайтиx, такой чтоg^xM(modp).

3.1. Алгоритм rsa

Описание алгоритма приведено в [3].

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

n=pq, гдеpиq– простые числа, которые должны оставаться в секрете

e– число взаимно простое с (p-1)(q-1)

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

d=e^-1mod((p-1)(q-1))

Алгоритм шифрования:

1. разделить открытый текст на блоки таким образом, чтобы каждый блок можно было представить в виде числа меньшего, чем n

2. получить блоки зашифрованного текста, c, из блоков открытого текстаm:c=m^emodn

Алгоритм дешифрования:

m=c^dmodn

3.2. Алгоритм Эль-Гамаля

Описание алгоритма приведено в [3].

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

p– простое число, которое может совместно использоваться несколькими лицами

g<p- число, которое может совместно использоваться несколькими лицами

y=g^xmodp

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

x<p

Алгоритм шифрования:

1. разделить открытый текст на блоки таким образом, чтобы каждый блок можно было представить в виде числа меньшего, чем p

2. для каждого блока открытого текста mвыбрать случайным образом числоk, взаимно простое сp-1

3. шифрованным текстом для блока mбудет пара чиселa=g^k modp,b=y^kMmodp

Алгоритм дешифрования:

m=(b/(a^x))modp

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

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

В качестве хеш-функции выбран алгоритм SHA, т.к. значение этой функции имеет длину 160 бит, что в настоящее время делает практически невозможной атаку путем простого подбора сообщений. Стандарт цифровой подписиDSSтребует использовать этот алгоритм [6].

4.1. Схема rsa

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

s=m^dmodn.

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

m’ =s^emodn.

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

4.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.