Русская Википедия:Криптоанализ RSA

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

Введение

На 2009 год система шифрования на основе RSA считается надёжной начиная с размера <math> n</math> в 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-ключ будет возможно в течение следующего десятилетияШаблон:Когда.

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

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

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

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

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

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

На случайные простые числа <math>p</math> и <math>q</math> накладывается следующее дополнительное ограничение:

<math>p</math> и <math>q</math> не должны быть слишком близки друг к другу, иначе можно будет их найти, используя метод факторизации Ферма. Однако, если оба простых числа <math>p</math> и <math>q</math> были сгенерированы независимо, то это ограничение с огромной вероятностью автоматически выполняется.

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

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

Задача: противник хочет расшифровать сообщение стороны <math>A</math>.

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

Защита: для каждого пользователя должен использоваться свой модуль <math>n</math>.

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

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

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

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

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

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

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

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

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

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

Задача: вычислить секретную экспоненту <math>d</math>.

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

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

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

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

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

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

<math>e=2^{16} +1=65537</math>.

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

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

Задача: противник хочет восстановить сообщение <math>M</math>.

Положим <math>e_i=3, \forall i</math>, тогда противник может восстановить <math>M</math> если <math>k \geqslant 3</math>. Шаблон:Hider В общем случае, если все открытые экспоненты равны <math>e</math>, противник может восстановить <math>M</math> при <math>k \geqslant e</math>.

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

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

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

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

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

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

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

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

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

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

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

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

Шаблон:Hider

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

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

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

Противник знает часть двоичного представления секретной экспоненты <math>d</math>.

Задача: восстановить <math>d</math>.

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

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

Тогда, зная <math> \eta/4</math> младших битов числа <math>d</math>, противник может восстановить <math> d</math> за время, пропорциональное <math>e \log_2e</math>

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

из определения <math>e</math> и <math>d</math>:

<math>ed - k \varphi(n) = ed - k(n-p-q+1)=1</math>

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

При заданном <math>k</math> противник может легко вычислить

<math> \hat{d}= \mathcal{b}(kn+1)/e \mathcal{c}</math>

Тогда при <math>q<p<2q</math>

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

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

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

Защита: увеличение открытой экспоненты <math>e</math>.

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

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

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

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

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

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

Задача: противник хочет получить секретную экспоненту <math>d</math>.

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

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

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

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

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

аналогично можно определить <math>d_2 , d_3, \dots</math>.

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

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

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

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

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

Задача: противник хочет вычислить модуль <math>n</math>.

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

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

<math> \sigma _p=M^{d_p} \mod p</math> , где <math>d_p = d \mod (p-1)EducationBot (обсуждение) 04:22, 24 августа 2023 (+04)(a)</math>

<math> \sigma _q=M^{d_q} \mod q</math> , где <math>d_q = d \mod (q-1)EducationBot (обсуждение) 04:22, 24 августа 2023 (+04)(b)</math>

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

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

<math> T_2=\mathcal{f} 0 \mod p , 1 \mod q \mathcal{g}</math>

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

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

В этом случае

<math>\hat{ \sigma ^e} \neq M \mod n</math>

<math>\hat{ \sigma ^e} \neq M \mod q</math>

однако

<math>\hat{ \sigma ^e} = M \mod p</math>

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

Защита:

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

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

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

Примечания

Шаблон:Примечания

↑ Ян С. Й. Криптоанализ RSA. — М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2011. — 312 с.
↑ Анонс факторизации RSA-768 Шаблон:Wayback Шаблон:Ref-en
↑ Факториация RSA-768 Шаблон:Wayback Шаблон:Ref-en
↑ Шаблон:PDFlink
↑ Шаблон:Cite web
↑ Шаблон:Cite web

[1] Ян С. Й. Криптоанализ RSA. — М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2011. — 312 с.

[2] Анонс факторизации RSA-768 Шаблон:Wayback Шаблон:Ref-en

[3] Факториация RSA-768 Шаблон:Wayback Шаблон:Ref-en

[4] Шаблон:PDFlink

[5] Шаблон:Cite web

[6] Шаблон:Cite web

[1]

[2]

[3]

[4]

[5]

[6]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.