Содержание
9.1 Хэш-функции
Хэш-функции применяются для тестирования логических устройств, для быстрого поиска и проверки целостности записей в базах данных.
- построения систем контроля целостности данных при их передаче или хранении,
- аутентификация источника данных.
Определение 9.2 Обозначим через множество, элементы которого будем называть сообщениями, — натуральное число. Хеш-функцией называется всякая легко вычислимая функция .
Обычно число возможных сообщений значительно превосходит число возможных значений сверток, в силу чего для каждого значения свертки имеется большое множество прообразов, то есть сообщений с заданным значением хеш-функции. Заметим, что при случайном и равновероятном выборе сообщений условие равномерности распределения значений хеш-функции эквивалентно наличию одинакового числа прообразов для каждого значения свертки.
Здесь — некоторый фиксированный начальный вектор. Если функция зависит от ключа, то этот вектор можно положить равным нулевому вектору. Если же функция не зависит от ключа, то для исключения возможности перебора коротких сообщений (при попытках обращения хеш-функции) этот вектор можно составить из фрагментов указывающих на дату, время, номер сообщения и т.п.
9.2 Электронная подпись
Появление криптографии с открытым ключом позволило решать задачи, которые ранее считались неразрешимыми. К таким задачам относится использование цифрового аналога собственноручной подписи абонента — электронной цифровой подписи (ЭЦП).
Задачи, которые решает подпись:
Для реализации схемы ЭЦП необходимы два алгоритма: алгоритм генерации подписи и алгоритм проверки. Надежность схемы ЭЦП определяется сложностью следующих задач:
Заметим, что между ЭЦП и собственноручной подписью имеются различия, хотя они и служат для решения одинаковых задач. Так, ЭЦП зависит от подписываемого текста, различна для разных тестов. Кроме того, ЭЦП требует дополнительных механизмов, реализующих алгоритмы ее вычисления и проверки. Наконец, принципиальной сложностью, возникающей при использовании ЭЦП, является необходимость создания инфраструктуры открытых ключей. Эта инфраструктура состоит из центров сертификации открытых ключей и обеспечивает возможность своевременного подтверждения достоверности открытой информации, необходимой для проверки ЭЦП, что необходимо для предотвращения подделки подписи.
В настоящее время имеется большое количество различных схем ЭЦП, обеспечивающих тот или иной уровень стойкости. Существующие схемы можно классифицировать таким образом:
9.2.2 Схема Эль-Гамаля
Безопасность схемы основана на трудности вычисления дискретных логарифмов в конечном поле. Для генерации пары ключей выбирается простое число и два случайных числа, и , оба меньше . Затем вычисляется . Открытым ключом является набор чисел . При этом и можно сделать общими для группы пользователей. Секретным ключом является . Чтобы подписать сообщение , сначала выбирается случайное число , взаимно простое с . Затем вычисляются подпись по формулам:
Первое замечание о выборе . Оно должно храниться в секрете и уничтожаться сразу после вычисления подписи, так как знание и значения подписи позволяет легко вычислить секретный ключ . И тогда подпись будет полностью скомпрометирована. Кроме того, должно быть действительно случайным и не должно повторяться для различных подписей, полученных на одном секретном ключе. Если злоумышление сможет получить два сообщения, подписанные с помощью одного и того же значения , то он сможет раскрыть , даже не зная значение .
Пример 9.1 Выберем и , а секретный ключ .
Открытым ключом являются , и . Чтобы подписать , сначала выберем случайное число , убеждаемся, что . Вычисляем:
Итак, подпись представляет собой пару: и .
Второе замечание. При вычислении подписи целесообразно использовать хэш-образ сообщения, а не само сообщение . Это защитит схему подписи от возможности подбора сообщений с известным значением подписи. Это распространенная практика. В приведенном примере можно считать, что . Наиболее распространена технология ЭЦП, основанная на совместном применении алгоритмов хеширования и шифрования с открытым ключом (в частности, RSA или Эль-Гамаля).
-
Пусть — подписываемое сообщение. Отправитель вычисляет хеш-значение подписываемого сообщения . Значение должно удовлетворять неравенству . - Отправитель выбирает случайное число , , взаимно простое с , и вычисляет числа:
— число, обратное по модулю , существует, так как и — взаимно просты. - Подпись добавляется к сообщению, и тройка передается получателю.
Если подпись верна, то это равенство выполняется.
Используемые на практике алгоритмы хеширования достаточно сложны, поэтому будем использовать учебные алгоритмы формирования хеш-значения . Схему учебных алгоритмов хэширования предложила Васильева И.Н. [1].
Входом для данного алгоритма является строка, состоящая из букв русского языка.
Следует отметить, что вычисленное по этому алгоритму хеш-значение зависит от всех символов сообщения .
Пример 9.2 Выполнить вычисление и проверку подписи сообщения по алгоритму Эль-Гамаля. Использовать параметры подписи:
Для проверки правильности вычисления полученной цифровой подписи следует произвести ее проверку с помощью открытого ключа абонента и убедиться, что подпись подлинная.
Второй учебный алгоритм хеширования
-
Начальное значение принимается равным числу десятичных разрядов в . - Для каждого десятичного знака числа вычисляется значение
- Значение , вычисленное для последнего символа, увеличенное на 1, является хеш-значением сообщения: .
Пример 9.3 Известны значения общих параметров системы Эль-Гамаля: , и открытый ключ абонента . От абонента получено сообщение , снабженное цифровой подписью Эль-Гамаля , . Проверить подлинность цифровой подписи. Хеш-значение сообщение вычисляется с помощью второго учебного алгоритма.
Источник