Практическое использование алгоритма RSA

 

Для алгоритмов, основанных на открытых ключах, существует ряд математических проблем, которые не всегда учитываются при построении криптосистемы. К ним можно отнести выбор начальных значений, на основе которых создаются ключи. Есть определенные числа, позволяющие очень быстро вычислить секретный ключ. В то же время правильный выбор начальных значений позволяет гарантировать невозможность вскрытия методом «грубой силы» в течение нескольких сотен лет при современном развитии вычислительной техники.

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

,

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

Поэтому первый вопрос, который необходимо обсудить, это выбор размера модуля n.

Определение. Размер параметра – количество битов в его двоичном представлении.

Учитывая последние достижения в области факторизации целых чисел, модуль n размером 512 бит обеспечивает лишь минимальную защиту от коллективной атаки. Так в 1996 году было рекомендовано выбирать модуль размером 768 бит, чтобы противостоять методам квадратичного просеивания и решета числового поля. Для долгосрочной защиты размер модуля должен быть 1024 или более бит.

Следующим важным моментом практического применения предлагаемого алгоритма является выбор параметров p и q.

Среди наиболее известных недостатков алгоритма RSA можно выделить некорректный выбор значений p и q. Основные требования к этим параметрам заключаются в следующем.

Во-первых, числа p и q должны быть простыми и не содержаться ни в одной из известных таблиц простых чисел. При факторизации можно всегда проверить всю таблицу или перебрать последовательность простых чисел специфического вида (например, числа Мерсенна или Ферма).

Во-вторых, p и q не должны быть близкими друг к другу. В противном случае можно воспользоваться методом факторизации Ферма. В целом рекомендуется, чтобы двоичное представление p и q различалось по длине на несколько битов.

В-третьих, при выборе p и q также должно быть рассмотрено и значение j. Оба числа p – 1 и q – 1 четны, из чего следует, что j делится на 4. Как известно, справедливо соотношение

,

где НОК – наименьшее общее кратное чисел, указанных в качестве аргументов. Поэтому, если НОД(p – 1, q – 1) окажется большим, то l = НОК(p‑1, q‑1) мало (ударение на букву о) по сравнению с j. Для нахождения экспоненты расшифрования d достаточно решить сравнение

вместо сравнения

.

В этом случае появляется возможность найти d простой проверкой, поэтому НОД(p – 1, q – 1) не должен быть большим. Вырожденным является случай, когда одно из p – 1 или q – 1 делит другое. В наилучшем случае НОД(p‑1,q‑1) = 2.

Необходимо также избегать ситуации, когда j раскладывается в произведение только малых простых сомножителей.

В-четвертых, чтобы исключить возможность применения (p – 1)- и (p + 1)-методов факторизации, рекомендуется выбирать в качестве p и q сильные простые числа. Эти два метода эффективны только если n имеет простой множитель p такой, что p – 1 или p + 1 раскладываются в произведение только малых простых сомножителей.

Определение. Простое число p называется сильным простым числом (strong prime), если выполнены следующие три условия:

1. p – 1 имеет большой простой множитель r;

2. p + 1 имеет большой простой множитель;

3. r – 1 имеет большой простой множитель.

Условие 1 этого определения предназначено для того, чтобы противостоять методу p – 1 Полларда. Условие 2 необходимо, чтобы противостоять методу p + 1 Вильямса. И, наконец, условие 3 необходимо, чтобы противостоять циклической атаке которая будет рассмотрена позднее.

Следует заметить, что в русскоязычной литературе нет общепринятой терминологии обозначающей английский термин strong prime. Например, используются следующие эквивалентные термины: строго простое число, сильно простое число, сильное простое число.

Если число p (аналогичные рассуждения справедливы и для q) выбрано случайно и подходящего по величине размера, то можно ожидать, что p – 1 и p + 1 имеют большие простые множители. В любом случае сильные простые числа защищают только от методов p – 1 и p + 1, но они не могут противостоять методу эллиптических кривых.

В дополнение к этому было показано, что вероятность успеха циклической атаки незначительна, если p и q выбраны случайно. Таким образом, сильные простые числа обеспечивают лишь незначительное увеличение стойкости алгоритма по сравнению с обычными простыми числами. Поэтому, учитывая современный уровень развития методов факторизации целых чисел, нет необходимости требовать обязательного выбора в качестве p и q сильных простых чисел. С другой стороны сильные простые числа обеспечивают, по крайней мере, не меньшую безопасность, чем обычные простые числа и требуют незначительного увеличения вычислений для своей генерации.

Наиболее сильное требование к p и q, сформулированное Райвестом (Rivest) в 1978 г., заключается в том, чтобы числа

, , ,

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

Следует заметить, что для алгоритма RSA характерно наличие так называемых нешифруемых сообщений, то есть таких m, для которых выполняется сравнение , где e – показатель зашифрования. Например, a = 0, a = 1 и a = n – 1 всегда являются нешифруемыми сообщениями. Точное количество нешифруемых сообщений равно

.

Учитывая, что e – 1, p – 1 и q – 1 всегда четны, то количество нешифруемых сообщений, по крайней мере, не меньше 9.

Одной из основных проблем, возникающих при использовании асимметричных алгоритмов, является низкая скорость проведения операций зашифрования/расшифрования по сравнению с симметричными алгоритмами. В частности алгоритм RSA, работает примерно в 1000 раз медленнее по сравнению с DES (Data Encryption Standard), который, в свою очередь, является далеко не самым быстрым из используемых в настоящее время симметричных алгоритмов. Один из способов решения проблемы – уменьшение размерности параметров системы, но это чревато уменьшением стойкости алгоритма.

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

Однако, выбор малых параметров e и d представляется небезопасным по ряду соображений.

Если значение e выбрано случайно, то процесс зашифрования с использованием бинарного алгоритма требует примерно N модульных возведений в квадрат и N/2 модульных умножений, где N – размер модуля n. Скорость зашифрования может быть увеличена за счет выбора малого показателя e и/или выбора такого значения e, чтобы его двоичное представление содержит малое количество единиц.

В связи с этим, на практике, часто используют значение e = 3. В этом случае необходимо, чтобы p – 1 и q – 1 не делились на 3. В результате получается очень быстрое зашифрование, так как для этого требуется только одно модульное возведение в квадрат и одно модульное умножение. Однако такой выбор позволяет провести следующую атаку.

Пусть несколько абонентов используют одно и то же значение e, но каждый из них имеет собственный уникальный модуль. Если абонент A отправляет одно и то же сообщение m трем другим абонентам, чьи открытые модули есть , и , то соответствующие шифротексты равны , где i = 1, 2, 3. Если эти модули окажутся попарно взаимно простыми (а скорее всего так и будет), то злоумышленник, перехватив , и может восстановить открытый текст m (детальное описание данной процедуры выходит за рамки лекционного курса).

Таким образом, малый показатель зашифрования, например, e = 3, не может использоваться, если одно и то же сообщение (или, даже одно и то же сообщение с известными модификациями) отправляется нескольким абонентам.

Малый показатель e нельзя использовать для шифрования малых сообщений m, так как если , то m может быть вычислено из шифротекста просто нахождением целого значения корня степени e из c.

Другим часто используемым значением является . Это число имеет только две единицы в своем двоичном представлении и процесс зашифрования потребует 16 модульных возведений в квадрат и 1 модульное умножение. Показатель имеет преимущество по сравнению с e = 3, так как маловероятно, что одно и то же сообщение будет отправлено абонентам.

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

Во-первых, при очень малых значениях секретного параметра d, например , его можно определить простым перебором.

Во-вторых, если значение мало, что обычно и бывает, и если размер d не больше четверти размера n, то существует эффективный алгоритм вычисления d из открытых данных (n, e). Этот алгоритм не может быть расширен на случай, когда d имеет примерно такой же размер, как и n. Таким образом, чтобы защититься от этой атаки необходимо, чтобы d и n были примерно одного размера.

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

Теорема. Пусть два абонента A и B используют алгоритм RSA для защищенного обмена сообщениями. Пусть – открытый ключ абонента A; – секретный ключ абонента A; – открытый ключ абонента B; – секретный ключ абонента B. То есть A и B используют общий модуль n, но у каждого имеются свои уникальные показатели за- и расшифрования. Тогда каждый из них в состоянии детерминированно найти секретный показатель расшифрования другого абонента за квадратичное время (без факторизации n).

Необходимо указать на еще одно свойство алгоритма RSA, касающееся использования общего модуля несколькими пользователями. Пусть абоненты A и B используют общий модуль n, – показатель зашифрования абонента A, – показатель зашифрования абонента B. Если , то можно осуществить бесключевое чтение сообщения m, зашифрованного на этих ключах. Действительно, пусть

, .

Тогда, используя расширенный алгоритм Евклида, можно найти целые числа x и y такие, что , а затем вычислить

.

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

Пусть m – открытый текст, c – шифротекст, e – показатель зашифрования, n – модуль. Тогда

.

Злоумышленник может последовательно вычислять

, , ,

пока, при некотором целом положительном k, не выполнится соотношение

.

Такое k всегда существует, так как зашифрование является подстановкой на множестве . Тогда

.