Криптографические хэш функции

Криптографической хэш-функцией называется всякая хэш-функция, являющаяся криптостойкой, то есть, удовлетворяющая ряду специфичных требований.

Contents

  • 1 Постановка задачи
  • 2 Требования
  • 3 Принципы построения
    • 3.1 Итеративная последовательная схема
    • 3.2 Сжимающая функция на основе симметричного блочного алгоритма
  • 4 Применения
    • 4.1 Электронная цифровая подпись
    • 4.2 Проверка пароля
  • 5 Случайный оракул
  • 6 Атака на основе парадокса дней рождений
  • 7 Сравнительная характеристика наиболее известных функций
  • 8 Глоссарий
  • 9 Литература

Постановка задачи

Хэш-функции, долгое время использующиеся в компьютерных науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, дли- ны (называемую значением хэш-функции). В качестве простой хэшфункции можно рассматривать функцию, которая получает прообраз и возвращает байт, представляющий собой XOR всех входных байтов. Смысл хэш-функции состоит в получении характерного признака, прообраза-значения, по которому анализируются различные прообразы при решении обратной задачи. Так как обычно хэш-функция представляет собой соотношение «многие к одному», невозможно со всей деленностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности. Однонаправленная хэш-функция – это хэш-функция, которая работает только в одном направлении. Легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш-функции которого равно заданной величине. Упоминавшиеся ранее хэш-функции, вообще говоря, не являются однонаправленными: задав конкретный байт, не представляет труда создать строку байтов, XOR которых дает заданное значение. С однонаправленной хэш-функцией такой вариант невозможен. Хэш-функция является открытой, тайны ее расчета не существует. Безопасность однонаправленной хэш-функции заключается именно в ее однонаправленности. У выхода нет видимой зависимости от входа. Изменение одного бита прообраза приводит к изменению (в среднем) половины битов значения хэш-функции, что известно также как лавинный эффект. Вычислительно невозможно найти прообраз, соответствующий заданному значению хэш-функции

Требования

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

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

Данные требования не являются независимыми:

  • Обратимая функция нестойка к коллизиям первого и второго рода.
  • Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

Атака «дней рождения» позволяет находить коллизии для хэш-функции с длиной значений n битов в среднем за примерно 2 n/2 вычислений хэш-функции. Поэтому n – битная хэш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2 n/2.

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

Принципы построения

Итеративная последовательная схема

В общем случае, в основе построения хэш-функции лежит итеративная последовательная схема (Структура Меркля-Дамгарда). Ядром алгоритма является сжимающая функция — преобразование k входных в n выходных бит, где n — разрядность хэш-функции, а k — произвольное число большее n. При этом сжимающая функция должна удовлетворять всем условиям криптостойкости.

Входной поток разбивается на блоки по (k-n) бит. Алгоритм использует временную переменную размером в n бит, в качестве начального значения которой берется некое произвольное число. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Значением хэш-функции являются выходные n бит последней итерации. Каждый бит выходного значения хэш-функции зависит от всего входного потока данных и начального значения. Таким образом достигается лавинный эффект.

При проектировании хэш-функций на основе итеративной схемы возникает проблема с размером входного потока данных. Размер входного потока данных должен быть кратен (k-n). Как правило, перед началом алгоритма данные расширяются неким, заранее известным, способом.

Помимо однопроходных алгоритмов, существуют многопроходные алгоритмы, в которых ещё больше усиливается лавинный эффект. В данном случае, данные сначала повторяются, а потом расширяются до необходимых размеров.

Сжимающая функция на основе симметричного блочного алгоритма

В качестве сжимающей функции можно использовать симметричный блочный алгоритм шифрования. Для обеспечения большей безопасности можно использовать в качестве ключа блок данных предназначенный к хэшированию на данной итерации, а результат предыдущей сжимающей функции в качестве входа. Тогда результатом последней итерации будет выход алгоритма. В таком случае безопасность хэш-функции базируется на безопасности используемого алгоритма.

A, B и C могут принимать значения Mj , Hj-1 , Mj ⊕ Hj-1 или быть константой, где Mj — j – ый блок входного потока, ⊕ — сложение по модулю 2, Hj — результат j – ой итерации.

Обычно при построении хэш-функции используют более сложную систему. Обобщенная схема симметричного блочного алгоритма шифрования изображена на рис.2

Таким образом, мы получаем 64 варианта построения сжимающей функции. Большинство из них являются либо тривиальными, либо небезопасными. Ниже изображены четыре наиболее безопасные схемы при всех видах атак.

Основным недостатком хэш-функций, спроектированных на основе блочных алгоритмов, является низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хэширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них — MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

Применения

Электронная цифровая подпись

Электронная цифровая подпись (ЭЦП) — по сути шифрование сообщения алгоритмом с открытым ключом. Текст, зашифрованный секретным ключом, объединяется с исходным сообщением. Тогда проверка подписи — расшифрование открытым ключом, если получившийся текст аналогичен исходному тексту — подпись верна.

Использование хэш-функции позволяет оптимизировать данный алгоритм. Производится шифрование не самого сообщения, а значение хэш-функции взятой от сообщения. Данный метод обеспечивает следующие преимущества:

  • Понижение вычислительной сложности. Как правило, документ значительно больше его хэша.
  • Повышение криптостойкости. Криптоаналитик не может, используя открытый ключ, подобрать подпись под сообщение, а только под его хэш.
  • Обеспечение совместимости. Большинство алгоритмов оперирует со строками бит данных, но некоторые используют другие представления. Хэш-функцию можно использовать для преобразования произвольного входного текста в подходящий формат.

Проверка пароля

В большинстве случаев парольные фразы не хранятся на целевых объектах, хранятся лишь их хэш-значения. Xранение самих паролей нецелесообразно, так как в случае несанкционированного доступа к файлу с паролями злоумышленник получает их в открытом и сразу готовом к использованию виде, а при хранении хэш-значений он узнает лишь хэши, которые не обратимы в исходные данные. В ходе процедуры аутентификации вычисляется хэш-значение введённого пароля, и сравнивается с хранимым.

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows. В них хранятся лишь хэш-значения парольных фраз из учётных записей пользователей.

Данная система подразумевает передачу сообщения по защищенному каналу, то есть каналу, из которого криптоаналитику невозможно перехватить сообщения или послать свое. Иначе он может перехватить хэш-значение пароля, и использовать его для дальнейшей нелегальной аутентификации. Защищаться от подобных атак можно при помощи метода «тройного рукопожатия».

Пусть некий клиент, с именем name, производит аутентификацию по парольной фразе, pass, на некоем сервере. На сервере хранится значение хэш-функции H(pass,R2), где R2 — псевдослучайное, заранее выбранное, число. Клиент посылает запрос (name, R1), где R1 — псевдослучайное, каждый раз новое, число. В ответ сервер посылает значение R2. Клиент вычисляет значение хэш-функции H(R1,H(pass,R2)) и посылает его на сервер. Сервер также вычисляет значение H(R1,H(pass,R2)) и сверяет его с полученным. Если значения совпадают — аутентификация верна.

В такой ситуации пароль не хранится открыто на сервере и, даже перехватив все сообщения между клиентом и сервером, криптоаналитик не может восстановить пароль, а передаваемое хэш-значение каждый раз разное.

Случайный оракул

Напомним свойство перемешивания, которое присуще функции хэширования: при любом аргументе хэширование неотличимо с вычислительной точки зрения от строки битов, равномерно распределенных в области значений функции. Если заменить последнее выражение фразой «принадлежит генеральной совокупности равномерно распределенных величин», мы получим весьма мощную гипотетическую функцию, называемую случайный оракул (randome oracle). Он обладает тремя свойствами: детерминированность, эффективность, равномерность распределения результирующих значений. Однако,все известные вычислительные модели в той или иной степени не соответствуют модели случайного оракула. Равномерность и детерминированность величин, вычисляемых случайным оракулом, означает, что энтропия его результатов выше, чем энтропия чисел, поступающих на вход. Поскольку свойства перемешивания, которым обладает хэш-функция является лишь предположением вычислительного характера, реальная хэш-функция должна обеспечивать лишь вычислительную неразличимость, то есть результаты должны иметь некое распределение вероятностей в области значений, которое невозможно определить за полиномиальное время. Итак, реальные функции хэширования лишь имитируют поведение случайного оракула, хоть и с высокой точностью.

Атака на основе парадокса дней рождений

Предположим, что функция хэширования h действительно является случайным оракулом. В атаке по методу квадратного корня (атака на основе парадокса дней раждения) предполагается, что для обнаружения коллизий с ненулевой вероятностью достаточно выполнить 2 в степени |h|/2 случайных вычислений значения функции хэширования. Для организации атаки на основе парадокса дней рождений атакующий должен сгенерировать пары «сообщение-хэшированное значение», пока не обнаружаться два сообщения m и m`, удовлетворяющие условиям m не равно m`, h(m)=h(m`). Такая пара сообщений называется коллизией(collision) функции хэширования h. Например, для функции хэшироания SHA-1 выполняется условие |h|=160, а значит его стойкость на основе парадокса дней рождения оценивается величиной 280.

Сравнительная характеристика наиболее известных функций

Существует длинный перечень криптографических хеш-функций, хотя многие из них были признаны уязвимыми и не должны быть использованы. Даже если хэш-функция никогда не была взломана, успешная атака против ослабленного варианта может подорвать доверие экспертов и привести к отказу от хэш-функции. Например, в августе 2004 года были найдены слаюости в ряде хэш-функций , которые были популярны в то время, в том числе SHA-0, RIPEMD и MD5. Это поставило под сомнение долгосрочную безопасность более поздних алгоритмов, которые являются производными от этих хеш-функций — в частности, SHA-1 ( усиленный вариант SHA-0 ), RIPEMD- 128 , и RIPEMD-160 (оба усиленные версии RIPEMD ). Ни SHA-0 , ни RIPEMD широко не используются, так как они были заменены на более усиленные версии. По состоянию на 2009, двумя наиболее часто используемыми криптографическими хэш-функциями являются MD5 и SHA-1. Тем не менее, MD5 была взломана, атака против него была также использована для взлома SSL в 2008. Функции SHA-0 и SHA-1 были разработаны в АНБ. В феврале 2005 года сообщалось, что проведена успешная атака на SHA-1, найдены коллизии за, примерно, 269 операций хэширования, а не в 280, которые ожидаются для 160-битной хэш-функции. В августе 2005 года сообщалось, об еще одном успешном нападении на SHA-1: нахождение коллизии за 263 операций. Новые приложения могут избежать этих проблем с безопасностью функции SHA-1 с помощью более продвинутых членов семьи SHA , например, SHA-2. Тем не менее, для обеспечения долгосрочной надежности приложений, использующих хэш-функций, был устроен конкурс на лучший проект — замену SHA-2. 2 октября 2012 года, Keccak был выбран в победителем в конкурсе, устроенном NIST. Версия этого алгоритма как ожидается, станет стандартным FIPS в 2014 году под названием SHA-3. Некоторые из следующих алгоритмов часто используется в приложениях криптографии.Обратите внимание, что этот список не включает кандидатов в текущем конкурсе NIST.

Демонстрационная программа, показывающая работу алгоритма SHA-1:
Исходный код на C#: File:SHA1 src.zip
Исполняемый файл: File:SHA1.zip

Демонстрационная программа, показывающая работу алгоритма MD2:
Исходный код на ЯП Python: File:Md2 src.zip
Исполняемый файл: File:Md2.zip

Глоссарий

  • Атака «дней рождения»
  • Аутентификация
  • Бит
  • Восстановление прообраза
  • Вычислительная сложность
  • Ключи в криптографии
  • Коллизия хэш-функции
  • Криптостойкость
  • Лавинный эффект
  • Хэш-функция
  • Электронная цифровая подпись

Литература

Перейти к списку литературы.

Составители

Комаров А.И. / Митцель А.С.

Назад к оглавлению </p>

Криптографические методы защиты информации

Лекции

10. ХЕШ-ФУНКЦИИ

10.1. Основные понятия.

10.2. MD5.

10.3. Применение шифрования для получения хеш-образа.

Вопросы для самопроверки.

10.1. Основные понятия

Хеширование (иногда хэширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, входной массив – прообразом, а результаты преобразования — хешем, хеш-кодом, хеш-образом, цифровым отпечатком или дайджестом сообщения (англ. message digest).

Хеш-функция – легко вычислимая функция, преобразующая исходное сообщения произвольной длины (прообраз) в сообщение фиксированное длины (хеш-образ), для которой не существует эффективного алгоритма поиска коллизий.

— для данного значения h(x) невозможно найти значение аргумента x. Такие хеш-функции называют стойкими в смысле обращения или стойкими в сильном смысле;

— для данного аргумента x невозможно найти другой аргумент y такой, что h(x) = h(y). Такие хеш-функции называют стойкими в смысле вычисления коллизий или стойкими в слабом смысле.

В случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то это значение называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой.

На практике хеш-функции используют в следующих целях:

— для ускорения поиска данных в БД;

— для проверки целостности и подлинности сообщений;

— для создания сжатого образа, применяемого в процедурах ЭЦП;

— для защиты пароля в процедурах аутентификации.

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

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

Процедура вычисления (стандартная схема алгоритма) хеш-функции представлена на следующем рисунке.

Рис.10.1. Процедура вычисления значения хеш-функции

1) К исходному сообщению Т добавляется вспомогательная информация (например, длина прообраза, вспомогательные символы и т.д.) так, чтобы длина прообраза Х стала кратной величине Lбл, определенной спецификацией (стандартом) хеш-функции.

2) Для инициализации процедуры хеширования используется синхропосылка y0.

3) Прообраз X разбивается на n блоков xi (i = 1 .. n) фиксированной длины Lбл, над которыми выполняется однотипная процедура хеширования f(yi-1, xi), зависящая от результата хеширования предыдущего блока yi-1.

4) Хеш-образом h(T) исходного сообщения Т будет результат процедуры хеширования yn, полученный после обработки последнего блока xn.

10.2. MD5

MD5 (англ. Message Digest 5) – 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 г. Является улучшенной в плане безопасности версией MD4 .

Ниже приведен алгоритм вычисления хеша.

1. Выравнивание потока.

В конец исходного сообщения, длиной L, дописывают единичный бит, затем необходимое число нулевых бит так, чтобы новый размер L’ был сравним с 448 по модулю 512 (L’ mod 512 = 448). Добавление нулевых бит выполняется, даже если новая длина, включая единичный бит, уже сравнима с 448.

2. Добавление длины сообщения.

К модифицированному сообщению дописывают 64-битное представление длины данных (количество бит в сообщении). Т.е. длина сообщения T становится кратной 512 (T mod 512 = 0). Если длина исходного сообщения превосходит 264 — 1, то дописывают только младшие 64 бита. Кроме этого, для указанного 64-битного представления длины вначале записываются младшие 32 бита, а затем старшие 32 бита.

3. Инициализация буфера.

Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения (шестнадцатеричное представление):

A = 67 45 23 01;
B = EF CD AB 89;
C = 98 BA DC FE;
D = 10 32 54 76.

В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.

4. Вычисление хеша в цикле.

Исходное сообщение разбивается на блоки T, длиной 512 бит. Для каждого блока в цикле выполняется процедура, приведенная на рис.10.2. Результат обработки всех блоков исходного сообщения в виде объединения 32-битных значений переменных ABCD и будет являться хешем.

Рис.10.2. Шаг основного цикла вычисления хеша

В каждом раунде над переменными ABCD и блоком исходного текста Т в цикле (16 итераций) выполняются однотипные преобразования по следующей схеме.

Рис.10.3. Одна итерация цикла раунда

Условные обозначения.

1) RF — раундовая функция, определяемая по следующей таблице.

Таблица 10.1. Раундовые функции RF

№ раунда Обозначение
функции
Формула расчета
1 F F(B, C, D) = (B ∧ C) ∨ (¬B ∧ D)
2 G G(B, C, D) = (B ∧ D) ∨ (¬D ∧ C)
3 H H(B, C, D) = B ⊕ C ⊕ D
4 I I(B, C, D) = C ⊕ (¬D ∨ B)

2) tj — j-ая 32-битовая часть блока исходного сообщения Т с обратным порядком следования байт;

3) ki — целая часть константы, определяемой по формуле

ki = 232 * | sin(i + 16 * (r — 1)) |, (10.1)

где i – номер итерации цикла (i = 1..16);
r – номер раунда (r = 1..4).

Аргумент функции sin измеряется в радианах.

4) ⊞ – сложение по модулю 232.

5) <<< si – циклический сдвиг влево на si разрядов.

Используемая 32-битовая часть блока исходного сообщения tj и величина циклического сдвига влево si зависят от номера итерации и приведены в следующей таблице.

Таблица 10.2. Величины, используемые на шаге цикла раунда

№ итерации 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Раунд 1 tj t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16
si 7 12 17 22 7 12 17 22 7 12 17 22 7 12 17 22
Раунд 2 tj t2 t7 t12 t1 t6 t11 t16 t5 t10 t15 t4 t9 t14 t3 t8 t13
si 5 9 14 20 5 9 14 20 5 9 14 20 5 9 14 20
Раунд 3 tj t6 t9 t12 t15 t2 t5 t8 t11 t14 t1 t4 t7 t10 t13 t16 t3
si 4 11 16 23 4 11 16 23 4 11 16 23 4 11 16 23
Раунд 4 tj t1 t8 t15 t6 t13 t4 t11 t2 t9 t16 t7 t14 t5 t12 t3 t10
si 6 10 15 21 6 10 15 21 6 10 15 21 6 10 15 21

После 4 раундов новое (модифицированное) значение каждой из переменных ABCD складывается (⊞) с исходным (значением переменной до 1-го раунда).

5. Перестановка байт в переменных ABCD. После обработки всех блоков исходного сообщения для каждой переменной выполняется обратная перестановка байт.

Поиск коллизий.

В 2004 г. китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии.

10.3. Применение шифрования для получения хеш-образа

Для выработки устойчивого к коллизиям хеш-образа могут применяться специальные режимы, предусмотренные в блочных шифрах (например, сцепление блоков шифра у DES), или в самой хеш-функции, как составная часть, может использоваться один из режимов блочного шифра (например, составной часть хеш-функции по ГОСТ 34.11-941 является режим простой замены алгоритма криптографического преобразования по ГОСТ 28147-892).

Напомним что в случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то хеш-образ называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой.

В качестве примера приведем режим DES-СВC (сцепление блоков шифра — Cipher Block Chaining).

Рис.10.4. Схема алгоритма DES в режиме сцепления блоков шифра

Последний зашифрованный блок Cn и есть хеш-образ сообщения T = {T1, T2, …, Tn}.

1ГОСТ 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования».

2ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».

Хэш функции Нестеров Антон

План доклада Что это такое Зачем оно надо Примеры

Hash-функция Пример не из криптографии – Хранение словаря Слово hash Word

Коллизии Пример не из криптографии – Хранение словаря Слово hash Word Зебра hash

Практическое использование Банкомат Цифровая подпись Быстро вычислимые Не обратимые Зная M сложно вычислить N такое, что H(M)=H(N) Кроме того, сложно найти такие P и Q, что H(P)=H(Q) Авторизация клиент-сервер

Пример взлома Контракт 1 Контракт

Нахождение коллизий Метод дней рождений Сколько человек должно быть в комнате, чтобы вероятность того, что найдется человек родившийса с вами в один день была равна 0.5 ??? Сколько человек должно быть в комнате, чтобы вероятность того, чтобы нашлась пара людей, родившихся в один день была 0.5 ???

Требования к функции Актуальный размер кэша Для 16 байтогого кэша (128 бит) 2 64 различных документов Secure Hash Standard 160 бит 2 64 Специальный метод для удлиннения хэш-значений Прибавить хэш значение к исходному сообщению, а затем повторить все заново Отсутствие коллизий осмысленных строк

Немного примеров из истории Snefru Ральф Меркл N-hash 1990 MD4, MD5 Рон Ривест SHA RIPE-MD HAVAL ГОСТ Р Использование блочных шифров

Взломы и попытки взломов Некоторые алгоритмы были вломаны Найдены алгоритмы нахождения коллизий Некоторые почти взломаны Найдены алгоритмы нахождения предколлизий коллизий за меньшее время коллизий в укороченных версиях Атака на 7 из 10 уровней AES Антуан Жу – работа о мульти хэш-функциях

MAC Message authentication code Хэш функция зависит от ключа Можно менять ключ для дополнительной проверки В качестве МАС можно использовать обычный хэш H(K,H(K,M)) H(K,p,H,M) Сложно подобрать ключ Вычислить значение хэша для другого ключа

Определения Определение hash-функции Функция H Или семейство Пользуясь предыдущим примером: D строчки русских букв R число от 0 до H: K ×D R. H K : D R

Определения Обратная функция Коллизия H K1 (y) = { x D : H K (x) = y } H K (x 1 ) =HK(x2)HK(x2)

Нахождение коллизий Три типа устойчивости CR2-KK Collision free, collision resistant CR1-KK Universal one-way CR0 Universal

Три вида атак на нахождение коллизий CR2-KK Найти коллизии для конкретной функции CR1-KK Подобрать пару к заданному значению, образующую коллизию для конкретгой функции. СК0 Найти коллизию для семейства функций

Криптографические хэш функции

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *