Kriptografik xesh funksiyasi. Xesh nima va u nima uchun

Keyingi maqolada
MD algoritmlarining umumiy ko'rinishi (MD4, MD5, MD6).
Adabiyot
A.P.Alferov, Kriptografiya asoslari.
Bryus Shnayer, Amaliy kriptografiya.
Izoh: Ushbu ma'ruzada xesh-funksiya tushunchasi, shuningdek, xesh-funksiyalarni yaratish algoritmlari haqida qisqacha ma'lumot berilgan. Bundan tashqari, xesh funktsiyasini yaratish uchun blokli shifrlash algoritmlaridan foydalanish imkoniyati ko'rib chiqiladi.
Ma’ruzaning maqsadi: “xesh-funksiya” tushunchasi, shuningdek, bunday funksiyalarning ishlash tamoyillari bilan tanishish.
Xesh funktsiyasi tushunchasi
Xesh funktsiyasi ixtiyoriy uzunlikdagi satr uchun ba'zi bir butun qiymatni yoki qat'iy uzunlikdagi boshqa qatorni hisoblaydigan matematik yoki boshqa funktsiyadir. Matematik jihatdan uni quyidagicha yozish mumkin:
bu erda M - asl xabar, ba'zan chaqiriladi prototip va h - hash qiymati deb ataladigan natija (va shuningdek hash kodi yoki xabarlarni hazm qilish(ingliz tilidan. xabar dayjesti)).
Xesh funktsiyasining ma'nosi preimagening xarakterli xususiyatini - hash funktsiyasining qiymatini aniqlashdir. Ushbu qiymat odatda 64 yoki 128 bit kabi ma'lum bir qattiq o'lchamga ega. Xesh-kod har qanday muammoni hal qilish uchun qo'shimcha tahlil qilinishi mumkin. Shunday qilib, masalan, ma'lumotlarni solishtirish uchun xeshlashdan foydalanish mumkin: agar ikkita ma'lumotlar massivlarida turli xil xesh kodlari bo'lsa, massivlar boshqacha bo'lishi kafolatlanadi; agar ular bir xil bo'lsa, massivlar bir xil bo'lishi mumkin. Umumiy holda, asl ma'lumotlar va xesh-kod o'rtasida birma-bir yozishmalar mavjud emas, chunki xesh-funksiyalarning qiymatlari soni har doim kiritilgan ma'lumotlarning variantlari sonidan kamroq bo'ladi. Shuning uchun, bir xil xesh kodlarini beruvchi ko'plab kirish xabarlari mavjud (bunday holatlar deyiladi to'qnashuvlar). To'qnashuvlar ehtimoli hash funktsiyalarining sifatini baholashda muhim rol o'ynaydi.
Xesh funksiyalari zamonaviy kriptografiyada keng qo'llaniladi.
Eng oddiy xesh-funksiyani “sum modulo 2” amali yordamida quyidagicha qurish mumkin: biz kiritish qatorini olamiz, barcha bayt modulini qo‘shamiz va natija baytini xesh funksiyaning qiymati sifatida qaytaramiz. Bu holda xesh qiymatining uzunligi, kirish xabarining o'lchamidan qat'i nazar, 8 bit bo'ladi.
Misol uchun, asl raqamlashtirilgan xabar quyidagicha bo'ldi (o'n oltilik formatda):
Keling, xabarni ikkilik shaklga o'tkazamiz, baytlarni bir-birining ostiga yozamiz va har bir ustun moduliga bitlarni qo'shamiz 2:
0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101
Natijada (0110 0101 (2) yoki 65 (16)) xesh funktsiyasining qiymati bo'ladi.
Biroq, bunday xesh funktsiyasidan kriptografik maqsadlarda, masalan, elektron imzo yaratish uchun foydalanish mumkin emas, chunki nazorat summasini o'zgartirmasdan imzolangan xabarning mazmunini o'zgartirish juda oson.
Shuning uchun ko'rib chiqilayotgan xesh funktsiyasi kriptografik ilovalar uchun mos emas. Kriptografiyada xesh-funksiya, agar bir xil xesh qiymatiga ega bo'lgan ikkita oldingi tasvirni yaratish qiyin bo'lsa, shuningdek, funktsiyaning chiqishi kirishga aniq bog'liq bo'lmasa yaxshi hisoblanadi.
Kriptografik xesh-funksiyalar uchun asosiy talablarni shakllantiramiz:

• 
  xesh funksiyasi har qanday hajmdagi xabarlarga tegishli bo'lishi kerak;
  
• 
  funksiya qiymatini hisoblash yetarlicha tez bajarilishi kerak;
  
• 
  xesh-funktsiyaning ma'lum qiymati bilan M ning mos keladigan tasvirini topish qiyin (deyarli imkonsiz) bo'lishi kerak;
  
• 
  ma'lum bo'lgan M xabari bilan asl xabar bilan bir xil xesh qiymatiga ega bo'lgan boshqa M xabarini topish qiyin bo'lishi kerak;
  
• 
  bir xil xesh qiymatiga ega bo'lgan har qanday tasodifiy turli xabarlarni topish qiyin bo'lishi kerak.
  

Bu barcha talablarga javob beradigan xesh funksiyasini yaratish oson ish emas. Shuni ham yodda tutish kerakki, funktsiyani kiritishda ixtiyoriy o'lchamdagi ma'lumotlar olinadi va xesh natijasi har xil o'lchamdagi ma'lumotlar uchun bir xil bo'lmasligi kerak.
Hozirgi vaqtda amalda funksiyalar xesh-funksiyalar sifatida foydalaniladi, ular kirish xabar blokini blok bo'yicha qayta ishlaydi va shaklning bog'liqligiga ko'ra kirish xabarining har bir M i bloki uchun h i xesh qiymatini hisoblaydi.
h i = H (M i, h i-1),
bu erda h i-1 - oldingi kirish ma'lumotlar bloki uchun xesh funktsiyasini hisoblashda olingan natija.
Natijada, h n xesh funksiyasining chiqishi kirish xabarining barcha n ta blokining funksiyasi hisoblanadi.