Особенности проектирования и криптоанализа асимметричной криптографической системы RSA



В данной статье рассматриваются некоторые особенности проектирования асимметричной (открытой) криптосистемы RSA, проводится обзор тестов на принадлежность классу простых чисел, а также рассматривается выбор показателей степеней чисел при кодировании.

В исследовании также приводится пример криптографического анализа систем RSA методами факторизации и прямой оценки секретного показателя степени.

Ключевые слова: шифрование, криптосистема, криптоанализ, RSA-система, факторизация

In this article, some features of projection of the asymmetric (open) RSA cryptosystem are considered, the review of tests for accessory to a class of prime numbers is carried out, and also the choice of indexes of degrees of numbers when coding is considered.

In the research the example of the cryptographic analysis of the RSA systems by methods of a factorization and direct assessment of a secret exponent is also given.

Keywords: enciphering, cryptosystem, cryptanalysis, RSA system, factorization

В системе RSA шифрование выполняется путем возведения в степень кодов символов сообщения в степень в арифметике вычетов по модулю , а дешифрование — возведением кодов символов зашифрованного сообщения в степень , т. е.

,

где модуль сравнения равен произведению двух больших простых чисел и . Открытый ключ шифрования — это пара , а секретный ключ дешифрования — пара . Показатели степени выбираются так, чтобы они были обратными величинами в арифметике вычетов по модулю и – перестановка в классе вычетов по модулю, то есть

где .

При проектировании RSA-системы пользователь должен выбрать два больших простых числа и , чтобы вычислить модуль сравнения , значение которого зависит от предполагаемой сложности раскрытия проектируемой криптографической системы. Таблица 1 дает представление о значениях величины . Число операций для каждого значения соответствует наилучшему из известных алгоритмов факторизации больших чисел.

Таблица 1

Используемые модули сравнения вRSA-системах [1]

	Число операций	Примечание
		Предел современных технологий
		За пределами современных технологий

При назначении модуля сравнения два простых числа и должны быть выбраны случайным образом. Теорема о простых числах утверждает, что вблизи числа количество простых чисел в среднем составляет на целых чисел. Таким образом, даже для очень больших простых чисел с количеством цифр, измеряемых сотнями, лишь несколько сотен простых чисел должны быть проверены на принадлежность классу простых. Как следствие, необходимо только проверить, является ли выбранное большое число простым. Наиболее распространены следующие три теста проверки на простое число: тест Ферма, тест Соловея — Штрассена и тест Рабина. Во всех тестах предполагается, что он применяется к числу .

Тест Ферма

Этот тест основан на малой теореме Ферма, которая утверждает, что если – простое число, то

для всех , .

Таким образом, тест состоит в выборе числа , меньшего , и проверке на принадлежность классу простых чисел согласно условию в соответствии с приведенным выше уравнением. Практически требуется проверить только несколько значений . Данным тестом пропускается небольшое количество составных чисел. Рекомендуется выполнить порядка тестов, чтобы удостовериться, что данное число простое. Утверждается, что выбор равным позволяет выявить все составные числа. Однако следует заметить, что данный тест пропускает составные числа Кармайкла (например, число ).

Тест Соловея — Штрассена

Данный тест позволяет выявлять все составные числа Кармайкла. Выбирается случайное число в диапазоне от до и проверяется выполнение условий

, ,

где — символ Якоби; — наибольший общий делитель.

Символ Якоби определяется следующими соотношениями:

, если имеет решение в

, если не имеет решения в ,

где — кольцо вычетов по модулю .

Если — простое число, условия, приведенные выше, всегда выполняются, а если — составное, то они не выполняются с вероятностью . Поэтому выполнение тестов гарантирует, что ответ неправилен с вероятностью , когда тестируемое число является простым, а если число составное, то условие всегда выполняется.

Тест Рабина

Поскольку число , которое должно быть простым, всегда нечетное, его можно представить в виде

,

где — четное число.

Затем в тесте выбирается случайным образом число в диапазоне от до и проверяется выполнение условий

,

для .

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

В ряде случаев алгоритмы факторизации могут оказаться не согласованными. Для проверки достаточно выбрать простые и такие, чтобы и имели в качестве множителя большое простое число. Например, можно задать некоторое большое простое число и затем выбрать в качестве (или ) первое простое число из последовательности …

Дополнительную защищенность можно обеспечить, если также имеет в качестве множителя большое простое число. Если , то — хорошая аппроксимация для величины, а зная ее легко восстановить , поскольку

.

Простые числа не должны принадлежать специальным классам, например, быть числами Ферма или Мерсенна, так как они хорошо изучены, что упрощает поиск факторизации.

Выбрав простые числа и , а, следовательно, и , необходимо приступить к выбору показателей степени и . Для этого выбирается из условия, чтобы оно было взаимно простым с . Это достигается вычислением остатка и помощью алгоритма Евклида. Алгоритм позволяет не только проверить, являются ли числа и взаимно простыми, но также подсчитать мультипликативно обратный к показатель степени . Известно, что сложность вычисления функции имеет временную оценку [2]. На выбор показателей и необходимо наложить условие, чтобы эти величины превышали . Если , то малые сообщения окажутся незашифрованными.

Если будет выполняться условие , то шифр будет раскрываться простым перебором. Если , то система может быть раскрыта только случайно.

Существует еще одно условие при выборе . Как уже упоминалось, чтобы осуществить перестановки в сообщении в соответствии с функцией , должно быть взаимно простым с функцией Эйлера , или, более точно, взаимно простым с — наименьшим общим кратным следующих чисел:

.

Среди этих перестановок есть и такие, которые сохраняют сообщение, и они удовлетворяют условию конгруэнтности

,

где — нечетное число, большее , и .

Известно, что любое решение уравнения

удовлетворяет и первому уравнению. Далее отметим, что второе уравнение имеет решений в диапазоне чисел .

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

.

Криптографический анализ RSA-системы

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

Метод факторизации .

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

Метод вычисления без факторизации.

Другой возможный способ криптоанализа связан с непосредственным вычислением функции Эйлера без факторизации. Однако прямое вычисление нисколько не проще факторизации, поскольку позволяет после этого легко факторизовать . Это можно видеть из следующего примера. Пусть

, .

Зная , можно определить и, следовательно, ; зная и , простые и можно определить из следующих соотношений

, .

Метод прямой оценки без факторизации или вычисления .

Третий способ криптоанализа состоит в непосредственном вычислении величины . Аргументация этого способа основана на том, что если выбрано достаточно большим, чтобы простой перебор был невозможен, вычисление не проще факторизации , поскольку если известно, то легко факторизуется. Показать это можно следующим образом: если известно, то можно вычислить величину, кратную функции Эйлера, используя условие

,

где — произвольное целое число.

Миллер [3] показал, что факторизацию можно выполнить, используя любое значение, кратное . Дешифровщик, с другой стороны, может попытаться найти некоторую величину , которая была бы эквивалентна скрытой величине , использованной при разработке шифра. Если существует много таких , то можно попытаться использовать прямой перебор, чтобы раскрыть шифр. Но все различаются множителем, равным , и если этот множитель вычислен, то можно факторизовать. Таким образом, нахождение столь же сложно, сколь и факторизация .

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

Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.

Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным сеансовым ключом (например, AES, IDEA, Serpent, Twofish), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптографически стойкий генератор псевдослучайных чисел для формирования случайного сеансового ключа симметричного шифрования. [4]

Литература:

1. Rivest, R.L., Shamir, A., Adleman, L. A. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems // Communications of the ACM. — 1978. — № 21(2).
2. Knuth D. E. The Art of Computer Programming: Vol 2: Seminumerical Algorithms. — Massachusetts, USA: Addison-Wesley, 1981.
3. Miller G. L. Riemann's Hypothesis and Tests for Primality // Journal of Computer and System Sciences. — 1976. — № 13.
4. RSA // Википедия URL: https://ru.wikipedia.org/wiki/RSA (дата обращения: 01.02.17).