Криптографическая система RSA

 

Самый общий алгоритм открытого ключа доступа – криптографическая система RSА, названная по имени его изобретателей Ривеста, Шамира, Эделмана (Rivest, Shamir и Adelman).

RSА использует два типа ключей – e и d, где e – открытый, a d – секретный. Предположим, что P – исходный текст и C – зашифрованный текст. Алиса использует C = P^e mod n, чтобы создать зашифрованный текст C из исходного текста P; Боб использует P = C^d mod n, чтобы извлечь исходный текст (файл), переданный Алисой. Модулей n создается очень большое количество с помощью процесса генерации ключей, который мы обсудим позже.

Для шифрования и дешифрования применяют возведение в степень по модулю. При использовании быстрого алгоритма возведение в степень по модулю выполнимо в полиномиальное время. Однако нахождение модульного логарифма так же сложно, как и разложение числа по модулю. Для него нет алгоритма с полиномиальным временем. Это означает, что Алиса может зашифровать сообщение общедоступным ключом (e) в полиномиальное время. Боб также может расшифровать его в полиномиальное время (потому что он знает d). Но Ева не может расшифровать это сообщение, потому что она должна была бы вычислить корень e-той степени из C с использованием модульной арифметики. Рис. 4 показывает идею RSA.

Рис. 4 Сложность операций в RSA

 

Другими словами, Алиса использует одностороннюю функцию (возведение в степень по модулю) с лазейкой, известной только Бобу. Ева не знает лазейку, поэтому не может расшифровать сообщение. Если когда-нибудь найдут полиномиальный алгоритм для модуля вычисления корня e-той степени из n, то возведение в степень по модулю n не будет больше односторонней функцией.

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

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

 

Рис. 5 Шифрование, дешифрование и генерация ключей в RSA

RSA использует две алгебраических структуры: кольцо и группу.

Кольца шифрования/дешифрования. Шифрование и дешифрование сделаны с использованием коммутативного кольца с двумя арифметическими операциями: сложение и умножение. В RSA это кольцо общедоступно, потому что модуль n общедоступен. Любой может послать сообщение Бобу, используя это кольцо для шифрования.

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

RSA использует две алгебраических структуры: открытое кольцо R = < Z_n, +, × > и секретную группу G = < Z _(n)*, × >.

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

• Выбираются два случайных простых числа p и q

• Вычисляется их произведение n=p*q, которое называется модулем.

• Вычисляется значение функции Эйлера от числа n:

φ(n)=(p-1)(q-1)

• Выбирается открытый ключ е с учетом условий:

1<e<φ(n), НОД(е,φ(n))=1

• Определяется секретный ключ d, удовлетворяющего условию:

e*d≡1 (mod φ(n)), где d<n

• Пара P=(e,n) публикуется в качестве открытого ключа RSA

• Пара S=(d,n) играет роль секретного ключа RSA и держится в секрете

Боб использует шаги, показанные в данном алгоритме, чтобы создать свои открытый и секретный ключи. После генерации ключей Боб объявляет кортеж (e, n) как свой открытый ключ доступа: Боб сохраняет d как свой секретный ключ. Боб может отказаться от p, q и ; они не могут изменить его секретный ключ, не изменяя модуль. Для безопасности рекомендуется размер для каждого простого p или q – 512 бит (почти 154 десятичные цифры). Это определяет размер модуля, n 1024 бита (309 цифр).

В RSA кортеж (e, n) – открытый ключ доступа; целое число d – секретный ключ.

Алгоритм шифрования сообщения P

· Разбиваем исходный текст на блоки P₁, P₂, …, P_m

· Шифруем текст сообщения в виде последовательности блоков

C_j= P_j^е mod n(j =1,n)

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

Чтобы расшифровать эти данные, используя секретный ключ (d,n), необходимо выполнить следующие вычисления: P_j= C_j^d mod n (j =1,n) В результате будет получено множество чисел P(j), которые представляют собой исходный текст.

В RSA p и q должны быть по крайней мере 512 битов; n должны быть по крайней мере 1024 бит.

Пример 3

Боб выбирает 7 и 11 как p и q и вычисляет . Значение или 60. Теперь он выбирает два ключа, e и d, из Z₆₀^*. Если он выбирает e = 13, то d = 37. Обратите внимание, что (они инверсны друг другу). Теперь предположим, что Алиса хочет передать исходный текст 5 Бобу. Она использует общедоступный ключ 13, чтобы зашифровать 5.

Исходный текст:5        

C = 5¹³ = 26 mod 77     

Зашифрованный текст: 26

Боб получает зашифрованный текст 26 и использует секретный ключ 37, чтобы расшифровать зашифрованный текст.

Зашифрованный текст: 26

P = от 26³⁷ до 5 mod 77

Исходный текст 5

Переданный Алисой текст получен Бобом как исходный текст 5.

Пример 4

Теперь предположим, что другой человек, Джон, хочет передать сообщение Бобу. Джон может использовать открытый ключ доступа, объявленный Бобом (вероятно, на его сайте), – 13; исходный текст Джона – 63. Джон делает следующие вычисления:

Исходный текст: 63

C = 63¹³ = 28 mod 77

Зашифрованный текст: 28

Боб получает зашифрованный текст 28 и использует свой секретный ключ 37, чтобы расшифровать зашифрованный текст.

Зашифрованный текст: 28

P = 28³⁷ = 63 mod 77

Исходный текст: 63

Пример 5

Дженнифер создает пару ключей для себя. Она выбирает p = 397 и q = 401. Она вычисляет . Затем она вычисляет . Затем она выбирает e = 343 и d = 12007. Покажите, как Тэд может передать сообщение «No» Дженнифер, если он знает e и n.

Решение

Предположим, что Тэд хочет передать сообщение «No» Дженнифер. Он изменяет каждый символ на число (от 00 до 25), сопоставляет каждой букве число, содержащее две цифры. Затем он связывает два кодированных символа и получает четырехзначное число. Исходный текст – 1314. Затем Тэд использует e и n, чтобы зашифровать сообщение. Зашифрованный текст 1314³⁴³ = 33677 mod 159197. Дженнифер получает сообщение 33677 и использует d ключ дешифрования, чтобы расшифровать это сообщение: 33677¹²⁰⁰⁷ = 1314 mod 159197. Затем Дженнифер расшифровывает 1314 как сообщение «No». Рисунок 14.7 показывает этот процесс.

 

Рис. 6 Шифрование и дешифрование в примере 5

 

Атаки RSA

 

До настоящего момента не было обнаружено никаких разрушительных атак RSА. Несколько атак были предсказаны. Они основаны на слабом исходном тексте, слабом выборе параметра или несоответствующей реализации. Рис.7 http://www.intuit.ru/department/security/mathcryptet/14/4.html - image.14.8 показывает категории потенциальных атак.

 

Рис. 7 Диаграмма возможных атак на RSA

· Атака разложения на множители

Безопасность RSА базируется на следующей идее: модуль настолько большой, что разложение на множители в разумное время неосуществимо. Боб выбирает p и q и вычисляет . Число n общедоступно, p и q являются секретными. Если Ева сможет разложить на множители n и получить p и q, то она может вычислить . Затем Ева тогда может вычислить , потому что e общедоступен. Секретный ключ d – лазейка, которую Ева может использовать, чтобы расшифровать зашифрованное сообщение.

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

· Атака с выборкой зашифрованного текста

Потенциальная атака RSА базируется на мультипликативном свойстве RSA. Предположим, Алиса создает зашифрованный текст C = P^e mod n и передает C Бобу. Также предположим, что Боб расшифрует произвольный зашифрованный текст для Евы – С₁, отличный от C. Ева перехватывает C и использует следующие шаги, чтобы найти P:

а. Ева выбирает случайное целое число X в Z_n*.

б. Ева вычисляет .

в. Ева передает Y Бобу для дешифрования и получает Z = Y^d mod n; это шаг атаки выборкой зашифрованного текста.

г. Ева может легко найти P, потому что

Z = Y^d mod n = (C × X^e)^d mod n = (C^d × X^ed) mod n = (C^d × X) mod n = (P × X) mod n

Z = (P × X) mod n  P=Z × X^-1 mod n

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

· Атаки на показатель степени шифрования

Чтобы уменьшить время шифрования, можно попытаться использовать короткий ключ шифрования – малое значение числа e, например, значение для e, такое как e = 3 (второе простое число). Однако есть некоторые потенциальные атаки на показатель при его малом значении степени шифрования, которые мы здесь кратко обсуждаем. Эти атаки вообще не кончаются вскрытием системы, но они все-таки должны быть предотвращены. Для того чтобы сорвать эти виды атак, рекомендуется использовать e = 2¹⁶ + 1 = 65537 (или простое число, близкое к этому значению).

· Атака теоремы Куперcмита (Coppersmith) может быть главной для атаки малого показателя степени на ключ шифрования. Основное положение этой теоремы: для полинома f(x) степени e по модулю n, чтобы найти корни, если один из корней является меньшим чем n^1/e, можно использовать алгоритм сложности, log n. Эта теорема может быть применена к RSA-криптосистеме C = f(P) = P^e mod n. Если e = 3 и известны хотя бы две трети битов в исходном тексте P, алгоритм может найти все биты в исходном тексте.

· Атака широковещательной передачи может быть начата, если один объект передает одно и то же сообщение группе получателей с тем же самым ключом шифрования. Например, предположим следующий сценарий: Алиса хочет передать одно и то же сообщение трем получателям с тем же самым общедоступным ключом e = 3 и модулями n₁, n₂ и n₃.

C₁ = P³ mod n₁    

C₂ = P³ mod n₂    

C₃ = P³ mod n₃

Применяя китайскую теорему об остатках к этим трем уравнениям, Ева может найти уравнение формы C’ = P³ mod n₁n₂n₃. Это означает, что P³ < n₁n₂n₃ и что C’ = P³ решается с помощью обычной арифметики (не модульной). Ева может найти значение C’ = P^1/3.

· Атака связанных между собой сообщений была обнаружена Франклином Рейтером (Franklin Reiter). Она может быть кратко описана следующим образом. Алиса зашифровала два исходных текста, P₁ и P₂, с помощью e = 3 и передает C₁ и C₂ Бобу. Если P₁ связан с P₂ линейной функцией, то Ева может восстановить P₁ и P₂ в выполнимое время вычисления.

· Атака короткого списка, обнаруженная Куперсмитом, может быть кратко описана следующим образом. Алиса имеет сообщение М для передачи Бобу. Она записывает сообщение и зашифровывает его как сообщение r₁, а результат записывает как C₁ и передает C₁ (Бобу). Ева перехватывает C₁ и удаляет его. Боб сообщает Алисе, что он не получил сообщение, так что Алиса заполняет сообщение, снова зашифровывает как сообщение r₂ и передает это Бобу. Ева также перехватывает и это сообщение. Ева теперь имеет C₁ и C₂, и она знает, что оба зашифрованных текста принадлежат одному и тому же исходному тексту. Куперсмит доказал, что если r₁ и r₂ короткие, то Ева способна восстановить первоначальное сообщение М.

· Атаки показателя степени дешифрации

Две формы атак могут быть проведены на показатель степени дешифрации: атака раскрытой степени дешифрации и атака малого показателя степени дешифровации. Они обсуждаются ниже.

· Атака раскрытого показателя степени дешифрации. Очевидно, что если Ева может найти показатель степени дешифрации, d, она сможет расшифровать текущее зашифрованное сообщение. Однако на этом атака не останавливается. Если Ева знает значение d, она может использовать вероятностный алгоритм (не обсуждаемый здесь) к числу n и найти значения p и q. Следовательно, если Боб изменит только угрожающий безопасности показатель степени дешифрования, но сохранит тот же самый модуль n, Ева сможет расшифровать будущие сообщения, потому что она сможет разложить на множители n. Поэтому если Боб узнает, что показатель степени скомпрометирован, он должен выбрать новое значение для p и q, вычислить n и создать полностью новые секретный и открытый ключи доступа.

В RSA, если показатель степени d скомпрометирован, тогда p, q, n, e и d должны быть сгенерированы заново.

· Атака малого значения показателя степени дешифрации. Боб может подумать, что использование малого значения степени секретного ключа d приводит к более быстрой работе алгоритма дешифрации. Винер показал, что в случае d < 1/3n^1/4 возможен специальный тип атаки, основанной на цепной дроби, – тема, которая рассматривается в теории чисел. Этот тип атаки может подвергнуть риску безопасность RSА. Для того чтобы это произошло, должно выполняться условие, что q < p < 2q; если эти два условия существуют, Ева может разложить n на сомножители в полиномиальное время.

В RSA рекомендовано, что d должно иметь величину d > 1/3 n^1/4, чтобы предотвратить атаку малого значения ключа дешифрации.

· Атаки исходного текста

Исходный текст и зашифрованный текст в RSA – это перестановки друг друга, потому что это целые числа в том же самом интервале (от 0 до n – 1). Другими словами, Ева уже знает кое-что об исходном тексте. Эти характеристики могут позволить некоторые атаки исходного текста. Три атаки были уже упомянуты в литературе: атака короткого сообщения, атака циклического повторения и явная атака.

· Атака короткого сообщения. В атаке короткого сообщения, если Ева знает множество возможных исходных текстов, то ей известна еще одна информация и дополнительный факт, что зашифрованный текст – перестановка исходного текста. Ева может зашифровать все возможные сообщения, пока результат не будет совпадать с перехваченным зашифрованным текстом. Например, если известно, что Алиса посылает число с четырьмя цифрами Бобу, Ева может легко испытать числа исходного текста 0000 к 9999, чтобы найти исходный текст. По этой причине короткие сообщения должны быть дополнены случайными битами в начале и конце, чтобы сорвать этот тип атаки. Настоятельно рекомендуется заполнять исходный текст случайными битами прежде начала шифрования. Здесь используется метод, называемый OAEP, который будет позже обсужден в этой лекции.

· Атака циклического повторения построена на факте, что если переставлять зашифрованный текст (перестановка исходного текста), то непрерывное шифрование зашифрованного текста в конечном счете кончится исходным текстом. Другими словами, если Ева непрерывно шифрует перехваченный зашифрованный текст C, она в итоге получит исходный текст. Однако сама Ева не знает, каков исходный текст, так что ей неизвестно, когда пора остановиться. Она должна пройти один шаг далее. Когда она получает зашифрованный текст C снова, она возвращается на один шаг, чтобы найти исходный текст.

Перехваченный зашифрованный текст C

C₁ = C^e mod n

C₂ = C₁^e mod n

………………

C_k = C_k-1^e mod n , если C_k = C, останов: исходный текст - P = C_k-1

Может ли это быть серьезной атакой на криптосистему RSA? Показано, что сложность алгоритма эквивалентна сложности разложения на множители n. Другими словами, нет никакого эффективного алгоритма, который может завершить эту атаку в полиномиальное время, если n является большим.

· Явная атака сообщения. Другая атака, которая базируется на отношениях перестановки между исходным текстом и зашифрованным текстом, – явная атака сообщения. Явное сообщение – сообщение, которое зашифровано само в себя (не может быть скрыто). Было доказано, что есть всегда некоторые сообщения, которые шифруются сами в себя. Поскольку ключ шифрования обычно нечетен, имеются некоторые исходные тексты, которые зашифрованы сами в себя, такие как P = 0 и P = 1. Но если ключ шифровки выбран тщательно, число их незначительно. Программа шифровки может всегда проверить, является ли вычисленный зашифрованный текст таким же, как исходный текст, и отклонить исходный текст перед передачей зашифрованного текста.

· Атаки модуля

Главной атакой RSA является атака разложения на множители. Ее можно рассматривать как атаку малого модуля. Однако поскольку мы уже обсудили эту атаку, мы концентрируемся на другой атаке модуля: общей атаке модуля.

· Общая атака модуля. Она может быть начата, если сообщество использует общий модуль, n. Например, люди в сообществе могли бы позволить третьей стороне, которой они доверяют, выбирать p и q, вычислять n и и создать пару образцов (e_i, d_i) для каждого объекта. Теперь предположим, что Алиса должна передать сообщение Бобу. Зашифрованный текст Бобу – это Боб использует свой секретный ключ, d_B, чтобы расшифровывать сообщение: . Проблема в том, что Ева может также расшифровать сообщение, если она – член сообщества и ей была назначена пара образцов (e_E и d_E), как мы узнали в разделе «атака малого значения ключа дешифрации». Используя свои собственные ключи (e_E и d_E), Ева может начать вероятностную атаку на сомножители n и найти d_B Боба. Чтобы сорвать этот тип атаки, модуль не должен быть в совместном пользовании. Каждый объект должен вычислить свой собственный модуль.

· Атаки реализации

Предыдущие атаки базировались на основной структуре RSА. Как показал Дэн Бонех (Dan Boneh), есть несколько атак реализации RSА. Мы приведем две из них: атака анализом времени и атака мощности.

· Атака анализом времени (Timing attack). Пауль Кочер (Paul Kocher) демонстрировал атаку только зашифрованного текста, называемую атака анализом времени. Атака основана на быстром алгоритме с показательным временем. Использует только возведение во вторую степень, если соответствующий бит в секретном показателе степени d есть 0; он используется и при возведении во вторую степень и умножении, если соответствующий бит – 1. Другими словами, синхронизация требует сделать каждую итерацию более длинной, если соответствующий бит – 1. Эта разность синхронизации позволяет Еве находить значение битов в d, один за другим.

Есть два метода сорвать атаку анализом времени:

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

2. Ривест рекомендовал «ослепление». По этой идее зашифрованный текст умножается на случайное число перед дешифрованием. Процедура содержит следующие шаги:

a. Выбрать секретное случайное число r между 1 и (n – 1).

b. Вычислить .

c. Вычислить P₁ = C₁^d mod n.

d. Вычислить .

· Атака анализом мощности подобна атаке анализом времени. Было показано, что если Ева может точно измерить мощность, использованную в течение дешифрования, она может начать атаку анализа мощности на основании принципов, рассмотренных для атаки анализом времени. Итеративное умножение и возведение в квадрат потребляют больше мощности, чем только итеративное возведение в квадрат. Та же самая группа методов, которая предотвращает атаки анализом времени, может сорвать атаки анализа мощности.

 

Рекомендации для RSA

 

Следующие рекомендации основаны на теоретических и экспериментальных результатах.

1. Число битов для n должно быть, по крайней мере, 1024. Это означает, что n должно быть приблизительно 2¹⁰²⁴, или 309 десятичных цифр.

2. Два простых числа p и q должны каждый быть по крайней мере 512 битов. Это означает, что p и q должны быть приблизительно 2⁵¹² или 154 десятичными цифрами.

3. Значения p и q не должен быть очень близки друг к другу.

4. p – 1 и q – 1 должны иметь по крайней мере один большой простой сомножитель.

5. Отношение p/q не должно быть близко к рациональному числу с маленьким числителем или знаменателем.

6. Модуль n не должен использоваться совместно.

7. Значение e должно быть 2¹⁶ + 1 или целым числом, близким к этому значению.

8. Если произошла утечка частного ключа d, Боб должен немедленно изменить n так же, как e и d. Было доказано, что знание n и одной пары (e, d) может привести к открытию других пар того же самого модуля.

9. Сообщения должны быть дополнены, используя OAEP, который рассматривается далее.