1.6. Специальные схемы цифровой подписи

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

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

1.6.1. Схема цифровой подписи с восстановлением сообщения

Весьма важной для многих применений является схема цифровой подписи с восстановлением сообщения (message recovery). Такая схема специфицирована в международном стандарте ISO/IEC 9796. Рассмотрим ее детально.

Стандарт не специфицирует конкретный алгоритм подписи, но указывает, что это должно быть отображение к бит на к бит: если М - подписываемое сообщение, то \M\ = k,\SignsL(M)\ = к .Этому условию удовлетворяет, к примеру, схема RSA, для которой S = Md (rnodn), где ed = l(mod(p(rc)).

Схема подписи с восстановлением сообщений отличается от обычной схемы цифровой подписи (схемы с дополнением, или «с

1.

аппендиксом») тем, что используется для подписания сообщений ограниченной длины и не требует криптографических хеш-функций, но позволяет восстановить сообщение только из подписи, без пере-дачи открытого текста. В схеме подписи «с аппендиксом» от подпи-сывающего к проверяющему передается М, Signsk [h(M)), а в схеме

подписи с восстановлением сообщений, только Signsk(M). Кроме

того, как станет ясно далее, такая схема подписи требует предварительной обработки подписываемых сообщений, в частности их вы-равнивания (message padding), если это необходимо.

Введем следующие обозначения: к - длина подписи в битах, d - длина подписываемого сообщения М в битах (требуется, чтобы

z - число байтов в сообщении, причем z = [d/8~\,

г - Sz~d + 1 - число, на единицу большее количества добавляемых

при выравнивании бит, r = |~(A:-l)/16~| - наименьшее целое, такое,

что строка из 21 байт включает по меньшей мере к-1 бит.

Например, параметры могут быть выбраны так: к - 1024 бита, d— 150 бит. Тогда z— 19 байт, г = 3 бита, t = 64 байта.

Процедура генерации подписи по ISO/IEC 9796 представляет собою последовательное выполнение пяти этапов.

«Выравнивание» сообщения (padding) — дополнение нулевыми битами. Пусть М - исходное сообщение. К нему добавляются нуле-вые биты таким образом, что длина получаемого в результате сооб-щения MP становится кратной 8 бит, т. е. равна целому числу байт:

MP = 0Г-1|М , где 1 < г < 8. Число байтов в MP равно z-

MP = mz II mz_! II... II m21| щ, \/Щ -1 байт.

Расширение сообщения (extension). MP расширяется за счет дописывания слева последовательности всех байтов MP, взятых справа налево в цикле, пока длина сообщения не станет равной t байт:

ME = ME, II MEt_x II... IIМЕ2II ME,, V|ME\ = 1 байт,

66 Запечников С. В. Криптографические протоколы и их применение

Введение избыточности (redundancy). ME преобразуется в

MR = MR2i [I MRlt_x II... IIMR2II MR,

таким образом, что:

а) t байт ME дополняются t избыточными байтами по следую-щему правилу:

Ш2М =MEnXгде S(u) - «теневая функция» байта и, которая определяется сле-дующим образом: и = и2\\щ, Щ = |и2| = 4- битовые строки длиной полбайта, т. е.

v /

б) выполняется преобразование MR2„ - г®MR2z (для того, чтобы проверяющий подпись мог восстановить длину исходного сооб-щения). Так как d = 8z - г +1, для этого достаточно знать г и г. Эти значения могут быть впоследствии получены из MR.

Усечение и усиление (truncating and forcing). MR преобразуется в /:-битовое целое число IR (intermediate integer), = k . Оно фор-мируется следующим образом:

а) k-\ младших бит МЛ дополняются слева единичным битом;

б) младший байт получившегося результата иг || и, замещается на и{ |(0110. Это делается, чтобы гарантировать, что IR = 6(modl6).

Генерация подписи. Число IR подписывается, используя любой механизм подписи, в котором длина подписи s равна длине подпи-сываемого сообщения, т. е. = |.у| = k .

В случае, если используются схемы подписи RSA или Рабина, подпись по ISO/IEC 9796 формируется следующим образом (е - от-крытый ключ схемы RSA или Рабина, п - модуль схемы, d - секрет-ный ключ). Вычисляется так называемый репрезентативный эле- (дО

мент: /?/? = //?, если е нечетное или е четное и — =1

I Л J

(т. е. символ Якоби числа IR, интерпретируемого как целое число по

f IR^\

модулю пу равен единице), и RR- IR/2, если е четное и — =-1.

п

\ /

Подпись генерируется под репрезентативным элементом:

= min{(fltf)rf modn, n-((RR)d mod и)}.

Процедура проверки подписи по ISO/IЕС 9796 состоит из по-следовательного выполнения трех этапов, на каждом из которых либо получается положительный результат, либо подпись отклоняется. Подпись принимается тогда и только тогда, когда выполнение каж-дого из этапов завершилось с положительным результатом.

Открытие подписи (signature opening). Пусть s — подпись. Выполнение этого этапа заключается в следующем:

а) к подписи s с целью восстановления 1R' применяется открытое преобразование проверки цифровой подписи, например для схе-мы RSA вычисляется se mod л = IR';

б) подпись отклоняется, если IR' не является строкой длиной к бит со старшим битом, равным единице, или если младшая тетрада не равна 0110.

Восстановление сообщения.

Из целого числа IR' конструируется битовая строка MR' длиной It байт. Для этого:

а) к-1 младших бит числа IR' обозначается X;

б) если и41| щ || и21| 0110 - четыре младшие тетрады X, младший байт X замещается на я"1 (и4) || и2;

в) MR' получается путем дописывания к X слева от нуля до 15 нулевых бит таким образом, что результирующая строка имеет длину 2г байт.

Вычисляются значения гиг следующим образом:

а) из 21 байт MR' вычисляются t сумм: MR^i®S(MR,2i_l), 1 б) г - наименьшее из г, для которого MR'2i © S (MR'2i_,) ф 0;

68 Запечников С. В. Криптографические протоколы и их прішеиеиие

в) г - самая младшая тетрада суммы, найденной на шаге «б»;

ПОДПИСЬ ОТКЛОНЯеТСЯ, ЄСЛИ НЄ ВЫПОЛНеНО уСЛОВИе 1 < >jgj < 8 (в шест-

надцатеричной системе счисления).

2.3. Из MR' конструируется строка MP' длиной z байт сле-дующим образом:

а)вычисляется МР.= MR'Tl_x для 1 б) подпись отклоняется, если г—1 старших бит MP' не все равны нулю;

в) М' - это 8z-r+l младших бит MP'.

3. Проверка избыточности. Подпись s проверяется следующим образом:

а) из М' конструируется строка MR" путем применения шагов (1) - (3) процедуры генерации подписи (т. е. производится ее по-вторный пересчет);

б) подпись принимается тогда и только тогда, когда k-1 младших бит MR" равны к-1 младшим битам MR'.