|
X argument istalgan uzunlikdagi bitlar qatori bo’lishi mumkin;
H(x)
|
| bet | 66/217 | | Sana | 15.05.2024 | | Hajmi | 2,85 Mb. | | #236153 |
Bog'liq Raqamli iqtisodiyot-Darslik-18.02.2020X argument istalgan uzunlikdagi bitlar qatori bo’lishi mumkin;
H(x) funktsiyaning qiymati aniq uzunlikka ega bo’lgan bitlar qatori bo’lishi lozim;
H(x) funktsiyaning qiymatini hisoblash oson bo’lishi kerak;
Har qanday aniq x uchun hisob-kitoblar vositasida H(x*) = H(x) bo’ladigan x*! = x qiymatini topish mumkin bo’lmasin. H(x*) = H(x) xolatidagi x*! = xjuftligi xesh-funktsiyaning kolliziyasi deb ataladi.
Kuchli xesh-funktsuya deb,kuchsiz funktsiya uchun yuqoridagi 1-3 shartlarni va quyidagi 5-shartni bajaradigan bir tomonlama H(x) funktsiyaga aytiladi:
H(x*) = H(x) bo’ladigan har qanday x*! = x qiymatini hech qanday hisob-kitoblar yordamida topish mumkin bo’lmaydi.
Har qanday simvollar ketma-ketligi kabi, elektron raqamli imzoni hisoblashning formulasini matematik ko’rinishda quyidagicha tasvirlash mumkin:
S = F (h(M), Ks)
Bu yerda M – ma’lumot matni, Ks – mahfiy kalit, h(M) – xeshlashtirish funktsiyasi.
Yuqorida keltirilgan ifodaga ko’ra, elektron raqamli imzoni xosil qilish uchun boshlang’ich xomashyo sifatida ma’lumotning o’zi emas, balki uning xeshi olinadi (ya’ni, ma’lumotning xesh-funktsiya yordamida xosil bo’lgan natijasidan foydalaniladi). Chunki imzo bilan tasdiqlanuvchi matn kattaligi noldan to bir necha megabaytgacha bo’lishi mumkin. Ayniqsa mu matn grafik elementlarga ega bo’lsa, yanada kattalashib ketishi mumkin. Ammo amaliyotda qo’llaniladigan barcha xeshlashtirish algoritmlari hisob-kitoblar
uchun matnning oldindan belgilangan standart uzunlikda bo’lishini talab qiladi. Masalan, Rossiyada ishlatiladigan ЭЦПГОСТР 34.10-94 algoritmida bu standart uzunlik 32 baytga teng bo’lishi talab qilinadi. Demak, xesh- funktsiya algoritmining hal qilishi kerak bo’lgan asosiy masala - istalgan uzunlikdagi va hajmdagi ma’lumotdan kerakli uzunlikdagi (masalan, 32 baytli) sonlar ketma-ketligini hosil qilishdir. Bunday talablarga javob beradigan xesh-funktsiya algoritmini yaratish unchalik qiyin ish emas, ammo bu funktsiya bir qancha talablarga javob berishi kerak. Eng avvalo, xesh- funktsiya yordamida olingan natija boshlang’ich ma’lumotga birga-bir mos kelsin va bu natija boshlangi’ch ma’lumotning har qanday o’zgarishida ham unga yana birga-bir mos kelsin. Undan tashqari, xesh-funktsiya shunday hisoblanilishi kerakki, har qanday M ma’lumot uchun h(M) =h(M*) bo’lgan M* ma’lumotni tanlab olish yoki topish mumkin bo’lmasin. Boshqacha so’zlar bilan aytganda, h(M) =h(M*) shartni qanoatlantiruvchu M ma’lumot va uning xesh-funktsiyasi ma’lum bo’lganida, M* ma’lumotni muvaffaqiyatli hisoblashga ketadigan mehnat sarfi ma’lumotlarni to’g’ridan-to’gri saralash uchun zarur bo’lgan mehnat sarfiga ekvivalent bo’lishi kerak. Bu shartning bajarilmasligi potentsial firibgarga imzoni o’zgartimasdan turib, ma’lumotlarni almashtirib qo’yish imkoniyatini yaratishi mumkin. Boshqa tomondan qaraganda, ko’pchilik ma’lumotlar uchun xesh-funktsiyalar bir xil bo’lishi mumkin, chunki mumkin bo’lgan ma’lumotlar to’plami xesh- funktsiyalarning mumkin bo’lgan to’plami sonidan ancha ko’p miqdorda bo’ladi. Ya’ni, ma’lumotlar soni cheksiz miqdorda bo’lib, xesh-funktsiyalar soni esa 2*N gateng bo’ladi, bu yerda N – xesh funktsiyaning bitlardagi uzunligi. Xozirgi paytda eng keng tarqalgan xesh-funktsiyalar algoritmlari sifatida quyidagilarni ko’rsatishimiz mumkin:
Rossiyada qo’llaniladigan standart ГОСТЗ 34.11-94 xesh-kattalikni 32 bayt kattalikda hisoblaydi.
|
| |
