Односторонні хеш-функції.

Хеш-функція h, яка використовується у протоколі ЕЦП, призначена для того, щоб стиснути підписуваний документ M довільної довжини до двійкового хеш-значення H = h (M) фіксованої довжини (декілька десятків біт). Завдяки цьому підписується не сам довгий документ, а його коротке хеш-значення, а довжина підпису стає фіксованою.

Основні властивості хеш-функції:

1) хеш-значення H залежить від усього документу M надзвичайно складним способом, завдяки чому за значенням H неможливо відновити документ M;

2) хеш-значення H є чутливим до будь-яких, навіть незначних, змін у документі M (вставки, вилучення, перестановки тощо);

3) хеш-функція h (M) є необоротною, тобто підбір деякого фіктивного документу з тим же самим хеш-значенням H є задачею практично нерозв’язуваною;

4) ймовірність того, що хеш-значення двох різних документів співпадуть, є надзвичайно малою.

Правило утворення одного хеш-значення із двох вхідних залежить від типу хеш-функції. У найпростішому випадку тут може використовуватись додавання за модулем 2, тобто H_i = M_i Å H_i-1.

Визначення кількості біт n для хеш-значення може здійснюватись на підставі значення модуля системи ЕЦП, а саме: кількість біт хеш-значення має бути на одиницю меншою кількості біт значення модуля системи ЕЦП.

Розглянемо приклад. Відомо, що модуль системи ЕЦП 19₁₀ = 10011₂. Кількість біт цього значення рівна 5. Виберемо кількість біт хеш-значення n = 4. Припустимо, що необхідно підписати наступний документ M: 29, 7, 11, 3, 20, 36. Необхідно знайти найпростіше хеш-значення для цього документу.

Утворюємо двійковий образ документу: 11101, 111, 1011, 11, 10100, 100100. Суцільна послідовність біт має вигляд: 1110111110111110100100100. Доповнюємо кількість біт цієї послідовності до числа, кратного n = 4, за рахунок початку цієї ж послідовності і отримуємо: 1110 1111 1011 1110 1001 0010 0111. Таким чином, даний документ розбито на сім блоків довжиною 4 біт кожний. Тепер утворюємо послідовність хеш-значень:

H₀ = 0000;

H₁ = M₁ Å H₀ = 1110 Å 0000 = 1110;

H₂ = M₂ Å H₁ = 1111 Å 1110 = 0001;

H₃ = M₃ Å H₂ = 1011 Å 0001 = 1010;

H₄ = M₄ Å H₃ = 1110 Å 1010 = 0100;

H₅ = M₅ Å H₄ = 1001 Å 0100 = 1101;

H₆ = M₆ Å H₅ = 0010 Å 1101 = 1111;

H₇ = M₇ Å H₆ = 0111 Å 1111 = 1000.

Остаточно, хеш-значенням усього документу M вважається значення H = 1000₂ = 8₁₀.

Дата добавления: 2014-01-11