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

Введение

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

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

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

На первый шаг (выбор пары полиномов степени 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-ключ будет возможно в течение следующего десятилетия ^{[ когда? ]} .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle S'=(M')^{d}\mod n}$

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

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

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

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

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

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

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

Теорема Винера:

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

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

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

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

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

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

Начальные условия: Сторона ${\displaystyle B}$ отсылает зашифрованное сообщение ${\displaystyle M}$ пользователям ${\displaystyle P_{1},P_{2},...P_{k}}$ . Каждый пользователь имеет свой открытый ключ ${\displaystyle (n_{i},e_{i})}$ , причём ${\displaystyle M<n_{i},\forall i}$ . Сторона ${\displaystyle B}$ зашифровывает сообщение, используя поочерёдно открытый ключ каждого пользователя, и отсылает его соответствующему адресату. Противник прослушивает канал передачи и собирает ${\displaystyle k}$ переданных шифротекстов.

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

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

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

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

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

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

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

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

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

Имеются два сообщения ${\displaystyle M_{1},M_{2}\in \mathbb {Z} _{n}}$ , причём

${\displaystyle M_{1}=f(M_{2})\mod n,}$ где ${\displaystyle f\in \mathbb {Z} _{n}[x]}$ некоторый открытый многочлен.

Сторона ${\displaystyle A}$ с открытым ключом ${\displaystyle (n,e)}$ получает эти сообщения от стороны ${\displaystyle B}$ , которая просто зашифровывает сообщения ${\displaystyle M_{1},M_{2}}$ и передаёт полученные шифротексты ${\displaystyle C_{1},C_{2}}$ .

Задача: Противник, зная ${\displaystyle (n,e,C_{1},C_{2},f)}$ , хочет восстановить ${\displaystyle M_{1},M_{2}}$ .

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

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

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

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

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

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

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

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

Пусть ${\displaystyle (n,d)}$ — секретный ключ системы RSA, где ${\displaystyle n=pq}$ имеет размер ${\displaystyle \eta }$ битов.

Тогда, зная ${\displaystyle \eta /4}$ младших битов числа ${\displaystyle d}$ , противник может восстановить ${\displaystyle d}$ за время, пропорциональное ${\displaystyle e\log _{2}e}$

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

из определения ${\displaystyle e}$ и ${\displaystyle d}$ :

${\displaystyle ed-k\varphi (n)=ed-k(n-p-q+1)=1}$

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

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

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

Тогда при ${\displaystyle q<p<2q}$

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

Таким образом, ${\displaystyle {\hat {d}}}$ является хорошим приближением при ${\displaystyle d}$ .

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

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

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

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

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

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

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

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

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

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

Противник получает подписи смарт-карты для большого числа произвольных сообщений ${\displaystyle M_{1},M_{2},\dots ,M_{k}\in \mathbb {Z} _{n}}$ , и измеряет время генерации их подписей ${\displaystyle T_{i}}$ .

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

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

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

• аналогично можно определить ${\displaystyle d_{2},d_{3},\dots }$ .

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \sigma =T_{1}\sigma _{p}+T_{2}\sigma _{q}({\bmod {n}})}$ , где ${\displaystyle T_{1}={\mathcal {f}}1\mod p,0\mod q{\mathcal {g}}}$

${\displaystyle T_{2}={\mathcal {f}}0\mod p,1\mod q{\mathcal {g}}}$

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

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

В этом случае

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

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

однако

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

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

Защита:

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

Уязвимость в процессорах AMD

В 2021 году, группа исследователей, включающая Грацский технический университет , технологический институт Джорджии и некоммерческий исследовательский центр «Lamarr Security Research», используя уязвимость SMT в процессорах AMD с архитектурами Zen , Zen 2 и Zen 3 , смогла «взломать» ключ шифрования RSA -4096 .

Примечания