Хеш функції

Сентябрь 7, 2022

Главная
Алгебра
Хеш функції

Содержание

2. Подходы к контролю целостности данных Контрольная сумма Выработка MDC – Manipulation Detection Code – кода обнаружения
3. Расшифровка номера карты Первая цифра — это основной идентификатор индустрии. 1, 2 — авиакомпании; 3 —
4. Расшифровка номера карты Первые шесть цифр представляют собой идентификационный номер эмитента. Другими словами, данный номер обозначает
5. Алгоритм Луна Алгоритм вычисление контрольной суммы Стандарт ISO/IEC 7812 Описан в 1954, патент 1960 Сотрудник IBM
6. Запатентованная реализация (1960)
7. Суть алгоритма Луна 1. Цифры проверяемой последовательности нумеруются справа налево. 2. Цифры, оказавшиеся на нечётных местах,
8. Односторонняя хэш-функция: Message digest cryptographic checksum Исходные данные: сообщение М любой длины; h - последовательность фиксированной
9. Практическая реализация MD5 SHA-1 SHA-3 (Keccak) 128-160-224/256/384/512 bit результат Используют, как правило, два входа: исходное сообщение
10. Secure Hash Algorithm (SHA) Rfc 3174 160-bit результат Если исходный текст
11. Описание алгоритма SHA Дополнение блоков (padding) Инициализация 5-ти переменных (MD5-4) Основной итерационный блок (512 бит) Подстановка
12. Этапы алгоритма SHA 1. Дополнение блоков (padding) В начале, сообщение достраивается до длины, кратной 512 (padding):
13. Основной итерационный блок алгоритма SHA 1. Подстановка переменных AA=A; BB=B; CC=C; DD=D; EE=E; 2. 4 раунда
14. Основной итерационный блок алгоритма SHA 3. Расширение сообщения. 4. Сложение результата с промежуточным результатом Далее A,
15. Схема выполнения одной операции SHA
16. Использование блочных алгоритмов Использование DES в режиме CBC (Режим сцепления блоков), CFB (Режим обратной связи по
17. Метод увеличения хэша Для получения хэш-значения с большей длиной, чем это позволяет выбранная хэш-функция, был предложен
18. Криптоанализ 1. «Лобовая атака» Имея h(M), найти M1, такую что h(M1). – 2^160 2. «Парадокс дней
19. Применение Контрольная сумма Проверка целостности сообщения (файла) Элемент цифровой подписи (Аутентификация источника данных) Элемент аутентификации
20. Задачи Реализовать свою хеш-функцию с результатом в 4 бита Оценить сложность подделки документа word для получения
22. Скачать презентацию

Слайд 2

Подходы к контролю целостности данных
Контрольная сумма
Выработка MDC – Manipulation Detection

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

Слайд 3

Расшифровка номера карты
Первая цифра — это основной идентификатор индустрии.
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-)

Слайд 4

Расшифровка номера карты
Первые шесть цифр представляют собой идентификационный номер эмитента. Другими

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

Слайд 5

Алгоритм Луна
Алгоритм вычисление контрольной суммы
Стандарт ISO/IEC 7812
Описан в 1954, патент 1960
Сотрудник

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

Слайд 6

Запатентованная реализация (1960)

Слайд 7

Суть алгоритма Луна
1. Цифры проверяемой последовательности нумеруются справа налево.
2. Цифры, оказавшиеся

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

Слайд 8

Односторонняя хэш-функция:
Message digest cryptographic checksum
Исходные данные: сообщение М любой длины; h

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

Слайд 9

Практическая реализация
MD5
SHA-1
SHA-3 (Keccak)
128-160-224/256/384/512 bit результат
Используют, как правило, два входа: исходное сообщение

и предыдущий хеш

Слайд 10

Secure Hash Algorithm (SHA)
Rfc 3174
160-bit результат
Если исходный текст <2^64, то формирует

160-bit хеш

Слайд 11

Описание алгоритма SHA
Дополнение блоков (padding)
Инициализация 5-ти переменных (MD5-4)
Основной итерационный блок (512

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

Слайд 12

Этапы алгоритма SHA
1. Дополнение блоков (padding)
В начале, сообщение достраивается до длины,

кратной 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.

Слайд 13

Основной итерационный блок алгоритма SHA
1. Подстановка переменных
AA=A; BB=B; CC=C; DD=D; EE=E;
2.

4 раунда по 20 операций (MD5-16). Нелинейные операции, сдвиги и сложения

Слайд 14

Основной итерационный блок алгоритма SHA
3. Расширение сообщения.
4. Сложение результата с промежуточным

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

Слайд 15

Схема выполнения одной операции SHA

Слайд 16

Использование блочных алгоритмов
Использование DES в режиме CBC (Режим сцепления блоков), CFB

(Режим обратной связи по шифрограмме) с фиксированным ключом.
Использование одного ключа

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

Слайд 17

Метод увеличения хэша
Для получения хэш-значения с большей длиной, чем это позволяет

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

Слайд 18

Криптоанализ
1. «Лобовая атака»
Имея h(M), найти M1, такую что h(M1). – 2^160
2.

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

Слайд 19

Применение
Контрольная сумма
Проверка целостности сообщения (файла)
Элемент цифровой подписи
(Аутентификация источника данных)
Элемент аутентификации

Слайд 20

Задачи
Реализовать свою хеш-функцию с результатом в 4 бита
Оценить сложность подделки документа

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

Хеш функції

Содержание

Подходы к контролю целостности данных Контрольная суммаВыработка MDC – Manipulation Detection

Расшифровка номера картыПервая цифра — это основной идентификатор индустрии. 1, 2

Расшифровка номера картыПервые шесть цифр представляют собой идентификационный номер эмитента. Другими

Алгоритм ЛунаАлгоритм вычисление контрольной суммыСтандарт ISO/IEC 7812Описан в 1954, патент 1960Сотрудник

Запатентованная реализация (1960)

Суть алгоритма Луна1. Цифры проверяемой последовательности нумеруются справа налево.2. Цифры, оказавшиеся

Односторонняя хэш-функция:Message digest cryptographic checksumИсходные данные: сообщение М любой длины; h

Практическая реализацияMD5SHA-1SHA-3 (Keccak)128-160-224/256/384/512 bit результатИспользуют, как правило, два входа: исходное сообщение

Secure Hash Algorithm (SHA)Rfc 3174160-bit результатЕсли исходный текст <2^64, то формирует

Описание алгоритма SHAДополнение блоков (padding)Инициализация 5-ти переменных (MD5-4)Основной итерационный блок (512

Этапы алгоритма SHA1. Дополнение блоков (padding) В начале, сообщение достраивается до длины,

Основной итерационный блок алгоритма SHA1. Подстановка переменныхAA=A; BB=B; CC=C; DD=D; EE=E;2.

Основной итерационный блок алгоритма SHA3. Расширение сообщения.4. Сложение результата с промежуточным