Баричев С. Криптография без секретов

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

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

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HHTP, S-MIME, S/WAN, STT и PCT.

Рас​смот​рим ма​те​ма​ти​че​ские ре​зуль​та​ты, по​ло​жен​ные в ос​но​ву это​го ал​го​рит​ма.

Теорема 1. (Малая теорема Ферма.)

Если р - простое число, то

xp-1 = 1 (mod p) (1)

для любого х, простого относительно р, и

xp = х (mod p) (2)

для любого х.

Доказательство. Достаточно доказать справедливость уравнений (1) и (2) для х(Zp. Проведем доказательство методом индукции.

Очевидно, что уравнение (8.2.2) выполняется при х=0 и 1. Далее

xp=(x-1+1)p= ( C(p,j)(x-1)j=(x-1)p+1 (mod p),

0(j(p

так как C(p,j)=0(mod p) при 0<j<p. С учетом этого неравенства и предложений метода доказательства по индукции теорема доказана.

Определение. Функцией Эйлера ((n) называется число положительных целых, меньших n и простых относительно n.

n

2

3

4

5

6

7

8

9

10

11

12

((n)

1

2

2

3

2

6

4

6

4

10

4

Теорема 2. Если n=pq, (p и q - отличные друг от друга простые числа), то

((n)=(p-1)(q-1).

Теорема 3. Если n=pq, (p и q - отличные друг от друга простые числа) и х - простое относительно р и q, то

x((n) = 1 (mod n).

Следствие . Если n=pq, (p и q - отличные друг от друга простые числа) и е простое относительно ((n), то отображение

Еe,n: x(xe (mod n)

является взаимно однозначным на Zn.

Очевиден и тот факт, что если е - простое относительно ((n), то существует целое d, такое, что

ed = 1 (mod ((n)) (3)

На этих математических фактах и основан популярный алгоритм RSA.

Пусть n=pq, где p и q - различные простые числа. Если e и d удовлетворяют уравнению (8.2.3), то отображения Еe,n и Еd,n являются инверсиями на Zn. Как Еe,n, так и Еd,n легко рассчитываются, когда известны e, d, p, q. Если известны e и n, но p и q неизвестны, то Еe,n представляет собой одностороннюю функцию; нахождение Еd,n по заданному n равносильно разложению n. Если p и q - достаточно большие простые, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA.

Пользователь i выбирает пару различных простых pi и qi и рассчитывает пару целых (ei, di), которые являются простыми относительно ((ni), где ni=pi qi . Справочная таблица содержит публичные ключи {(ei ,ni)}.

Предположим, что исходный текст

x =(x0, x1, ..., xn-1), x(Zn , 0 ( i < n,

сначала представлен по основанию ni :

N = c0+ci ni+....

Пользователь i зашифровывает текст при передаче его пользователю j, применяя к n отображение Edi,ni :

N ( Edi,ni n = n’.

Пользователь j производит дешифрование n’, применяя Eei,ni :

N’ ( Eei,ni n’= Eei,ni Edi,ni n = n .

Очевидно, для того чтобы найти инверсию Edi,ni по отношению к Eei,ni, требуется знание множителей n=pi qi. Время выполнения наилучших из известных алгоритмов разложения при n=10100 на сегодняшний день выходит за пределы современных технологических возможностей.

Рассмотрим небольшой пример, иллюстрирующий применение алгоритма RSA.

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