RSA

Материал из Википедии — свободной энциклопедии
Текущая версия страницы покане проверялась опытными участниками и может значительно отличаться отверсии, проверенной 19 мая 2024 года; проверки требуют5 правок.
Перейти к навигацииПерейти к поиску
У этого термина существуют и другие значения, см.RSA (значения).
RSA
Дата возникновения1977[1]
Названо в честьРональд Линн Ривест, Ади Шамир и Леонард Макс Адлеман
Определяющая формула(me)dm(modn){\displaystyle \left(m^{e}\right)^{d}\equiv m{\pmod {n}}}[2]
Обозначение в формулеm{\displaystyle m}, e{\displaystyle e}, d{\displaystyle d} и n{\displaystyle n}

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

Криптосистема RSA стала первой системой, пригодной и дляшифрования ицифровой подписи. Алгоритм используется в большом числе криптографических приложений, включаяPGP,S/MIME,TLS/SSL,IPsec/IKE и других[3].

Содержание

История

[править |править код]

Алгоритм шифрования с открытым и закрытым ключом приписываетсяУитфилду Диффи иМартину Хеллману, которые опубликовали эту концепцию в 1976 году. Они также ввели цифровые подписи и попытались применить теорию чисел. В их формулировке использовался секретный ключ с общим доступом, созданный путем экспоненциализации некоторого числа, простого по модулю. Однако они оставили открытой проблему реализации односторонней функции, возможно потому, что сложность факторизации в то время не была хорошо изучена.

Рон Ривест,Ади Шамир иЛеонард Адлеман из Массачусетского технологического института в течение года предприняли несколько попыток создать одностороннюю функцию, которую было бы трудно инвертировать. Ривест и Шамир, будучи компьютерными учеными, предложили множество потенциальных функций, а Адлеман, будучи математиком, отвечал за поиск их слабых мест. Они опробовали множество подходов, включая "ранцевый" и "перестановочные полиномы". Какое-то время они думали, что то, чего они хотели достичь, невозможно из-за противоречивых требований. В апреле 1977 года они провели Песах в доме одного из студентов и выпили много манишевицкого вина, а затем вернулись к себе домой около полуночи. Ривест, не в силах заснуть, лег на диван с учебником математики и начал думать о своей односторонней функции. Остаток ночи он провел, формализуя свою идею, и к рассвету большая часть статьи была готова. Алгоритм теперь известен как RSA - инициалы их фамилий в том же порядке, что и в их статье.

Клиффорд Кокс, английский математик, работавший в британской разведывательной службеGovernment Communications Headquarters (GCHQ), описал эквивалентную систему во внутреннем документе в 1973 г. Однако, учитывая относительно дорогие компьютеры, необходимые для ее реализации в то время, она считалась в основном курьезом и, насколько известно, так и не была применена. Однако его открытие было раскрыто только в 1997 году из-за его сверхсильного засекречивания.

В августе1977 года в колонке «Математические игры» Мартина Гарднера в журналеScientific American с разрешения Рональда Ривеста[4] появилось первое описание криптосистемы RSA[5]. Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом:

9686
1477
8829
7431
0816
3569
8962
1829
9613
1409
0575
9874
2982
3147
8013
9451
7546
2225
9991
6951
2514
6622
3919
5781
2206
4355
1245
2093
5708
8839
9055
5154

В качестве открытых параметров системы были использованы числа n=1143816...6879541 (129 десятичных знаков, 425бит, также известно какRSA-129) и e=9007. За расшифровку была обещана награда в 100 долларов США. По заявлению Ривеста, для факторизации числа потребовалось бы более 40 квадриллионов лет[6][3]. Однако чуть более, чем через 15 лет, 3 сентября1993 года, было объявлено о запуске проектараспределённых вычислений с координацией через электронную почту по нахождению сомножителей числа RSA-129 и решению головоломки. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (три из которых были факс-машинами[источник не указан 3375 дней]). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE[англ.]» («Волшебные слова — это брезгливыйягнятник»)[7][8]. Полученную награду победители пожертвовали вфонд свободного программного обеспечения.

После публикации Мартина Гарднера полное описание новой криптосистемы любой желающий мог получить, выслав по почте запрос Рональду Ривесту с приложенным конвертом с обратным адресом и марками на 35 центов.[5] Полное описание новой криптосистемы было опубликовано в журнале «Communications of the ACM» в феврале 1978 года[9].

Заявка на патент была подана 14 декабря 1977 года, в качестве владельца был указан MIT. Патент 4405829 был выдан 20 сентября1983 года, а 21 сентября 2000 года срок его действия истёк[10]. Однако за пределами США у изобретателей патента на алгоритм не было, так как в большинстве стран его необходимо было получить до первой публикации[11].

В 1982 году Ривест, Шамир и Адлеман организовали компаниюRSA Data Security[англ.] (в настоящий момент — подразделениеEMC). В 1989 году RSA, вместе с симметричным шифромDES, упоминается вRFC 1115, тем самым начиная использование алгоритма в зарождающейся сети Internet[12], а в 1990 году использовать алгоритм начинает министерство обороны США[13].

В ноябре 1993 года открыто публикуется версия 1.5 стандартаPKCS1[англ.], описывающего применение RSA для шифрования и создания электронной подписи. Последние версии стандарта также доступны в видеRFC (RFC 2313 — 1.5, 1993 год;RFC 2437 — 2.0, 1998 год;RFC 3447 — 2.1, 2002 год).

В декабре1997 года была обнародована информация о приоритете Клиффорда Кокса[14].

Описание алгоритма

[править |править код]

Введение

[править |править код]

Криптографические системы с открытым ключом используют так называемыеодносторонние функции, которые обладают следующим свойством:

Под односторонностью понимается не математически доказанная однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являютсявзаимно обратными, то есть:

{\displaystyle \forall } допустимых пар открытого и закрытого ключей(p,s){\displaystyle (p,s)}
{\displaystyle \exists } соответствующие функции шифрованияEp(x){\displaystyle E_{p}(x)} и расшифрованияDs(x){\displaystyle D_{s}(x)} такие, что
{\displaystyle \forall } сообщенияmM{\displaystyle m\in M}, гдеM{\displaystyle M} — множество допустимых сообщений,
m=Ds(Ep(m))=Ep(Ds(m)).{\displaystyle m=D_{s}(E_{p}(m))=E_{p}(D_{s}(m)).}

Алгоритм создания открытого и секретного ключей

[править |править код]

RSA-ключи генерируются следующим образом[15]:

1) выбираются два различныхслучайных простых числаp{\displaystyle p} иq{\displaystyle q} заданного размера (например, 1024бита каждое);
2) вычисляется их произведениеn=pq{\displaystyle n=p\cdot q}, которое называетсямодулем;
3) вычисляется значениефункции Эйлера от числаn{\displaystyle n}:
φ(n)=(p1)(q1){\displaystyle \varphi (n)=(p-1)\cdot (q-1)};
4) выбирается целое числоe{\displaystyle e} (1<e<φ(n){\displaystyle 1<e<\varphi (n)}),взаимно простое со значением функцииφ(n){\displaystyle \varphi (n)};
числоe{\displaystyle e} называетсяоткрытой экспонентой (англ. public exponent);
обычно в качествеe{\displaystyle e} берут простые числа, содержащие небольшое количество единичных бит вдвоичной записи, например,
простые изчисел Ферма: 17, 257 или 65537, так как в этом случае время, необходимое для шифрования с использованием
быстрого возведения в степень, будет меньше;
слишком малые значенияe{\displaystyle e}, например 3, потенциально могут ослабить безопасность схемы RSA.[16];
5) вычисляется числоd{\displaystyle d},мультипликативно обратное к числуe{\displaystyle e} по модулюφ(n){\displaystyle \varphi (n)}, то есть число, удовлетворяющеесравнению:
de1(modφ(n)){\displaystyle d\cdot e\equiv 1{\pmod {\varphi (n)}}}
(числоd{\displaystyle d} называетсясекретной экспонентой; обычно оно вычисляется при помощирасширенного алгоритма Евклида);
6) пара(e,n){\displaystyle (e,n)} публикуется в качествеоткрытого ключа RSA (англ. RSA public key);
7) пара(d,n){\displaystyle (d,n)} играет рользакрытого ключа RSA (англ. RSA private key) и держится в секрете.

Шифрование и расшифрование

[править |править код]

Предположим, Боб хочет послать Алисе сообщениеm{\displaystyle m}.

Сообщениями являютсяцелые числа в интервале от0{\displaystyle 0} доn1{\displaystyle n-1}.[15]

Алгоритм шифрования[15]:

Алгоритм расшифрования:

Данная схема на практике не используется по причине того, что она не являетсяпрактически надёжной (semantically secured). Действительно, односторонняя функция E(m) являетсядетерминированной — при одних и тех же значениях входных параметров (ключа и сообщения) выдаёт одинаковый результат. Это значит, что не выполняется необходимое условие практической (семантической) надёжности шифра.

Алгоритм шифрования сеансового ключа

[править |править код]

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

Алгоритм шифрования сеансового ключа выглядит следующим образом[17]:

Алгоритм:

Алгоритм:


В случае, когда сеансовый ключ больше, чем модульn{\displaystyle n}, сеансовый ключ разбивают на блоки нужной длины (в случае необходимости дополняют нулями) и шифруют каждый блок.

Корректность схемы RSA

[править |править код]
Уравнения(1){\displaystyle (1)} и(2){\displaystyle (2)}, на которых основана схема RSA, определяютвзаимно обратные преобразования множестваZn{\displaystyle \mathbb {Z} _{n}}
Доказательство[15][18]

Действительно, дляmZn{\displaystyle \forall m\in \mathbb {Z} _{n}}

D(E(m))=E(D(m))=medmodn{\displaystyle D\left({E\left(m\right)}\right)=E\left({D\left(m\right)}\right)=m^{ed}\mod n}

Покажем, что:

mZn:medmmodp{\displaystyle \forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod p}.

Возможны два случая:

Поскольку числаe{\displaystyle e} иd{\displaystyle d} являются взаимно обратными относительно умножения по модулюφ(n)=(p1)(q1){\displaystyle \varphi (n)=(p-1)(q-1)}, т.e

ed=1+k(p1)(q1){\displaystyle ed=1+k(p-1)(q-1)} для некоторого целогоk{\displaystyle k},

тогда:

medm1+k(p1)(q1)modpm(mp1)k(q1)modpm(1)k(q1)mmodp{\displaystyle {\begin{aligned}m^{ed}&\equiv m^{1+k\left({p-1}\right)\left({q-1}\right)}&\equiv &\mod p\\&\equiv m\left({m^{p-1}}\right)^{k\left({q-1}\right)}&\equiv &\mod p\\&\equiv m\left(1\right)^{k\left({q-1}\right)}&\equiv m&\mod p\end{aligned}}}

где второе тождество следует изтеоремы Ферма.

  • Рассмотрим второй случай:
m0modp{\displaystyle m\equiv 0\mod p},

тогда

med0mmodp{\displaystyle m^{ed}\equiv 0\equiv m\mod p}

Таким образом, при всехm{\displaystyle m} выполняется равенство

medmmodp{\displaystyle m^{ed}\equiv m\mod p}

Аналогично можно показать, что:

mZn:medmmodq{\displaystyle \forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod q}.

Тогда, изкитайской теоремы об остатках

mZn:medmmodn{\displaystyle \forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod n}

Пример

[править |править код]
ЭтапОписание операцииРезультат операции
ГенерацияключейВыбрать два простых различных числа
p=3557{\displaystyle p=3557},
q=2579{\displaystyle q=2579}
Вычислить произведение
n=pq=35572579=9173503{\displaystyle n=p\cdot q=3557\cdot 2579=9173503}
Вычислитьфункцию Эйлера
φ(n)=(p1)(q1)=9167368{\displaystyle \varphi (n)=(p-1)(q-1)=9167368}
Выбрать открытую экспоненту
e = 3
Вычислить секретную экспоненту
d=(kφ(n)+1)/e=(29167368+1)/3=6111579{\displaystyle {\begin{aligned}d&=(k\cdot \varphi (n)+1)/e\\&=(2\cdot 9167368+1)/3\\&=6111579\end{aligned}}}
Опубликоватьоткрытый ключ
{e,n}={3,9173503}{\displaystyle \{e,n\}=\{3,9173503\}}
Сохранитьзакрытый ключ
{d,n}={6111579,9173503}{\displaystyle \{d,n\}=\{6111579,9173503\}}
ШифрованиеВыбрать текст для зашифрования
m=111111{\displaystyle m=111111}
Вычислить шифротекст
c=E(m)=memodn=1111113mod9173503=4051753{\displaystyle {\begin{aligned}c&=E(m)\\&=m^{e}\mod n\\&=111111^{3}\mod 9173503\\&=4051753\end{aligned}}}
РасшифрованиеВычислить исходное сообщение
m=D(c)==cdmodn=40517536111579mod9173503=111111{\displaystyle {\begin{aligned}m&=D(c)=\\&=c^{d}\mod n\\&=4051753^{6111579}\mod 9173503\\&=111111\end{aligned}}}

Цифровая подпись

[править |править код]

Система RSA может использоваться не только для шифрования, но и дляцифровой подписи.

Предположим, что Алисе (сторонеA{\displaystyle A}) нужно отправить Бобу (сторонеB{\displaystyle B}) сообщениеm{\displaystyle m}, подтверждённоеэлектронной цифровой подписью.

Алгоритм:

s=SA(m)=mdmodn{\displaystyle s=S_{A}\left(m\right)=m^{d}\mod n}

Алгоритм:

m=PA(s)=semodn{\displaystyle m'=P_{A}\left(s\right)=s^{e}\mod n}

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

Важное свойство цифровой подписи заключается в том, что её может проверить каждый, кто имеет доступ к открытому ключу её автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись. Например, сторонаA{\displaystyle A} может переслать сторонеB{\displaystyle B} электронный чек. После того как сторонаB{\displaystyle B} проверит подпись стороныA{\displaystyle A} на чеке, она может передать его в свой банк, служащие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию.

Заметим, что подписанное сообщениеm{\displaystyle m} незашифровано. Оно пересылается в исходном виде и его содержимое не защищено от нарушения конфиденциальности. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа, принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа[17]. Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.

Скорость работы алгоритма RSA

[править |править код]

Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисленияa=bcmodn{\displaystyle a=b^{c}{\bmod {n}}} представляет основную вычислительную сложность. Эта задача может быть разрешена с помощьюалгоритма быстрого возведения в степень. С использованием этого алгоритма для вычисленияmemodn{\displaystyle m^{e}{\bmod {n}}} требуетсяO(lne){\displaystyle O\left(\ln e\right)} операцийумножения по модулю[19].

Подробнее
  • представимe{\displaystyle e} в двоичной системе счисления:
e=ek2k+ek12k1++e12+e0{\displaystyle e=e_{k}\cdot 2^{k}+e_{k-1}\cdot 2^{k-1}+\dots +e_{1}\cdot 2+e_{0}}, где
ek=1,ei{0,1}{\displaystyle e_{k}=1,e_{i}\in \left\{0,1\right\}}
mi=(mi12meki)modn{\displaystyle m_{i}=\left(m_{i-1}^{2}\cdot m^{e_{k-i}}\right){\bmod {n}}}

Т. к. каждое вычисление на шаге 2 требует не более трёх умножений по модулюn{\displaystyle n} и этот шаг выполняетсяklog2e{\displaystyle k\leq \log _{2}e} раз, то сложность алгоритма может быть оценена величинойO(lne){\displaystyle O(\ln e)}.

Чтобы проанализировать время выполнения операций с открытым и закрытым ключами, предположим, что открытый ключ{e,n}{\displaystyle \left\{e,n\right\}} и закрытый ключ{d,n}{\displaystyle \left\{d,n\right\}} удовлетворяют соотношениямlog2e=O(1){\displaystyle \log _{2}e=O(1)},log2dβ{\displaystyle \log _{2}d\leq \beta }. Тогда в процессах их применения выполняется соответственноO(1){\displaystyle O\left(1\right)} иO(β){\displaystyle O\left(\beta \right)} умножений по модулю.

Таким образом время выполнения операций растёт с увеличением количества ненулевых битов вдвоичном представлении открытой экспонентыe. Чтобы увеличить скорость шифрования, значениеe часто выбирают равным 17, 257 или 65537 —простым числам, двоичное представление которых содержит лишь две единицы: 1710=100012, 25710=1000000012, 6553710=100000000000000012 (простыечисла Ферма).

По эвристическим оценкам длина секретной экспонентыd{\displaystyle d}, нетривиальным образом зависящей от открытой экспонентыe{\displaystyle e} и модуляn{\displaystyle n}, с большой вероятностью близка к длинеn{\displaystyle n}. Поэтому расшифрование данных идёт медленнее, чем шифрование, а проверка подписи – быстрее, чем её создание.

Алгоритм RSA намного медленнее, чемAES и другие алгоритмы, использующие симметричныеблочные шифры.

Использование китайской теоремы об остатках для ускорения расшифрования

[править |править код]

При расшифровании или подписывании сообщения в алгоритме RSA показатель вычисляемой степени будет довольно большим числом (порядка 1000 бит). Поэтому требуется алгоритм, сокращающий количество операций. Так как числаp{\displaystyle p} иq{\displaystyle q} в разложенииN=pq{\displaystyle N=pq} известны владельцу закрытого ключа, то можно вычислить:

mp=Cdmodp=Cdmodp1modp,{\displaystyle m_{p}=C^{d}{\bmod {p}}=C^{d{\bmod {p-1}}}{\bmod {p}},}
mq=Cdmodq=Cdmodq1modq.{\displaystyle m_{q}=C^{d}{\bmod {q}}=C^{d{\bmod {q-1}}}{\bmod {q}}.}

Посколькуp{\displaystyle p} иq{\displaystyle q} — числа порядка2512,{\displaystyle 2^{512},} на эти действия потребуется два возведения числа в 512-битовую степень по модулю 512-битового числа. Это существенно (для 1024 бит тестирование показало в 3 раза) быстрее, чем одно возведение в 1024-битовую степень по модулю 1024-битового числа.Далее осталось восстановитьm{\displaystyle m} поmp{\displaystyle m_{p}} иmq,{\displaystyle m_{q},} что можно сделать с помощьюкитайской теоремы об остатках[20].

Криптоанализ RSA

[править |править код]
Основная статья:Криптоанализ RSA

Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования[21]

c=E(m)=memodn{\displaystyle c=E(m)=m^{e}\mod n}.

Для вычисленияm{\displaystyle m} по известнымc,e,n{\displaystyle c,e,n} нужно найти такойd{\displaystyle d}, чтобы

ed1(modφ(n)),{\displaystyle e\cdot d\equiv 1{\pmod {\varphi (n)}},}

то есть найтиобратный элемент кe{\displaystyle e} вмультипликативной группе вычетов по модулюφ(n).{\displaystyle \varphi (n).}

Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значениеφ(n){\displaystyle \varphi (n)}. Для вычисленияфункции Эйлера от известного числаn{\displaystyle n} необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей —«потайной дверцей» (англ. backdoor), которая используется для вычисленияd{\displaystyle d} владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, так называемойфакторизации, самый быстрый из которых на сегодняшний день —общий метод решета числового поля, скорость которого для k-битного целого числа составляет

exp((c+o(1))k13log23k){\displaystyle \exp((c+o(1))k^{\frac {1}{3}}\log ^{\frac {2}{3}}k)} для некоторогоc<2{\displaystyle c<2}.

В 2010 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялосьобщим методом решета числового поля[22]. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года[23]. С 31 декабря 2013 года браузеры Mozilla перестали поддерживать сертификаты удостоверяющих центров с ключами RSA меньше 2048 бит[24].

Кроме того, при неправильной или неоптимальной реализации или использовании алгоритма возможны специальные криптографические атаки, такие как атаки на схемы с малой секретной экспонентой или на схемы с общим выбранным значением модуля.

Атаки на алгоритм RSA

[править |править код]

Атака Винера на RSA

[править |править код]
Основная статья:Атака Винера

В некоторых приложениях требуется ускорить процесс расшифровывания в алгоритме RSA. Поэтому выбирается небольшая расшифровывающая экспонента. В случае когда расшифровывающая экспонентаd<N14{\displaystyle d<N^{\frac {1}{4}}} можно определитьd{\displaystyle d} за полиномиальное время с помощьюатаки Винера[20], опирающейся нанепрерывные дроби.

Подробнее
По вещественному числуαR{\displaystyle \alpha \in \mathbb {R} } определим последовательности:

α0=α,p0=q0=1,p1=a0a1+1,q1=a1,{\displaystyle \alpha _{0}=\alpha ,p_{0}=q_{0}=1,p_{1}=a_{0}a_{1}+1,q_{1}=a_{1},}
αi=αi,αi+1=1αiai,{\displaystyle \alpha _{i}=\lfloor \alpha _{i}\rfloor ,\alpha _{i+1}={\frac {1}{\alpha _{i}-a_{i}}},}
pi=aipi1+pi1{\displaystyle p_{i}=a_{i}p_{i-1}+p_{i-1}} приi2,{\displaystyle i\geq 2,}

qi=aiqi1+qi1{\displaystyle q_{i}=a_{i}q_{i-1}+q_{i-1}} приi2.{\displaystyle i\geq 2.}

Целые числаa0,a1,a2,...{\displaystyle a_{0},a_{1},a_{2},...} называютсянепрерывной дробью, представляющейα,{\displaystyle \alpha ,} а рациональные числаpiqi{\displaystyle {\frac {p_{i}}{q_{i}}}-} подходящими дробями. Каждая из подходящих дробей несократима, а скорость роста их знаменателей сравнима с показательной.Один из важных результатов теориинепрерывных дробей:

Если несократимая дробьpq{\displaystyle {\frac {p}{q}}} удовлетворяет неравенству:
|αpq|12q2,{\displaystyle \left|\alpha -{\frac {p}{q}}\right|\leq {\frac {1}{2q^{2}}},}

тоpq{\displaystyle {\frac {p}{q}}-} одна из подходящих дробей в разложенииα{\displaystyle \alpha } внепрерывную дробь.

Пусть у нас есть модульN=pq,{\displaystyle N=pq,} причёмq<p<2q.{\displaystyle q<p<2q.}  Допустим нападающему известна шифрующая экспонента E, обладающая свойством
Ed=1modφ,{\displaystyle Ed=1\mod \varphi ,}
гдеφ=φ(N)=(p1)(q1).{\displaystyle \varphi =\varphi (N)=(p-1)(q-1).}  Будем также считать, чтоE<φ,{\displaystyle E<\varphi ,} поскольку это выполнено в большинстве приложений. Из предположений следует, что
Edkφ=1.{\displaystyle Ed-k\varphi =1.}
Следовательно,

|Eφkd|=1dφ.{\displaystyle \left|{\frac {E}{\varphi }}-{\frac {k}{d}}\right|={\frac {1}{d\varphi }}.}

|Nφ|=|p+q1|<3N12.{\displaystyle \left|N-\varphi \right|=\left|p+q-1\right|<3N^{\frac {1}{2}}.}
Отсюда видно, чтоEN{\displaystyle {\frac {E}{N}}-} довольно хорошее приближение дляkd.{\displaystyle {\frac {k}{d}}.}  Действительно,
|ENkd|=|EdNkdN|=|EdkφNk+kφdN|=|1k(Nφ)dN||3kN12dN|=3kdN12.{\displaystyle \left|{\frac {E}{N}}-{\frac {k}{d}}\right|=\left|{\frac {Ed-Nk}{dN}}\right|=\left|{\frac {Ed-k\varphi -Nk+k\varphi }{dN}}\right|=\left|{\frac {1-k(N-\varphi )}{dN}}\right|\leq \left|{\frac {3kN^{\frac {1}{2}}}{dN}}\right|={\frac {3k}{dN^{\frac {1}{2}}}}.}

Так какE<φ,{\displaystyle E<\varphi ,} очевидно,k<d.{\displaystyle ,k<d.} Кроме того, так как предполагалось, чтоd<14N14.{\displaystyle d<{\frac {1}{4}}N^{\frac {1}{4}}.} Значит,

|ENkd|<12d2.{\displaystyle \left|{\frac {E}{N}}-{\frac {k}{d}}\right|<{\frac {1}{2d^{2}}}.}

Поскольку НОД(k,d)=1,{\displaystyle (k,d)=1,} тоkd{\displaystyle {\frac {k}{d}}-} подходящая дробь в разложении дробиEN{\displaystyle {\frac {E}{N}}} внепрерывную. Таким образом, можно узнать расшифровывающую экспоненту, поочерёдно подставляя знаменатели подходящих дробей в выражение:

(ME)d=MmodN{\displaystyle (M^{E})^{d}=M\mod N}

для некоторого случайного числаM.{\displaystyle M.} Получив равенство, найдёмd.{\displaystyle d.} Общее число подходящих дробей, которое придётся проверить оценивается какO(lnN).{\displaystyle O(lnN).}

Обобщённая атака Винера

[править |править код]

Атака Винера, описанная выше, возможна лишь в том случае, когда атакующему известно о неравенстве

d13N14,{\displaystyle d\leq {\frac {1}{3}}N^{\frac {1}{4}},}

гдеd{\displaystyle d} — секретная экспонента, аN{\displaystyle N} — модуль RSA.Боне и Дерфи, используя двумерный аналогТеоремы Копперсмита, смогли обобщитьатаку Винера[20] на случай, когда

dN0,292.{\displaystyle d\leq N^{0,292}.}

Атака посредника, или атака «человек посередине»

[править |править код]

Атака посредника не опасна если злоумышленник может только прослушивать канал связи по которому передаётся открытый ключ. В этом случае злоумышленник сможет перехватить открытый ключ и зашифрованные сообщения, и подписи. Но при условии, что злоумышленник перехватил ключ и может отправлять сообщения по каналу связи. Злоумышленник может отправлять ложные сообщения.

Применение RSA

[править |править код]

Система RSA используется для защитыпрограммного обеспечения и в схемахцифровой подписи.

Также она используется в открытой системе шифрованияPGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании ссимметричными алгоритмами.

Из-за низкой скорости шифрования сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайнымсеансовым ключом (например,AES,IDEA,Serpent,Twofish), а с помощью RSA шифруют лишь этот ключ, таким образом реализуетсягибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использоватькриптографически стойкий генератор псевдослучайных чисел для формирования случайного сеансового ключа симметричного шифрования.

Примечания

[править |править код]
  1. Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its FoundersОбщество промышленной и прикладной математики.
  2. Introduction to Modern Cryptography (англ.) — 2 —CRC Press, 2015. — P. 411. — 583 p. —ISBN 978-1-4665-7026-9
  3. 12Bakhtiari, Maarof, 2012, p. 175.
  4. A Quarter Century of Recreational Mathematics, by Martin Gardner (англ.). Scientific American. — «Ronald L. Rivest of the Massachusetts Institute of Technology allowed me to be the first to reveal—in the August 1977 column—the «publickey» cipher system that he co-invented». Дата обращения: 3 марта 2012. Архивировано изоригинала 23 июня 2012 года.
  5. 12Gardner, 1977.
  6. Bruce Schneier. Factoring — State of the Art and Predictions (англ.) (12 февраля 1995). Дата обращения: 3 марта 2012. Архивировано изоригинала 23 июня 2012 года.
  7. Donald T. Davis. A Discussion of RSA-129 Activity (англ.) (25 ноября 2003). Дата обращения: 3 марта 2012. Архивировано изоригинала 23 июня 2012 года.
  8. Чмора А. Л. 4.6.4. Силовая атака на основе распределенных вычислений // Современная прикладная криптография. — 2002. —2000 экз. —ISBN 5-85438-046-3.
  9. Rivest, Shamir, Adleman, 1978.
  10. Ronald L. Rivest et al.Cryptographic Communications System and Method
  11. Adam Back. PGP Timeline (англ.). Дата обращения: 3 марта 2012. Архивировано изоригинала 23 июня 2012 года.
  12. J. Linn. Privacy Enhancement for Internet Electronic Mail: Part III — Algorithms, Modes, and Identifiers (англ.) (август 1989). Дата обращения: 18 марта 2012. Архивировано изоригинала 23 июня 2012 года.
  13. RSA Security Inc. Company history (англ.). FundingUniverse. Дата обращения: 18 марта 2012. Архивировано изоригинала 23 июня 2012 года.
  14. C. C. CocksA note on «non-secret encryption»Архивировано 4 августа 2009 года. (англ.) 20 ноября 1973
  15. 1234Menezes, Oorschot, Vanstone, 1996, 8.2. RSA public-key encryption.
  16. Boneh, 1999.
  17. 12Брюс Шнайер. Прикладная криптография 2-е издание протоколы, алгоритмы и исходные тексты на языке C++
  18. Rivest, Shamir, Adleman, 1978, pp. 7—8.
  19. Rivest, Shamir, Adleman, 1978, p. 8.
  20. 123 Н. СМАРТ Мир программирования Криптография — изд. Техносфера, Москва 2006
  21. Ян С. Й. Криптоанализ RSA. — М.—Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2011. — 312 с.
  22. Анонс факторизации RSA-768Архивная копия от 13 апреля 2014 наWayback Machine (англ.)
  23. Факторизация RSA-768Архивная копия от 13 декабря 2012 наWayback Machine (англ.)
  24. Dates for Phasing out MD5-based signatures and 1024-bit moduli  (неопр.). Дата обращения: 2 марта 2013. Архивировано 20 ноября 2012 года.

Литература

[править |править код]
Перейти к шаблону «Криптосистемы с открытым ключом»
Алгоритмы
Факторизация целых чисел
Дискретное логарифмирование
Криптография на решётках
Другие
Теория
Стандарты
Темы
Источник —https://ru.wikipedia.org/w/index.php?title=RSA&oldid=143959365
Категории:
Скрытые категории: