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

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

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

Если пользователь A хочет отправить зашифрованное послание пользователю B, он шифрует его с помощью открытого ключа B. Теперь текст не сможет прочесть никто, кроме B (даже сам A), поскольку для дешифрования нужен закрытый ключ.

Схему шифрования можно записать в следующем виде:

M' = E(M, Kоткр)

M = D(M', Kзакр),

где Е — функция шифрования (encrypt), D — функция дешифрования (decrypt), а Kоткр и Kзакр — соответственно открытый и закрытый ключи получателя сообщения.

Принципиальный метод шифрования с открытым ключом впервые был публично предложен в 1976 году Диффи и Хеллманом. При этом они не смогли придумать конкретного алгоритма, но сформулировали принципиальные условия, которым такие алгоритмы должны удовлетворять:

1.   Процесс генерации пары ключей (открытый и закрытый) не должен представлять вычислительных трудностей.

2.   Процесс зашифрования текста, т.е. вычисления E(M, Kоткр), а также процесс де-шифрования, т.е. вычисления D(M', Kзакр) также не должны представлять вычислительных трудностей.

3.   Для противника должно быть невозможно (с точки зрения вычислительных возможностей) вычисление закрытого ключа Kзакр по имеющемуся открытому ключу Kоткр.

4.   Для противника должно быть невозможно (с точки зрения вычислительных воз-можностей) вычисление открытого текста M по имеющемуся зашифрованному тексту M' и открытому ключу Kоткр.

Кроме этого желательно, чтобы операции шифрования и дешифрования выполня-лись в любом поряке, т.е. можно было бы зашифровать текст закрытым ключом, а рас-шифровать открытым. Преимущества этой возможности будут рассмотрены позже.

 

Алгоритм RSA

RSA — один из первых алгоритмов шифрования с открытым ключом — разработан в 1977 году, название составлено из первых букв имен его авторов (Райвест, Шамир и Ад-леман). На протяжении двадцати лет он был самым опулярным и практически единствен-ным широко использующимся алгоритмом с открытым ключом.

Рассмотрим этот алгоритм подробно.

 По теореме Эйлера Mϕ(n)

Для генерации ключей выбираются два больших случайных простых числа p и q и вычисляется их произведение n = pq. Затем вычисляется функция Эйлера: ϕ(n) = (p-1)(q-1)

Далее выбирается целое число e, такое что 1 < e < ϕ(n) и e взаимно просто с ϕ(n). Находится число d такое, что ed ≡ 1 (mod ϕ(n)). Это может быть сделано, например, при помощи расширенного алгоритма Евклида.

Открытым ключом является пара чисел (n, e), а закрытым ключом — пара (n, d). Как видно, для того, чтобы по открытому ключу определить закрытый, необходимо вычислить ϕ(n), а для этого большое (на практике порядка 1024 битов) число n необходи-мо разложить на простые множители. Но эффективного алгоритма разложения числа на простые множители не существует.

RSA предназначен для шифрования двоичных текстов. Открытый текст разбивается на блоки и каждый блок рассматривается как двоичное число M. При этом должно соблю-даться ограничение M < n, исходя из этого условия выбираются длина блока и минималь-но возможные значения p и q.

Для того, чтобы зашифровать сообщение, вычисляется

M' = Me mod n

Для дешифрования необходимо вычислить

M= M'd mod n

Убедимся в корректности алгоритма.

M'd mod n = (Me mod n)d mod n = Med mod n

Т.к. ed ≡ 1 (mod ϕ(n)), то ed ≡ kϕ(n) + 1 для некоторого целого k. Отсюда:

Med mod n = Mkϕ(n) + 1 mod n

≡ 1 (mod n). Т.о.:

Mkϕ(n) + 1 mod n = M

Получили M'd mod n = M, что и требовалось доказать.

 

Очевидно, что открытый и закрытый ключ в алгоритме RSA взаимозаменяемы: то, что зашифровано одним из них, расшифровывается другим.

Недостатком алгоритмов с открытым ключом является низкая скорость выполняемых операций. Так, в алгоритме RSA шифрование и дешифрование заключается в возве-дении очень большого числа в очень большую степень, а это достаточно ресурсоемкая операция.

Поэтому на практике чаще всего используется комбинация двух алгоритмов. Сообщение шифруется с помощью симметричного алгоритма шифрования (например, AES). При этом каждый раз генерируется новый случайный ключ. Этот ключ зашифровывается открытым ключом получателя (например, с помощью RSA) и отправляется вместе с со-общением. Такая гибридная схема обеспечивает как скорость операций шифрова-ния/дешифрования, так и надежность.