Мемуары о будущем

Дмитрий Беляев

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

Опубликовано: 22 января 2011 года






В продолжение курса лекций по криптологии поговорим сегодня об известнейшем асимметричном алгоритме шифрования 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, Д.А. Беляев, Ю.В. Гольчевский

См. также:

0


1 звезда2 звезды3 звезды4 звезды5 звезд (1 голосов, средний: 5.00 из 5)
Loading ... Loading ...
Google Bookmarks Digg Reddit del.icio.us Ma.gnolia Technorati Slashdot Yahoo My Web News2.ru БобрДобр.ru RUmarkz Ваау! Memori.ru rucity.com МоёМесто.ru Mister Wong





Записи с теми же метками:

Комментарии:


  1. Комментатор: AL4EMIST

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


  2. Комментатор: Дмитрий Беляев

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

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

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


  3. Комментатор: Алексей

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


  4. Комментатор: Дмитрий Беляев

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

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

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

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

Оставить комментарий

:wink: :-| :-x :twisted: :) 8-O :( :roll: :-P :oops: :-o :mrgreen: :lol: :idea: :-D :evil: :cry: 8) :arrow: :-? :?: :!:

ВНИМАНИЕ! Все комментарии, содержащие явные оскорбления (в адрес автора статьи или собеседника-комментатора), спам и очевидную рекламу сторонних ресурсов, будут удалены. Также не рекомендуется злоупотреблять матом (такие сообщения будут отмодерированы или удалены).


Другие материалы: