Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 10. Методы защиты целостности данных
355
Код аутентификации сообщений, обеспечивающий целостность данных в сообщении М для пользователей, владеющих ключом к, иногда обозначается как MAC(fc, М). В этом обозначении игнорируются детали реализации, например, однонаправленное преобразование, использованное при вычислении кода.
10.4 Асимметричные методы I: цифровые подписи
В криптографии с открытым ключом пользователь может применять для шифрования сообщения свой закрытый ключ, а для расшифровки — открытый ключ. Очевидно, что зашифрованный текст, созданный таким способом, может использоваться в качестве кода распознавания манипуляций (MDC), сопровождающего зашифрованное сообщение, т.е. обеспечивать защиту целостности данных. Здесь процесс расшифровки с помощью открытого ключа представляет собой верификацию кода MDC.
Более того, верификацию кода может осуществить кто угодно, поскольку открытым ключом владеют все. В противоположность этому считается, что создать код MDC с помощью соответствующего открытого ключа мог только владелец закрытого ключа, использованного для создания этого кода Такое применение криптографии с открытым ключом — цифровая подпись (digital signature) — позволяет установить автора сообщения. Иначе говоря, криптографию с открытым ключом, а точнее, однонаправленную функцию с секретом (см. свойство 8.1 в разделе 8.1) можно применять для реализации цифровой подписи.1 Первыми цифровую подпись изобрели Диффи и Хеллман [97] (эта работа опубликована в 1976 году, хотя [ распространялась в качестве препринта с 1975 года [96]).
Возможность создавать цифровые подписи предоставляет криптографии с открытым ключом огромное преимущество над криптографией с секретным ключом (вторым достоинством криптографии с открытым ключом является возможность распределять ключи между удаленными пользователями, как показано в разделе 8.15). Теперь, когда только один пользователь может создать цифровую подпись сообщения, которую может верифицировать кто угодно, легко разрешить вопрос о его авторстве. Это дает возможность предотвратить отказ от авторства (non-repudiation), т.е. отрицать свою связь с посланным сообщением. Предотвращение отказа от авторства представляет собой важное требование безопасности в электронной коммерции.
Дадим формальное определение цифровой подписи.
'Несмотря на то что теоретическую основу цифровых подписей образуют однонаправленные функции [173], на практике для их создания используются однонаправленные функции с секретом.
356
Часть III. Основные методы криптографии
Определение 10.2 (Схема цифровой подписи). Схема цифровой подписи состоит из следующих компонентов.
• Пространство исходных сообщений Л4: множество строк над некоторым алфавитом.
• Пространство подписей §: пространство возможных подписей.
• Пространство ключей подписи К: пространство возможных ключей, применяемых при создании подписи, и пространство ключей верификации К!\ множество возможных ключей, применяемых для верификации подписи.
• Эффективный алгоритм генерации ключа Gen : N К х К', где К и К! пространства закрытых и открытых ключей соответственно.
• Эффективный алгоритм подписи Sign : М х К •—» §.
• Эффективный алгоритм верификации Verify : Л4 х К х К! н-> {True, False}. Для любого ключа подписи skEtC и любого сообщения тЕЛ4 операция подписи^
обозначается как
s — Signsfc(m).
Это выражение читается следующим образом: "s — подпись сообщения т, со\ зданного с помощью ключа sk ".
Для любого секретного ключа подписи skEK, соответствующего открытого^ ключа рк, любого сообщения т Е Л4 и подписи s должно выполняться условие
J True с вероятностью 1, если s *— Signsfc^m),
Veritypfc/m s\ = < _
I False с огромной вероятностью, если s <— bignsfc(mj,
где вероятностное пространство содержит пространства S, Л4, К, и К! и, вот можно, пространство случайных исходных данных, если алгоритмы подписи/вЛ рификации являются вероятностными.
Это определение можно считать частным вариантом определения 10.1: пары| (Sign, Verify), (sk,pk) и (m,s) соответствуют парам (f,g), (Ke,Kv) и (Data, MDC).
Заметим, что размер ключей подписи/верификации определяется целыми числами, поступающими на вход алгоритма генерации ключей Gen. Поскольку этот алгоритм является эффективным, и время его работы полиномиально зависит от размера целого числа, поступающего на вход, это число следует представлять в унарном виде (причины указаны в определении 4.7 в разделе 4.4.6.1). Это целое число представляет собой параметр безопасности схемы цифровой подписи и определяет размер пространства подписей.
Поскольку размер пространства подписей зависит от параметра безопасности, смысл выражения "огромная вероятность" в формуле "Verify^ (тп, s) = False
Глава 10. Методы защиты целостности данных
357
с огромной вероятностью, если s<—Signsfc(m)" полностью соответствует понятию, определенному в разделе 4.6. Однако эта вероятность не должна учитывать вариант, когда подпись допускает легкую фальсификацию, как указано в замечании 10.1. Количественная оценка этой вероятности будет дана в ходе формального доказательства стойкости некоторых реальных схем цифровой подписи в главе 16.
