Презентация на тему Хеш функції

– Manipulation Detection Code – кода обнаружения манипуляций (с

данными) - Хеш-функция (message digest)
Выработка MAC – Message Authentification Code – кода аутентификации сообщений – электронно-цифровая подпись

индустрии.
1, 2 — авиакомпании;
3 — туризм, развлечения;

4, 5 — финансовые организации, банки;
6 — торговля, банковская сфера;
7 — нефтяные компании;
8 — телекоммуникации;
9 — государственные предприятия.

Первая цифра — указывает на платежную систему.
American Express (34xxxx, 37xxxx)
VISA (4xxxxx)
MasterCard (51xxxx - 55xxxx)
Discover (6011xx, 644xxx, 65xxxx )
Maestro (3-, 5-, 6-)

номер эмитента. Другими словами, данный номер обозначает компанию, выдавшую

карточку и тип карты.
Девять цифр, начиная с седьмой, представляют собой идентификационный код держателя данной пластиковой карты.
А вот самая последняя цифра предназначена для контроля (алгоритм Луна)

1954, патент 1960
Сотрудник IBM Ганс Питер Лун
Алгоритм не криптографический,

реализует проверку целостности
Предназначен для выявления ошибок либо искажений при вводе номеров:
кредитных карт
номеров дисконтных карт
кодов соц. страхований
IMEI - кодов

налево.
2. Цифры, оказавшиеся на нечётных местах, остаются без изменений.
3.

Цифры, стоящие на чётных местах, умножаются на 2.
4. Если в результате такого умножения возникает число больше 9, оно заменяется суммой цифр получившегося произведения — однозначным числом, т.е. цифрой.
5. Все полученные в результате преобразования цифры складываются. Если сумма кратна 10, то исходные данные верны.

любой длины; h - последовательность фиксированной длины.
1. по М

легко вычисляется h(М)
2. по h трудно найти М
3. по М трудно найти M′ : h(M) = h( M′ ).
4. Желательно чувствительность к не значительным изменениям
“Трудно” 2^64 ≈ операций или больше.
Три способа разработки:
на основе труднорешаемой мат. задачи;
на основе алгоритмов блочного шифрования (DES);
самостоятельная разработка.

входа: исходное сообщение и предыдущий хеш

итерационный блок (512 бит)
Подстановка переменных
4 раунда по 20 операций

(MD5-16). Нелинейные операции, сдвиги и сложения
Расширение сообщения.
Сложение результата с промежуточным результатом
Переход к следующему блоку

достраивается до длины, кратной 512 (padding): к сообщению добавляется

«1», затем столько нулей, сколько надо до длины, кратной 512 минус 64 бита, затем 64-битное представление длины сообщения до padding’а (алгоритм padding’a такой же, как в MD5)
2. Инициализация 5-ти переменных (MD5-4)
A=67 45 23 01
B=EF CD AB 89
C=98 BA DC FE
D=10 32 54 76
E=C3 D2 E1 F0.

CC=C; DD=D; EE=E;
2. 4 раунда по 20 операций (MD5-16).

Нелинейные операции, сдвиги и сложения

результата с промежуточным результатом
Далее A, B, C, D, E

прибавляют к AA, BB, CC, DD, EE и берется следующий блок. Результат– конкатенация AA, BB, CC, DD, EE.

сцепления блоков), CFB (Режим обратной связи по шифрограмме) с

фиксированным ключом.
Использование одного ключа

Xor криптограммы предыдущего и текста текущего

чем это позволяет выбранная хэш-функция, был предложен следующий метод:
1)

Сгенерировать хэш от сообщения
2) Добавить хэш в конец сообщения (append)
3) Сгенерировать хэш от конкатенации сообщения и хэша
4) Получить длинное хэщ-значение путем конкатенации хэш-значения из пункта 1) и хэш-значения из пункта 3)
5) Повторять шаги (1-3) до получения необходимой длины.
Надежность или ненадежность данного метода не доказаны.

h(M1). – 2^160
2. «Парадокс дней рождения» - 2^80
(1) Аня

готовит 2 версии контракта – один выгодный для Вани, а другой разоряющий его;
(2) Аня делает несколько малозначительных изменений к каждому документу и считает хэш-значения каждый раз (напр., заменить SPACE на SPACE-BACKSPACE-SPACE, добавить один или два пробела перед переводом строки и т.д. Только путем одного «изменения / оставления как было» на каждой строке Аня может сгенерировать 32^2 документов).
(3) Аня сравнивает набор хэшей для обоих документов, подыскивая одинаковые пары (если х.-ф. = 64 бит, то обычно хватит 32^2 пар). Выбирается та пара, что дает одинаковые хэши.
(4) Аня подсовывает Ване выгодный контракт; Ваня подписывает его хэш.
(5) Аня может теперь доказать, что Ваня подписал невыгодный ему контракт.

источника данных)
Элемент аутентификации

сложность подделки документа word для получения такого дайжест сообщения