O’zbekiston milliy universiteti m. Aripov, A. S. Matyakubov axborotlarni himoyalash usullari toshkent

5.6. ElGamal shifrlash algoritmi

Bu sxema 1984 yilda misrlik olim Taher El Gamal tomonidan taklif etilgan. ElGamal algoritmi shifrlash va raqamli imzo qo’yishda foydalaniladi. Algoritm xavfsizligi chekli maydonda diskret logarifmlarni hisoblash qiyinligiga asoslangan. ElGamal sxemasi AQSh(DSA) va Rossiya (GOSTR34.10-94) elektron raqamli imzo standartlari asosini tashkil etadi.
Shifrlash.

1. 
   p – katta tub son tanlanadi.
   
2. 
   Foydalanuvchilar guruhi uchun umumiy g < p tanlanadi.
   
3. 
   x < p-1 yopiq kalit tanlanadi.
   
4. 
   M < p qilib bloklarga ajratiladi.
   
5. 
   y = g ^x mod p hisoblanadi.
   
6. 
   Tasodifiy sessiys kaliti 1< k < p-1 soni tanlanadi.
   
7. 
   a = g ^k mod p hisoblanadi.
   
8. 
   b = (y ^k *M) mod p hisoblanadi. a va b juftlik shifr tekst deyiladi.
   

Shifrni ochish.
M= modp formula orqali shifr ochiladi.

Misol.
Tub son p=89, yopiq kalit x=3 va M=BBC matn berilgan. Shu matnni Elgamal algoritmidan foydalanib shifrlaymiz.
Shifrlash.

1. 
   Foydalanuvchilar guruhi uchun umumiy g = 11 (g
   
2. 
   x =3 yopiq kalit.
   
3. 
   Matnni ikkilik sanoq tizimida ifodalaymiz:
   

. Demak, BBC matn ikkilik sanoq tizimida quyidagicha
ifodalanadi: M=

4. 
   Matnni 6 bit uzunlikda bloklarga ajratamiz: M₁=010000₂ 16₁₀, M₂=100100₂ 36₁₀, M₃=001001₂ 9₁₀, M₄=000011₂ 3₁₀,
   
5. 
   y = g ^x mod p= 11³mod89=85
   
6. 
   k=7.
   

7.a=g^kmodp =11⁷mod89=87
8.b₁=(y^k*M₁)modp=(85⁷*16)mod89=(81*16)mod89=50
b₂=(y^k*M₂)modp=(85⁷*36)mod89=(81*36)mod89=68
b₃=(y^k*M₃)modp=(85⁷*9)mod89=(81*9)mod89=17
b₄=(y^k*M₄)modp=(85⁷*3)mod89=(81*3)mod89=65
C={a,b₁,b₂,b_3,b₄}={87,50,68,17,65} shifrtekst hosil bo’ladi.