В асимметричных методах применяются два разных ключа. Один из них, несекретный, используется для шифровки и может публиковаться вместе с адресом пользователя, другой - секретный, применяется для расшифровки и известен только получателю.
Алгоритм Шамира
Алгоритм может использоваться для передачи короких сообщений, например, ключей.
Пусть абонент А хочет передать сообщение m абоненту В в зашифрованном виде. А выбирает случайное большое число p и открыто передает его В. Затем А выбирает два числа Са и Da, такие что Са · Da mod (p-1) = 1. B точно также выбирает Сb и Db. Поле этого можно передать сообщение m, используя следующий трехступенчатый протокол.
Шаг 1. A вычисляет число x1 = mCa mod p, где m – исходное сообщение, и пересылает x1 к B.
Шаг 2. B, получив x1, вычисляет число x2 = x1Cb mod p и пересылает x2 к A.
Шаг 3. A вычисляет число x3 = x2Da mod p и пересылает его к B.
Шаг 4. B, получив x3,вычисляет число x4 = x3Db mod p.
Криптосистема RSA
Криптосистема RSA, была разработана в 1977 году и получила название в честь своих создателей: Рона Райвеста (Rivest), Ади Шамира (Shamir) и Леонарда Адлемана (Adleman).
|
|
Они воспользовались тем фактом, что нахождение больших простых чисел осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. В 1993 г. метод RSA был обнародован и принят в качестве стандарта (PKCS # 1: RSA Encryption Standard).
Генерация ключей
1. Выбираются два больших простых целых числа p и q приблизительно одинакового размера.
2. Вычисляется модуль системы n = pq и φ(n) = (p-1)(q-1) – функция Эйлера.
3. Выбирается достаточно большое число d, удовлетворяющее условию 1 < d < φ(n), и взаимно простое с φ(n), то есть НОД(d, (p-1)(q-1)) = 1.
4. Используя расширенный алгоритм Евклида, вычисляется большое целое число e, отвечающее условию (ed) mod φ(n) = 1, 1 < e < φ(n). Метод Евклида находит множество пар (e, y), каждая из которых является решением уравнения: e * d + (p - 1)(q - 1) * y = 1 в целых числах.
Таким образом, секретным ключом является пара чисел (n,d), а открытым – пара чисел (n,e), но можно взять и наоборот.
Зашифрование и расшифрование
1. Входное сообщение разбивается на блоки mi, их размер определяется целым k, соответствующим неравенству 10k-1 < n < 10k.
2. Вычисляется значение ci = mie mod n.
3. Значение ci, которое является зашифрованным блоком сообщения, посылается по открытым каналам передачи данных.
4. Расшифрование заключается в вычислении значения mi = cid mod n.
Математические основы RSA
Рассмотрим математические результаты, положенные в основу этого алгоритма.