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


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


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

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

Первый подход предполагает затраты дисковой памяти, так как необходимо хранить 2L+1–2 значений хэш-функции всех уровней, а второй требует большого объема вычислений в момент формирования подписи. Можно использовать и компромиссный подход – хранить все хэш-комбинации начиная с некоторого уровня  l*, а комбинации меньшего уровня вычислять при формировании подписи.

В рассмотренной выше схеме подписи на 8 сообщений можно хранить все 14 контрольных комбинаций, используемых при проверки (всего их 15, но самая верхняя не используется), тогда при проверке подписи их не надо будет вычислять заново. Можно хранить 6 комбинаций начиная с уровня 1 (C0(1), C1(1), C2(1), C3(1), C0(2), C1(2)), тогда при проверке подписи сообщения № 5 необходимо будет заново вычислить комбинацию C4(0), а остальные (C0(2),C3(1)) взять из таблицы, и т.д.. Указанный подход позволяет достичь компромисса между быстродействием и требованиям к занимаемому количеству дискового пространства.

Отметим, что отказ от хранения комбинаций одного уровня приводит к экономии памяти и росту вычислительных затрат примерно вдвое, то есть зависимость носит экспоненциальный характер.




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