Первая страница / Теория / Кодирование /

Система шифрования RSA

Голосование: 6, 1

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

Криптосистемы с открытым ключом

Криптосистемы с открытым ключом (к которым относится RSA) позволяют обмениваться секретными сообщениями по открытому каналу, не договариваясь заранее о ключе шифра; даже перехватив весь разговор от начала до конца, враг (или, как говорят, противник) не узнает секретного сообщения.

При использовании таких систем каждый участник переговоров имеет открытый ключ (public key) и секретный ключ (secret key).

Далее для примера мы будем говорить о переговорах Алисы (А) и Боба (Б).

Криптосистема RSA

Чтобы построить пару ключей для RSA, надо сделать следующее:

  1. Взять два больших простых числа p и q.
  2. Вычислить n = pq.
  3. Взять небольшое нечетное число e, взаимно простое с φ(n) = (p−1)(q−1).
  4. Вычислить d = e−1 (mod φ(n)).
  5. Пара P = (en) — открытый RSA-ключ.
  6. Пара S = (dn) — секретный RSA-ключ.

Шифром сообщения m будет me (mod n).

Для дешифровки сообщения x надо вычислить xd (mod n).

Надежность RSA

Надежность криптосистемы RSA основывается на трудности задачи разложения составных чисел на множители: если враг разложит (открыто опубликованное) число n на множители p и q, он сможет найти d тем же способом, что и создатель ключа.

Криптосистема RSA на практике

На практике для ускорения вычислений криптосистему RSA часто используют вместе с какой-то традиционной системой шифрования, в которой ключ небходимо хранить в секрете. Выбрав такую систему, мы используем для шифрования ее — а система RSA используется только для передачи секретного ключа.

Протокол электронной подписи

Пусть Алиса хочет послать Бобу сообщение m, подписанное ее цифровой подписью. Тогда:

  1. Алиса вычисляет цифровую подпись (digital signature) md и посылает Бобу пару (mmd).
  2. Боб получает пару (ms) и убеждается в подлинности подписи, проверив равенство m ≡ se (mod n).

Таким образом, цифровая подпись выполняет функции обычной. Подлинность цифровой подписи может проверить каждый, знающий открытый ключ Алисы. Например, подписанным документом может быть банковское поручение о перечислении денег со счета Алисы на счет Боба — и банк будет уверен в его достоверности.

Электронные деньги

Простейшей реализацией электронных денег может быть следующая:

  1. Все электронные купюры имеют одинаковое достоинство.
  2. Электронная банкнота представляет из себя пару (mm′), где m — номер банкноты, а m′ — цифровая подпись банка на этот номер.

В такой казалось бы надежной системе есть критическая дыра. Какая?

Дело в том, что имея две банкноты (aad) и (bbd) враг может легко получить новую банкноту (ab, (ab)d).

Неотслеживаемость

Рассмотрим простейший вариант платежной системы, в которой используется затемненная подпись, соответствующая схеме подписи RSA. Итак, банк выбирает и публикует числа N и e, а также некоторую функцию f, назначение которой станет ясно из дальнейшего (вспомните предыдущий вопрос).

При снятии со счета клиент выбирает случайное число n и вычисляет f(n). Ему нужно получить подпись банка на этой банкноте, то есть значение f(n)d. Для этого клиент выбирает случайное число r и отправляет значение f(n) · re на подпись банку. Банк вычисляет значение f(n)d · r (mod N) и возвращает его клиенту. Клиент легко получает подписанную банкноту (nf(n)d (mod N)).

Как строить большие простые числа.

Конечно же, большие простые числа можно строить сравнительно быстро. В противном случае теряла бы всякий практический смысл система шифрования RSA. Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма.

Теорема

Пусть N, S — нечетные натуральные числа, N−1 = S·R, причем для каждого простого делителя q числа S существует целое число a такое, что

an−1 ≡ 1 (mod N),   (a(N−1) ⁄ q − 1, N) = 1   (1)

Тогда каждый простой делитель p числа N удовлетворяет сравнению

p ≡ 1 (mod 2S)

Доказательство см. [3] стр. 99.

Следствие. Если выполнены условия теоремы и R < 4S+2, то N — простое число.

Покажем теперь, как с помощью этого утверждения, имея большое простое число S, можно построить существенно большее простое число N.

  1. Выберем случайное четное число R на промежутке S < R < 4S+2 и положим N = SR+1.
  2. Проверим число N на отсутствие малых простых делителей, испытаем N некоторое количество раз с помощью теста Миллера-Рабина. Если при этом выяснится, что N — составное, то перейти к шагу 1.
  3. Итак, N скорее всего простое, и следует попытаться доказать его простоту с помощью нашей теоремы. Для этого можно случайным образом выбирать число a, 1 < a < N, и проверять для него выполнимость соотношений (1).
  4. Если при выбранном a эти соотношения выполняются, то N точно простое. Если нет — выбираем другое a и переходим к шагу 3.

Заметим, что построенное N будет удовлетворять неравенству N > S2, т. е. будет записываться вдвое большим количеством цифр, чем исходное число S.

На обычном компьютере без особых затрат времени строятся таким способом простые числа порядка 10300. Подробности см. в [3].

Литература

  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
  2. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд. — М.: Издательский дом «Вильямс», 2001.
  3. Введение в криптографию, 2-е изд., испр. / Под общ. ред. В.В.Ященко. — М.: МЦНМО-«ЧеРо», 1999.
  4. Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии — М.: МЦНМО, 2003.
  5. Журнал «Математическое просвещение», вып. 4-7. — М.: МЦНМО, 2000-2003.
  6. Виноградов И.М. Элементы высшей математики. — M.: Высшая школа, 1999.

Михаил Лукин, Роман Сатюков


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий