Elliptik egri chiziqlar nazariyasi va ularning kriptografiyaga tadbiqi

Egri chiziqning singulyar emaslik sharti. Mayli, biz Veyershtrassning kanonik shakldagi tenglamasi bilan berilgan elliptik egri chiziqlariga qaraylik


bunda (1) tenglamani umumiy ko’rinishdagi kublik tenglama ko’rinishda quyidagicha ifodalashimiz mumkin

Ya’ni, tenglikning o`ng tomoni uchinchi darajali oddiy ko’phad sifatida qaraladi.

Yuqoridagi (1), (2) tengliklardagi funksiyasining koyfisientlari ratsional hususiy holda haqiyqiy sonlar to’plami elementlari sifatida qaraymiz. Bunda, yuqoridagi (2) uchinchi tartibli ko’phad eng kamida bitta haqiyqiy ildizga ega bo’ladi. (2) turidagi tenglamani haqiyqiy yechimlariga ega bo’lish ko’paytuvchilarga ajratish usulidan foydalanamiz

bunda, – haqiyqiy sonlar. Agar ko’phad bitta haqiyaiy ildizga ega bo’lsa, u holda (1) elliptik egri chiziq quyidagicha ko’rinishga ega bo’ladi 1-rasm.
1-rasm

1-rasm. bitta ildizga ega ko’phad uchun elliptik egri chizig’ining ko’rinishi

Agarda berilgan uchta haqiqiy ildizga ega bo`lsa, u holda elliptik egri chiziq egri chiziq quyidagi rasmdagi kabi ko`rinishga ega bo’ladi 2-rasm.

2-rasm

2-rasm. bitta ildizga ega ko’phad uchun elliptik egri chizig’ining ko’rinishi
bunda holda haqiqiy nuqtalar ikki tarkibiy qismni tashkil qilgan holda, tenglamaning ildizlari har xil bo’lganda o’rinli bo’ladi. Elliptik egri chiziqlarni tanlab olishda aynan manashu holat bizni qiziqtiradi. Bundan quyidagicha savol kelib chiqadi.

• 
  Bu keltirilgan shart kriptotizimlar uchun elliptik egri chiziqlarni tanlashda qanchalik muhimlik kasb etadi?
  

Dastlab shuni eslatib o’tishimiz kerakki, biz kriptotizimlarda elliptik egri chiziqlarni faqatgina uning nuqtalar guruxini tashkil qilish va undan algoritmda foydalanish uchun qo’llaymiz. Albatta nuqtalar guruxlari va to’plamlarida barcha amallar geometrik tuzilishlar bilan bog’liq bo’ladi. Bunda, ixtiyoriy egri chiziqning
va nuqtalari uchun nuqtasi – bu o’qiga nisbatan simmetrik akslatiriladi, elliptik egri chizig’i bilan to’g’ri chizig’ining kesilishishining uchinchi nuqtasi olinadi. Shuning uchun, biz avvalo egri chiziqning ixtiyoriy nuqtalari uchun mos geometrik elementlar (vatarlar va urinmalar)ning mavjud bo’lish shartlariga e’tibor berishimiz kerak.
Endi biz egri chiziqning tenglamasini quyidagicha,

ko’rinishda yozamiz. (1) ko’rinishdagi egri chiziq funksiyasidan birinchi tartibli hususiy hosilalarni olamiz

hususiy hosilalarni olamiz. Agar hususiy hosilalar egri chiziqning ba’zibir nuqtasida nolga intilsa, u holda bo’lib, o’z navbatida va ko’phadlari umumiy ildizga ega bo`ladi, ya`ni nuqtasi funktsiyaning ikkilangan ildizi hisoblanadi. Aksincha, agar ikkilangan ildizga ega bo’lsa, u holda nuqtasi egri chiziqning singulyar (maxsus nuqta) nuqtasi kelib chiqadi. Shunday qilib, keltirilgan tenglamalardan tushunishimiz mumkinki singulyarlik tushunchasini quyidagicha holatdagina mavjudligini ko’ramiz.

1. 
   Berilgan funksiyaning hususiy hosilalari mavjud bo’lmasa.
   
2. 
   Berilgan funksiyaning hosilasi
   

Shundan, quyidagicha shartlar kelib chiqadi.

1. 
   Agarda elliptik egri chiziq singulyar (maxsus) nuqtaga ega bo’lsa, egri chiziq ham singulyar (maxsus) bo’ladi.
   
2. 
   Agarda bir vaqtda o’zgaruvchilarga nisbatan xususiy hosilalar bir vaqtning o’zida mavjud bo’lmasa, egri chiziq singular emas (maxsus emas) egri chiziq bo’ladi.
   

Bu shartlar egri chiziqdagi har bir nuqta to’liq ma’lum urinmaga ega ekanligini bildiradi.
Mayli masalani aniqroq ko’rsataylik, biz faqatgina singulyar bo’lmagan egri chiziqlarga e’tibor qaratishimiz kerakmi? Albatta bu masalani chuqur mulohaza qilgan holda tushunish lozim. Endi, elliptik egri chiziqlarning singulaylik (maxsuslik) holatini birqancha aniqroq qaraymiz. Bunda singulyarlikning ikkita turi mavjud bo’ladi. Ularning qaysi turi kelib chiqishi funksiyasining ikkilangan yoki uch karrali ildizga ega bo’lishiga bog’liq bo’ladi. Biz quyidagicha elliptik egri chiziqni tahlil qilgan holda, funksiyaning ikkilangan ildizlar mavjud holini o’rganishimiz zarurli va yetarli.

Keltirilgan egri chiziq 2-rasmda ko`rsatilgandek, har xil yo’nalishli urinmalari bo’lgan singulyar nuqtaga ega bo’ladi, ya’ni bu nuqtada urinma bir qiymatli aniqlanmaydi 2-rasm.

3-rasm. Egri chiziqlarning singulyarligi
Agar funksiyasining uchta karrali ildizlari mavjud bo’lsa, u holda tenglamani quyidagicha ko’rinishga keltirishimiz mumkin.

Bu funksiya grafigi uchlari koordinata boshida yotuvchi yarim kubli parabolani hosil qiladi 4-rasm.

4-rasm

4-rasm. Egri chiziqning singulyarligi
Veyershtras egri chiziqning singulyarlik hossasini qanoatlantiruvchi bir qancha misollarni funksiyalarni keltirishimiz mumkin, lekin bu funksiyalarning barchasi grafik kordinatalari o’zgarishi natijasida umumiy holga keltiriladi.
Endi berilgan funksiyaning ratsional nuqtalariga to’g’ri chiziqdagi ratsional nuqtalar bilan yakka muvofiqlik qo’yish mumkin. Shunday qilib, elliptik egri chiziqning to’g’ri chiziqqa proektsiyasi o’zaro yakka akslanishini ko’rishimiz mumkin.
Haqiqatan ham, agar biz almashtirishni qo’llash natijasida (7) tenglama ko’rinishga keltiramiz. Bundan, va ekanligi kelib chiqadi. Har bir ratsional soni uchun va ni aniqlash mumkin, ya’ni elliptik egri chiziqda ratsional nuqtani olish mumkin; agar biz kubda ratsional nuqtadan boshlasak, unda biz ratsional songa ega bo’lamiz. Bu amallar bir-biriga teskari va egri chiziqda maxsus nuqtadan tashqari barcha ratsional nuqtalar uchun aniqlanadi. Lekin bu shuni bildiradiki, bunday usul bilan biz egri chiziqdagi barcha ratsional nuqtalarga ega bo’lishimiz mumkin. Endi, (7.1) turidagi egri chiziqni qaraylik. Bunda biz quyidagicha almashtirishlarni bajaramiz.

Shunday qilib, singulyar egri chiziq holatida biz uning ratsional nuqtalarining to’plami o’rniga ba’zibir to’g’ri chiziqning nuqtalar to’plamini qarashimiz mumkin. Shunday qilib, singulyar kublar undagi ratsional nuqtalar kabi tahlil yetarlicha natijali hisoblanmaydi. Lenkin singulyarlikdan qutulish gurux nuqtalariga ega bo’lishga imkoniyat beradi. Endi, biz quyidagicha singulyar bo’lmagan elliptik egri chiziqlarni o’rganamiz. Bunda quyidagicha muammolar kelib chiqadi. Berilgan elliptik egri chiziqning singulyarlik shartida tekshirish va singulyar emasligini aniqlash lozim.

Endi, biz hosilalari hosilalari bir vaqtning o’zida yo’qolib ketuvchi (nolga teng) nuqtalarga ega bo’lmaydigan egri chiziqlarni ko’rib chiqaylik.

(8) turidagi egri chiziqlar silliq deb ataladi.
Keltirilgan ellitik egri chiziqning silliqligi diskriminanta tushunchasiga bog’liq bo’lib hisoblanadi. Diskriminantani o’rganishda asosan polinom ko’phadlar va algebraik tenglamalar sistemasini tadqiqot qilish lozim.
Faraz qilaylik, bizga quyidagicha polinom ko’phad berilgan bo’lsin,

(9) turidagi polinom ko’phadning diskriminantini hisoblash uchun koyfitsienti va tenglamaning ildizlarining barcha ayirmalarining ko’paytmasi hisoblashimiz:

Bunda, butun foyfitsientlar, -Vandermont aniqlovchisi. Vandermont aniqlovchisi quyidagicha matritsani tuzadi.

Bunda, diskriminant ildizlarning simmetrik¹ funktsiyasi bo’lib, eng kamida bir karrali ( va ning ildizi bo’lishi shart bo’lgan) ildizga ega bo’lgandagina nolga aylanadi. Muammoning yechimi sifatida quyidagicha berilgan

(12)
kublik uchhadning ildizlari bo’lganda diskerminantini hisoblash lozim bo’lsin. Buning uchun dastlab quyidagicha formuladan foydalanamiz
(13)
bunda, - hususiy hosilalarni
(14)
hisoblagan holda (13) tenglamaga qo’yamiz.
(15)
Endi (15) tenglamani quyidagicha soddalashtiramiz
(16)
Endi quyidagicha almashtirisharni bajaramiz. Bizga elementar matematikadan ma’lumki,
(17)
(18)
(17),(18) tengliklarni (16) tenglamaga qo’yamiz va quyidagicha ifodaga ega bo’lamiz
(19)
bundan, elliptik egri chiziqning kubik ko’phadi diskerminantining umumiy ko’rinishi kelib chiqadi. Shundan bizda (19) tenglamani kanonik ko’rinishga keltirish muammoli kelib chiqadi. (19) tenglamani kanonik ko’rinishga keltirishda quyidagicha belgilashlarni kiritamiz
(20)
mos holda almashtirishlarni bajargan holda soddalashtiramiz. Natijada,
(21)
(2) normal ko’rinishdagi elliptik egri chiziq uchun funksiyasining diskerminanti miqdori hisoblanadi. Shunday qilib, (2) turidagi elliptik egri chiziqlar uchun diskerminantni hisoblashning umumiy kanonik shaklini keltirib chiqardik. Yuqoridagi (21) tenglamaga asoslangan holda, sharti bajarilsa quyidagicha (7) ko’rinishidagi elliptik egri chiziqlar diskerminantining umumiy tenglamasi kelib chiqadi.
(22)
Xulosa o’rnida shuni aytishimiz kerakki, yuqoridagi teoremalardan ko’rishimiz mumkinki, ko’phad faqat diskerminanti bo’lgandagina karrali ildizga ega bo’ladi. Agarda, diskriminatning sharti bajarilmasa, u holda funksiyaning ildizlari har xil ekanligi ma’lum bo’ladi. Shundan, nollik emas diskriminantli har xil rastional koeffitsientli (ya’ni R maydonida) elliptik egri chiziq silliq egri chiziqni ifodalab, uning har bir nuqtasiga urinma yurgizish mumkin ekanligini ko’rsatadi. Elliptik egri chiziqlar nazariyasini chuqur tadqiq qilishda Veyl juftliklar va diskret logarifmlash masalalarining yechimlari yuqori ahamiyatni kasb etadi.
Foydalanilgan adabiyotlar

1. 
   Miller V.C. Use og Elliptic Curve in Cryptography // Cryptology: Proceedings of Crypto 85, Springer LNCS 218, 1986. – P. 417-426.
   
2. 
   Lenstra H.W. Factoring integers with elliptic curves //Ann. Of Vath, (2) 126 (1987). – H. 674-745.
   
3. 
   Silverman J. The Arithmetic of Elliptic Curves. – New York: Springer-Verlag, 1986.
   
4. 
   Долгов В.И., Лисицкая И.В. Теория групп и колец: Конспект лекцій з дисципліни ″Спеціальні розділи математики″. – Х.: ХТУРЭ, 2000.
   
5. 
   Diffie W., Hellman M. E. New Directions in Cryptography // IEEE Transactions on Information Theory. November 1976. – V.IT-22, n.6. – Р. 644-654.
   
6. 
   Koblitz N. Eliptic Curve Cryptosystems // Mathematics of Computation. – 1987. – V. 48, № 177. – Р. 203-209.
   
7. 
   Menezes A., Okamoto T., Vanstone S. Reducing Elliptic Curve Logarithms to a Finite Field // IEEE Trans. Info. Theory. – 1993. – 39. – Р. 1603-1646.
   
8. 
   Coppersmith D. Fast evaluation of logarithms in fields of characteristic two // IEEE Trans. Inform. Theory. 1984. – IT 30. –Р. 587-594.
   
9. 
   G. Juraev and K. Rakhimberdiev, Mathematical Modeling of Credit Scoring System Based on the Monge-Kantorovich Problem, 2022 IEEE International IOT, Electronics and Mechatronics Conference, IEMTRONICS 2022 Proceedings.
   
10. 
    G. Juraev and K. Rakhimberdiev, Modeling the decision-making process of lenders based on blockchain technology, International Conference on Information Science and Communications Technologies: Applications, Trends and Opportunities, ICISCT 2021, pp. 1-5.
    
11. 
    G. Juraev and K. Rakhimberdiev, Prospects of application of blockchain technology in the banking , International Conference on Information Science and Communications Technologies: Applications, Trends and Opportunities, ICISCT 2022, pp. 1-5.
    
12. 
    M. Karimov, J.Arzieva and K. Rakhimberdiev, Development of Approaches and Schemes for Proactive Information Protection in Computer Networks, International Conference on Information Science and Communications Technologies: Applications, Trends and Opportunities, ICISCT 2022, pp. 1-5.
    
13. 
    K.Tashev, J. Arzieva, A. Arziev and K. Rakhimberdiev, Method authentication of objects information communication systems, International Conference on Information Science and Communications Technologies: Applications, Trends and Opportunities, ICISCT 2022, pp. 1-5.
    
14. 
    J. Arzieva, A.Arziev and K. Rakhimberdiev, Modeling the decision-making process of lenders based on blockchain technology, International Conference on Information Science and Communications Technologies: Applications, Trends and Opportunities, ICISCT 2022, pp. 1-5.
    

1^ Simmetrik funktsiya – o’z argumentlarini ixtiyoriy almashtirishdan o’zgarmaydigan funktsiya