Шифр RSA. 
Криптографические методы защиты информации

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

Шифр Эль-Гамаля позволяет решить ту же задачу за одну пересылку данных, но объем передаваемого шифротекста в два раза превышает объем сообщения.

Система RSA лишена подобных недостатков. Шифр предложен в 1977 г. Р. Ривестом (Ron Rivest), А. Шамиром (Adi Shamir) и Л. Адлеманом (Leonard Adleman) и назван по именам своих создателей. RSA — это алгоритм асимметричного шифрования и цифровой подписи. До сих пор RSA является одной из самых распространенных систем асимметричной криптографии.

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

• 1) задача проверки чисел на простоту является сравнительно легкой;
• 2) задача разложения чисел вида N = pq_y р и q — простые числа, на множители (факторизация) является трудной вычислительной задачей, если известно только N> а р и q — большие числа.

Пусть в системе имеются абоненты Д В, С,… Каждый абонент вырабатывает свою пару ключей (личный и открытый ключ). Для этого он случайным образом генерирует два больших простых числа р и q и вычисляет произведение N = pq.

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

Затем абонент вырабатывает случайное число е, взаимно простое со значением функции Эйлера (р(N) от числа N: ср (АГ) = (/? — 1) • (q — 1), и находит число d из условия е • d = 1 [mod (p (iV)], т. е. d является числом, обратным е по модулю (р (А/):

Поскольку е и (р (Л^{, г}) взаимно просты — I ЮД (е, tp (A^r)) = 1, то такое число d существует и оно единственно. Значение числа d может быть найдено с помощью расширенного алгоритма Евклида.

Пара (N, е) объявляется открытым ключом абонента и публикуется открыто. Значение d является личным ключом абонента и держится им в секрете. Для расшифрования достаточно знать секретный ключ. Числа р, q, ф (Л^{, г}) в дальнейшем не нужны, поэтому их можно уничтожить.

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

Рис. 3.6. Справочник открытых ключей абонентов системы RSA.

Пусть абонент, А хочет передать секретное сообщение М абоненту В. Сообщение М, как и в предыдущих системах с открытым ключом, рассматривается как число, причем М удовлетворяет неравенству М < N_B (в противном случае оно делится на части). Протокол RSA состоит в следующем:

1) отправитель Л выбирает из открытого справочника пару (JV_B, е_и) абонента В (далее индекс В у величин е, d и N будем опускать). Абонент, А вычисляет значение криптограммы и передает его абоненту В:

2) чтобы получить исходный текст, абонент В вычисляет Покажем, что М' = М.

Поскольку е? d = 1 [mod ср (ЛГ)], т. е. е? d = ср (А')? k + 1, где k — целое число, то, применяя приведенную ранее теорему (x^k<9(N)*¹ mod N = х, N = pq, pnq — простые), получим.

Пример 3.23.

Пусть абонент В выбрал простые числа р = 7, q = 17. Тогда N = 1 ? 17 = 119, ф(N) = 6 • 16 = 96. Он также должен выбрать значение е: е < 96, ПОД (е, 96) = 1. Пусть он выбрал е = 5. Теперь абонент находит секретный ключ d с помощью расширенного алгоритма Евклида: d = е ¹ mod ф (Л0. d = 77.

Открытый ключ абонента В — 119,5, личный ключ абонента В — 77. Пусть абонент, А хочет послать ему сообщение М= 19, зашифрованное RSA Для зашифрования абонент, А вычисляет С = М' mod N = 19^Г‘ mod 119 = 66. Получив криптограмму 66, абонент В расшифровывает се своим личным ключом: М = С mod N = = 66⁷⁷ mod 119 = 19.

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

Для противника вычисление значения М на основе перехваченного шифротекста С без знания секретного ключа d является практически невыполнимым (ввиду сложности задачи дискретного логарифмирования). Вычисление же d на основе открытого ключа также практически неосуществимо, так как для этого надо вычислить ф (Л/), что можно сделать, если знать/; и q, а значит, надо решить трудную задачу факторизации большого числа N.

Рассмотренная система обладает практической стойкостью при больших р и q (порядка 512 бит и выше), однако допускает мошенничество следующего вида: поскольку в шифре используются только ключи получателя В, то противник, хотя и не может читать сообщения абонента, А к В, но сможет отправить В свое сообщение от лица, А Избежать этого можно, используя более сложные протоколы, например следующий (рис. 3.7):

• 1) сначала, А вычисляет число F = М'^/Л mod N_A. Злоумышленник не может этого сделать, поскольку не знает d_A — личного ключа А;
• 2) затем, А вычисляет С = F^eli modN_B. А передает С абоненту В;
• 3) В получает С и вычисляет последовательно числа F = С^<�т mod N_B wM' = F^f eA mod ЛГд.

Здесь В знает, что сообщение пришло от, А поскольку, А «подписал» его, зашифровав своим секретным ключом. Это пример использования ЭЦП.

Рис. 3.7. Обеспечение секретности и аутентичности в системе RSA

Выбор параметров и безопасность RSA Для безопасности схемы RSA важно, чтобы каждый абонент выбирал собственную пару простых чисел р и q, т. е. все модули N_A, jV_b, N_c,… были различны. В противном случае один абонент смог бы читать сообщения, предназначенные для другого (поскольку смог бы вычислить чужой личный ключ, зная разложение числа N на множители р и q и, как следствие, значение cp(N)). Кроме того, в случае пересылки пользователям с одинаковыми модулями одного и того же сообщения противник сможет прочитать это сообщение с помощью атаки на алгоритм RSA методом бесключевого чтения.

Небезопасная ситуация может сложиться, когда несколько абонентов пользуются одинаковым открытым ключом е. Тогда в случае пересылки этим пользователям одного и того же сообщения становится возможной атака на основе китайской теоремы об остатках. Кроме того, нежелателен выбор малых значений экспонент е и d (хотя это и позволяет ускорить выполнение шифрования или расшифрования соответственно). Так, сущест;

вует эффективный способ вычисления значения d в случае, если d<�—y[N,

о

предложенный М. Винером (Michael J. Wiener). Атака Винера была обобщена на случай d < N^0,292. Поэтому для 1024-битного RSA значение d должно иметь длину порядка 300 бит и более.

Если же малым является параметр е, то достаточно большое число открытых сообщений, удовлетворяющих неравенству М будут зашифровываться простым возведением в степень С = М^е < N, и поэтому их можно найти путем извлечения корня степени е из С.

Выбор параметров во многом определяет криптостойкость системы RSA Чтобы исключить возможность применения методов факторизации, накладывают следующие ограничения^[1] на р и q:

• числа р — 1, р + 1, q — 1, <7 + 1 не должны разлагаться в произведение малых простых множителей и должны содержать в качестве сомножителя хотя бы одно большое простое число;

• числа должны быть простыми, причем р_{ — 1 и q_{ — 1 не должны разлагаться в произведение малых простых множителей;

• • числа р и q не должны содержаться в списках известных больших простых чисел. Например, выбор в качестве модуля числа N = 536 813 567 неудачен, так как оно является произведением простого числа Мерсенна 8191 и простого числа Ферма 65 537;
• • значения р и q не должны быть близкими, так как иначе можно воспользоваться для факторизации N методом Ферма.

При перемножении двух чисел длина результата примерно равна сумме длин сомножителей. Поэтому для получения 1024-битного числа Апеобходимо выбрать р и q длиной 512 бит. Чтобы получить результат длиной 1024 бита, можно также перемножить, например, числа длиной 612 и 412 бит.

Безопасность алгоритма RSA основана на трудоемкости разложения на множители (факторизации) больших чисел. К началу 2010 г. с помощью метода решета числового поля удалось факторизовать 768-битное число^[2]. Следовательно, разрядность N = pq должна быть больше. 64-битному ключу симметричного шифрования примерно соответствует 512-битный ключ RSA, а 128-битному — ключ RSA длиной более 2300 бит. В настоящее время система шифрования на основе RSA с модулем, А размером 1024 бит находится на грани потери надежности^[3]. На практике предпочтительно применение более безопасного 2048;битового RSA хотя это и снижает производительность криптосистемы.

Следует также отметить, что реализации системы RSA подвержены атакам, использующим утечки по побочным каналам^[4].

Атаки на алгоритм RSA при неудачном выборе параметров. Метод бесключевого чтения. Метод бесключевого чтения применим, когда пользователи используют один и тот же модуль А. Пусть два пользователя выбрали одинаковый модуль N и разные (взаимно простые) экспоненты е_х и е₂. Если им будет послано одинаковое сообщение М, криптоаналитик сможет определить эго сообщение.

Криптоаналитик перехватит два зашифрованных текста: С, = М^еЛ mod N, С₂ = М⁽'² mod N. Затем, используя расширенный алгоритм Евклида, криптоаналитик может получить г и s такие, что ге_{ + sе₂ = 1. Зная г и 5, он сможет получить исходное сообщение: С[ • С₂ mod N = М^{геЛ +se2} mod N= М¹ mod N = М.

Пример 3.24.

Пусть пользователи применяют общий модуль N= 137 759, но разные взаимно простые экспоненты е_х = 191 и е₂ = 233. Пусть пользователям направлены криптограммы С, = 60 197 и С₂ = 63 656 соответственно, которые содержат одно и то же открытое сообщение М. Поскольку е_х и е₂ — взаимно просты, всегда найдутся числа г и s, такие, что г • е_х + s • е₂ = 1.

Найдем г и s с помощью расширенного алгоритма Евклида (рис. 3.8): вычисляем U <�— {тах^, е₂), 1, 0}, V <�— {пйп (^₁, е₂), 0, 1}, k = и_л div v_v Т ?*— {и_{ mod v_v u₂-kv₂, щ — к • Вычисления продолжаются, пока ?, не станет равным нулю.

Рис. 3.8. Вычисление чисел г, s с помощью расширенного алгоритма Евклида С помощью расширенного алгоритма Евклида найдено: г = 61, s = -50; проверка: 61 • 191 — 50 • 233 = 11 651 — И 650 = 1.

Получим исходное сообщение:

= 1234.

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

Пусть, например, три корреспондента имеют попарно взаимно простые модули N_v N₂> N₃ и общую экспоненту е = 3. Если им послано одно и то же сообщение х, криптоаналитик сможет его определить.

Криптоаналитик перехватит три зашифрованных текста C_v C_v С₃, C_i = = М³ mod Nj, г = 1,2,3. Далее он может найти решение С системы сравнений, лежащее в интервале от 0 до • iV₂ • N₃: 0 < С < N_{ • N₂ • N₃:

Согласно китайской теореме об остатках такое решение С единственно, а так как С³ < JV, • N₂ • JV₃, то С = М Значение М можно найти, вычислив кубический корень М = у/С.

Пример 3.25.

Пусть три пользователя имеют модули ЛГ, = 26 549, N₂ = 45 901, N₃ = 25 351. Все пользователи используют экспоненту е = 3. Всем пользователям было послано одинаковое открытое сообщение М, причем пользователи получили криптограммы С, = 5366, С₂ = 814, С₃ = 4454. Найдем Y=N_rN,-N₃ = 30 893 378 827 799. Далее находим:

с помощью расширенного алгоритма Евклида можно найти:

— исходное сообщение, отправленное пользователям.

Атака методом Ферма. Метод Ферма для криптоанализа RSA применим в том случае, если параметры р и q оказались достаточно близкими друг к другу.

Пусть р > q> тогда имеем . Обозначим:

. Поскольку s мало, то t — целое число, лишь немногим большее VN,.

причем t^[5] — N является полным квадратом (т.е.  — целое число).

Для нахождения значения t сначала следует вычислить , затем следует проверять подряд целые числа t- > Vw, пока не окажется целым числом. Если для некоторого значения г = k оказалось v_k — целое, то t = t_ky v = v_k и задача факторизации числа N решена: p = t + v_yq = t-v.

При известных р и q можно оценить стойкость выбранных параметров к атаке методом Ферма. Оценить количество попыток k, необходимых для факторизации N методом Ферма, можно, но формуле.

где [х] — операция округления х до ближайшего целого^[5].

Пример 3.26.

Пусть абонент системы RSA выбрал значение N = 7571. Применим метол Ферма для факторизации N.

Вычислим . Округлим результат вверх до ближайшего целого:

Г, = 88, t — N = 88² — 7571 = 7744 — 7571 = 173,  — не является целым, значит, потребуется опробовать еще одно значение ?, = ?, + 1.

1₂ = 88 + 1 = 89, t₂ — N = 350, v₂ ~ 18,71 — не является целым, следовательно, опробуем t₃ = t₂ + 1.

г₃ = 89 + 1 = 90, t — N = 529, у, = 23 — целое,.

t = t₃ = 90, v = v₃ = 23, р = t + v = 113, q = t — v = 67.

Проверка: pq = 113−67 = 7571 = N.

• [1] Жданов О. Я, Лубкин И. А. Алгоритм RSA: метод, указания к выполнению лабораторных работ для студ. спец. 90 105. Красноярск: Сибирский государственный аэрокосмический университет, 2007.
• [2] Factorization of a 768-bit RSA modulus. V. 1.4, February 18,2010. URL: http://eprint.iacr.org/2010/006.pdf
• [3] Там же; К вопросу о безопасности 1024-битной версии RSA и 160-битной криптографиина эллиптических кривых. URL: https://www.pgpru.com/biblioteka/statji/stojjkostjrsal024
• [4] Genkin D., Shamir A., Tromer E. RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis. December 18, 2013. URL: http://www.tau.ac.il/~tromer/papers/acoustic-20 131 218.pdf
• [5] Жданов О. Я., Лубкин И. А. Алгоритм RSA: метод, указания к выполнению лабораторных работ для студ. спец. 90 105.
• [6] Жданов О. Я., Лубкин И. А. Алгоритм RSA: метод, указания к выполнению лабораторных работ для студ. спец. 90 105.