Elliptik egri chiziqlarni tanlashda veyl juftliklari va diskret logarifm masalasi tadbiqi

ELLIPTIK EGRI CHIZIQLARNI TANLASHDA VEYL JUFTLIKLARI VA DISKRET LOGARIFM MASALASI TADBIQI


Raximberdiyev Q.B. (O’zbekiston milliy universiteti, tayanch doktarant)
Bozorov A.X. (O’zbekiston milliy universiteti, tayanch doktarant)

Kriptografik algoritmlar uchun elliptik egri chiziqlarni tanlash shartlarini muhokama qilgan holda, shuni takidlashimiz lozimki elliptik egri chiziqlar kriptografik algoritmlar, blokcheyn texnologiyasi va kriptovalyutalar (Bitcoin, ethurum, Litecoin h.k.) keng qo’llaniladi.

Bizning oldimizda turgan muammolar quyidagicha:

1. 
   Elliptik egri chiziqlarni to’g’ri tanlash;
   
2. 
   Effektiv va tez hisoblanuvchi elliptik egri chiziqlarni tanlash;
   
3. 
   Singulyar elliptik egri chiziqlarni aniqlash va bu muammoni matematik nazariyalar asosida hal qilish;
   

Bu qo’yilgan masalalarni yechishda elliptik egri chiziqlar nazariyasini chuqur o’rganish, elliptik egri chiziqlar ustidagi ilmiy tadqiqot ishlarini va keltirilgan xulosalarni tahlil qilish zarur. Jumladan ko’pgina ilmiy tadqiqot ishlari xulosalarini tahlil qilish natijasida elliptik egri chiziqlarning nuqtalar guruxlarini akslantirish va ular asosida kriptoalgortimlar, protokollar va kriptovalyutalarni shakllantirishda qo’llash effektiv natijalarga olib kelishini ko’rishimiz mumkin.
Kriptografik algoritmlarda elliptik egri chiziqlarni qo’llashning eng asosiy bosqichlaridan biri egri chiziqni tanlash bo’lib hisoblanadi. Tadqiqotlar davomida, elliptik egri chiziqlarni tanlashda supersingulyarlik muammosi kelib chiqdi. Supersingulyarlik elliptik egri chiziqlarni tanlashda bir qancha cheklovlarni keltirib chiqaradi. Masala mohiyatini tushunishda, dastlab kriptografik algoritmlarni yasash va ularning turg’unligini ta’minlashning ba’zi printsiplarini o’rganishimiz talab qilinadi. Kriptografik algoritmlarning bardoshliligini oshirishda eng ahamiyatli vositalardan biri bir tomonlama funksiyalar bo’lib hisoblanadi. Bir tomonlama funksiyalarni tuzishning umumiy mohiyati shundan iboratki, katta chekli takrorlanuvchi gurux va generatorini qo’llagan holda, barcha uchun ko’paytma oson hisoblanishi va bajariluvchi ba’zi ixtiyoriy elementi uchun ni hisoblash murakkab bo’ladiganday qilib tuziladi. Bunda, hisoblashlarning osonligi tartibdagi darajaga ega bo’lgan ko’phad qisqa vaqt ichida bajarilishi bilan bog’liq. Bu masalalarni amalga oshirishga misol tariqasida Diffi – Hellman tomonidan tqdim qilingan chekli maydonda darajaga ko’tarish ya’ni eksponensirlash hisoblanadi. Bu printsip, xususiy holda ochiq kalitli kriptografik algoritmlarni yaratish uchun elliptik egri chiziqlarda ishlatiladi.

Kriptografik qo’llashlarda elliptik egri chiziqlar chekli maydonda qaraladi, ya’ni kublik egri chizig’i koeffitsientli tenglamani qanoatlantiruvchi barcha nuqtalarning to’plami sifatida aniqlanadi. Kripto almashtirishlarni bajarish uchun chekli maydoni ustidagi elliptik egri chiziqning ¹ nuqtalari qo`llanilib, ular nuqtalarni qo`shish amaliga nisbatan guruhni tashkil etadi. Bu holda qiyin qaytariluvchi turlantirish, elliptik egri chiziqning nuqtalar guruhining ba’zibir hosil bo’luvchi elementiga karrali bo`lgan nuqtalarni hisoblashdan iborat. U biz yuqorida aytgandek ko’rinishga ega: . Bu yerda elliptik egri chiziqning tayanch nuqtasi (uni shuningdek generator deb ham ataladi), – ba’zibir butun son, . Bu tayanch nuqta katta tartibga ega bo`lishi kerak. Shunda , -marta skalyar ko`paytmani hisoblash nisbatan oson, lekin va ma’lum qiymatlar bo’yicha ni hisoblash qiyin. va ma’lum qiymatlar bo’yicha ko`paytuvchini aniqlash masalasi diskret logarifmlash deb ataladi.

Diskret logarifmlash masalasining asosiy mohiyati va ma’lum qiymatlari bo’yicha ko’paytuvchini topishdan iborat. Berilgan amallarni ko’paytirish orqali talqin qiladigan bo’lsak, bunda bu oshkor additiv va multiplikativ guruhlar o’rtasidagi moslikni bildiradi, bu esa additiv guruh holatida logarifmlash tushunchasini qo’llashni effektivligini ko’rsatib beradi. Bu kriptografik almashtirishning turg’unligi katta oddiy tartibli takrorlash guruxida diskret logarifmlash masalasini yechishning murakkabligi bilan aniqlanadi. Bizning holatda bu egri chiziqning tayanch nuqtasi tomonidan hosil qilingan elliptik egri chiziqning nuqtalari guruxining tartibi anglatadi.
Endi elliptik egri chiziqlarni tanlashdagi navbatdagi cheklovga qaytish mumkin. Dastlab, 1987-yilda Koblits ochiq kalitli kriptotizimlar uchun chekli sondagi element (egri chiziqdagi nuqta)li supersingulyar egri chiziqlar deb nomlanuvchi egri chiziqlarni ishlatishni tavsiya qilgan.
Lekin keyinchalik bunday egri chiziqlar kriptografik qo’llashlar uchun yaroqsiz ekanligi ko’rsatildi. Bunday turdagi egri chiziqlarga asoslangan kriptotizimlar 1993-yilda A.Menezis, T.Okomoto va S.Venston tomonidan taqdim qilingan diskret logarifmlash algoritmlari bilan hujum qilinishi mumkin. Bu algoritm berilgan chekli maydonning ba’zi sohalarining multiplikativ guruhiga maydoni ustida elliptik egri chiziqning nuqtalari guruhini o’rnatish uchun Veyl juftliklarini foydalanib, egri chiziqdagi diskret logarifmlash masalasini chekli maydondagi diskret logarifmlash masalasiga olib kelishga imkon beradi[5]. So’ngra Koblits tomonidan taqdim qilingan elliptik egri chiziqlarni qo`llash uchun birqancha ishonchli deb faraz qilingan ba`zibir boshqa supermaxsus egri chiziqlar bilan almashtirishga kuch berildi. Lekin, bu egri chiziqlarni ham katta o`lchamdagi ba`zi bir chekli maydonga olib kelish mumkin.
Endi, biz A.Menezis, T.Okomoto va S.Venston tomonidan taqdim qilingan algoritmning mohiyatini eslatamiz. Berilgan algoritmning asosiy goyasi shundan iboratki, Biror maydonida qaralayotgan elliptik egri chizig’ining nuqtalar guruxida diskret logarifmlashni hisoblashda, nuqtalar guruxini maydoning multiplikativ va diskret logarifmlash masalasiga keltirishdan iborat.
Bizga elliptik egri chiziqlar nazariyasidan ma’lumki, ixtiyoriy nuqtalar to’plamida, nuqtalarni qo’shish, ko’paytirish kabi arifmetik amallar qiymatlari va kiritilgan elliptik egri chiziq nuqtalari cheksizlikdagi nutalar guruxini tashkil qiladi[3,4].
Bundan Elliptik egri chiziqning ixtiyoriy nuqtasi chekli tartibli nuqtalar guruxining qism guruxini shakllantiradi. Bunday qism guruh elliptik egri chiziqning aylanish guruhi deb nomlanadi.
Agar – toq son bo’lsa, unda aylanish guruhining tartibi ko’rinishida bo’ladi. Kriptografik algoritmlar aynan oddiy tartibli takrorlash guruhida tuziladi. Bu takrorlash guruhi aylanish guruhining qism guruhi hisoblanadi. Aylanish guruhining boshqa nuqtalari asosiy maydonga ( elementli qism maydonga) tegishli bo’lmaydi. Aylanish guruhi chegaralanganlikdan, berilgan maydonning kengaytmasi mavjud bo’lib, unda aylanish guruhining barcha nuqtalari yotadi. Bu kengaytmaning multiplikativ guruhi tartibga ega, shuning uchun Langranj teoremasi bo’yicha bu kengaytmaning multiplikativ guruhiga aylanish guruhining kiritilishi shart bajarilsagina amalga oshirili yetarli va zarurli[5]. Ko’rsatilgan fakt subeksponentsial murakkablikdagi diskret logarifmlash masalasini yechish algorimi mavjud bo’lgan, berilgan chekli maydonning kengaytmasining multiplikativ guruhida diskret logarifmlash masalasiga elliptik egri chiziq nuqtalari guruhidagi diskret logarifmlash masalasini keltirish usulining asosida yotadi.
Haqiqatan, ko’rinishidagi akslantirish natijasida barcha hisoblashlar Veyl juftlashtirilishi yordamida bajariladi, bunda - chekli maydoni multiplikativ guruxining, qism guruxining darajali ildizlar guruxi. Bundan quyidagicha masala qo’yiladi kelib chiqadi.
Masala. Agar va nuqtalari, biror elliptik egri chiziqning tayanch nuqtasiga tegishli bo’lmagan qism guruxdagi nuqta bo’lsa, u holda va uchun akslantirish bichiziqli va aynimaydigan bo’ladi.
Bundan quyidagicha masalaning yechimi kelib chiqadi.
(1)
(2)
Masalaning yechimi shuni ko’rsatadiki, elliptik egri chiziqning tayanch nuqtasining takrorlash guruhida ifodani diskret logarifmlash masalasi, chekli maydonda ni diskret logarifmlash masalasiga keltiriladi.
Agar kengaytirish koyfitsienti birdan kichik bo`lsa, unda berilgan diskret logarifmlash masalasi uchun subeksponensial algortim mavjud bo’ladi. Masalan, hisoblash nuqtai nazaridan juda qiziqarli supersingulyar egri chiziqlar uchun , shuning uchun asosiy maydonning nisbatan kichik o’lchamlarida bunday egri chiziqlarni kriptografik algoritmlarda qo’llash yuqori natijalarga olib kelmaydi.
Shunday qilib, biz egri chiziqlarni tanlashdagi MOV sharti (Menezis-Okomoto-Venston sharti) deb nomlanuvchi yana bir shartga ega bo’ldik: kriptografik qo`llashga ruxsat berilgan elliptik egri chiziqlarning tayanch nuqtalarining tartibi uchun cheklovni qanoatlantirishi shart.
Bu shuni bildiradi, tayanch nuqtadan hosil bo’luvchi takrorlash guruhi katta tartibga ega bo’lishi kerak (yuqorida keltirilgan muhokamalar 2 xarakteristikasidagi maydon kengaytirish koyfisientiga tegishli, ya’ni umumiy holda gap chekli kengaytirish haqida tushunishimiz kerak).
Bu yerda shuni belgilash kerak, chekli maydonda diskret logarifm murakkablik bilan Kopershmit algoritmi yordamida hisoblanishi mumkin[10]. Keyinchalik, MOV sharti supersingulyar bo’lmagan elliptik egri chiziqlardan foydalanilsa, bajarilishi mumkinligi oshkor bo’ldi.
Demak, shunday xulosaga ega bo’lamizki, bu bir biriga zid bo’lgan supersingulyarlik va supersingulyar emaslik shartlari asosida elliptik egri chiziqlarni tanlashda MOV algoritmidan foydalanish zarur. Supersingulyar egri chiziqni ham MOV algotimidan foydalanishga keltirishimiz mumkin. Endi quyidagicha supersingulyar emaslik masalasini o’rganib tahlil qilamiz.

Mualliflar haqida ma’lumot:

F.I.Sh.	Ish joyi	Kafedrasi nomi	Telefon raqami
Bozorov Asqar Xaitmurotovih	Tayanch doktarant, O’zMU	Axborot xavfsizligi	[phone]
Raximberdiyev Quvonchbek Baxtiyorovich	Tayanch doktarant, O’zMU	Axborot xavfsizligi	[phone]

1