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

Для улучшения этой статьи желательно?: Викифицировать статью.

Данная статья описывает условия использования криптоалгоритма с открытым ключом RSA, упрощающие криптоаналитические атаки^[1], и методы исключения таких условий.

Введение

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

Группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит.^[2] По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года. ^[3]

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

На первый шаг (выбор пары полиномов степени 6 и 1) было потрачено около полугода вычислений на 80 процессорах, что составило около 3 % времени, потраченного на главный этап алгоритма (просеивание), который выполнялся на сотнях компьютеров в течение почти двух лет. Если интерполировать это время на работу одного процессора AMD Opteron 2.2ГГц с 2Гб памяти, то получилось бы порядка 1500 лет. Обработка данных после просеивания для следующего ресурсоёмкого шага (линейной алгебры) потребовалось несколько недель на малом количестве процессоров. Заключительный шаг после нахождения нетривиальных решений ОСЛУ занял не более 12 часов.

Решение ОСЛУ проводилось с помощью метода Видемана на нескольких раздельных кластерах и длилось чуть менее 4 месяцев. При этом размер разреженной матрицы составил 192 796 550х192 795 550 при наличии 27 795 115 920 ненулевых элементов (то есть в среднем 144 ненулевых элементов на строку). Для хранения матрицы на жёстком диске понадобилось около 105 гигабайт. В то же время понадобилось около 5 терабайт сжатых данных для построения данной матрицы.

В итоге группе удалось вычислить 232-цифровой ключ, открывающий доступ к зашифрованным данным.

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

Зная разложение модуля $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\,$ были сгенерированы независимо, то это ограничение с огромной вероятностью автоматически выполняется.

Схема с общим модулем 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=pq$, где $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 \,$.

Оказывается, что:

Пусть $(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 \,$.

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

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

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

С помощью квантового компьютера, если он будет построен, можно будет взломать RSA, так как квантовый алгоритм Шора позволяет осуществить факторизацию больших чисел за достаточно короткое время. Разложив модуль n на простые множители (это можно сделать за время ${\textstyle{O(\log^2 n \log^3(\log n))}}$, используя O(log n) логических Q-битов), можно будет вычислить секретный показатель 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) \,$.

Защита:

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

Примечания

1. ↑ Ян С. Й. Криптоанализ RSA. — М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2011. — 312 с.
2. ↑ Анонс факторизации RSA-768  (англ.)
3. ↑ Факториация RSA-768  (англ.)