Kriptografik xesh funksiyasi. Xesh nima va u nima uchun

10.2. MD5
MD5(Eng. Message Digest 5) 1991-yilda Massachusets Texnologiya Instituti (MIT) professori Ronald L. Rivest tomonidan ishlab chiqilgan 128-bitli xeshlash algoritmidir. Bu MD4 ning xavfsizligini kuchaytirilgan versiyasidir.
Quyida xeshni hisoblash algoritmi keltirilgan.
1. Oqimni tekislash.
Asl xabarning oxirida, uzunligi L, bitta bit qo'shing, so'ngra yangi o'lchamga ega bo'lishi uchun kerakli miqdordagi nol bit qo'shing L " 448 mod 512 (L 'mod 512 = 448) bilan solishtirish mumkin edi. Nol bitlarni qo'shish hatto yangi uzunlik, shu jumladan bir bit allaqachon 448 bilan solishtirish mumkin bo'lsa ham amalga oshiriladi.
2. Xabar uzunligini qo'shish.
O'zgartirilgan xabarga ma'lumotlar uzunligining 64 bitli ko'rinishi (xabardagi bitlar soni) qo'shiladi. Bular. xabar uzunligi T 512 ga karrali bo'ladi (T mod 512 = 0). Agar asl xabarning uzunligi 2 64 - 1 dan oshsa, u holda faqat eng kam ahamiyatli 64 bit qo'shiladi. Bunga qo'shimcha ravishda, belgilangan 64-bit uzunlikdagi tasvir uchun birinchi navbatda eng kam ahamiyatli 32 bit, keyin esa eng muhim 32 bit yoziladi.
3. Buferni ishga tushirish.
Hisob-kitoblar uchun 32 bitli 4 ta o'zgaruvchi ishga tushiriladi va boshlang'ich qiymatlar o'rnatiladi (on oltilik ko'rinish):
A = 67 45 23 01;
B= EF CD AB 89;
C= 98 BA DC FE;
D = 10 32 54 76.
Ushbu o'zgaruvchilar oraliq hisoblar natijalarini saqlaydi. Dastlabki holat A B C D ishga tushirish vektori deb ataladi.
4. Loopda xeshni hisoblash.
Asl xabar bloklarga bo'lingan T, 512 bit uzunligi. Loopdagi har bir blok uchun 10.2-rasmda ko'rsatilgan protsedura bajariladi. Asl xabarning barcha bloklarini o'zgaruvchilarning 32-bit qiymatlari birlashmasi sifatida qayta ishlash natijasi A B C D va xesh bo'ladi.

10.2-rasm. Xeshni hisoblash uchun asosiy tsikl bosqichi
Har bir turda o'zgaruvchilar ustida A B C D va manba matn bloki T halqada (16 ta takroriy) bir xil turdagi transformatsiyalar quyidagi sxema bo'yicha amalga oshiriladi.

10.3-rasm. Dumaloq halqaning bir iteratsiyasi
Shartli belgilar.
1) RF- quyidagi jadvalda belgilangan yumaloq funksiya.
10.1-jadval. Round RF funktsiyalari
2) t j- original xabar blokining j-th 32-bit qismi T katta endian;
3) k i formula bilan aniqlangan doimiyning butun qismidir
k i = 2 32 * | gunoh (i + 16 * (r - 1)) |, (10.1)
bu erda i - sikl iteratsiyasining soni (i = 1..16);
r - dumaloq raqam (r = 1..4).
Sin funktsiyasi argumenti radyanlarda o'lchanadi.
4) ⊞ - qo'shimcha mod 2 32.
5) <<< s i- s i raqamlari bilan chapga tsiklik siljish.
Asl xabar blokining 32-bitli qismi ishlatilgan t j va chapga tsiklik siljish miqdori s i iteratsiya soniga bog'liq va quyidagi jadvalda keltirilgan.
10.2-jadval. Dumaloq aylanish bosqichida ishlatiladigan qiymatlar

Takrorlash raqami		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1-tur	t j	t 1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10	t 11	t 12	t 13	t 14	t 15	t 16
	s i	7	12	17	22	7	12	17	22	7	12	17	22	7	12	17	22
2-tur	t j	t 2	t 7	t 12	t 1	t 6	t 11	t 16	t 5	t 10	t 15	t 4	t 9	t 14	t 3	t 8	t 13
	s i	5	9	14	20	5	9	14	20	5	9	14	20	5	9	14	20
3-tur	t j	t 6	t 9	t 12	t 15	t 2	t 5	t 8	t 11	t 14	t 1	t 4	t 7	t 10	t 13	t 16	t 3
	s i	4	11	16	23	4	11	16	23	4	11	16	23	4	11	16	23
4-tur	t j	t 1	t 8	t 15	t 6	t 13	t 4	t 11	t 2	t 9	t 16	t 7	t 14	t 5	t 12	t 3	t 10
	s i	6	10	15	21	6	10	15	21	6	10	15	21	6	10	15	21

4 turdan so'ng, har bir o'zgaruvchining yangi (o'zgartirilgan) qiymati A B C D original bilan (⊞) qo'shiladi (1-turdan oldingi o'zgaruvchining qiymati).
5. ABCD o'zgaruvchilarda baytlarni almashtirish... Asl xabarning barcha bloklari qayta ishlangandan so'ng, har bir o'zgaruvchi uchun teskari bayt almashinuvi amalga oshiriladi.
To'qnashuvlarni qidiring.
2004-yilda xitoylik tadqiqotchilar Van Xiaoyun, Feng Dengguo, Lai Xuejia va Yu Hongbo qisqa vaqt ichida (IBM p690 klasterida 1 soat) toʻqnashuvlarni topishga imkon beruvchi algoritmda zaiflikni aniqlaganliklarini eʼlon qilishdi.
10.3. Xesh tasvirini olish uchun shifrlashdan foydalanish
To'qnashuvga chidamli xesh tasvirni yaratish uchun blokli shifrlarda (masalan, y shifr bloklarini birlashtirish) yoki xesh funktsiyasining o'zida, komponent qismi sifatida blokli shifrlash rejimlaridan biri taqdim etilgan maxsus rejimlardan foydalanish mumkin. ishlatilishi mumkin (masalan, GOST 34.11-94 1 ga muvofiq komponent hash -funktsiyasi 2 ga muvofiq kriptografik o'zgartirish algoritmini oddiy almashtirish rejimi).
Eslatib o'tamiz, agar xesh funktsiyasining qiymati nafaqat oldingi rasmga, balki shaxsiy kalitga ham bog'liq bo'lsa, u holda xesh tasviri Xabar autentifikatsiya kodi (MAC), ma'lumotlarni autentifikatsiya kodi (DAC) yoki taqlid kiritma.
Misol tariqasida rejimni olaylik (Cipher Block Chaining).

10.4-rasm. Shifr bloklarini birlashtirish rejimida DES algoritm diagrammasi
Oxirgi shifrlangan blok C n va xabarning xesh tasviri mavjud T = (T 1, T 2, ..., T n).
1 GOST 34.11-94 “Axborot texnologiyalari. Kriptografik ma'lumotlarni himoya qilish. Xesh funktsiyasi ".
2 GOST 28147-89 “Axborotni qayta ishlash tizimlari. Kriptografik himoya. Kriptografik o'zgartirish algoritmi ".
O'z-o'zini tekshirish uchun savollar
1. Tushunchalarga ta’rif bering: “”, “”, “”.
Biz ko'rib chiqqan qidiruv algoritmlari odatda mavhum taqqoslash operatsiyasiga asoslanadi. Ushbu turkumdan "Tanzimalar jadvallari va ikkilik qidiruv daraxtlari" da tavsiflangan tarqatish qidirish usuli ajralib turadi, bunda i kaliti bo'lgan element jadvalning i-pog'onasida saqlanadi, bu unga to'g'ridan-to'g'ri kirish imkonini beradi. Qidiruvni tarqatishda taqqoslash operatsiyasining operandlari emas, balki massiv indekslari sifatida kalitlarning qiymatlaridan foydalaniladi; Usulning o'zi kalitlarning jadval indekslari bilan bir xil diapazondagi alohida butun sonlar ekanligiga tayanadi. Ushbu bobda biz kalitlar bunday qulay xususiyatlarga ega bo'lmagan odatiy qidiruv ilovalarida qo'llaniladigan kengaytirilgan tarqatuvchi qidiruvni ko'rib chiqamiz. Ushbu yondashuvning yakuniy natijasi taqqoslashga asoslangan usullardan butunlay farq qiladi - qidiruv tugmachalarini elementlardagi kalitlar bilan taqqoslash orqali lug'at ma'lumotlar tuzilmalari bo'ylab harakatlanish o'rniga, biz arifmetik konvertatsiya qilish orqali jadvaldagi elementlarga to'g'ridan-to'g'ri kirishga harakat qilamiz. jadval manzillari kalitlari.
Xashing qidiruv algoritmlari ikkita alohida qismga ega. Birinchi qadam qidirish kalitini jadvaldagi manzilga aylantiruvchi xesh funksiyasini hisoblashdir. Ideal holda, turli xil kalitlar turli manzillarga mos keladi, lekin ko'pincha ikki yoki undan ortiq turli xil kalitlar jadvalda bir xil manzilni berishi mumkin. Shuning uchun, xeshlash qidiruvining ikkinchi qismi to'qnashuvni hal qilish jarayoni bo'lib, bunday kalitlarni boshqaradi. Ushbu bobda biz ko'rib chiqadigan mojarolarni hal qilish usullaridan biri bog'langan ro'yxatlardan foydalanadi, shuning uchun u qidiruv kalitlari sonini oldindan taxmin qilish qiyin bo'lgan dinamik vaziyatlarda to'g'ridan-to'g'ri foydalanishni topadi. Boshqa ikkita to'qnashuvni hal qilish usullari yuqori darajaga erishadi ishlash elementlar belgilangan massivda saqlanganligi sababli qidirish. Biz ushbu usullarni qanday qilib yaxshilash mumkinligini ko'rib chiqamiz, ular hatto jadval o'lchamini oldindan aytib bo'lmaydigan holatlarda ham qo'llanilishi mumkin.
Hashing vaqt va xotira o'rtasidagi muvozanatning yaxshi namunasidir. Agar foydalaniladigan xotira miqdori bo'yicha hech qanday cheklovlar bo'lmasa, har qanday qidiruvni faqat bitta xotiraga kirish orqali amalga oshirish mumkin edi, shunchaki kalitni xotira manzili sifatida, ajratuvchi qidiruvda bo'lgani kabi. Biroq, bu ideal holat odatda erishib bo'lmaydi, chunki uzun tugmalar katta hajmdagi xotirani talab qilishi mumkin. Boshqa tomondan, agar hech qanday cheklovlar bo'lmasa Yangi mahsulotni o'zlashtirib olishga ketadigan vaqt, ketma-ket qidiruv usuli yordamida minimal xotira miqdori bilan ishlash mumkin. Xeshlash - bu xotira va vaqtning maqbul miqdoridan foydalanish va bu ikki ekstremal o'rtasidagi muvozanatni saqlash usuli. Xususan, kodni qayta yozish yoki boshqa algoritmlarni tanlash o‘rniga, oddiygina jadval hajmini o‘zgartirish orqali har qanday muvozanatni saqlash mumkin.
Xeshlash informatikaning klassik muammolaridan biridir: uning turli algoritmlari batafsil o'rganilgan va keng qo'llaniladi. Ko'ramizki, bo'sh taxminlar bilan, jadval o'lchamidan qat'i nazar, doimiy vaqtda belgilar jadvallarida topish va kiritish operatsiyalarini qo'llab-quvvatlashga umid qilish mumkin.
Ushbu kutilgan qiymat har qanday ramz jadvalini amalga oshirish uchun optimal nazariy ishlashdir, ammo ikkita asosiy sababga ko'ra xeshlash hali ham davo emas. Birinchidan, Yangi mahsulotni o'zlashtirib olishga ketadigan vaqt kalit uzunligiga bog'liq bo'lib, bu uzoq tugmalar yordamida haqiqiy ilovalarda muhim bo'lishi mumkin. Ikkinchidan, xeshlash tanlash yoki saralash kabi boshqa belgilar jadvali operatsiyalarini samarali amalga oshirishni ta'minlamaydi. Ushbu bobda biz ushbu va boshqa masalalarni batafsil ko'rib chiqamiz.