Интернет магазин китайских планшетных компьютеров

Компьютеры - N-Hash - Особенности N-Hash

Однонаправленность

Определение: Пусть M — сообщение некоторой длины.

Функция H называется однонаправленной, если из равенства h = H

легко:

• найти хеш-код h, зная сообщение M

очень трудоёмко:

• найти сообщение M по известному хеш-коду h;
• найти отличное от M сообщение M', такое что их хеш-коды H = H совпадают.

Проще определение можно записать так:

Однонаправленность — это «отпечаток пальца»:

• Если дан конкретный человек, то можно взять у него отпечаток пальца;
• Невозможно найти человека по отпечатку его пальца;
• Невозможно найти второго человека с таким же как у другого отпечатком пальца.

Однонаправленность решает очень важную проблему. Рассмотрим её на примере.

Алиса и Боб традиционно обозначают субъектов передачи информации.

Примеры

• Допустим, Алиса подписала контракт M с известным Алисе и Бобу хеш-кодом h = H. Если бы H была неоднонаправленная, то Боб мог бы найти такой другой контракт M', что H = H и, значит, смог бы утверждать, что Алиса подписала M'.
• Допустим, Алиса имеет один и тот же отпечаток пальца h с каким-нибудь преступником, тогда Боб смог бы утверждать, что этот преступник — Алиса.

Устойчивость к столкновениям

Чтобы предотвратить возможность Алисы использовать метод «дней рождения» для обмана Боба, очень удобно ввести ещё более сильное условие, чем условие однонаправленности. H такова, что трудно найти сообщения M и M', такие что их хеш-коды H = H совпадают. То есть невозможно найти двух человек с одинаковыми отпечатками пальцев.

Данное условие называется устойчивостью к столкновениям и для хеш-функции N-Hash оно не выполняется.

По причине неустойчивости к столкновениям Алиса может обмануть Боба таким образом:

• Алиса пишет две версии контракта: одна из них выгодна для Боба, а другая нет;
• Внося небольшие изменения в каждый контракт, она добьется того, что версий контрактов будет достаточно много для подбора M и M', для которых совпадают хеш-коды;
• Теперь Алиса сможет доказать, что Боб подписал M'.

Для того, чтобы избежать подобной проблемы, достаточно вносить косметические изменения в подписываемый контракт. И хотя это действие никак не изменяет хеш-функцию H, а, значит, никак не влияет на её устойчивость к столкновениям, но человек этим действием получит новую версию контракта, хеш-код которого не совпадает с хеш-кодом версии контракта злоумышленника. То есть, если Боб в 5-ой строке поставит в каком-нибудь месте запятую, или поставит две точки вместо одной, то Алиса не сможет доказать, что он подписал другой контракт.

Можно рассмотреть жизненный пример: когда нотариус ставит печать в подписываемый контракт, он вносит туда косметические изменения.