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

7.1. DSA (Digital Signature Algorithm) elеktron raqamli imzo algoritmi

Bu algoritm AQSHning standart algoritmi hisoblanadi. Bu algoritmni 1991 yili AQSHning NIST (National Institut Standart and Tekhnology) kompaniyasi U.S.Patent 5231668 patenti bilan ishlab chiqqan. Aslida NSA yaratuvchisi hisoblanadi. Ushbu algoritm ma‘lumotni shifrlash uchun emas, balki elektron raqamli imzo yaratishda qo’llaniladi. Ushbu algoritm SHA-1 xesh funksiyasi bilan birgalikda DSS(Digital Signature Standard) ning qismi hisoblanadi. DSS versiyasida SHA-1 xesh funksiyasi 160 bitli uzunlik taklif etilgan. Lekin hozirgi kunda SHA-1 algoritmi yetarlicha mustahkam emas. Ushbu versiyada foydalanilayotgan tub sonlarning uzunliklari quyidagi L va N juftliklarida keltirilgan:
L = 1024, N = 160,
L = 2048, N = 224, L =2048, N = 256, L =3072, N =256.
Albatta bular bilan birgalikda SHA-2 xesh funksiyasi ham taklif etilgan. Yuqori tashkilotlar bulardan birini tanlashi lozim, lekin ular ixtiyoriy tanlashlari mumkin. Tizimni loyihalashda ixtiyoriy xesh- funksiyani tanlasa bo’ladi. DSA algoritmining mustahkamligi xesh- funksiyaning mustahkamligi va L,N juftliklarining mustahkamligini ta‘minlab bermaydi. Avvalari L ning uzunligi 1024 bit bo’lgan bo’lsa, hozirgi kunda tizimlarning mustahkamligi uchun 2011 yildan 2030 yilgacha L ning uzunligi 2048-3072 bitgacha taklif etilmoqda.
DSA algoritmi:

1. 
   p – katta tub son tanlanadi. Uzunligi 512-1024 bitgacha va uzunligi 64 ga karrali.
   
2. 
   q-tub son tanlanadi, uzunligi 160 bit va (p-1) ning bo’luvchisi, ya‘ni (p-1)/q € N.
   
3. 
   Quyidagi tengsizlikni qanoatlantiruvchi h-natural son tanlanadi:
   

h < q, h^p-1/q mod p > 1.

4. 
   g-hisoblanadi: g = h^(p-1)/q mod p.
   
5. 
   Uzunligi 160 bit bo’lgan q dan kichik ixtiyoriy natural son x tanlanadi va u yopiq kalit hisoblanadi.
   
6. 
   Ochiq kalit quyidagi formula yordamida hisoblanadi: y = g^x mod p, uning uzunligi 512-1024 bitgacha.
   

(p, q, g, y) – ochiq parametrlar hisoblanadi, faqatgina x yopiq parametr hisoblanadi. (p, q, g) barcha foydalanuvchi guruhlar uchun ochiq bo’lishi mumkin, x va y esa yopiq bo’ladi. Ma‘lumotni imzolashda maxfiy son x va k dan foydalaniladi. Bu yerda k ixtiyoriy tanlanadi. Imzo qo’yish:

7. 
   k < q - tasodifiy son tanlanadi.
   
8. 
   a=(g^kmodp)modq – birinchi imzo
   
9. 
   b=(k^-1(H(m)+x·a))modq – ikkinchi imzo, bu yerda H(m) - xesh qiymat.
   
10. 
    (a,b) sonlar juftligi imzo hisoblanadi. M, (a,b) - ikkinchi tomonga yuboriladi.