Rsa shifrlash rsa shifrlash algoritmiga misol. Eds va ochiq kalit

10.1-jadval
RSA shifrlash ma'lumotlarni xavfsiz uzatish uchun keng qo'llaniladigan birinchi amaliy ochiq kalit kriptotizimlaridan biridir. Uning shunga o'xshash xizmatlardan asosiy farqi shundaki, shifrlash kaliti ochiq bo'lib, maxfiy saqlanadigan shifrni ochish kalitidan farq qiladi. Texnologiyada RSA ikkita katta tub sonni faktoring ko'paytirishning amaliy qiyinligiga asoslanadi (faktoring muammosi).
Yaratilish tarixi
RSA nomi Rivest, Shamir va Adleman ismlarining bosh harflaridan kelib chiqqan bo'lib, 1977 yilda familiyalarni birinchi marta ommaga ta'riflagan olimlar. Britaniya razvedka xizmatlarida ishlagan ingliz matematigi Klifford Koks birinchi marta 1973 yilda ekvivalent tizimni ishlab chiqdi, ammo 1997 yilgacha uning maxfiyligi ochilmadi.
RSA foydalanuvchisi yordamchi qiymat bilan birga ikkita katta asosiy songa asoslangan ochiq kalitni yaratadi va keyin nashr etadi. sir saqlanishi kerak. Har kim xabarni shifrlash uchun ochiq kalitdan foydalanishi mumkin, lekin agar u etarlicha katta bo'lsa, faqat asosiy raqamlarni biladigan kishi xabarni dekodlashi mumkin. RSA shifrlashning oshkor etilishi asosiy muammo ekanligi ma'lum: bugungi kunda ushbu mexanizm qanchalik ishonchli ekanligi haqida ochiq muhokamalar mavjud.

RSA nisbatan sekin algoritmdir, shuning uchun u to'g'ridan-to'g'ri foydalanuvchi uchun keng qo'llanilmaydi. Ushbu usulning eng keng tarqalgan qo'llanilishi simmetrik shifrlash kaliti uchun ochiq kalitlarni shifrlangan shaklda uzatishdir, bu esa o'z navbatida ommaviy shifrlash va shifrni ochish operatsiyalarini ancha yuqori tezlikda amalga oshirishi mumkin.

Zamonaviy shaklda kriptotizim qachon paydo bo'lgan?
Asimmetrik kalit kriptotizimining g'oyasi 1976 yilda kontseptsiyani nashr etgan, raqamli imzolarni joriy qilgan va raqamlar nazariyasini qo'llashga harakat qilgan Diffie va Hellmanga tegishli. Ularning formulasi tub son moduli bo'yicha ba'zi bir sonning eksponentatsiyasidan yaratilgan umumiy sirdan foydalanadi. Biroq, ular bu xususiyatni amalga oshirish muammosini ochiq qoldirdilar, chunki o'sha paytda faktoring tamoyillari yaxshi tushunilmagan edi.
MITdagi Rivest, Adi Shamir va Adleman bir yil davomida dekodlash qiyin bo'lgan bir tomonlama funktsiyani yaratishga bir necha bor urinishgan. Rivest va Shamir (kompyuter olimlari sifatida) ko'plab potentsial xususiyatlarni taklif qilishdi, Adleman (matematik sifatida) algoritmdagi "zaif nuqtalarni" qidirdi. Ular ko'plab yondashuvlarni oldilar va oxir-oqibat 1977 yil aprel oyida RSA deb nomlanuvchi yakuniy tizimni ishlab chiqdilar.

EDS va ochiq kalit

Elektron raqamli imzo yoki ERI elektron hujjatlarning ajralmas qismi hisoblanadi. U ma'lumotlarning ma'lum kriptografik o'zgarishi bilan shakllanadi. Ushbu atributdan foydalanib, hujjatning yaxlitligini, uning maxfiyligini tekshirish, shuningdek uning egasi kimligini aniqlash mumkin. Aslida, bu odatiy standart imzoga muqobildir.
Ushbu kriptotizim (RSA shifrlash) nosimmetriklardan farq qiladigan ochiq kalitni taklif qiladi. Uning ishlash printsipi shundaki, ikkita turli xil kalitlar qo'llaniladi - shaxsiy (shifrlangan) va umumiy kalit. Birinchisi ERI yaratish va keyinchalik matnni parolini ochish uchun ishlatiladi. Ikkinchisi raqamli imzoni haqiqiy shifrlash va tekshirish uchun.
Imzodan foydalanish RSA shifrlashni yaxshiroq tushunishga imkon beradi, bunga misol sifatida oddiy sir sifatida "beg'araz ko'zlardan yopiq" hujjatni keltirish mumkin.
Algoritmning mohiyati nimada?
RSA algoritmi to'rt bosqichdan iborat: kalitlarni yaratish, kalitlarni taqsimlash, shifrlash va shifrni ochish. Yuqorida aytib o'tilganidek, RSA shifrlash ochiq kalit va shaxsiy kalitni o'z ichiga oladi. Ochiq hammaga ma'lum bo'lishi mumkin va xabarlarni shifrlash uchun ishlatiladi. Uning mohiyati shundan iboratki, ochiq kalit yordamida shifrlangan xabarlar faqat ma'lum bir vaqt ichida maxfiy kalit yordamida shifrlanishi mumkin.

Xavfsizlik maqsadida, butun sonlar tasodifiy tanlanishi va kattaligi bo'yicha bir xil bo'lishi kerak, lekin faktoringni qiyinlashtirish uchun uzunligi bir necha raqamga farqlanadi. Bir xil raqamlarni soddaligi uchun test yordamida samarali topish mumkin, shuning uchun ma'lumotni shifrlash, albatta, murakkablashishi kerak.

Ochiq kalit modul va umumiy ko'rsatkichdan iborat. Private modul va shaxsiy ko'rsatkichdan iborat bo'lib, ular maxfiy saqlanishi kerak.
RSA fayl shifrlash va zaif tomonlari
Biroq, oddiy RSAni buzish uchun bir qator mexanizmlar mavjud. Past unumdorlik va kichik raqamlar bilan shifrlash bilan shifrni butun sonlar ustidagi shifrlangan matnning ildizini tanlash orqali osongina buzish mumkin.

RSA shifrlash deterministik algoritm bo'lgani uchun (ya'ni, uning tasodifiy komponenti yo'q), tajovuzkor ochiq kalit bilan ochiq matnlarni shifrlash va ularning shifrlangan matnga tengligini tekshirish orqali kriptotizimga tanlangan ochiq matnli hujumni muvaffaqiyatli boshlashi mumkin. Agar tajovuzkor ikkita shifrlashni bir-biridan ajrata olmasa, hatto ochiq shakldagi tegishli matnlarni bilsa ham, kriptotizim semantik jihatdan xavfsiz deb ataladi. Yuqorida aytib o'tilganidek, boshqa xizmatlar qo'shmasdan RSA semantik jihatdan xavfsiz emas.

Qo'shimcha shifrlash va himoya qilish algoritmlari
Yuqoridagi muammolarni oldini olish uchun RSA ning amaliy qo'llanilishi odatda shifrlashdan oldin tuzilgan, tasodifiy to'ldirishning qandaydir shaklini inline qiladi. Bu kontent xavfli ochiq matnlar doirasiga kirmasligini va xabarni tasodifiy tanlash orqali topib bo'lmasligini ta'minlaydi.

RSA kriptotizimining xavfsizligi va axborotni shifrlash ikkita matematik masalaga asoslanadi: katta sonlarni faktoring muammosi va RSA muammosining o'zi. RSA-da shifrlangan matn va raqamli imzoning to'liq oshkor etilishi bu ikkala muammoni birgalikda hal qilib bo'lmaydi degan taxminda qabul qilinishi mumkin emas.

Biroq, asosiy omillarni tiklash qobiliyati tufayli, tajovuzkor ochiq kalitdan maxfiy ko'rsatkichni hisoblashi va keyin standart protsedura yordamida matnni parolini ochishi mumkin. Bugungi kunda klassik kompyuterda katta sonlarni faktorizatsiya qilishning mavjud usuli topilmagan bo'lsa-da, uning mavjud emasligi isbotlanmagan.
Avtomatlashtirish
Bu jarayonni soddalashtirish uchun Yafu deb nomlangan vositadan foydalanish mumkin. YAFU-da avtomatlashtirish - bu o'zboshimchalik bilan kiritilgan raqamlarning omillarini topish vaqtini minimallashtiradigan aqlli va moslashuvchan metodologiyada faktorizatsiya algoritmlarini birlashtirgan eng zamonaviy xususiyatdir. Algoritmning aksariyat ilovalari ko'p tarmoqli bo'lib, Yafu ko'p yoki ko'p (shu jumladan SNFS, SIQS va ECM) imkoniyatlaridan to'liq foydalanishga imkon beradi. Birinchidan, bu boshqariladigan buyruq qatori vositasi. Oddiy kompyuterda Yafu yordamida shifrlash omilini qidirish uchun sarflangan vaqt 103,1746 soniyagacha qisqartirilishi mumkin. Asbob 320 bit yoki undan ortiq sig'imga ega ishlov berishni ishlab chiqaradi. Bu o'rnatish va sozlash uchun ma'lum miqdordagi texnik ko'nikmalarni talab qiladigan juda murakkab dastur. Shunday qilib, RSA shifrlash C zaif bo'lishi mumkin.

Zamonaviy davrda xakerlik urinishlari

2009-yilda Benjamin Moody RSA-512 bit kalitidan foydalanib, faqat taniqli dasturiy ta'minot (GGNFS) va o'rtacha ish stoli kompyuteri (1900 MGts chastotada ikki yadroli Athlon64) yordamida kriptomatnni dekodlash ustida 73 kun davomida ishladi. Ushbu tajriba shuni ko'rsatdiki, "elakdan o'tkazish" jarayoni uchun 5 gigabayt diskdan sal kamroq va taxminan 2,5 gigabayt operativ xotira kerak bo'ldi.
2010 yil holatiga ko'ra, eng katta faktorlangan RSA raqami 768 bit uzunlikda edi (232 o'nlik raqam yoki RSA-768). Uning oshkor etilishi bir vaqtning o'zida bir necha yuzta kompyuterda ikki yil davom etdi.
Amalda, RSA kalitlari uzunroq, odatda 1024 dan 4096 bitgacha. Ba'zi ekspertlarning fikricha, 1024-bitli kalitlar yaqin kelajakda ishonchsiz bo'lib qolishi yoki hatto yaxshi moliyalashtirilgan tajovuzkor tomonidan buzilgan bo'lishi mumkin. Biroq, yaqin kelajakda 4096 bitli kalitlar ham paydo bo'lishi mumkinligi haqida kam odam bahslasha oladi.
istiqbollari
Shuning uchun, agar raqamlar etarlicha katta bo'lsa, RSA odatda xavfsiz deb hisoblanadi. Agar asosiy raqam 300 bit yoki undan qisqaroq bo'lsa, shifrlangan matn va raqamli imzo bir necha soat ichida shaxsiy kompyuterda bepul mavjud bo'lgan dasturiy ta'minot yordamida parchalanishi mumkin. 512-bitli kalitlarni 1999-yilda bir necha yuzlab kompyuterlar yordamida buzish mumkinligi ko'rsatilgan. Bu kunlarda keng tarqalgan uskuna yordamida bir necha hafta ichida buni amalga oshirish mumkin. Shunday qilib, kelajakda barmoqlardagi RSA shifrlash osongina fosh qilinishi va tizim umidsiz ravishda eskirib qolishi mumkin.
Rasmiy ravishda 2003 yilda 1024 bitli kalitlarning xavfsizligi so'roq qilingan. Hozirda uning uzunligi kamida 2048 bit bo'lishi tavsiya etiladi.
RSA ikki turdagi kalitlardan foydalanadi - e va d , bu erda e ochiq va d maxfiydir. Faraz qilaylik, P ochiq matn, C esa shifrlangan matn. Elis P ochiq matndan C shifrlangan matnni yaratish uchun C = P e mod n dan foydalanadi; Bob Elis tomonidan taqdim etilgan manba matnini (faylni) chiqarish uchun P = C d mod n dan foydalanadi. Juda ko'p sonli modullar n kalitlarni yaratish jarayoni yordamida yaratilgan, biz ularni keyinroq muhokama qilamiz.
Modulli eksponentatsiya shifrlash va shifrni ochish uchun ishlatiladi. 12-13-ma'ruzalarda aytib o'tganimizdek, tezkor algoritmdan foydalanganda ko'rsatkich modulini ko'pnomli vaqtda amalga oshirish mumkin. Biroq, modul logarifmini topish son modulini faktoring qilish kabi qiyin. Buning uchun polinomli vaqt algoritmi yo'q. Bu shuni anglatadiki, Elis xabarni polinom vaqtida ochiq kalit (e) bilan shifrlashi mumkin. Bob uni polinom vaqtida ham dekodlashi mumkin (chunki u d ni biladi). Ammo Momo Havo bu xabarni hal qila olmaydi, chunki u modulli arifmetika yordamida C ning elektron ildizini hisoblashi kerak edi. 14.5-rasmda RSA ortidagi g'oya ko'rsatilgan.