Xreferat.com » Рефераты по информатике и программированию » Баричев С. Криптография без секретов

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

бло­ков со­об­ще­ния. Из по­лу­чен­но­го 64-раз­ряд­но­го чис­ла вы­би­ра­ет­ся от­ре­зок Ир дли­ной р бит.

Ими­тов­став­ка пе­ре­да­ет­ся по ка­на­лу свя­зи по­сле за­шиф­ро­ван­ных дан­ных. На при­ем­ной сто­ро­не ана­ло­гич­ным об­ра­зом из при­ня­то­го со­об­ще­ния выделяется? ими­тов­став­ка и срав­ни­ва­ет­ся с по­лу­чен­ной откуда?. В слу­чае не­сов­па­де­ния ими­тов­ста­вок со­об­ще­ние счи­та­ет­ся лож­ным.

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

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

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

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

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



Система

с открытым ключом

Система

с открытым ключом






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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ал­го­ритм RSA

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

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

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

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

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

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

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

xp-1 = 1 (mod p) (1)

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

xp = х (mod p) (2)

для любого х.

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

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

xp=(x-1+1)p= C(p,j)(x-1)j=(x-1)p+1 (mod p),

0jp

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

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

n 2 3 4 5 6 7 8 9 10 11 12
(n) 1 2 2 3 2 6 4 6 4 10 4

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

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

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

x(n) = 1 (mod n).

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

Еe,n: xxe (mod n)

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

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

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

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

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

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

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

x =(x0, x1, ..., xn-1), xZn , 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.

  1. Расшифруем полученное зашифрованное сообщение (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 = gk mod 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.


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

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

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

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

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

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

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

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

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

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

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

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

Под­дел­ка.

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

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

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

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

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

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

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

По­втор.

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

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

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

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









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

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

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

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

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

Замечания.

1. Разложение по n дает: (n)=(p-1)(q-1); зная (n) и e, можно найти d.

2. Из e и d можно найти кратность (n); кратность (n) позволяет определить делители n.

Пусть DATA - передаваемое Александром Борису сообщение.

Александр подписывает DATA для Бориса при передаче :

EeB,nB { EdA,nA {DATA}}.

При этом он использует:

  • закрытый ключ EdA,nA Александра,

  • открытый ключ EeB,nB Бориса.

Борис может читать это подписанное сообщение сначала при помощи закрытого ключа EdВ,nВ Бориса с целью получения

EdA,nA {DATA} = EdB,nB {EeB,nB {EdA,nA {DATA}}}

и затем - открытого ключа EeA,nA Александра для получения

DATA = EeA,nA { EdA,nA {DATA}}.

Таким образом, у Бориса появляется сообщение DATA, посланное ему Александром.

Очевидно, что данная схема позволяет защититься от нескольких видов нарушений.

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

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

Данная схема позволяет при решении многих конфликтных ситуаций обходиться без посредников.

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


Исходный текст

Исходный текст

Исходный текст


Подпись

Исходный текст ’






В 1991 г. Национальный институт стандартов и технологии (NIST) предложил для появившегося тогда алгоритма цифровой подписи DSA (Digital Signature Algorithm) стандарт DSS (Digital Signature Standard), в основу которого положены алгоритмы Эль-Гамаля и RSA. 13

Цифровая сигнатура

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

Цифровая сигнатура - это строка символов, зависящая как от идентификатора отправителя, так и содержания сообщения.


сообщение

сигнатура







Цифровая сигнатура

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

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

Рас­смот­рим ти­пич­ную схе­му циф­ро­вой сиг­на­ту­ры.

Пусть Е - функция симметричного шифрования и f - функция отображения некоторого множества сообщений на подмножество мощности р из последовательности {1, ..., n}.

Например р=3 и n=9. Если m - сообщение , то в качестве f можно взять функцию f(m) = {2, 5, 7}.

Для каждого сообщения пользователь А выбирает некоторое множество ключей K=[K1, ..., Kn} и параметров V={v1, ...,vn} для использования в качестве пометок сообщения, которое будет послано В. Множества V и V’={E(v1,K1) ..., E(vn,Kn)} посылаются пользователю В и заранее выбранному посреднику С.

Пусть m - сообщение и idm - объединение идентификационных номеров отправителя, получателя и номера сообщения. Если f({idm, m}), то цифровая сигнатура m есть множество K’=[Ki, ..., Kj}. Сообщение m, идентификационный номер idm и цифровая сигнатура К’ посылаются В.

V, V'


сообщение, K'




V, V'




Получатель В проверяет сигнатуру следующим образом. Он вычисляет функцию f({idm, m}) и проверяет ее равенство К’. Затем он проверяет, что подмножество {vi, ...,vj} правильно зашифровано в виде подмножества {E(vi,Ki) ..., E(vj,Kj)} множества V’.

В кон­фликт­ной си­туа­ции В по­сы­ла­ет С сообщение m, иден­ти­фи­ка­ци­он­ный но­мер idm и мно­же­ст­во клю­чей K’, ко­то­рое В объ­яв­ля­ет сиг­на­ту­рой m. То­гда по­сред­ник С так же, как и В, бу­дет спо­со­бен про­ве­рить сиг­на­ту­ру. Ве­ро­ят­ность рас­кры­тия двух со­об­ще­ний с од­ним и тем же зна­че­ни­ем функ­ции f долж­на быть очень ма­ла. Что­бы га­ран­ти­ро­вать это, чис­ло n долж­но быть дос­та­точ­но боль­шим, а чис­ло р долж­но быть боль­ше 1, но мень­ше n.

Ряд не­дос­тат­ков этой мо­де­ли оче­ви­ден:

  • долж­но быть третье ли­цо - по­сред­ник, ко­то­ро­му до­ве­ря­ют как по­лу­ча­тель, так и от­пра­ви­тель;

  • по­лу­ча­тель, от­пра­ви­тель и по­сред­ник долж­ны об­ме­нять­ся су­ще­ст­вен­ным объ­е­мом ин­фор­ма­ции, пре­ж­де чем бу­дет пе­ре­да­но ре­аль­ное со­об­ще­ние;

  • пе­ре­да­ча этой ин­фор­ма­ции долж­на осу­ще­ст­в­лять­ся в за­кры­том ви­де;

  • эта ин­фор­ма­ция ис­поль­зу­ет­ся край­не не­эф­фек­тив­но, по­сколь­ку мно­же­ст­ва K, V, V’ ис­поль­зу­ют­ся толь­ко один раз.

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

Хэш-функции

Использование цифровой сигнатуры предполагает использование некоторых функций шифрования:

S = H(k, T),

где S - сигнатура, k - ключ, T - исходный текст.

Функция H(k, T) - является хэш-функцией, если она удовлетворяет следующим условиям:

  1. исходный текст может быть произвольной длины;

  2. само значение H(k, T) имеет фиксированную длину;

  3. значение функции H(k, T) легко вычисляется для любого аргумента;

  4. восстановить аргумент по значению с вычислительной точки зрения - практически невозможно;

  5. функция H(k, T) - однозначна14.

Из определения следует, что для любой хэш-функции есть тексты-близнецы - имеющие одинаковое значение хэш-функции, так как мощность множества аргументов неограниченно больше мощности множества значений. Такой факт получил название «эффект дня рождения».15

Наиболее известные из хэш-функций - MD2, MD4, MD5 и SHA.

Три алгоритма серии MD разработаны Ривестом в 1989-м, 90-м и 91-м году соответственно. Все они преобразуют текст произвольной длины в 128-битную сигнатуру.

Алгоритм MD2 предполагает:

  • дополнение текста до длины, кратной 128

    Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
    Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

    Поможем написать работу на аналогичную тему

    Получить выполненную работу или консультацию специалиста по вашему учебному проекту
    Нужна помощь в написании работы?
    Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: