Иванов М.А. КМЗИ сети

Суть протокола объясняет следующая его «физическая» реализация. Абонент В выбирает случайный бит b, записывает его на листе бумаги, запирает этот лист в ящик ( yB суть криптогра-

фический аналог этого ящика), оставляя ключ ( xB ) у себя, и по-

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

точно таким же образом узнает с [4].

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

Протокол подбрасывания монеты

1. Абонент А выбирает случайным образом некоторое число

zА абоненту В.

2.Абонент В сообщает абоненту А свое предположение о четности или нечетности yA .

3.Абонент А сообщает абоненту В числа xА и yA , а также дает возможность убедиться, что n является числом Блюма.

4. Абонент В проверяет равенства yA xA2 mod n и zA yA2 mod n.

Таким образом, абонент А передает абоненту В квадратичный вычет по модулю целого числа Блюма, а В пытается угадать, является ли его примитивный квадратный корень четным или нечетным. Выбор в качестве n целого числа Блюма – гарантия отсутствия у z A двух квадратных корней различной четности, оба

из которых являются квадратичными вычетами. Можно предложить следующую «физическую» реализацию приведенного протокола. А бросает монету в колодец. А видит исход бросания монеты, но не может его изменить. В находится далеко и не может

191

его увидеть. Однако А в конце концов может позволить В подойти поближе и заглянуть в колодец [4].

6.4. Протоколы битовых обязательств

Если из приведенной выше схемы Блюма вычленить шаги 1, 2

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

или привязки к биту (bit commitment). Шаги 1 и 2 в этом протоколе называются этапом привязки, а шаг 4 – этапом открытия бита. В данной схеме для значения yB , в которое «упаковывается» бит b, используется термин блоб (blob), абонент А называется получателем, а абонент В – отправителем. Схема привязки к биту классический пример криптографического примитива, который используется в многочисленных прикладных протоколах.

Идеальная конструкция блоба должна обеспечивать одновременное выполнение двух требований:

1)гарантии безопасности отправителя – после выполне-

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

2)гарантии безопасности получателя – на этапе открытия бита отправитель может открыть блоб либо только как 0, либо как 1.

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

Описанный протокол привязки к биту гарантирует безусловную безопасность отправителя. В то же время безопасность получателя основывается на недоказанном предположении о вычислительной неразрешимости задачи дискретного логарифмирования. Существует другой тип протоколов привязки к биту, в которых безопасность получателя безусловна, а безопасность отправителя основывается на недоказанном предположении. Учитывая, что такая асимметрия типична для многих типов криптографических протоколов, иногда строятся двойственные протоколы такого рода [4].

192

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

Рассмотрим схему разделения доступа Шамира. Пусть n –

число участников протокола, GF(p) – конечное поле из p элементов, p – простое, p > n. Поставим в соответствие каждому

i-му участнику ненулевой элемент поля i , i 1, n, и положим

0 0.

Схема разделения доступа Шамира

Стадия распределения долей секрета s0 . Дилер СРС выра-

батывает t – 1 независимых равномерно распределенных на

Стадия восстановления секрета. Учитывая, что любой многочлен степени t – 1 однозначно восстанавливаются по его значениям в произвольных t точках, то любые t участников могут восстановить многочлен f(x), т.е. найти значение секрета по формуле s0 f 0 . По этой же причине для

любых t – 1 участников, любых значений si и любого секрета s0 существует только один соответствующий им многочлен, для которого справедливо si f i и s0 f 0 .

Схемы подобного типа находят применение при построении пороговых структур доступа и носят название (n, t)-пороговых СРС. Такие схемы, например, позволяет владельцу некоей секретной информации распределить эту информацию при хранении на n своеобразных ее дубликатов таким образом, что ему для восстановления секрета достаточно получить доступ к любым t из них. При этом никакие t – 1 дубликатов не предоставляют никакой информации об этом секрете [4].

194

6.6. Протоколы электронной подписи

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

с помощью электронной подписи получатель документа может доказать, что он принадлежит отправителю, при этом автор подписи не сможет оспорить факт отправки подписанного документа; электронную подпись невозможно подделать, только або-

нент, чья подпись стоит на документе, мог подписать данный документ; электронная подпись – неотъемлемая часть документа, пе-

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

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

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

Схема электронной подписи включает в себя:

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

пространство исходных сообщений;

максимальное число подписей (signature bound), которые могут быть получены в данной схеме без замены секрет-

ной информации;

195

алгоритм G генерации ключей – полиномиальный (от n) ве-

роятностный алгоритм, формирующий по заданному параметру n пару

kАsecret , kАpublic ,

где kАsecret – секретный ключ подписывающего (абонента А),

kАpublic – соответствующий открытый ключ проверяющего (абонента В);

алгоритм S формирования подписи сообщения – полино-

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

kАsecret подпись s для сообщения M ;

алгоритм V проверки (verification) подписи – полиномиаль-

ный вероятностный алгоритм, дающий на выходе при заданных сообщению M, открытому ключу kАpublic и возмож-

ной подписи sχ либо значение 1, когда подпись сообщения принимается, либо 0, когда подпись отвергается.

Подпись s SkАsecret M называется допустимой для сообще-

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

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

196

V M , s, kApublic

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

В классической схеме электронной подписи предполагается, что подписывающий (абонент А) знает содержание документа M, который он подписывает; проверяющий (абонент В), зная открытый ключ проверки подписи, может проверить правильность подписи в любое время без какого-либо разрешения или участия претендента А. При создании электронной подписи по классической схеме (рис. 6.5) претендент А выполняет следующую последовательность действий:

применяет к исходному сообщению M хеш-функцию h(x) и формирует хеш-образ или дайджест (message digest) сообщения h M ;

при необходимости дополняет хеш-образ до требуемой длины;

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

дания подписи:

s DAsecret Ext h M .

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

верификатор В применяет к тексту полученного сообщения хеш-функцию; дополняет в случае необходимости хеш-образ сообщения

до требуемой длины (на рис. 6.5 рассматривается случай, когда расширение Ext h M не требуется);

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

подписи и сравнивает полученное значение EApublic s с найденным на предыдущем шаге Ext h M ; при положи-

197

тельном результате сравнения подпись признается, в противном случае – отвергается [4].

Рис. 6.5. Классическая схема создания и проверки электронной подписи

6.6.1. Протокол электронной подписи RSA

Криптосистема с открытым ключом RSA часто используется не только для шифрования, но и для построения схемы элек-

Схема электронной подписи RSA

1.Абонент А (претендент) вычисляет хеш-образ h M сообщения M.

2.Абонент А зашифровывает полученное значение h M на

своем секретном ключе d, вычисляя подпись

198

sh M d mod n,

иотправляет абоненту В пару документ-подпись M , s .

3.Абонент В (верификатор) расшифровывает s на открытом ключе e отправителя, т.е. вычисляет

se mod n.

4.Абонент В вычисляет хеш-образ h M полученного со-

общения и проверяет равенство h M se mod n.

В случае положительного результата проверки подпись принимается, в противном случае – отвергается.

Вкачестве хеш-функции в схеме подписи RSA используются функции семейства MD.

6.6.2.Протокол электронной подписи Шнорра

Впротоколе аутентификации Шнорра интерактивность требуется только для того, чтобы получить от верификатора В слу-

чайный запрос xB . Если бы у претендента А был бы надежный

источник случайности на замену генератору ПСЧ В, пользующийся доверием верификатора В, то протокол можно было бы сделать неинтерактивным. Фиат и Шамир предложили способ преобразования схемы аутентификации в протокол электронной подписи. Если M – подписываемое сообщение, а h(x) – криптографическая хеш-функция, вместо обращения к верификатору (получателю) претендент (отправитель) вычисляет h M и ис-

пользует ее вместо запроса xB . Этот прием универсален, так как применим и к другим протоколам аутентификации.

Пусть p и q – такие простые числа, что q делит (p – 1). Пусть g Z p такое, что

gq 1 mod p , g ζ 1.

199

Пусть хеш-функция h(x) отображают пары значений yA, M на множество 0, 1, ..., 2t - 1`. В качестве своего секретного ключа kАsecret абонент А выбирает случайное число из Zq . Затем

он вычисляет

g-kA(secret) mod p

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

ключа kA( public).

Схема электронной подписи Шнорра

1. Абонент А выбирает случайное число x1A Zq , после чего вычисляет

Если оно выполняется, В признает подлинность подписи, в противном случае – отвергает.

Стойкость приведенной схемы сильно зависит от свойств используемой хеш-функции. Если противник может по заданной паре yA, M находить другое сообщение M', M' ζ M, для кото-

рого

h yA, M = h yA, M' ,

он может осуществить подделку подписи. Для этого после перехвата сообщения M и подписи x2 A , s он должен найти указан-

200