Elliptik egri chiziqning nuqtalarini qo‘shish formulalari uning geometrik ma’nosidan kelib chiqqan holda keltirib chiqariladi. Ko‘rib o‘tilganlarga muvofiq, agar Px1, y1 va Qx2, y2- nuqtalar E -elliptik egri chiziqda yotsa, ya’ni Px1, y1,
Qx2, y2E nuqtalar bo‘lsa, unda ular orqali kesuvchi to‘g‘ri chiziq o‘tkazilib, bu kesuvchi to‘g‘ri chiziq E -elliptik egri chiziqni biror uchinchi R(x3 , y3 ) nuqtada kesib o‘tadi.
3-tasdiq. Agar Px1, y1, Qx2, y2E nuqtalar rasional koordinatali bo‘lsa,
u holda R(x3 , y3 ) nuqta koordinatalari ham rasional bo‘ladi.
Isboti. Px1, y1 , Qx2 , y2 E nuqtalar orqali o‘tuvchi to‘g‘ri chiziqning umumiy ko‘rinishi:
y kx d
ifodaga ega bo‘lib, bu yerda k, d – koeffisiyentlar P(x1, y1 ) va Q(x2 , y2 ) nuqtalarning koordinatalari orqali ifodalanadi. P(x1, y1 ), Q(x2 , y2 ) -nuqtalar
ykxd chiziqqa tegishli. Bundan esa:
y1 kx1 d,
y2 kx2 d, y1 y2 k(x1 x2 )ва k yx11 xy22 , ekanligi kelib chiqadi.
Shuningdek,
y y2 x1 y2x1 y1x2 .
d y1 kx1 y1 x x2 x1 x2
Shunday qilib, u = k x + d to‘g‘ri chizig‘i tiklab olindi. Keyingi qadamda u = kx+d – ifoda y2 x3 ax2 bxc,
elliptik egri chiziqning tenglamasiga qo‘yiladi, yani
(kx d)2 x3 ax2 bx c,
x3 (a k 2 )x2 (b 2kd)x c d 2 0,
u holda uchinchi tartibli tenglama uchun Viyet teoremasiga ko‘ra:
x1 x2 x3 k 2 a
tenglik o‘rinli bo‘lib, bu oxirgi tenglikda x1, x2 - rasional sonlar bo‘lgani uchun, x3 ham rasional son bo‘ladi. Xuddi shuningdek,
y3 kx3 d
ifodaga ko‘ra y3 - sonining ham rasional ekanligi kelib chiqadi.
Bu keltirilgan tasdiq isbotidan esa P Q yig‘indi nuqta koordinatasini hisoblash formulasini keltirib chiqarish mumkin. P Q nuqta R – nuqtani Ox- o‘qiga simmetrik ko‘chirishdan hosil bo‘lar edi. Natijada, yig‘indi nuqtaning koordinatalari (u,v) , deb belgilansa, bu koordinatalar quyidagi formulalar orqali topiladi:
u k 2 a x1 x2 , v kud (k(ux1 ) y1 )
chunki u x3 , v y3. Bu formulada k -koeffisiyenti qiymatining
o‘rniga y1 y2 qo‘yilsa, quyidagi tengliklar hosil bo‘ladi:
x1 x2 v y1 y2 (ux1) y1, x1 x2
u ((yx11 xy22))22 (ax1 x2) (7)
Bu yerda, x1 x2 .
Agar x1 x2 bo‘lsa, u holda kesuvchi to‘g‘ri chiziq o‘rniga urinma o‘tkazilib, quyidagi formulalar keltirib chiqariladi:
2
u2x1 a 4y12 ,
vy1 3x12 2ax1 b (ux1). (8) 2y1
Shunday qilib, hyech bo‘lmasa bitta P - rasional nuqta elliptik egri chiziqdagi nuqta bo‘lsa, u holda (7), (8) - formulalar orqali [2]P-ni topish uchun, [2]P=P+P, [3]P-ni topish uchun, [3]P=[2]P+P, shu kabi [4]P=[3]P+P, [5]P=[4]P+P va hokazolarni topishimiz mumkin bo‘ladi.
Shuni alohida ta’kidlash kerakki, keltirilgan (7) va (8) formulalar (3) tenglamaga nisbatan keltirib chiqarildi. Endi elliptik egri chiziqning kriptografiyada keng qo‘llaniladigan
y x3 ax b
tenglamasi uchun rasional nuqtalarini qo‘shish formulalari keltirib o‘tiladi:
u ((yx11 xy22))22 x1 x2, (9)
vy1 y1 y2 (x1 u). x1 x2
bu yerda, x1 x2.
Agar x1 x2 bo‘lsa, u holda
2
u 4y12 2x1,
(10)
3x12 a
vy1 (x1 u).
2y1
Oldindan berilgan y 2 x3 ax2 bx c - EECh rasional nuqtalarini topishning samarali usulini aniqlash hozirgi kunda sonlar nazariyasining muammolaridan biri hisoblansada, egri chiziqqa tegishli bitta nuqta topilsa, qolganlari (7), (8) formulalar orqali aniqlanadi.
EECh nuqtalarini qo‘shish jarayonida quyidagi ikkita holat bo‘lishi mumkin:
Biror n –qadamda [n]P= 0E tenglik bajarilishi mumkin;
[2]P, [3]P, [4]P va hokazo [n]P – nuqtalar har xil qiymatga ega bo‘lishi mumkin.
25-ta’rif. Agar barcha mn holatlarda [m]P0E bajarilib, [n]P = 0E bo‘lsa, u holda P – nuqta n – chekli tartibga ega deyiladi.
3.6.3. Maydon ustida berilgan parametrli elliptik egri chiziq nuqtalari gruppasi
3.6.3.1. Parametrli elliptik egri chiziq nuqtalari gruppasi
Oshkora kriptografiyaning an’anaviy elliptik egri chiziq (EECh)li nosimmetrik kriptotizimlaridan qo‘shimcha maxfiylikka ega bo‘lgan yangi kriptotizimlarga o‘tish dolzarb muammo hisoblanadi.
Quyida an’anaviy EEChlar asosida shakllantirilgan parametrli algebraik gruppa haqida so‘z boradi [55].
Ma’lumki, foydalanish uchun qulay bo‘lgan EECh tenglamalarining ko‘pchiligi Veyershtrass [56-58] tenglamasini umumlashgan shaklining xususiy hollaridir. Shu jumladan, GOST R 34.10-2001ga asos qilib olingan Veyershtrass tenglamasi umumlashgan shaklining xususiy holi
y02 x03+ax0+b
ko‘rinishga ega bo‘lib, o‘zgaruvchilarni va koeffisiyentlarni almashtirish, parametr R ni kiritish orqali quyidagi modulyar ko‘rinishga keltiriladi:
y\2 x\3+ax+B (mod p),
bu yerda:
B ≡ (a+b) R-1(mod p), y\2 ≡ (y02-1) R-1(mod p), y ≡ (y0-1) R-1(mod p), y ≡ ( x\3+ax+B)\0.5(mod p), y - ≡ - (y+2 R-1) (mod p), x\3 ≡ (x03-1) R-1(mod p), x ≡ (x0-1) R-1 (mod p), y0 , x0 ,y, y -, x - o‘zgaruvchilar, a, B - butun sonli koeffisiyentlar,
R – parametr, 0 shartlarini qanoatlantiradi.
Q1=(x1, y1) va Q2=(x2, y2) nuqtalar ustida parametrli qo‘shish amali “+\ “ bilan belgilanadi va Q3 = Q1 + \Q2 ko‘rinishida ifodalanadi. (x1, y1) va (x2, y2) nuqtalar ustida parametrli qo‘shish quyidagi taqqoslamalar asosida amalga oshiriladi:
1) x1≠ x2 hol uchun Q3=(x3, y3):
x3 ≡ (L2-3)R-1-x1- x2) (mod p), (11) y3≡ L(x1- x3)+ y1- (mod p), (11’) bu yerda:
L ≡(y2- y1) (x2- x1) -1 (mod p);
x1=x2, y1= y2≠0 hol uchun Q3=(x3, y3):
x3 ≡ (L2-3)R-1-2x1 (mod p), (12)
y3 ≡ L(x1- x3) + y1- (mod p), (12’)
bu yerda: L ≡(3(R x1\2+1)+a)(2(R y1+1))-1 (mod p);
x1=x2, y2= y1 - hol uchun Q1=(x1, x2) va Q2=(x2, y1 -) nuqtalarning parametrli yig‘indisi nollik (cheksizlikdagi) nuqta 0E ga teng.
Nollik nuqta uchun Q+\ 0E = 0E +\Q = Q (13)
tenglik o‘rinlidir.
EECh nuqtasini o‘ziga o‘zini d marta parametrli qo‘shish natijasi nuqtani skalyar son d ga ko‘paytirish amalini beradi. EECh nuqtasini skalyar son d ga ko‘paytirish amali “ *\ “ belgisi bilan ifodalanadi.
Shuni ta’kidlash kerakki, Veyershtrass [56-58] umumiy ko‘rinishdagi tenglamasining qolgan barcha xususiy hollari bo‘lgan EECh tenglamalari uchun ham yuqorida keltirilgan EECh nuqtalari ustida parametrli qo‘shish +\ va EECh nuqtasini skalyar son d ga ko‘paytirish amali *\ ni aniqlash hyech qanday qiyinchilik tug‘dirmaydi.
EECh barcha nuqtalari ustida parametr R≥1 bilan qo‘shish amali chekli additiv kommutativ gruppani tashkil etadi.
3.26-ta’rif. PE(Fn) = {parametrli EECh nuqtalari} U{0E}, ya’ni parametrli EECh barcha nuqtalari to‘plami va nollik nuqta, parametr 0< RFn bo‘lsa, +\ – PE(Fn) ustida aniqlangan parametrli qo‘shish amali bo‘lsa, (PE(Fn); +\) – juftlik parametrli EECh nuqtalari gruppasi deb ataladi.
An’anaviy EECh va parametrli EECh nuqtalari to‘plamlari o‘zaro izomorfligi tufayli additiv kommutativ gruppaning barcha aksiomalari parametrli EECh nuqtalari gruppasini ham qanoatlantiradi.
Bu holat parametrli EECh nuqtalari gruppasi asosida qo‘shimcha maxfiylikka ega bo‘lgan bir tomonlama funksiyalar asosida mavjud kriptotizimlarga analog bo‘lgan yangi kriptotizimlarni va yangi kriptotahlillash usullarini yaratishga yo‘l ochadi.
Do'stlaringiz bilan baham: |