Texnologiyalari universiteti kriptografiyaning matematik asoslari

5.2. 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. Koblis 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 y  f x funksiyaki, uning aniqlanish sohasidan bo‘lgan ixtiyoriy x uchun f x yqiymat oson hisoblanadi, qiymatlar sohasining barcha y qiymatlariga mos keluvchi x 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 zZ parametrlarga bog‘liq bo‘lib, teskarisiga ega bo‘lgan shunday f_Z funksiyalar sinfiki, berilgan z parametrda aniqlanish sohasidagi barcha xX argumentlar uchun f_Z x y qiymatlarni oson hisoblash algoritmi E_Z mavjud bo‘lib, qiymatlar sohasidagi barcha yY qiymatlar uchun f_Z^1 y x qiymatlarni ma’lum bo‘lgan E_Z algoritm bilan hisoblashning imkoniyati yo‘q (yoki boshqacha aytganda f_Z^1 y x 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 rasional koordinatali nuqtalarni topish, ularni qo‘shish hamda tartibini aniqlash.
   
5. 
   Xarakteristikasi yetarli katta bo‘lgan chekli parametrli gruppalarda parametrni topish.
   

Quyida nisbatan ommaviylashgan ochiq kalitli kriptotizimlar qisqacha
ko‘rib o‘tiladi.