Axborot xavfsizligi” kafedrasi «rsa kriptoalgoritmini dasturiy ta’minoti va tahlili» mavzusida

II-BOB. RSA KRIPTOALGORITIMING DASTURIY TA’MINOTI NI YARATISH VA TAHLILI QILISH
2.1 RSA shifrlash algoritmi va blok sexemalari
RSA algoritmi: RSA algoritmi 1978-yilda paydo bo'lgan assimetrik shifrlash algoritmining bir turidir. Algoritm ochiq kalitli shifrlash algoritmi bo'lib, keng qabul qilingan va jamoatchilik tomonidan amalga oshirilgan. Shifrlash tavsifi: Shifrlash algoritmi ikki turga bo'linadi, simmetrik va assimetrik shifrlash. Nosimmetrik shifrlashdan foydalanib, ikki tomon yagona kalitga muhtoj bo'lgan umumiy kalit bilan bog'lanadi. Shifrlash va dekodlashning jo'natuvchisi yoki qabul qiluvchisidan qat'i nazar, kalitdan foydalaning Shifrlash algoritmi: ma'lum bo'lgan ochiq matn x(x3-rasm: Simmetrik shifrlash modeli
Algoritm katta butun sonlar va asosiy testlarga asoslangan; uning matematik asosi Eyler teoremasi. Elementar sonlar nazariyasida; uning xavfsizligi katta butun sonni faktoring qilish qiyinligiga asoslanadi. Kalit avlodi: Birinchidan, bir xil uzunlikdagi ikkita katta tub sonni tasodifiy tanlaymiz: p, q, n = p*q, t = (p-1)*(q-1), keyin e raqamini, uning diapazonini tanlaymiz. 0 dan katta va t dan kichik. biz odatda e ning qiymatini ishlatamiz 3, 17, 65537 (216 plyus 1) va e Shartga javob berishi kerak d*e %t = =1, keyin biz d qiymatini olamiz. Natijada biz to'rtta sonni olamiz n, t, e, d; e - shifrlash kaliti, d - shifrni ochish kaliti, n va d - hamma uchun ochiq, p, q va e-ni hamma uchun saqlang. Garchi shifrlash va shifrni hal qilishning o'zgarishi teskari bo'lsa-da, shaxsiy kalit tizimi ma'lumotlarni bir oz sifatida ishlaydi, lekin ochiq kalit tizimi ma'lumotlarni funktsiyani bajaradigan raqam sifatida ishlaydi va matematik funktsiya bir tomonlama. Ya'ni, bu bir tomondan osonlikcha amalga oshishi mumkin, lekin boshqa tomondan juda qiyin, shuning uchun oddiy qadamlar shifrlangan matnni hal qila olmaydi. RSA algoritmiga misol: Ma'lum p = 11, q = 19, olingan n = 209, t = 180. Raqamni tasodifiy e = 7 ni tanlang, 0Raqamli imzo: RSA algoritmi shifrlash/parchalash jarayonida shifrlash uchun ochiq kalitdan va shifrni ochish uchun shaxsiy kalitdan foydalanadi. Maxfiy kalit shifrlash uchun, ochiq kalit esa raqamli imzoda shifrni ochish uchun ishlatiladi. Yuboruvchi M faylining xesh qiymatini hisoblash uchun xesh algoritmidan foydalanadi, so'ngra raqamli abstraktni shifrlash uchun kalitdan foydalanib C raqamli imzosini yaratadi va keyin M C ni birgalikda va qabul qiluvchiga yuboradi. Qabul qiluvchi M1 faylini va C1 raqamli imzosini oladi, M va M1 bir xil ekanligini tekshirishi kerak. Tasdiqlash jarayoni xesh funksiyasidan foydalangan holda M1 ning H1 xesh qiymatini olish va ochiq kalit yordamida C1 raqamli imzosining shifrini ochishdan H2 ni olishdan iborat. H1 bilan H2 ni solishtiring bir xil (Shi va boshq., 2008). Agar xuddi shunday bo'lsa, axborot uzatish xavfsizlikdir.
Maxsus jarayon 5-rasmda ko'rsatilganidek.

Dasturda foydalanuvchi raqamli, xitoycha belgilar, harflar va boshqa ma'lumotlarni shifrlashi va shifrini ochishi mumkin. Raqamli ma'lumotlarni shifrlash va shifrini ochishda foydalanuvchi taklif qilingan protseduraga muvofiq shifrlangan va shifrlangan raqamni bevosita kiritadi, so'ngra kiritilgan raqamning shifrlangan yoki shifrlangan ma'lumotlarini olishi mumkin. Raqamli ma'lumotlarga hech qanday ishlov berishimiz shart emas. Agar foydalanuvchi xitoycha belgilardan iborat ma'lumotni kiritsa, biz ma'lumotni URL kodiga aylantiramiz. Nihoyat, biz shifrlash va shifrini ochish uchun URL kodini ASCII kodiga aylantiramiz. Agar foydalanuvchi ma'lumot satrdan iborat bo'lsa, shifrlash va shifrni ochish uchun ma'lumot ASCII kodiga aylantiriladi. Agar ma'lumot juda uzun satr bo'lsa, avval shifrlash ma'lumotlarini paketlashimiz kerak. Dasturda asosiy funktsiya N va uning Eyler raqamini T ni foydalanuvchi kiritadigan va foydalanuvchining ochiq kaliti e tomonidan berilgan p va q tubiga ko'ra oladi, funktsiyani fun (E va T) deb ataydi va kop yoki yo'qligini aniqlaydi. rime va shaxsiy kalitni oldi D. foydalanuvchi ma'lumotni shifrlash yoki shifrini ochishni tanlaydi, funktsiyani my (shifrlash) deb ataydi, daraja va ko'paytirishni hisoblashni amalga oshiradi
RSA algoritmi ochiq va yopiq kalitdan iborat bo’lib, ochiq kalit hammaga oshkor holatda bo’ladi va u yordamida ma’lumot shifrlanadi. Ochiq kalit yordamida shirfrlangan ma’lumotni maxfiy kalitdan foydalangan holda deshifrlash deyarli zarur vaqt talab qiladi.
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:
3. Quyidagi formula bo‘yicha (Eyler funksiyasi qiymati) hisoblanadi:
4. qiymati bilan o‘zaro tub bo‘lgan katta tub son e tanlab olinadi.
va
5. Quyidagi shartni qanoatlantiruvchi d soni aniqlanadi:
Yoki ushbu formulani yanada takomillashtirib quyidagi ko’rinishga keltiramiz:

Bu shartga binoan ko‘paytmaning 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 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. Axborot quyidagi formula bo’yicha shifrlanadi: .
_Axborotni deshifrlashda quyidagi munosabatdan foydalaniladi:

2.3.-rasm. RSA shifrlash algoritmida ochiq va yopiq kalitni hosil qilinishi.

2.4.-rasm. RSA shifrlash algoritmida matnni shifrlash va deshifrlash
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.

Mukammallashtirilgan RSA (MRSA) algoritmi

Taklif etilayotgan Modified RSA (MRSA) sxemasi RSA tizimining asosiy muammolarini hal qilishga qaratilgan. Aksariyat hollarda asosiy muammo shundaki, u "N" ga asoslanib hisoblangan kalitlar osongina sinishi mumkin . Chunki u faqat 2 ta tub sonlarning mahsulidir. "N"ning qiymatini olgandan so'ng, xaker kalitlarni topib, tizimni buzishi mumkin. Asosiy modifikatsiyalar tizimni samarali va xavfsiz qilishlari quyidagi bo'limda muhokama qilinadi. MRSA kalit avlodi Taklif etilayotgan modelda “n” farqli tub sonlar mavjud. Ushbu bo’limda barcha hisoblash va ishlash tahlillari to'rtta katta tub son yordamida amalga oshiriladi. Ochiq va yopiq kalit ko'rsatkichi uchta komponentdan iborat. "N" to'rtta tub son "w", "x", "y" va "z" ko'paytmasi. Ochiq kalit ko'rsatkichi uchta komponentdan (e, f, N) iborat bo'lib, bu erda "e" va "f" tasodifiy olinadi. Bu "N" faktoringi bilan birga yanada murakkablikni qo'shadi. Chunki faqat “N” qiymati umumiy va shaxsiy komponent sifatida saqlanadi, bu bilan tajovuzkor "N" ni bilganda ham to'rtta tub sonning qiymatini aniqlay olmaydi. Maxfiy kalit exponentlari uchta komponentdan (d, g, N) iborat. Xavfsizlik maqsadida, Barcha to'rtta tanlangan tub sonning bit uzunligi oddiy RSA dagi kabi bir xil uzunlikda bo’ladi. Algoritm quyida keltirilgan.
MRSA kalit generatsiyasi
MRSA_key_gen()
Kiritish:
To’rtta tub sonlar: w, x, y, and z
Chiqarish:
Ochiq kalit exponentalari:
Yopiq kalit exponentalari:
Jarayon:

Eyler funksiyasidan foydalanib ning qiymatini hisoblash

va tengliklarni qanoatlantiradigan ixtiyoriy e o’zgaruvchi topish.
va tengliklarni qanoatlantiradigan boshqa ixtiyoriy e o’zgaruvchi topish.
Quyidagi tenglikni qanoatlantiruvchi ixtiyoriy d ni hisoblash
Quyidagi tenglikni qanoatlantiruvchi ixtiyoriy g ni hisoblash
MRSA shifrlash va deshifrlash
MRSA da matnni shifrlash ochiq kalit exponentalari yordamida amalga oshirilsa, deshifrlash yopiq kalit exponentalari yordamida amalga oshiriladi. Shifrlash va deshifrlash faqatgina 4 ta katta tub sonlar ko’paytmasidan tashkil topgan N ga bog’liq bo’libgina qolmasdan balki, 4 ta ixtiyoriy tanlangan komponentalar ya’ni “e”, “f”, “d”, “g” larga ham bog’liq. Bu komponentalar tizimni buzish maqsadini yanada qiyinlashtiradi.
MRSA_Encryption()
Kiritish:
Oddiy matnli xabar, M(Ochiq kalit exponentalari:
Chiqarish:
Shifrlangan matn, X
Jarayon:

MRSA_Decryption()
Kiritish:
Shifrlangan matn, X
Yopiq kalit exponentalari:
Chiqarish:
deshifrlangan matn, Y
Jarayon:

Quyida, taklif qilingan Modified RSA (MRSA) yordamida shifrlash va deshifrlash na’munasini muhokama qilamiz.
MRSA na’munasi:

• 
  4 ta har xil tub sonlar olinadi , , , .
  
• 
  Hisoblanilsin
  
• 
  
  
• 
  Eyler funksiyasidan foydalanib ning qiymatini hisoblash
  
• 
  
  

• 
  va tengliklarni qanoatlantiradigan ixtiyoriy e o’zgaruvchi topish.
  

e=41

• 
  Quyidagi tenglikni qanoatlantiruvchi ixtiyoriy d ni hisoblash
  

d=294041

• 
  va tengliklarni qanoatlantiradigan boshqa ixtiyoriy f o’zgaruvchi topish.
  

f=97

• 
  Quyidagi tenglikni qanoatlantiruvchi ixtiyoriy g ni hisoblash
  

g=455713
Kiritiladigan xabar, M=12321
Shifrlash,
Deshifrlash, =12321

2.5-rasm. Mukammallashtirilgan RSA algoritmining diagrammasi.
2.5-rasmda Mukammallashtirilgan RSA (MRSA) algoritmi ritmining oqim diagrammasi ko'rsatilgan. N va ni hisoblash uchun kirish sifatida to'rtta alohida tub son olinadi. Tasodifiy sonlar jufti (e, f) , diapazonidan tanlanadi. ochiq kalit ko'rsatkichi. Ushbu tasodifiy sonlarning (d, g) modulli multiplikativ teskarisi shaxsiy kalit ko'rsatkichi sifatida foydalanish uchun hisoblanadi. Shifrlash va deshifrlash ushbu maxfiy kalit va ochiq kalit exponentlari yordamida amalga oshiriladi.
Algoritm Intel (R) Core (TM) i5-3230M CPU @ 2,60 gigagertsli mashinada va 4,00 GB RAMda ishlaydigan JAVA 8 da amalga oshiriladi. Algoritm (RSA va MRSA) xavfsizlik darajasi va tezligiga ta'sir qiluvchi turli xil muhim parametrlarga ega. Modul uzunligini oshirish uni faktorlarga ajratishning murakkabligini keltirib chiqaradi. Shunday qilib, kalitni aniqlash qiyinchilik tug’dirsada, shaxsiy kalit uzunligini oshirish muhim. RSA va Modified RSA (MRSA) parametrlarining o'zgarishi vaqtga va boshqa shunga yaqin bo’lgan xususiyatlarga bog’liq.

2.6-rasm. RSA algoritmining ishlash tezligi.

2.7-rasm. Mukammallashtirilgan RSA algoritmining ishlash tezligi .
Taklif etilgan Modified RSA (MRSA) algoritmi turli bit o'lchamlari bo'yicha tekshiriladi kiritish. Rivest, Shamir va Adleman tomonidan original RSA algoritmining ishlashi 2.6-jadvalda tasvirlangan. Shuningdek, Modified RSA (MRSA) sxemasining ishlashi kalitlarni yaratish, shifrlash vaqti va shifrni ochish bo'yicha 2.7-jadvalda ko'rsatilgan. Yuqoridagi jadvallarni solishtirganda, modifikatsiyalangan RSA (MRSA) kalitini yaratish vaqti RSA ga qaraganda yuqoriroq degan xulosaga kelish mumkin. Modified RSA (MRSA) ning yuqori kalit yaratish vaqti, buning afzalligi sifatida qaralishi mumkin qo'shimcha murakkablik tufayli tizimni buzish vaqti yuqori.

2.8-rasm RSA va MRSA ning shifrlash uchun sarflaydigan vaqtlari orasidagi farq

2.9-rasm RSA va MRSA ning deshifrlash uchun sarflaydigan vaqtlari orasidagi farq
2.8-rasmda RSA va tavsiya etilgan shifrlash vaqtini taqqoslash tasvirlangan O'zgartirilgan RSA (MRSA) sxemasi. Bu shuni ko'rsatadiki, pastki bit uzunligi uchun tub sonlar, ikkita algoritm deyarli bir xil vaqtni sarflaydi. Ammo bit uzunligi ortishi bilan egri chiziqlar orasidagi farq tez o'sib boradi.
Misol uchun, 2048 bit uzunligidagi kirish boshlang'ich sonlari, Modified RSA da shifrlash vaqti (MRSA) 21,9 ms va RSA 3,32 ms oladi.
2.9-rasmda RSA va tavsiya etilgan shifrni ochish vaqtini taqqoslash ko'rsatilgan O'zgartirilgan RSA (MRSA) sxemasi. Bu deyarli bir xil miqdorni ko'rsatadi RSA va Modified RSA (MRSA) tomonidan quyi bit uzunligi uchun sarflangan vaqt tub sonlar. Bit uzunligi ortishi bilan egri chiziqlar orasidagi farq tez ko'tariladi. Misol uchun, 4096 bit uzunligidagi kirish boshlang'ichlari, shifrni ochish vaqti Modified RSA (MRSA) da 19 983,37 milodiy va original RSA 1116,24 milodiyni oladi. Yuqoridagi grafiklardan shifrlash va dekodlashni osonlik bilan ko'rish mumkin marta RSA dan yuqori. Vaqt o'sishi moslashadi, chunki u ortadi tavsiya etilgan Modified RSA (MRSA) usulida xavfsizlik katta darajada.
Xavfsizlik tahlili. RSAda turli xil hujumlar bo’lishi mumkin, ular orasida qo'pol kuch hujumi, vaqtli hujum va hokazo. [20]. RSA tizimini buzish uchun zarur bo'lgan vaqt ishlatilgan tub sonlarni topish uchun zarur bo'lgan vaqtga teng. Bu “N” mahsulotini faktoring qilish talabini joriy qiladi. Elliptik egri faktorizatsiya usuli (ECM) va umumiy sonli maydon elaklari (GNFS) odatda “N” faktoring uchun ishlatiladi. Bu meni faktoring bo'yicha eng tez ma'lum bo'lgan usullardir. Garchi tajovuzkor ushbu usullardan foydalangan holda "N" ni faktorlarga ajratishi mumkin bo'lsa ham, lekin bu hali ham ikkita ixtiyoriy "e" va "f" komponentlarini hisoblashda etarli emas. Yuqoridagi faktorizatsiya usuli "w", "x", "y", "z" ni topish uchun ishlatilishi mumkin, ammo "e" va "f" ni faqat to'liq qo'pol kuch hujumi bilan topish mumkin. Boshqa so'z bilan aytganda,

Bu yerda,
=Tizimni buzish uchun zarur bo'lgan vaqt
= GNFS yoki ECM yordamida w, x, y, z ni topish uchun zarur bo'lgan vaqt
= e, f ni topish uchun kuchli hujum uchun zarur bo'lgan vaqt
Yaqqol kuzatilgan holat shundaki, Modified RSA (MRSA) shifrlash uchun to'rtta tub "w", "x", "y", "z" va ikkita tasodifiy "e", "f" sonlarni o'z ichiga oladi, asl RSA esa faqat ikkita tub sonni o'z ichiga oladi. Shifrlash uchun "w", "x" va faqat bitta tasodifiy raqam "e". Shunday qilib, Modified RSA (MRSA) algoritmini buzish uchun zarur bo'lgan vaqt, hech bo'lmaganda, asl RSA ni buzish uchun zarur bo'lgan vaqtdan ko'proq bo'ladi. 2 faktor bilan. Va bu taklif qilingan Modified RSA (MRSA) algoritmini original RSA algoritmiga qaraganda xavfsizroq qiladi.
Xulosa va kelgusi ish RSA xavfsizligi ko'p sonli faktoringga bog'liq.
Ushbu tadqiqot ikkita tub son o'rniga "n" farqli tub sonlar asosida ishlaydi va u katta tub sonni topish uchun hujum vaqtini qisqartiradi. Modified RSA (MRSA) ning asosiy avlodi "N" katta omil qiymatiga bog'liq, shuning uchun u yuqoriroq talab qilinadi asosiy ishlab chiqarish vaqti. Kalit ishlab chiqarish vaqti qanchalik baland bo'lsa, tizimni buzish uchun vaqt kerak bo'ladi, bu esa tizimni kuchliroq qiladi. Modified RSA (MRSA) ning ikki marta shifrlash va shifrini ochish protsedurasi RSA algoritmiga nisbatan sodda, shuning uchun u tizimga ortiqcha yuk emas. Shifrlash va dekodlash RSA algoritmiga qaraganda ko'proq vaqt talab etadi. Algoritmning bajarilishi qo'pol kuch hujumi uchun olingan vaqtga asoslanib o'lchanadi. Ushbu taklif qilingan sxemaning cheklovi shundaki, agar "n" alohida tub sonlar hisobga olinmasa, u to'g'ri ishlamaydi. Ba'zi qo'shimchalarni qo'shish orqali RSA algoritmining xavfsizligini oshirish uchun shifrlash va dekodlash jarayonidagi omillar kelajakda yaxshi ish bo'lishi mumkin.