Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
• В прикладных криптосистемах с открытым ключом хэш-функции широ- I ко используются для реализации механизма верификации правильности за- ' шифрованных текстов. Такой механизм необходим для того, чтобы обеспечить доказуемую стойкость к активным атакам. Пример такого применения хэш-функций описан в разделе 10.5. Формальное доказательство того, что хэш-функции обеспечивают доказуемую стойкость криптосистем с открытым ключом, приведено в главе 15.
• В широком круге криптографических приложений функции хэширования I используются в качестве псевдослучайных функций. К таким приложениям относятся согласование ключей (например, когда два пользователя используют общее начальное значение в качестве аргумента функции хэширования для получения разделенного значения ключа), протоколы аутентификации (например, когда два участника протокола подтверждают выполнение протокола, обмениваясь хэшированными значениями), протоколы электронной коммерции (например, для обеспечения накопления платежей для биржевой
Глава 10. Методы защиты целостности данных
351
игры [201, 297]), протоколы доказательства знания (например, для обеспечения автономного режима доказательства (см. раздел 18.3.2.2)). В книге изложено большое количество примеров применения функций хэширования.
10.3.1.2 Случайный оракул
Напомним свойство перемешивания, которое присуще функции хэширования: при любом аргументе хэшированное значение неотличимо с вычислительной точки зрения от строки битов, равномерно распределенных в области значений функции. Если заменить последнее выражение фразой "принадлежит генеральной совокупности равномерно распределенных чисел", мы получим весьма мощную гипотетическую функцию под названием случайный оракул (random oracle).
Мы назвали этого оракула весьма мощным, поскольку он обладает тремя свойствами: он является детерминированным, эффективным и обеспечивает равномерное распределение результирующих значений. Причина, по которой эта функция считается гипотетической, заключается в том, что все известные вычислительные модели не являются настолько мощными.
С одной стороны, нам известно, как эффективно сгенерировать равномерно распределенные случайные величины, например, подбрасывая монету. Однако этот способ не является детерминированным. С другой стороны, можно рассматривать множество равномерно распределенных независимых величин с детерминированной точки зрения, например, упорядочивая их так, чтобы между любыми двумя числами и расстоянием между ними в упорядоченном списке существовала детерминированная зависимость. Однако эти расстояния невозможно вычислить за полиномиальное время, зависящее от величины случайных чисел (для упорядочения п элементов списка необходимо nlogn операций).
Равномерность и детерминированность величин, вычисляемых случайным оракулом, означает, что энтропия его результатов выше, чем энтропия чисел, поступающих на вход (определение энтропии дано в разделе 3.7). Однако, если теория Шеннона (теорема 3.2 в разделе 3.7) верна, детерминированная функция никогда не сможет увеличить энтропию. Следовательно, случайного оракула в реальном мире не существует.
Поскольку свойство перемешивания, которым обладает хэш-функция, является лишь предположением вычислительного характера (предположение 4.2 в разделе 4.7), реальная хэш-функция должна обеспечивать лишь вычислительную неразличимость в смысле определения 4.15 (раздел 4.7), т.е. ее результаты должны иметь некое распределение вероятностей в области значений, которое невозможно определить за полиномиальное время. Итак, реальные функции хэширования лишь имитируют поведение случайного оракула с высокой точностью.
Несмотря на это, функции хэширования играют важную роль в криптографии с открытым ключом. По существу, хэширование сообщений вносит в них необходимую избыточность, причем эта процедура носит детерминированный характер.
352
Часть III. Основные методы криптографии
10.3.1.3 Атака на основе парадокса дней рождений
Предположим, что функция хэширования h действительно является случай-1 ным оракулом. В атаке по методу квадратного корня (атака на основе пара! докса дней рождений, раздел 3.6) предполагается, что для обнаружения коллш|
зии с ненулевой вероятностью достаточно выполнить 2 2 = V2lftl случайным вычислений значения функции хэширования. Для организации атаки на основа парадокса дней рождений атакующий должен сгенерировать пары "сообщение-хэшированное значение"
(mi, h(m{)), (m2, h(m2)),
пока не обнаружатся два сообщения т и тп', удовлетворяющих условиям
т ф т, h(m) = h(m'). (10.3.1)
Такая пара сообщений называется коллизией (collision) функции хэширования h. Разумеется, чтобы атака была успешной, сообщения т и т' должны сдержать осмысленную информацию. Например, рассмотрим хэшируемое сообщение, ког торое должно сопровождаться цифровой подписью (раздел 10.4) и представляет^ собой санкцию на оплату, имеющую вид
М = Цена, Описание_товара, R,
где R — случайное число, предназначенное для рандомизации протокольных сообщений (что весьма желательно). Тогда сообщение в атаке на основе парадокса! дней рождений выглядит следующим образом.
