|
Kriptografiyaning maqsadi
|
| bet | 7/13 | | Sana | 30.07.2023 | | Hajmi | 225.22 Kb. | | #77651 |
Bog'liq Axborotni kriptografik himoya qilish vositalari IKKILAMCHI ELEKTRON EMISSIYASI, Axborot Himoya Kriptografik Usullari9.6.3. Algoritm R.S.A. RSA (mualliflar Rivest, Shamir va Alderman nomi bilan atalgan) shifrlash va autentifikatsiya (raqamli imzo) uchun mo'ljallangan ochiq kalit algoritmidir. Bu algoritm 1977-yilda ishlab chiqilgan va katta butun sonlarni tub omillarga (faktorizatsiya) parchalashga asoslangan.
RSA juda sekin algoritmdir. Taqqoslash uchun, dasturiy ta'minot darajasida DES RSA dan kamida 100 marta tezroq; apparatda - amalga oshirilishiga qarab 1000-10 000 marta.
RSA algoritmi quyidagicha. Ikkita juda katta tub sonni oling p va q. Belgilangan n ko'paytirish natijasida p ustida q(n=p q). Katta tasodifiy butun sonni tanlang d, bilan tenglashtiring m, qayerda
. Bu raqam belgilangan e, nima
. Keling, uni ochiq kalit deb ataymiz. e va n, va maxfiy kalit raqamlardir d va n.
Endi ma'lumotni ma'lum kalit bilan shifrlash uchun ( e,n), quyidagilarni bajaring:
shifrlangan matnni bloklarga bo'ling, ularning har biri raqam sifatida ifodalanishi mumkin M(i)=0,1,…,n-1;
raqamlar ketma-ketligi sifatida qabul qilingan matnni shifrlash M(i) formula bo'yicha C(i)=(M(i)) mod n;
maxfiy kalit yordamida ushbu ma'lumotlarni shifrini ochish uchun ( d,n), quyidagi hisob-kitoblarni bajarish kerak M(i)=(C(i)) mod n.
Natijada raqamlar to'plami bo'ladi M(i) asl matnni ifodalovchi.
Misol. Xabarni shifrlash uchun RSA usulidan foydalanishni ko'rib chiqing: "kompyuter". Oddiylik uchun biz juda kichik raqamlardan foydalanamiz (amalda ancha katta raqamlar qo'llaniladi - 200 va undan yuqori).
Keling, tanlaymiz p=3 va q=11. Keling, aniqlaymiz n=3×11=33.
topamiz ( p-1)×( q-1)=20. Shuning uchun, kabi d masalan, 20 ga nisbatan tub bo'lgan istalgan sonni tanlang d=3.
Raqamni tanlang e. Bunday raqam sifatida har qanday raqam olinishi mumkin, bu bilan bog'liqlik (( e×3) mod 20=1, masalan, 7.
Shifrlangan xabarni 1…32 diapazonidagi butun sonlar ketma-ketligi sifatida taqdim qilaylik. "E" harfi 30 raqami, "B" harfi 3 raqami va "M" harfi 13 raqami bilan ifodalansin. Keyin asl xabarni raqamlar ketma-ketligi (30 03 13) sifatida ko'rsatish mumkin. ).
(7,33) kalit yordamida xabarni shifrlaymiz.
S1=(307) mod 33=21870000000 mod 33=24,
C2=(37) mod 33=2187 mod 33=9,
C3=(137) mod 33=62748517 mod 33=7.
Shunday qilib, shifrlangan xabar (24 09 07) ko'rinadi.
Keling, teskari masalani hal qilaylik. Keling, maxfiy kalit (3.33) asosida ma'lum kalit bilan shifrlash natijasida olingan xabarni (24 09 07) shifrini ochamiz:
M1=(24 3) mod 33=13824 mod 33=30,
M2=(9 3) mod 33=739 mod 33=9,
M3=(7 3)mod33=343mod33=13 .
Shunday qilib, xabarning shifrini ochish natijasida "kompyuter" asl xabari olindi.
RSA algoritmining kriptografik kuchi ma'lum bo'lganidan maxfiy kalitni aniqlash juda qiyin degan taxminga asoslanadi, chunki buning uchun butun son bo'linuvchilari mavjudligi muammosini hal qilish kerak. Bu muammo NP-to'liq va bu haqiqatning natijasi sifatida hozirda samarali (polinom) yechimni tan olmaydi. Bundan tashqari, NP-to'liq muammolarni hal qilish uchun samarali algoritmlarning mavjudligi haqidagi savol hali ham ochiq. Shu munosabat bilan, 200 ta raqamdan iborat raqamlar uchun (masalan, bunday raqamlardan foydalanish tavsiya etiladi) an'anaviy usullar juda ko'p operatsiyalarni talab qiladi (taxminan 1023).
RSA algoritmi (9.2-rasm) AQShda patentlangan. Boshqa shaxslar tomonidan foydalanishga yo'l qo'yilmaydi (agar kalit uzunligi 56 bitdan ortiq bo'lsa). To'g'ri, bunday muassasaning haqiqiyligini shubha ostiga qo'yish mumkin: oddiy eksponentsiyani qanday patentlash mumkin? Biroq, RSA mualliflik huquqi qonunlari bilan himoyalangan.
Guruch. 9.2. Shifrlash sxemasi
Abonentning ochiq kaliti yordamida shifrlangan xabarni faqat uning o'zi hal qilishi mumkin, chunki maxfiy kalit faqat unga ega. Shunday qilib, shaxsiy xabarni yuborish uchun siz qabul qiluvchining ochiq kalitini olishingiz va u bilan xabarni shifrlashingiz kerak. Shundan so'ng, hatto o'zingiz ham uni parolini hal qila olmaysiz.
|
| |
