Материал: Раздел 2.Криптографические системы с открытым ключом

Пусть имеется уравнение а^x = b, из которого требуется найти x. Прологарифмируем левую и правую части уравнения. Получим:

x log a = log b, откуда , т.е. для степенного уравнения решение находится просто.

Если же имеется сравнение а^x  b mod P, ( 1 )

в котором известны значения a, b, и P, то x находится в общем случае с помощью перебора. Задача решения сравнений вида ( 1 ) называется задачей дискретного логарифмирования. Несмотря на безусловные успехи последних лет в этой области, для произвольных модулей P решение близко к полному перебору. Если же P имеет порядка 100 десятичных разрядов, то и значения k₁ и k₂ имеют примерно тот же порядок и для решения сравнения требуется производить перебор около 10¹⁰⁰ вариантов, что является нереализуемым ни за какое приемлемое время.

2.4. Криптосистема rsa

Наиболее широко распространенной системой с открытым ключом является криптосистема RSA (Rivest, Shamir, Adleman). Идея системы состоит в том, что очень сложно разложить произведение двух простых чисел на сомножители, т.е. найти эти сомножители. Сама же идея системы RSA исключительно проста.

Пусть p и q – два случайно выбранных простых числа (каждое примерно по 100 десятичных разрядов). Обозначим:

n = pq и j(n) = (p-1)(q-1), где j (n) – функция Эйлера от n.

Случайно выбирается большое число d >1, такое, что (d, j(n)) = 1, и вычисляется e, 1 < e < j(n), удовлетворяющее сравнению:

ed º 1 mod j(n).

Числа n, e и d называются соответственно модулем, экспонентой зашифрования и экспонентой расшифрования соответственно.

Числа n и e образуют открытый ключ, а p,q, j(n) и d секретную лазейку. При этом секретная лазейка включает в себя взаимозависимые величины. Так, если известно p (и, конечно, n и e), то остальные числа лазейки вычисляются просто:

q = n/p; j(n) = (p-1)(q-1); d находится из условия: ed º 1 mod j(n).

Зашифрование обеспечивается возведением числового фрагмента текста S в степень e по модулю n.

Расшифрование достигается возведением результата предыдущего шага в степень d.

При зашифровании получаем S^e º C mod n. Здесь C – зашифрованный фрагмент текста.

При расшифровании C^d = S^ed = S^1+j(n)k = S^j(n)k S º S mod n. ( * )

Справедливость (*) легко видна, так как из сравнения ed º 1 mod j(n) следует, что ed = 1 + j(n)k, где k – некоторое целое.

Пример. Пусть p = 11, q = 13. Тогда n = 143, j(n) = 120.

Выберем d из условия: ( d, j(n)) = 1, например, d = 37, тогда из сравнения: ed º 1 mod j(n) находим e = 13. Действительно,

13*37 = 481 º mod 143.

Для зашифрования возьмем фрагмент текста, который закодирован, например, числом S = 42.

42¹³ º 3 mod 143, т.е. шифр фрагмента C = 3.

Для расшифрования возведем число 3 в степень 37:

3³⁷ º 42 mod 143. Таким образом, легальный получатель вычисляет значение исходного кода фрагмента/

2.5. Идея криптосистемы ЭльГамаля.

Идея ЭльГамаля [ 3 ] является аналогом идеи RSA и состоит в следующем. Алиса выбирает очень большое простое число P и число g – первообразный корень по модулю P. Вычисляет значение y  g^x mod P. Открытыми ключами являются P, g и y. Число x является секретным ключом Алисы. Если Боб решает послать секретное сообщение m Алисе, он придумывает некоторое целое число k, вычисляет a  g^k mod P и передает Алисе пару чисел b  m*y^k mod P и a  g^k mod P. Алиса возводит а в известную только ей степень x и решает сравнение:

(2)

В результате Алиса читает переданное ей сообщение m.

Пример. Пусть P = 113. Возьмем g = 3. Это число является первообразным корнем по модулю 113. Пусть Алиса выбрала x = 59. Вычислим y  3⁵⁹mod 113  86 mod 113. Открытыми ключами являются P = 113, g = 3 и y = 86. Секретным ключом Алисы является число x = 59. Боб хочет послать секретное сообщение Алисе в виде числа m = 92. Боб придумывает число k = 37 , вычисляет a  3³⁷ mod 113  24 mod 113 и b  92* 86³⁷  7 mod 113 и посылает Алисе два числа a = 24 и b = 7. Алиса вычисляет: mod 113  mod 113  92 mod 113. Полученное сообщение полностью соответствует исходному.