8-amaliy mashg’ulot Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish

C a^N (mod p), C = 3 ⁴(mod 13) =3.

3^u (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

4. 
   7*3^v(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

5. 
   Ikkita jadval natijalari ustma-ust tushgan u, v –elementlarni tanlab olamiz. Biroq bunday qiymatlar mavjud emas ekan.
   
6. 
   Javob butun yechim yo’q degan xulosaga kelamiz.
   

Topshiriq

1. 
   Diskret logarifmlash muammosini bartaraf etuvchi ( Delpi, Java, C++ va C# dasturlash tizimlaridan biridan foydalangan holda) dasturiy vosita ishlab chiqilsin.
   
2. 
   Har bir talaba tartib nomeridagi diskret logarifmlash muammosini bartaraf variantlar kesmida
   

№	X=?

Nazorat savollari

1. 
   Diskret logarifmlash muammosini izohlang.
   
2. 
   Diskret logarifmlashga qaratilgan qanday hujumlar mavjud.
   

11- amaliy mashg’ulot
Mavzu: El-Gamal algoritmida ma’lumotni shifrlovchi dasturiy vositani ishlab chiqish.
Ishdan maqsad: El-Gamal shifrlash algoritmi haqida nazariy va amaliy bilim ko‘nikmalarni shakllantirish.
Nazariy qism
El-Gamal shifrlash algoritmi. Ushbu ochiq kalitli shifrlash algoritmi diskert logarifmlash muammosiga asoslangan boʼlib, kalitlar uzunligi teng boʼlgan holda bardoshligi RSA algoritmi bardoshligiga teng.
Kalit generatori. El-Gamal algoritmida kalit generatori quyidagi bosqichlardan iborat:
p – katta tub son tanlanadi;

• 
  g
  shartni qanoatlantiruvchi g butun son tanlanadi;
  
• 
  maxfiy kalit sifatida a
  shartni qanoatlantiruvchi butun son tanlanadi;
  
• 
  ochiq kalit sifatida hisoblanadi;
  
• 
  ochiq kalitlar jufti (y,g,p) ma’lumotni shifrlovchi tomonlarga yoki ixtiyorov odamlarga tarqatiladi.
  

Ochiq matnni shifrlash. Shifrlanishi kerak boʼlgan M ochiq matn va ochiq kalitlar juftiga egi foydalanuvchi quyidagi ketma – ketlikdagi amallarni bajaradi:
p sonidan kichik boʼlgan va shartni bajaruvchi k - sonini tanlab olinadi;

• 
  k son asosida hisoblanadi;
  
• 
  ochiq matnning har bir belgisi uchun tenglikni hisoblash orqali shifrmatn olinadi;
  
• 
  shifrlash amalga oshirilgach, k son o’chirib tashlanadi va qabul qiluvchiga (r, c) juftlik yuboriladi.
  

Shifrmatnni deshifrlash. Shifrmatn va maxfiy kalitga ega foydalanuvchi quyidagi ketma – ketliklarni bajarish orqali ochiq matnga ega boʼladi:
qabul qilingan maʼlumotlar asosida ochiq matn hisoblanadi.
Ushbu algoritm asosida sodda misol quyida keltirilgan:
A tomon oʼzining maxfiy kaliti asosida ochiq kalit juftini hosil qiladi va uni B tomonda yuboradi. Olingan qiymatlar quyidagilar:
g=3; p=31; a=4; =(3^4)mod31=19. Bu yerda (p,g,y) – ochiq kalitlar jufti va a maxfiy kalit.
Shifrlash. Bu bosqich A tomonning ochiq kalitlariga esa B tomondan amalga oshiriladi. Ochiq maʼlumot sifatida M=CDEF (2,3,4,5 – alfavitdani oʼrni) olinib, EKUB ( , ) =1 shartni qanoatlantiruvchi k=7 tanlandi. Shundan soʼng quyidagilar hisoblanadi:
=(3^7)mod31=17;
C1= =2*(19^7)mod31=14;
C2= =3*(19^7)mod31=21;
C3= =4*(19^7)mod31=28;
C4= =5*(19^7)mod31=4;
Shundan soʼng C1,C2,C3,C4 lardan iborat C va A tomonga yuboriladi.
Deshifrlash. Bu jarayon maxfiy kalitga ega boʼlgan A tomondan amalga oshiriladi va ochiq matn olinadi:
M1=
M2=
M3=
M4=
Bu yerda diskert logarifmlash muammosi sifatida ochiq kalitlar jufti berilganda tenglamadan a maxfiy kalitni topish mumkin, hozirda ushbu muammoning optimal usuli mavjud emas.