преодолен, поскольку это невозможно в рамках подхода Диффи-Хеллмана. Для практического использования такой схемы, рассчитанной на подпись N сообщений, отправителю необходимо хранить N ключей подписи, а получателю - N ключей проверки, что достаточно неудобно. Эта проблема может быть решена в точности так же, как была решена проблема ключей для множественных битовых групп - генерацией ключей подписи для всех N сообщений из одного мастер-ключа и свертывание всех проверочных комбинаций в одну контрольную комбинацию с помощью алгоритма вычисления хэш-функции. Такой подход решил бы проблему размера хранимых ключей, но привел бы к необходимости вместе подписью каждого сообщения высылать недостающие N-\ проверочных комбинаций, необходимых для вычисления хэш-функции массива всех контрольных комбинаций отдельных сообщений. Ясно, что такой вариант не обладает преимуществами по сравнению с исходным. Упомянутыми выше авторами был предложен механизм, позволяющий значительно снизить остроту проблемы. Его основная идея - вычислять контрольную комбинацию (ключ проверки подписи) не как хэш-функцию от линейного массива проверочных комбинаций всех сообщений, а попарно - с помощью бинарного дерева. На каждом уровне проверочная комбинация вычисляется как хэш-функция от конкатенации двух проверочных комбинаций младшего уровня. Чем выше уровень комбинации, тем больше отдельных ключей проверки "учитывается" в ней. Предположим, что наша схема рассчитана на 2 сообщений. Обозначим через /-тую комбинацию /-того уровня. Если нумерацию комбинаций и уровней начинать с нуля, то справедливо следующее условие: О < / < 2", а /-ая проверочная комбинация /-того уровня рассчитана на 2 сообщений с номерами от i-2 до (/+1)-2-1 включительно. Число комбинаций нижнего, нулевого уровня равно 2, а самого верхнего, Z-того уровня - одна, она и является контрольной комбинацией всех 2 сообщений, на которые рассчитана схема. На каждом уровне, начиная с первого, проверочные комбинации рассчитываются по следующей формуле:

с) =я(с« II с;),).

где через А\\В обозначен результат конкатенации двух блоков данных А и В, а через ЩХ) - процедура вычисления хэш-функции блока данных X. Уровень

0: Сп

Рис. 4.1. Двоичное дерево для схемы ЭЦП на 8 сообщений

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

Пример организации проверочных комбинаций в виде двоичного дерева в схеме на восемь сообщений приведена на рисунке 4.1. Так, при передаче сообщения № 5 (контрольная комбинация выделена рамкой) вместе с его подписью должны быть переданы контрольная комбинация сообщения № 4 (С*"), общая для сообщений №№ 6-7 (Cj) и общая для сообщений №№ 0-3 (Cq ), все они выделены на рисунке другим фоном.

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

С = = я(сГ II ЖжсГ II cf) II с;>)).

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

теме на 1024=2" подписей вместе с сообщением и его подписью необходимо дополнительно передавать 10 контрольных комбинаций, а в системе на 1048576 = 2" подписей - всего 20 комбинаций. Однако, при большом числе подписей, на которые рассчитана система, возникает другая проблема - хранение дополнительных комбинаций, если они рассчитаны предварительно, или их выработка в момент формирования подписи.

Дополнительные контрольные комбинации, которые передаются вместе с подписью и используются при ее проверке, вырабатываются при формировании ключа проверки по ключу подписи и могут храниться в системе и использоваться в момент формирования подписи, либо вычисляться заново в этот момент. Первый подход предполагает затраты дисковой памяти, так как необходимо хранить 2-2 значений хэш-функции всех уровней, а второй требует большого объема вычислений в момент формирования подписи. Можно использовать и компромиссный подход - хранить все хэш-комбинации начиная с некоторого уровня /, а комбинации меньшего уровня вычислять при формировании подписи. В рассмотренной выше схеме подписи на 8 сообщений можно хранить все 14 контрольных комбинаций, используемых при проверки (всего их 15, но самая верхняя не используется), тогда при проверке подписи их не надо будет вычислять заново. Можно хранить 6 комбинаций начиная с уровня 1 (Сц , Cj , , С3 , Сц , Cj ), тогда при проверке подписи сообщения № 5 необходимо будет заново вычислить комбинацию С\ а остальные (сС*) взять из таблицы, и т.д.. Указанный подход позволяет достичь компромисса между быстродействием и требованиям к занимаемому количеству дискового пространства. Отметим, что отказ от хранения комбинаций одного уровня приводит к экономии памяти и росту вычислительных затрат примерно вдвое, то есть зависимость носит экспоненциальный характер.

4.3. Функции хэширования

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

например, Н(М) может быть 128 или 256 бит, тогда как М может быть размером в мегабайт или более.

Функция хэширования может служить для обнаружения модификации сообщения. То есть, она может служить в качестве криптографической контрольной суммы (также называемой кодом обнаружения изменений (MDC - Manipulation Detection Code) или проверкой целостности сообщения (MIC - Message Integrity Check)).

Теоретичес1си возможно, что два различных сообщения могут быть сжаты в одну и ту же свертку (так называемая ситуация "столкновения"). Поэтому для обеспечения стойкости функции хэширования необходимо предусмотреть способ избегать столкновений. Полностью столкновений избежать нельзя, поскольку в общем случае количество возможных сообщений превышает количество возможных выходных значений функции хэширования. Однако вероятность столкновения должна быть низкой.

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

1. Н может быть применена к аргументу любого размера;

2. Выходное значение Н имеет фиксированный размер;

3. Н(х) достаточно просто вычислить для любого х. Скорость вычисления хэш-функции должна быть такой, чтобы скорость выработки и проверки ЭЦП при использовании хэш-функции была значительно больше, чем при использовании самого сообщения;

4. Для любого у с вычислительной точки зрения невозможно найти X, такое что Н(х)=у.

5. Для любого фиксированного х с вычислительной точки зрения невозможно найти х Ф х, такое что Н(х)=Н(х).

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

Свойство 4 эквивалентно тому, что Н является односторонней функцией. Стойкость систем с открытыми ключами зависит

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

Классическая хэш-функция является открытым преобразованием. В специальном случае, когда она зависит от ключа, результат ее вычисления носит название кода аутентификации сообщения (MAC - Message Authentication Code).

4.3.1. Функция хэширования SHA

Алгоритм безопасного хэширования SHA (Secure Hash Algorithm) принят в качестве стандарта США в 1992 г. и предназначен для использования совместно с алгоритмом цифровой подписи, определенным в стандарте DSS. При вводе сообш,ения М алгоритм вырабатывает 160-битовое выходное сообш,ение, называемое сверткой (Message Digest), которая и используется при выработке ЭЦП.

Рассмотрим работу алгоритма подробнее.

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

Далее инициализируются пять 32-битовых переменных сле-дуюш,ими шестнадцатеричными константами: А = 67452301 В = EFCDAB89 С = 98BADCFE D= 10325476 E = C3D2E1F0,

Далее эти пять переменных копируются в новые переменные а, Ь,с,с1ие соответственно.

Главный цикл может быть довольно просто описан на псевдокоде следуюш,им образом: for(/=0;/<80;/++){

temp = (а «< 5)ЩЬ, c,d) +е+ W, + Kt; e = d;d = c;c = b «< 30;b = a;a = temp;

«< - операция циклического сдвига влево; К( - шестнадцатеричные константы, определяемые по сле-дуюш,им формулам:

5А827999, / = 0..19 6ED9EBA1, t = 20.39 8F1BBCDC, / = 40.59 CA62C1D6, / = 60..79

функции ft(x, у, z) задаются следуюш,ими выражениями: f(x,y,z), =

XaYvXaZ, t = 0..19 X©Y©Z, t = 20..39,60..79 XaYvXaZvYaZ, t = 40..59

значения W( получаются из 32-битовых подблоков 512-битового блока расширенного сообш,ения по следуюш,ему правилу:

М,, t = 0..19

(W, 3 © W, 3 © W, i4 © W, i6) «< 1, t = 16..79

После окончания главного циьсла значения а, b, с, d и е складываются с содержимым А, В, С, D и Е соответственно и осу-ш,ествляется переход к обработке следуюш,его 512-битового блока расширенного сообш,ения. Выходное значение хэш-функции является конкатенацией значений А, В, С, D и Е.

4.3.2. Функции хэширования SHA-256, SHA-512 и SHA-384

Стойкость функции хэширования к поиску столкновений примерно равна 2", где п - длина выходного значения функции. В связи с разработкой в США нового стандарта шифрования с длиной ключа 128, 192 и 256 бит, потребовалось создать "сопровождаюш,ие" алгоритмы, обеспечиваюш,ие такой же уровень стойкости. В этом пункте описаны алгоритмы вычисления функций хэширования с длиной выходного значения 256, 512 и 384 бита, которые предполагается принять в качестве нового стандарта США.