Elektron raqamli imzo algoritmlaridan foydalanish
![I BOB. ELEKTRON RAQAMLI IMZO HAQIDA UMUMIY MA’LUMOT.
AXBOROTLARNI KRIPTOGRAFIK HIMOYALASH USULLARI
1.1 Elektron raqamli imzo tushunchasi
Qabul qilib olingan ma’lumotlarning haqiqiy yoki haqiqiy emasligini aniqlash
masalasini, ya’ni ma’lumotlar autentifikatsiyasi masalasining mohiyati haqida to‘xtalamiz.
Har qanday yozma xat yoki hujjatning oxirida shu hujjatni tuzuvchisi yoki tuzish
uchun javobgar bo‘lgan shaxsning imzosi bo‘lishi tabiiy holdir. Bunday holat odatda quyidagi
ikkita maqsaddan kelib chiqadi. Birinchidan, ma’lumotni olgan tomon o‘zida mavjud imzo
namunasiga olingan ma’lumotdagi imzoni solishtirgan holda shu ma’lumotning haqiqiyligiga
ishonch hosil qiladi. Ikkinchidan, shaxsiy imzo ma’lumot hujjatiga yuridik jihatdan
mualliflikni kafolatlaydi. Bunday kafolat esa savdo–sotiq, ishonchnoma, majburiyat va shu
kabi bitimlarda alohida muhimdir[3].
Hujjatlardagi qo‘yilgan shaxsiy imzolarni soxtalashtirish nisbatan murakkab bo‘lib,
shaxsiy imzolarning mualliflarini hozirgi zamonaviy ilg‘or kriminalistika uslublaridan
foydalanish orqali aniqlash mumkin. Ammo elektron raqamli imzo xususiyatlari bundan farqli
bo‘lib, ikkilik sanoq sistemasi xususiyatlari bilan belgilanadigan xotira registrlari bitlariga
bog‘liq. Xotira bitlarining ma’lum bir ketma-ketligidan iborat bo‘lgan elektron imzoni
ko‘chirib biror joyga qo‘yish yoki o‘zgartirish kompyuterlar asosidagi aloqa tizimlarida
murakkablik tug‘dirmaydi.
Bugungi yuqori darajada rivojlangan butun dunyo sivilizatsiyasida hujjatlar, jumladan
maxfiy hujjatlarning ham, elektron ko‘rinishda ishlatilishi va aloqa tizimlarida uzatilishi keng
qo‘llanilib borilayotganligi elektron hujjatlar va elektron imzolarning haqiqiyligini aniqlash
masalalarining muhimligini keltirib chiqarmoqda.
Ochiq kalitli kriptografik tizimlar qanchalik qulay va kriptobardoshli bo‘lmasin,
autentifikatsiya masalasining to‘la yechilishiga javob bera olmaydi. Shuning uchun
autentifikatsiya uslubi va vositalari kriptografik algoritmlar bilan birgalikda kompleks holda
qo‘llanilishi talab etiladi.
Quyida ikkita (A) va (B) foydalanuvchilarning aloqa munosabatlarida autentifikatsiya
tizimi raqib tomonning o‘z maqsadi yo‘lidagi qanday hatti-harakatlaridan va kriptotizim
foydalanuvchilarining foydalanish protokolini o‘zaro buzilishlardan saqlashi kerakligini
ko‘rsatuvchi holatlar ko‘rib chiqiladi.
Rad etish (renegatstvo).
Foydalanuvchi (A) foydalanuvchi (B) ga haqiqatan ham ma’lumot jo‘natgan bo‘lib,
uzatilgan ma’lumotni rad etishi mumkin.
4](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_4.png?v=1)
![qiymatiga solishtiradi. Agar matnlar bilan xesh qiymatlar bir xil bo‘lsa imzo haqiqiy, aks
holda haqiqiy emas deb qabul qilinadi. Bunday ERI tizimi bir martalik hisoblanadi, chunki
- kalitdan ikkinchi marta foydalanish imkoniyati elektron xujjatlarni qalbakilashtirish
imkoniyatini yaratadi. Bunday holatga chek qo‘yish uchun elektron hujjat almashinuvi
ishonchli uchinchi tomon orqali amalga oshirilishi mumkin: - foydalanuvchi o‘ziga va faqat
ishonchli uchinchi tomonga ma’lum bo‘lgan kalit bilan raqamli imzoni amalga oshirib,
imzolangan elektron hujjatni uchinchi ishonchli tomonga jo‘natadi, uchinchi tomon imzoni
xaqiqiyligini - kalit bilan tekshirib, agar haqiqiy bo‘lsa, - foydalanuvchining o‘ziga va
faqat ishonchli uchinchi tomonga ma’lum bo‘lgan kalit bilan raqamli imzoni amalga
oshirib, imzolangan elektron xujjatni - foydalanuvchiga jo‘natadi. Bunday ERI tizimi
foydalanuvchilar uchun noqulay bo‘lib, ko‘plab kelishmovchiliklarni keltirib chiqaradi.
Amalda, uchinchi turdagi imzoni hisoblash va uni tekshirishning maxsus
algoritmlariga asoslangan raqamli imzo tizimlaridan keng foydalaniladi.
Maxsus ERI algoritmlari raqamli imzoni hisoblash va imzoni tekshirish qismlaridan
iborat. Raqamli imzoni hisoblash qismi imzo qo‘yuvchining mahfiy kaliti va imzolanishi
kerak bo‘lgan hujjatning xesh qiymatiga bog‘liq bo‘ladi. Imzoni tekshirish qismi imzo
egasining ochiq kalitiga va qabul qilib olingan hujjatning xesh qiymatiga bog‘liq holda
amalga oshiriladi.
Maxsus ERI standartlari turkumiga [ 5 ]:
1. Rossiya ERI standarti: ГОСТ Р 34.10-94 va uning elliptik egri chiziqda
takomillashtirilgan varianti ГОСТ Р 34.10-2001;
2. Amerika ERI standarti: DSA va uning elliptik egri chiziqda
takomillashtirilgan varianti ECDSA - 2000;
3. O‘zbekiston Respublikasi standarti: O’zDSt 1092:2005;
algoritmlari misol bo‘la oladi.
Raqamli imzo bitlar ketma-ketligida ifodalangan biror sondan iborat. Shuning uchun
uni boshqa elektron xujjatlarga ko‘chirish yoki o‘zgartirish kiritish katta qiyinchilik
tug‘dirmaydi. Shuning uchun elektron xujjat almashinuvi tizimida ERI ni
qalbakilashtirishning oldini olish chora – tadbirlari – ERI algoritmining elektron xujjatlarni
qalbakilash ti rishga bardoshliligi masalasini yechish talab etiladi. ERI algoritmining
bardoshliligi quydagi uchta masalaning murakkabligi bilan aniqlanadi [ 5 ,1 7 , 2 3 ]:
- imzoni qalbakilashtirish , berilgan hujjatga, mahfiy kalitga ega bo‘lmagan holda
to‘g‘ri imzo hisoblash;
6](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_6.png?v=1)
![iPM
,
umuman qaraganda, dastlabki ma’lumot o‘zgartirilgan bo‘lishi mumkin, shuning uchun
iPM
1 ,
bo‘lib,
1MH
- xesh qiymat hisoblanadi. Agar yoki
bo‘lsa, u holda elektron xujjat haqiqiy, aks holda qalbaki
hisoblanadi.
Endi imzoni hisoblash va uni tekshirishga asoslangan ERI algoritmlari DSA va ГОСТ Р
34.10-94 standarlari bilan tanishiladi. Bu algoritmlarning asosini El-Gamal shifrlash algoritmi
tashkil etadi.
1.3. DSА ERI standarti. ГОСТ Р 34.10-94 elektron raqamli imzosi
1991 yilda NIST (National Institute of Standard and Technology) tomonidan DSA
(Digital Signature Algorithm) algoritmiga asoslangan DSS (Digital Signature Standard) ERI
standartining loyihasi muhokamaga qo‘yildi. Ushbu algoritm bardoshliligi yetarli katta tub
xarakteristikaga ega bo‘lgan chekli maydonda diskret logarifmlash masalasining
murakkabligiga asoslangan [5, 17, 23]. Quyida algoritm qadamlari ketma-ketligi keltirilgan.
Imzoni shakllantirish
1. Ma’lumot jo‘natuvchi M -ma’lumotni va quyidagi parametrlarni keng doiradagi
tizim foydalanuvchilariga ochiq e’lon qiladi:
p – tub son, 2 512
< p < 2 1024
, bit uzunligi 64 ga karrali;
q - tub son, 2 159
< q < 2 160
, p-1 ning bo‘luvchisi;
g = h ( p-1 ) /q
mod p , bu yerda h ushbu 0 < h < p va h ( p-1 ) /q
mod p >1 shartlarni
qanoatlantiruvchi butun son;
y – ochiq kalit bo‘lib, y = q x
mod p formula orqali aniqlanadi. Bu yerda x – maxfiy
kalit bo‘lib, 0<x<q oraliqdan olingan va faqat imozolovchining o‘zigagina ma’lum;
H ( M ) – М ma’lumotdan [ 1;q ] oraliqdagi butun sonni generatsiya qiluvchi xesh-
funksiya.
2. Ma’lumot jo‘natuvchi 0<k < q oraliqdan tasodifiy k sonni tanlaydi, uni maxfiy
tutadi va imzo generatsiyasidan keyin darhol yo‘qotadi.
3. Ma’lumot jo‘natuvchi r va s qiymatlarni quyidagi qonuniyat orqali hisoblaydi:
r = g k
mod p mod q,
s = k -1
( xr + H ( M )) mod q.
M - ma’lumotga qo‘yilgan imzo ( r, s ) sonlar juftligidan iborat.
11](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_11.png?v=1)
![II BOB. ELEKTRON RAQAMLI IMZO ALGORITMLARIDAN
FOYDALANISH
2.1. Elliptik egri chiziqlarga asoslangan elektron raqamli imzo algoritmlari
Elliptik egri chiziqlarga asoslangan kriptotizimlar kriptografiyaga 1985 yilda V.Miller
va N.Koblits [22, 24] tomonidan tadbiq qilingan. Asimmetrik kriptografik algoritmlarning
ko‘pchiligi chekli maydonda diskret logarifmlash masalasining murakkabligiga asoslangan
bo‘lib, bu algoritmlarni elliptik egri chiziqlarga o‘tkazish masalasi alohida izlanish talab etadi.
Quyida xalqaro standart sifatida qabul qilingan EC DSA va ГОСТ Р 34.10-2001 elliptik egri
chiziqlarga asoslangan elektron raqamli imzo algoritmlari ko‘rib o‘tiladi.
Elektron raqamli imzo algoritmining boshlang‘ich parametrlari
Qaralayotgan algoritmning asosiy parametrlari xarakteristikasi -tub sondan iborat
bo‘lgan chekli maydonda aniqlangan -elliptik egri chiziq va shu chiziqda olingan katta
tub tartibga ega bo‘lgan -bazaviy nuqta hisoblanadi.
Bu chiziq quyidagi tenglama bilan beriladi [ 20 , 22, 40 ] :
.
Turli parametrlar juftligi izomorf elliptik egri chiziqlarni aniqlaydi.
Tenglamaning muhim parametrlari esa mos ravishda diskriminant d = -16 ( 4a 3
+ 27b 2
) va
invariant j = 1728 ( 4a) 3
/ d ko‘rinishda
bo‘ladi. Tenglamaning koeffitsiyentlari a va b ma’lum j invariant bo‘yicha quyidagicha
aniqlanadi [20]:
bu yerda
Elliptik egri chiziqning nuqtasi maydondan olingan ( )
elementlar juftligi bilan aniqlanadi. Bu nuqtani hisoblashning yagona aniq usuli yo‘q.
Shuning uchun tanlash usuli bilan – biror -qiymat olinadi va maydonda
ifodaning qiymati hisoblanib, bu qiymat biror sonni kvadrat ildizi bo‘lishi yoki bo‘lmasligi
tekshiriladi. Agarda kvadrat ildiz mavjud bo‘lsa, bu idiz deb olinadi. Kvadrat ildiz
mavjudligi Lejandr simvoli yordamida tekshiriladi [20].
14](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_14.png?v=1)
![Kriptografik bardoshli raqamli imzo tizimini olish uchun quyidagi shartlar bajarilishi
kerak[20, 29]:
1) Elliptik egri chiziq supersingulyar bo‘lmasligi kerak, ya’ni ;
2) barcha lar uchun, bu yerda C yetarli katta son,
qaysiki maydonda diskret logarifmlashni hisoblash vaqt nuqtai nazaridan mumkin
bo‘lmasin (odatda qilib tanlanadi);
3) Elliptik egri chiziq anomal bo‘lmasligi kerak, ya’ni .
4) Elliptik egri chiziqning ratsional koordinatali nuqtalari soni m quyidagi shartni
qanoatlantirsin:
# , bu yerda - katta tub son, va .
Hozirda maxsus chiziqlar sinflariga mavjud bo‘lgan hujumlardan himoyalanishning
mavjud usuli - - Elliptik egri chiziqni yuqoridagi shartlarni qanoatlantiruvchi qilib olishdan
iboratdir.
Ushbu parametrlar foydalanuvchilar guruhi uchun umumiy bo‘lishi mumkin. Imzoni
generatsiya qilish va tekshirish uchun ishlatiladigan individual parametrlar – mahfiy va ochiq
kalitlar deb nomlanadi.
Imzo qo‘yish kaliti (mahfiy kalit) – bu intervaldagi ihtiyoriy soni.
Imzoni tekshirish kaliti (ochiq kalit) – bu elliptik egri chiziqdagi nuqta.
Bundan tashqari raqamli imzo algoritmida h -xesh-funksiyadan ham foydalaniladi.
2.2. EC DSA raqamli imzo algoritmi
Imzoni generatsiya qilish algoritmi.
Boshlang‘ich ma’lumotlar: -imzolanishi kerak bo‘lgan ma’lumot, berilgan
parametrlar va imzo kaliti. Natija: imzo .
1) intervaldan tasodifiy soni tanlanlanadi, bu yerda nuqta tartibi
shartni qanoatlantiruvchi tub son bo‘lishi kerak.
2) hisoblanadi.
3) hisoblanadi.
4) Agar bo‘lsa, u holda 1-qadamga boriladi, aks holda keyingi qadamga o‘tiladi.
5) hisoblanadi.
6) hisoblanadi.
7) hisoblanadi.
8) Agar bo‘lsa, u holda 1-qadamga boriladi.
9) -ma’lumot imzosi - juftligidan iborat.
15](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_15.png?v=1)
![Imzo qo‘yish kaliti (mahfiy kalit) sifatida – intervaldagi ixtiyoriy
sonini olamiz.
Imzoni tekshirish kaliti (ochiq kalit) sifatida elliptik egri chiziqdagi , ya’ni
)576959;168708(]63289[ GQ
nuqta hisoblanadi.
Bundan tashqari raqamli imzo algoritmida -xesh-funksiyadan ham foydalaniladi.
Ushbu misolda xesh qiymat sifatida h=86347 qiymatdan foydalaniladi.
Imzoni generatsiya qilish qadamlari:
1) intervaldan tasodifiy soni tanlanadi.
2) hisoblanadi.
3) hisoblanadi.
4) shart bajarilmaganligi uchun keyingi qadamga o‘tiladi. Bizning misolda r noldan
farqli. Ushbu qiymat ERI ning birinchi parametri sifatida qabul qilinadi.
5) hisoblanadi.
6) )(: mhe
hisoblanadi. Uning qiymati deb olingan.
7) Yuqoridagi parametrlar asosida hisoblanadi. Natijada s=278097
olinadi.
8) Agar bo‘lsa, u holda 1-qadamga boriladi. Berilgan misolda bu qiymat noldan
farqli va u ERIning ikkinchi parametri hisoblanadi.
9) -ma’lumot imzosi - juftligidan iborat.
Endi ushbu imzoni tekshirish qadamlari bilan tanishib chiqamiz. Ochiq kalit sifatida
-nuqta olingan edi. Bundan tashqari imzolangan matnni o‘zgarmagan
deb faraz qilib, imzoni tekshirish qadamlari ko‘rib o‘tiladi.
Imzoni tekshirish qadamlari:
1) Avvalo 1,1 nsr
shart tekshiriladi. Bu misolda ushbu shart bajarilgani uchun
keyingi qadamlarga o‘tiladi.
2) hisoblanadi va matn jo‘natilish jarayonida o‘zgartirilmaganligi uchun
ga teng bo‘ladi.
3) hisoblab topiladi.
4) hisoblanadi.
5) hisoblanadi.
6) Yuqoridagi parametrlar asosida hisoblanadi, ya’ni
hisoblanadi. Bunda ,
va .
17](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_17.png?v=1)
![7) shart tekshiriladi. Ya’ni 246423 mod 500933 =246423
imzoning birinchi parametri bilin taqqoslanadi. Keltirilgan misolda bu ikkala qiymat ham
ga teng va “imzo haqiqiy” degan xulosaga kelinadi. Agar elektron
xujjat uzatilish jarayonida o‘zgartirilgan bo‘lsa, u holda imzoni tekshirishdagi xesh qiymat
imzo qo‘yishdagi xesh qiymatdan farqlanganligi hisobiga, 7- shart bajarilmaydi va “imzo
qalbaki” degan xulosaga kelinadi.
Quyida EC DSA kabi, ГОСТ Р 34. 10–94 ERI algoritmining elliptik egri chiziqqa
o‘tkazilgan modifikatsiyasi hisoblangan Rossiya standarti ГОСТ Р 34.10-2001 algoritmi
haqida to‘xtalinadi.
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 255
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 254
<
n < 2 256
shartni qanoatlantiruvchi son .
2. (x
1 ,y
1 )= [ k ] G hisoblansin, ya’ni tanlangan egri chiziqqa tegishli G nuqtani k marta
qo‘shilsin.
3. r=x
1 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 <n 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.
18](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_18.png?v=1)
![4. u
1 = s w mod q hisoblansin.
5. u
2 = ( n-r ) w mod n hisoblansin.
6. X= [ u
1 ] G+ [ u
2 ] Q= ( x
1 ,y
1 ) hisoblansin.
7. Агар x
1 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< e<n oraliqda 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 k<n larda [ 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
1 ] G+ [ u
2 ] 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
1 bo‘lib, uning mod n bo‘yicha qoldig‘i
r ga teng, ya’ni x
1 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
19](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_19.png?v=1)
![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.
Imzoni generatsiya qilish qadamlari:
1. 1 k n-1 intervaldan ixtiyoriy k=1625 soni tanlanadi.
2. ( x
1 ,y
1 )= [ 1625 ] G hisoblanadi, ya’ni tanlangan egri chiziqqa tegishli G nuqtani 1625
marta qo‘shib, ( 5814; 5316 ) nuqtani hosil qilinadi.
3. r=x
1 mod n hisoblanadi. Agar r=0 bo‘lsa, 1-qadamga qaytiladi va boshqa k soni
tanlanadi. Ko‘rilayotgan misolda r=5814 mod 8297 = 5814 ga teng.
4. M -ma’lumotning xesh-funksiyasi hisoblanadi, ya’ni e=H ( M ). Agar H ( M ) mod n =0
bo‘lsa, u holda H ( M ) mod n =1 deb olinadi. Qarayotgan misolda bu qiymat h=459 ga teng.
5. 0< d <n intervaldan olingan d mahfiy kalit asosida yuqorida topilgan parametrlardan
foydalanib, s= ( dr+ke ) mod n hisoblab, topiladi, ya’ni s= (725*5814 +1625*459 ) mod 8297
=7716.
6. Agar s=0 bo‘lsa, 1-qadamga qaytiladi va boshqa k soni tanlanadi.
7. Hosil bo‘lgan ( r,s ) = ( 5814; 7716 ) -sonlar juftligi M - ma’lumotning imzosi sifatida
ma’lumotga qo‘shib uzatiladi.
Imzoni tekshirish qadamlari. Qabul qilingan imzo ( r,s ) = ( 5814; 7716 ) sonlar
juftligidan iborat bo‘lsin.
1. Agar olingan imzo 1 r, s n-1 shartni qanoatlantirmasa, u holda imzo qalbaki va
tekshirishni shu yerda to‘xtatish mumkin, lekin yuqoridagi imzo ushbu shartni
qanoatlantiradi, shuning uchun navbatdagi qadamlarni bajarish davom ettiriladi.
2. e= H ( M ) hisoblanadi, elektron xujjat uzatilish jarayonida o‘zgartirilmagan deb qabul
qilinib, xujjatning xesh qiymati imzo qo‘yishdagi xesh qiymat bilan aynan bir xil, ya’ni e=
459 .
3. w= H ( M ) ( n-2 )
mod n hisoblanadi, ya’ni w= 459 (8297 -2 )
mod 8297 =2133 .
4. u
1 = s w mod n = 7716*2133 mod 8297 = 5277 hisoblab topiladi .
5. u
2 = ( n-r ) w mod n=(8297-5814)*2133 mod 8297 = 2753 hisoblab topiladi.
20](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_20.png?v=1)
![6. Yuqoridagi parametrlar asosida hisoblanadi, ya’ni
. Bunda va
ga teng. Shunga ko‘ra, .
shart tekshiriladi, ya’ni 5814 mod 8297 =5814 imzoning birinchi
parametri bilan taqqoslanadi. Bizning misolda bu ikkala qiymat ham
teng va “imzo haqiqiy” xulosasiga kelinadi. Agar elektron xujjat uzatilish jarayonida
o‘zgartirilgan bo‘lsa, u holda imzoni tekshirishdagi xesh qiymat imzo qo‘yishdagi xesh
qiymatdan farqlanganligi hisobiga 7-shart bajarilmaydi va “ imzo qalbaki ” degan xulosaga
kelinadi.
2.4. Mavjud hisoblash murakkablik masalalariga asoslangan ERI algoritmi
E’tiboringizga xarakteristikasi katta son bo‘lgan chekli maydonda diskret
logarifimlashni, yetarli katta sonni tub ko‘paytuvchilarga ajratish va elliptik egri chiziq
nuqtalari ustida amallar bajarishga oid hisoblash murakkablik masalalariga asoslangan holda
yaratilgan ERI algoritmi havola etamiz.
Biror M –ma’lumotni imzolash uchun, quyidagilar amalga oshiriladi:
1) -ochiq va -maxfiy kalitlar de 1 mod ( n ) taqqoslamadan hisoblab olinadi,
bu yerda , maxfiy tutiluvchi yetarli katta tub sonlar, ( n ) -Eyler
funksiyasi, aniqlik uchun bo‘lsin;
2) tasodifiy k va sonlari tanlanadi, ular ushbu , q – tub son va ,
, hamda EKUB( x , n )=1 shartlarni qanoatlantiradi;
3) -parametr tanlanadi, bu yerda ushbu EKUB va
shartlarni qanoatlantiradi hamda -soni -Eyler funksiyasi qiymatini bo‘luvchisi emas.
Ochiq kalitlar sifatida ushbu:
1) , bu yerda a –sonining qiymati tenglikdan olinadi;
2) va , bu yerda -bazaviy nuqta tanlangan elliptik egri
chiziqda q –tartibga ega parametrlar qabul qilinadi.
Imzo quyidagicha hisoblanadi:
1. Tanlangan tasodifiy - soni bo‘yicha (bu son mahfiy tutiladi va imzo hisolanib
bo‘lingandan so‘ng darhol yo‘qotiladi) hisoblanadi.
2. hisoblanadi.
3. hisoblanadi.
4. + ] hisoblanadi.
5. hisoblanadi.
21](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_21.png?v=1)
![Imzo sifatida: ( r,s ) –uchlik qabul qilinadi .
Imzoni tekshirish quydagicha amalga oshiriladi :
1. Agar 1 r, s< q va shartlar buzilsa, u holda “imzo qalbaki” va jarayon
to‘xtatiladi, aksincha bo‘lsa keyingi bosqichga o‘tiladi.
2. M – ma’lumotning H ( M ) - xesh qiymati hisoblanadi, ya’ni h=H ( M ).
3. hisoblanadi .
4. , bu yerda , chunki .
5 . hisoblanadi, bu yerda
= .
6. hisoblanadi, bu yerda = .
7. hisoblanadi.
8. Agar bo‘lsa, u holda imzo haqiqiy, aks holda qalbaki
bo‘ladi.
ERI algoritmi to‘g‘riligining isboti. Buning uchun
tenglikning o‘rinli ekanligi ko‘rsatiladi.
Haqiqatan ham, ushbu
+ ifodadan
= =
= topiladi.
U holda:
[ + ] G = [ + [
== tenglik o‘rinli.
Ikkinchi tomondan esa:
=[ +[ =
=[ +[ - ==[ +
==[ + = .
Shunday qilib talab qilingan isbot ko‘rsatildi.
Algoritmning tuzilishiga ko‘ra, har bir hisoblash murakkablik turlari bo‘yicha ochiq va
mahfiy kalitlar generatsiya qilinib, mahfiy kalitlar bilan imzoni hisoblash amalga oshiriladi,
ochiq kalitlar bilan esa imzo tekshiriladi. Bunday tuzilish algoritmning o‘ziga xosligi bo‘lib,
bardoshlilikni tubdan oshiradi.
22](https://docx.uz/documents/967452c8-e269-48df-85a3-ccbd8eb5dda7/page_22.png?v=1)
Elektron raqamli imzo algoritmlaridan foydalanish