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

Хеширующая функция это функция "многие-к-одному", отображающая свои аргументы на ограниченное множество значений. Обычно это множество - диапазон натуральных чисел. Простая хеширующая функция - f(x) = 0 для всех целых x. Более интересна функция f(x) = x mod 37, которая отображает x в остаток от деления x на 37.

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

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

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

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

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