Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 253

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 247 248 249 250 251 252 < 253 > 254 255 256 257 258 259 .. 311 >> Следующая

MdA (mod Ал)] (mod NB).
Хотя идея весьма проста,- в учебном варианте алгоритма RSA она совершенно бесполезна, поскольку модуль функции RSA, принадлежащей Алисе, может оказаться больше, чем модуль функции RSA, принадлежащей Бобу. В этом случае "внутренняя обертка" зашифрованного текста, представляющая собой целое число, всегда будет больше, чем модуль, использованный для ее "внешней обертки".
Несмотря на это следует отметить, что в прикладной схеме RSA, как шифрования, так и цифровой подписи, сообщение "заворачивается" только после обработки с помощью рандомизированной схемы заполнения. В таком случае системные пользователи должны применять модули одинакового размера, поскольку как отправители, так и получатели должны согласовывать схему заполнения (padding) и распаковки ("unpadding").
Если системные пользователи используют модули одинакового размера, "двойное заворачивание" работает прекрасно. Если "внутренняя обертка" превосходит модуль "внешней обертки", пользователь просто "отрезает" один бит (например, старший) от "внутренней обертки". Чтобы "заворачивание" стало возможным, оставшееся целое число должно быть меньше модуля "внешней обертки". Напомним, что получатель такого зашифрованного текста проверит целостность данных. На этапе верификации получатель может восстановить отрезанный бит с помощью метода проб и ошибок. Вот в чем заключается идея описанного метода.
Итак, пусть lA^I = \Nb\ = к. Обозначим через Padding(M, г) G {0,1}к рандомизированное заполнение сообщения М с помощью случайного числа г. Тогда сообщение М, посланное Алисой Бобу в "двойной обертке" и снабженное зашифрованной подписью TBOS, выглядит следующим образом.
Padding (М, rfA (mod NA) d]dB (mod Nb) -
Описав схему шифрования TBOS, укажем три преимущества, которыми она обладает.
Глава 16. Сильная и доказуемая стойкость схем цифровой подписи 627
• Схема позволяет создавать компактные зашифрованные тексты: размер текста зашифрованной подписи совпадает с размером текста RSA без подписи, а также с размером подписи RSA без шифрования. По этой причине схема получила название "двух зайцев — одним выстрелом". Это свойство весьма привлекательно во многих электронных коммерческих приложениях, в которых необходимо пересылать через Internet короткие сообщения (например, номер кредитной карточки), соблюдая секретность и гарантируя невозможность отрицания авторства. В этих приложениях схема TBOS позволяет создавать одну короткую шифрограмму. Это не только обеспечивает эффективность, но и упрощает разработку протокола электронной коммерции.
• Невозможность отрицать авторство гарантируется непосредственно: получатель Боб, "развернувший" зашифрованный текст, снабженный зашифрованной подписью, и, возможно, восстановивший "отрезанный" бит, обнаруживает подпись Алисы: Padding (М, r)dA (mod Na) ¦ Любой посредник может верифицировать эту подпись, применяя обычную процедуру.
• Доказательства стойкости схемы TBOS основаны на стойкости прикладных схем заполнения RSA и носят редукционный характер. Несмотря на то что они основаны на модели случайного оракула, редукционные доказательства используют только общеизвестные неразрешимые задачи (задача RSA, определение 8.4 и предположение 8.3 из раздела 8.7).
Докажем теперь, что Боб всегда может правильно расшифровать зашифрованную подпись. Это очевидно, если Na < Nb- Для ситуации, когда Na > Nb с приблизительной вероятностью 1/2, получаем следующее.
а = Padding (М, r)dA (modNA) > NB-
Однако, поскольку \Na\ = \Nb\ = к,
a<NA< 2к.
Следовательно, отбрасывая старший бит
о <— а — 1 ,
получаем,
а' < 2к-г < NB.
Иначе говоря, Боб может правильно восстановить величину а'. В дальнейшем будем считать, что в ходе верификации Боб сам определяет, следует ему восстанавливать "отрезанный" бит или нет.
628
Часть V. Методы формального доказательства стойкости
Алгоритм 16.4. Двух зайцев RSA-TBOS
одним выстрелом: схема зашифрованной подписи
Параметры ключа
Пусть к — четное положительное целое число. Обозначим параметры открытого и закрытого ключей RSA, принадлежащих отправителю Алисе (соответственно получателю Бобу), как (А^д, ед), (АГд, d^) (соответственно (ЛГ^ев), (АГв,с?в)), причем lA^I = \Nb\ = к.
Пусть G и Н — две функции хэширования, удовлетворяющие условиям
Н : {0,1}п+ко н-» {О, I}*1 и G : {0, l}kl н-» {0,1}п+к° , где к = n + ko + ki,a числа 2~~ко и 2~kl — пренебрежимо малы.
Шифрование подписи
Когда Алиса снабжает сообщение М G (0,1}п зашифрованной подписью, она выполняет следующие инструкции.
1. г «-и {0,1}*°.
2. со «- Н{М || г).
3. s *— G{co) © (М || г). If s || со > NA goto 1. c'«-(s || u)dA (mod NA). If d > NB,d ^d -2k~\ с <- deB (mod NB). Послать сообщение с Бобу.
4. 5. 6. 7. 8.
Расшифровка подписи
Когда Боб расшифровывает криптограмму с, полученную от Алисы, он выполняет такие инструкции.
1. d *- cdB (ггкхШв).
2. If d > Na отказать. /л-с'ел (modA^). Представить число р в виде s || со. М || г «- G(co) © s. If Н(М || г) = w, return М. <7 «_ с' + 2*-1.
If с7 > Na, отказ.
9. /л- с"^ (гшхШд).
Предыдущая << 1 .. 247 248 249 250 251 252 < 253 > 254 255 256 257 258 259 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed