mi=cid mod n.

Последнее справедливо, так как

Cid=(mie)e=mied=mikφ(n)+1=mi*mi kφ(n)=mi*1=mi.

Все вычисления выполняються по модулю n.

Отметим, что сообщение может быть зашифровано с помощью d, а дешифровано с помощью e, возможен любой выбор.

Рассмотрим короткий пример. Если

p=47 и q=71, то n=pq=3337.

Ключ e не должен иметь общих множителей с

φ(n)=46*70=3220.

Выберем (случайное) e равным 79. В этом случае d=79-1 mod 3220 = 1019. Опубликуем e и n, сохранив в секрете d. Для шифрования сообщения

m=6882326879666683

сначала разобьем его на блоки. Для выбранных параметров ограничимся блоками по три десятичных разряда. Сообщение разбивается на шесть блоков mi:

m1=688

m2=232

m3=687

m4=966

m5=668

m6=003

Первый блок шифруется как 68879 mod 3337 = 1570 = c1. Выполняя те же операции для последующих блоков, создадим шифротекст сообщения:

c=15702756209122762423158.

Для дешифрования нужно выполнить возведение в степень, используя ключ дешифрования 1019:

15701019 mod 3337 = 688 = m1.

Аналогично восстанавливается оставшаяся часть сообщения.

Эффективность реализации

Существует много публикаций, затрагивающих тему аппаратных реализаций RSA.

Быстродействие аппаратной реализации RSA примерно в 1000 раз ниже, чем быстродействие аппаратной реализации DES. Быстродействие СБИС-реализации RSA с 512-битовым модулем – 64 Кбит/сек. Существуют также микросхемы RSA, которые оперируют с 1024-битовыми числами. В настоящее время разрабатываются микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1 Мбит/сек. Производители так же реализуют RSA в интеллектуальных карточках, однако производительность этих реализаций невысока. Программная реализация DES примерно в 100 раз быстрее программной реализации RSA. Эти оценки могут незначительно могут незначительно меняться в зависимости от используемых технологий, но RSA никогда не достигнет производительности симметрических алгоритмов.

Шифрование RSA выполняются намного эффективнее, если правильно выбрать значение e. Чаще всего используются 3, 17 или 65537 = 216+1 – двоичное представление этого числа содержит только две единицы, поэтому для возведения в степень нужно выполнить лишь 17 умножений. Стандарт X.509 рекомендует число 65537, PEM – 3, PKCS#1 – 3 или 65537. Использование в качестве e любого из указанных значений (при условии, что сообщение дополняются случайными числами) не влияет на криптостойкость, даже если одно и то же значение e используется группой пользователей. Операции с секретным ключом можно ускорить при помощи китайской теоремы об остатках, если сохранить значения p и q, а так же заранее по секретному и открытому ключам вычислить вспомогательные значения: d mod (p-1), d mod (q-1) и q-1 mod p.

Криптостойкость RSA

Предполагается, что криптостойкостью RSA зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно разложить n на множители, чтобы восстановить m по c и e. Не исключено, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Так же можно атаковать RSA, угадав значение (p-1)(q-1). Однако этот метод не проще разложения n на множители. Доказано, что при использовании RSA раскрытие даже нескольких битов информации по шифротексту не легче, чем дешифрования всего сообщения. Самой очевидной атакой на RSA является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрования d, противник должен разложить n на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже менее эффективна, чем попытка разложения n на множители. В 1993 г. Был предложен метод кирптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет, если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь, открывает возможности для атаки путем факторизации модуля. Другая опасность заключается в генерации псевдопростых чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума.

Итоги по безопасности

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

• знание одной пары показателей шифрования/дешифрования для данного модуля позволяет злоумышленнику разложить модуль на множители;
• знание одной пары показателей шифрования/дешифрования для данного модуля позволяет злоумышленнику вычислить другие пары показателей, не расладывая модуль на множители;
• в криптографических протоколах с использованием RSA общий модуль использоваться не должен. (Это являеться очевидным следствием предыдущих двух пунктов.);
• для предотвращения раскрытия малого показателя шифрования сообщения должны быть дополнены («набиты») случайными значениями;
• показатель дешифрования должен быть большим.

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

Криптосистема ЭльГамаля.

Криптосистему, предложенную ЭльГамалем в 1985 г. Можно использовать как для цифровых подписей, так и для шифрования. Криптостойкость определяется трудоемкость вычисления дискретного алгоритма в конечном поле. Криптоалгоритм не запатентован, но попадает под действие патента на метод экспоненциального ключевого обмена Диффи-Хеллмана.

Для генерации пары ключей сначала выбираются простое число p и два случайных числа, g и x; оба этих числа должны быть меньше p. Затем вычисляется

y=gx mod p.

Открытым ключом являются y, g и p. И g, и p можно сделать общими для группы пользователей. Секретным является x.

Вычисление и проверка подписи

Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое с p-1. Затем вычисляется a=gk mod p, и с помощью расширенного алгоритма Евклида из уравнения

M=(xa+kb) mod (p-1)