Уроки 125 - 135
Хэширование и пароли. Безопасность в Интернете
§78. Шифрование. §79. Хэширование и пароли. §80. Современные алгоритмы шифрования. §81. Стеганография. §82. Безопасность в Интернете

Содержание урока

§80. Современные алгоритмы шифрования

Блочный шифр

Алгоритм RSA

Цифровая подпись

Вопросы и задания

Задачи

§80. Современные алгоритмы шифрования

Алгоритм RSA

В Интернете популярен алгоритм RSA, названный так по начальным буквам фамилий его авторов — Р. Райвеста (R. Rivest), А. Шамира (A. Shamir) и Л. Адлемана (L. Adleman). Это алгоритм с открытым ключом, стойкость алгоритма основана на том, что перемножить два очень больших простых числа достаточно просто, а вот разложить такое произведение на простые сомножители очень трудно (эту задачу сейчас умеют решать только перебором вариантов). Поскольку количество вариантов огромно, для раскрытия шифра требуется много лет работы современных компьютеров.

Для применения алгоритма RSA требуется построить открытый и секретный ключи следующим образом.

1. Выбрать два больших простых числа, р и q.

2. Найти их произведение п = р • q и значение φ = (р - 1) • (q - 1).

3. Выбрать число е (1 < е< φ), которое не имеет общих делителей с φ.

4. Найти число d, которое удовлетворяет условию d • e = kφ + 1 для некоторого целого k.

5. Пара значений (е, n) — это открытый ключ RSA (его можно свободно публиковать), а пара (d, n) — это секретный ключ.

Передаваемое сообщение нужно сначала представить в виде последовательности чисел в интервале от 0 до n - 1. Для шифрования используют формулу

y = X^е mod n,

где х — исходное сообщение (число), (е,n) — открытый ключ, y — закодированное сообщение (число), а запись х^е mod n обозначает остаток от деления х^е на n. Расшифровка сообщения выполняется по формуле

х = y^d mod n.

Это значит, что зашифровать сообщение может каждый (открытый ключ общеизвестен), а прочитать его — только тот, кто знает секретный показатель степени d.

Для лучшего понимания мы покажем работу алгоритма RSA на простом примере. Возьмём р = 3 и q = 7, тогда находим n = p • q = 21 и φ = (р - 1) • (q - 1) = 12. Выберем е = 5, тогда равенство d • е = kφ + 1 выполняется, например, при d = 17 (и k = 7). Таким образом, мы получили открытый ключ (5, 21) и секретный ключ (17, 21).

Зашифруем сообщение, состоящее из чисел 1, 2 и 3, с помощью открытого ключа (5,21). Получаем:

1 => 1⁵ mod 21 = 1, 2 => 2⁵ mod 21 = 11, 3 => 3⁵ mod 21 = 12,

т. е. зашифрованное сообщение состоит из чисел 1, 11 и 12. Зная секретный ключ (17, 21), можно его расшифровать:

1=>1¹⁷ mod 21 = 1, 11 => 11¹⁷ mod 21 = 2, 12 => 12¹⁷ mod 21 = 3.

Мы получили исходное сообщение.

Конечно, вы заметили, что при шифровании и расшифровке приходится вычислять остаток от деления очень больших чисел (например, 12¹⁷) на n. Оказывается, само число 12¹⁷ в этом случае находить не нужно. Достаточно записать в обычную целочисленную переменную, например х, единицу, а потом 17 раз выполнить преобразование х = 12 • х mod 21. После этого в переменной х будет значение 12¹⁷ mod 21 = 3. Попробуйте доказать правильность этого алгоритма.

Чтобы взломать шифр, злоумышленнику надо узнать секретный показатель степени d. А для этого необходимо найти большие простые числа р и q, такие что n = p • q. Если n велико, это очень сложная задача, её решение перебором вариантов на современном компьютере займёт сотни лет. В 2009 г. группа учёных из разных стран в результате многомесячных расчётов на сотнях компьютеров смогла расшифровать сообщение, зашифрованное алгоритмом RSA с 768-битным ключом. Поэтому сейчас надёжными считаются ключи с длиной 1024 бита и более. Если будет построен работающий квантовый компьютер, взлом алгоритма RSA будет возможен за очень небольшое время.

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

Следующая страница Цифровая подпись

Cкачать материалы урока