5-amaliy mashg’ulot Mavzu: Elliptik ergi chiziqlarda nuqtalarni n lashtirish imkonini beruvchi dasturiy vositani ishlab chiqish

5-amaliy mashg’ulot
Mavzu: Elliptik ergi chiziqlarda nuqtalarni n lashtirish imkonini beruvchi dasturiy vositani ishlab chiqish. EECh asoslangan Diffi-Xelman algoritmi
Ishdan maqsad: Elliptik ergi chiziqlarda nuqtalarni n lashtirish imkonini beruvchi dasturiy vositani ishlab chiqish. EECH algoritmlari bilan amaliy ishlash ko’nikmasiga ega bo’lish.
Matnlarni elliptik egri chiziqlar yordamida shifrlash va shifrlash uchun bir necha usullardan foydalanilgan. Ulardan biri, rasmda ko‘rsatilgandek, yoki ichidagi elliptik egri chiziqdan foydalanib El Gamal kriptosistemasini modellashtirishdir.

Rasm. Elliptik funktsiyadan foydalangan holda El Gamal kriptosistemasi.
Bob yoki dagi elliptik egri chiziq bilan ni tanlaydi.
Bob egri chiziqqa nuqta qo‘yadi,
Bob sonini tanlaydi.
Bob ni hisoblaydi. Iltimos, diqqat qiling: bu erda ko‘paytirish yuqorida aniqlangan nuqtalarni ko‘paytirishni anglatadi.
Bob ni ochiq kirish kaliti sifatida e’lon qiladi; u maxfiy kalit sifatida ni saqlaydi.
Shifrlash
ALISA o‘zining boshlang‘ich matni sifatida egri chiziqdagi nuqtani tanlaydi, esa u bir nechta nuqtalarni hisoblab chiqadi, shifrlangan matn sifatida yo‘naltiradi:

O’quvchi o‘zboshimchalikdagi manba matni qanday qilib elliptik egri chiziqqa nuqta bo‘lishi mumkinligi haqida savol tug‘dirishi mumkin. Bu modellashtirish uchun elliptik egri chiziqni qo‘llashdagi asosiy muammolardan biridir. Alisa algoritmdan foydalanib, egri chiziqdagi belgilar va nuqtalar o‘rtasida to‘g‘ridan-to‘g‘ri yozishmalarni topishi kerak.
Deshifrlash
Bob, va ni olgandan so‘ng, quyidagi formuladan foydalanib, , boshlang‘ich matnni hisoblaydi:
Bu erda minus belgisi inversiya bilan qo‘shishni anglatadi.
Bob tomonidan hisoblangan , quyida ko‘rsatilgandek, Alisa tomonidan etkazilgan bilan bir xil ekanligini isbotlashimiz mumkin:

egri chiziqdagi nuqtalardir. E’tibor bering, egri chiziqqa ikkita teskari nuqta qo‘shishning natijasi nol nuqtadir.
Misol.
dagi elliptik egri chiziq yordamida shifrlashning juda arzimas namunasi.
1. Bob ni dagi elliptik egri sifatida tanlaydi.
2. Bob va ni tanlaydi.
3. Bob ni hisoblaydi, bu erda
4. Bob guruhni e’lon qiladi
5. Alisa ) asl matnni Bobga berishni xohlaydi. U ni tanlaydi.
6. Alisa nuqtani topadi, bu erda
7. Alisa nuqtani topadi, bu erda
8. Bob va ni oladi. U dan foydalanadi va oladi (23, 25).
9. Bob (23, 25) nuqtani o‘zgartiradi va (23, 42) nuqtani oladi.
10. Bob ni qo‘shadi va asl matn manbasini oladi.
Taqqoslash
Elliptik egri chiziq yordamida El Gamal algoritmini uning varianti bilan qisqacha taqqoslash.

1. 
   Al-Gamal algoritmida multiplikativ guruh qo‘llaniladi; variant - elliptik guruh.
   
2. 
   El-Gamal algoritmidagi ikkita a’zo multiplikativ guruhdagi raqamlardir; Elliptik egri chiziqda nuqta variantini qo‘llashda.
   
3. 
   Har bir algoritmdagi maxfiy kalit butun sondir.
   
4. 
   Har bir algoritmda Elis tomonidan tanlangan maxfiy raqamlar butun sonlardir.
   
5. 
   El Eamal algoritmida quvvatni ko‘tarish bir nuqtani doimiyga ko‘paytirish bilan almashtiriladi.
   
6. 
   El Eamal algoritmidagi ayirish nuqta qo‘shilishi bilan almashtiriladi.
   
7. 
   El Eamal algoritmida inversiya - multiplikativ guruhdagi multiplikativ inversiya; inversiya - bu egri chiziqdagi nuqtaning qo‘shimchali inversiyasi bilan almashtiriladi.
   
8. 
   Hisoblash odatda elliptik egri chiziqda osonroq, chunki ko‘paytirish eksponentatsiyaga qaraganda oson, qo‘shimcha ko‘paytirishga qaraganda osonroq va teskari topish elliptik egri guruhda multiplikativ guruhga qaraganda osonroq.
   

Elliptik egri usulining xavfsizligi
Xabarning shifrini ochish uchun Eva yoki qiymatini topishi kerak.

1. 
   Agar Eva qiymatini bilsa, u dan foydalanib, manba matni bilan bog‘liq nuqtani topishi mumkin. Ammo ni topish uchun Eva tenglamani echishi kerak. Bu va egri chizig‘idan ikkita nuqta topishni anglatadi. Eva dan boshlab hosil qiluvchi omilni topishi kerak. Ushbu muammo elliptik egri chizig‘ining logarifmasi deb nomlanadi, bu muammoni hal qilishning yagona ma’lum usuli - Polard algoritmi bo‘lib, agar da katta qiymat va da katta berilgan bo‘lsa, bu mumkin emas.
   
2. 
   Agar Eva qiymatini bilsa, u dan foydalanib, manba matni bilan bog‘liq nuqtani topishi mumkin. bo‘lgani uchun, bu oldingi xatboshidagi kabi bir xil muammo. Eva va ning ma’nosini biladi - u ni topishi kerak.
   

Elliptik egri chiziq bilan kriptotizimning xavfsizligi elliptik egri chizig‘ining logarifmini echishda murakkabliklarga bog‘liq.
Modul hajmi
Xuddi shu darajadagi xavfsizlik (hisoblash xarajatlari) uchun n modul elliptik tizimda ga qaraganda kichikroq bo‘lishi mumkin. [Masalan, 160 bitdan iborat n bilan da , 1024 bitli bilan bir xil darajadagi xavfsizlikni ta’minlay oladi.
Topshiriq
Har bir talaba El Gamal kriptotizimiga asoslanga elliptik egri chiziqning kriptografiyasida kalitlar hosil qilib, o‘z ismini shifrlasin.
Nazorat savollari
Chekli maydon deb nimaga aytiladi.
Elliptik egri chiziq algoritmlari qanday muammoga asoslangan