TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
MUSTAQIL ISH 1
RSA ochiq kalitli shifrlash algoritmining kriptotahlili
Bajardi: 070-20-guruh talabasi
Meliboyev Davron Elshodovich
Tekshirdi: Karimov A.A
Toshkent
2024
Reja:
1. RSA shifrlash algoritm tarixi
2. RSAning keng qo’llanila boshlanishi
3. Kriptotahlil
Ochiq kalitli kriptotizimlarni bir tomonli funksiyalar ko‘rinishi bo‘yicha farqlash mumkin. Bularning ichida RSA, El-Gamal va Mak-Elis tizimlarini alohida tilga olish o‘rinli. Hozirda eng samarali va keng tarqalgan ochiq kalitli shifrlash algoritmi sifatida RSA algoritmini ko‘rsatish mumkin.
1976 yilda Uitfild Diffi va Martin Xellmanlar tomonidan chop etilgan “Kriptografiyada yangi yo‘nalish” deb nomlangan maqola kriptografik tizimlar haqidagi tasavvurlarni o‘zgartirib yubordi, ochiq kalitli kriptografiya paydo bo‘lishiga zamin yaratdi. Bu maqolani o‘rganib chiqqan Massachusets texnologiyalar instituti olimlari Ronald Rivest, Adi Shamir va Leonard Adleman 1977 yilda RSA algoritmini yaratdilar.
RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan olingan. Algoritm modul arifmetikasining darajaga ko‘tarish amalidan foydalanishga asoslangan. 1977 yil avgust oyida ScientificAmerican jurnalida RSA kriptotizimini yoritib berishdi va shu algoritm bilan shifrlangan quyidagi iborani ochishni o‘quvchilarga taklif etishdi:
n=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147 599290026879543541, e=9007, M=?
Mukofot sifatida 100 AQSh dollari e’lon qilindi. Algoritm avtorlaridan biri Rivest bu shifrni ochishga 40 kvadrillion yil ketishini aytgan bo‘lsa, 1993 yil 3 sentabrdan 1994 yil mart oyigacha 20 ta mamlakatdan 600 ta ko‘ngilli shaxslar 1600 ta kompyuterda parallel ishlab bu shifrni ochishdi - THE MAGIC WORDS ARE SQUEAMISHOSSIFRAGE.
1982 yilda Ronald Rivest, Adi Shamir va Leonard Adleman RSA Data Security kompaniyasini tashkil etishdi. 1989 yildan boshlab RSA algoritmi Internetda foydalanila boshlandi. 1990 yildan boshlab AQSh mudofaa vazirligi foydalana boshladi.1993 yilda PKCS1 standartining 1.5 versiyasida RSA algoritmini shifrlash va elektron imzo yaratishda qo‘llash keltirildi. Bu standartning oxirgi versiyalari RFC standartida keltirilgan (RFC 2313 — 1.5, 1993 yil; RFC 2437 — 2.0, 1998 yil; RFC3447— 2.1, 2002 yil).
Algoritmni quyidagi qadamlar ketma-ketligi ko‘rinishida ifodalash mumkin:
1. Ikkita katta tub son p va q tanlanadi.
2. Kalitning ochiq tashkil etuvchisi n hosil qilinadi: n=p·q
3. Quyidagi formula bo‘yicha k (Eyler funksiyasi qiymati) hisoblanadi: k=(p-1)(q-1).
4. k qiymati bilan o‘zaro tub bo‘lgan katta tub son e tanlab olinadi.
5. Quyidagi shartni qanoatlantiruvchi d soni aniqlanadi: d =e-1 mod k . Bu shartga binoan e · d ko‘paytmaning k qiymatga bo‘lishdan qolgan qoldiq 1 ga teng. e soni ochiq kalitning ikkinchi tashkil etuvchisi sifatida qabul qilinadi. Yopiq kalit sifatida d soni ishlatiladi.
6. Dastlabki axborot uning fizik tabiatidan qat’iy nazar raqamli ikkili ko‘rinishda ifodalanadi. Bitlar ketma-ketligi L bit uzunlikdagi bloklarga ajratiladi, bu yerda blok sifatida L < log2(n+1) shartini qanoatlantiruvchi eng katta butun sonni olish tavsiya etiladi. Har bir blok [0, n-1] oraliqqa taalluqli butun musbat son 134 kabi ko‘riladi. Shunday qilib, dastlabki axborot Mi, i=17 sonlarning ketma-ketligi orqali ifodalanadi. I ning qiymati shifrlanuvchi ketma-ketlikning uzunligi orqali aniqlanadi.
7. Shifrlangan axborot quyidagi formula bo‘yicha aniqlanuvchi Q sonlarning ketma-ketligi ko‘rinishida olinadi: C = Mi e mod n. Axborotni ochishda quyidagi munosabatdan foydalaniladi:
M = C modn.
Bugungi kunda RSA tizimi programma ta’minoti xavfsizligini ta’minlashda va elektron raqamli imzo sxemalarida foydalaniladi. Shifrlash tezligining pastligi sababli (2 GHz protsessorlarda 512 bitli kalit yordamida 30 kb/s tezlikda shifrlaydi) simmetrik algoritmlarning kalitlarini shifrlab uzatishda ko‘proq foydalaniladi.
Modul son n = p - q = 1517, (p -1)-(q -1) ko‘paytma bilan o‘zaro tub bo‘lgan e=11 ochiq kalit, shifrlanadigan matn M=BESH so‘zi va matn uzunligi L=8 bit berilgan. Agar L berilmagan bo‘lsa, L=[log2(n+1)] formula orqali topiladi.
Shifrlash:
BESH so‘zini ASCII jadvali yordamida bit ko‘rinishga o‘tkazamiz: 01000010010001010101001101001000.
Bitlardan iborat matnni 8 bitdan bloklarga ajratamiz va har bir blokni o‘nlik sanoq sistemasiga o‘tkazamiz: M1=66, M2=69, M3=83, M4=72.
C = Me i mod n formula yordamida shifrlanadi:
C1 = Me 1 mod n=6611mod 1517=(66·(665mod 1517)2 )mod 1517=(66·5322 mod 1517) mod 1517=(66·862) mod 517=763,
C2 = Me 2 mod n=6911mod 1517=821,
C3 = Me 3mod n=8311mod 1517=812,
C4 = Me 4 mod n=7211mod 1517=1097
Hosil bo‘lgan shifrtekst quyidagicha: C = {763,1441,821,1097}.
Shifrni ochish:
Modul son n = p - q = 1517, (p -1)-(q -1) ko‘paytma bilan o‘zaro tub bo‘lgan e=11 ochiq kalit, matn uzunligi L=8 bit va C = {763,1441,821,1097} bizga ma’lum.
1. e sonining (p -1)·(q -1) modul bo‘yicha teskarisini topamiz: d = e-1 mod ((p -1) · (q -1)) = 11-1 mod1440 = 11383 mod1440 = 131
2. Mi = Ci d modn formula yordamida shifrni ochamiz: M1= C d i mod n = 763131 mod1517 = 66; M2 = Cd modn = 1441131 mod1517 = 69, M3 = C3 d modn = 821131 mod1517 = 83, M4 = Cd modn = 1097131 mod1517 = 72,
3. Mi larni o‘nlikdan ikkilikka o‘tkazib, ASCII jadval yordamida harflarga o‘tamiz va natijada M=BESH so‘zi paydo bo‘ladi.
|
