Xech funktsiyasini hisoblash kriptografik xech-funksiyalar nega sizga xesh kerak?

KRIPTOGRAFIK XECH-FUNKSIYALAR
REJA:

1. 
   XECH FUNKTSIYASINI HISOBLASH
   
2. 
   KRIPTOGRAFIK XECH-FUNKSIYALAR
   
3. 
   NEGA SIZGA XESH KERAK?
   

Ikki n dan kam tub sonlarning jadvali, stolning o'lchami bosh bo'lishi uchun zarur bo'lganda, hash stolni dinamik ravishda tarqatish uchun ishlatilishi mumkin. Berilgan diapazondagi har qanday ijobiy qiymat uchun ushbu jadvaldan undan 2 martaga kam farq qiluvchi ko'payishni aniqlash uchun foydalanish mumkin.

Butun sonli tugmachalarni qayta ishlashning yana bir varianti multiplikativ va modulli usullarni birlashtirishdir: siz kalitni 0 va 1 oralig'idagi doimiyga ko'paytirishingiz kerak, keyin M. bo'linish modulini bajaring. Boshqacha aytganda, siz funktsiyadan foydalanishingiz kerak. Nazariy jihatdan g'ayritabiiy xatti-harakatlarga olib kelishi mumkin bo'lgan qadriyatlar, M va kalitlarni raqamlash tizimining samarali bazasi o'rtasida bog'liqlik mavjud, ammo agar siz a-ning ixtiyoriy qiymatidan foydalansangiz, haqiqiy dasturda har qanday muammo bo'lmaydi. Ko'pincha f \u003d 0.618033 ... (oltin nisbat) ning qiymati a sifatida tanlanadi.
Ushbu mavzudagi boshqa ko'plab o'zgarishlar o'rganildi, xususan, siljitish va niqobni tanlash kabi samarali mashina ko'rsatmalaridan foydalanib bajarilishi mumkin bo'lgan hash funktsiyalari (bog'lanishlar bo'limiga qarang).
Belgilar jadvalidan foydalanadigan ko'plab dasturlarda kalitlar raqam emas va ular qisqa bo'lishi shart emas; tez-tez bu juda uzun bo'lishi mumkin bo'lgan alfanumerik raqamlardir. Averylongkey kabi so'z uchun hash funktsiyasini qanday hisoblash mumkin?
7 bitli ASCII kodida bu so'z 84 bitli raqamga to'g'ri keladi \\ boshlash (tekislang *) 97 \\ cdot 128 ^ (11) va + 118 \\ cdot 128 ^ (10) + 101 \\ cdot 128 ^ (9) + 114 \\ ^ (3) \\\\ & + 107 \\ cdot 128 ^ (2) + 101 \\ cdot 128 ^ (1) + 121 \\ cdot 128 ^ (0), \\ end (tekislang *),
ko'pgina kompyuterlar bilan odatiy arifmetik funktsiyalarni bajarish uchun juda katta. Va ko'pincha siz uzoqroq tugmachalarni qayta ishlashingiz kerak.
Uzoq tugmachalar uchun modulli hash funktsiyasini hisoblash uchun ular qismlarga bo'laklarga aylantiriladi. Modul funktsiyasining arifmetik xususiyatlaridan foydalanishingiz va Horner algoritmidan foydalanishingiz mumkin (4.9 "Mavhum ma'lumot turlari" bo'limiga qarang). Ushbu usul tugmachalarga mos keladigan raqamlarni yozishning boshqa usuliga asoslangan. Ko'rib chiqilayotgan misol uchun biz quyidagi ifodani yozamiz: \\ boshlamoq (tekislang *) (((((((((((((((97) cdot 128 ^ (11)) 128) (+) 118) \\ cdot 128 ^ (10) + 101)) 9) + 114) \\ cdot 128 ^ (8) + 121) \\ cdot 128 ^ (7) \\\\ & + 108) \\ cdot 128 ^ (6) + 111) \\ cdot 128 ^ (5) + 110) \\ cdot 128 ^ (4) + 103) \\ cdot 128 ^ (3) \\\\ & + 107) \\ cdot 128 ^ (2) + 101) \\ cdot 128 ^ (1) + 121. \\ end (tekislang *)
Ya'ni, satrni belgilar kodlashiga mos keladigan o'nlik raqamni chapdan o'ngga qarab ko'rib chiqishda, to'plangan qiymatni 128 ga ko'paytirganda va keyingi belgining kod qiymatini qo'shganda hisoblash mumkin. Uzun simli holatda bu hisoblash usuli oxir-oqibat umuman kompyuterda namoyish etilishi mumkin bo'lganidan kattaroq songa olib keladi. Ammo bu raqam kerak emas, chunki uning M.ga bo'linishidan faqat kichik (kichik) qismi talab qilinadi.Natijani katta to'plangan qiymatni saqlamasdan olish mumkin, chunki hisoblash paytida istalgan vaqtda, siz M ga ko'paygan sonni tashlab yuborishingiz mumkin - har safar ko'paytirsangiz va qo'shsangiz, siz M. bo'linish modulining faqat qolgan qismini saqlashingiz kerak bo'ladi, natijada biz uzoq raqamni hisoblash va keyin bo'linishni amalga oshirish imkoniga ega bo'lgandek bo'lamiz (qarang). mashq 14.10). Ushbu kuzatish uzun simlar uchun modulli xesh funktsiyalarini hisoblash uchun to'g'ridan-to'g'ri arifmetik usulga olib keladi - 14.1 dasturiga qarang. Ushbu dasturda yana bitta, oxirgi hiyla qo'llaniladi: baza 128 o'rniga, u 127 raqamini ishlatadi. Ushbu o'zgarish sababi keyingi paragrafda muhokama qilinadi.
Horner (Horner) usuli yordamida modulli xeshlash bilan bir xil narxda xesh funktsiyalarini hisoblashning ko'p usullari mavjud (har bir belgi uchun bitta yoki ikkita arifmetik amallar). Tasodifiy kalitlar uchun ushbu usullar deyarli bir-biridan farq qilmaydi, ammo haqiqiy kalitlar kamdan-kam hollarda tasodifiydir. Kichkina narxga haqiqiy kalitlarni tasodifiy ko'rish qobiliyati tasodifiy xeshlash algoritmlarini ko'rib chiqishga olib keladi, chunki biz kalitlarning taqsimlanishidan qat'i nazar, tasodifiy jadval indekslarini yaratadigan hash funktsiyalariga muhtojmiz. Tasodifiylashtirishni tashkil qilish qiyin emas, chunki modulli hashing ta'rifiga so'zma-so'z rioya qilish shart emas - faqat M dan kichik bo'lmagan butun sonni hisoblashda kalitning barcha raqamlari ishlatilishi kerak.
M \u003d 96 va a \u003d 128 (yuqorida),
M \u003d 97 va a \u003d 128 (markazda) va
M \u003d 96 va a \u003d 127 (pastki)
Birinchi holda notekis taqsimlash bu harflarning notekis ishlatilishi va jadvalning kattaligi ham, omil ham 32 ga ko'payganligi sababli notekislikni saqlashning natijasidir. Boshqa ikkita misol tasodifiy ko'rinadi, chunki stol kattaligi va omil - bu nusxa raqamlari.
14.1-dastur buni amalga oshirishning bitta usulini ko'rsatadi: 2-quvvat o'rniga oddiy bazadan va ASCII-ning mag'lubiyatiga mos keladigan butun sondan foydalanish. Shaklda 14.5 rasm. 14.5-rasmda ushbu o'zgarish odatiy simli tugmalar uchun taqsimlashni qanday yaxshilaganligi ko'rsatilgan. Nazariy jihatdan, 14.1 dasturi tomonidan yaratilgan xash qiymatlari jadval jadvallari uchun 127 ga teng bo'lgan yomon natijalar berishi mumkin (garchi amalda bu deyarli ko'rinmas bo'lishi mumkin); Tasodifiy algoritmni yaratish uchun multiplikatorning qiymatini tasodifiy tanlash mumkin. Keyinchalik samaraliroq usul - bu hisoblashda koeffitsientlarning tasodifiy qiymatlari va kalitning har bir raqami uchun turli xil tasodifiy qiymatlardan foydalanish. Ushbu yondashuv universal hashing deb nomlangan tasodifiy algoritmni taqdim etadi.
Nazariy jihatdan ideal universal hash funktsiyasi - bu M o'lchamidagi jadvalda ikkita turli xil kalitlarning to'qnashuvi ehtimoli to'liq 1 / M bo'lgan funktsiya. 14.1 dasturida a koeffitsienti sifatida foydalanish qat'iy belgilangan qiymat emas, balki tasodifiy turli xil qiymatlar ketma-ketligi modulli xeshni universal xesh funktsiyasiga o'zgartirishi isbotlanishi mumkin. Biroq, kalitdagi har bir belgi uchun yangi tasodifiy raqamni yaratish qiymati odatda qabul qilinishi mumkin emas. Amalda, 14.1 dasturida ko'rsatilgan murosaga har bir kalit belgisi uchun turli xil tasodifiy raqamlar qatorini saqlash bilan emas, balki oddiy soxta tasodifiy tartib yaratish orqali koeffitsientlarni o'zgartirish orqali erishish mumkin.
Xulosa qilish uchun: mavhum belgilar jadvalini amalga oshirish uchun xeshdan foydalanish uchun avval siz M-jadval jadvalidan kichikroq manfiy bo'lmagan butun sonlarga kalitlarni joylashtiradigan xesh-operatsiyani kiritish uchun mavhum tipli interfeysni kengaytirish kerak.
Ushbu maqolaning bir qismi sifatida sizga aytaman xesh nimanima uchun kerak, qaerda va qanday ishlatilganligi, shuningdek, eng mashhur misollar.
Axborot texnologiyalari sohasidagi ko'plab vazifalar ma'lumotlar hajmi uchun juda muhimdir. Masalan, agar siz har biringiz uchun 1 KB hajmdagi ikkita faylni va bir-biringizdan 10 GB hajmdagi ikkita faylni taqqoslashingiz kerak bo'lsa, unda bu mutlaqo boshqa vaqt. Shu sababli, qisqa va sig'imli qiymatlar bilan ishlashga imkon beradigan algoritmlar juda mashhur deb hisoblanadi.
Ushbu texnologiyalardan biri ko'p muammolarni hal qilishda o'zining amaliy dasturini topgan Hashing. Ammo, menimcha, oddiy foydalanuvchi sifatida u qanday hayvon ekanligi va u nimaga tegishli ekanligi hali ham aniq emas. Shuning uchun, bundan keyin hammasini sodda so'zlar bilan tushuntirishga harakat qilaman.
Izoh: Material oddiy foydalanuvchilar uchun mo'ljallangan va ko'pgina texnik jihatlarni o'z ichiga olmaydi, ammo asosiy tanishish uchun bu etarli emas.
Xesh yoki xesh nima?
Shartlardan boshlayman.

Hash funktsiyasi, konvolyutsiya funktsiyasi - Bu o'zboshimchalik bilan yozilgan matnlarni sobit uzunlikdagi kodlarga (odatda qisqa alfasayısal yozuvga) aylantirish imkonini beradigan funktsiyaning maxsus turi.

Hashing - Bu dastlabki kodni konvertatsiya qilish jarayoni.
Xesh, xash kodi, xashning qiymati, xash miqdori bu Hash funktsiyasining chiqish qiymati, ya'ni natijada olingan blok sobit uzunlikdir.
Ko'rib turganingizdek, atamalar biroz majoziy tavsifga ega, ulardan bularning barchasi nima uchun zarurligini tushunish qiyin. Shuning uchun men darhol kichik bir misol keltiraman (biroz keyinroq boshqa dasturlar haqida gaplashaman). Aytaylik, sizda 10 Gb hajmdagi 2 ta fayl mavjud. Qaysi biri to'g'ri ekanligini tezda qanday aniqlashim mumkin? Siz fayl nomidan foydalanishingiz mumkin, ammo uning nomini o'zgartirish juda oson. Siz sanalarni ko'rishingiz mumkin, lekin fayllarni nusxalashgandan so'ng, sanalar bir xil yoki boshqa ketma-ketlikda bo'lishi mumkin. O'zingiz bilganingizdek, o'lcham ozgina yordam berishi mumkin (ayniqsa, o'lchamlar mos bo'lsa yoki baytlarning aniq qiymatlariga qaramagan bo'lsangiz).
Bu Hash kerak bo'lgan joy, bu faylning boshlang'ich matnidan hosil bo'lgan qisqa blok. Ushbu ikkita 10GB fayllar ikki xil, ammo qisqa Hash kodlariga ega ("ACCAC43535" va "BBB3232A42" kabi). Ulardan foydalanib, nomlarni nusxalash va o'zgartirishdan keyin ham kerakli faylni tezda topishingiz mumkin.
Izoh: Kompyuter dunyosida va Internetda Hash juda mashhur tushuncha bo'lganligi sababli, ko'pincha Hash bilan bog'liq bo'lgan barcha narsalar shu so'z bilan qisqartiriladi. Masalan, tarjimada "Men MD5 xashidan foydalanaman" iborasi MD5 standartidagi xesh algoritmi saytda yoki boshqa joyda ishlatilishini anglatadi.
Hash funktsiyasining xususiyatlari

Endi men Hash funktsiyalarining xususiyatlari haqida gaplashaman, shunda u qayerda ishlatilishini va Hashing nima uchun ekanligini tushunishingiz osonroq bo'ladi. Ammo birinchi navbatda, boshqa ta'rif.

To'qnashuv - bu ikki xil matn uchun bir xil Hash summasi olingan vaziyat. Siz tushunganingizdek, blok qat'iy uzunlikka ega bo'lgani sababli, u cheklangan miqdordagi qiymatlarga ega va shuning uchun takrorlash mumkin.
Va endi Hash funktsiyalarining xususiyatlariga:
1. Har qanday o'lchamdagi matnni kirishga boqish mumkin va chiqishda ma'lum bir uzunlikdagi ma'lumotlar bloki olinadi. Bu ta'rifdan kelib chiqadi.
2. Xuddi shu matnlarning hash summasi bir xil bo'lishi kerak. Aks holda, bunday funktsiyalar shunchaki foydasiz - bu tasodifiy raqamga o'xshash.
3. Yaxshi yig'ish funktsiyasi yaxshi taqsimotga ega bo'lishi kerak. Agar chiqadigan Hash hajmi, masalan, 16 bayt bo'lsa, agar funktsiya har qanday matnlar uchun atigi 3 xil qiymatni qaytarsa, unda bunday funktsiyaning ma'nosi yo'q va bu 16 bayt (16 bayt 2 ^ 128 parametr bo'lib, bu taxminan 3 ga teng). 4 * 10 ^ 38 daraja).
4. Funksiya dastlabki matndagi ozgina o'zgarishlarga qanchalik yaxshi javob beradi. Oddiy misol. 10 GB hajmdagi faylda 1 harfni o'zgartirdik, funktsiyaning qiymati boshqacha bo'lishi kerak. Agar bunday bo'lmasa, unda bunday funktsiyani qo'llash juda muammoli.
5. To'qnashuv ehtimoli. Muayyan sharoitlarda hisoblangan juda murakkab parametr. Ammo, uning mohiyati shundan iboratki, agar hosil bo'lgan Hash miqdori ko'pincha mos kelsa, Hash funktsiyasining ma'nosi nima.
6. Hashni hisoblash tezligi. Agar hisoblash uchun ko'p vaqt kerak bo'lsa, yig'ilish funktsiyasidan foydalanish nima? Yo'q, chunki fayl ma'lumotlarini taqqoslash yoki boshqa yondashuvdan foydalanish osonroq bo'ladi.

7. Hash qiymatidan dastlabki ma'lumotlarni tiklash qiyinligi. Ushbu belgi umumiyga qaraganda o'ziga xosdir, chunki bu har doim ham talab qilinmaydi. Biroq, eng taniqli algoritmlar uchun bu xususiyat baholanadi. Masalan, dastlabki faylni bu funktsiyadan zo'rg'a olasiz. Ammo, agar to'qnashuv muammosi bo'lsa (masalan, siz bunday Hashga mos keladigan har qanday matnni topishingiz kerak), unda bu belgi muhim bo'lishi mumkin. Masalan, parollar, lekin ular haqida biroz keyinroq.

8. Bunday funktsiyaning dastlabki kodi ochiq yoki yopiq. Agar kod ochiq bo'lmasa, ma'lumotlarni qayta tiklashning murakkabligi, xususan kriptografik quvvat savol tug'iladi. Qisman, bu shifrlash bilan bog'liq muammo.
Endi biz "bularning barchasi nima uchun?" Degan savolga o'tamiz.