Криптосистема Ривеста — Шамира — Адельмана

RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом.

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

История

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

Изучив эту статью, трое ученых Рональд Райвест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman) из Массачусетского Технологического Института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами, им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

Описание RSA было опубликовано в августе 1977 года в журнале Scientific American. Авторы RSA поддерживали идею её активного распространения. В свою очередь, Агентство национальной безопасности (США), опасаясь использования этого алгоритма в негосударственных структурах, на протяжении нескольких лет безуспешно требовало прекращения распространения системы. Ситуация порой доходила до абсурда — например, когда программист Адам Бек(Adam Back) описал алгоритм RSA на языке

В 1983 году MIT был выдан патент 4405829 США, срок действия которого истёк 21 сентября 2000 года.^[1]

В 1977 году создателями RSA была зашифрована фраза «The Magic Words are Squeamish Ossifrage» («Волшебные слова — это брезгливый ягнятник»). За расшифровку была обещана награда в 100 долларов США. Лишь в конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. На протяжении полугода более 600 добровольцев жертвовали процессорное время 1600 машин (две из которых были факс-машинами). Координирование проходило через Интернет, и это был один из первых подобных проектов распределённых вычислений. Полученную награду победители пожертвовали в фонд свободного программного обеспечения.

В декабре 1997 года была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году, несколькими месяцами позже в 1974 году Малькольм Вильямсон изобрел математический алгоритм, основанный на коммутативности возведения в степень, аналогичный алгоритму Диффи-Хеллмана-Меркле.

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

Введение

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

• Если $x\,$ известно, то $f(x)\,$ вычислить относительно просто
• Если известно $y=f(x)\,$, то для $x\,$ нет простого пути вычисления

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

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

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

$\forall\,$ сообщения $M \in D\,$, где $D\,$-множество допустимых сообщений.
  $\forall\,$ открытого  и секретного ключа $P\,$ и $S\,$ 
    $\exist\,$ соответствующие функции $P()\,$ и  $S():\,$  
                     
                                $M=S(P(M))\,$
                                $M=P(S(M))\,$

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

1. Выбираются два случайных простых числа $p\,$ и $q\,$ заданного размера (например, 512 битов каждое).
2. Вычисляется их произведение $n=pq \,$
3. Вычисляется значение функция Эйлера от числа n:

   $\varphi(n)=(p-1)(q-1).$

4. Выбирается целое число $e\,$, взаимно простое со значением функции $\varphi(n) \,$. Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257, или 65537.
5. Вычисляется число d, мультипликативно обратное к числу e по модулю $\varphi(n)$, т.е число, удовлетворяющее сравнению:

   $d e \equiv 1\pmod{\varphi(n)}$; то есть $de = 1 + k\varphi(n)$, где k любое натуральное число (0, 1, 2…).

6. Пара $P=(e,n) \,$ публикуется в качестве открытого ключа RSA (RSA public key).
7. Пара $S=(d,n) \,$ играет роль секретного ключа RSA (RSA secret key) и держится в секрете.

Число $n\,$ называется модулем, а числа $e\,$ и $d\,$ — открытой и секретной экспонентами, соответственно.

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

Схема RSA

Предположим, сторона $B \,$ хочет послать стороне $A \,$ сообщение $M \,$.

Сообщением являются целые числа лежащие от $0 \,$ до $n-1 \,$, т.е $M \isin D=\mathbb{Z}_{n}\,$.

Алгоритм: Взять открытый ключ $(e,n) \,$ стороны $A \,$ Взять открытый текст $M \,$ Передать шифрованное сообщение: $P_A(M)=M^e \mod n~~~~~~~~~~(1)\,$

Алгоритм: Принять зашифрованное сообщение $C \,$ Применить свой секретный ключ $(d,n) \,$ для расшифровки сообщения: $S_A(C)=C^d \mod n~~~~~~~~~~(2)\,$

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

Уравнения $(1)\,$ и $(2)\,$, на которых основана схема RSA, определяют взаимно обратные преобразования множества $\mathbb{Z}_{n}\,$

Доказательство  

Действительно, для $\forall M \isin \mathbb{Z}_{n}\,$

$P(S(M))=S(P(M))= M^{ed} \mod n \,$

Докажем, что $M^{ed} \equiv M \pmod p ~~~\forall M \,$.

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

• $M \not\equiv 0 \pmod p \,$.

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

$ed=1+k(p-1)(q-1)\,$ для некоторого целого $k\,$ , тогда

$M^{ed}~~\equiv M(M^{p-1})^{k(q-1)} \pmod p \equiv$

$\equiv M(1)^{k(q-1)} \pmod p \equiv$

$\equiv M \pmod p ,$

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

• $M \equiv 0 \pmod p \,$, тогда $M^{ed} \equiv M \pmod p \,$

Таким образом, при всех $M\,$ выполняется равенство

$M^{ed} \equiv M \pmod p\,$

Аналогично можно показать, что $M^{ed} \equiv M \pmod q~~~ \forall M\,$.

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

$\boldsymbol {M^{ed} \equiv M \pmod n~~~\forall M}\,$

Пример

Этап	Описание операции	Результат операции
Генерация ключей	выбрать два простых числа	$p=3557, q=2579\,$
	вычислить модуль	$n=p\cdot q=3557\cdot2579=9173503$
	вычислить функцию Эйлера	$\varphi(n)=(p-1)(q-1)=9167368$
	выбрать открытый показатель	$e=3\,$
	вычислить секретный показатель	$d=6111579\,$
	опубликовать открытый ключ	$(e,n)=(3,9173503)\,$
	сохранить секретный ключ	$(d,n)=(6111579,9173503)\,$
Шифрование	выбрать открытый текст	$M=111111\,$
	вычислить шифротекст	$P(M)=M^e \bmod n=111111^3\bmod\ 9173503=4051753\,$
Расшифрование	вычислить исходное сообщение	$S(C)=C^d \bmod n=4051753^{6111579}\bmod\ 9173503=111111\,$

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

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

Предположим, что стороне $A\,$ нужно отправить стороне $B\,$ ответ $M'\,$, подтверждённый цифровой подписью.

Алгоритм: Взять открытый текст $M'~~~\,$ Создать цифровую подпись $\sigma \,$ с помощью своего секретного ключа$(d,n) \,$ $\sigma = S_A(M')=M'^d \mod n\,$ Передать пару $(M',\sigma )\,$, состоящую из сообщения и подписи.

Алгоритм: Принять пару $(M',\sigma )\,$ Взять открытый ключ $(e,n)\,$ стороны $A\,$ Проверить подлинность подписи: $P_A(\sigma )=\sigma ^e \mod n \equiv M' \rarr \,$ подпись верная

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

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

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

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

Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления $a=b^e \bmod n \,$ представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью алгоритма быстрого возведения в степень. Таким образом для вычисления $M^e \bmod n \,$ требуется $O( \ln e) \,$ операций умножения по модулю.

Доказательство  

• представим $e \,$ в двоичной системе счисления:

$e=e_{k} \cdot 2^{k}+e_{k-1} \cdot 2^{k-1}+...+e_{1} \cdot 2+e_{0}$, где $e_{k}=1, e_{i} \in \{ 0,1 \}$

• положим $M_0=1 \,$ и затем для $i=1,...,k \,$ вычислим

$M_i=M_{i-1}^2 \cdot M^{e_{k-i}} \,$

• найденное $M_k \,$ и будет искомым значением $M^e \bmod n \,$

Т.к каждое вычисление на шаге 2 требует не более трёх умножений по модулю $n \,$ и этот шаг выполняется $k \le \log_2 e \,$ раз, то сложность алгоритма может быть оценена величиной $O( \ln e) \,$.

Чтобы проанализировать время выполнения операций с открытым и секретным ключами, предположим, что открытый ключ $(e,n) \,$ и секретный ключ $(d,n) \,$ удовлетворяют соотношениям $\log_2 e =O(1),\log_2 d \le \beta \,$. Тогда в процессах их применения выполнятся соответственно $O(1)\,$ и $O(\beta)\,$ умножений по модулю.

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

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

Алгоритм RSA намного медленнее чем блочного шифрования. Программная реализация DES работает быстрее, по крайней мере, в 100 раз и от 1000 до 10 000 — в аппаратной реализации (в зависимости от конкретного устройства).

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

На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера $n \,$ в 1024 бита.

Зная разложение модуля $n \,$ на произведение двух простых чисел, противник может легко найти секретную экспоненту $d \,$ и тем самым взломать RSA. Однако на сегодняшний день самый быстрый алгоритм факторизации — решето обобщённого числового поля (General Number Field Sieve), скорость которого для k-битного целого числа составляет

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

не позволяет разложить большое целое за приемлемое время. Будем рассматривать возможные атаки на RSA, которые позволяют взломать эту систему, не используя прямого разложения модуля n на произведение двух простых чисел.

Элементарные атаки

Рассмотрим несколько атак связанных с неправильным использованием алгоритма RSA.

Генерация простых чисел

На случайные простые числа $p\,$ и $q\,$ накладываются следующие дополнительные ограничения:

• $p\,$ и $q\,$ не должны быть слишком близки друг к другу, иначе можно будет их найти, используя метод факторизации Ферма. Однако, если оба простых числа $p\,$ и $q\,$ были сгенерированы независимо, то это ограничение с огромной вероятностью автоматически выполняется.
• Необходимо выбирать «сильные» простые числа, чтобы нельзя было воспользоваться p-1 методом Полларда.

Схема с общим модулем n

Начальные данные: Чтобы избежать генерирования различных модулей $n=p*q \,$ для каждого пользователя, защищённый сервер использует единый n для шифрования всех сообщений. Сторона $A \,$ использует этот сервер для получения сообщения $M \,$

Задача: противник хочет расшифровать сообщение стороны $A \,$.

Казалось бы, шифротекст $C= M^{e_a} \mod n ,\,$ отправленный стороне $A \,$, не может быть расшифрован стороной $B \,$, если она не обладает секретным ключом $d_{a} \,$. Однако сторона $B \,$ может использовать свои экспоненты $e_b , d_b \,$, чтобы разложить модуль $n \,$, и после этого, зная $e_a \,$, вычислить секретную экспоненту $d_a \,$.

Защита: для каждого пользователя должен использоваться свой модуль $n \,$.

Атака на подпись RSA в схеме с нотариусом

Начальные данные: $(n,e) \,$ — открытый ключ нотариуса. Противник получает отказ при попытке подписания нотариусом сообщения $M \isin \mathbb{Z}_{n}\,$

Задача: противник хочет получить подпись нотариуса на сообщении $M \isin \mathbb{Z}_{n}\,$.

Противник выбирает произвольное $r \isin \mathbb{Z}_{n},\,$ вычисляет $M'= r^{e}M \mod n \,$ и отправляет это сообщение на подпись нотариусу.

Если нотариус подписывает это сообщение:

$S'= (M')^d \mod n \,$

то противник, вычислив $S= S'/r \mod n \,$, получает подпись сообщения $M \,$.

Действительно, $S^e=(S')^e/r^e=(M')^{ed}/r^e \equiv M'/r^e = M (\mod n) \,$

Защита: при подписи добавлять в сообщение некоторое случайное число (например, время).

Малые значения секретной экспоненты

Начальные данные: Чтобы увеличить скорость расшифрования (или создания цифровой подписи) было уменьшено число ненулевых битов двоичного представления секретной экспоненты $d \,$ (см. скорость алгоритма RSA).

Задача: вычислить секретную экспоненту $d \,$.

В 1990 году Михаэль Винер (Michael J. Wiener) показал, что в случае малого значения d возможен взлом системы RSA, а именно:

Теорема Винера:
  Пусть 
         n = pd, где $q<p<2q \,$
         $d< \frac{1}{3}n^{ \frac{1}{4}}$
  Тогда, если известно (n,e), где $ed = 1 \mod \varphi(n)$,
  то существует эффективный способ вычислить d.

Защита: Таким образом если n имеет размер 1024 бита, необходимо чтобы d был не менее 256 бит длиной.

Малые значения открытой экспоненты

Чтобы увеличить скорость шифрования и проверки цифровой подписи, используют малые значения открытой экспоненты $e \,$. Наименьшее из них $e=3 \,$. Однако, чтобы повысить криптоустойчивость алгоритма RSA, рекомендовано использовать

$e=2^{16} +1=65537 \,$.

Атака Хастада

Начальные условия: Сторона $B \,$ отсылает зашифрованное сообщение $M \,$ пользователям $P_1,P_2,...P_k \,$. Каждый пользователь имеет свой открытый ключ $(n_i,e_i) \,$, причём $M<n_i, \forall i\,$. Сторона $B \,$ зашифровывает сообщение, используя поочерёдно открытый ключ каждого пользователя, и отсылает его соответствующему адресату. Противник прослушивает канал передачи и собирает $k \,$ переданных шифротекстов.

Задача: противник хочет восстановить сообщение $M \,$.

Положим $e_i=3, \forall i \,$, тогда противник может восстановить $M \,$ если $k \geqslant 3 \,$.

Доказательство  

Действительно, если противник получил $C_1,C_2,C_3 \,$, где

$C_1=M^3 \mod n_1 \,$

$C_2=M^3 \mod n_2 \,$

$C_3=M^3 \mod n_3 \,$

Очевидно $n_1,n_2,n_3 \,$ взаимно просты, так как в противном случае хотя бы один из них был составным, что невозможно в системе RSA.Применяя китайскую теорему об остатках к $C_1,C_2,C_3 \,$, получим $C' \in \mathbb{Z}_{n_1 n_2 n_3} \,$,

$C'=M^3 \mod n_1n_2n_3 \,$

Поскольку $M<n_i, \forall i\,$,то $M^3<n_1n_2n_3, \forall i\,$ и

$C'=M^3 \,$

Т.е противник может восстановить сообщение $M \,$ вычислив корень кубический из $C' \,$.

В общем случае, если все открытые экспоненты равны $e \,$, противник может восстановить $M \,$ при $k \geqslant e \,$.

Рассмотрим простейшую защиту от этой атаки. Пусть сообщение $M_i \,$ для каждого пользователя является некоторой фиксированной перестановкой исходного сообщения $M \,$.К примеру

$M_i=i2^m+M \,$ — сообщение для i-го пользователя.

Хастад (Johan Hastad) показал, что даже в этом случае, противник может восстановить сообщение $M \,$ при достаточном количестве пользователей.

Защита: Эта атака возможна только при малом значении открытой экспоненты $e \,$, в этом случае криптостойкость системы RSA можно достигнуть, используя произвольную перестановку, а не фиксированную, пример которой был приведён выше.

Атака Франклина-Рейтера

Начальные условия:

Имеются два сообщения $M_1, M_2 \in \mathbb{Z}_n \,$, причём

$M_1=f(M_2) \mod n ,\,$ где $f \in \mathbb{Z}_n[x]\,$ некоторый открытый многочлен.

Сторона $A \,$ с открытым ключом $(n,e) \,$ получает эти сообщения от стороны $B \,$, которая просто зашифровывает сообщения$M_1 ,M_2 \,$ и передаёт полученные шифротексты $C_1 ,C_2 \,$.

Задача: Противник, зная $(n,e, C_1, C_2 ,f) \,$, хочет восстановить $M_1 , M_2 \,$.

Метью Франклин (Matthew K. Franklin) и Михаэль Рейтер (Michael K. Reiter) доказали, следующее утверждение:

Пусть    
     1)$(n,e) \,$ - открытый ключ системы RSA, причём $e= 3 \,$
     2)$M_1 \neq M_2 \in \mathbb{Z}_n \,$ и $M_1= f(M_2 ) \mod N \,$,
       для некоторого линейного многочлена $f=ax+b \in \mathbb{Z}_n[x] \,$, $b \neq 0 \,$
Тогда, зная $(n,e,C_1 , C_2,f) \,$, противник может восстановить $M_1 , M_2 \,$ 

Доказательство  

Действительно, для произвольного $e \,$:

$C_1={M^e}_1 \mod n ~~~~ \rightarrow ~~~~M_2 \,$, является корнем многочлена

$g_1(x)=f(x)^e-C_1 \in \mathbb{Z}_n[x] \,$

но, $M_2 \,$ является также корнем многочлена

$g_2(x)=x^e-C_2 \in \mathbb{Z}_n[x] \,$.

Таким образом $(x-M_2) \,$ делит оба многочлена. И противник может использовать алгоритм Евклида, чтобы вычислить НОД $(g_1 ,g_2) \,$. Если результат окажется линейным многочленом, то $M_2 \,$ будет найдено.

Когда $e=3 \,$, НОД $(g_1 ,g_2) \,$ является линейным многочленом, и следовательно противник может эффективно вычислить сообщения $M_1 , M_2 \,$.

Защита: при $e>3 \,$ время взлома системы RSA пропорционально $e^2 \,$, поэтому данная атака может быть использована только при малых значениях открытой экспоненты.

Атака по частично известной секретной экспоненте

Начальные условия:

Противник знает часть двоичного представления секретной экспоненты $d \,$.

Задача: восстановить $d \,$.

Оказывается, что когда $e< \sqrt{n} \,$, эта атака возможна, а именно:

  Пусть $(n,d) \,$ — секретный ключ системы RSA, где $n=pq \,$ имеет размер $\eta \,$ битов. 
  Тогда, зная $\eta/4 \,$ младших битов числа $d \,$, противник может восстановить  $d \,$ 
   за время, пропорциональное $e \log_2e \,$

Возможность взлома системы RSA в случае, когда открытая экспонента $e \,$ мала, так же очевидна из следующих рассуждений:

из определения $e \,$ и $d \,$:

$ed - k \varphi(n) = ed - k(n-p-q+1)=1 \,$

Поскольку $d< \varphi(n) \,$, то очевидно $0<k \leqslant e \,$.

При заданном $k \,$ противник может легко вычислить

$\hat{d}= \mathcal{b}(kn+1)/e \mathcal{c} \,$

Тогда при $q<p<2q \,$

$| \hat{d} -d| \leqslant k(p+q)/e \leqslant 3k \sqrt{n}/e < 3 \sqrt{n} \,$

Таким образом, $\hat{d} \,$ является хорошим приближением при $d \,$. Экспериментально показано, что в большинстве случаев старшие биты двоичного представления $\hat{d} \,$ совпадают с соответствующими битами секретной экспоненты $d \,$.

Поскольку возможны только $e \,$ различных значений $k \,$, противник может построить ряд, содержащий $e \,$ членов, для которого двоичное представление одного из его элементов совпадает со старшей половиной двоичного представления секретной экспоненты $d \,$.

Защита: увеличение открытой экспоненты $e \,$.

Атака с помощью квантового компьютера

С помощью квантового компьютера, если он будет построен, можно будет взломать RSA, так как квантовый алгоритм Шора позволяет осуществить факторизацию больших чисел за достаточно короткое время. Разложив модуль n на простые множители, можно будет вычислить секретный показатель d.

Атаки, связанные с реализацией системы RSA

Атака по времени выполнения

Начальные условия:

Рассмотрим смарт-карту, микропроцессор которой подписывает сообщения, используя встроенный секретный ключ RSA.

Задача: противник хочет получить секретную экспоненту $d \,$.

Пол Кохер (Paul Kocher), предложил атаку, основанную на высокоточных замерах времени выполнения шифратором смарт-карты определенных операций. Рассмотрим эту атаку на примере системы RSA, использующей алгоритм быстрого возведения в степень:

Противник получает подписи смарт-карты для большого числа произвольных сообщений $M_1 , M_2,...,M_k \in \mathbb{Z}_n \,$, и измеряет время генерации их подписей $T_i \,$.

В ходе атаки значение секретной экспоненты $d \,$ восстанавливается побитно, начиная с младшего бита:

• $d \,$ нечётное, поэтому $d_0=1 \,$.
• если $d_1=1 \,$ то микропроцессору смарт-карты необходимо произвести три умножения по модулю $n \,$, в отличии от двух, необходимых при $d_1=0 \,$(см.алгоритм быстрого возведения в степень).Обозначим $t_i \,$ — время вычислений процессора для сообщения $M_i \,$.

Кохер показал, что когда $d_1=1 \,$ два ансамбля $\mathcal{f} t_i \mathcal{g} \,$ и $\mathcal{f} T_i \mathcal{g} \,$ коррелируют.Однако в случае $d_1=0 \,$ они независимы. Таким образом, прибегая к корреляционному анализу, противник может определить $d_1 \,$.

• аналогично можно определить $d_2 , d_3 ... \,$.

Заметим, что в случае малой открытой экспоненты $e \,$ может быть применена атака по частично открытой секретной экспоненте.В этом случае достаточно восстановить половину бит секретной экспоненты $d \,$.

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

Атака при сбое аппаратной реализации RSA

Начальные условия:

Рассмотрим смарт-карту, микропроцессор которой подписывает сообщения, используя встроенный секретный ключ RSA. Микропроцессор карты использует китайскую теорему об остатках в целях ускорения процедуры подписи. Противник пытается вызвать сбой в вычислениях микропроцессора.

Задача: противник хочет вычислить модуль $n \,$.

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

Действительно, вычислив

$\sigma _p=M^{d_p} \mod p \,$ , где $d_p = d \mod (p-1)~~~~(a) \,$

$\sigma _q=M^{d_q} \mod q \,$ , где $d_q = d \mod (q-1)~~~~(b) \,$

можно получить подпись

$\sigma = T_1 \sigma _p + T_2 \sigma _q (\bmod n) \,$, где $T_1=\mathcal{f} 1 \mod p , 0 \mod q \mathcal{g} \,$

$T_2=\mathcal{f} 0 \mod p , 1 \mod q \mathcal{g} \,$

Очевидно вычисления $(a), (b) \,$ гораздо быстрее возведения в степень по модулю $n \,$.

Пусть действия противника вызвали сбой, повлёкший за собой дефект одного бита подписи. Тогда по крайней мере одна из $\sigma _p \,$ или $\sigma _q \,$ вычислена неправильно. Положим дефект содержится в $\hat{ \sigma _q} \,$.

В этом случае

$\hat{ \sigma ^e} \neq M \mod n \,$

$\hat{ \sigma ^e} \neq M \mod q \,$

однако

$\hat{ \sigma ^e} = M \mod p \,$

Таким образом противник может найти разложение $n \,$,как результат поиска НОД$(n, \hat{ \sigma_e} - m) \,$.

Защита:

• при подписи добавлять в сообщение некоторое случайное число(например время).
• проверять подпись перед тем как её отправить.

Применение RSA

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

Также она используется в открытой системе шифрования симметричными алгоритмами.

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

Примечания

1. ↑ U.S. Patent 4405829 (англ.)

Ссылки

• Справочное описание

Литература

• A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7
• Венбо Мао. Современная криптография: теория и практика = Modern Cryptography: Theory and Practice. — М.: «Вильямс», 2005. — 768 с. — ISBN 0-13-066943-1
• Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: «Диалектика», 2004. — 432 с. — ISBN 0-471-22357-3
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4

Криптографические алгоритмы с парой открытый/закрытый ключ

RSA • Схема Эль-Гамаля • ГОСТ Р 34.10-2001