Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии

Хэш-функции

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

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

нове схемы ( М , Е к(к(М)У) строятся алгоритмы вычис­

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

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

Е к{(М,Нк2( М ) ) , ( Е к1(М),Нк2( М ) ) ,

( Е к](М),Нк2( Е к1(М )) ),

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

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

361

Iлава 13

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

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

§13.5. Возможные атаки на функции хэширования

Простейшая атака с целью создания поддельного сообще­ ния, применимая к любой хэш-функции, состоит в следую­ щем. Злоумышленник может осуществить генерацию некото­ рого числа (гу) сообщений, вычислить значения их сверток и сравнить получившиеся значения с известными значениями сверток некоторого множества (из г2) переданных ранее со­ общений. Атака окажется успешной при получении хотя бы одного совпадения. Вероятность успеха Р можно оценить на основании парадокса “дней рождений”. Известно, что эта ве­ роятность оценивается по формуле

г\*1

Р * 1 - е 2* ,

362

Хэш-функции

где п — длина свертки, е — основание натуральных логариф­ му

мов. Наибольшей эта вероятность становится при гх ~г2 - 2 2.

В этом случае ее значение приблизительно равно 0,63.

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

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

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

Е к(х ) = х ), коллизии ключей (то есть пар различных ключей,

для которых выполняется равенство Е к(х) = Ек,(х )) и т. п.

Контрольные вопросы

1.Для каких целей применяются хэш-функции?

2.Перечислите основные требования, предъявляемые к хэшфункциям.

3.Почему нельзя использовать в качестве хэш-функций ли­ нейные отображения?

4.Сравните требования, предъявляемые к ключевым и бесключевым хэш-функциям.

363

Глава 14

Цифровые подписи

§ 14.1. Общие положения

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

Цифровая подпись позволяет решить следующие три за­ дачи:

—осуществить аутентификацию источника сообщения,

—установить целостность сообщения,

—обеспечить невозможность отказа от факта подписи конкретного сообщения.

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

365

Для реализации схемы цифровой подписи необходимы два алгоритма:

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

и

— алгоритм ее проверки.

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

Надежность схемы цифровой подписи определяется сложностью следующих трех задач:

366

цифровые подписи

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

—создания подписанного сообщения, то есть нахождения хотя бы одного сообщения с правильным значением подписи;

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

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

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

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

367

I лава 14

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

—кто должен нести ответственность в случае, если под­ писанные сделки не состоятся;

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

—какова ответственность уполномоченного по сертифи­ катам в случае, если открытый ключ будет сфальсифициро­ ван;

—какова ответственность владельца секретного ключа в случае его утраты;

—кто несет ответственность за плохую реализацию сис­ темы в случае повреждения или разглашения секретного клю­ ча;

—каков порядок разрешения споров и т. п.

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

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

1) схемы на основе систем шифрования с открытыми ключами;

2) схемы со специально разработанными алгоритмами вычисления и проверки подписи;

3) схемы на основе симметричных систем шифрования. Рассмотрим их более подробно.

368

цифровые подписи

§14.2. Цифровые подписи на основе шифрсистем с открытыми ключами

Идея использования систем шифрования с открытыми ключами для построения систем цифровой подписи как бы заложена в постановке задачи. Действительно, пусть имеется пара преобразований (Е, В \ первое из которых зависит от открытого ключа, а второе — от секретного. Для того чтобы вычислить цифровую подпись 5* для сообщения, владелец секретного ключа может применить к сообщению М второе преобразование В: 8 = В ( М ) . В таком случае вычислить

подпись может только владелец секретного ключа, в то время как проверить равенство Е(8) = М может каждый. Основ­

ными требованиями к преобразованиям Е и В являются:

— выполнение равенства М = Е ( В ( М ) ) для всех сооб­

щений М;

— невозможность вычисления значения В{М) для задан­ ного сообщения М без знания секретного ключа.

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

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

369

I лава 14

тивник получит только шифртекст, а во втором — и откры­ тый, и шифрованный тексты.

Очевидно, что рассмотренная схема цифровой подписи на основе пары преобразований (Е, О) удовлетворяет требова­ нию невозможности подделки, в то время как требование не­ возможности создания подписанного сообщения не выполне­ но: для любого значения каждый может вычислить значение М = Е (8) и тем самым получить подписанное сообщение.

Требование невозможности подмены сообщения заведомо выполняется, так как преобразование Е взаимно однозначно.

Для защиты от создания злоумышленником подписанного сообщения можно применить некоторое взаимно-однозначное отображение К : М I—>М , вносящее избыточность в пред­ ставление исходного сообщения, например, путем увеличения

его длины, а затем уже вычислять подпись 5 = В ( М ) . В этом случае злоумышленник, подбирая $ и вычисляя значения

М —Е ( 8 ) , будет сталкиваться с проблемой отыскания та­

ких значений й , для которых существует прообраз М. Если отображение К выбрано таким, что число возможных образов Й значительно меньше числа всех возможных последова­ тельностей той же длины, то задача создания подписанного сообщения будет сложной.

Другой подход к построению схем цифровых подписей на основе систем шифрования с открытым ключом состоит в ис­ пользовании бесключевых хэш-функций. Для заданного со­ общения М сначала вычисляется значение хэш-функции И(М) , а затем уже значение подписи 5 = 0 ( Н ( М ) ) . Ясно,

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

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

370