Однонаправленные хэш-функции

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

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

- хэш-функция должна быть чувствительна к всевозможным из­менениям в тексте М, таким как вставки, выбросы, перестанов­ки и т.п.;

- хэш-функция должна обладать свойством необратимости, то есть задача подбора документа , который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;

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

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

Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением всего сообщения . В результате однонаправленная хэш-функция всегда фор­мирует выход фиксированной длины (независимо от длины входного текста).

Часто функции хэширования строят, используя в качестве однона­правленной функции – симметричный блочный алгоритм шифрования (DES, ГОСТ 28147-89) в режиме с обратной связью, принимая последний блок шифротекста за хэш-значение всего документа. Так как длина блока в указанных алгоритмах невелика (64 бита), то часто в качестве хэш-значения используют два блока шифротекста. Одна из возможных схем хэширования на основе блочного алгоритма шифрования изображена на рис.7.2.

7.3. Алгоритм электронной цифровой подписи RSA

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.

Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электрон­ных документов вычисляет два больших простых числа и , затем находит их произведение и значение функции Эйлера . Далее отправитель вычисляет число из условий: , НОД и число из условий: , .

Пара чисел является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число сохраняется автором как секретный ключ для подписывания. Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис.7.3.

Допустим, что отправитель хочет подписать сообщение перед его отправкой. Сначала сообщение (блок информации, файл, таблица) сжимают с помощью хэш-функции в целое число . Затем вычисляют цифровую подпись под электронным докумен­том , используя хэш-значение и секретный ключ : . Пара передается партнеру-получателю как электрон­ный документ , подписанный цифровой подписью , причем подпись сформирована обладателем секретного ключа . После приема пары получатель вычисляет хэш-значение сообщения двумя разными способами. Прежде всего, он восстанавливает хэш-значение , применяя криптографическое преобразование подписи с использованием открытого ключа : . Кроме того, он находит результат хэширования принятого сообще­ния с помощью такой же хэш-функции : . Если соблюдается равенство вычисленных значений, т.е. , то получатель признает пару подлинной. Доказано, что только обладатель секретного ключа может сформировать цифровую подпись по документу , а определить секретное число по открытому числу не легче, чем разложить модуль на множители. Кроме того, можно строго математически доказать, что ре­зультат проверки цифровой подписи будет положительным только в том случае, если при вычислении был использован секретный ключ , соответствующий открытому ключу . Поэтому открытый ключ иногда называют "идентификатором" подпи­
савшего.

Недостатками алгоритма цифровой подписи RSA являются:

1. При вычислении модуля , ключей и для системы цифровой подписи RSA необходимо проверять большое количе­ство дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фаль­сификацию цифровой подписи со стороны того, кто обнаружит та­кое невыполнение при подписании важных документов нельзя допускать такую возможность даже теоретически.

2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, напри­мер, национального стандарта США на шифрование информации (алгоритм DES), т.е. , необходимо использовать при вычисле­ниях , и целые числа не менее (или около ) каж­дое, что требует больших вычислительных затрат, превышающих на 20..30% вычислительные затраты других алгоритмов циф­ровой подписи при сохранении того же уровня криптостойкости.

3. Цифровая подпись RSA уязвима к так называемой муль­типликативной атаке. Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа сформировать подписи под теми документами, у которых резуль­тат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.

Пример 7.1. Допустим, что злоумышленник может сконструировать три сообще­ния , и , у которых хэш-значения , , , причем . Допустим также, что для двух сообщений и получены законные подписи и

S₁ = m₁^Kc (mod n) и S₂ = m₂^Kc (mod n)

Тогда злоумышленник может легко вычислить подпись S₃ для документа Мз, даже не зная секретного ключа

S₃ = S_1* S₂ (mod n). Действительно,

S_1* S₂ (mod n) = m₁^Kc m₂^Kc (mod n) = (m_1* m₂)^Kc (mod n) = m₃^Kc (mod n) = S₃.