|
Читайте также: |
Хэш-функция - это преобразование, получающее из данных произвольной длины некое значение фиксированной длины. Простейшими примерами являются контрольные суммы. Бывают криптографические и программистские хэши. Криптографический хэш отличается от программистского следующими двумя свойствами: необратимостью и свободностью от коллизий. Обозначим m - исходные данные, h(m) - хэш от них. Необратимость означает, что если известно число h0, то трудно подобрать m такое, что h(m) = h0. Свободность от коллизий означает, что трудно подобрать такие m1 и m2, что m1!= m2, но h(m1) = h(m2).
Криптографические хэш-функции разделяются на два класса:
- хэш-функции без ключа
- хэш-функции с ключом.
Хэш-функции без ключа разделяются на два подкласса:
- слабые хэш-функции,
- сильные хэш-функции.
Слабой хэш-функцией называется односторонняя функция H(x), удовлетворяющая следующим условиям:
1) аргумент х может быть строкой бит произвольной длины;
2) значение H(x) должно быть строкой бит фиксированной длины;
3) значение H(x) легко вычислить;
4) для любого фиксированного x вычислительно невозможно найти другой x'!= x, такой что H(x')=H(x).
Пара x'!= x, когда H(x')=H(x) называется коллизией хэш-функции. Сильной хэш-функцией называется односторонняя функция H(x), удовлетворяющая условиям 1-3 для слабой хэш-функции и свойству 4':
4') вычислительно невозможно найти любую пару x'!= x, такой что H(x')=H(x).
Поскольку из свойств 1-2 следует, что множество определения хэш-функции значительно шире множества значений, то коллизии должны существовать. Свойство 4 требует, чтобы найти их для заданного значения х было практически невозможно. Требование 4' говорит о том, что у сильной хэш-функции вычислительно невозможно вообще найти какую-либо коллизию.
Хэш-функцией с ключом называется функция H(k,x) удовлетворяющая свойствами:
1) аргумент х функции H(k,x) может быть строкой бит произвольной длины;
2) значение H(k,x) должно быть строкой бит фиксированной длины;
3) при любых k и x легко вычислить H(k,x);
4) для любого х должно быть трудно вычислить H(k,x) не зная k;
5) должно быть трудно определить k даже при большом числе неизвестных пар {x, H(k,x)} при выбранном наборе х или вычислить по этой информации H(k,x') для x'!= x.
Многие криптографические преобразования (в частности, вычисление и проверка электронной цифровой подписи, ЭЦП) выполняются над данными фиксированного размера. Поэтому перед простановкой электронной подписи под многобегабайтным файлом обычно рассчитывают значение хэш-функции от него, а уже от этого значения считают ЭЦП. Кроме того, удобно, например, пароли в базе хранить не в открытом виде, а в хэшированном.
Вот некоторые алгоритмы хэш-функций:
MD2
Автор: FIXME!
Размер: 128 бит.
MD4
Автор: Р.Райвест (R. Rivest).
Размер: 128 бит.
MD5. Капитально переделанный MD4.
Автор: Р.Райвест (R. Rivest).
Размер: 128 бит.
SHA.
Один из (относительно) новых алгоритмов свертки.
Автор: FIXME!
Размер: 160 бит.
ГОСТ Р34.11-94
Российский алгоритм. Размерность получаемого значения очень удобна для формирования по паролю ключа для ГОСТ 28147-89.
Автор: FIXME!
Размер: 256 бит.
Рассмотрим поиск подстроки в строке с помощью хэш-функции. Каждый символ имеет свой уникальный код от 0 до 255. Суть метода заключается в том, чтобы для подстроки подсчитать некоторую хэш-функцию (например, сумму кодов всех символов в строке), затем посчитать ту же самую хэш-функцию для части строки, равной по длине подстроке, и, в случае совпадения хэш-функции, полностью сравнить его. Ускорение работы алгоритма связано с тем, что мы каждый раз не пересчитываем каждый раз хэш-функцию, а только отнимаем значение функции от самого "старого" символа и добавляем значение функции от следующего символа.
Дата добавления: 2014-12-23; просмотров: 41 | Поможем написать вашу работу | Нарушение авторских прав |