19. Функции хеширования, их место в схемах цифровой подписи.

Электронная цифровая подпись также является криптографией с асимметричным ключом. Смысл: зашифрование производится с помощью секретного ключа, расшифрование – с помощью открытого ключа. Цель: сохранить целостность данных, а не сохранить секрет.

Так как подписать ЭЦ подписью требуется порой большой документ, что требует длительного времени, применяют ХЭШ-функции. Хэш – это представитель данных большого объема, имеющий постоянную длину, то есть большой документ преобразуется в малый документ. Любое изменение в исходном документе вызовет изменение в хэщ-функции. Хэш-функция выглядит случайным набором символов.

Алгоритмы получения Хэш: MD-2,4,5.

ЭЦП ставится только на хэш-функцию, а не на весь документ.

Схемы ЭЦП: RSA, OSS, ElGamal, Рабин, ГОСТ 34.10-94 (DSS в США).

Коллизия – это ситуация, когда h(х1) = h(х2), в то время как x1 < > x2. Очевидно, что количество коллизий необходимо минимизировать.

Хорошая хеш-функция должна удовлетворять двум требованиям:

1. ее вычисление должно выполняться очень быстро;

1. она должна минимизировать число коллизий.

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

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

Методы атак на хэш-функции.

1. Метод лобовой атаки: m – разрядность, М – исходное сообщение, М’ – поддельное сообщение, Н – хэш-функция (ее значение). Смысл: найти Н(М) = Н(М’). Нужно перебрать 2^m вариантов.

1. Метод дней рождения: m – разрядность, М – исходное сообщение, М’ – измененное сообщение, М’’ – другое измененное сообщение, М’ ≠ M’’.

Парадокс дней рождения в более общем смысле применим к хэш-функциям: если хэш-функция генерирует N-битное значение, то число элементов, которые можно обработать без высокой вероятности получения коллизии (то есть возврата одинакового значения функции для двух разных элементов), равно не 2^N, а только около 2^N/2. Как следствие, небольшое число коллизий хэш-функций в практических приложениях возникает неизбежно. Этот эффект используется в «атаке дня рождения» (birthday attack) на криптографические хэш-функции.

Применение хэш в ЭЦП.

20. Стандартные и нестандартные нападения на системы эцп. Примеры.

Стандартное нападение – методы перебора: лобовая атака и метод дней рождения.

Нестандартное нападение:

1) Нападение, в котором участвует секретарь.

2) Вставление закладок (программа всегда выдает что подпись правильная).

3) Нападение на систему открытых ключей

Здесь Мэллори – злоумышленник "козлищще", Трент – посредник из представителей семейства "посредникус обыкновенникус", Алиса и Боб передают друг другу сообщения.

Проще всего узнать чей-то открытый ключ, считав его откуда-то из безопасной базы данных. Эта база дан­ных должна быть общедоступна, чтобы каждый мог получить нужный ему ключ. База данных должна быть защищена от несанкционированной записи, в противном случае Мэллори сможет подменить открытый ключ Боба. После этого Боб уже не сумеет читать адресованные ему сообщения, зато это сможет сделать Мэллори .

Даже если открытые ключи хранятся в надежной базе данных, Мэллори может подменить их при передаче. Чтобы воспрепятствовать этому, Трент должен подписывать каждый открытый ключ, используя свой собственный закрытый ключ. Трента, который действует подобным образом, часто называют Органом сертификации ключей или Центром распределения ключей (Key Distribution Center, KDC). На практике KDC подписывает сложное сообщение, состоящее из имени пользователя, его открытого ключа и другой информации о пользователе. Это подписанное сложное сообщение и хранится в базе данных KDC. Когда Алиса получает ключ Боба, она проверяет подпись KDC, удостоверяясь в правильности ключа.

При окончательном анализе видно, что и это только затрудняет, но не делает невозможным мошенничество Мэллори. Алиса же должна откуда-то получить открытый ключ KDC. Мэллори нужно подменить этот ключ своим открытым ключом, испортить базу данных и заменить правильные ключи своими (подписанными его закрытым ключом, как если бы он и был KDC), и его дело сделано.