|
Мы приводим фрагмент, посвященный криптосистеме RSA, из книги Т. Кормена,
Ч. Лейзерсона и Р. Ривеста "Алгоритмы. Построение и анализ", изданной в
русском переводе
МЦНМО (Москва, 1999-2001 г.).
Криптосистемы с открытым ключом позволяют обмениваться секретными
сообщениями по открытому каналу, не договариваясь заранее о ключе шифра;
даже перехватив весь разговор от начала до конца, враг (или, как говорят,
"противник") не узнает секретного сообщения. Кроме того, эти же методы
позволяют добавлять к сообщению "цифровую подпись", удостоверяющую, что
сообщение не фальсифицировано врагами. Проверить аутентичность подписи
легко, а подделать её крайне трудно. Понятно, что такие методы находят
широкое применение в банках, при подписывании контрактов, при денежных
переводах и т. п.
Криптосистема RSA основана на таком обстоятельстве: в настоящее время
известны эффективные алгоритмы поиска больших простых чисел, но не известно
сколько-нибудь приемлемого по времени работы алгоритма разложения
произведения двух больших простых чисел на множители. Мы рассмотрим эти
задачи (проверка простоты и разложение на множители) в разделах 33.8 и 33.9.
При использовании таких систем каждый участник переговоров имеет
открытый ключ (public key) и секретный ключ (secret key).
В системе RSA ключ состоит из двух целых чисел. Участников переговоров
может быть несколько. но для примера мы будем говорить о переговорах
Алисы (A) и Боба (B). Их открытые ключи мы будем обозначать
PA и PB,
а секретные - SA и SB.
Каждый участник сам создаёт два своих ключа. Секретный ключ он хранит
в тайне, а открытый сообщает остальным участникам (и вообще всем желающим,
например, через газеты или Internet; открытые ключи можно публиковать в
специальных справочниках и т. п.).
Обозначим через D множество всех возможных сообщений (например, это
может быть множество всех битовых строк). Потребуем, чтобы каждый ключ
задавал перестановку множества D, и через PA() и
SA() будем обозначать перестановки, соответствующие ключам
Алисы. Мы считаем, что каждая из перестановок PA() и
SA() может быть быстро вычислена, если только известен
соответствующий ключ.
Мы хотим, чтобы ключи одного участника задавали взаимно обратные
перестановки, т. е. чтобы
M=SA(PA(M)) (33.37)
и
M=PA(SA(M)) (33.38)
было выполнено для любого сообщения M C D
Самое главное - чтобы никто, кроме Алисы, не мог вычислять
функцию SA() за разумное время; именно на этом основаны все
полезные свойства криптосистемы, перечисленные выше. Потому-то
Алиса и держит значение SA в секрете: если кто-либо
узнает её секретный ключ, он сможет расшифровывать адресованные ей
сообщения, подделывать её подпись или подменять сообщения,
которые она отправляет от своего имени. Главная трудность при
разработке криптосистем состоит в том, чтобы придумать функцию
SA(), для которой трудно было бы найти быстрый способ
вычисления, даже зная такой способ для обратной функции
PA().
Опишем процесс пересылки шифрованного сообщения. Допустим, Боб
желает послать Алисе секретное сообщение. Это происходит так:
Боб узнаёт PA - открытый ключ Алисы (по справочнику или
прямо от Алисы);
Боб зашифровывает своё сообщение M и посылает Алисе
результат шифрования (ciphertext)
C = PA(M);
Алиса получает C и восстанавливает исходное сообщение
M=SA(C)
Этот процесс показан на рис. 33.5.
Рис. 33.5. Шифрование с открытым ключом. Боб шифрует сообщение
M с помощью функции PA и получает рузультат шифрования
C = PA(M). Функции SA() и
PA() взаимно обратны, поэтому Алиса может восстановить
исходное сообщение: M = SA(C). Никто, кроме
Алисы, не знает способа вычисления SA(), поэтому сообщение
M останется секретным, даже если враг подслушает C и знает
PA.
Теперь объясним, как снабдить сообщение цифровой подписью.
Пусть Алиса хочет послать Бобу ответ M', подписанный
цифровой подписью (рис.33.6). Тогда
Алиса вычисляет цифровую подпись (digital signature)
s = SA(M');
Алиса посылает Бобу пару (M', s),
состоящую из сообщения и подписи;
Боб получает пару (M', s) и убеждается
в подлинности подписи, проверив равенство
M'=PA(s);
Рис. 33.6. Цифровая подпись в системе с открытым ключом. Алиса
подписывает своё сообщение M', прикладывая к нему цифровую подпись
s = SA(M').
Боб, получая от Алисы пару (M', s),
проверяет соотношение
M' = PA(s).
Если оно выполняется, подпись и само сообщение подлинны.
Если участников переговоров много, будем считать, что каждое
сообщение M' должно начинаться с имени отправителя - прочтя
его, можно узнать, чей ключ надо использовать для проверки. Если равенство
выполняется, то можно быть уверенным в том, что сообщение действительно
было послано отправителем и дошло в неизменённом виде. Если же равенство не
выполнено, сообщение было повреждено помехами или фальсифицировано.
Таким образом, цифровая подпись выполняет функции обычной. Подлинность
цифровой подписи может проверить каждый, знающий открытый ключ Алисы.
Прочитав сообщение Алисы, Боб может переслать его другим участникам
переговоров, которые также смогут убедиться в его подлинности. Например,
подписанным документом может быть банковское поручение о перечислении денег
со счёта Алисы на счёт Боба - и банк будет знать, что оно настоящее, а
не фальсифицировано Бобом.
При таком сценарии содержание подписанного сообщения не является секретным.
Можно добиться и этого, скомбинировав два описанных приёма. Отправитель,
желающий зашифровать и подписать своё сообщение, должен сначала приложить к
своему сообщению цифровую подпись, а затем зашифровать пару (сообщение,
подпись) при помощи открытого ключа получателя. Получатель сначала расшифрует
эту пару с помощью своего секретного ключа, а затем проверит её подлинность
с помощью открытого ключа отправителя. Аналогичная процедура с бумажным
документом могла бы выглядеть так: письмо пишется от руки, подписывается и
вкладывается в конверт, который может открыть только получатель.
Чтобы построить пару ключей для криптосистемы RSA (RSA cryptosystem),
надо сделать следующее.
Взять два больших простых числа p и q (скажем, около
100 десятичных цифр в каждом).
Вычислить n = pq.
Взять небольшое нечётное число e, взаимно простое с
j(n). (Из соотношения (33.20) следует,
что j(n)=(p-1)(q-1)
Вычислить
d=e-1 mod j(n)
(По следствию 33.26 d существует и определено однозначно
по модулю j(n). )
Составить пару P = (e, n) - открытый RSA-ключ
(RSA public key).
Составить пару S = (d, n) -
секретный RSA-ключ (RSA secret key).
Множеством D всех возможных сообщений для этой криптосистемы
является Zn
Открытому ключу
P = (e, n) соответствует преобразование
P(M)=Me mod n (33.39)
а секретному ключу S = (d, n) - преобразование
S(C)=Cd mod n (33.40)
Как уже говорилось, эти преобразования можно использовать и для
шифрования, и для электронных подписей.
Для возведения в степень в формулах (33.39)-(33.40) разумно
пользоваться процедурой MODULAR-EXPONENTATION из раздела 33.6.
Если считать, что числа d и n имеют порядка
b битов, а число e имеет O(1)
битов, то преобразование P потребует O(1) умножений по модулю
n ( O(b2) битовых
операций), а преобразование S потребует
O(b) умножений
( O(b3) битовых операций)
(разумеется, при известном ключе).
Теорема 1 (корректность системы RSA)
Формулы (33.39) и (33.40) задают взаимно обратные перестановки множества
Zn
Доказательство.
Очевидно,
P(S(M)) = S(P(M)) = Med mod n
для всякого M C Zn
Мы знаем, что e и d взаимно обратны по
модулю j(n), т. е.
ed = 1 + k(p - 1)(q - 1)
для некоторого целого k. Если M =/= 0 (mod p), то по
малой теореме Ферма (теорема 33.31) имеем
Med=M(Mp-1)k(q-1)=M*1k(q-1)=M
по модулю p. Равенство
Med=M (mod p)
выполнено, конечно, и при M = 0 (mod p), так что оно
верно для всех M. По тем же причинам
Med=M (mod q),
и потому (следствие 33.29)
Med = M (mod n) при всяком M.
Надёжность криптосистемы RSA основывается на трудности задачи разложения
сставных чисел на множители: если враг разложит (открыто опубликованное)
число n на множители p и q, он сможет найти d
тем же способом, что и создатель ключа. Таким образом, если задача разложения
на множители может быть решена быстро (каким-то пока неизвестным нам
алгоритмом), то "взломать" криптосистему RSA легко. Обратное утверждение,
показывающее, что если задача разложения на множители сложна, то взломать
систему RSA трудно, не доказано - однако за время существования этой системы
никакого иного способа её взломать обнаружено не было.
Как мы увидим в разделе 33.9, разложение чисел на множители - дело
непростое, быстрого алгоритма для этого мы не знаем; известные ныне методы
не позволяют разложить на множители произведение двух 100-значных простых
чисел за разумное время - для этого нужны какие-то новые идеи и методы
(если это вообще возможно).
Конечно, надёжность системы RSA зависит от размера простых чисел, поскольку
небольшие числа легко разложить на множители. Поэтому надо уметь искать
большие простые числа. Этой задачей мы займёмся в разделе 33.8.
На практике для ускорения вычислений криптосистему RSA часто используют
вместе с какой-то традиционной системой шифрования, в которой ключ необходимо
хранить в секрете. Выбрав такую систему, мы используем для шифрования её -
а система RSA используется только для передачи секретного ключа, который
может быть значительно короче самого сообщения. Сам этот ключ может
выбираться, например, случайно и только на один раз.
Похожий подход применяется для ускорения работы с цифровыми подписями.
Система RSA используется при этом в паре с так называемой односторонней
хеш-функцией (one-way hash function). Такая функция отображает каждое
сообщение M в достаточно короткое сообщение h(M)
(например, 128-битовую строку), при этом h(M) легко вычислить
по M, но не удаётся найти два разных сообщения M и M',
для которых h(M) = h(M') (хотя таких пар много
по принципу Дирихле).
Образ h(M) сообщения M можно сравнить с "отпечатком
пальца" (fingerprint) сообщения M. Алиса, желая подписать своё
сообщение M, вычисляет h(M), а затем шифрует
h(M) своим секретным RSA-ключом. Затем она посылает Бобу пару
(M, SA(h(M))). Боб удостоверяется
в подлинности подписи, проверив, что
PA(SA(h(M))) = h(M).
Конечно, можно фальсифицировать текст сообщения, найдя другое сообщение
M', для которого h(M) = h(M'), но это
(по нашему предположению) сложно.
Конечно, при использовании открытых ключей надо ещё убедиться, что сами
ключи не были подменены. Предположим, что имеется некоторый "нотариус"
(trusted authority), честность которого вне подозрений и открытый ключ
которого все знают (и в его правильности не сомневаются).
[В книге "Введение в криптографию" (под ред. В. В. Ященко, М.: МЦМНО, 1998)
используется термин "центр доверия".] Нотариус может выдавать известным ему
людям справки (сертификаты, certificates) о том, что их открытый ключ
такой-то, подписывая эти справки собственной цифровой подписью.
(Приходящие должны сообщить нотариусу свой открытый ключ.) Подлинность
сертификата может быть проверена каждым, кому известен открытый ключ
нотариуса; любой зарегистрированный у нотариуса участник переговоров может
прилагать к своим сообщениям выданный нотариусом сертификат.
33.7-1 Вычислите открытый и секретный RSA-ключи при p = 11,
q = 29, n = 319 и e = 3. Чему равно d в
секретном ключе? Зашифруйте сообщение M = 100.
33.7-2 Пусть значение e для открытого ключа равно 3. Докажите,
что враг, узнавший значение d, сможет разложить n на множители
за время, полиномиальное относительно длины двоичной записи n.
(Аналогичное утверждение верно и для произвольного e,
см. работу Миллера [147].)
33.7-3* Докажите, что система RSA мультипликативна,
то есть
PA(M1)PA(M2)
=
PA(M1M2) (mod n)
для любых M1, M2 C
Zn. Предположим, что враг имеет способ быстро расшифровывать
1% всех сообщений из Zn
Используя мультипликативность системы RSA, объясните, как тогда он может с
высокой вероятностью достаточно быстро расшифровать любое сообщение.
|
