KNOW INTUIT, Лекция, Криптографски хеш функции

Целта на лекцията: да се запознаят с понятието "хеш функция", както и с принципите на работа на такива функции.

Концепцията за хеш функция

Хеш функция (хеш функция)е математическа или друга функция, която за низ с произволна дължина изчислява някаква целочислена стойност или някакъв друг низ с фиксирана дължина. Математически това може да се запише като:

където M е оригиналното съобщение, понякога наричанопредобраз, а h е резултатът, наречен хеш стойност (илихеш кодилисводка на съобщението).

Смисълът на хеш функцията е да определи характерната черта на прототипа - стойността на хеш функцията. Тази стойност обикновено има определен фиксиран размер, като например 64 или 128 бита. Хеш кодът може да бъде допълнително анализиран, за да се реши някакъв проблем. Така например хеширането може да се използва за сравняване на данни: ако два масива от данни имат различни хеш кодове, гарантирано е, че масивите ще се различават; ако са еднакви, масивите най-вероятно са еднакви. В общия случай няма едно към едно съответствие между изходните данни и хеш кода поради факта, че броят на стойностите на хеш функцията винаги е по-малък от опциите за входни данни. Следователно има много входни съобщения, които дават едни и същи хеш кодове (такива ситуации се наричат ​​сблъсъци). Вероятността от сблъсъци играе важна роля при оценката на качеството на хеш функциите.

Хеш функциите се използват широко в съвременната криптография.

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

Например, нека оригиналното съобщение, дигитализирано, е както следва (в шестнадесетичен):

Нека преведем съобщението в двоична форма, напишем байтовете един под друг и добавим битовете във всяка колона по модул 2:

Резултатът (0110 0101(2) или 65(16)) ще бъде хеш стойността.

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

Нека формулираме основните изисквания за криптографските хеш функции:

  • хеш функцията трябва да е приложима към съобщение от всякакъв размер;
  • изчисляването на стойността на функцията трябва да бъде достатъчно бързо;
  • като се има предвид стойността на хеш функцията, би трябвало да е трудно (на практика невъзможно) да се намери подходящ предобраз на M;
  • като се има предвид съобщението M, трябва да е трудно да се намери друго съобщение M' със същата хеш стойност като оригиналното съобщение;
  • трябва да е трудно да се намери двойка произволно различни съобщения с една и съща хеш стойност.

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

Понастоящем на практика като хеш функции се използват функции, които обработват входното съобщение блок по блок и изчисляват хеш стойността hi за всеки блок Mi на входното съобщение според зависимостите на формата

където hi-1– резултатът, получен при изчисляване на хеш функцията за предходния блок от входни данни.

В резултат на това изходът на хеш функцията hn е функция на всички n блока на входното съобщение.

Използване на блокови алгоритми за криптиране за формиране на хеш функция

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

Най-лесният начин да използвате блоковия алгоритъм за получаване на хеш код е да шифровате съобщението в режим CBC. В този случай съобщението се представя като поредица от блокове, чиято дължина е равна на дължината на блока на алгоритъма за криптиране. Ако е необходимо, последният блок се допълва отдясно с нули, за да се получи блок с желаната дължина. Хеш стойността ще бъде последният шифрован блок от текст. Ако се използва силен алгоритъм за блоково криптиране, получената хеш стойност ще има следните свойства:

  • практически е невъзможно да се изчисли хеш стойност за даден отворен масив от информация, без да се знае ключа за криптиране;
  • практически е невъзможно да изберете отворени данни за дадена хеш стойност, без да знаете ключа за криптиране.

Така генерираната хеш стойност обикновено се наричаmockinsertилиauthenticatorи се използва за проверка на целостта на съобщението. По този начин имитационната вложка е контролна комбинация, която зависи от отворени данни и секретна информация за ключ. Целта на използването на имитатори на вмъкване е да се открият всички случайни или умишлени промени в масива от информация. Стойността, получена от хеш функцията при обработката на входното съобщение, се прикачва към съобщението в момента, когато е известно, чесъобщението е правилно. Получателят проверява целостта на съобщението, като изчислява симулакрума на вмъкване на полученото съобщение и го сравнява с получения хеш код, който трябва да бъде предаден по сигурен начин. Един такъв защитен метод би бил шифроването на фалшивата вложка с частния ключ на подателя, т.е. създаване на подпис. Също така е възможно да шифровате получения хеш код със симетричен алгоритъм за шифроване, ако подателят и получателят имат общ симетричен ключ за шифроване.

Посоченият процес на получаване и използване на имитация на вложка е описан във вътрешния стандарт GOST 28147-89. Стандартът предлага да се използват най-малко значимите 32 бита от блока, получен на изхода от операцията за криптиране на цялото съобщение в режим на верига на шифровани блокове, за да се контролира целостта на предаденото съобщение. По същия начин всеки алгоритъм за блоково симетрично криптиране може да се използва за формиране на имитация на вмъкване.

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

По този начин, ако напишем обичайната схема за криптиране на съобщение M, използвайки блоков шифър f на ключ K като E=f(M,K) , тогава схемата за получаване на хеш код h, използвайки алгоритъма, описан по-горе, може да бъде представена като

Някаква константа се приема като начален хеш код h0. Шифроването се извършва в режим на проста замяна. Когато използвате този метод, размерът на блока е същият като дължинатаключът и размерът на хеш стойността ще бъдат дължината на блока.

Възможен е и друг начин за използване на блоков шифър в режим на проста замяна: елементите на съобщението се криптират с хеш стойностите, получени в предишната стъпка:

Всъщност са възможни още няколко схеми за използване на блоков шифър за формиране на хеш функция. Нека Мi е блокът на оригиналното съобщение, hi е стойността на хеш функцията на i-тия етап, f е блоковият алгоритъм за криптиране, използван в режима на проста замяна, е операцията на добавяне по модул 2. Тогава са възможни например следните схеми за генериране на хеш функцията:

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

Основният недостатък на хеш функциите, проектирани на базата на блокови алгоритми, е тяхната относително ниска скорост. Необходимата криптографска сила може да се постигне и с по-малък брой операции върху входните данни. Има по-бързи алгоритми за хеширане, проектирани независимо, от нулата, въз основа на изискванията за криптографска сила (най-често срещаните от тях са MD5, SHA-1, SHA-2 и GOST R 34.11-94).