Основы современной криптографии


Цифровые подписи, основанные на симметричных криптосистемах - часть 9


Предположим, что наша схема рассчитана на 2L

сообщений. Обозначим через

 i-тую комбинацию  l-того уровня. Если нумерацию комбинаций и уровней начинать с нуля, то справедливо следующее условие: 0 Ј i < 2L–l, а i-ая проверочная комбинация l-того уровня рассчитана на 2l

сообщений с номерами от  iЧ2l

до (i+1)Ч2l–1  включительно. Число комбинаций нижнего, нулевого уровня равно 2L, а самого верхнего, L-того уровня – одна, она и является контрольной комбинацией всех 2L сообщений, на которые рассчитана схема.

На каждом уровне, начиная с первого, проверочные комбинации рассчитываются по следующей формуле:

,

где через A||B обозначен результат конкатенации двух блоков данных A и B, а через H(X) – процедура вычисления хэш-функции блока данных X.

При использовании указанного подхода вместе с подписью сообщения необходи­мо передать не N–1, как в исходном варианте, а только log2N

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

Пример организации проверочных комбинаций в виде двоичного дерева в схеме на восемь сообщений при­ведена на рисунке 4.1. Так, при передаче сообще­ния № 5 (контрольная комбинация выделена рамкой) вместе с его под­писью должны быть переданы кон­трольная комбинация сообщения № 4 (C4(0)), общая для сообщений №№ 6–7 (C3(1)) и общая для сообще­ний №№ 0–3 (C0(2)), все они выделе­ны на рисунке другим фоном.

При проверке подписи значение C5(0) будет вычислено из сообщения и его подписи, а итоговая контрольная комбинация, подлежащая сравнению с эталонной, по следующей формуле:

C=C0(3)=H(C0(2)||H(H(C4(0)||C5(0))||C3(1))).

Необходимость отправлять вместе с подписью сообщения дополнительную информацию, нужную для проверки подписи, на самом деле не очень обременительна. Действительно, в системе на 1024=210 подписей вместе с сообщением и его подписью необходимо дополнительно передавать 10 контрольных комбинаций, а в системе на 1048576=220




- Начало -  - Назад -  - Вперед -



Книжный магазин