4-Ma’ruza Mavzu: El-Gamal ochiq kalitli shifrlash algoritmi Reja

_4-Ma’ruza
Mavzu: El-Gamal ochiq kalitli shifrlash algoritmi
Reja

1. 
   Diskret logarifmlash muammosi va ularni hisoblash usullari;
   
2. 
   Pohlig-Xelman algoritmi;
   
3. 
   Baby-Step/Giant-Step algoritmi;
   

Bir tomonlama funksiyalar
Ochiq kalitli kriptotizimlar bir tomonlama akslantirishlarga (funksiyalarga) asoslanadi.
Nosimmetrik kriptotizimlarning matematik asosini katta tartibli chekli to‘plamlarda berilgan chekli maydon, halqa, gruppa, qismgruppa ko‘rinishidagi algebraik strukturalar va shaxsiy maxfiylikga ega bo‘lgan uch turdagi bir tomonlama funksiyalar tashkil etadi. Nosimmetrik kriptotizimlarning turli hujumlarga bardoshliligi esa bir tomonlama funksiyalarning teskarilanishi o‘ta murakkab muammo (masala) bo‘lishiga asoslanadi.
Bir tomonlama funksiyalar birinchi turining hujumlarga bardoshliligi diskret logarifmlash masalasining murakkabligiga asoslangan. Bu funksiya U. Diffi va M. Xellman taklif etgan tub maydon F(p) hosil qiluvchi (generator, boshlang‘ich ildiz) element a ni maxfiy x darajaga oshirish funksiyasidir.
Bir tomonlama funksiyalarning ikkinchi turi K. Koks, R. Rayvest, A. Shamir, L. Adleman tomonidan taklif etilgan bo‘lib, uning hujumlarga bardoshliligi chekli halqada faktorlash muammosining murakkabligiga asoslangan.
Bir tomonlama funksiyalarning uchinchi turining hujumlarga bardoshliligi EECh nuqtalari gruppasida diskret logarifmlash masalasining murakkabligiga asoslangan. Bu funksiya N. Koblits va V. Miller taklif etgan hosil qiluvchi (generator, boshlang‘ich ildiz) element G ni maxfiy d butun songa ko‘paytirish funksiyasidir.
Bir tomonlama funksiya – shunday funksiyaki, uning aniqlanish sohasidan bo‘lgan ixtiyoriy uchun qiymat oson hisoblanadi, qiymatlar sohasining barcha qiymatlariga mos keluvchi qiymatlarni hisoblash esa amaliy jihatdan murakkab bo‘lgan masala (muammo)ni yechishni talab etadi.
Ko‘rinib turibdiki, bir tomonlama funksiyaning bunday ta’rifi «oson hisoblanadigan», «barcha qiymatlar uchun», «amaliy jihatdan», «murakkab bo‘lgan masalani yechishni talab etadi» iboralar asosida berilib, matematika nuqtai nazaridan aniq emas. Shunday bo‘lsada, bu ta’rif amaliy kriptotizim masalalari nuqtai nazaridan yetarli darajada aniq bo‘lib, alohida olingan kriptotizimlar uchun takomillashtirilib, mutlaqo aniq ifodalanishi mumkin. Shunday funksiyalardan kriptografiyada qanday foydalanilishi haqida qisqacha to‘xtalamiz. Yashirin yoki maxfiy uslubli bir tomonlama funksiya, ta’rif bo‘yicha biror parametrlarga bog‘liq bo‘lib, teskarisiga ega bo‘lgan shunday funksiyalar sinfiki, berilgan parametrda aniqlanish sohasidagi barcha argumentlar uchun qiymatlarni oson hisoblash algoritmi mavjud bo‘lib, qiymatlar sohasidagi barcha qiymatlar uchun qiymatlarni ma’lum bo‘lgan algoritm bilan hisoblashning imkoniyati yo‘q (yoki boshqacha aytganda qiymatlarni hisoblash sarf-xarajatlari va vaqti maqsadga muvofiq emas). Bunday ta’rif matematika nuqtai nazaridan aniq bo‘lmasada, amaliy kriptologiya masalalarida samarali qo‘llanilishi mumkinligiga shak-shubha yo‘q.
Ochiq kalitli kriptotizimlar algoritmlari ularning asosini tashkil etuvchi bir tomonlama funksiyalar bilan farqlanadi. Har qanday bir tomonlama funksiya ham ochiq kalitli kriptotizimlar yaratish uchun va ulardan amaldagi axborotlar tizimida maxfiy aloqa xizmatini o‘rnatish algoritmini qurish uchun qulaylik tug‘dirmaydi.
Bir tomonlama funksiyalarning aniqlanish ta’rifida nazariy jihatdan teskarisi mavjud bo‘lmagan funksiyalar emas, balki berilgan funksiyaga teskari bo‘lgan funksiyaning qiymatlarini hisoblash amaliy jihatdan maqsadga muvofiq bo‘lmagan funksiyalar tushunilishi ta’kidlangan edi. Shuning uchun, ma’lumotning ishonchli muhofazasini ta’minlovchi ochiq kalitli kriptotizimlarga quyidagi muhim talablar qo‘yiladi:
1. Dastlabki (ochiq) ma’lumotni shifrmatn ko‘rinishiga o‘tkazish bir tomonlama jarayon va shifrlash kaliti bilan shifrmatn ochish – deshifrlash mumkin emas, ya’ni shifrlash kalitini bilish shifrmatn deshifrlash uchun yetarli emas.
2. Ochiq kalitning ma’lumligiga asoslanib, maxfiy kalitni zamonaviy fan va texnika yutuqlari yordamida aniqlash uchun zarur bo‘ladigan sarf-xarajatlar hamda vaqt maqsadga muvofiq emas. Bunda shifrni ochish uchun bajrilishi kerak bo‘ladigan eng kam miqdordagi amallar sonini aniqlash muhimdir.
Zamonaviy ochiq kalitli kriptotizimlar quyidagi turdagi masalalarni yechishning ko‘p vaqt talab qilishi va hisob-kitoblar uchun hisoblash qurilmalarida katta hajmdagi xotira talab etilishi bilan bog‘liq bo‘lgan murakkabliklarga tayanadi:
1. Yetarli katta sonlarni tub ko‘paytuvchilarga yoyish (faktorlash).
2. Xarakteristikasi yetarli katta bo‘lgan chekli maydonlarda diskret logarifmlarni hisoblash.
3. Yetarli katta tartibdagi algebraik tenglamalar tizimining ildizlarini chekli maydonlarda hisoblash.
4. Elliptik egri chiziqlarda ratsional koordinatali nuqtalarni topish, ularni qo‘shish hamda tartibini aniqlash.
5. Xarakteristikasi yetarli katta bo‘lgan chekli parametrli gruppalarda parametrni topish.