- Мемуары о будущем - http://bda-expert.com -
Асимметричный алгоритм шифрования RSA: теоретические основы
Автор Дмитрий Беляев дата: 22 января 2011 @ 11:15 в Информационная безопасность, Лекции, Творчество | 4 Comments
В продолжение курса лекций по криптологии [1] поговорим сегодня об известнейшем асимметричном алгоритме шифрования RSA.
Краткая история появления
Несмотря на достаточно большое число различных систем с открытыми ключами, одной из наиболее популярных остается криптосистема RSA, созданная в 1977 г. и названная в честь ее создателей Рона Ривеста, Ади Шамиpа и Леонарда Эйдельмана. Они воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, а разложение на множители произведения двух таких чисел – сложно.
В статье этих авторов, вышедшей в 1978 г., премия в сто долларов была назначена тому, кто первым расшифрует сообщение
686137546220614771409222543558829057599911257431987
469512093081629822514570835693147662883989628013391
99055182994515781515.
Метод шифрования был известен, единственное, что требовалось – разложить на два сомножителя 129-значное число, приведенное в этой статье.
Это было сделано только в 1994 г.
Задача была решена с помощью 600 человек и потребовала 220 дней и 1600 компьютеров, связанных через Internet.
Теоретические основы алгоритма RSA
Рассмотрим математические результаты, которые положены в основу этого алгоритма.
Определение 1. Сравнением целых чисел a и b будем называть соотношение между ними вида a = b + mk, означающее, что их разность (a – b) делится на заданное положительное число m, называемое модулем сравнения. При этом а называется вычетом числа b по модулю m.
Определение 2. Говорят, что два целых числа a и b сравнимы между собой и обозначают этот факт через a = b (mod m), если a и b имеют одинаковые остатки при делении на m.
Приведем некоторые очевидные свойства сравнений.
Пусть a = b (mod m) и с = d (mod m). Тогда:
1) a (+-) c = b (+-) d (mod m),
2) a*c (+-) b*d (mod m).
Легко также проверить, что операция сравнения по модулю m является эквивалентностью (выполняются свойства рефлексивности, транзитивности и симметричности), и, следовательно, можно говорить о разбиении множества целых чисел Z на непересекающиеся классы эквивалентности.
Теорема 1. (Малая теорема Ферма). Если p – простое число, то (x в степени (p – 1)) = 1 (mod p) для любого х, простого относи-тельно p, и (x в степени p) = х (mod p) для любого х.
Определение 3. Функцией Эйлеpа Ф(n) называется число положительных целых, меньших n и простых относительно числа n.
Теорема 2. Если n = pq, (p и q – отличные друг от друга простые числа), то Ф(n) = (p – 1)(q – 1).
Теорема 3. Если n = pq, (p и q – отличные друг от друга простые числа) и х – простое относительно p и q, то (x в степени Ф(n)) = 1 (mod n).
Следствия:
Пусть n = pq, где p и q – различные простые числа. Если e и d удовлетворяют уравнению (см. следствие 2), то отображения Е(e,n) и Е(d,n) являются инверсиями на кольце Zn.
Как Е(e,n), так и Е(d,n) легко рассчитываются, когда известны e, d, p, q.
Если известны e и n, но p и q неизвестны, то Е(e,n) представляет собой однонаправленную функцию; нахождение Е(d,n) по заданному n равносильно разложению n на простые сомножители.
Если p и q – достаточно большие простые числа, то разложение n – достаточно сложная вычислительная операция.
Это и заложено в основу системы шифрования RSA.
Пользователь i выбирает пару различных простых p(i) и q(i) и рассчитывает пару целых (e(i), d(i)), которые являются простыми относительно Ф(n(i)), где n(i) = p(i)*q(i). Справочная таблица содержит публичные ключи {(e(i), n(i))}.
Итак, в реальных системах RSA реализуется следующим образом:
(С) 2004, Д.А. Беляев [2], Ю.В. Гольчевский
См. также:
Статья распечатана с Мемуары о будущем: http://bda-expert.com
URL статьи: http://bda-expert.com/2011/01/asimmetrichnyj-algoritm-shifrovaniya-rsa/
URL-ы в этой записи:
[1] криптологии: http://bda-expert.com/tag/kriptologiya/
[2] Д.А. Беляев: http://bda-online.ru
[3] Асимметричный алгоритм шифрования RSA: http://bda-expert.ru/forum/24-83-1
Нажмите здесь для печати.
Копирайт © 2010-2022 Дмитрий Беляев, bda-expert.com - "Мемуары о будущем". Все права сохранены.
4 Comments на "Асимметричный алгоритм шифрования RSA: теоретические основы"
#1 Комментарий от AL4EMIST дата: 22 января 2011 @ 11:47
Интересно сколько бы понадобилось времени на расшифровку такого ключа на средненьком компьютере 2010 года? прогресс уже далеко убежал от 94 года)
#2 Комментарий от Дмитрий Беляев дата: 22 января 2011 @ 12:29
Наверно, один день. Максимум .
Хотя, надо спрашивать практиков. Честно признаюсь (в очередной раз), что если брать криптологию, то я – исключительно математик-теоретик (причём теряющий квалификацию; за потоком других “нематематических” задач).
#3 Комментарий от Алексей дата: 22 января 2011 @ 12:41
Как жизненно в это время для 133 группы)
Задача вычисления обратных функций для односторонних функций является практически не разрешимой! (это определение практически определение односторонней функции) на этом основаны почти все криптосистемы с открытыми ключами.
#4 Комментарий от Дмитрий Беляев дата: 22 января 2011 @ 12:42
Не думал об этом. Но рад, что частично “кстати”
Именно так. Только “односторонние функции” обычно называются “однонаправленными”.