Texnologiyalari universiteti kriptografiyaning matematik asoslari

Elliptik egri chiziqning nuqtalarini qo‘shish formulalari uning geometrik ma’nosidan kelib chiqqan holda keltirib chiqariladi. Ko‘rib o‘tilganlarga muvofiq, agar Px₁, y₁ va Qx₂, y₂- nuqtalar E -elliptik egri chiziqda yotsa, ya’ni Px₁, y₁,
Qx₂, y₂E 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(x₃ , y₃ ) nuqtada kesib o‘tadi.
3-tasdiq. Agar Px₁, y₁, Qx₂, y₂E nuqtalar rasional koordinatali bo‘lsa,
u holda R(x₃ , y₃ ) nuqta koordinatalari ham rasional bo‘ladi.
Isboti. Px₁, y₁ , Qx₂ , y₂ 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(x₁, y₁ ) va Q(x₂ , y₂ ) nuqtalarning koordinatalari orqali ifodalanadi. P(x₁, y₁ ), Q(x₂ , y₂ ) -nuqtalar
ykxd chiziqqa tegishli. Bundan esa:
y₁ kx₁ d,
y₂  kx₂ d, y1 y2  k(x1 x2 )ва k  y_x1^{1 }_x^y2² _, 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 y² x³ ax² bxc,
elliptik egri chiziqning tenglamasiga qo‘yiladi, yani
(kx d)²  x³  ax² bx c,
x³ (a k ² )x² (b 2kd)x c d ²  0,
u holda uchinchi tartibli tenglama uchun Viyet teoremasiga ko‘ra:
x₁  x₂  x₃  k ² a
tenglik o‘rinli bo‘lib, bu oxirgi tenglikda x₁, x₂ - rasional sonlar bo‘lgani uchun, x₃ ham rasional son bo‘ladi. Xuddi shuningdek,
y₃  kx₃  d
ifodaga ko‘ra y₃ - 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 ²  a  x₁  x₂ , v kud (k(ux₁ )  y₁ )
chunki u _ x₃ , v _{ }y₃. Bu formulada k -koeffisiyenti qiymatining
o‘rniga y^{1  y2} qo‘yilsa, quyidagi tengliklar hosil bo‘ladi:
x1  x2 v y^{1 y2} (ux₁) y₁, x1 x2
u ((yx¹₁ ^x^y₂²)⁾₂² (ax₁ x₂) (7)
Bu yerda, x₁  x₂ .
Agar x₁  x₂ bo‘lsa, u holda kesuvchi to‘g‘ri chiziq o‘rniga urinma o‘tkazilib, quyidagi formulalar keltirib chiqariladi:
2
u2x₁ a 4y1₂ ,
vy₁  ^{3x12  2ax1 b} (u_x₁). (8) 2y₁
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  x³  ax  b
tenglamasi uchun rasional nuqtalarini qo‘shish formulalari keltirib o‘tiladi:
u ((yx11 xy22))₂2 x1 x2, (9)
vy₁  y^{1 y2} (x₁ u). x1 x2
bu yerda, x₁  x₂.
Agar x₁  x₂ bo‘lsa, u holda
2
u 4y₁₂  2x₁,
(10)
3x¹² a
vy₁  (x₁ u).
2y₁
Oldindan berilgan y ² _ x³ _ ax² _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:

1. 
   Biror n –qadamda [n]P= 0_E tenglik bajarilishi mumkin;
   
2. 
   [2]P, [3]P, [4]P va hokazo [n]P – nuqtalar har xil qiymatga ega bo‘lishi mumkin.
   
3. 
   25-ta’rif. Agar barcha mn holatlarda [m]P0_E bajarilib, [n]P = 0_E 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 ≡ (y₀²-1) R^-1(mod p), y ≡ (y₀-1) R^-1(mod p), y ≡ ( x^\3+ax+B)^\0.5(mod p), y ^- ≡ - (y+2 R^-1) (mod p), x^\3 ≡ (x₀³-1) R^-1(mod p), x ≡ (x₀-1) R^-1 (mod p), y₀ , x₀ ,y, y ^-, x - o‘zgaruvchilar, a, B - butun sonli koeffisiyentlar,
R – parametr, 0 shartlarini qanoatlantiradi.
Q₁₌(x₁, y₁) va Q₂=(x₂, y₂) nuqtalar ustida parametrli qo‘shish amali “+^\ “ bilan belgilanadi va Q₃ = Q₁ + ^\Q₂ ko‘rinishida ifodalanadi. (x₁, y₁) va (x₂, y₂) nuqtalar ustida parametrli qo‘shish quyidagi taqqoslamalar asosida amalga oshiriladi:
1) x₁≠ x₂ hol uchun Q₃=(x₃, y₃):
x₃ ≡ (L²-3)R^-1-x₁- x₂) (mod p), (11) y₃≡ L(x₁- x₃)+ y₁^- (mod p), (11’) bu yerda:
L ≡(y₂- y₁) (x₂- x₁) ^-1 (mod p);

2. 
   x₁=x₂, y₁= y₂≠0 hol uchun Q₃=(x₃, y₃):
   

x₃ ≡ (L²-3)R^-1-2x₁ (mod p), (12)
y₃ ≡ L(x₁- x₃) + y₁^- (mod p), (12’)
bu yerda: L ≡(3(R x₁^\2+1)+a)(2(R y₁+1))^-1 (mod p);

2. 
   x₁=x₂, y₂= y₁ ^- hol uchun Q₁=(x₁, x₂) va Q₂=(x₂, y₁ ^-) nuqtalarning parametrli yig‘indisi nollik (cheksizlikdagi) nuqta 0_E ga teng.
   

Nollik nuqta uchun Q+^\ 0_E = 0_E +^\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(F_n) = {parametrli EECh nuqtalari} U{0_E}, ya’ni parametrli EECh barcha nuqtalari to‘plami va nollik nuqta, parametr 0< RF_n bo‘lsa, +^\ – PE(F_n) ustida aniqlangan parametrli qo‘shish amali bo‘lsa, (PE(F_n); +^\) – 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.