7- amaliy ish Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish Faktorlash muammosini bartaraf etuvchi algoritmlar

11-12 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.