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

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

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

Ал­го­ритм RSA

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

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

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

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

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

Теорема 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	2	3	4	5	6	7	8	9	10	11	12
j(n)	1	2	2	3	2	6	4	6	4	10	4

 

Теорема 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 ni}+....

Пользователь 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} - закрытый (хотя можно взять и наоборот).

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

Практическая реализация RSA

В настоящее время алгоритм RSA активно реализуется как в виде самостоятельных криптографических продуктов[8], так и в качестве встроенных средств в популярных приложениях[9].

Важная проблема практической реализации - генерация больших простых чисел. Решение задачи «в лоб» - генерация случайного большого числа n (нечетного) и проверка его делимости на множители от 3 вплоть до n^0.5. В случае неуспеха следует взять n+2 и так далее.[10]

В принципе в качестве p и q можно использовать «почти» простые числа, то есть числа для которых вероятность того, что они простые, стремится к 1. Но в случае, если использовано составное число, а не простое, криптостойкость RSA падает. Имеются неплохие алгоритмы, которые позволяют генерировать «почти» простые числа с уровнем доверия 2^-100.

Другая проблема - ключи какой длины следует использовать?

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

log10 n	Число операций	Примечания
50	1.4*1010	Раскрываем на суперкомпьютерах
100	2.3*1015	На пределе современных технологий
200	1.2*1023	За пре­де­ла­ми со­вре­мен­ных тех­но­ло­гий
400	2.7*1034	Тре­бу­ет су­ще­ст­вен­ных из­ме­не­ний в тех­но­ло­гии
800	1.3*1051	Не раскрываем

В кон­це 1995 го­да уда­лось прак­ти­че­ски реа­ли­зо­вать рас­кры­тие шиф­ра RSA для 500-знач­но­го клю­ча. Для это­го с по­мо­щью се­ти Ин­тер­нет бы­ло за­дей­ст­во­ва­но 1600 ком­пь­ю­те­ров.

Сами авторы RSA рекомендуют использовать следующие размеры модуля n:

·   768 бит - для частных лиц;

·   1024 бит - для коммерческой информации;

·   2048 бит - для особо секретной информации.[11]

Третий немаловажный аспект реализации RSA - вычислительный. Ведь приходится использовать аппарат длинной арифметики. Если используется ключ длиной k бит, то для операций по открытому ключу требуется О(k²) операций, по закрытому ключу - О(k³) операций, а для генерации новых ключей требуется О(k⁴) операций.

Криптографический пакет BSAFE 3.0 (RSA D.S.) на компьютере Pentium-90 осуществляет шифрование со скоростью 21.6 Кбит/c для 512-битного ключа и со скоростью 7.4 Кбит/c для 1024 битного. Самая «быстрая» аппаратная реализация обеспечивает скорости в 60 раз больше.

По сравнению с тем же алгоритмом DES, RSA требует в тысячи и десятки тысяч раз большее время.

Криптосистема Эль-Гамаля

Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость[12].

В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно.

Основу системы составляют параметры p и g - числа, первое из которых - простое, а второе - целое.

Александр генерирует секретный ключ а и вычисляет открытый ключ y = g^а mod p. Если Борис хочет послать Александру сообщение m, то он выбирает случайное число k, меньшее p и вычисляет

y₁= g^k mod p  и

y₂= m Å y^k,

где Å означает побитовое сложение по модулю 2. Затем Борис посылает (y₁,y₂) Александру.

Александр, получив зашифрованное сообщение, восстанавливает его:

m = (y₁^a mod p) Å y₂.

Алгоритм цифровой подписи DSA, разработанный NIST (National Institute of Standard and Technology) и являющийся частью стандарта DSS частично опирается на рассмотренный метод.

Криптосистемы на основе эллиптических уравнений

Эллиптические кривые - математический объект, который может определен над любым полем (конечным, действительным, рациональным или комплексным). В криптографии обычно используются конечные поля. Эллиптическая кривая есть множество точек (x,y), удовлетворяющее следующему уравнению:

y² = x³ + ax + b,

а также бесконечно удаленная точка. Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения в криптосистемах RSA и Эль-Гамаля.

В реальных криптосистемах на базе эллиптических уравнений используется уравнение

y² = x³ + ax + b mod p,

где р - простое.

Проблема дискретного логарифма на эллиптической кривой состоит в следующем: дана точка G на эллиптической кривой порядка r (количество точек на кривой) и другая точка Y на этой же кривой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G.

Электронная подпись

В чем со­сто­ит про­бле­ма ау­тен­ти­фи­ка­ции дан­ных?

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

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

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

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

Итак, пусть име­ют­ся два поль­зо­ва­те­ля Александр и Борис. От ка­ких на­ру­ше­ний и дей­ст­вий зло­умыш­лен­ни­ка долж­на за­щи­щать сис­те­ма ау­тен­ти­фи­ка­ции.

От­каз (ре­не­гат­ст­во).

Александр за­яв­ля­ет, что он не по­сы­лал со­об­ще­ние Борису, хо­тя на са­мом де­ле он все-та­ки по­сы­лал.

Для ис­клю­че­ния это­го на­ру­ше­ния ис­поль­зу­ет­ся элек­трон­ная (или циф­ро­вая) под­пись.

Мо­ди­фи­ка­ция (пе­ре­дел­ка).

Борис из­ме­ня­ет со­об­ще­ние и ут­вер­жда­ет, что дан­ное (из­ме­нен­ное) со­об­ще­ние по­слал ему Александр.

Под­дел­ка.

Борис фор­ми­ру­ет со­об­ще­ние и ут­вер­жда­ет, что дан­ное (из­ме­нен­ное) со­об­ще­ние по­слал ему Александр.

Ак­тив­ный пе­ре­хват.

Владимир пе­ре­хва­ты­ва­ет со­об­ще­ния ме­ж­ду Александром и Борисом с це­лью их скры­той мо­ди­фи­ка­ции.

Для за­щи­ты от мо­ди­фи­ка­ции, под­дел­ки и мас­ки­ров­ки ис­поль­зу­ют­ся циф­ро­вые сиг­на­ту­ры.

Мас­ки­ров­ка (ими­та­ция).

Владимир по­сы­ла­ет Борису со­об­ще­ние от име­ни Александра .

В этом случае для за­щи­ты так­же ис­поль­зу­ет­ся элек­трон­ная под­пись.

По­втор.

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

Наи­бо­лее дей­ст­вен­ным ме­то­дом за­щи­ты от по­вто­ра яв­ля­ют­ся

* ис­поль­зо­ва­ние ими­тов­ста­вок,

* учет вхо­дя­щих со­об­ще­ний.

Возможные нарушения защиты сообщений,. посылаемых пользователем А пользователю В.

Электронная подпись на основе алгоритма RSA

Наи­бо­лее про­стым и рас­про­стра­нен­ным ин­ст­ру­мен­том элек­трон­ной под­пи­си яв­ля­ет­ся уже зна­ко­мый ал­го­ритм RSA. Ни­же оно бу­дет рас­смот­ре­на в ка­че­ст­ве при­ме­ра. Кро­ме это­го су­ще­ст­ву­ют еще десятки других схем цифровой подписи.

Предположим, что

 d,p,q - секретные, а е, n=pq - открытые.

Замечания.