Компьютерная безопасность. Криптографические методы защиты - Петров А.А.
ISBN 5-89818-064-8
Скачать (прямая ссылка):
В настоящем разделе рассматриваются основные атаки на алгоритм RSA, известные на сегодняшний день. Следует отметить, что стойкость RSA может быть снижена за счет некорректного выбора параметров алгоритма.
Среди наиболее известных недостатков алгоритма RSA можно выделить некорректный выбор значений р и q. Числа р и q должны быть простыми и не содержаться ни в одной из известных таблиц простых чисел. Эти числа также не должны быть близкими друг к другу. Если (р - q)/2 мало и (р + q)/2 немного больше, чем Vn , то при (р + q)2/4 - n С (р - q)2/4 левая часть равенства образует полный квадрат. При факторизации п перебираем целые числа на соответствие неравенству х > Vn до тех пор, пока не найдем такое значение, что х2 - n = у2. Тогда p = x + ynq = x-y. Учитывая изложенный факт, а также ряд других атак, основанных на неправильном выборе чисел р и q, сформулируем следующие требования к выбору чисел р и q:
1. Данные числа должны быть большими числами одинаковой длины; например: если n = 1024 бита, то длина р и q должна быть равна 512 битам.
2. Различие между р и q должно быть большим.
3. Числа р и q должны быть строго простыми. Число называется строго простым, если выполнены условия:
а) р - 1 должно иметь большой простой делитель (обозначим его через г);
58
Общие сведения по классической криптографии
б) р + 1 должно иметь большой простой делитель;
в) г - 1 должно иметь большой простой делитель.
Требование а) обусловлено противодействием алгоритмам факторизации п (один из таких алгоритмов был предложен Поллардом). Аналогично обосновывается требование б). Выполнение на практике требования в) позволяет противостоять циклическим атакам.
Циклические атаки
Пусть с = me mod п - зашифрованное сообщение, к - положительное целое, при этом се = с (mod п). Тогда зашифрованием является подстановка на множестве {0,1 ... п-1}, в которой присутствует к, что может привести к ситуации, когда сеЫ = m (mod п). Злоумышленник вычисляет значения се mod n, се mod п и т.д. до тех пор, пока не будет получено значение с. Если се mod n = с, тогда се" = m (mod п). Основой циклической атаки является нахождение такого небольшого положительного целого и, при котором выполняется условие f(u) = НОД (се" - с, n) > 1. Если cc'u= c(mod р) HCeVc (mod q), то f(u) = р. Аналогично, если ceU ^ с (mod р) и cc>u= с (mod q), то f(u) = q. В любом из этих случаев злоумышленник получает разложение п на множители.
При этом существует вероятность возникновения одной из следующих ситуаций:
• если выбрать общий модуль п для каждого участника при различных парах (ei5 d;), появляется потенциальная возможность разложить на множители модуль п (правда, для этого необходимо знать каждую пару (eb dj)). Более того, если одно и то же сообщение отправлено несколькими участниками, злоумышленник, перехватив эти сообщения, может восстановить открытый текст на основе знания общедоступных параметров системы. Учитывая сказанное, при выборе параметров в асимметричных алгоритмах шифрования необходимо, чтобы п создавалось для каждого участника системы отдельно. Кроме того, развитие эффективных алгоритмов факторизации больших целых чисел предъявляет жесткие требования к размеру п; на сегодняшний день минимально рекомендуемая длина п должна быть равна 768 битам;
• при выборе экспонент end тоже могут возникать ситуации, существенно ослабляющие стойкость RSA. При выборе экспоненты е обычно ориентируются на обеспечение приемлемой скорости операций зашифрования/расшифрования, что приводит к выбору малых значений е. Например, рассмотрим случай, когда е = 3 для участников А, В и С (предполагается также, что модули п у каких-либо двух
Асимметричные алгоритмы шифрования
59
участников взаимно просты). В этом случае злоумышленник, перехватив одинаковые сообщения, переданные всем участникам (например, многоадресная доставка), Cj= m° mod п, где i = А, В, С, может вычислить число х = m3mod (nAnBnc). Поскольку m3< nAnBnc, это возможно только в случае, если х = т3. Тогда злоумышленник, вычислив кубический корень, может найти m. С точки зрения достижения приемлемых скоростных параметров и обеспечения должного уровня безопасности имеет смысл выбрать число е = 216 + 1, являющееся числом Ферма и имеющее в битовом представлении всего лишь две единицы. Выбор небольшого числа d также опасно тем, что если НОД (р - 1, q - 1) и d приблизительно равны п/4, то существуют алгоритмы факторизации п на основе знания только открытого ключа. Кроме того, в случае небольшого значения d оно может быть найдено простым перебором всех возможных значений.
Для RSA характерно наличие так называемых пешифруемых блоков открытого сообщения, то есть таких т, для которых выполняется равенство mL> = m (mod п). Например, Tn = O, т=1ит = п-1 всегда являются иешифруемыми блоками сообщения. Необходимым и достаточным условием нешифруемости сообщения является m0"1 = 1 (mod п).
В общем случае под единицей в равенстве следует понимать отдельный элемент группы, к которой принадлежит т. Как видно из приведенного условия нешифруемости, таких блоков сообщения совсем немало. Точное количество пешифруемых блоков сообщения равно (1 + НОД(е, р - 1)) х X(I + НОД (е - 1, q - I)). Данная особенность алгоритма RSA налагает определенные требования при выборе значения е. Так, например, если е равно 1 + k[(p(q), ф(р)], все элементы кольца сообщений окажутся иешифруемыми.
