Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
16.5 Зашифрованная подпись
Для того чтобы предотвратить фальсификацию и обеспечить секретность письма, автор должен подписать его и запечатать в конверт и лишь затем отправить его адресату. Как правило, в практике обмена секретными сообщениями цифровая подпись и шифрование данных выполняются отдельно и непосредственно: отправитель подписывает и шифрует сообщение, а получатель расшифровывает его и верифицирует подпись.
622
Часть V. Методы формального доказательства стойкости
На подпись и шифрование затрачиваются машинные циклы, а дополнительные биты удлиняют сообщение. Стоимость криптографических операций обычно выражается через относительное увеличение размера сообщения и затраты времени на вычисления, выполняемые отправителем и получателем. В прямой процедуре 1 шифрования-подписания стоимость доставки аутентичного секретного сообщения зависит от стоимости цифровой подписи и шифрования. Как правило, такой способ оказывается неэкономным.
Зашифрованная подпись (signcryption) — это конструкция с открытым ключом, позволяющая эффективно реализовать процедуру подписи и шифрования сообщений. Она обеспечивает три необходимые функциональные возможности: секретность, аутентичность и невозможность отречения от авторства. Поскольку I на практике эти возможности довольно часто необходимы одновременно, Жень (Zheng) предложил понятие зашифрованной подписи [309], которое эффективным образом объединяет в себе процедуру подписания и шифрования сообщений.
16.5.1 Схема зашифрованной подписи Женя
Жень предложил две очень похожие схемы зашифрованной подписи под названием SCSI и SCS2 [309]. Они используют две весьма близкие схемы цифровой подписи Эль-Гамаля — SDSS1 и SDSS2 соответственно.
Напомним, что в тройной схеме Эль-Гамаля фиксатор г в цифровой подписи I (г, s, е) обычно вычисляется по формуле г = gk(modp), где числа д и р представ- I ляют собой компоненты открытого ключа, а передача к является целым числом, I независящим от величин, использованных в предыдущих подписях. Кроме того, I в схеме цифровой подписи Шнорра (алгоритм 10.4), представляющей собой ва- I риант тройной схемы Эль-Гамаля, отправитель не обязан посылать получателю I фиксатор. Способ, которым создается цифровая подпись, позволяет получателю I восстанавливать фиксатор с помощью формулы г = gsye(modp).
Итак, если отправитель сообщения (автор подписи) вычисляет фиксатор особым образом, так что его может восстановить только легальный получатель (с помощью своего открытого ключа), то значение фиксатора можно использовать как I симметричный ключ, общий для отправителя и получателя, а для обеспечения I секретности сообщения — применять симметричное шифрование.
Вот как выглядит приблизительное описание схемы зашифрованной подписи I Женя: для обеспечения секретности в качестве симметричного ключа шифрования сообщений используется восстанавливаемое значение фиксатора в тройной I схеме цифровой подписи Эль-Гамаля. Это краткое и абстрактное описание можно | представить в виде тройки (с, е, s), где с — зашифрованный текст, созданный симметричным алгоритмом шифрования, а (е, s) — второй и третий элемент тройной подписи. Первый элемент тройки Эль-Гамаля (как правило, обозначаемый как г) может восстановить только предназначенный получатель.
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи
623
Поскольку схемы SCS1 и SCS2 очень похожи, мы опишем только схему SCS1 (см. алгоритм 16.5.1.1). Для простоты изложения в спецификации используются обозначения, принятые в схеме Эль-Гамаля, за исключением того, что вместо символа г используется символ К (значение фиксатора в тройной схеме цифровой подписи Эль-Гамаля), обозначающий симметричный ключ.
Покажем, что система, описанная алгоритмом 16.3, одновременно является криптосистемой и схемой цифровой подписи, т.е. 1) процедура расшифровки, выполняемая Бобом, действительно восстанавливает исходный текст, снабженный зашифрованной подписью Алисы, и 2) Алиса подписывает сообщение.
Для того чтобы доказать первое утверждение, достаточно показать, что Боб может восстановить число К = gB(modp), зашифрованное Алисой. Процедура расшифровки выглядит следующим образом.
К = {деуАГХв (modp) = (<f ВГ {дХАХВТ = yf+XA) = yMmodp).
Итак, действительно, Боб восстанавливает число К, зашифрованное Алисой. Используя число К\, выделенное из числа К, Боб, конечно, может расшифровать текст с и восстановить сообщение М.
Чтобы доказать второе утверждение, заметим, что после вычисления значения К = gB(modp), тройка (К2,е, s) образует тройную подпись Эль-Гамаля на восстановленном сообщении М. Следовательно, алгоритм 16.3 действительно является схемой цифровой подписи.
16.5.1.1 Выводы
• Эффективность. Схема SCSI весьма эффективна как с вычислительной, так и коммуникативной точек зрения. Для того чтобы создать зашифрованную подпись отправитель сообщения выполняет одно возведение в степень, одно хэширование и одно симметричное шифрование. Для того чтобы выполнить обратную операцию, получатель выполняет приблизительно такой же объем вычислений, если выражение {деулУхв можно переписать в виде дыхву^в и применить алгоритм 15.2. С точки зрения ширины полосы пропускания, учитывая, что симметричное шифрование сообщения не приводит к увеличению размера сообщений, зашифрованную подпись можно уложить в 2\q\ бит плюс длина сообщения. Эта длина совпадает с шириной пропускания при передаче подписи Эль-Гамаля. Более того, применение симметричного алгоритма шифрования делает схему пригодной для эффективной пересылки основного объема данных (например, с помощью блочного шифра в режиме СВС). По существу, схему SCSI можно рассматривать как гибридную схему шифрования с открытым ключом (см. раздел 15.4).
