Сис­те­мы с от­кры­тым клю­чом

Как бы ни бы­ли слож­ны и на­деж­ны крип­то­гра­фи­че­ские сис­те­мы - их сла­бое ме­ст при прак­ти­че­ской реа­ли­за­ции - про­блема рас­пре­де­ле­ния клю­чей. Для то­го, что­бы был воз­мо­жен об­мен кон­фи­ден­ци­аль­ной ин­фор­ма­ци­ей ме­ж­ду дву­мя субъ­ек­та­ми ИС, ключ дол­жен быть сге­не­ри­ро­ван од­ним из них, а за­тем ка­ким-то об­ра­зом опять же в кон­фи­ден­ци­аль­ном по­ряд­ке пе­ре­дан дру­го­му. Т.е. в об­щем слу­чае для пе­ре­да­чи клю­ча опять же тре­бу­ет­ся ис­поль­зо­ва­ние ка­кой-то крип­то­си­сте­мы.

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

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

Ис­ход­ный текст шиф­ру­ет­ся от­кры­тым клю­чом адресата и пе­ре­да­ет­ся ему. За­шиф­ро­ван­ный текст в прин­ци­пе не мо­жет быть рас­шиф­ро­ван тем же от­кры­тым клю­чом. Де­шиф­ро­ва­ние со­об­ще­ние воз­мож­но толь­ко с ис­поль­зо­ва­ни­ем за­кры­то­го клю­ча, ко­то­рый из­вес­тен толь­ко са­мо­му ад­ре­са­ту.

 

Крип­то­гра­фи­че­ские сис­те­мы с от­кры­тым клю­чом ис­поль­зу­ют так называемые не­об­ра­ти­мые или од­но­сто­рон­ние функ­ции, ко­то­рые об­ла­да­ют сле­дую­щим свой­ст­вом: при за­дан­ном зна­че­нии x от­но­си­тель­но про­сто вы­чис­лить зна­че­ние f(x), од­на­ко ес­ли y = f(x), то нет про­сто­го пу­ти для вы­чис­ле­ния зна­че­ния x.

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

В са­мом оп­ре­де­ле­нии не­об­ра­ти­мо­сти при­сут­ст­ву­ет не­оп­ре­де­лен­ность. Под необратимостью понимается не теоретическая необратимость, а практическая невозможность вычислить обратное значение используя современные вычислительные средства за обозримый интервал времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

Ал­го­ритм RSA

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

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

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

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

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

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

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

x^{p -1} = 1 (mod p) (1)

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

x^p = х (mod p) (2)

для любого х.

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

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

x^p =(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. С учетом этого неравенства и предложений метода доказательства по индукции теорема доказана.

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

n
j(n)

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

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

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

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

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

Е_e,n: x ® x ^e (mod n)

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

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

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

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

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

Пользователь i выбирает пару различных простых p _i и q _i и рассчитывает пару целых (e_i, d_i), которые являются простыми относительно j(n_i), где n _i= p _i q _i. Справочная таблица содержит публичные ключи {(e_i,n_i)}.

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

x =(x ₀, x ₁,..., x _n-1), x ÎZ_n, 0 £ i < n,

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

N = c₀+c_{i n i}+....

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

N ® Ed_i,n_i n = n ’.

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

N’ ® Ee_i,n_i n ’= Ee_i,n_i Ed_i,n_i n = n.

Очевидно, для того чтобы найти инверсию Ed_i,n_i по отношению к Ee_i,n_i, требуется знание множителей n = p _i q _i. Время выполнения наилучших из известных алгоритмов разложения при n =10¹⁰⁰ на сегодняшний день выходит за пределы современных технологических возможностей.

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

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

1. Выберем p =3 и q =11.

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

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

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

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

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

ШТ2 = (1⁷) (mod 33) = 1 (mod 33) = 1,

ШТ3 = (2⁷) (mod 33) = 128 (mod 33) = 29.

6. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (9³) (mod 33) = 729 (mod 33) = 3,

ИТ2= (1³) (mod 33) = 1 (mod 33) = 1,

ИТ3 = (29³) (mod 33) = 24389 (mod 33) = 2.

Итак, в реальных системах алгоритм RSA реализуется следующим образом: каждый пользователь выбирает два больших простых числа, и в соответствии с описанным выше алгоритмом выбирает два простых числа e и d. Как результат умножения первых двух чисел (p и q) устанавливается n.

{e,n} образует открытый ключ, а {d,n} - закрытый (хотя можно взять и наоборот).

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