Современные информационные технологии/4.Информационная безопасность.

Волокитин С. С.

Юго-Западный государственный университет, Россия

Надежность реализаций алгоритма 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 копий.

function generate_keys ($show_debug=0){

global $primes, $maxprimes;

while (empty($e) || empty($d)) {

$p = $primes[mt_rand(0, $maxprimes)];

while (empty($q) || ($p==$q)) $q = $primes[mt_rand(0, $maxprimes)];

$n = $p*$q;

$pi = ($p - 1) * ($q - 1);

$e = tofindE($pi, $p, $q);

$d = extend($e,$pi);

$keys = array ($n, $e, $d);

}

Листинг 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).

4. RSA Library[Интернет-портал]. URL: http://sourceforge.net/projects/rsalib/ (дата обращения: 30.10.2013).