Buxoro davlat universiteti tarix fakulteti tarix kafedrasi

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 = p²*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-funkstiya hisoblanadi, 02. x son generastiyalanadi, 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-funkstiya m = H(M) hisoblanadi;
2. oshkora kalit (n, k) dan foydalanib S uchun S^k (mod n) hisoblanadi;
3. n bitlar sonining ikqilanganini 3 ga bo’lganiga teng yoki katta bo’lgan, butundan ancha kichik a soni va 2^a hisoblanadi;
4. m va m+2^a bilan S^k (mod n) taqqoslanadi:
m = = s^k (mod n);
m+2^a = = s^k (mod n).
Agar S^k (mod n) m ga teng yoki undan katta bo’lsa va s^k (mod n) m+2^a 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.
Elektron raqamli imzoni shakllantrish

p, q, x, k, n

Elektron raqamli imzoni

tekshirish

n, k, S


M

a, 2a
m = = s^k (mod n)

m+2^a = = s^k (mod n)

m = H(M)
w  ((m - x ^k) (mod n))/p*q
S  x+((w/kx k^-1 (mod p))p*q


S

3-rasm. ESIGN algoritmini shakllantirish va tekshirish jarayonlari.

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 generastiya qilish uchun avvalo ikkita tub p va q son shunday tanlanadiki, q soni p-1 ning ko’paytuvchisi bo’lsin. Keyin a^q  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 generastiya 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.
Hozirgi vaqtda eng murakkab hisoblangan elliptik egri chiziqli diskret logarifm muammosiga asoslangan ERI algoritmlaridan keng foydalanilmoqda. Elliptik kriptografiyaning afzallik tarafi shundaki, ayni paytda elliptik egri chiziqlar nuqtalari guruxida diskret logarifmlash masalalari echimlari uchun subeksponenstial algoritmlar mavjud emas.
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 [5].
2-jadval
RSA va ECDSA algoritmlari asosida ERI yaratish va uni tekshirish