Галуев Г.А. Математические основы криптологии

Подождите немного. Документ загружается.

101

можно толковать и как сложность закона генерации псевдослу-

чайной последовательности чисел. Если по достаточно длинно-

му отрезку этой последовательности нельзя ни статистически,

ни аналитически определить этот закон генерации, то в принци-

пе этим можно удовлетвориться.

И, наконец, третье требование должно гарантировать воз-

можность практической реализации генераторов псевдослучай-

ных последовательностей с

учетом требуемого быстродействия

и удобства практичного использования.

Рассмотрим теперь некоторые практические методы полу-

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

был метод, предложенный в 1946 году Д. фон Нейманом. Этот

метод базировался на том, что каждое последующее число в

псевдослучайной последовательности формировалось возведе-

нием предыдущего числа в квадрат и отбрасыванием

цифр с

обоих концов. Однако этот метод оказался ненадежным, и от не-

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

конгруэнтный способ. Его математическое выражение имеет

вид:

).(mod

mckgg

Здесь каждое последующее случайное число

1+n

g получа-

ется умножением предыдущего числа

g на k сложением с c и

взятием остатка от деления на

m. Главной проблемой здесь было

подобрать хорошие значения коэффициентов

k, c, m. Выбор в

качестве

k, c, m иррациональных чисел, требующих для своего

представления бесконечного числа знаков, практически не реа-

лизуем. Выбор почти иррациональных чисел представленных,

например, 4 байтами в формате с плавающей запятой, дает псев-

дослучайные последовательности с периодами всего лишь 1225

и 147 в зависимости от начального заполнения. Исследования

показали, что более эффективно вести вычисления в целых чис-

лах.

Для них, в частности, было показано, что при c = 0,

m 2= наибольшей период составит m/4 при k = 3+8j или k =

5+8j

и нечетном начальном числе. При этом при достаточно

больших

к последовательность производит впечатление случай-

102

ной. Дальнейшие исследования показали, что если

c нечетно, а k

= 1+4, то период можно увеличить до числа

m 2= . После дол-

гих поисков числа

k исследователи остановились на значениях k

= 69069 и k = 71365.

Интересный класс генераторов псевдослучайных последо-

вательностей основан на использовании

последовательностей

Фибоначчи. Классический пример такой последовательности

{0,1,1,2,3,5,8,13,21,34 …} - за исключением первых двух ее

членов, каждый последующий член равен сумме двух предыду-

щих.

Если брать только последнюю получающуюся в результате

суммирования цифру, то получим

{0,1,1,2,3,5,8,3,1,4 …} Если

ввести в схему Фибоначчи «бит переноса», который может

иметь начальные значения

0 или 1, то можно построить генера-

тор сложения с переносом, который по своим свойствам превос-

ходит конгруэнтные генераторы.

И, наконец, построение псевдослучайных последователь-

ностей с гарантированно хорошими для криптографии свойст-

вами (максимальная длина периода, равномерный спектр) воз-

можно путем использования аппарата и результатов теории ли-

нейных рекуррентных последовательностей над конечными по-

лями,

о которых мы подробно говорили на прошлых лекциях.

Получаемые при помощи рассмотренных методов псевдо-

случайные последовательности, используются в поточных крип-

тосистемах для игнорирования сообщений путем использования

различных типов шифров замены. Например, для шифрования

сообщений может быть использована та или иная модификация

известной уже вам системы Вернама:

⊕

, где

- псев-

дослучайная последовательность чисел, определяемая секрет-

ным ключом

Примерами стандартизованных алгоритмов блочных крип-

тосистем являются американский стандарт

DES (режим элек-

тронной кодовой книги

ЕСВ) и российский стандарт ГОСТ

28147-89 (режим простой замены). Поскольку описание этих ал-

горитмов носит закрытый характер, проиллюстрируем работу

блочных алгоритмов на примере описания работы криптосистем

103

с открытым ключом, в частности, системы на базе алгоритма

RSA.

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

Хеллмана.

Прежде чем перейти к описанию алгоритма функциониро-

вания

RSA криптосистемы с открытым ключом рассмотрим, ле-

жащий в ее основе, принцип работы схемы открытого распреде-

ления ключей, предложенной в 1976 году Диффи и Хеллманом.

Схема открытого распределения ключей предполагает, что

все пользователи знают некоторое простое число

Р и примитив-

ный элемент

a (1<a<P) конечного поля Галуа GF(p) (примитив-

ный элемент, а это такой элемент степени

a которого дают все

элементы поля

GF(p)). Такие элементы всегда существуют и их

число равно

(

(p)), где

- функции Эймера. Для выработки

общей секретной информации

К пользователи А и В должны

сделать следующее:

1. Пользователи

А и В независимо выбирают случайные

числа

и K

из интервала (1,…,р -1), называемые секретными

ключами пользователей.

2. Пользователи

А и В на основе известных параметров a и

р вычисляют величины: y

= a

(mod p); Y

= a

(mod p), кото-

рые являются открытыми ключами пользователей.

3. Пользователи

А и В обмениваются этими ключами по

открытому каналу связи (с подтверждением авторства, чтобы

избежать замены их кем - то другим, т.е. с использованием про-

цедуры аутентификации).

4. По полученным значениям

и y

каждый из пользова-

телей независимо вычисляет секретный параметр

К, который и

будет их общим сеансовым секретным ключом:

A: K=y

(mod p)=[a

]

(mod p)=a

(mod p)

B: K=y

(mod p)=[a

]

(mod p)=a

(mod p).

Стойкость такой системы зависит от сложности вычисле-

ния дискретных логарифмов в мультипликативной группе ко-

нечного поля в

F(p). Эта стойкость гарантирована тем, что до

настоящего времени не найдено быстрых алгоритмов нахожде-

ния

КАКВ

из

а, а

КА

, а

КВ

без вычисления

из а, а

КА

или К

из

а,

104

КВ

Описанная схема открытого распределения ключей совме-

стно с введенным понятием односторонней функции с секретом

послужили основой для создания принципа открывать соста-

вившего новое направление в области построения криптографи-

ческих систем. Такие системы получили название криптосистем

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

Основная идея принципа открытого шифрования заключа-

ется в следующем: если получатель секретного

сообщения вы-

берет одностороннюю функцию с секретом

(x) и сообщит по

открытому каналу отправителю эффективный алгоритм

ее

вычисления, то тот может вычислить значение функции

(M)=C

от сообщения

М и передать это значение по открытому каналу

получателю. Только тот, кто знает (в данном случае получатель)

секретный ключ

К, знает и алгоритм D

вычисления обратной

функции

-1

(c).

В общем виде криптографическая система с открытым

ключом представляет собой систему, включающую следующие

компоненты:

- пространство открытых текстов

;

- пространство шифротекстов

;

- пространство секретных ключей

;

- множество преобразований зашифрования

∈

CCMMCME

: ∈∈→

;

- множество преобразований расшифрования

KKD

, ∈

: CCMMMCD

∈∈→

При этом преобразования

и D

должны обладать сле-

дующими свойствами:

1. Для каждого

∈

преобразование

D является обрат-

ным к преобразованию

т.е.

MMED

)([

при всех

∈ .

2. По каждому выбранному ключу

∈

легко найти пару

обратимых преобразований Е

K..

3. Для всех CCMMKK

∈∈∈ величины E

(M) и D

(C)

105

легко вычисляются за полиномиальное время.

4. Почти для всех

∈

вычислительно невозможно из Е

вывести какое - либо легко вычисляемое преобразование, экви-

валентное

Свойство 4 отличает криптосистемы с открытым ключом

от традиционных криптосистем с секретным ключом, в которых

преобразования

и D

также зависят от секретного ключа К, но

знание преобразования

дает знание К и D

или наоборот, зна-

ние

позволяет определить К и Е

, поэтому преобразования

и D

либо оба известны, либо оба неизвестны. Это свойство 4

позволяет не засекречивать преобразование зашифрования

К,

делать его открытым для всех, кто хочет послать секретное со-

общение.

Так как в силу открытости любой злоумышленник имеет

доступ к преобразованию зашифрования Е

, то он может всегда

выбрать любой открытый текст и получить соответствующий

ему шифрованный текст. Поэтому системы с открытым ключом

должны быть всегда устойчивы к методам атаки по выбранному

открытому тексту.

Криптосистемы с открытым ключом обеспечивают только

практическую стойкость.

106

12. Алгоритм RSA и алгоритм Эль Гамаля работы

криптосистем с открытым ключом. Цифровая

подпись. Алгоритм цифровой подписи Эль Гамаля.

Алгоритм Ривеста (Rivest) - Шамира (Shamir) – Алде-

мана (Aldeman) – RSA(1978 год).

Одной из первых криптосистем с открытым ключом была

предложенная в 1978 году система на алгоритма

RSA. Как видно

название алгоритма,

RSA образовано из первых букв фамилий

авторов этого алгоритма. В его основе лежит использование сте-

пенной односторонней функции с секретом, которую мы рас-

сматривали на прошлых лекциях.

RSA относится к блочным ал-

горитмам, так как каждый блок ]1,0[

−

∈

nM открытого текста,

представленный как целое число из интервала

(1,2,…,n -1), пре-

образуются в блок ]1,0[

−

∈

nC шифрованного текста путем вы-

числения

),(mod)(

),(

nMMEC

где e, n – ключ преобразования зашифрования.

При расшифровании блок отрытого текста

М восстанавли-

вается также путем экспоненцирования, но с другой степенью

в качестве ключа расшифрования, т.е.

).(mod)(

),(

ncCDM

Зашифрование и расшифрование могут быть выполнены с

использованием быстрых алгоритмов экспоненцирования не бо-

лее чем за

][log0

n операций.

В основе алгоритма лежит известная уже теорема Эйлера,

согласно которой для каждого целого числа

М, взаимно просто-

го с модулем

n (т.е. MOD(M, n)=1) выполняется соотношение

),(mod1

)(

≡

где

)(n

- функция Эйлера, т.е. число целых чисел < n и

взаимно простых с

Можно показать, что если числа

e и d удовлетворяют соот-

ношению

)),((mod1 nde

≡

⋅

107

а ]1,1[

−

∈ nM взаимно просто с n, то

MnnM

=)(mod)](mod[,

что в свою очередь означает, что

MMED

nend

))((

),(),(

Действительно,

).(mod)(mod)](mod[ nMnnM

edde

Условие

))((mod1 nde

≡⋅

означает, что

)(1 ntde

+=⋅

для некоторого целого

Тогда

1() ()

()

(mod ) (mod ) (mod )

[ (mod )](mod ),

ed tn tn

nM nMM n

MM n n

ϕϕ

=⋅ =

где

1)(mod1)(mod)](mod[)(mod

)()(

===

⋅

nnnMnM

ttnnt

ϕϕ

Значит

.)](mod1[)(mod MnMnM

=⋅=

⋅

При наличии )(n

можно легко найти пару чисел е и d,

удовлетворяющих соотношению

)).((mod1 nde

≡⋅

Для этого выбирается число

е взаимно простое с )(n

, что

можно проверить с помощью алгоритма Евклида. Взаимная про-

стота нужна для разрешимости сравнения

))((mod1 nxe

≡⋅

относительно неизвестного

х. Число х=d определяется с

помощью алгоритма Евклида, определяющего числа

d и t, удов-

летворяющие соотношению 1)(

⋅

−⋅ tnde

, что и означает

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

)).((mod1 nde

≡⋅

При этом, сложность алгоритма Евклида не превосходит

][log0

n операций.

108

Все сказанное выше справедливо для произвольного цело-

го модуля

n. В алгоритме RSA модуль n есть произведение про-

стых чисел

p и q, т.е. n=p·q. Поэтому в данном случае

)1()1()(

−

⋅

−

= qpn

и любое простое число e>max(p,q) будет

взаимно простым с

)(n

, т.е. при выборе ключа зашифрования е

можно не применять алгоритм Евклида, а воспользоваться из-

вестными быстрыми тестами проверки числа

е на простоту.

Без знания простых сомножителей

p и q значение функции

)(n

, а значит и ключей е и d определить очень трудно. Поэтому

если делать открытыми числа

e и n, а число d держать в секрете,

то нахождение

М из С сводится к трудной задаче извлечения

корня степени

е из числа С по модулю n. Это и означает, что ал-

горитм

RSA может быть использован для построения криптоси-

стемы с открытым ключом, т.е. системы открытого шифрования,

когда преобразование зашифрования

),( ne

E открыто, а преобра-

зование расшифрования

),( nd

D держится в секрете.

С учетом описанного выше алгоритма

RSA работу крипто-

системы с открытым ключом можно представить в виде сле-

дующей последовательности действий:

1. Пользователь выбирает два больших простых числа

p и q

и вычисляет два произведения

⋅

).1)(1()( −

−

qpn

2. Затем пользователь выбирает случайное целое число е и

вычисляет число

d, удовлетворяющее условию

))((mod1 nde

≡

⋅

т.е.

)).1)(1(mod(1

−

≡

⋅

qpde

3. После этого пользователь публикует другим пользовате-

лям числа

е и n как свой открытый ключ, сохраняя при этом

найденное число

d в секрете как закрытый ключ.

4. Если

М сообщение, длина которого определяется по зна-

чению выражаемого им целого числа, должна быть в интервале

от

1 до n, то оно преобразуется в шифровку с возвращением в

степень

е числа М по модулю n и отправляется получателю

(пользователю, который знает ключ

109

).(mod nMC

5. Получатель сообщения (пользователь , у которого хра-

нится ключ

d) расшифровывает сообщение С, возводя его в сте-

пень

d по модулю n, т.е.

).(mod)(mod nMnCM

ded ⋅

Пример.

Пусть р=211, q=223 – простые числа. Тогда

n=p·q=47053,

46620)1)(1()( =−

−

qpn

. Выберем открытый

ключ

с = 16813 и вычислим секретный ключ расшифрования d

такой, что

,46620(mod116813))(mod(1

≡

⋅=

≡

⋅

dnde

откуда

d = 19837. Возьмем в качестве сообщения М название ал-

горитма, т.е.

RSA. Чтобы перевести RSA в число будем считать

букву

R= 18, S= 19, A = 1 по порядковому номеру в латинском

алфавите. На представление каждой буквы отведем по 5 бит

числа, представляющего открытый текст

М. Тогда слову RSA

будет соответствовать число

16501832)19)321((

⋅+⋅

С помощью открытого ключа

е получим шифровку:

1650)(mod == nMC

16813

3071)47053(mod

Получатель расшифрует эту шифровку с помощью секрет-

ного ключа

19837

(mod ) 3071

MC n==(mod 47053) 1650

Для полноты изложения отметим, что для алгоритма

RSA

существует малая вероятность того, что шифровка числа

М воз-

ведем в степень

е по модулю n может не изменить открытый

текст

М. Это следует из теоретического факта, что для каждого

значения

е существует, по крайней мере, 9 таких значений М,

что

).(mod nMM

≡

Например,

для n=p·q= 47·59=2773 это числа

М = 0,1,2773,2537,2303,235,2538,471,236.

В алгоритме

RSA вместо функции Эйлера )(n

можно ис-

пользовать функцию Кармайкла )(n

, которая для произвольно-

го целого числа определяется

110

⎪

⎩

⎪

⎨

⎧

≥=

−

....2)),(),...,2((

3,2,2

)(

ppnpHOK

tт

λλ

Для )(n

справедлива теорема Камайкла, обобщающая

теорему Эйлера: для любого целого

М, взаимно простого с чис-

лом

n, верно сравнение

).(mod1

)(

≡

Если теперь в алгоритме

RSA заменить )(n

на )(n

и при

n=p·q считать

),1,1(

)1,1(

)(

)( −−=

−−

= qpHOK

qpHOD

то получим модификацию

RSA на основе функции Кармайкла

).(n

Стойкость алгоритма

RSA можно оценить сверху сложно-

стью разложения целого числа

n на простые сомножители p и q с

последующим определением )(n

. Это весьма трудная задача.

Другим примером криптосистемы с открытым ключом яв-

ляется система открытого шифрования Эль Гамаля, предложен-

ная в 1985 году. Алгоритм, лежащий в основе этой системы,

предлагает следующую последовательность действий:

1. Отправитель

А и получатель В знают большое простое

число

Р. Сообщения М представляются целыми числами из ин-

тервала

{1, p} т.е. M=2,…, p -1. Отправитель А генерирует слу-

чайное число

},1{ pe

∈

, получатель В также генерирует случай-

ное число

d из интервала {1, p}.

2. Отправитель

А шифрует сообщение ключом е в виде

)(mod pCC

= и посылает его В.

3. Получатель В шифрует принятое сообщение

C своим

ключом

d в виде

)(mod pCC

и посылает его

А.

4. Отправитель

А «снимает» свой ключ операцией

111

)(mod pCC

−

и возвращает

С получателю В.

6. Получатель

В расшифровывает сообщение

).(mod pCM

d−

Стойкость этой криптосистемы с открытым ключом осно-

вана на том, что достаточно лично вычислить степень любого

целого числа, умножив его на самого себя, требуемое число раз.

В тоже время весьма трудно найти ключи

е и d, т.е. показатель

степени, в которую нужно возвести заданное число, чтобы полу-

чить другое заданное число. Это задача поиска дискретного ло-

гарифма некоторого числа

а по модулю n, которая еще более

сложна, чем разложение целого числа на простые сомножители.

Следует отметить, что специалисты в области криптологии

пока не очень доверяют алгоритмам открытого шифрования и

предпочитают их использовать только для реализации процедур

рассылки секретных ключей пользователям и аутентификации

сообщений (подтверждения подлинности сообщения и лица по-

славшего сообщения), в то

время как шифровку самых сообще-

ний предпочитают осуществлять классическими криптографиче-

скими методами замены или перестановки. Поэтому одним из

основных применений алгоритмов и систем открытого шифро-

вания является в настоящее время их использования при созда-

нии так называемой цифровой подписи, позволяющей подтвер-

дить подлинность получаемых пользователем сообщений. Рас-

смотрим принципы построения схемы

цифровой подписи.

Схема цифровой подписи.

Существенным недостатком многих электронных систем

передачи данных является отсутствие возможности проверки

подлинности и авторства пересылаемых документов. Это не по-

зволяет использовать такие системы для заключения юридиче-

ски признаваемых сделок или для передачи юридически под-

тверждаемых документов, что часто сводит на нет преимущест-

ва таких систем по сравнению с обычной почтовой пересылкой

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

тывается на бумажный носитель, подписывается физическим

112

лицом и удостоверяется печатью юридического лица. Эту про-

блему можно решить путем использования электронной цифро-

вой подписи, т.е. средства, позволяющего на основе криптогра-

фических методов надежно установить авторство и подлинность

документа.

Наиболее простой вид

цифровой подписи представляет со-

бой так называемый имитоприставка, которая реализуется в виде

шифра контрольной суммы по сообщению. В качестве такой

контрольной суммы по сообщению может использоваться какое

- либо число, отпечаток пальца, и др. Однако в полной мере под-

линность и авторство документа устанавливает электронная

цифровая подпись, позволяющая заменить при безбумажном

до-

кументообороте традиционные подпись и печать.

Цифровая подпись зависит от текста заверяемого докумен-

та, секретного ключа, доступного только заверяющему лицу, и

несекретного общедоступного ключа.

Для реализации схемы цифровой подписи требуется, чтобы

преобразования зашифрования

и расшифрования D

также

действовали на пространствах открытых текстов

и шифро-

текстов

и преобразование Е

было бы обратным преобразова-

нием к

, т.е.:

→

: CM

→

(M)]=M

для любого открытого текста

∈

Если теперь некоторый пользователь

А желает послать со-

общение

М пользователю В с подтверждением своего авторства,

то он может воспользоваться своим секретным ключом, т.е. пре-

образованием

K,A

, вычислить величину C=D

K,A

[M] и по-

слать это значение (это и будет цифровой подписью) пользова-

телю

В. в этом случае преобразование D

K,A

используется для

шифрования текста

М и цифровая подпись обратна алгоритму

открытого шифрования. Пользователь

В, также как и любой дру-

гой пользователь, знающий открытое преобразование

K,A

может

убедиться в авторстве сообщения

М вычислением этого сообще-

113

ния из соотношения

)],([)(

,,,

MDECEM

AKAKAK

и проверкой, является ли М осмысленным текстом. Т.е. здесь

K,A

действуют как преобразование расшифрования.

Авторство пользователя

А основано на том, что только он

знает секретное преобразование

K,A

. Злоумышленник, желаю-

щий подменить сообщение

М на другое сообщение

′

, должен

решить задачу нахождения такого значения

С, что

)(

CEM

′

В силу односторонней природы (используется односторон-

няя функция) преобразования сделать это крайне трудно.

Обычно на практике, для сокращения времени подписыва-

ния преобразования

применяется не для всего исходного

текста

М, а для некоторой его хэш-функции H(M) , которая ото-

бражает любое сообщение

М в сообщение H(M) фиксированно-

го малого размера. Другими словами, цифровая подпись имеет

вид

)].([

MHD

Пользователь

В, получив сообщение М и подпись к нему

K,A

может вычислить (функция хэширования общеизвестна) и

проверить выполнимость соотношения

).()]]([[

MHmHDE

AKAK

С учетом сказанного, общую схему цифровой подписи мо-

жет представить следующим образом: схема включает:

1. Пространство открытых сообщений },{

MM = к кото-

рым применяется алгоритм цифровой подписи.

2. Пространство секретных параметров },{

KK = которые

выбираются пользователем.

3. Алгоритм генерации за полиномиальное время пары

) - открытого и секретного ключей по выбранному пара-

метру

К.

4. Алгоритм подписи

Q, который вырабатывает значение Q

[М, D

], называемое цифровой подписью сообщению М.

5. Алгоритм проверки подписи, который проверяет пра-

114

вильность подписи и сообщение с использованием открытого

ключа

Рассмотрим теперь конкретный алгоритм цифровой подпи-

си, предложенный Эль Гамалем (1985)

Все пользователи знают большое простое число и прими-

тивный элемент

)1,2( −∈ pa по модулю Р. Секретная информа-

ция подписывающего пользователя

А состоит из двух частей:

)1,2( −∈ pX

- долговременный секретный ключ под-

писи выбирается случайно из интервала

)1,2( −p и хранится в

секрете.

)1,1( −∈ pK

- разовый секретный ключ подписи кон-

кретного сообщения, такой что 1)1,(

−

pKHOD

, т.е.

K вза-

имно просто с

p -1.

Открытая информация подписывающего тоже имеет 2 час-

ти:

1. )(mod

pay

= - открытый ключ подписи.

2. )(mod

par

= - первая из двух частей подписи (r,s).

Подписываемое сообщение представляется числом из ин-

тервала

(0,p -1) точнее его функцией хэширования H(M).

АЛГОРИТМ ПОДПИСИ СООБЩЕНИЯ М:

1. Пользователь А выбирает случайное число из интерва-

ла

(1, 1)P

−

, таким образом, чтобы НОД (, 1)1

−

2. Вычисляет

(mod 1)

−

т.е. число удовлетворяющее

сравнению 1(mod 1)

Kx P

⋅

≡− Именно для разрешимости этого

сравнения при выборе

K наложено условие его простоты,

1P − .

3. Вычисляем первую часть подписи )(mod

par

= .

4. Вычисляем вторую часть подписи по формуле

[

]

(mod 1)

SK MrX P

−

=− −.

На этом процедура выработки подписи

(r,S) к сообщению

М заканчивается, и эти данные M,r,S сообщаются получателям.

115

АЛГОРИТМ ПРОВЕРКИ ПОДПИСИ К СООБЩЕНИЮ М

По полученным данным

M, r, S и имеющемуся у получате-

ля открытому ключу отправителя

вычисляются величины

)(mod pa

и ).(mod pry

⋅ В случае выполнения равенства

)(mod)(mod prypa

⋅=

считается, что подпись верная.

Поясним работу алгоритмов. Рассмотрим проверяемое ра-

венство )(mod)(mod prypa

⋅= или сравнение

),(mod prya

⋅≡ решением которого и является числа r и s.

После подстановки

и r оно примет вид

).(mod paaa

SKrX

⋅≡

⋅

Учитывая свойства сравнений (теорема Эйлера - Ферма),

последнее эквивалентно сравнение по модулю

(Р – 1) вида:

).1(mod

−

≡

pSKrXM

Именно из этого сравнения подписывающий пользователь

вычисляет величину

).1(mod][

−⋅−=

−

pKrXMS

Особенностью алгоритмов цифровой подписи является на-

личие у подписывающего абонента секретного ключа

),(

xK .

При этом, в случае проверки, он предъявляет контролеру не сам

секретный элемент, а некоторые значение функции, вычисляе-

мое с помощью секретного ключа по случайному запросу кон-

тролера, доказывая тем самым, что он обладает секретом, путем

его косвенной демонстрации, путем вычислений. Именно отсю-

да появилось название «доказательство при нулевом знании»,

которое

получил протокол общения абонентов, когда абонент

доказывает, что он обладает секретом, не раскрывая самого сек-

рета. Алгоритмы «доказательства при нулевом знании» не явля-

ются собственно криптографическими, т.к. они служат для пере-

дачи сообщений типа « я знаю эту информацию». Однако, такие

алгоритмы совместно с алгоритмами цифровой подписи, шиф-

рования с открытым

ключом и открытого распределения ключей

позволяют организовывать более совершенные протоколы взаи-

116

модействия пользователей криптографической сети, которые

реализуют одновременно и подтверждение подлинности доку-

ментов и доказательство при нулевом знании.

Общая идея алгоритмов доказательства при нулевом зна-

нии состоит в том, что он может вычислять некоторую функ-

цию, зависящую от секретного

ключа и от аргументов, задавае-

мых проверяющим. Проверяющий, даже зная эти аргументы, не

может по данному ему значению функции восстановить секрет-

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

ряющий мог удостовериться в правильности ее вычисления, на-

пример, эта функция может представлять собой цифровую под-

пись выбранных им аргументов

Рассмотрим алгоритм доказательства при нулевом знании,

в основе которого лежит описанный ранее алгоритм

RSA:

1. Доказывающий

А и контролер В, оба знают идентифика-

тор

I и открытый ключ n, e, но А, кроме того, знает еще секрет-

ное число )(mod nIS

= , сформированное по секретному ключу

d. Сначала А генерирует случайное число Х и вычисляет

)(mod nXy

= . Затем он отсылает I,y к B.

2. После этого

В генерирует и передает А случайное число

3. Затем

А вычисляет и передает В число

).(mod nyxW

⋅=

4. Контролер В проверяет принадлежность идентификатора

I к А путем проверки тождества

).(mod nyIW

117

Список рекомендуемой литературы.

Лидл Р.,Нидеррайтер Г. Конечные поля. М.: Мир, 1998.

Том 1,2,822с.

Варфоломеев А., Пеленицин М. Методы криптографии и

их применение в банковских технологиях. Учебное посо-

бие. М.: МИФИ, 1995-116с.

Жельников В. Криптография от папируса до компьютера.

М.: АBF, 1997-336с.

Мельников В.В. Защита информации в компьютерных сис-

темах. М.: Финансы и статистика, 1997-425с.

Герасименко В.А., Малюк А.А. Основы защиты информа-

ции. М.: МИФИ, 1997-537с.

Фомичев В.М. Симметричные криптосистемы. Учебное

пособие. М.: МИФИ, 1995-325с.

Давыдова Е.В., Дмитриев И.Л., Курепкин И.А. Новые сред-

ства криптографической защиты информации. Учебное по-

собие. М.: МИФИ, 1996-132с.

118

119

Галуев Геннадий Анатольевич

МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОЛОГИИ:

Учебно-методическое пособие

ПО

КУРСУ

МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОЛОГИИ

Для студентов специальностей 075300,

075400, 075600.

всех

форм обучения

Ответственный за выпуск Галуев Г.А.

ЛР №020565 от 23 июня 1997г. Подписано к печати 24.05.2003 г.

Формат 60х80 1/16 Бумага офсетная.

Офсетная печать. Усл. п. л. 8,2. Уч.- изд. л. 8,0

<<C>>

Издательство Таганрогского государственного радиотехниче-

ского университета

ГСП 17 А, Таганрог,28, Некрасовский, 44

Типография Таганрогского государственного радиотех-

нического университета

ГСП 17 А, Таганрог,28, Энгельса, 1

120