Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti nukus filali

El Gamal raqamli imzo algoritmi (EGSA).

Ushbu algoritmning asosiy g'oyasi elektron raqamli imzoni qalbakilashtirishning mumkin emasligi. Bunday maqsadga erishish uchun katta sonni ajratibgina qolmay, murakkabroq hisoblash masalasini echish talab etiladi. Bundan tashqari, El Gamal ishlab chiqaruvchisi RSA algoritmining kamchiliklarini bartaraf etishga va maxfiy kalitni aniqlamasdan ERIni qalbakilashtirish xavfini oldini olishga muvaffaq bo'ldi.

Umumiy va shaxsiy kalitni yaratish uchun P va G ikkita ikkita butun sonni tanlash kerak< P. Отправитель и адресат электронного документа, подписанного ЭЦП, применяют одинаковые большие несекретные числа P (~10 308 = ~2 1024) и G (~10 154 = ~1 512). Первый из них берёт случайное целое число X, 1 < X £ (P - 1), и вычисляет: Y = G X mod P.

Y parametr - bu elektron raqamli imzoning haqiqiyligini tekshirish uchun foydalaniladigan ochiq kalit. Parametr X bu elektron hujjatlarni imzolashda foydalanadigan maxfiy kalit. M xabarini imzolash uchun, jo'natuvchidan h h funktsiyasidan foydalanib, m: m \u003d h (M), 1 soniga o'tish kerak.< m < (P - 1), и сгенерировал случайное целое число К, 1 < K < (P - 1), при этом К и (P - 1) должны быть взаимно простыми. На следующем этапе он рассчитывает значение параметра a по формуле: a = G K mod P. На основе расширенного алгоритма Евклида с помощью секретного ключа Х определяет целое число b: m = X * a + K * b (mod (P - 1)). Пара чисел (a, b) формируют электронную цифровую подпись S: S = (a, b).

M, a va b parametrlarining qiymatlari adresatga uzatiladi, X va K raqamlarining qiymatlari oshkor qilinmaydi. Keyin xabarni qabul qiluvchi m formuladan foydalanib m qiymatini hisoblaydi: m \u003d h (M). Keyinchalik, A \u003d Y a a b mod (P) sonining qiymati hisoblanadi. Agar A \u003d G m mod (P) bo'lsa, M xabari haqiqiy deb hisoblanadi.

M x xabaridagi S imzosi aniq X maxfiy kalitidan foydalanib hisoblanganda, Y ochiq kaliti olingan bo'lsa, oxirgi tenglik haqiqat bo'lishiga qattiq matematik isbot berilishi mumkin.

Shuni yodda tutish kerakki, har bir elektron raqamli imzoni yaratish uchun tasodifiy ravishda aniqlanadigan K sonining yangi qiymati kerak bo'ladi.

https://i2.wp.com/gd.ru/images/articles/9777/elektronnaya-tsifrovaya-podpis_2.jpg

EGSA algoritmi autentifikator (a, b) bilan birgalikda ochiq shaklda xabarni etkazib berishning klassik namunasidir. ElGamal algoritmi va RSA algoritmi o'rtasidagi farq:

1. 
   Xuddi shunday xavfsizlik darajasi bilan EGSA algoritmi RSA algoritmiga qaraganda 25% ga qisqargan butun sonlarda ishlaydi. Bu hisoblash vaqtini o'rtacha 2 baravar kamaytiradi.
   
2. 
   P modulini hisoblash oson, shunchaki uning sonini va sonning (P - 1) katta asosiy omilga ega ekanligiga ishonch hosil qilishingiz kerak.
   
3. 
   EGSA algoritmi maxfiy xabarni bilmasdan yangi xabarlarga elektron raqamli imzolarni kiritishga ruxsat bermaydi.
   
4. 
   EGSA algoritmi yordamida yaratilgan imzo RSA algoritmi yordamida yaratilgan imzoga nisbatan 1,5 baravar katta.