Texnologiyalari universiteti kriptografiyaning matematik asoslari

5.1-teorema. Agar n = pq, p  q- tub sonlar va (x, p) _1, ( ,x q) _1 bo‘lsa, u holda
x^{( )n} 1modn.
Isboti. Agar (x, p) _1, ( ,x q) _1 munosabatlar o‘rinli bo‘lsa, u holda
x^p1 1mod p x^q1 1modq,
bo‘lib, y _ x^{( )n} _ x^{(p 1)(q 1)} modul p bo‘ycha ham, modul q bo‘yicha ham 1 ga teng bo‘ladi. Haqiqatan ham:
y  xn mod p  xp1q1 mod p [xp1 modn]q1 modn 1q1 modn 1
yoki
y  xn mod p  xp1q1 mod p [xq1 modn]p1 modn 1p1 modn 1.
Bundan esa, (y – 1) ning p va q sonlariga qoldiqsiz bo‘linishi kelib chiqadi hamda y=1 mod pq tenglik o‘rinli bo‘ladi.
5.2-teorema. Agar n = pq, p  q – tub sonlar va ( , ( ))e _ n _1 bo‘lsa, u holda ushbu
E_en, : x  x^e modn
akslantirish Z_n =0;1;2;...;n_1-chekli maydonda o‘zaro bir qiymatli akslantirish bo‘ladi.
Isboti. Agar ( , ( ))e _ n _1 bo‘lsa, u holda shunday d - haqiqiy son mavjud bo‘ladiki, uning uchun
ed 1mod( )n ,
munosabat o‘rinli bo‘ladi. Bundan esa ushbu munosabat
(xe d)  xed  x1K n( )  x(modn)
EKUB(x n, ) _1 ifodani qanoatlantiruvchi barcha x lar uchun bajariladi. Agar x = py bo‘lsa, bu yerda (y q, ) _1, u holda

16. 
    x| 1K n( ) _ x.
    

Bu yerda x soni q ga qoldiqsiz bo‘linmaganligidan
x1K n( ) _ x _ x(xq1)K p( 1) _1^
kelib chiqadi.
Fermaning kichik teoremasiga ko‘ra x^q1 _1modq va natijada, kvadrat qavs ichidagi ifoda modul p bo‘yicha ham va modul q bo‘yicha ham 0 ga teng bo‘lib, bundan ushbu
x1K n( )  x  0 modn
tenglikning o‘rinliligi kelib chiqadi.
Xuddi shu kabi, agar x = qy bo‘lsa, bu yerda ( y, p) _1, u holda

16. 
    x| 1K n( ) _ x.
    

Bu yerda x soni q ga qoldiqsiz bo‘linmaganligidan
x1K n( ) _ x _ x(xp1)K q( 1) _1
 
kelib chiqadi.
Fermaning kichik teoremasiga ko‘ra x^p1 1modp va natijada, kvadrat qavs ichidagi ifoda modul p bo‘yicha ham va modul q bo‘yicha ham 0 ga teng bo‘lib, bundan ushbu
x1K n( )  x  0 modn
tenglikning o‘rinliligi kelib chiqadi.
Shunday qilib, keltirilgan teoremalarga ko‘ra
C^{d j} modn  M ^{ejd j} modn  M ^K(n)1 modn [(M^(n))^K modnM modn]modn 
[1^K modnM modn]modn  M modn  M
chunki, M  n .
Ochiq va maxfiy kalitlarning generasiyasi chog‘ida
e_id_i 1modntenglikni qanoatlantiruvchi d _i - sonini n- soni ma’lum bo‘lganda Yevklid algoritmi bo‘yicha topiladi. Ammo _n- soni foydalanuvchilarga noma’lum bo‘lganda d_i - sonidan tashqari n-soni ham maxfiy bo‘lib, n - sonini aniqlash uchun n–sonini tub ko‘paytuvchilarga ajratib, r va q sonlarini topish talab etilib, so‘ngra n (p1)(q1) hisoblanadi. n–soni yetarli katta bo‘lganda uni tub ko‘paytuvchilarga ajratib, r va q sonlarini topishning rasional usuli bugungi kunda mavjud emas. Adabiyotlar ro‘yxatida keltirilgan [60] da yetarli katta natural sonlarni eksponensial va subeksponensial murakkabliklarga ajratib, ularni tub ko‘paytuvchilarga ajratishning ba’zi usullari keltirilgan.
Keyingi paragrafda diskret logarifmlash masalasi yechimini xarakteristikasi yetarli katta bo‘lgan chekli maydonda amalga oshirishning murakkabligiga asoslangan El Gamal algoritmi keltirilgan.

5.4. Chekli maydonlarda diskret logarifmlash masalasining yechimi murakkabligiga asoslangan nosimmetrik shifrlar

El Gamal algoritmida kriptotizimning har bir i -foydalanuvchisiga tub modul r va hosil qiluvchi (generator) g ma’lum hisoblanadi va i -foydalanuvchi uchun shaxsiy kalitni ifodalovchi x_i -son bo‘yicha hisoblanadigan y_i a^xi modp- ochiq kalit generasiya qilinadi va u barchaga oshkor etiladi. Agarda mana shu i foydalanuvchi bilan biror boshqa j -foydalanuvchi ochiq ma’lumot M ni shifrmatnga o‘girilgan holda axborot almashuvini amalga oshirmoqchi bo‘lsa, u holda j -foydalanuvchi r sonidan kichik bo‘lgan biror k -sonini tanlab olib y₁ g^k (mod p) va y₂  (M / y^k)(mod p) ,
sonlarini hisoblaydi. So‘ngra j -foydalanuvchi (y₁;y₂) ma’lumotlarini i foydalanuvchiga jo‘natadi. O‘z navbatida i -foydalanuvchi bu shifrlangan ma’lumotni qabul qilib, quyidagicha
(y₁^x  y₂)mod p  M
hisoblash bilan ochiq ma’lumotni tiklaydi.
El Gamal kriptoalgoritmiga asoslangan kriptotizimning har bir i foydalanuvchisi uchun y_i ,x_i  - kalitlar juftligi quyidagicha yaratilishi ham mumkin: biror p_i -tub soni va g_i  p_i - tengsizlikni qanoatlantiruvchi g_i (foydalanuvchilar guruhi uchun umumiy p va g _ p tengsizlikni qanoatlantiruvchi g ) sonlari tanlanadi. Ushbu x_i  p_i tengsizlikni qanoatlantiruvchi maxfiy bo‘lgan x_i - soni bo‘yicha ochiq deb e’lon qilinadigan y_i -soni ushbu formula y_i g_i^xi (mod p_i ) (foydalanuvchilar guruhi uchun x_i  p hamda y_i  g ^xi mod p ) orqali hisoblanadi. Shunday qilib, El Gamal kritotizimida
p_i ,g_i , y_i  – uchlik (foydalanuvchilar guruhi uchun p va g umumiy bo‘lib, p,g, y_i ) – uchlik ) ochiq kalit, x_i - esa maxfiy (shaxsiy) kalit deb olinadi.
Shundan so‘ng i -foydalanuvchidan j - foydalanuvchiga shifrlangan ma’lumotni jo‘natish quyidagicha amalga oshiriladi:

1.