Еднопосочни хеш функции

Еднопосочни хеш функции - раздел Компютри, глава 18.

Глава 18

Еднопосочни хеш функции

Дължини на еднопосочни хеш функции

Преглед на еднопосочните хеш функции

Фиг. 18-1. Еднопосочна функция

Хешираният вход трябва по някакъв начин да съдържа двоично представяне на дължината на цялото съобщение. Това преодолява потенциалния проблем, че съобщения с различна дължина могат да произведат една и съща хеш стойност [1069, 414]. Този метод понякога се наричаMD Gain [930].

Различни изследователи предполагат, че ако функцията за компресия е сигурна, тогава този метод на x-esching входни данни с произволна дължина също е сигурен - но нищо не е доказано [1138, 1070, 414].

Много е писано по темата за проектиране на еднопосочни хеш функции. По-подробна математическа информация може да бъде намерена [1028, 793, 791, 1138, 1069, 414, 91, 858, 1264]. Може би най-разумната интерпретация на еднопосочните хеш функции е тезата на Bart Preneel [1262].

Snefru е еднопосочна хеш функция, разработена от Ralph Merkle [1070]. (Снефру, подобно на Хуфу и Хефрен, е бил египетски фараон.) Снефру хешира съобщения с произволна дължина, превръщайки ги в 128-битови 256-битови стойности.

Първо, съобщението се разделя на части с дължина 512-от. (Променливаm е дължината на хеш стойността.) Ако изходът е 128-битова стойност, тогава парчетата са дълги 384 бита, а ако изходът е 128-битова стойност, тогава парчетата са дълги 256 бита.

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

Функцията H се основава на E, функция за обратим блоков шифър, която работи с 512 бита

блокове. H са последнитеmбита на изход E, XORed с първитеmбита на вход E.

Сигурността на Snefru разчита на функцията E, която рандомизира данните в множество преминавания. Всяко преминаване се състои от 64 рандомизирани етапа. Всеки етап използва различен байт данни като вход към S-box. Изходната дума се подлага на XOR с две съседни думи на съобщение. Конструкцията на S-кутиите е подобна на конструкцията на S-кутиите в Khafre (вижте раздел 13.7). Освен това се извършват редица циклични смени. Оригиналният Snefru се състоеше от два прохода.

Криптоанализ Снефру

M-хеш

N-hash е алгоритъм, изобретен през 1990 г. от изследователи на Nippon Telephone и Telegraph, същите хора, които изобретиха FEAL [1105, 1106]. Пи-хешът използва 128-битови блокове за съобщения, сложна рандомизираща функция, подобна на FEAL, и произвежда 128-битова хеш стойност.

Хеш-стойността на всеки 128-битов блок е функция на блока и хеш-стойността на предишния блок.

R0 = /, където / е произволна начална стойност

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

Функцията g е доста сложна. Алгоритъмна схемададено на 16-ти. Първо, лявата и дясната 64-битова половина на 128-битовата хеш стойност на предишния блок Rn се разменят и след това се извършва XOR с повтарящия се модел (128-битов) и XOR с текущия блок съобщение Mn. След това тази стойност се каскадира вN(на фигуритеN=8) етапи на обработка. Другият вход към етапа на обработка е предишната хеш стойност XOR с една от осемте двоични константи.

EXG: пермутация на лява и дясна частv.1010 . 1010 (двоичен, 128 бита) PS: етап на обработка C-=bAy1 6CD-2 bD3 bD4 : конкатенация b: 000 . 0 (двоичен, 24 бита) d.L=4*(/-1)+/s(/s=1,2,3,4,A]k -дължина 8 бита)Hi = g(Mi,Hiu)® Mi®Hiu