Системы криптографической защиты данных с открытым ключом.

 

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

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

Операция шифрования и дешифрования алгоритмом с открытым ключом K обозначается так же, как в случае симметричного алгоритма:

Е_К1 (О) = С,

D_К2 (С) = О.

Ясно, что в отличие от симметричных алгоритмов при использовании алгоритмов с открытым ключом не возникает проблемы передачи ключа. В таких системах для шифрования данных используется один ключ, а для расшифрования – другой. Разумеется, ключ дешифрования не может быть определен из ключа шифрования.

В целом, система переписки при использовании асимметричного шифрования выглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя пара ключей: открытый K1 _j и закрытый K2 _j, где j – номер абонента. Все открытые ключи известны всем пользователям сети, каждый закрытый ключ, наоборот, хранится только у того абонента, которому он принадлежит. В случае если абонент под номером 3 собирается передать информацию абоненту номер 9, он шифрует данные открытым ключом шифрования K1 ₉ и отправляет ее 9-му абоненту, который сможет дешифровать сообщение своим секретным ключом K2 ₉. Другие абоненты, имеющие в наличии ключ шифрования абонента 9, не смогут, тем не менее, прочесть шифрованное послание 3-го абонента в силу необратимости шифрования по открытому ключу.

Если абонент номер 9 захочет ответить своему собеседнику номер 3, то ему нужно будет зашифровать свое ответное послание открытым ключом 3-го абонента K1 ₃ и отправить его номеру 3. Тот, в свою очередь, выполнит дешифровку ответа от номера 9 своим закрытым ключом K2 ₃. и снова никто из любопытствующих абонентов номер 1, 2, 4, …8, 10… N не сможет прочесть это сообщение.

В асимметричных системах количество существующих ключей связано с количеством абонентов линейно (в системе из N пользователей используется 2* N ключей), а не квадратично, как в симметричных системах. Помимо этого, при нарушении конфиденциальности m -ой рабочей станции злоумышленник узнает только ключ K2 _m: это позволяет ему читать все сообщения, приходящие абоненту m, но не позволяет выдавать себя за него при отправке писем.

Большинство асимметричных алгоритмов основано на необратимых функциях. Все действующие сейчас системы опираются на один из следующих типов необратимых преобразований:

1. разложение больших чисел на простые множители (алгоритм RSA);

2. вычисление логарифма в конечном поле (криптосистема Эль-Гамаля);

3. Вычисление корней алгебраических уравнений на основе эллиптических уравнений ( алгоритм Месси-Омуры).

 

Алгоритм RSA.

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

Под простым числом будем понимать такое число, которое делится только на 1 и на само себя. Эвклид в своих «Началах» показал, что для любого простого числа есть большее простое число, то есть количество простых чисел бесконечно.

Доказательство. Допустим, что существует наибольшее простое число p, определим произведение всех простых чисел P =2・3・5・7・…・ p.

Рассмотрим число P +1. Оно или само является простым числом большим p или произведением простых чисел, которые больше P. Мы пришли к противоречию, значит количество простых чисел бесконечно.

Примеры:

2・3+1=7; 2・3・5+1=31; 2・3・5・7+1=211;

2・3・5・7・11+1=2311; 2・3・5・7・11・13+1=30031=59・509.

Взаимно простыми числами будем называть такие числа, которые не имеют ни одного общего делителя, кроме 1.

Наконец, под результатом операции i mod j будем считать остаток от целочисленного деления i на j. Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги.

1. Выберем два очень больших простых числа р и q.

2. Определим n как результат умножения р на q (n=p·q).

3. Выберем большое случайное число, которое назовем d. Это число должно быть взаимно простым с результатом умножения (р – 1) · (q – 1).

4. Определим такое число е, для которого является истинным следующее соотношение (е·d) mod ((p – 1) · (q – 1)) = 1.

5. Назовем открытым ключом числа е и n, а секретным ключом – числа d и n.

Теперь, чтобы зашифровать данные по известному ключу { е, n }, необходимо сделать следующее:

– разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i);

– зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле С(i) = (M(i)e) mod n. Чтобы расшифровать эти данные, используя секретный ключ {d, n}, необходимо выполнить следующие вычисления: M(i)=(C(i)d) mod n. В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Алгоритм RSA основан на одной из доказанных теорем Эйлера, частный случай которой утверждает, что если число 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). Получаем (xe·d) mod n = x.

Для того чтобы прочесть сообщение ci = ((mi)e)mod n достаточно возвести его в степень d по модулю m:

((ci)d)mod n = ((mi)e·d) mod n = mi.

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

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

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

3. Найдем (р–1) (q–1)= 20. В качестве d выберем любое число, которое является взаимно простым с 20, например d= 3.

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

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

С(1)=(З7) mod 33 = 2187 mod 33 = 9,

С(2) = (17) mod 33 = 1 mod 33 = 1,

С(З) = (27) mod 33 = 128 mod 33 = 29.

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

M(1) = (93) mod 33 = 729 mod 33 = 3,

М(2) = (13) mod 33 = 1 mod 33 = 1,

М(З) = (293) mod 33 = 24389 mod 33 = 2.

Таким образом, в результате расшифровывания сообщения получено исходное сообщение «CAB».

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

Криптосистема RSA используется в самых различных платформах и во многих отраслях. Она встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении

алгоритм RSA применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании фирмы Zaxus (Rasal). Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах.

Технологию шифрования RSA BSAFE используют более 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего ключа в мире, и это количество имеет явную тенденцию к увеличению по мере роста пользователей Internet.