Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

Shifrlangan bloklar zanjiridan foydalanish

Shifrlangan bloklar zanjirini yaratishga asoslangan turli xil hash funktsiyalari mavjud, ammo maxfiy kalitdan foydalanmasdan. Bunday hash funktsiyalaridan biri Rabin tomonidan taklif qilingan. Xabar M   belgilangan uzunlikdagi bloklarga bo'linadi M1, M2 ,. . . , MN   va hesh kodini hisoblash uchun DES kabi nosimmetrik shifrlash algoritmidan foydalanadi G   quyida bayon qilinganidek:

H 0   - boshlang'ich qiymati H i = E mil G = H n

Bu SHS rejimida shifrlashdan foydalanishga o'xshaydi, ammo bu holda hech qanday maxfiy kalit mavjud emas. Har qanday oddiy xesh funktsiyasida bo'lgani kabi, ushbu algoritm "tug'ilgan kunga hujum" ga sezgir va agar DES shifrlash algoritmi bo'lsa va faqat 64 bitli xesh kod yaratilsa, u holda tizim juda zaif hisoblanadi.

Tug'ilgan kun kabi boshqa hujumlarni amalga oshirish mumkin, hatto dushman faqat bitta xabarga va unga tegishli shifrlangan xesh kodga kirish huquqiga ega bo'lsa ham, bir necha juft xabarlarni va shifrlangan xesh kodlarni ololmasa ham mumkin. Quyidagi stsenariy mavjud bo'lishi mumkin: dushman xabarni autentifikator bilan shifrlangan hash kod ko'rinishida tutib olgan va faraz qilinmagan hash kodning uzunligi bor deb taxmin qiling. m   bitlar. Keyin dushman quyidagi harakatlarni bajarishi kerak:

Yuqorida tavsiflangan algoritmdan foydalanib, shifrlanmagan hesh kodini hisoblang G .

Soxta xabarni quyidagicha yarating Q1, Q2,. . . , QN-2 .

Hisoblang H i \u003d E Qi   uchun 1 <= i <= N-2 .

· Yarating 2 m / 2   tasodifiy bloklar X   va har bir bunday blok uchun X   hisoblash E X . Ixtiyoriy yarating 2 m / 2   tasodifiy bloklar Y   va har bir blok uchun Y   hisoblash D Y [G] qayerda D   - mos keladigan dekodlash funktsiyasi E . "Tug'ilgan kun paradoksi" ga asoslanib, shuni aytish mumkinki, yuqori ehtimollik bilan ushbu ketma-ketlik bloklarni o'z ichiga oladi X   va Y   shunday E X \u003d D Y [Y] .

· Xabar yarating Q1, Q2,. . . , QN-2, X, Y . Ushbu xabarda hash kod mavjud. G   va shuning uchun shifrlangan autentifikator bilan foydalanish mumkin.

Hujumning bu shakli o'rtadagi hujum deb nomlanadi. Turli tadqiqotlar blokirovka zanjiri yondashuvini takomillashtirishning nozik usullarini taklif qiladi. Masalan, Devis va Prays quyidagi variantni tavsiflagan:

Boshqa variant ham mumkin:

Biroq, ushbu ikkala sxemada turli xil hujumlarda ham zaifliklar mavjud. Umumiy holda, «tug'ilgan kunga hujum» ning biron-bir shakli maxfiy kalitni ishlatmasdan shifrlangan bloklar zanjiridan foydalanishni o'z ichiga oladigan xesh algoritmi bilan muvaffaqiyatli bo'lganligini ko'rsatish mumkin.

Keyingi tadqiqotlar hash funktsiyalarini yaratishda boshqa yondashuvlarni izlashga qaratilgan edi.

MD5 xesh funktsiyasi

MITning Ron Rivest tomonidan ishlab chiqilgan MD5 xabar hazm qilish algoritmini (RFC 1321) ko'rib chiqing.

  MD5 ijro mantig'i

Algoritm kirishda ixtiyoriy uzunlikdagi xabarni oladi va chiqish sifatida 128-bitli xabar hazmini yaratadi. Algoritm quyidagi bosqichlardan iborat:

Shakl 8.1.MD5 ijro mantig'i