- Мемуары о будущем - 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).

Следствия:

  1. Если n = pq, (p и q – отличные друг от друга простые числа) и е – пpостое число относительно Ф(n), то отображение Е(e,n): x -> (x в степени e) (mod n) является взаимно однозначным на алгебраическом кольце вычетов Z(n).
  2. Если е – пpостое число относительно Ф(n), то существует целое число d, такое, что e*d = 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 реализуется следующим образом:

  1. Каждый пользователь выбирает два больших простых числа p и q, и в соответствии с описанным выше алгоритмом вы-бирает два простых числа e и d; как результат умножения первых двух чисел устанавливается n. После этого {e, n} образует открытый ключ, а {d, n} – секретный (хотя можно взять и наоборот).
  2. Открытый ключ публикуется и доступен каждому, кто желает послать владельцу ключа сообщение, которое зашифровывается указанным алгоритмом. После шифрования, сообщение невозможно дешифровать с помощью открытого ключа. Владелец же секретного ключа без труда может pасшифpовать принятое сообщение.

(С) 2004, Д.А. Беляев [2], Ю.В. Гольчевский

См. также:


4 Comments (Открыть | Закрыть)

4 Comments на "Асимметричный алгоритм шифрования RSA: теоретические основы"

#1 Комментарий от AL4EMIST дата: 22 января 2011 @ 11:47

Интересно сколько бы понадобилось времени на расшифровку такого ключа на средненьком компьютере 2010 года? прогресс уже далеко убежал от 94 года)

#2 Комментарий от Дмитрий Беляев дата: 22 января 2011 @ 12:29

Интересно сколько бы понадобилось времени на расшифровку такого ключа на средненьком компьютере 2010 года? прогресс уже далеко убежал от 94 года)

Наверно, один день. Максимум :) .

Хотя, надо спрашивать практиков. Честно признаюсь (в очередной раз), что если брать криптологию, то я – исключительно математик-теоретик (причём теряющий квалификацию; за потоком других “нематематических” задач).

#3 Комментарий от Алексей дата: 22 января 2011 @ 12:41

Как жизненно в это время для 133 группы)
Задача вычисления обратных функций для односторонних функций является практически не разрешимой! (это определение практически определение односторонней функции) на этом основаны почти все криптосистемы с открытыми ключами.

#4 Комментарий от Дмитрий Беляев дата: 22 января 2011 @ 12:42

Как жизненно в это время для 133 группы)

Не думал об этом. Но рад, что частично “кстати” :wink:

Задача вычисления обратных функций для односторонних функций является практически не разрешимой! (это определение практически определение односторонней функции) на этом основаны почти все криптосистемы с открытыми ключами.

Именно так. Только “односторонние функции” обычно называются “однонаправленными”.


Статья распечатана с Мемуары о будущем: 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 - "Мемуары о будущем". Все права сохранены.