Цифровая подпись на основе асимметричных криптосистем

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

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

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

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

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

Итак, цифровая подпись представляет собой относительно не­боль­шое количество дополнительной цифровой информации, пе­редаваемой вместе с подписываемым текстом. Протокол электронной цифровой подписи (ЭЦП) включает в себя две процедуры:

1) процедуру по­становки подписи; в ней используется секретный ключ отправителя сообщения;

2) процедуру проверки подписи, в ней используется открытый ключ от­правителя.

При формировании ЭЦП отправитель прежде всего вычис­ляет хэш-фун­кцию h (M) от подписываемого текста M. Вычисленное зна­чение хэш-функ­ции m= h (M) представляет собой один короткий блок информации m, зави­сящий от всего текста M в целом. Затем число m шифруется секретным ключом отправителя и результат шифрования представляет собой ЭЦП для дан­ного текста M.

При проверке ЭЦП получатель сообщения также вычис­ляет хэш-функцию m = h (M) принятого по каналу текста M по известному алгоритму хеширования. По­сле этого он расшифровает полученную вместе с текстом подпись при помощи открытого ключа отправителя и сравнивает, со­ответ­ствует ли полученный результат вычисленному значению m хэш-функции.

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

1.24. Хэш-функции

Хэш-функция предназначена для сжатия подписываемого документа M до нескольких десятков или сотен бит. Значение хэш-функции h (M) сложным образом зависит от документа M и не позволяет восстановить сам документ M. Хэш-функция h (^.) принимает в качестве аргумента сообщение (документ, файл) M произвольной длины и возвращает хэш-значение h (M)= m фикси­рованной длины. Таким образом, хэшированная информация является сжатым представлением основного сообщения произ­вольной длины. Иногда результат хэширования называют дайджестом сообщения.

Хэш-функция должна удовлетворять следующим условиям:

Ø хэш-функция должна быть однозначна;

Ø хэш-функция должна быть чувствительна к всевозможным изме­нениям в тексте M, таким, как вставки, выбросы, перестанов­ки и др.

Ø хэш-функция должна обладать свойством необратимости, то есть задача подбора документа M ', который обладал бы тре­буемым значением хэш-функции, должна быть вычислительно неразрешима;

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

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

Для построения хэш-функций, как правило, используется односто­ронняя функция f (^.), которая образует выходное значение длиной n при задании двух входных значений длиной n.

Этими входами являются блок исходного текста M_i и хэш-значение H_{i -1} предыдущего блока текста: H_i = f (M _i H _{i -1}).

M_i ¾¾¾¾® Однонаправленная ¾¾¾¾® H_i

H_{i -1} ¾¾¾¾®                     функция f

Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением всего сообщения M.

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