| RSA | |
|---|---|
| Yaratilgan | 1977 |
| Turi | kriptotizim |
RSA (familiyalarning bosh harflaridan olingan qisqartma: Rivest, Shamir va Adleman) — ochiq kalitli kriptografik algoritm bo‘lib, uning xavfsizligi hisoblash jihatidan murakkab bo‘lgan katta yarim tub sonlarni ko‘paytuvchilarga ajratishga asoslanadi.
RSA kriptotizimi ham shifrlash, ham raqamli imzo uchun yaroqli bo‘lgan birinchi tizimga aylandi. Algoritm ko‘plab kriptografik ilovalarda, jumladan PGP, S/MIME, TLS/SSL, IPsec/IKE va boshqalarda qo‘llanadi.
Tarixi
Ochiq va yopiq kalit yordamida shifrlash algoritmi Uitfild Diffi va Martin Xellmanga tegishli deb hisoblanadi; ular bu konsepsiyani 1976-yilda e'lon qilgan. Ular, shuningdek, raqamli imzo tushunchasini kiritib, sonlar nazariyasini qo‘llashga uringan. Ularning usulida modul bo‘yicha tub bo‘lgan biror sonni darajaga ko‘tarish orqali hosil qilingan umumiy maxfiy kalit ishlatilgan. Biroq ular bir tomonlama funksiyani amalga oshirish masalasini ochiq qoldirgan. Bunga o‘sha paytda sonni ko‘paytuvchilarga ajratishning murakkabligi yetarlicha o‘rganilmagani sabab bo‘lgan bo‘lishi mumkin.
Ron Rivest, Adi Shamir va Leonard AdlemanMassachusets texnologiya institutida bir yil davomida teskari hisoblash qiyin bo‘lgan bir tomonlama funksiyani yaratishga qayta-qayta urindilar. Kompyuter fanlari mutaxassislari Rivest va Shamir ko‘plab ehtimoliy funksiyalarni taklif qilishdi, matematik Adleman esa ularning zaif tomonlarini topish bilan shug‘ullandi. Ular «ryukzak» usuli va «o‘rin almashtirish ko‘phadlari» kabi turli yondashuvlarni sinab ko‘rishdi. Bir muddat ular qo‘yilgan talablar bir-biriga zidligi sababli maqsadga erishish mumkin emas, deb o‘ylashdi. 1977-yil aprelida ular talabalardan birining uyida Pesax bayramini nishonlab, ko‘p miqdorda Manishevits vinosini ichishdi va yarim tunga yaqin uylariga qaytishdi. Uyqusi kelmagan Rivest matematika darsligi bilan divanga yotib, bir tomonlama funksiyasi haqida o‘ylay boshladi. U tunning qolgan qismini o‘z g‘oyasini matematik jihatdan rasmiylashtirishga sarfladi; tongga kelib maqolaning katta qismi tayyor edi. Algoritm hozir RSA nomi bilan tanilgan — bu mualliflarning maqolada keltirilgan tartibdagi familiyalari bosh harflaridir.
Britaniya razvedka xizmati Hukumat aloqa shtab-kvartirasi (Government Communications Headquarters) (GCHQ)da ishlagan ingliz matematigi Klifford Koks 1973-yildagi ichki hujjatda shunga teng kuchli tizimni tavsiflagan. Ammo o‘sha davrda uni amalga oshirish uchun zarur kompyuterlar nisbatan qimmat bo‘lgani sababli bu tizim ko‘proq qiziqarli nazariy g‘oya sifatida qaralgan va ma'lum bo‘lishicha, amalda qo‘llanmagan. Koksning kashfiyoti o‘ta maxfiy saqlangani bois faqat 1997-yilda oshkor etilgan.
Avgust oyida, 1977-yilda Martin Gardnerning «Matematik o‘yinlar» ruknida, Scientific American jurnalida Ronald Rivest ruxsati bilan RSA kriptotizimining dastlabki tavsifi chop etildi. O‘quvchilarga tavsiflangan algoritm yordamida shifrlangan inglizcha iborani ochish ham taklif qilindi:
- 9686
- 1477
- 8829
- 7431
- 0816
- 3569
- 8962
- 1829
- 9613
- 1409
- 0575
- 9874
- 2982
- 3147
- 8013
- 9451
- 7546
- 2225
- 9991
- 6951
- 2514
- 6622
- 3919
- 5781
- 2206
- 4355
- 1245
- 2093
- 5708
- 8839
- 9055
- 5154
Tizimning ochiq parametrlari sifatida n=1143816...6879541 (129 ta o‘nlik raqam, 425 bit, shuningdek RSA-129 nomi bilan ma'lum) va e=9007 sonlari olingan. Shifrni ochgan kishiga 100 AQSH dollari mukofot va'da qilingan. Rivestning fikricha, bu sonni ko‘paytuvchilarga ajratishga 40 kvadrillion yildan ko‘proq vaqt ketishi kerak edi. Ammo oradan 15 yildan sal ko‘proq vaqt o‘tib, 3-sentabr 1993-yilda, quyidagi loyihaning ishga tushirilishi e'lon qilindi: taqsimlangan hisoblashlar loyihasi elektron pochta orqali muvofiqlashtirilgan bo‘lib, RSA-129 sonining ko‘paytuvchilarini topish va jumboqni yechishga qaratilgan edi. Yarim yil davomida 600 dan ortiq ko‘ngilli 20 mamlakatdan turib, 1600 ta mashinaning hisoblash vaqtini ajratdi (ulardan uchtasi faks apparati edi[manba 3988 kundan beri ko‘rsatilmagan]). Natijada tub ko‘paytuvchilar topildi va «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE[inglizcha]» («Sehrli so‘zlar — injiq jig‘altoy qushi») iborasidan iborat dastlabki xabar ochildi. G‘oliblar mukofot pulini Erkin dasturiy ta'minot jamg‘armasi.
Martin Gardner maqolasi e'lon qilingach, istagan kishi Ronald Rivestga o‘z manzili yozilgan va 35 sentlik pochta markasi yopishtirilgan konvert bilan so‘rov yuborib, yangi kriptotizimning to‘liq tavsifini olishi mumkin edi. Yangi kriptotizimning to‘liq tavsifi «Communications of the ACM» jurnalining 1978-yil fevral sonida chop etildi.
Patent olish uchun ariza 14-dekabr 1977-yilda topshirilgan, patent egasi sifatida MIT ko‘rsatilgan. 4405829-raqamli patent 20-sentabr 1983-yilda berilgan, 21-sentabr 2000-yilda esa amal qilish muddati tugagan. Biroq ixtirochilar AQSHdan tashqarida algoritmga patent olmaganlar, chunki aksariyat mamlakatlarda patent dastlabki nashrdan oldin olinishi kerak edi.
1982-yilda Rivest, Shamir va Adleman RSA Data Security[inglizcha] kompaniyasini tashkil etishdi (hozirda u EMC bo‘linmasi). 1989-yilda RSA simmetrik shifrlash algoritmi DES bilan birga RFC 1115da tilga olindi; shu tariqa algoritmdan shakllanayotgan internet tarmog‘ida foydalanish boshlandi. 1990-yilda esa AQSH Mudofaa vazirligi ham undan foydalana boshladi.
1993-yil noyabrida 1.5-versiyali standart ochiq e'lon qilindi: PKCS1[inglizcha]. Unda RSA yordamida shifrlash va elektron imzo yaratish tartibi tavsiflangan. Standartning keyingi versiyalari ham RFC (RFC 2313 — 1.5, 1993-yil; RFC 2437 — 2.0, 1998-yil; RFC 3447 — 2.1, 2002-yil) shaklida mavjud.
Dekabr oyida, 1997-yilda, Klifford Koksning ustuvorligi haqidagi ma'lumot oshkor qilindi.
Algoritm tavsifi
Kirish
Ochiq kalitli kriptografik tizimlarda bir tomonlama funksiyalar deb ataladigan funksiyalardan foydalaniladi. Ular quyidagi xususiyatga ega:
- agar ma'lum bo‘lsa, ni hisoblash nisbatan oson;
- agar ma'lum bo‘lsa, ni hisoblashning oddiy (samarali) usuli yo‘q.
Bir tomonlamalik deganda matematik jihatdan isbotlangan bir yo‘nalishlilik emas, balki hozirgi hisoblash vositalari bilan oqilona vaqt ichida teskari qiymatni amalda hisoblab bo‘lmasligi tushuniladi.
RSA ochiq kalitli kriptografik tizimining asosi ikkita katta tub son ko‘paytmasini ko‘paytuvchilarga ajratish masalasining murakkabligidir: ya'ni ikki katta tub sonning ko‘paytmasini ajratish qiyin. Shifrlashda modul bo‘yicha darajaga ko‘tarish amali katta son ustida bajariladi. Shifrni ochish (teskari amal)ni maqbul vaqt ichida bajarish uchun berilgan katta sonning Eyler funksiyasini hisoblash lozim; buning uchun sonning tub ko‘paytuvchilarga ajratilishini bilish kerak.
Ochiq kalitli kriptografik tizimda har bir ishtirokchining ochiq kaliti (ingl. public key) va yopiq kaliti (ingl. private key) bo‘ladi. RSA kriptografik tizimida har bir kalit ikkita butun sondan iborat. Har bir ishtirokchi ochiq va yopiq kalitlarini mustaqil yaratadi. Yopiq kalit sir saqlanadi, ochiq kalitlar esa istalgan kishiga berilishi yoki hatto e'lon qilinishi mumkin. RSA kriptotizimida xabar almashadigan ishtirokchining ochiq va yopiq kalitlari «mos keluvchi juftlik»ni tashkil etadi, ya'ni ular o‘zaro teskari bo‘ladi, boshqacha aytganda:
- ruxsat etilgan ochiq va yopiq kalitlar juftligining har biri uchun
- tegishli shifrlash funksiyalari va shifrni ochish funksiyalari mavjud bo‘lib, ular quyidagi shartni qanoatlantiradi:
- xabarlari uchun , bunda — ruxsat etilgan xabarlar to‘plami.
- xabarlari uchun , bunda — ruxsat etilgan xabarlar to‘plami.
- tegishli shifrlash funksiyalari va shifrni ochish funksiyalari mavjud bo‘lib, ular quyidagi shartni qanoatlantiradi:
Ochiq va maxfiy kalitlarni yaratish algoritmi
RSA kalitlari quyidagicha yaratiladi:
- 1) berilgan uzunlikdagi ikkita har xil tasodifiy tub son va tanlanadi (masalan, har biri 1024 bitdan iborat);
- 2) ularning ko‘paytmasi hisoblanadi; u modul deb ataladi;
- 3) Eyler funksiyasining qiymati hisoblanadi: :
- ;
- 4) shunday butun son tanlanadiki, u (), o‘zaro tub bo‘ladi — quyidagi funksiya qiymati bilan: ;
- . Ushbu soni ochiq eksponenta deb ataladi (ingl. public exponent);
- Odatda sifatida ikkilik yozuvida birlik bitlari kam bo‘lgan tub sonlar, masalan,
Fermatning tub sonlari: 17, 257 yoki 65537 tanlanadi, chunki bu holda
tez darajaga ko‘tarishdan foydalanilganda shifrlashga kamroq vaqt ketadi; - juda kichik qiymatlar , masalan, 3, RSA sxemasining xavfsizligini pasaytirishi mumkin;
- 5) quyidagi son hisoblanadi: , multiplikativ teskari bo‘lib, u soniga modul bo‘yicha teskari bo‘lishi kerak. Ya'ni quyidagi taqqoslama:
- bajariladi (son maxfiy eksponenta deb ataladi; odatda u kengaytirilgan Evklid algoritmi yordamida hisoblanadi);
- 6) juftlik RSA ochiq kaliti sifatida e'lon qilinadi (ingl. RSA public key);
- 7) juftlik RSA yopiq kaliti vazifasini bajaradi (ingl. RSA private key) va sir saqlanadi.
Shifrlash va shifrni ochish
Faraz qilaylik, Bob Alisaga .
Xabarlar butun sonlar bo‘lib, ular dan .

|
Shifrlash algoritmi:
|
Shifrni ochish algoritmi:
|
Ushbu sxema amalda qo‘llanmaydi, chunki u semantik jihatdan xavfsiz (semantically secured) emas. Haqiqatan ham, bir tomonlama E(m) funksiya deterministik — kirish parametrlarining (kalit va xabarning) bir xil qiymatlarida doimo bir xil natija beradi. Bu esa shifrning amaliy (semantik) xavfsizligi uchun zarur shart bajarilmasligini anglatadi.
Seans kalitini shifrlash algoritmi
Aralash shifrlash algoritmi ishonchliroq: unda avval seans kaliti shifrlanadi, keyin ishtirokchilar shu kalit yordamida xabarlarini simmetrik tizimlar orqali shifrlaydilar. Seans tugagach, seans kaliti odatda yo‘q qilinadi.
Seans kalitini shifrlash algoritmi quyidagicha:

|
Algoritm:
|
Algoritm:
|
Seans kaliti moduldan katta bo‘lsa, u kerakli uzunlikdagi bloklarga bo‘linadi (zarur bo‘lganda nol bilan to‘ldiriladi) va har bir blok alohida shifrlanadi.
RSA sxemasining to‘g‘riligi
- Tenglamalar va RSA sxemasi asosida yotadi va o‘zaro teskari almashtirishlarni quyidagi to‘plamda aniqlaydi:
Darhaqiqat,
Quyidagini ko‘rsatamiz:
- .
Ikki holat mumkin:
- .
Chunki va sonlari modul bo‘yicha ko‘paytirishga nisbatan o‘zaro teskari, ya'ni
- biror butun ,
u holda:
bunda ikkinchi ayniyat Fermaning kichik teoremasi.
- Ikkinchi holatni ko‘rib chiqamiz:
- ,
u holda
Shunday qilib, barcha uchun quyidagi tenglik bajariladi:
Xuddi shunday quyidagini ham ko‘rsatish mumkin:
- .
U holda qoldiqlar haqidagi Xitoy teoremasi
Misol
| Bosqich | Amal tavsifi | Amal natijasi |
|---|---|---|
| Kalitlarni yaratish | Ikkita turli tub sonni tanlash |
|
| Ko‘paytmani hisoblash |
| |
| Quyidagini hisoblash: Eyler funksiyasi |
| |
| Ochiq eksponentani tanlash |
| |
| Maxfiy eksponentani hisoblash |
| |
| E'lon qilish: ochiq kalit |
| |
| Sir saqlash: yopiq kalit |
| |
| Shifrlash | Shifrlash uchun matn tanlash |
|
| Shifrmatnni hisoblash |
| |
| Shifrni ochish | Dastlabki xabarni hisoblash |
|
Raqamli imzo
RSA tizimidan nafaqat shifrlash, balki raqamli imzo yaratishda ham foydalanish mumkin.
Faraz qilaylik, Alisa ( tomon) Bobga ( tomon) xabarini elektron raqamli imzo bilan tasdiqlab yuborishi kerak.

|
Algoritm:
|
Algoritm:
|
Chunki raqamli imzo xabar muallifining autentifikatsiyasini hamda imzolangan xabarning yaxlitligini tasdiqlaydi, shu bois u qo‘lyozma hujjat oxiridagi qo‘l imzosiga o‘xshash vazifani bajaradi.
Raqamli imzoning muhim xususiyati shundaki, uni muallifning ochiq kalitiga ega bo‘lgan har qanday kishi tekshirishi mumkin. Xabar almashinuvi ishtirokchilaridan biri raqamli imzo haqiqiyligini tekshirgandan so‘ng imzolangan xabarni imzoni tekshira oladigan boshqa kishiga ham yuborishi mumkin. Masalan, tomon tomonga elektron chek yuborishi mumkin. tomon chekdagi tomonning imzosini tekshirgach, chekni o‘z bankiga topshirishi mumkin; bank xodimlari ham imzoni tekshirishi va tegishli pul operatsiyasini bajarishi mumkin.
E'tibor bering, imzolangan xabar shifrlanmagan. U dastlabki ko‘rinishda uzatiladi va mazmuni maxfiyligi himoyalanmagan bo‘ladi. RSA tizimida yuqorida bayon etilgan shifrlash va raqamli imzo sxemalarini birgalikda qo‘llash orqali ham shifrlangan, ham raqamli imzoga ega xabarlarni yaratish mumkin. Buning uchun muallif avval xabarga o‘z raqamli imzosini qo‘shadi, so‘ng hosil bo‘lgan juftlikni (xabar va unga tegishli imzoni) qabul qiluvchining ochiq kaliti bilan shifrlaydi. Qabul qiluvchi esa kelgan xabarni o‘z maxfiy kaliti bilan ochadi. Oddiy qog‘oz hujjat yuborishga qiyoslasak, bu hujjat muallifi avval hujjatga muhr bosib, keyin uni qog‘oz konvertga solib, konvertni faqat mo‘ljallangan qabul qiluvchi ochishi uchun yopishtirishiga o‘xshaydi.
RSA algoritmining ishlash tezligi
Kalitlar shifrlash, shifrni ochish, raqamli imzo yaratish va uni tekshirish amallariga qaraganda ancha kam yaratilgani uchun ni hisoblash asosiy hisoblash murakkabligini tashkil etadi. Bu masalani tez darajaga ko‘tarish algoritmi yordamida yechish mumkin. Ushbu algoritm yordamida ni hisoblash uchun ta modul bo‘yicha ko‘paytirish.
- Quyidagini ikkilik sanoq sistemasida ifodalaymiz:
- , bunda
- deb belgilaymiz: , so‘ng uchun quyidagini hisoblaymiz:
- Hosil bo‘lgan izlanayotgan
bo‘ladi. 2-bosqichdagi har bir hisoblash modul bo‘yicha ko‘pi bilan uchta ko‘paytirishni talab qilgani va bu bosqich marta bajarilgani uchun algoritm murakkabligini .
bilan baholash mumkin. Ochiq va yopiq kalitlar bilan bajariladigan amallar vaqtini tahlil qilish uchun ochiq kalit va yopiq kalit quyidagi munosabatlarga mos keladi, deb faraz qilaylik: , . Ularni qo‘llashda mos ravishda va ta modul bo‘yicha ko‘paytirish amali bajariladi.
Shunday qilib, amallarning bajarilish vaqti ikkilik ifodadagi ochiq eksponenta ening noldan farqli bitlari soni ortishi bilan ko‘payadi. Shifrlashni tezlashtirish uchun e qiymati ko‘pincha 17, 257 yoki 65537 deb tanlanadi — bu tub sonlar bo‘lib, ularning ikkilik yozuvida atigi ikkita birlik mavjud: 1710=100012, 25710=1000000012, 6553710=100000000000000012 (tub Fermat sonlari).
Evristik baholashlarga ko‘ra, maxfiy eksponenta ning uzunligi ochiq eksponenta va modul ga murakkab tarzda bog‘liq bo‘lib, katta ehtimol bilan uzunligiga yaqin. Shu sababli ma'lumotni ochish shifrlashdan sekinroq, imzoni tekshirish esa imzo yaratishdan tezroq bajariladi.
RSA algoritmi AES yoki simmetrik blokli shifrlar bilan ishlaydigan boshqa algoritmlarga qaraganda ancha sekin ishlaydi.
Shifrni ochishni tezlashtirish uchun qoldiqlar haqidagi Xitoy teoremasidan foydalanish
RSA algoritmida xabarni ochish yoki imzolashda daraja ko‘rsatkichi juda katta son (taxminan 1000 bit) bo‘ladi. Shu sababli amallar sonini kamaytiruvchi algoritm kerak. Chunki va sonlar sonning ko‘paytuvchilari bo‘lib, yopiq kalit egasiga ma'lum, quyidagilarni hisoblash mumkin:
Chunki va taxminan kattalikdagi sonlar, bu amallar uchun 512 bitli sonni 512 bitli modul bo‘yicha darajaga ko‘tarish ikki marta bajariladi. Bu 1024 bitli misolda 3 baravar tezroq bo‘lgan; bunda bitta 1024 bitli sonni 1024 bitli modul bo‘yicha darajaga ko‘tarish o‘rniga ikkita kichik amal bajariladi. Keyin ni va orqali tiklash mumkin; buning uchun qoldiqlar haqidagi Xitoy teoremasi qo‘llanadi.
RSA kriptotahlili
Algoritmning bardoshliligi shifrlash funksiyasiga teskari funksiyani hisoblashning qiyinligiga asoslanadi.
- .
Xabarni tiklash, ya'ni ni ma'lum parametrlar orqali hisoblash uchun ( ) shunday sonni topish kerakki,
ya'ni teskari elementni uchun qoldiqlarning multiplikativ guruhidan quyidagi modul bo‘yicha topish kerak:
Modul bo‘yicha teskari elementni hisoblash qiyin emas, ammo hujumchi ning qiymatini bilmaydi. Eyler funksiyasining ma'lum son uchun qiymatini hisoblashda uning tub ko‘paytuvchilarga ajratilishini bilish kerak. Bunday ko‘paytuvchilarni topish qiyin, ularni bilish esa «yashirin eshik» (ingl. backdoor) bo‘lib, undan kalit egasi ni hisoblashda foydalanadi. Tub ko‘paytuvchilarni topish, ya'ni faktorizatsiya uchun ko‘plab algoritmlar mavjud. Hozirda ularning eng tezkori — sonlar maydonining umumiy g‘alvir usuli bo‘lib, k bitli butun son uchun uning ishlash tezligi quyidagicha ifodalanadi:
- , bu yerda .
2010-yilda Shveysariya, Yaponiya, Fransiya, Niderlandiya, Germaniya va AQSH olimlari guruhi 768 bitli RSA standartidagi kriptografik kalit bilan shifrlangan ma'lumotlarni muvaffaqiyatli ochishga erishdi. Tub ko‘paytuvchilarni topishda sonlar maydonining umumiy g‘alvir usuli qo‘llanildi. Tadqiqotchilar fikricha, shundan so‘ng faqat uzunligi 1024 bit va undan ortiq bo‘lgan RSA kalitlarini ishonchli shifrlash tizimi sifatida qarash mumkin edi. Ular yaqin uch-to‘rt yil ichida 1024 bitli kalitdan ham voz kechish lozimligini ta'kidlashdi. 31-dekabr 2013-yildan boshlab Mozilla brauzerlari RSA kaliti 2048 bitdan qisqa bo‘lgan sertifikatlashtirish markazlari sertifikatlarini qo‘llab-quvvatlashni to‘xtatdi.
Bundan tashqari, algoritm noto‘g‘ri yoki optimal bo‘lmagan usulda amalga oshirilsa yoki ishlatilsa, maxfiy eksponentasi kichik bo‘lgan sxemalarga yoki bir xil modul qiymatidan foydalanadigan sxemalarga hujumlar kabi maxsus kriptografik hujumlar yuzaga kelishi mumkin.
RSA algoritmiga hujumlar
RSA ga Viner hujumi
Ayrim ilovalarda RSA orqali shifrni ochish jarayonini tezlashtirish talab etiladi. Shu bois shifrni ochish uchun kichik eksponenta tanlanadi. Agar shifrni ochish eksponentasi bo‘lsa, ni Viner hujumi yordamida polinomial vaqt ichida aniqlash mumkin; buning uchun uzluksiz kasrlardan foydalaniladi.
bo‘lganda
Butun sonlar ketma-ketligi uzluksiz kasr deb ataladi va sonni ifodalaydi; ratsional sonlar esa mos kasrlar deyiladi. Har bir mos kasr qisqarmas, uning maxraji eksponensialga yaqin tezlikda o‘sadi.
Quyidagi fikr uzluksiz kasrlar nazariyasining muhim natijasidir:
u holda quyidagi sonning yoyilmasidagi mos kasrlardan biridir: ning uzluksiz kasrga yoyilmasi.
Faraz qilaylik, modul berilgan va bo‘lsin. Hujumchiga quyidagi xususiyatga ega E shifrlash eksponentasi ma'lum deb olaylik:bu yerda Shuningdek, deb hisoblaymiz, chunki ko‘pchilik ilovalarda shunday. Farazlardan quyidagilar kelib chiqadi:
Demak,
Bundan ko‘rinadiki, son ga juda yaqinlashadi. Haqiqatan ham,
Chunki , ravshanki, Bundan tashqari, deb faraz qilingan. Demak,
Chunki EKUB, demak, kasr quyidagi nisbatning yoyilmasidagi mos kasrdir: ning uzluksiz kasrga yoyilmasi kasrga yoyilmasidagi mos kasrdir. Shunday qilib, mos kasrlarning maxrajlarini navbat bilan quyidagi ifodaga qo‘yib, shifrni ochish eksponentasini topish mumkin:
biror tasodifiy son uchun. Tenglik topilgach, topiladi. Tekshiriladigan mos kasrlarning umumiy soni
Umumlashtirilgan Viner hujumi
Viner hujumi yuqorida tavsiflangan ko‘rinishda faqat hujumchiga quyidagi tengsizlik ma'lum bo‘lsa amalga oshirilishi mumkin:
bunda — maxfiy eksponenta, — RSA moduli. Bone va Derfi Koppersmit teoremasining ikki o‘lchovli analogidan foydalanib, Viner hujumini quyidagi holatga umumlashtirdilar:
Vositachi hujumi yoki «o‘rtadagi odam» hujumi
Vositachi hujumi hujumchi ochiq kalit uzatiladigan aloqa kanalini faqat tinglay olganida xavf tug‘dirmaydi. Bu holda hujumchi ochiq kalitni, shifrlangan xabarlar va imzolarni tutib olishi mumkin. Ammo u kalitni tutib olgach, aloqa kanali orqali xabar yubora olsa, soxta xabarlarni jo‘natishi mumkin.
RSA dan foydalanish
RSA tizimidan dasturiy ta'minotni himoyalash va raqamli imzo sxemalarida foydalaniladi.
Shuningdek, u ochiq shifrlash tizimi PGP hamda boshqa shifrlash tizimlarida (masalan, DarkCryptTC va xdc formatida) simmetrik algoritmlar bilan birga qo‘llanadi.
RSA algoritmining shifrlash tezligi past bo‘lgani sababli xabarlar odatda tasodifiy seans kalitidan foydalanadigan tezroq simmetrik algoritmlar yordamida shifrlanadi (masalan, AES, IDEA, Serpent, Twofish), RSA bilan esa faqat shu kalit shifrlanadi. Natijada gibrid kriptotizim yaratiladi. Mazkur yondashuvning ehtimoliy zaifligi shundaki, tasodifiy seans kalitini yaratishda kriptografik jihatdan bardoshli psevdotasodifiy sonlar generatoridan foydalanish talab qilinadi.
Adabiyotlar
- Diffie W., Hellman M. E. Kriptografiyaning yangi yo‘nalishlari (New Directions in Cryptography) (ingl.) // IEEE axborot nazariyasi bo‘yicha ishlari (IEEE Transactions on Information Theory) / F. Kschischang — IEEE, 1976. — Jild 22, son 6. — B. 644—654. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1976.1055638
- Gardner M. Shifrning yangi turi: uni buzishga millionlab yillar kerak bo‘ladi (A New Kind of Cipher that Would Take Millions of Years to Break) (ingl.) // Scientific American — Nyu-York: NPG, 1977. — Jild 237, son 2. — B. 120—124. — 5 b. — ISSN 0036-8733; 1946-7087 — doi:10.1038/SCIENTIFICAMERICAN0877-120
- Rivest R., Shamir A., Adleman L. Raqamli imzolar va ochiq kalitli kriptotizimlarni yaratish usuli (A method for obtaining digital signatures and public-key cryptosystems) (ingl.) // Communications of the ACM — Nyu-York: Hisoblash texnikasi assotsiatsiyasi (Association for Computing Machinery), 1978. — Jild 21, son 2. — B. 120—126. — ISSN 0001-0782; 1557-7317 — doi:10.1145/359340.359342
- Menezes A. J., van Oorschot P., Vanstone S. A. Amaliy kriptografiya qo‘llanmasi (Handbook of Applied Cryptography) (ingl.) — Boka-Raton: CRC Press, 1996. — 816 b. — (Diskret matematika va uning qo‘llanishlari (Discrete Mathematics and Its Applications)) — ISBN 978-0-8493-8523-0
- Boneh D. RSA kriptotizimiga hujumlarning yigirma yillik tarixi (Twenty Years of attacks on the RSA Cryptosystem) (ingl.) // Amerika matematika jamiyati xabarnomasi (Notices of the American Mathematical Society) / F. Morgan — AMS, 1999. — Jild 46, son 2. — B. 203–213. — ISSN 0002-9920; 1088-9477
- Bakhtiari M., Maarof M. A. RSA kriptotizimidagi jiddiy xavfsizlik zaifligi (Serious Security Weakness in RSA Cryptosystem) (ingl.) // Kompyuter fanlari muammolari xalqaro jurnali (International Journal of Computer Science Issues) — 2012. — Jild 9, son 1, № 3. — B. 175—178. — ISSN 1694-0814; 1694-0784; 1694-0814
- Nils Fergyuson, Bryus Shnayer. Amaliy kriptografiya = Amaliy kriptografiya: xavfsiz kriptografik tizimlarni loyihalash va amalga oshirish (Practical Cryptography: Designing and Implementing Secure Cryptographic Systems). — Moskva : Dialektika, 2004. — 432 b. — 3000 nusxa — ISBN 5-8459-0733-0, ISBN 0-4712-2357-3.
- Shnayer B. Amaliy kriptografiya. Protokollar, algoritmlar va C tilidagi dastlabki kodlar = Amaliy kriptografiya. Protokollar, algoritmlar va C tilidagi dastlabki kodlar (Applied Cryptography. Protocols, Algorithms and Source Code in C). — Moskva: Triumf, 2002. — 816 b. — 3000 nusxa — ISBN 5-89392-055-4.