Предыдущая страница реферата | 17  18  19  20  21  22  23  24  25  26  27 | Следующая страница реферата

Q: Что такое хэш-функция (hash, hash-function)?

A: Это преобразование, получающее из данных произвольной длины некое значение

(свертку) фиксированной длины. Простейшими примерами являются контрольные

суммы (например, crc32). Бывают криптографические и программистские хэши.

Криптографический хэш отличается от программистского следующими

двумя свойствами: необратимостью и свободностью от коллизий.

Обозначим m -- исходные данные, h(m) -- хэш от них. Hеобратимость

означает, что если известно число h0, то трудно подобрать m такое,

что h(m) = h0. Свободность от коллизий означает, что трудно

подобрать такие m1 и m2, что m1 != m2, но h(m1) = h(m2).

Криптографические хэш-функции разделяются на два класса:

 - хэш-функции без ключа (MDC (Modification (Manipulation) Detect Code) - коды),

 - хэш-функции c ключом (MАC (Message Authentication Code) - коды).

Хэш-функции без ключа разделяются на два подкласса:

 - слабые хэш-функции,

 - сильные хэш-функции.

Слабой хэш-функцией назывется односторонняя функция 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' говорит о том, что у сильной хэш-функции

вычислительно невозможно вообще найти какую-либо коллизию.

Хэш-функцией с ключом (MAC) называется функция 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.

Q: А зачем она нужна?

A: Дело в том, что многие криптографические преобразования (в частности,

вычисление и проверка электронной цифровой подписи, ЭЦП) выполняются над

данными фиксированного размера. Поэтому перед простановкой электронной

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

от него, а уже от этого значения считают ЭЦП. Кроме того, удобно, например,

пароли в базе хранить не в открытом виде, а в хэшированном (так сделано

во всех юниксах).

Рекомендуем скачать другие рефераты по теме: ответы 5 класс, реферат теория.





Предыдущая страница реферата | 17  18  19  20  21  22  23  24  25  26  27 | Следующая страница реферата