находиться b. Подписью является пара чисел: a и b. Случайное значение k должно храниться в секрете. Для проверки подписи необходимо убедиться, что

yaab mod p = gM mod p.

Каждая новая подпись требует нового значения k, и это значение должно выбираться случайным образом. Если злоумышленник раскроет k, используемое Алисой, он сможет раскрыть секретный ключ Алисы x. Если злоумышленник сможет получить два сообщения, подписанные при помощи одного и того же k, он сможет раскрыть x, даже не зная k.

Рассмотрим простой пример. Выберем p=11 и g=2. Пусть секретный ключ x=8. Вычислим

y=gx mod p = 28 mod 11 = 3.

Открытым ключом являются y=3, g=2 и p=11. Чтобы подписать M=5, сначала выберем случайное число k=9. Убедимся, что gcd(9,10)=1. Далее вычислим

a=gk mod p = 29 mod 11 = 6,

и затем с помощью расширенного алгоритма Евклида найдем b из уравнения

5=(8*6+9*b) mod 10.

Решение: b=3, а подпись представляет собой пару: a=6 и b=3. Для проверки подписи убедимся, что yaab mod p = gM mod p:

3663 mod 11 = 25 mod 11.

Шифрование/дешифрование

Некоторая модификация позволяет использовать криптосистему для шифрования/дешифрования сообщений.

Для шифрования сообщения M сначала выбирается случайное число k, взаимно-простое с p-1. Затем вычисляются:

a=gk mod p,

b=ykM mod p.

Пара (a,b) является шифротекстом. Отметим, что шифротекст в два раза длиннее открытого текста.

По сути описанное преобразование – это то же самое, что и экспоненциальный ключевой обмен по Диффи-Хеллману, за исключением того, что обмен по Диффи-Хеллману, за исключением того, что - это часть ключа, а при шифровании сообщение умножается на yk.

Хеш-функции

Односторонняя функция H применяется к сообщению произвольной длины M и возвращает значение h=H(M) фиксированной длины m. Многие функции позволяют значение фиксированной длины по входным данным произвольной длины, но однонаправленные (или односторонние) хеш-функции обладают рядом дополнительных свойств:

• зная M, легко вычислить h;
• при заданном h задача нахождения M, для которого H(M)=h, должна быть вычислительно-трудоемкой;
• при заданном M задача нахождения другого сообщения M’, для которого H(M)=H(M’), должна быть вычислительно трудоемкой.

Смысл применения однонаправленных хеш-функций и состоит в обеспечении для M уникального значения – «отпечатка пальца» сообщения. Если Алиса подписала M цифровой подписью с использованием хеш-функции H(M), а боб может создать другое сообщение M' отличное от M, для которого H(M)=H(M'), то Боб сможет утверждать, что Алиса подписала сообщение M'. В некоторых приложениях необходимо выполнение дополнительного требования, называемого устойчивостью к коллизиям. Смысл данного требования заключается в том, что задача нахождения двух случайных сообщений M и M', для которых H(M)=H(M’), должна быть вычислительно-трудоемкой (с экспоненциальным объемом перебора).

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

1. Алиса готовит две версии контракта: одну, выгодную для Боба, и другую, приводящую его к банкротству.
2. Алиса вносит несколько незначительных изменений в каждый документ и вычисляет хеш-функции. (Этими изменениями могут быть действия, подобные следующим: замена одного пробела комбинацией пробелов, вставка одного - двух пробелов перед возвратом каретки и так далее. Производя или не производя по одному изменению в каждой из 32 строк, Алиса может Легко получить 232 различных документов.)
3. Алиса сравнивает хеш-значения для каждого изменения в каждом из двух документов, разыскивая пару, для которой эти значения совпадают. (Если выходом хеш-функции является 64-битное значение, Алиса, как правило, сможет найти совпадающую пару выполнив 232 сравнений.) Таким образом, она получает два документа, дающих одинаковое значение хеш-функции.
4. Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только значение хеш-функции.
5. Спустя некоторое время, Алиса подменяет контракт, подписанный Бобом, другим, которого он не подписывал. Теперь она может убедить арбитра в том, что Боб подписал другой контракт.

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

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

Федеральный стандарт СШФ – SHS (алгоритм SHA)

Национальный Институт Стандартов США при участии АНБ разработал алгоритм вычисления хеш-функции SHA, используемый в алгоритме цифровой подписи DSA стандарта DSS.

Для любого входного сообщения длиной меньше 264 битов SHA выдает 160-битовый «дайджест» сообщения. Далее «дайджест» подается на вход DSA, который вычисляет подпись для сообщения. Подписывание «дайджеста» вместо сообщения часто повышает эффективность процесса, так как «дайджест» намного меньше, чем само сообщение. Тот же «дайджест» сообщения должен быть получен тем, кто проверяет подпись. При использовании SHA задача поиска сообщения, соответствующего данному «дайджесту», или двух различных сообщений с одинаковым «дайджестом» является вычислительно-трудоемкой. Любые изменения сообщения, произошедшие во время передачи, с очень высокой вероятностью приведут к изменению «дайджеста», и подпись не пройдет проверку.

Стандарт России – ГОСТ Р 34.11-94

Разработанная российскими криптографами хеш-функция описана в стандарте ГОСТ 34.11-94. В ней используется блочный шифр ГОСТа 28147-89, хотя теоретически может использоваться любой блочный шифр с 64-битным блоком и 256-битным ключом. Хеш-функция выдает 256-битное значение.

Еще стоит отметить такие известные хеш-функции, как MD2, MD4, MD5 и RIPEMD-160.