Guruh talbasi Maxsudov Azamxon Yunusxo’ja o’g’li

El-gamal kriptografik algoritmi.

El-Gamal kriptografik tizimi uchta jarayonni o’z ichiga oladi:

1. 
   kalitlarni hosil qilish
   
2. 
   ma’lumotni shifrlash 3 ma’lumotni deshifrlash
   

Kalitlarni hosil qilish quyidagi qadamlardan iborat

1. 
   Katta uzunlikdagi q tub sonini hosil qilinadi
   
2. 
   ^{Modul q dan kichik bo’lgan tasodifiy primitiv} a ^{butun son tanlab olinadi}
   

3. ^{1  x  p 1} shartni qanoatlantiruvchi maxfiy kalit, tasodifiy butun x sonni hosil qilinadi.

4. 
   y  a^x mod q
   

hisoblashni amalga oshiriladi

5. 
   Shundan so’ng ^{{q, a, y}} ochiq kalit sifatida, x maxfiy kalit sifatida olinadi,
   

Ma’lumotni shifrlash quyidagi qadamlardan iborat

1. M ochiq ma’lumot q dan kichik bo’lgan bloklarga ajratiladi

2. 
   1  k  q 1 shartni qanoatlantiruvchi va q bilan o’zaro tub bo’lgan k soni tasodifiy tanlab olinadi.
   

3. 
   C₁
   

 a^k mod q
va C₂
 M * y^k mod q

shifrmatnlar hisoblanadi.

Ma’lumotni deshifrlash quyidagi qadamlardan iborat

1. 
   2
   K

 (C₁
)^x mod q qiymat hisoblanadi.

2. M

 (C * K ^1) mod q
hisoblanib, M ochiq matn olinadi.

El-gamal--AMALIY
Kalit generatsiya qilish
q=97; a=2; x=12; y=a^x modq=2¹² mod97=22; ochiq kalit (97,2,22);
yopiq kalit 12;
shifrlash
M=8; K=3;
^C1^{=akmodq=23mod97=8; C}2^{=M*yk modq=8*223 mod97=18; C}1^{=8, C}2^=18;
Deshifrlash
^K=C1^{q-x-1 modq=897-12-1 mod97=75 M=C}2^{*K-1 modq= 18*22 mod97=8;}
9-amaliy ish
Mavzu: Diskret logarifmlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish.
Diskret logarifmlash muammosini bartaraf etuvchi algoritmlar
Diskret logarifmlash muammosini izohlang.
Diskret logarifmlashga qaratilgan qanday hujumlar mavjud JAVOBLAR
1
Diskret logarifmlash algoritmi: Qadam. Quyidagi son hisoblansin
H:= [p1/2] +1

Qadam. Quyidagi son hisoblansin H aH (mod p)
3- Qadam. u, 1 u H sonli qiymatlari uchun Cu (mod p) jadval tuzing. Bu qiymatlarni tartiblab chiqing. 4 – Qadam. Keyingi jadval esa b*a v (mod p) , 0 H qiymatlar uchun tuzilib tartiblansin.

5. 
   Qadam. Birinchi va ikkinchi jadvalda teng chiqqan u, v elementlar olinsin. 6- Qadam. Javob sifatida
   

x H*u – v (mod p-1) olinsin.
Amaliy qism Misol 1. Quyidagi
3x 15 (mod 17) ifodadan x- ni toping.
Yechish: Bevosita tekshirib ko’rish mumkinki, x= 6 bu tenglikni qanoatlantiradi . Haqiqatan 36 = 729; 729 = 42*17 + 15 .
Shuni ta’kidlash kerakki bizni faqat butun yechimlar qiziqtiradi. Shuning uchun ham (1) ifodadan butun x-ni topish masalasi murakkab hisoblanadi.
Bu misolni yechish jarayoni yuqoridagi algoritm orqali quyidagicha amalga oshiriladi.
qadam. H := [ p1/2] +1 , H= 5.
qadam. C aH (mod p), C = 35(mod 17) =5.
qadam. 5u (mod 17) , 1 u 5 jadval qiymatlarini hisoblaymiz: u =1, 5(mod 17) =5
u=2, 25(mod17) = 8 u=3, 125(mod 17)=6 u=4, 625(mod17) = 13 u=5, 3125(mod17) = 6
Bu qiymatlarni tartiblasak: 5,6,8,13 .
qadam. 15*3v(mod 17) , 0 v 5 jadval qiymatlarini hisoblaymiz : v=1, 45(mod 17)=1
v=2, 15*9(mod 17) =16
v=3, 15*27(mod 17)= 14 v=4, 15*81(mod17)=8 v=5, 15*243(mod 17) = 7
Bu qiymatlarni tartiblasak: 7,8,11,14,16.
qadam. Ikkita jadval natijalari ustma-ust tushgan u, v –elementlarni tanlab olamiz. Yani, u =2, v = 4.
qadam. Javob :
x H*u – v (mod p-1)
ya’ni x 5*2 – 4(mod 16) = 6(mod 16) , x = 6.
Misol 2. Berilgan ifodadan x – ni toping 3x 7 (mod 13).
Yechish. Bevosita tekshirib ko’rish mumkinki butun x-soni mavjud emas. Buni ham yuqoridagi algoritm orqali tekshiramiz : a = 3, b =7, p = 13
H := [ p1/2] +1 , H= 4.
C aN (mod p), C = 3 4(mod 13) =3.
3u (mod 13) , 1 u 4 jadval qiymatlarini hisoblaymiz:
u =1, 3(mod 17) =3 u=2, 9(mod17) = 9 u=3, 27(mod 17)= 10 u=4, 81(mod17) = 3
7*3v(mod 13) , 0 v 4 jadval qiymatlarini hisoblaymiz : v= 0, 7 (mod 13) = 7
v=1, 21(mod 17)=4
v=2, 21*3(mod 17) =12
v=3, 7*27(mod 17)= 2
v=4, 7*81(mod17)= 4
Ikkita jadval natijalari ustma-ust tushgan u, v –elementlarni tanlab olamiz. Biroq bunday qiymatlar mavjud emas ekan.
Javob butun yechim yo’q degan xulosaga kelamiz.
2
Diskret logarifmlash muammosini bartaraf etuvchi ( Delpi, Java, C++ va C# dasturlash tizimlaridan biridan foydalangan holda) dasturiy vosita ishlab chiqilsin.
Har bir talaba tartib nomeridagi diskret logarifmlash muammosini bartaraf variantlar kesmida
№ X=?
3^( x)≡26 mod 39 7^( x)≡18 mod 41 5^( x)≡11 mod 39 8^( x)≡19 mod 43
16^( x)≡14 mod 53
11^( x)≡24 mod 37 7^( x)≡16 mod 37 3^( x)≡26 mod 53 7^( x)≡11 mod 19 8^( x)≡11 mod 29 13^( x)≡7 mod 43 9^( x)≡19 mod 53 15^( x)≡5 mod 37 7^( x)≡29 mod 37 7^( x)≡12 mod 17 11^( x)≡13 mod 23
13^( x)≡35 mod 43 9^( x)≡41 mod 53 10^( x)≡36 mod 41
15^( x)≡32 mod 37
18^( x)≡14 mod 23
10^( x)≡13 mod 29 9^( x)≡22 mod 37