Шифрование/дешифрование. 
Обзор современных средств криптографии

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

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

a=g^k mod p,.

b=y^kM mod p.

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

Для дешифрования (a, b) вычисляются По сути описанное преобразование — это то же самое, что и экспоненциальный ключевой обмен по Диффи-Хеллману, за исключением того, что обмен по Диффи-Хеллману, за исключением того, что — это часть ключа, а при шифровании сообщение умножается на y^k.

Хеш-функции

Односторонняя функция 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 строк, Алиса может Легко получить 2³² различных документов.)
• 3. Алиса сравнивает хеш-значения для каждого изменения в каждом из двух документов, разыскивая пару, для которой эти значения совпадают. (Если выходом хеш-функции является 64-битное значение, Алиса, как правило, сможет найти совпадающую пару выполнив 2³² сравнений.) Таким образом, она получает два документа, дающих одинаковое значение хеш-функции.
• 4. Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только значение хеш-функции.
• 5. Спустя некоторое время, Алиса подменяет контракт, подписанный Бобом, другим, которого он не подписывал. Теперь она может убедить арбитра в том, что Боб подписал другой контракт.

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

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