Смекни!
smekni.com

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

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

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.

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

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 = (37) (mod 33) = 2187 (mod 33) = 9,

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

ШТ3 = (27) (mod 33) = 128 (mod 33) = 29.

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

ИТ1 = (93) (mod 33) = 729 (mod 33) = 3,

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

ИТ3 = (293) (mod 33) = 24389 (mod 33) = 2.

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

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

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

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

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

Важная проблема практической реализации - генерация больших простых чисел. Решение задачи «в лоб» - генерация случайного большого числа n (нечетного) и проверка его делимости на множители от 3 вплоть до n0.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 бит, то для операций по открытому ключу требуется О(k2) операций, по закрытому ключу - О(k3) операций, а для генерации новых ключей требуется О(k4) операций.

Криптографический пакет 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 и вычисляет

y1 = gkmod p и

y2 = m Å yk,

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

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

m = (y1a mod p) Å y2.

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

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

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

y2 = x3 + ax + b,

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

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

y2 = x3 + ax + b mod p,

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

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

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

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

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

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

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

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

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