Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
— кто несет ответственность за плохую реализацию системы в случае повреждения или разглашения секретного ключа;
— каков порядок разрешения споров и т. п.
Поскольку данные проблемы носят юридический, а не
технический характер, то для их разрешения нужен юридически правильно заключенный договор, оформленный стандартным образом на бумаге.
В настоящее время предложено несколько принципиально различных подходов к созданию схем цифровой подписи. Их можно разделить на три группы:
1) схемы на основе систем шифрования с открытыми ключами;
2) схемы со специально разработанными алгоритмами вычисления и проверки подписи;
3) схемы на основе симметричных систем шифрования.
Рассмотрим их более подробно.
368
цифровые подписи
§ 14.2. Цифровые подписи на основе шифрсистем с открытыми ключами
Идея использования систем шифрования с открытыми ключами для построения систем цифровой подписи как бы заложена в постановке задачи. Действительно, пусть имеется пара преобразований (?, D), первое из которых зависит от открытого ключа, а второе — от секретного. Для того чтобы вычислить цифровую подпись S для сообщения, владелец секретного ключа может применить к сообщению M второе преобразование D: S = D(M). В таком случае вычислить
подпись может только владелец секретного ключа, в то время как проверить равенство E(S) = M может каждый. Основными требованиями к преобразованиям E и D являются:
— выполнение равенства M = E(D(M)) для всех сообщений М\
— невозможность вычисления значения D(M) для заданного сообщения M без знания секретного ключа.
Отличительной особенностью предложенного способа построения цифровой подписи является возможность отказаться от передачи самого подписываемого сообщения М, так как его можно восстановить по значению подписи. В связи с этим подобные системы называют схемами цифровой подписи с восстановлением текста.
Заметим, что если при передаче сообщение дополнительно шифруется с помощью асимметричного шифра, то пара преобразований (E, D), используемая в схеме цифровой подписи, должна отличаться от той, которая используется для шифрования сообщений. В противном случае появляется возможность передачи в качестве шифрованных ранее подписанных сообщений. При этом более целесообразно шифровать подписанные данные, чем делать наоборот, то есть подписывать шифрованные данные, поскольку в первом случае про-
369
І лава 14
тивник получит только шифртекст, а во втором — и открытый, и шифрованный тексты.
Очевидно, что рассмотренная схема цифровой подписи на основе пары преобразований (E, D) удовлетворяет требованию невозможности подделки, в то время как требование невозможности создания подписанного сообщения не выполнено: для любого значения S каждый может вычислить значение M = E(S) и тем самым получить подписанное сообщение. Требование невозможности подмены сообщения заведомо выполняется, так как преобразование E взаимно однозначно.
Для защиты от создания злоумышленником подписанного сообщения можно применить некоторое взаимно-однозначное отображение R: M I—> M, вносящее избыточность в представление исходного сообщения, например, путем увеличения
его длины, а затем уже вычислять подпись S = D(M). В этом случае злоумышленник, подбирая S и вычисляя значения M = E(S) , будет сталкиваться с проблемой отыскания таких значений й , для которых существует прообраз М. Если отображение R выбрано таким, что число возможных образов Й значительно меньше числа всех возможных последовательностей той же длины, то задача создания подписанного сообщения будет сложной.
Другой подход к построению схем цифровых подписей на основе систем шифрования с открытым ключом состоит в использовании бесключевых хэш-функций. Для заданного сообщения M сначала вычисляется значение хэш-функции h(M), а затем уже значение подписи S = D(h(M)). Ясно,
что в таком случае по значению подписи уже нельзя восстановить сообщение. Поэтому подписи необходимо передавать вместе с сообщениями. Такие подписи получили название цифровых подписей с дополнением. Заметим, что системы подписи, построенные с использованием бесключевых хэш-функций, заведомо удовлетворяют всем требованиям, предъ-
370
цифровые подписи
являемым к цифровым подписям. Например, невозможно создание сообщения с известным значением подписи, поскольку бесключевая хэш-функция должна быть однонаправленной.
В качестве системы шифрования с открытыми ключами можно использовать, например, систему RSA.
§ 14.3. Цифровая подпись Фиата — Шамира
Рассмотрим подход к построению схемы цифровой подписи, основанной на сложности задач факторизации больших целых чисел и извлечения квадратного корня в кольце вычетов. Идея построения схемы принадлежит А. Фиату и А. Шамиру (см. гл. 12). Приведем одну из модификаций схемы, предложенную ими совместно с У. Фейджем. В ней реализуется цифровая подпись с дополнением.
Пусть h — некоторая хэш-функция, преобразующая исходное сообщение в битовую строку длины т. Выберем различные простые числа р и q и положим n = pq . В качестве секретного ключа каждый абонент должен сгенерировать т различных случайных чисел а{,а2,...,ат є Zn . Открытым ключом объявляется набор чисел bl9b2,...,bm є Zw, где