Свойства HASH - функций

Пример

Рассмотрим в качестве примера хеш-функцию H(x) = xmod 19, определенную на множестве целых чисел. Её область значений состоит из 19 элементов (кольца вычетов по модулю 19), а область определения — бесконечна. Так как множество прообразов заведомо больше множества значений, коллизии обязаны существовать.

Построим коллизию для этой хеш-функции для входного значения 38, хеш-сумма которого равна нулю. Так как функция H(x) — периодическая с периодом 19, то для любого входного значения y, значение y+19 будет иметь ту же хеш-сумму, что и y. В частности, для входного значения 38 той же хеш-суммой будут обладать входные значения 57, 76, и т. д. Таким образом, пары входных значений (38,57), (38,76) образуют коллизии хеш-функции H(x).

Коллизии криптографических хеш-функций

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

Cвойства криптографических хеш-функций

Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

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

Стойкость к коллизиям первого рода: для заданного сообщения M должно быть практически невозможно подобрать другое сообщение N, для которого H(N) = H(M).

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

6.4.2.3Тестирование HASH–функций

http://www.slavasoft.com/

SHA1

Let the message be the ASCII binary-coded form of "abc", i.e.,

01100001 01100010 01100011

61 62 63hex

Message digest = A9993E364706816ABA3E25717850C26C9CD0D89D

"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq".

Message digest =

84983E441C3BD26EBAAE4AA1F95129E5E54670F1

Let the message be the binary-coded form of the ASCII string which consists of 1,000,000 repetitions of "a".

Message digest = 34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F

Certificate:
Data:
Version: 3 (0x2)
Serial Number: 0 (0x0)
Signature Algorithm: md5WithRSAEncryption
Issuer: O=Root CA, OU=http://www.cacert.org, CN=CA Cert Signing Authority/emailAddress=[e-mail] Validity Not Before: Mar 30 12:29:49 2003 GMT Not After: Mar 29 12:29:49 2033 GMT Subject: O=Root CA, OU=http://www.cacert.org, CN=CA Cert Signing Authority/emailAddress=[e-mail]
Subject Public Key Info:
Public Key Algorithm: rsaEncryption RSA
Public Key: (4096 bit)
Modulus (4096 bit):...

Этот сертификата является КС удостоверяющего центра CA Cert (обратите внимание, что УЦ выдает этот сертификат самому себе). Как и все КС, этот сертификат обладает длительным сроком валидности (до 2033 года). Интересно отметить также, что сертификат был выпущен в 2003 году, то есть тогда, когда об уязвимости алгоритма MD5 еще не было известно, поэтому цифровая подпись сертификата получена с помощью алгоритма MD5, о чем свидетельствует строка

Signature Algorithm: md5WithRSAEncryption

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

Дата добавления: 2015-07-07