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

Вообще однонаправленными называют функции, которые вычислить сравнительно легко, но их обратные функции для вычисления требуют неприемлемых трудозатрат, т.е. более формально, однонаправленную функцию F(x) несложно рассчитать для каждого значения аргумента х, но очень трудно для известного значения F(x) вычислить соответствующее значение аргумента х. Примером однонаправленных функций могут служить полиномы. В этом случае вычисление обратной функции равносильно нахождению корней полинома, что, как известно из школьной алгебры, затруднительно даже для квадратичного полинома. Во всяком случае примем на веру, что такие функции существуют (всём сомневающимся советуем обратиться к одному из руководств по криптографии).

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

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

h=H(M)

где значение h, называемое хэшем, или необратимым хэшем, имеет разрядность m

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

• Зная М, легко вычислить h.

• Зная h, трудно определить значение М, для которого Н(М)=h.

• Зная M, трудно определить другое сообщение, M', для которого H(М)=H(М').

Вот что это означает. Пусть Переговорщик-1 вычислил дайджест H(М) своего сообщения м и зашифровал дайджест своим закрытым ключом. Может ли полученное значение служить в качестве цифровой подписи? Если Взломщик, располагая достаточными ресурсами, сможет создать другое сообщение M', отличное от M, но с одинаковым дайджестом, т.е. H(M)=H(M'), то цифровая подпись будет скомпрометирована.

Если же хэш-функция, использованная для вычисления дайджеста, обладает последним из указанных выше дополнительных свойств, то дайджест, по сути, становится уникальным идентификатором сообщения. В этом случае, если Переговорщик-1 зашифрует дайджест сообщения своим закрытым ключом, то Переговорщик-2 сможет удостовериться в его подлинности, восстановив дайджест с помощью открытого ключа Переговорщика-1 и затем самостоятельно вычислив дайджест сообщения и сравнив результат с дайджестом, полученным в сообщении. Именно так и создается цифровая подпись документов средствами современных криптосистем.