Симметричная криптография и цифровая подпись

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

Но существуют ли механизмы цифровой подписи, построенные вокруг симметричной криптографии?

Некоторые вспомнят классический пример с третьей доверенной стороной. Например, Алиса и Боб обмениваются документами, есть третья сторона — Дэн. Алиса и Боб доверяют Дэну, поэтому они заранее делятся с ним своими секретными ключами шифрования. Теперь Дэн может легко проверять аутентичность сообщений и подтверждать ее каждому из участников.

И вот, Алиса шифрует документ со своим ключом и посылает Бобу. Боб не знает ключа Алисы и не может расшифровать сообщение, он посылает сообщение Дэну (ему все доверяют). Боб также сообщает, что документ, кажется, от Алисы. Дэн знает ключ Алисы и расшифровывет документ, далее он шифрует его с ключом Боба и отправляет документ ему. Боб может расшифровать документ и таким образом убедиться, что он был действительно от Алисы.

Но у этой схемы много ограничений. Например, участникам нужно как-то передать Дэну секретные ключи по незащищенным каналам связи. Еще необходимо доверять третьей стороне, что не всегда возможно.

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

Такой алгоритм существует и его придумал лауреат премии Тьюринга, Лесли Лэмпорт.

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

Алиса хочет подписывать свои документы. Для этого она создает 256 пар случайных 256-битных чисел. Это будет приватным ключом Алисы. Длина такого ключа — 128 килобит (256 бит * 256 * 2).

Далее Алиса хеширует каждое число из своего приватного ключа. Это публичный ключ, он тоже состоит из 512-ти 256-битных чисел. Этот публичный ключ Алиса может выложить в сети и объявить, что с его помощью можно проверять ее подпись.

Алиса хочет подписать документ. Для этого она хеширует его, получая 256-битный хеш. Для каждого бита из этого хеша Алиса выбирает одно из соответствующих 256-битных значений приватного ключа. Если N-ый бит равен нулю, то выбирается первое число из N-ной пары приватного ключа, если единице, то выбирается второе число. В итоге Алиса получает подпись размером в 64 килобита. Эту подпись можно отправить вместе с документом в каком-нибудь контейнере.

Боб получил документ Алисы и 64 килобита ее подписи. Теперь Боб пытается проверить подпись. Как ему это сделать?

Боб пропускает документ через хеш-функцию и получает 256-битный хеш. Далее для каждого бита хеша Боб выбирает одно из соответствующих 256-битных значений публичного ключа Алисы. Правило такое же как при подписи: для N-го бита хеша мы смотрим в N-ую пару публичного ключа и выбираем первое или второе число.

Теперь у Боба есть 64 килобита данных. Будем называть это проверочным значением. Боб может захешировать числа из подписи, предоставленной Алисой, и сравнить каждое из получившихся чисел с числами из проверочного значения. Если совпало, то документ действительно был отправлен Алисой.

У этого алгоритма немало проблем. Как минимум, Алиса не может повторно использовать тот же приватный ключ. Выходит, подпись-то — одноразовая! К тому же, подпись, полученная по этому алгоритму, — достаточно большая. Но подход этот очень надежный и простой в реализации.

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

Рассмотрим пример.

Вы покупаете квартиру в новостройке на стадии строительства. Во время покупки для вас оформят договор долевого участия (ДДУ), причем оформят в электронной форме.

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

Далее приватный ключ вашей подписи становится бесполезным. Обычно он выдается на время и сервис инвалидирует ключ через полгода-год с момента сделки.

В такой модели недостаток подписи Лэмпорта не кажется столь серьезным. Если порой достаточно одноразовой подписи, то алгоритм применим в таких областях, фактически, без изменений. А размер подписи в 64 килобита можно и потерпеть.