Алгоритм RSA

Источник: Патрик Гёлль

Наиболее известным алгоритмом на открытом ключе является алгоритм RSA (Rivest Shamir Adleman), который использует математические свойства степеней по модулю N: выбираются два простых числа (p и q), произведение которых (pq) послужит модулем для вычисления последующих степеней. Проще говоря, A в степени B по модулю N представляет собой A, умноженное B раз на A, минус столько раз N, чтобы получить положительный результат, меньший чем молдуль N.

Алгорит RSA основывается на том факте, что
(p-1)(q-1)/x = 1 по модулю pq
при условии, что x не делится ни на p, ни на q.

На практике это условие выполняется автоматически, если каждое из чисел p и q больше x, что, в общем, характерно при кодировании (чаще всего работают на числах разрядностью 512 бит).

	10 REM -- MODULO.BAS --
	20 KEY OFF:CLS
	30 INPUT"Данные? ", D
	40 INPUT"Показатель степени? ", E
	50 INPUT"Коэффициент? ", M
	60 R=D
	70 FOR F=1 TO E-1
	80 R=R*D
	90 IF R<M THEN 110
	100 R=R-M:GOTO 90
	110 NEXT F
	120 PRINT"результат: ";R
	130 PRINT:GOTO 30

Небольшая программа MODULO.BAS позволит провести несколько экспериментов со свободно выбранными операндами, а кроме этого проиллюстрирует принцип, используемый для возведения в степень по модулю с помощью программы на языке BASIC, без особого риска возникновения ошибок переполнения (overflow).

Оба ключа RSA (открытый e и секретный d или наоборот) выбираются так, чтобы они отвечали условию:
ed = 1 модуль (p-1)(q-1).
В таком случае мы имеем:
(x^d)^e = x (модуль pq)
При этом ничто не позволяет вывести d из e или наоборот.

	10 REM -- RSA.BAS --
	20 A$ = "www.HackersRussia.ru"
	30 FOR G=1 TO LEN(A$)
	40 D$=MID(A$,G,1):D=ASC(D$)
	50 E=15:M=391
	55 REM Открытый ключ = 15, коэффициент = 391
	60 GOSUB 130
	70 PRINT D$,R,
	80 E=47:M=391
	85 REM Секретный ключ = 47, коэффициент = 391
	90 D=R:GOSUB 130
	100 PRINT CHR$(R)
	110 NEXT G
	120 END
	130 R=D
	140 FOR F=1 TO E-1
	150 R=R*D
	160 IF R<M THEN 180
	170 R=R-M:GOTO 160
	180 NEXT F
	190 RETURN

Программа RSA.BAS применяет данный алгоритм в условиях, полностью сравнимых с вышеназванными, при использовании следующих ключей:

• открытый ключ: 15, модуль 391
• секретный ключ: 47, модуль 391

Значения получены из простых чисел p=17 и q=23.

Конечно, надежность операций не выше, чем в предыдущем случае, так как обработка идет байт за байтом, в то время как лучше было бы обрабатывть блоки по 512 бит. Однако преимущество этого способа в том, что он показывает, насколько замедленны вычисления даже при работе с блоками по 8 бит: именно благодаря этому ныне возможность снабжать смарт-карты алгоритмом RSA только при наличии на карте специального сопроцессора, пока не появились крутые смарт-карты с 32-битным ядром. Например, с микроконтроллером 83C852 удается провести вычисления за полторы секунды, в то время как для проведения аналогичной операции с помошью базовой системы команд микропроцессора на 8 бит понадобилось бы почти 3 минуты. По этой причине большинство карт на микропроцессорах довольствуется симметричным алгоритмом, ультрасекретный ключ которого физически присутствует на карте и в связи с этим должен очень тщательно защищаться.

Источник: лекции МСЗИ

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.

Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций

1. Выбираются два простых (!) числа p и q

2. Вычисляется их произведение n(=p*q)

3. Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

4. Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

5. Два числа (e,n) – публикуются как открытый ключ.

6. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

Как же производится собственно шифрование с помощью этих чисел:

1. Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

2. Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа (назовем его m_i) вычисляется выражение c_i=((m_i)^e)mod n. Блоки c_i и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.

А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x^(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y) : (x^{(-y)(p-1)(q-1)})mod n = 1^(-y) = 1. Теперь умножим обе ее части на x : (x^{(-y)(p-1)(q-1)+1})mod n = 1*x = x.

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (x^e*d)mod n = x. То есть для того чтобы прочесть сообщение c_i=((m_i)^e)mod n достаточно возвести его в степень d по модулю m : ((c_i)^d)mod n = ((m_i)^e*d)mod n = m_i.

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