|
2-rasm. ERIni tekshirish jarayoni
1-jadval
ERI algoritmlarining muammolar murakkabligi bo‘yicha sinflanishi
ERI algoritmlari
|
Faktorlash muammosiga asoslangan ERI
|
Diskret logarifmlash muammosiga asoslangan ERI
|
Elliptik egri chiziqli diskret logarifmlash muammosiga asoslangan ERI
|
Parametr-lar algebrasi muammosiga asoslangan ERI
|
Turli muammolar-ga asoslangan ERI
|
RSA,
ESIGN,
Ong-Schnorr-Shamir,
PGP,
RPK
|
EGSA,
DSA,
SHnorr,
GOST 34.10-94
|
ECDSA,
GOST 34.10-2001,
EC-KCDSA,
EC-GDSA ,
DSTU 4145-2002
|
O’zDSt 1092:2009
|
Kvadratik chegirma,
n moduli bo‘yicha kvadrat ildizdan chiqarishga asoslangan ERI algoritm-lari amaliyotda kam qo‘llaniladi
|
Faktorlash muammosiga asoslangan algoritmlar turkumiga kiruvchi RSA va ESIGN kabi ERI algoritmlari eng ko‘p qo‘llaniladi. RSA algoritmining xavfsizlik darajasi katta sonlarni ko‘paytuvchilarga ajratish murakkabligiga asoslanadi. Ushbu algoritm oshkora modul n ikki tub sonning ko‘paytmasi bo‘lib, ko‘paytuvchilar sir tutiladi. Bu tub faktor (ko‘paytuvchi)larni n bo‘yicha topish, ya’ni faktorlashtirish muammosi echish o‘ta murakkab muammolar sirasiga kirishi kriptotizimning yuqori bardoshliligini ta’minlaydi.
ESIGN sxemasi 1985 yil YAponiya olimlari tomonidan taklif qilingan. Bu elektron raqamli imzoning asosiy xususiyati uning tezkorligidir. RSA yoki El-Gamal algoritmlariga solishtirilganda, ESIGN algoritmi yordamida hujjatni imzolash va imzoni tekshirish jarayoni bir necha marta tezlik bilan amalga oshiriladi.
Imzo parametrlariga quyidagilar kiradi: ESIGN algoritmida maxfiy kalit sifatida katta tub p va q sonlar juftligidan foydalaniladi va ular bo‘yicha n = p2*q ifoda bilan aniqlanadi. Oshkora kalit sifatida (n, k) juftligi olinadi. Bu erda k – xavfsizlik parametridir.
ESIGN algoritmi bo‘yicha ERI shakllantirish va uni uzatish quyidagi qadamlar ketma-ketligini o‘z ichiga oladi (3-rasm):
1. M axborot uchun m = H(M) xesh-funksiya hisoblanadi, 02. x son generatsiyalanadi, p*q3. w ((m - x k) (mod n))/p*q.
4. S elektron raqamli imzo shakllantiriladi:
S x+((w/kx k-1 (mod p))p*q.
Qabul qiluvchi tomon olingan axborot M va elektron raqali imzo S dan foydalanib quyidagi qadamlar ketma-ketligini amalga oshiradi:
1. xesh-funksiya m = H(M) hisoblanadi;
2. oshkora kalit (n, k) dan foydalanib S uchun Sk (mod n) hisoblanadi;
3. n bitlar sonining ikkilanganini 3 ga bo‘lganiga teng yoki katta bo‘lgan, butundan ancha kichik a soni va 2a hisoblanadi;
4. m va m+2a bilan Sk (mod n) taqqoslanadi:
m = = sk (mod n);
m+2a = = sk (mod n).
Agar Sk (mod n) m ga teng yoki undan katta bo‘lsa va sk (mod n) m+2a dan kichik bo‘lsa, ERI haqiqiy, aks holda haqiqiy emas deb topiladi. Bu algoritmda x va k bilan bog‘liq hisoblashlarni oldindan bajarib qo‘yish imkoniyati mavjudligi ERI shakllantirish jarayonini tezlashtirishga imkoniyat yaratadi.
Diskret logarifmlash muammosiga asoslangan SHnorr elektron raqamli imzosini shakllantirishda asosiy modul asosida hisoblanadigan va undan ancha kichik ikkinchi tub moduldan foydalaniladi. SHnorr elektron raqamli imzosi kalitlarni generatsiya qilish uchun avvalo ikkita tub p va q son shunday tanlanadiki, q soni p-1 ning ko‘paytuvchisi bo‘lsin. Keyin aq 1 (mod p) bo‘lganda 1 dan katta a tanlanadi. r, q va a erkin holda e’lon qilinishi hamda foydalanuvchilar guruhi uchun qo‘llanilishi mumkin [5].
Kalitlar juftligini generatsiya qilish uchun q dan kichik tasodifiy son tanlanadi. U maxfiy kalit s bo‘lib, uning yordamida oshkora kalit a-s (mod p) hisoblanadi.
SHnorr elektron raqamli imzo sxemasining asosiy kamchiligi shundaki, dushman kriptotizim asosiga olingan diskret logarifm muammosini etarlicha aniq qo‘ya olganda va uning bu muammoni hal qilishga resurslari etarlicha bo‘lganda qabul qiluvchiga kelib tushgan elektron raqamli imzo soxta bo‘lsa, imzolovchi shaxsda imzoni soxtaligini isbotlovchi dalillar va ma’lumotlarning yo‘qligidir.
Xavfsizlik pog‘onasi bir xil bo‘lganda SHnorr sxemasi uchun elektron raqamli imzo uzunligi RSA va El-Gamal elektron raqamli imzo sxemalarinikidan ancha qisqaroqdir. Milliy standartdagi O’zDSt 1092:2009 standartida ham SHnorr algoritmiga asoslangan r va q modullaridan foydalaniladi.
Bu muammoga asoslangan algoritmlarning eng mashxurlari GOST 34.10-2001, ECDSA ERI algoritmlaridir. ECDSA algoritmida kalit o‘lchamini oshirish bilan imzo shakllantirish sezilarli darajada tezroq amalga oshiriladi, imzo haqiqiyligini tasdiqlash esa ancha sekinroq bo‘ladi.
Quyidagi 2-jadvalda elliptik egri chiziqli diskret logarifm muammosiga asoslangan ECDSA algoritmining faktorlash muammosiga asoslangan RSA algoritmiga nisbatan qisqa kalitlarda tezkorligi ko‘rsatilgan.
2-jadval
RSA va ECDSA algoritmlari asosida ERI yaratish va uni tekshirish
Do'stlaringiz bilan baham: |
