НАДЕЖНОСТЬ РЕАЛИЗАЦИЙ АЛГОРИТМА RSA

В современном обществе задача обеспечения защищенной передачи информации является одной из наиболее актуальных из-за широкого распространения информационных систем и сервисов, обрабатывающих конфиденциальную информацию. При этом зачастую существует необходимость обеспечить защищенную передачу информации между узлами, не имеющими безопасного канала связи, например, компьютерами, подключенными к сети Интернет. Первым шагом к решению этой проблемы была работа Уитфилда Диффи и Мартина Хеллмана «Новые направления в современной криптографии», описывающая передачу открытого ключа по открытому каналу, для получения секретных ключей [1].

Алгоритм RSA разработан Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом в 1977 году и до сих пор является широко распространённым криптографическим алгоритмом с открытым ключом [2]. В основе алгоритма RSA, применяемого как для шифрования, так и для цифровой подписи, лежит задача факторизации больших целых чисел. Несмотря на то, что в 2010 году были опубликованы результаты о взломе шифра с длиной ключа 768 бит, зашифрованные данные с помощью ключей 1024 и 2048 бит по-прежнему считаются защищёнными и используются в современных криптосистемах [3].
Для получения зашифрованных данных с помощью алгоритма RSA злоумышленнику необходимо найти значение , определяемое по формуле (1).

      (1)

Открытым ключом, который может быть известен злоумышленнику, является пара значений . Значение  может быть получено, если известно значение , вычисляемое по формуле (2).

        (2)

Для получения , злоумышленнику необходимо разложить известное ему число  на простые множители  и , что в общем случае является крайне сложной задачей.
При этом, не смотря на высокую надежность алгоритма RSA, существует большое количество уязвимостей в различных реализациях этого алгоритма. Одной из таких уязвимостей может быть уязвимость в выборе простых чисел  и . Если простые числа не выбираются независимо друг от друга, а, например, являются последовательными простыми числами, то атака на данную реализацию может быть проведена за . Исходные простые числа  и  будут лежать в окрестностях числа .
Другим примером реализации алгоритма RSA, не обеспечивающем необходимой надежности, является библиотека «RSA Library», распространяемая под лицензией LGPLv2 [4]. Данная библиотека написана на языке PHP и с 2005 года была распространена тиражом более 5000 копий.

Листинг 1. Фрагмент кода генерации простых чисел  и 

На представленном выше фрагменте исходного кода программы «RSA Library» видно, что для генерации простых чисел  и  используется выбор случайных элементов из массива простых чисел, подготовленного заранее я заданного явно в коде программы. Очевидно, что обеспечить надежность зашифрованных с применением данной программы данных невозможно, т.к. простые числа выбираются из конечного, к тому же сильно ограниченного, массива простых чисел. Массив чисел содержит 570 элементов и задача факторизации, столь сложная в алгоритме RSA, в данной его реализации является вполне тривиальной и может быть с лёгкостью решена полным перебором всех возможных делителей числа .
Из представленных выше примеров видно, что использовать надежные криптографические алгоритмы недостаточно для обеспечения защищенности данных, необходимо применять надежные реализации таких алгоритмов.

1. Whitfield Diffie, Martin E. Hellman. New Directions in Cryptography (англ.) // IEEE Transactions on Information Theory. — Nov. 1976. — Т. IT-22. — С. 644–654.
2. R.L. Rivest, A. Shamir, L. Adleman. A method for obtaining digital signatures and public key cryptosystems (англ.) Comm. ACM, — 1978. — P. 120–126.
3. Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé: Factorization of a 768-bit RSA modulus. IACR Cryptology ePrint Archive 2010: 6 (2010).

Все статьи автора «Волокитина Татьяна Сергеевна»