Imzoni generatsiya qilish algoritmi qadamlari

2.3. ГОСТ Р 34.10-2001 elektron raqamli imzo algoritmi

Imzoni generatsiya qilish algoritmi. Boshlang‘ich ma’lumotlar: ma’lumot, berilgan (elliptik chiziqqa aloqador) parametrlar va imzo maxfiy kaliti. Ushbu algoritmda Elliptik egri chiziq tenglamasi p > 2²⁵⁵ shartni qanoatlantiruvchi tub xarakteristikali maydonda deb qaraldi. Natija, imzo .
Imzoni generatsiya qilish algoritmi qadamlari:

1. 
   1 k n-1 intervaldan ixtiyoriy k soni tanlansin, bu yerda nuqta tartibi 2²⁵⁴ < n < 2²⁵⁶ shartni qanoatlantiruvchi son.
   
2. 
   (x₁,y₁)= [k]G hisoblansin, ya’ni tanlangan egri chiziqqa tegishli G nuqtani k marta qo‘shilsin.
   
3. 
   r=x₁ mod n hisoblansin. Agar r=0 bo‘lsa, 1-qadamga qaytilsin va boshqa k soni tanlansin.
   
4. 
   M ma’lumotning xesh funksiyasi hisoblansin, ya’ni e=H(M). Agar H(M) mod n=0 bo‘lsa, u holda H(M) mod n=1 deb olinsin.
   
5. 
   0< d intervaldan olingan d maxfiy kalit asosida s=(dr+ke) mod n hisoblab topilsin.
   
6. 
   Agar s=0 bo‘lsa, 1-qadamga qaytilsin va boshqa k soni tanlansin.
   
7. 
   Hosil bo‘lgan (r,s) sonlar juftligi M ma’lumotga qo‘yilgan imzo hisoblanadi.
   

Imzoni tekshirish algoritmi. Boshlang‘ich ma’lumotlar ma’lumot, berilgan (elliptik chiziqqa aloqador) parametrlar, imzoni tekshirish kaliti va ma’lumot imzosi-(r,s). Natija: imzo haqiqiyligi yoki qalbakiligi haqidagi tasdiq .
Imzoni tekshirish algoritmi qadamlari:

1. 
   Agar 1 r, s n-1 bajarilmasa, u holda imzo qalbaki va tekshirishni shu yerda to‘xtatish mumkin.
   
2. 
   e= H(M) hisoblansin.
   
3. 
   w= H(M) ^(n-2)mod n hisoblansin.
   
4. 
   u₁ = s w mod q hisoblansin.
   
5. 
   u₂ = (n-r) w mod n hisoblansin.
   
6. 
   X=[ u₁] G+[ u₂] Q=(x₁,y₁) hisoblansin.
   
7. 
   Агар x₁ mod n = r bo‘lsa, imzo haqiqiy, aks holda imzo qalbaki va algoritm to‘xtatiladi.
   

ГОСТ Р 34.10-2001 imzo algoritmining to‘g‘riligi. Isbot qilishimiz kerakki, keltirilgan algoritm asosida qo‘yilgan ixtiyoriy imzo shu algoritm bilan tekshirilganda har doim haqiqiy.
Imzoni shakllantirish jarayoniga muvofiq r va s parametrlar n butun songa bo‘lishdagi qoldiq sifatida olinganligi sababli n-1 qiymatdan oshib ketmaydi. Imzoni generatsiya qilish algoritmidagi 3 va 6-qadamlarga ko‘ra r, s 0 shart ham har doim bajariladi. Shunga ko‘ra, imzoni generatsiya qilish algoritmidan olingan r va s parametrlar imzoni tekshirish algoritmining 1-qadamidagi shartni qanoatlantiradi.
Imzoni generatsiya qilishning 5-qadamiga ko‘ra, s = ke+dr (mod n) tenglik bajariladi. Bundan (dr+ke –s)/n =t yoki k=(nt+s-dr)e^-1 ekanligi kelib chiqadi. Oxirgi keltirilgan uchta tenglik ixtiyoriy butun manfiy bo‘lmagan t lar uchun ekvivalent va shu bilan birga t=d da ham bajariladi. Agar t=d bo‘lsa, oxirgi tenglik k=s e^-1 + (n-r)de^-1 ko‘rinishga keladi. Xesh-funksiya qiymati 0<eoraliqda yotadi va n ning tubligidan ЭКУБ(e,n)=1 ekani kelib chiqadi. U holda Eylera – Ferma teoremasiga ko‘ra, e^-1 bo‘ladi. Ushbu taqqoslamadan foydalanib, k parametrni quyidagicha ifodalash mumkin k=s e^-1 + (n-r)de^-1 = s e^n-2 mod n + (n-r)e^n-2 mod n d . Bu yerdan e^n-2 mod n=w shartga ko‘ra k=s w + (n-r)wd ni olish mumkin.
G nuqta n tartibga ega, ya’ni [n] G=E va ixtiyoriy klarda [k] G E bo‘ladi. Ikkinchi tomondan esa:
[k] G=[ s w + (n-r)wd] G=[sw] G+ [(n-r)w] [d] G= [sw] G+ [(n-r)w]Q =
=[u₁]G+[u₂]Q = X.
Demak, imzoni generatsiya qilishdagi 6-qadamdan olingan X nuqta imzoni generatsiya qilish algoritmidan olingan [k] G nuqtaga mos keladi. Imzoni generatsiya qilish algoritmining 3-qadamiga ko‘ra, X nuqtaning birinchi koordinatasi x₁ bo‘lib, uning mod n bo‘yicha qoldig‘i r ga teng, ya’ni x₁ mod n= r. Natijada algoritm korrektligi kelib chiqadi.
Misol: maydonda tenglamaga nisbatan parametrlar tanlansin. p = 8443 ga teng bo‘lsin. Boshlang‘ich nuqta sifatida P(141; 65) nuqtani olamiz. Shularga asosan ushbu elliptik egri chiziqning shu nuqtadagi tartibi n=8297 teng va u tubdir. Umuman olganda ГОСТ Р 34.10-2001 raqamli imzo algoritmida EC DSA -2000 raqamli imzo algoritmidan farqli o‘laroq, elliptik egri chiziqda olingan bazaviy G -nuqtaning tartibi tub bo‘lishi shart emas. Faqat tanlangan р sonning tub bo‘lishining o‘zi yetarli. Ko‘rilayotgan misolda elliptik egri chiziqqa tegishli bo‘lgan bazaviy nuqtaning n -tartibini tub bo‘lganligini esa tasodifiy holat deb qarash mumkin. Quyida imzo algoritmi shartiga ko‘ra ochiq va maxfiy kalitlar tanlanadi.
Imzo qo‘yish kaliti (mahfiy kalit) sifatida – intervaldagi biror soni olinadi.
Imzoni tekshirish kaliti (ochiq kalit) – elliptik egri chiziqdagi nuqta, ya’ni nuqta hisoblanadi.
Bundan tashqari raqamli imzo algoritmida - xesh-funksiyadan ham foydalaniladi. Ushbu misolda xesh qiymat sifatida h=459 qiymat tanlangan.