Защищенность алгоритма rsa

Существуют 3 возможных подхода для к крипто анализу алгоритма RSA:

1) Простой перебор. То есть крипто анализ предполагает проверку всех возможных личных ключей до тех пор, пока не будет найден подходящий.

2) Математический анализ. Большинство вариантов математического анализа по своей сути эквивалентны процедуре нахождения множителей произведения двух простых чисел.

3) Анализ временных затрат. Действия опираются а анализ времени выполнения алгоритма дешифрования.

Защита от простого перебора заключается в использовании большого пространства ключей. Чем больше бит в значении e и d, тем лучше. Но чем больше размер ключа, медленнее будет работать система.

Математические проблемы разложения на множители:

1) Разложение величины N на 2 простых множителя. Это позволит вычислить преобразования n. и

2) Определение значения непосредственно без определения предварительного подбора p и q

3) Определение непосредственно значения d без того, чтобы предварительно вычислять

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

- постоянное время выполнения операции возведения в степень. Изменение алгоритма таким образом, чтобы все возведения степень занимали одно и то же время (от начала выполнения до получения результата). Но существенно возрастает время выполнения алгоритма.

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

- маскировка. Предполагает умножение шифрованного текста на случайное число перед выполнением операции возведения в степень. Это не позволит нарушителю узнать какие биты обрабатывались в ПК.

В некоторых продуктах компании RSA Data Security уже заранее предполагается возможность использования функции маскировки. В них операция с личным ключом выполняется следующим образом:

1) Генерируется секретное случайное число r в диапазоне от 0 до n-1

2) Вычисляется вспомогательная величина с’ как 3) Вычисление

4) Само , где r-1 – мультипликативное обратное значение r о модулю.

При использовании маскировки общая производительность алгоритма RSA снижается от 2 до 10%.

Ограничения rsa:

1) Знание одной пары показателей шифрования/расшифрования для одного конкретного модуля позволяет взломщику разложить модуль на множители.

2) Знание одной пары показателей шифрования/расшифрования для одного конкретного модуля позволяет взломщику вычислить другие пары показателей. При этом не раскладывая модуль на множители.

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

4) Для предотвращения вскрытия малого показателя шифрования сообщения должны быть дополнены случайными значениями. Это позволит усложнить вскрытие.

5) Показатель расшифрования должен быть большим.

Алгоритм RSA также может быть применён для генерации псевдослучайных последовательностей! (САМОСТОЯТЕЛЬНОЕ ИЗУЧЕНИЕ)

Недостатком RSA является недостаточное быстродействие, особенно на ПК. На 3-4 порядка работают медленнее, чем симметричные.

Кроме RSA в группу асимметричных входят:

1) Алгоритм Полига-Хеллмена 2) Схема Рабина

3) Схема Вильямса 4) Схема Эль Гамаля

Для ускорения шифрования с передачей секретного ключа (для эффективного шифрования), использованного отправителем, сообщение сначала симметрично зашифровывают случайным ключом, а затем этот ключ зашифровывают открытым ассиметричным ключом получателя. После чего сообщение и ключ отправляются по сети. В этом мы видим сочетание симметричного и асимметричного шифрования.