|
3-kurs 961-19 guruh talabasi Reja: Hesh tushunchasi
|
| bet | 4/4 | | Sana | 22.05.2024 | | Hajmi | 329,56 Kb. | | #249844 |
Bog'liq Mustaqil ishi3- bosqich. Xesh qiymat uchun bufer initsializatsiya qilish.
Xesh funksiyaning oraliq va oxirgi natijalarini saqlash uchun 160 bitlik buferdan foydalaniladi. Bu buferni beshta 32 bitlik A, B, C, D, E registrlar ko‘rinishida tasvirlash mumkin. Bu registrlarga 16 lik sanoq sistemasida quyidagi boshlang‘ich qiymatlar beriladi:
A=0x67452301, B=0xEFCDAB89, C=0x98BADCFE, D=0x10325476, E=0xC3D2E1F0.
Keyinchalik bu o‘zgaruvchilar mos ravishda yangi a, b, c, d va e o‘zgaruvchilarga yozib olinadi. 4- bosqich. Ma’lumotni 512 bitlik bloklarga ajratib qayta ishlash.
Bu xesh funksiyaning asosiy sikli quyidagicha bo‘ladi: for (t = 0; t < 80; t++){ temp = (a <<< 5) + ft(b, c, d) + e + Wt + Kt ; e = d; d = c; c = b <<< 30; b = a; a = temp; }, Bu yerda <<< - chapga siklik surish amali. Kt lar 16 lik sanoq sistemasida yozilgan quyidagi sonlardan iborat:
ft(x, y, z) funksiyalar esa quyidagi ifodalar bilan aniqlanadi: Wt lar kengaytirilgan ma’lumotning 512 bitlik blokining 32 bitlik qism bloklaridan quyidagi qoida bo‘yicha hosil qilinadi:
Asosiy sikl tugagandan keyin a, b, c, d va e larning qiymatlari mos ravishda A, B, C, D va E registrlardagi qiymatlarga qo‘shiladi hamda shu registrlarga yozib qo‘yiladi va kengaytirilgan ma’lumotning keyingi 512 bitlik blokini qayta ishlashga o‘tiladi.
5- bosqich. Natija. Ma’lumotning xesh qiymati A, B, C, D va E registrlardagi qiymatlarni birlashtirish natijasida hosil qilinadi.
Xash funktsiyasi kalit turiga bog'liq. Qattiq gapirish, alohida xesh funktsiyasi alohida kalitni talab qiladi. Samaradorlik samaradorligini oshirish uchun, odatda, arifmetik hisob-kitoblarda ishlatilishi mumkin bo'lgan butunlar sifatida klavish so'zidagi tugmachalarni ko'rib chiqish g'oyasi sifatida turlarini aniq o'zgartirishdan qochish maqsadga muvofiqdir. Yuqori darajadagi tillardan oldin paydo bo'lgan, erta kompyuterlar uchun odatiy moddalar satr kaliti sifatida, keyin butun son sifatida ko'rib chiqilishi mumkin edi. Ba'zi yuqori darajadagi tillarda ma'lum bir kompyuterdagi tugmachalarni taqdim etishga bog'liq bo'lgan dasturlarni yaratish qiyin, chunki bunday dasturlar asosan mashinaga bog'liq, shuning uchun ular boshqa kompyuterga topshirish qiyin. Odatda, xesh funktsiyalari asosiy konversiya jarayoni sonlar ichiga bog'liq, shuning uchun bir vaqtning o'zida mashinada amalga oshirishda yordam va samaradorlikni ta'minlash qiyin. Qoida tariqasida, oddiy butun sonli kalitlar yoki suzuvchi nuqta tipidagi kalitlar faqat bitta mashinadan foydalanish orqali o'zgartirilishi mumkin, ammo struktura tugmachalari va boshqa turdagi kalitlar samaradorlikka yuqori xarajat va ko'proq e'tibor talab etiladi.
Ehtimol, eng oddiy vaziyat, kalitlar suzuvchi nuqta bilan belgilangan nuqtadan iborat. Masalan, agar tugmachalar raqamlar bo'lsa, katta 0 va kichik 1 bo'lsa, uni m bilan ko'paytirishi mumkin, natijani kichik bir songa ko'paytirish va 0 va 1 oralig'ida manzilni olish; Ushbu misol rasmda ko'rsatilgan. 14.1. Agar tugmachalar s dan kattaroq bo'lsa va ular tarqalishi, ularni ajratish va tslarni ajratish va natijada ular 0 dan 1 gacha bo'lgan qiymatlar oralig'iga tushib, keyin m vani ko'paytiradilar jadvaldagi manzili.
Suzuvchi nuqta bilan 0 va 1 oralig'ida, ularning o'lchami 97 ga ko'paytiriladi. Ushbu misolda uchta mojarolar sodir bo'ldi: 17, 53 va 76 ga teng bo'lgan ko'rsatkichlar uchun. Xash qadriyatlari oqsoqollar kalitlari tomonidan aniqlanadi, yosh zarralari hech qanday rol o'ynaydi. Hash funktsiyasini ishlab chiqish maqsadlaridan biri bu nomutanosiblikni yo'q qilish uchun bunday nomutanosiblikni yo'q qilishdir.
Agar tugmachalar W-bit butun son bo'lsa, ular suzuvchi nuqta raqamlariga aylantirilishi va oldingi paragrafda bo'lgani kabi, m i ga ko'paytiring. Agar suzuvchi nuqta operatsiyalari ko'p vaqtni egallab olsa, raqamlar shunchalik baland emas, natijada raqamlar shunchalik baland emas, natijada bir xil natijaga ko'ra, simni m uchun ko'paytirish kerak, so'ngra m uchun ko'payishingiz kerak 2 Vt (yoki ko'paytirish tufayli ko'payish, siljish va keyin ko'payishiga olib keladigan bo'lsa) 2 Vtni ajratish uchun o'chirish uchun o'ngda. Bunday usullar, agar kalitlar diapazon bilan bir xil tarzda taqsimlanmagan bo'lsa, hash qiymati faqat kalitning etakchi raqamlari bilan belgilanmaydi.
Ko'proq oddiy I. samarali usul W-bit butun sonlar uchun - ehtimol ko'p ishlatiladigan HOZID MARKAZIDA MIS-ning o'lchamidagi M, I, I.00 ga bo'linishni hisoblash. h (k) \u003d k mod m har qanday butun sonli k harfi uchun. Ushbu funktsiya modulli hash funktsiyasi deb ataladi. Hisoblash juda oson, va Kichik M qiymatdagi k ++ tilida), kichik m qiymatlar o'rtasidagi yagona qiymatlarni taqsimlashiga erishish samarali bo'ladi. 14.2.
Uchta o'ng ustunlarda chap tomonda ko'rsatilgan 7 bitli kalitlarning natijasi quyidagi funktsiyalardan foydalangan holda ko'rsatilgan:
v% 97 (chapda)
v% 100 (markaz) va
(int) (A * V)% 100 (o'ngda),
qaerda a \u003d .618033. Ushbu funktsiyalar uchun jadvalning o'lchamlari mos ravishda 97, 100 va 100 ni tashkil etadi. Tasodifiy ko'rinishga ega (tugmachalar tasodifiy). Ikkinchi funktsiya (v% 100) faqat ikkita tugmachani to'g'ri tugmachalardan foydalanadi va shuning uchun tasodifiy kalitlar uchun past ko'rsatkichlarni ko'rsatishi mumkin.
Modulli xalani suzuvchi nuqta kalitlariga qo'llaniladi. Agar tugmachalar kichik oralig'iga tegishli bo'lsa, ular 0 dan 1 gacha bo'lgan oralig'ida, 0 va 1-oralig'dan, 2-bitli butun sonlarni olish uchun raqamlarga ajratish mumkin va keyin modulli xash funktsiyasidan foydalaning. Boshqa variant - bu shunchaki modulli xesh funktsiyani ikkilik kalit taqdimotidan foydalanish (agar mavjud bo'lsa).
Moddiy narsalardan qat'i nazar, ular mashina so'zi bilan to'ldirilgan belgilar ketma-ketligi, yoki boshqa har qanday boshqa narsalar bilan to'ldirilgan belgilar ketma-ketligidan qat'iy nazar mumkin bo'lgan variant. Mashinasoz so'ziga qadoqlangan tasodifiy belgilarning ketma-ketligi tasodifiy butun sonli kalitlar bilan bir xil emas, chunki ularning hammasi kodlash uchun ishlatiladi. Ammo bu ikkala turning ikkala turini (va boshqacha kodlangan har qanday asosiy kodni) kichik stolda tasodifiy indekslarga o'xshab ko'rinishi mumkin.
Tanlovning o'lchamdagi m o'lchamidagi modulli hash stol sifatida, rasmda oddiy raqamning jadvali sifatida ko'rsatilgan. 14.3. Ushbu misolda 7 bit kodlash bilan ramziy ma'lumotlar, kalit 128 bazasi bo'lgan raqam sifatida tarjima qilinadi - kalitdagi har bir belgi uchun bitta raqamga ega. Endi so'z 1816567 raqamiga to'g'ri keladi, bu ham yozilishi mumkin
aSCII kod belgilari n, o va w raqamlarga mos keladi va 1568 \u003d 110, 1578 \u003d 1678 \u003d 119 raqamlariga mos keladi. Ushbu turdagi kalitning o'lchami muvaffaqiyatsiz bo'lsa, ishonchsiz bo'lsa, X qiymatlar, 64 (yoki 128) ga qo'shadi - har qanday kalit uchun xesh funktsiyasining qiymati Ushbu kalitning oxirgi 6 raqamining qiymati. Albatta, yaxshi xesh funktsiyasi barcha kalitni o'chirish, ayniqsa ramziy kalallar uchun hisobga olinishi kerak. Shunga o'xshash holatlar m va ko'p darajadagi ko'p darajani o'z ichiga olgan bo'lsa, shunga o'xshash holatlar paydo bo'lishi mumkin. Eng oddiy usul Buning oldini oling - m oddiy raqam sifatida tanlang.
Ushbu jadvalning har bir qatorida siz quyidagilar: 3 harfli so'z, ASCII kodida 34 va 31 (ikkitasi) o'lchamlari uchun 21 va 31-jadvallar mavjud. o'ngdagi haddan tashqari ustun). 64-jadvalning hajmi nomaqbul natijalarga olib keladi, chunki faqat xesh qiymatini olish uchun o'ngga va odatiy tilning so'zlari bilan harflar notekis taqsimlanmagan. Masalan, y harfi bilan ataladigan barcha so'zlar Hash 57-darajasiga mos keladi.
akiraning o'lchamlari oddiy raqam bo'lishi kerak, bundan tashqari, amalga oshirish juda oson. Ba'zi dasturlar uchun siz kichik bir taniqli oddiy raqamdan qoniqishingiz yoki jadvalning istalgan hajmiga yaqin bo'lgan taniqli bosh raqamlar ro'yxatidan qoniqishingiz mumkin. Masalan, raqamlar 2 T - 1, oddiy t \u003d 2, 3, 5, 7, 13, 17, 19 va 31 (va boshqa qadriyatlarda< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). И yagona sababjadvalning o'lchami oddiy raqamni berishga arziydi; Yana bir sabab 14.4 bo'limida ko'rib chiqiladi.
Xulosa
Bugungi jamiyat taraqqiyoti insoniyat tafakkurining maxsuli bo’lgan rivojlangan ilm-fan yutuqlariga asoslangan texnika va texnologiyalar bilan bir qatorda, keng ma’noda, axborotlarning muhim ahamiyatga egaligi orqali xam belgilanadi. Faoliyat maqsadlarining turlicha bo’lishi tabiiy ravishda axborotlardan turli maqsadlarda foydalanish asoslariga sabab bo’ladi. Shuning uchun bugungi, axborotlarni saqlash va uzatish tizimlari bir tomondan takomillashib murakkablashgan va ikkinchi tomondan axborotdan foydalanuvchilar uchun keng qulayliklar vujudga kelgan davrda, axborotlarni maqsadli boshqarishning qator muhim masalalari kelib chiqadi. Bunday masalalar qatoriga katta xajmdagi axborotlarning tez va sifatli uzatish xamda qabul qilish, axborotlarni ishonchliligini ta’minlash, axborotlar tizimida axborotlarni begona shaxslardan(keng ma’noda) muxofaza qilish kabi ko’plab boshqa masalalar kiradi. Yuqoridagi keltirilgan asosli muloxazalardan kelib chiqib, axborotlarni asli xolidan o’zgartirilgan xolda, ya’ni shifrlangan xolda, saqlash va uzatish masalalarining muhim ekanligiga shubxa yo’qdir.
+Xesh funksiyalar asosan ma’lumotning butunliligini ta’minlashda ya’ni axborot xavfsizligini ta’minlashda keng ko’lamda qo’llaniladi. Shuning uchun ham xesh funksiyalarning zamonaviy kriptografiya tutgan o’rni juda muhimdir.
|
| |
