Analysis of secret-key algorithm vulnerability in RSA-cryptosystems

Full Text

Введение. Постановка задачи Криптосистему RSA разработали R. Rivest, A. Shamir, L. Adleman [1], а саму концепцию шифрования с помощью открытого ключа предложили W.Diffie и M.Hellman [2]. Асимметричная криптосистема RSA широко используется в современных инфокоммуникационных системах благодаря своим несомненным достоинствам: передача приватной информации по незащищенным каналам связи без предварительной передачи секретных ключей с помощью курьеров [3], цифровой подпись финансовых документов [4]. На базе RSA реализована известная почтовая программа PGP [5]. Взлом криптосистемы RSA затруднен вычислительной сложностью факторизации большого целого числа, являющегося произведением простых чисел. При формировании открытого ключа из множества допустимых значений рекомендуют формировать его по случайному закону [7; 11; 13]. В некоторых источниках предлагают использовать открытые ключи, которые содержат малое число единиц при их представлении в двоичной системе счисления [8]. Это позволяет повысить скорость шифрования, так как уменьшается число операций возведения в степень. В других источниках рекомендуют использовать числа Мерсенна и Ферма [6] и малые нечетные числа [10; 12]. Рассмотрим случаи, когда использование некоторых из перечисленных рекомендаций приводит к появлению уязвимостей в криптосистеме. Теоретическое обоснование Известно, что расчет секретной экспоненты t в криптосистеме RSA осуществляется с помощью соотношения [1]: , (1) здесь s - число взаимно простое с j(r), так называемая открытая экспонента; r - произведение двух простых чисел p и q (модуль); j(r) - функция Эйлера, которая вычисляется по формуле: . (2) Из соотношения (1) по вычисленному значению функции Эйлера j(r) и значению s требуется найти такое значение t, при котором целочисленное деление величины s×t на j(r) даст остаток 1. Открытая экспонента s и модуль r образуют открытый ключ, а числа t и r - закрытый ключ. Для проведения анализа уязвимостей криптосистемы RSA рассмотрим несколько лемм. Лемма 1. Функция Эйлера j(r) является четным числом. Доказательство. Функция Эйлера вычисляется по формуле (2). Все простые числа нечётные, поэтому функция Эйлера, равная произведению двух четных чисел, является четным числом. Лемма 2. Множество чисел открытой экспоненты s состоит из множества нечётных чисел. Доказательство. В соответствии с алгоритмом формирования ключей для асимметричной криптосистемы числа s должны быть взаимно простыми с четными числами j(r), поэтому числа s будут обязательно нечетными. Лемма 3. Секретная экспонента t является нечетным числом. Доказательство. В соответствии с выражением (1) целочисленное деление произведения s×t на четное число j(r) должно дать остаток, равный единице. Это возможно только при нечётных значениях произведения s×t. В соответствии с леммой 2 число s является нечетным. Произведение s×t будет нечетным только при нечетных значениях t. Лемма 4. Функция Эйлера кратна 10, если хотя бы одно простое число модуля (p или q) оканчивается на 1. Доказательство. Используемые в практической криптографии простые числа могут оканчиваться только цифрами 1; 3; 7 и 9. Единственное простое число, которое оканчивается на 5 - это само число 5. Однако оно слишком мало для практического формирования криптографических ключей. В соответствии с формулой для вычисления функции Эйлера (2) произведение указанных сомножителей будет кратно 10, если хотя бы одно простое число оканчивается на 1. Можно ожидать, что 25% ключей формируются при значениях функции Эйлера, кратной 10. Лемма 5. Если j(r) кратно 10, а число s оканчивается цифрой 7, то число t оканчивается цифрой 3. Доказательство. Так как произведение указанных чисел s и t будет оканчиваться единицей, то в результате вычитания единицы из произведения s×t будет получено число, кратное 10. Таким образом, величину t нужно искать среди чисел, у которых последняя цифра 3, например, 3, 13, 23 и т.д. Пример 1. Пусть j(r) = 440, s = 27. Расчет секретной экспоненты с помощью обобщенного алгоритма Евклида дал t = 163. Лемма 6. Если j(r) кратно 10, а число s оканчивается цифрой 3, то число t оканчиваться цифрой 7. Доказательство. Доказательство аналогично доказательству леммы 5. Итак, величину t нужно искать среди чисел, оканчивающихся на цифру 7, например, 7, 17, 27 и т.д. Пример 2. Пусть j(r) = 440, s = 23, тогда t = 287. Лемма 7. Если j(r) кратно 10, а s оканчивается цифрой 9, то последняя цифра числа t должна быть 9. Доказательство. Только произведение двух чисел, оканчивающихся цифрами 9 (при s, оканчивающимся на 9), дает число, у которого последняя цифра 1. В этих случаях число s×t - 1 будет кратно 10. Пример 3. Пусть j(r) = 120, s = 19. Расчёт дал t = 19. Лемма 8. Если j(r) кратно 10, а s оканчивается цифрой 1, то последняя цифра числа t должна быть 1. Доказательство. Только произведение двух чисел, оканчивающихся цифрами 1 (при числе s, оканчивающимся цифрой 1), дает число, у которого последняя цифра 1. В этих случаях число s t - 1 будет кратно 10. Пример 4. Пусть j(r) = 120, s = 31. Расчет дал t = 31. Леммы 7 и 8 указывают на снижение криптостойкости в рассмотренных случаях (последние цифры открытой и закрытой экспоненты обязательно совпадают). Можно предположить, что могут быть сформированы полностью совпадающие числа s и t (ключи близнецы), то есть секретный ключ может быть ошибочно опубликован абонентом. Примеры 3 и 4 подтверждают это утверждение. Другими словами, при j(r), кратном десяти и открытых экспонентах, оканчивающихся цифрами 1 и 9 есть вероятность открытой публикации секретного ключа. Если величина s выбирается по случайному закону, то для j(r), кратных 10, вероятность формирования ключей, оканчивающихся цифрами 1 или 9, составляет 0,125. При этом некоторая часть секретных ключей полностью совпадет с открытыми ключами. Экспериментальное подтверждение Рассмотренная гипотеза о возможности совпадения открытых и закрытых ключей была проверена расчетным путем с помощью математической системы Mathcad. Для j(r) = 440 выявлено 15 уязвимостей (открытый и закрытый ключи полностью совпали, например, 241, 351, 309, 419). Для j(r) = 18240 выявлено также 15 уязвимостей (например, 14401, 14591, 15391). В последнем случае анализировались только ключи, оканчивающиеся на единицу. Вывод При практическом формировании ключей в криптосистеме RSA в случаях, когда функция Эйлера кратна 10, а открытая экспонента оканчивается цифрами 1 или 9, следует произвести проверку на полное совпадение сформированных открытого и зарытого ключей. Очевидно, что совпадающие ключи не должны быть использованы. Среди существующих рекомендаций по выбору открытой экспоненты следует считать предпочтительным использование чисел Ферма.

About the authors

Aleksander Petrovich Alekseev

Povolzhskiy State University of Telecommunications and Informatics

Email: apa_ivt@rambler.ru

References

Supplementary files