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

Криптографска хеш функция се нарича всяка хеш функция, която е криптографски силна, тоест удовлетворяваща редица специфични изисквания.

Формулиране на проблема

Хеш функциите, използвани отдавна в компютърните науки, са функции, математически или по друг начин, които вземат като вход низ с променлива дължина (наречен преобраз) и го преобразуват във фиксиран, обикновено по-кратък низ (наречен хеш стойност) ... Като обикновена хеш функция можете да помислите за функция, която взема първообраз и връща байт, който е XOR на всички входни байтове. Смисълът на хеш функцията е да се получи характерен признак, преобраз-стойност, чрез който се анализират различни преизображения при решаване на обратната задача. Тъй като хеш функцията обикновено е съотношение много към едно, невъзможно е да се каже с пълна мярка, че два струни са еднакви, но те могат да се използват за получаване на приемлива оценка на точността. Еднопосочната хеш функция е хеш функция, която работи само в една посока. Лесно е да се изчисли хеш стойност от предобраз, но е трудно да се създаде преобраз, чиято хеш стойност е равна на дадена стойност. По-горе споменатите хеш функции, най-общо казано, не са еднопосочни: чрез посочване на конкретен байт не е трудно да се създаде низ от байтове, XOR от които дава дадена стойност. Това не е възможно с еднопосочна хеш функция. Хеш функцията е отворена, няма тайна за нейното изчисляване. Сигурността на еднопосочната хеш функция се крие именно в нейната еднопосочност. Изходът няма видима зависимост от записа. Промяната на един бит от изображението променя (средно) половината битове на хеш стойността, известна още като лавинен ефект. Невъзможно е изчислително да се намери първообраз, съответстващ на дадена хеш стойност

Изисквания

За да има хеш функция З. Считан за криптографски силен, той трябва да отговаря на три основни изисквания, на които се основават повечето употреби на хеш функции в криптографията:

Необратимост или устойчивост: за дадена хеш стойност м трябва да е невъзможно изчислително да се намери блокът с данни х, за което Н (X) = m .
Устойчивост на сблъсъци от първи вид или възстановяване на втори прототип: за дадено съобщение М трябва да е изчислително невъзможно да се вземе друго съобщение н, за което H (N) = H (M) .
Устойчивост на сблъсъци от втори вид: трябва да е невъзможно изчислително да вземете чифт съобщения (М, М '), като има същия хеш.

Тези изисквания не са независими:

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

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

Атаката за рожден ден ви позволява да намерите сблъсъци за хеш функция със стойности на дължината н бита средно за около 2 n/2 изчислителна хеш функция. Следователно н - битова хеш функция се счита за криптографски силна, ако изчислителната сложност на намиране на сблъсъци за нея е близка до 2 n/2 .

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

Строителни принципи

Итеративна последователна верига

По принцип конструкцията на хеш функция се основава на итеративна последователна схема (структура на Merkle-Damgard). Ядрото на алгоритъма е функция на свиване - трансформация к вход към н изходни битове където н Е битовата ширина на хеш функцията и к - произволно число по-голямо н . В този случай функцията за свиване трябва да отговаря на всички условия на криптографска сила.

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