5-Мавзу: Хэш функциялар Криптология кафедраси кат.ўқит., Мардиев У. Р. Хеш функциялар

Хеш функциялар (Тугилган кун хужуми)

• Ушбу хужум коллизияни топишга каратилган булиб тугилган кун муаммоси ёки тугилган кун парадокси га асосланади. Бу муаммо минимал сондаги одамлар орасида камида иккита одамнинг тугилган кунининг бир хил булиш эхтимоли дан катта булиши хакида булиб, буни хэш функцияларга кўллаганда бир тугилган кунга эга булган иккита инсоннинг мавжудлигини билдиради.
• Ушбу хужумда хужумчи махсус коллизияни топишдан кура ихтиёрий коллизияни топишга харакат килади.

•  

Хеш функциялар (Тугилган кун хужуми)

• Агар хужумчи та одамлар орасидан бирор махсус коллизияни, яъни бир одамнинг тугилган куни билан бир хил булган кунни топаётган булса, у холда бу эхтимол куйидагига тенг булади:
• Бу эхтимоллик дан катта булиши учун N киймат 254 дан катта булиши талаб этилади. Ушбу ғояни хэш функцияга тадбик этилса, бирор хабар ва у нинг хэш киймати берилганда хэш кийматлари тенг булган турли маълумотни топиш масаласи каралади.

•  

Хеш функциялар (Тугилган кун хужуми)

• Бироқ ҳужумчидан N туғиган кунлар орасида ихтиёрий коллизияни топиш эҳтимоли қуйидагига тенг бўлади.
• Ушбу холда эхтимоллик дан катта булиши учун имкониятнинг ўзи етарли булади.
• Агар хужумчи п битли хэш киймат чикарувчи хэш функция учун ундан кўп булган эхтимоллик билан ихтиёрий коллизияни топиш! 2п/2 га тенг булади.

•  

Хеш функциялар (Тугилган кун хужуми)

• Агар хэш функция учун хэш кийматнинг узунлиш битга тенг булса ва у эхтимоллик билан аникланиши учун керак булган хисоблашлар сони N га тенг булса. улар орасидаги богликликнинг ментал куриниши куйидагига тенг булади:

•  

Криптографик бўлмаган хеш функциялар

• Кўплаб криптографик хешлардан фойдаланиб келинади, бироқ уларнинг ҳеч бири криптграфик иловалар учун мос эмас.
• Қуйидаши маълумотни кўриб чиқсак