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

1. Преобразование исходного текста должно быть необратимым и исключать его восстановление на основе открытого ключа.

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

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых систем и рекомендован МККТТ.

Вообще же все предлагаемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:

1. Разложение больших чисел ан простые множители.

2. Вычисление логарифма в конечном поле.

3. Вычисление корней алгебраических уравнений.

Здесь же следует отметить, что алгоритмы криптосистемы с открытым ключом (СОК) можно использовать в трех назначениях.

1. Как самостоятельные средства защиты передаваемых и хранимых данных.

2. Как средства для распределения ключей. Алгоритмы СОК более трудоемки, чем традиционные криптосистемы. Поэтому часто на практике рационально с помощью СОК распределять ключи, объем которых как информации незначителен. А потом с помощью обычных алгоритмов осуществлять обмен большими информационными потоками.

3. Средства аутентификации пользователей. Об этом будет рассказано в главе «Электронная подпись».

Ниже рассматриваются наиболее распространенные системы с открытым ключом.

Алгоритм RSA

Несмотря на довольно большое число различных СОК, наиболее популярна - криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.

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

в настоящее время он возглавляет компанию RSA Data Security

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

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

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

Теорема 1. (Малая теорема Ферма.) Если р - простое число, то

xf- = 1 (mod р) (1)

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

= х (mod р) (2)

для любого X.

Доказательство. Достаточно доказать справедливость уравнений (1) и (2) для XG Z. Проведем доказательство методом индукции. Очевидно, что уравнение (8.2.2) выполняется при х=0 и 1. Далее

дЦх-1+1/= L C(p,i){x-lMx-iy+l (mod/7),

0<i<p

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

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

п 23456789 10 11 12

ф(п)

122326464 10 4

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

(?(n)=(p-l)(q-l).

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

x"=l(mod«).

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

Ее,п: хх (mod п)

является взаимно однозначным на Zn. Очевиден и тот факт, что если е - простое относительно ф(п), то существует целое d, такое, что

ed = 1 (mod ф(п)) (3)

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

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

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

X =(хо, хи Xn-i), XG Zn , о < i < л, сначала представлен по основанию щ :

N = Co+Ci„i+....

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

N Edi,ni п = п\

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

N Eei,ni л= Eei,ni Edi,ni П = П .

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

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

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

1. Выберемр=Ъ \iq=ll.

2. Определим «=3*11=33.

3. Найдем (p-l)(q-l)=20. Следовательно, в качестве d, взаимно простое с 20, например, d=3.

4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е*3) (mod 20) = 1, например 7.

5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А1, В2, СЗ. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}.

ШТ1 = (3) (mod 33) = 2187 (mod 33) = 9,