Zamonaviy tarmoqlarda RSA algoritmi
Reja:
Tarixi
Kirish
RSA kalitlari va ma'lumotlarni shifrlash
RSA xabarlarini shifrlash
RSA ma'lumotlarini imzolash
Xulosa
Foydalanilgan adabiyotlar
Ommaviy-xususiy kalitlarni shifrlash algoritmi kontseptsiyani 1976 yilda nashr etgan Uitfild Diffi va Martin Xelmanga tegishli . Shuningdek, ular raqamli imzolarni joriy qilishdi va raqamlar nazariyasini qo'llashga harakat qilishdi. Ularning formulasi ba'zi modulli tub sonlarni eksponensiallashtirish orqali yaratilgan umumiy maxfiy kalitdan foydalangan. Biroq, ular bir tomonlama funktsiyani amalga oshirish muammosini ochiq qoldirdilar, ehtimol, faktorizatsiyaning murakkabligi o'sha paytda yaxshi tushunilmagan.
MITdagi Ron Rivest, Adi Shamir va Leonard Adleman bir yil davomida invertatsiya qilish qiyin bo'lgan bir tomonlama funktsiyani yaratishga bir necha bor urinishgan. Rivest va Shamir kompyuter olimlari sifatida ko'plab potentsial funktsiyalarni taklif qilishdi va matematik bo'lgan Adleman ularning zaif tomonlarini topishga mas'ul edi. Ular turli xil yondashuvlarni sinab ko'rdilar, jumladan, "xalta" va "o'zgartirish polinomlari". Bir muncha vaqt ular bir-biriga zid bo'lgan talablar tufayli erishmoqchi bo'lgan narsa imkonsiz deb o'ylashdi. 1977 yil aprel oyida ular Fisih bayramini talabalardan birining uyida o'tkazdilar va ko'p Manischewitz sharobini ichishdi, keyin yarim tunda uylariga qaytishdi. Rivest uxlay olmay, matematika darsligi bilan divanga yotib, o‘zining bir tomonlama funksiyasi haqida o‘ylay boshladi. U tunning qolgan qismini o‘z g‘oyasini rasmiylashtirish bilan o‘tkazdi va tongga yaqin qog‘ozning katta qismi tayyor bo‘ldi. Algoritm endi RSA deb nomlanadi - familiyalarining bosh harflari qog'ozdagi kabi tartibda.
Britaniya razvedka xizmati Hukumat Aloqa Bosh qarorgohida (GCHQ) ishlaydigan ingliz matematigi Klifford Koks 1973 yilda ichki hujjatda ekvivalent tizimni tasvirlab berdi. Biroq, o'sha paytda uni amalga oshirish uchun nisbatan qimmat kompyuterlar talab qilinganini hisobga olsak, u ko'p jihatdan tizim deb hisoblanardi. qiziquvchanlik va, Ma'lumki, u hech qachon ishlatilmagan. Biroq, uning kashfiyoti faqat 1997 yilda o'ta kuchli tasnifi tufayli aniqlandi.
1977 yil avgust oyida RSA kriptotizimining birinchi tavsifi Scientific American jurnalida Martin Gardnerning Matematik oʻyinlari ustunida Ronald Rivest \ ruxsati bilan paydo boʻldi . Shuningdek, o'quvchilardan tasvirlangan algoritm tomonidan shifrlangan inglizcha iborani ochish so'ralgan:
Asimmetrik RSA kriptografiya algoritmi, kelib chiqishi 1976 yil deb hisoblanadi, hozirda ma'lumotlar almashinuvi, dasturiy ta'minot manbasini tekshirish va ma'lumotlar almashinuvi yoki jo'natuvchini tekshirish zarur bo'lgan boshqa sohalarda juda faol qo'llaniladi. Bundan tashqari, u HTTPS protokolining asosiy qismi bo'lib, Yandex.Radar ma'lumotlariga ko'ra Rossiyada foydalanish 98% ga yetdi .
Masalan, sevimli buvingizga mashhur messenjer orqali qo'ng'iroq qilganda yoki onlayn bozorda bank kartangiz ma'lumotlarini kiritganda, video tasvir yoki bank kartasi ma'lumotlarini almashishdan oldin, autentifikatsiya jarayoni amalga oshiriladi va RSA algoritmi yordamida shifrlash kaliti almashtiriladi.
Lekin bu qanday algoritm va u qanday ishlaydi? Ushbu maqolada men uning ishlashining asosiy tamoyillarini va umuman assimetrik kriptografiyani buzishga harakat qilaman.
RSA kalitlari va ma'lumotlarni shifrlash
Axborotni shifrlash va shifrini ochish uchun faqat bitta kalitga ega bo'lgan simmetrik shifrlash algoritmlaridan farqli o'laroq, RSA algoritmi 2 ta kalitdan foydalanadi - ochiq (ommaviy) va shaxsiy (xususiy).
Ochiq shifrlash kaliti ochiq aloqa kanallari orqali uzatiladi, shaxsiy kalit esa har doim sir saqlanadi. Lekin nima uchun sizga ikkita kalit kerak va ular qanday ishlaydi?
Asimmetrik kriptografiya va RSA algoritmida, xususan, ochiq va yopiq kalitlar bir butunning ikki qismi bo'lib, bir-biridan ajralmasdir. Axborotni shifrlash uchun ochiq kalit, uni ochish uchun esa shaxsiy kalit ishlatiladi.
Aytaylik, Bob Elisga xabar yubormoqchi, lekin u buni shaxsan qila olmaydi, shuning uchun u Stiv kabi vositachidan foydalanishi kerak. Biroq, Bob Elisga tug'ilgan kunida Stiv uchun kutilmagan sovg'a haqida ma'lumot beradi, shuning uchun u Stivga bu xabarni ko'rishga ruxsat bera olmaydi. Va bu erda RSA protokoli yordam beradi.
Xabar almashishdan oldin Bob Elisdan ochiq kalitini so'raydi.
Stiv orqali uzatilgan kalitni olgandan so'ng, Bob o'z xabarini Elisning kaliti bilan shifrlaydi
Keyin Bob Stiv orqali Elisga shifrlangan xabar yuboradi
Elis o'zining shaxsiy kaliti bilan xabarni hal qiladi
Shunday qilib, Stiv Elisning ochiq kalitini va Bobdan shifrlangan xabarni ko'rdi, ammo Elisning shaxsiy kalitisiz xabarni shifrlab bo'lmaydi. Ya'ni, Stiv barcha uzatilgan ma'lumotlarni qo'lida ushlab tursa ham, Bob Elisga nimani uzatganini topa olmaydi!
Vizual diagramma:
RSA xabarlarini shifrlash
Sizni qiziqtirgandirsiz, nega Stiv Elisning kalitini o'z kalitiga almashtira olmaydi, xabarning shifrini ochadi va keyin josuslik qilgandan so'ng uni Elisning kaliti bilan qayta shifrlay olmaydi? U o'rtadagi odam (MITM) hujumi deb ham ataladi va u quyidagicha ko'rinadi:
MITM
Ammo bu muammoning yechimi bormi? Ha! Ishonch zanjiri yoki "Ishonch zanjiri"
Ma'lumotlar imzosi va ishonch zanjiri
"Ishonch zanjiri" nima ekanligini tushunishdan oldin, siz shaxsiy kalitning yana bir imkoniyati - ma'lumotni imzolash haqida bilishingiz kerak. Bu shaxsiy kalit yordamida amalga oshiriladi va ochiq kalit tomonidan tasdiqlanadi.
Ya'ni, agar Bob va Elis ilgari ochiq kalitlarini almashtirgan bo'lsa, ular bir-biriga xabar yozishlari va ularga ma'lum ma'lumotlar to'plamini biriktirishlari mumkin. Agar siz ushbu ma'lumotlar to'plamini, ochiq kalitni va xabarning o'zini olsangiz, xabar haqiqatan ham suhbatdosh tomonidan yuborilganmi yoki yo'lda kimdir uni almashtirganmi yoki yo'qligini tekshirishingiz mumkin.
RSA ma'lumotlarini imzolash
Biz shaxsiy kalitni imzolash funktsiyasini aniqladik, bu juda foydali narsa! Ammo bu o'rtadagi odam muammosini qanday hal qiladi, chunki agar Bob va Elis vositachilarsiz ochiq kalitlarni almashtira olmasalar, Stiv uzatish paytida ularni almashtira oladi va doimiy ravishda xabarlarni ushlab turishi mumkin?
Bu oddiy! Maxfiy kalit yordamida ba'zi ma'lumotlarni imzolashingiz mumkin bo'lganligi sababli, umumiy kalitni o'zi imzolash uchun undan foydalanishingiz mumkin.
Agar Bob va Elis ishonishi mumkin bo'lgan va ochiq kalitga ega bo'lgan Grant bo'lsa, Grant ochiq kalitlarga imzo chekishi mumkin. Shunday qilib, agar Stiv Bobga yuborgan Elisning ochiq kalitini almashtirishga harakat qilsa, Bob almashtirishni darhol aniqlaydi, chunki Grantning imzosi kalitda bo'lmaydi.
Grant ochiq kalitni Markga ham imzolashi mumkin, u Bob va Elisning ochiq kalitlariga imzo chekadi va shu bilan xuddi shunday "ishonch zanjiri" ni yaratadi.
Haqiqiy dunyoda ishonchli ildiz CA (Grant), oraliq CA (Mark) va yakuniy oluvchilar (Bob va Elis) mavjud.
Ishonch zanjiri
Murosa va bekor qilishning asosiy ro'yxati
Keling, Elis o'zining shaxsiy kalitini ko'rinadigan joyda qoldirgan deb faraz qilaylik, Stiv buni ko'rdi va endi har qanday xabarlarga imzo chekishi, shuningdek, Elisning ochiq kaliti bilan shifrlangan barcha ma'lumotlarni ushlab turishi va shifrini ochishi mumkin. Ushbu muammo "Kalit kelishuvi" deb ataladi.
Bunday holda, aqlli odamlar "Sertifikatlarni bekor qilish ro'yxati (CRL)" ni ishlab chiqdilar, unda endi ishonchli bo'lmagan buzilgan kalitlar nashr etiladi.
Bunday bekor qilish ro'yxati joylashgan manzil barcha ildiz va oraliq sertifikat organlariga kiritilgan. Ya'ni, agar Elis Stiv o'zining shaxsiy kalitini ko'rganidan shubhalansa, u darhol Markga uning sertifikat raqamini bekor qilish ro'yxatida e'lon qilishini aytadi. Bob, o'z navbatida, Stiv foydalanmoqchi bo'lgan eski sertifikatni olgach, Markning ro'yxatida uning bekor qilinganligi haqidagi yozuvni topadi va Elis buzilganligini va uning eski sertifikatiga endi ishonib bo'lmasligini tushunadi.
Sertifikatdagi CRL
Kaput ostida
RSA algoritmining asosiy jihatlari aniqlangandan so'ng, keling, "kaput ostida" ni ko'rib chiqamiz va bu sehr qanday ishlashini ko'rib chiqamiz.
Barcha assimetrik kriptografiya "bir yo'nalishda tez, boshqa yo'nalishda asossiz uzoq" tamoyiliga asoslanadi.
Masalan, 592939 va 592967 sonlarini ko'paytirsak, 351593260013 sonini olamiz.Lekin faqat 351593260013 raqami bilan 592939 va 592967 sonlarini qanday topish mumkin? Agar bu ikki raqamning har biri 1000 belgidan ortiq bo'lsa-chi? Bu " ikkita katta tub sonlar mahsulotini faktorizatsiya qilish muammosining murakkabligi " deb ataladi, ya'ni. bir yo'li oson, ikkinchisi esa nihoyatda qiyin.
Endi umumiy va shaxsiy kalitlarni yaratish tartibini ko'rib chiqamiz:
Ikki tasodifiy tub sonni tanlang p va q
Biz ularning mahsulotini hisoblaymiz: N = p * q
Eyler funksiyasini hisoblaymiz : (N) = (p-1) * (q-1)
Biz e raqamini (odatda tub, lekin shart emas) tanlaymiz, u (N) dan kichik va (N) bilan ko'paytiriladi (1dan tashqari bir-biri bilan umumiy omillarga ega emas).
Biz e sonining teskari moduli (N) d raqamini qidiramiz.Ya'ni, bo'linishning qolgan qismi (d*e) va (N) 1 ga teng bo'lishi kerak. Uni kengaytirilgan Evklid algoritmi yordamida topishingiz mumkin (spoiler ostida)
Kengaytirilgan Evklid algoritmi
Hisob-kitoblarni amalga oshirgandan so'ng, biz quyidagilarga ega bo'lamiz:
e va n - ochiq kalit
d va n - shaxsiy kalit
Keling, misol tariqasida kichik tub sonlardan foydalanib, ushbu kalitlarni yaratamiz:
p = 19, q = 41 bo'lsin
Ma'lum bo'lishicha:
{691, 779} – ochiq kalit
{571, 779} – shaxsiy kalit
Biz kalitlarni aniqladik, endi xabarlarni shifrlashga o'tamiz.
Faraz qilaylik, Bob Elisdan bugun ziyofat soat nechada ekanligini so'radi. Elis ziyofat 21 yoshda ekanligini biladi, lekin buni Stiv bilmasdan Bobga etkazish uchun u nima qilishi kerak?
Buni amalga oshirish uchun Elis Bobning ochiq kalitini bilishi kerak, keling, uni oldingi hisob-kitoblardan olamiz {691, 779}. Keyinchalik, u e (691) mod n (779) quvvatiga xabarni ko'tarishi kerak va Bob keyin Elisdan olingan raqamni d (571) mod n (779) quvvatiga ko'tarishi kerak. Keling, buni tasavvur qilaylik
Xulosa
Biz RSA kriptografik algoritmining asosiy jihatlarini ko'rib chiqdik, lekin ko'p narsa sahna ortida qoldi; Umid qilamanki, men kriptografiya va shunga o'xshash narsalardan juda uzoq bo'lganlar uchun ham uning qanday ishlashini etarlicha aniq tushuntira oldim.
Foydalanilgan adabiyotlar.
Internet saxifalari: https://ru.wikipedia.org/wiki/RSA ;
|
