Rossiya Federatsiyasi Ta'lim va fan vazirligi Oliy kasbiy ta'lim davlat ta'lim muassasasi

1.3 Elliptik egri chiziqdagi ElGamal shifrlash

Diskret logarifmlarga asoslangan kriptografik tizim elliptik egri chiziqlar yordamida amalga oshirilishi mumkin.
P maydoni ustidagi elliptik egri chiziq uchinchi tartibli silliq chiziqdir (tor ma'noda elliptik egri chiziq). Keng ma’noda P ustidagi elliptik egri chiziq F( x, y )=O uchinchi darajali tenglamaga ega bo‘lgan elliptik egri chiziq bo‘lib, P maydonining har qanday kengayishi bo‘yicha silliq egri chiziqni aniqlaydi. Ma'lumki, tegishli koordinatalar tizimida chekli maydon ustidagi har qanday elliptik egri chiziq tenglamasi shaklga ega bo'ladi.
C) y + fX + ad + ab.
Agar koordinatalari ( xo, yo ) boʻlgan A nuqta (*) tenglamali egri chiziqqa tegishli boʻlsa, A ga qarama-qarshi boʻlgan nuqta nuqta deyiladi.
to'g'ridan-to'g'ri tekshiriladi - (- A) = A. E'tibor bering - A nuqta ham egri chiziqqa tegishli bo'ladi. Agar P maydoni 2 xarakteristikaning maydoni bo'lmasa, u holda egri chiziq tenglamasini y2=x3+phx2+ad+a6 ko'rinishga keltirish mumkin.
Agar maydonning xarakteristikasi 2 yoki 3 ga teng bo'lmasa, egri chiziq tenglamasini y \u003d x + ax + b ko'rinishiga keltirish mumkin, bu Weierstrass shakli deb ataladi.
Elliptik egri chiziq (*) tenglama bilan berilsin. Ushbu egri chiziqning nuqtalariga cheksizlik 0 deb ataladigan nuqtani qo'shamiz va hosil bo'lgan G to'plamiga qo'shish amalini quyidagi qoidalarga muvofiq aniqlaymiz:

2. 
   V AEG: A-4-
   
3. 
   mA, BEG, A va A#-B: A+B=-C, bu yerda C nuqtasi quyida tavsiflangan algoritm bilan aniqlanadi. C nuqtasini topish algoritmi.
   

a) A va B nuqtalari orqali rasmiy to'g'ri chiziq (AB) o'tkaziladi, bu A * B holatida sekantdir va A \u003d B holatida bu egri chiziqqa tegib, A nuqtada chizilgan.
b) (AB) chiziq va ko'rib chiqilayotgan egri chiziqning kesishish nuqtalari topiladi. Ushbu nuqtalarning ko'pligini hisobga olsak, aniq uchta bo'ladi: A, B va C.
E'tibor bering, C nuqta A va B dan farq qilishi shart emas.
Kiritilgan qo'shish amaliga kelsak, G to'plami elliptik egri chiziqning nuqtalar guruhi deb ataladigan Abel guruhi bo'ladi.
Elliptik egri nuqtalar guruhida ElGamal usuli bilan shifrlash quyidagicha amalga oshiriladi:

1. 
   G = (ho y( ;) - tanlangan nuqta E(F);
   
2. 
   n - E(F) guruhidagi G ning tartibli tub son;
   

H) h - / n - "kofaktor " G.
ph, a, b, G, n, h) parametrlari birgalikda kriptografiya nuqtai nazaridan ma'lum bir elliptik egri chiziqni o'rnatadi.
d - {l, 2,n-1} dan tasodifiy butun son - maxfiy kalit
Q = dG - egri nuqta - ochiq kalit
Bunday kriptotizimlarni qurishning asosiy printsipi y = q ^x modp operatsiyasini Y = [x] G mod p bilan almashtirishdir.
Bundan tashqari, yagona farq shundaki, birinchi holatda y raqam va ichida
ikkinchi U allaqachon nuqta.
Kriptotizimlarni yaratishda bir necha yondashuvlar mavjud. Birida, barqarorlikni ta'minlash nuqtai nazaridan eng ishonchli strategiya tasodifiy egri chiziqni tanlashdir. Boshqa yondashuv esa berilgan xossalarga ega egri chiziqni tizimli ravishda qurish orqali hisoblash nuqtai nazaridan samaradorlikni oshirish muammosini qo‘yadi. Bunday holda, xakerlikdan himoya qilish bilan bog'liq muammolar mavjud, chunki. yondashuvni amalga oshirishning maxsus usullari egri chiziqlardan foydalanishga asoslangan bo'lib, ular aslida ba'zi o'ziga xos xususiyatlarning yo'qligi bilan nisbatan kichik sinfdan tanlanadi.
12
Keling, ElGamal shifrining elliptik egri chiziqlardagi nazariy tatbiqlarini tasvirlaylik.
foydalanuvchilari U ) uchun biz umumiy elliptik egri Ep (a, b) va undagi G nuqtasini tanlaymiz. Bundan tashqari, G, [2]G, [3]G, ..., [n]G turli nuqtalar va ba'zi bir tub son q uchun [q]G = 0.
< ʼn < q sonini tanlaydi va ochiq kalitni - DU = [CU]G egri chizig'idagi nuqtani hisoblaydi. Ochiq kalitlar ro'yxati va egri parametrlar ochiq kanal orqali tarmoq foydalanuvchilariga uzatiladi.
Elliptik egri chiziqlar bo'yicha ElGamal tizimida shifrlash va dekodlashning amalga oshirilishini tasvirlaylik.
< p son sifatida ifodalansin .
Shifrlash algoritmi:

1. 
   tasodifiy K sonni tanlaydi, 0 < K < q;
   
2. 
   = [k]G, P = [k]DB =
   

3) shifrlash e = mx mod p; 4) (R, e) - shifrlangan matn.
Shifrni ochish algoritmi:

1. 
   Ma'lum (R, e) dan biz Q = [CB]R - ex -1 mod p ni hisoblaymiz;
   
2. 
   Biz t' = t ni olamiz, chunki
   

Amalga oshirishning mohiyati shundaki, Q nuqtasining x koordinatasi sir bo'lib qoladi (raqam
K noma'lum). K ni hisoblash qiyin ish hisoblanadi, chunki buning uchun egri chiziq bo'yicha diskret logarifm masalasini hal qilish kerak.
Ko'rib chiqilgan protokol blok yoki oqim shifrlash uchun maxfiy kalitning m soni sifatida uzatish uchun keng qo'llaniladi. Bunday holda, egri parametrlarni logqr shifrlash kalitining uzunligi ikki barobarga teng bo'lishi uchun tanlash kerak.
GOST R 34.10-2012 va GOST R 34.10-2001 elliptik egri chiziqlarga asoslanganligini unutmang. Ushbu algoritmlarning barqarorligi elliptik egri chiziqdagi nuqtalar guruhida diskret logarifmni hisoblashning murakkabligi bilan bog'liq.