El-Gamal shifrlash algoritmi

Ma’ruza: El-Gamal ochiq kalitli shifrlash algoritmi

1. 
   El-Gamal shifrlash algoritmi
   
2. 
   El-Gamal shifrlash algorimi xavfsizligi va unga boʼladigan xujumlar
   

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.
Калит генератори. 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 М ochiq matn va ochiq kalitlar juftiga egi foydalanuvchi quyidagi ketma – ketlikdagi amallarni bajaradi:
р 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.
  

Шифрматнни дешифрлаш. 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:
А 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. Бу ерда (p,g,y) – ochiq kalitlar jufti va a maxfiy kalit.
Shifrlash. Bu bosqich А tomonning ochiq kalitlariga esa B tomondan amalga oshiriladi. Ochiq maʼlumot sifatida M=CDEF (2,3,4,5 – alfavitdani oʼrni) olinib, ЭКУБ( , ) =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  А tomonga yuboriladi.
Deshifrlash. Bu jarayon maxfiy kalitga ega boʼlgan А 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.
El-Gamal shifrlash algorimi xavfsizligi va unga boʼladigan xujumlar. Ushbu algoritmga qaratilgan hujumlarni aktiv va passiv turlarga ajratish mumkin.
Passiv xujum. El-Gamal shifrlash algorimida berilgan quyidagi ketma-ketlikdan x nomalumni topishga asoslangan.  ва  . Diffi-Helman algoritmining murakkabligi ham aynan shunga asoslangan.
Bobning mahfiy kalitini qidirish asosida x ni qayta tiklash.

Аgar parametrlar toʼgʼri tanlansa, faqatgina hisoblash murakkabligiga bogʼliq boʼlib qoladi. Ushbu qadam muvofaqiyatli amalga oshirilsa, x ni quyidagi formula orqali hisoblashi mumkin: 
Boshqa tarafdan, Bobning d mahfiy elementi asosida Аlisaning quyidagi tasodifiy i elementini hisoblashi mumkin:

Bu asosida x ni quyidagi formula orqali hisoblashi mumkin:

Har ikki holatda ham hujumchi chekli guruhda diskret logarifm muammosini yechishi lozim. Bundan tashqari uning xavfsizligini oshirish uchun Elleptik egri chiziqlar va Indeksni hisoblash usullarini kiritish hamda p ning oʼlchami kamida 1024 bit boʼlishi lozim.
Aktiv hujum. Аsimmetirik kriptotizimlarda ochiq kalitlarning egasi maʼlum va ochiq tarmoqda uzatiladi. Hujumchi oʼrtadagi odam hujumini qoʼllagan holda Аlisadan kelgan xabarni oʼzgartirib Bobga va aksincha joʼnatish orqali mahfiy kalitni olishga harakat qilishi mumkin.
Uning boshqa zaifligi sifatida ikki tomon oʼrtasidagi mahfiy element i takror foydalanilmaydi. Tasavur qilaylik Аlisa  va  xabarlarni shifrlash uchun i qiymatdan foydalangan. Ushbu holatda ikki niqob kalit  bir hil boʼlishi lozim. Аlisa ikkita shifrmalumotni uzatadi: ( ) ва ( ). Аgar hujumchi birinchi xabarni tahmin qila olsa, unda niqob kalitni quyidagicha hisoblaydi:

Bu asosida  xabarlarni quyidagicha hisoblaydi:
 .
Boshqa xabarlar ham i qiymat yordamida shifrlanadi va shu yoʼl asosida qayta tiklanadi.