Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

"Tug'ilgan kun paradoksi"

Keyinchalik murakkab hash funktsiyalarini ko'rib chiqishdan oldin, siz oddiy hash funktsiyalariga bitta aniq hujumni tahlil qilishingiz kerak.

"Tug'ilgan kun paradoksi" deb nomlangan narsa quyidagicha. Aytaylik, xesh funktsiyasining chiqish qiymatlari soni N   teng n . Qanday raqam bo'lishi kerak k shunday qilib, ma'lum bir qiymat uchun X   va qadriyatlar Y1, , Yk   tenglik kamida bitta Yi uchun ehtimollik

H (X) \u003d H (Y)

0,5 dan yuqori bo'lishi kerak edi.

Biri uchun Y   bu ehtimollik H (X) \u003d H (Y) ga teng 1 / n .

Shunga ko'ra, ehtimollik  ga teng 1 - 1 / n .

Agar yaratsangiz k   qiymatlar bo'lsa, ularning har biri uchun tasodif bo'lmasligi ehtimolligi bitta qiymatga mos keladigan ehtimolliklarning ko'payishiga teng, ya'ni. (1 - 1 / n) k .

Shuning uchun kamida bitta matchning ehtimoli