Хеш функции: концепция и основи

В различните отрасли на информационните технологии се използват хеш-функции. Те са предназначени, от една страна, за значително опростяване на обмена на данни между потребителите и обработката на файлове, използвани за различни цели, от друга страна, за оптимизиране на алгоритмите за осигуряване на контрол на достъпа до съответните ресурси. Хеш функцията е един от ключовите инструменти за осигуряване на парола за защита на данните, както и организиране на обмена на документи, подписани с електронен подпис. Има голям брой стандарти, чрез които файловете могат да бъдат кеширани. Много от тях са разработени от руски специалисти. В какви варианти могат да бъдат представени хеш-функциите? Какви са основните механизми за тяхното практическо приложение?

Какво е това?

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

характеристики на

Разгледайте ключовите характеристики на изследваните алгоритми. Сред тях:

• наличието на вътрешни алгоритми за преобразуване на данни от първоначалната дължина в по-къса последователност от символи;
• откритост за криптографска проверка;
• наличието на алгоритми за надеждно криптиране на оригиналните данни;
• адаптиране към дешифрирането, когато се използват малки изчислителни мощности.

Сред другите най-важни свойства на хеш функцията:

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

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

Изисквания за хеш

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

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

структура

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

В коя структура може да се използва хеш функция за такива цели? Пример за неговото компилиране може да бъде: H (хеш, т.е. хеш) = f (T (текст), H1), където H1 е алгоритъм за обработка на текст T. Тази функция има T по такъв начин, че без да знае H1, да го отвори като пълнофункционален файлът ще бъде почти невъзможен.

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

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

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

Хеш функция и EDS

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

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

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

Проверка на паролата

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

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

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

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

Сблъсък с хеш

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

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

История на външния вид

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

Популярни Hash стандарти

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

От своя страна, при криптиране, стандартите MD4 и MD5 са широко използвани. Друг популярен криптографски алгоритъм е SHA-1. По-специално, той се характеризира с хеш-размер от 160 бита, който е по-голям от този на MD5 - този стандарт поддържа 128 бита. Има руски стандарти, регламентиращи използването на хеш функции, - ГОСТ Р 34.11-94, както и замяна с ГОСТ Р 34.11-2012. Може да се отбележи, че хеш стойността, предоставена от алгоритмите, приети в Руската федерация, е 256 бита.

Въпросните стандарти могат да бъдат класифицирани по различни причини. Например, има такива, които използват блокови и специализирани алгоритми. Простотата на изчисленията, базирани на стандартите от първия тип, често се придружава от тяхната ниска скорост. Следователно, като алтернатива на блокови алгоритми, могат да се включат тези, които включват по-малко изчислителни операции. Обичайно е да се приписва на високоскоростните стандарти, по-специално гореспоменатите MD4, MD5, както и SHA. Разгледайте по-подробно спецификата на специалните алгоритми на хеширане на примера на SHA.

Характеристики на алгоритъма SHA

Използването на хеш функции, базирани на стандарта SHA, най-често се извършва в областта на разработването на инструменти за цифров подпис за DSA документи. Както отбелязахме по-горе, алгоритъмът SHA поддържа 160-битов хеш (осигуряващ така нареченото "дайджест" на поредица от символи). Първоначално разглежданият стандарт разделя масив от данни на блокове от 512 бита. Ако е необходимо, ако дължината на последния блок не достигне зададената цифра, файловата структура се допълва с 1 и необходимия брой нули. Също така в края на съответния блок съответства кодът, който фиксира дължината на съобщението. Разглежданият алгоритъм включва 80 логически функции, чрез които се обработват 3 думи, представени в 32 бита. Също така в стандартната SHA се използват 4 константи.

Сравнение на алгоритми с хеш

Нека разгледаме как свойствата на хеш функциите, свързани с различни стандарти, корелират, например, сравнявайки характеристиките на руския стандарт ГОСТ Р 34.11-94 и американското SHA, което обсъдихме по-горе. На първо място, трябва да се отбележи, че разработеният алгоритъм в Руската федерация включва изпълнението на 4 операции за криптиране на 1 цикъл. Това съответства на 128 кръга. На свой ред, за 1 кръг, при активиране на SHA се приема, че са изчислени около 20 команди, докато общият брой на кръговете е 80. По този начин, използването на SHA ви позволява да обработвате 512 бита на изходните данни по време на един цикъл. В същото време руският стандарт е способен да извършва операции на цикъл от 256 бита данни.

Специфика на най-новия руски алгоритъм

По-горе, отбелязахме, че стандартът ГОСТ Р 34.11-94 е заменен с по-нова - ГОСТ Р 34.11-2012 "Стрибог". Ние изследваме неговите особености по-подробно.

Чрез този стандарт могат да бъдат въведени криптографски хеш-функции, какъвто е случаят с алгоритмите, обсъдени по-горе. Може да се отбележи, че последният руски стандарт поддържа блок от входни данни в размер на 512 бита. Основните предимства на ГОСТ Р 34.11-2012:

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

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

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

Нека разгледаме по-подробно как видовете алгоритми, които изучаваме, могат да бъдат използвани в областта на криптографията. Ключовото изискване за съответните функции е съпротивлението на сблъсъци, което споменахме по-горе. Това означава, че стойностите на дублираната хеш функция не трябва да се формират, ако тези стойности вече са налице в структурата на съседния алгоритъм. Други критерии, посочени по-горе, също трябва да отговарят на криптографските функции. Ясно е, че винаги има някаква теоретична възможност за възстановяване на изходен файл на базата на хеш, особено ако в достъпа има мощен компютърен инструмент. Този сценарий обаче трябва да бъде минимизиран благодарение на надеждните алгоритми за шифроване. Така че, ще бъде много трудно да се изчисли хеш функцията, ако нейната изчислителна сила съответства на формулата 2 ^ {n / 2}.

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

Итеративни схеми

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

Разбира се, функцията за компресия трябва да отговаря на необходимите критерии за криптографска сила. В интерактивната схема първата операция за обработка на потока входни данни е разделена на блокове, размерът на които се изчислява в битове. Съответният алгоритъм включва и времеви променливи на даден брой битове. Първата стойност използва добре познат номер, докато следващите блокове данни се комбинират със стойността на въпросната функция на изхода. Хеш стойността се превръща в изходните битове за последната итерация, които отчитат целия входящ поток, включително първата стойност. Осигурява се т.нар. "Лавинен ефект" на хеширането.

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

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

Алгоритъм на блока

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

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