|
1.2.RSA ochiq kalitli kriptotizm
RSA (Rivest – Shamir – Adleman) a ochiq kalitli kriptotizim xavfsiz ma'lumotlarni uzatish uchun keng foydalaniladi. Bundan tashqari, bu eng qadimiylardan biri. The qisqartma RSA familiyalaridan kelib chiqqan Ron Rivst, Adi Shamirva Leonard Adleman, 1977 yilda algoritmni ommaviy ravishda tasvirlab bergan. Ekvivalent tizim 1973 yilda yashirincha ishlab chiqilgan GCHQ (inglizlar razvedka signallari agentligi), ingliz matematikasi tomonidan Clifford Cocks. Ushbu tizim edi maxfiylashtirilmagan 1997 yilda.
Ochiq kalitda kriptotizim, shifrlash kaliti ochiq va boshqalardan farq qiladi parolni hal qilish kalitiRSA foydalanuvchisi ikkita katta hajmga asoslangan ochiq kalitni yaratadi va nashr qiladi tub sonlar, yordamchi qiymat bilan birga. Asosiy raqamlar sir saqlanadi. Xabarlarni hamma ochiq kalit orqali shifrlashi mumkin, ammo uni faqat oddiy raqamlarni biladigan kishi hal qilishi mumkin.
RSA xavfsizligi amaliy qiyinchiliklarga bog'liq faktoring ikkita katta mahsulot tub sonlar, "faktoring muammosi". RSAni buzish shifrlash nomi bilan tanilgan RSA muammosi. Kabi qiyin bo'ladimi faktoring muammosi ochiq savol. Agar etarlicha katta kalit ishlatilsa, tizimni mag'lub etishning e'lon qilingan usullari mavjud emas.
RSA nisbatan sekin algoritmdir. Shu sababli, odatda foydalanuvchi ma'lumotlarini to'g'ridan-to'g'ri shifrlash uchun foydalanilmaydi. Ko'pincha, RSA umumiy kalitlarni uzatish uchun ishlatiladi nosimmetrik kalit kriptografiya, keyinchalik ommaviy shifrlash-parol hal qilish uchun ishlatiladi.
Kalitlarni yaratish
RSA algoritmining kalitlari quyidagi tarzda hosil qilinadi:
Ikkita farqni tanlang tub sonlar p va q.
Xavfsizlik maqsadida butun sonlar p va q tasodifiy tanlanishi kerak va kattaligi o'xshash bo'lishi kerak, lekin faktoringni qiyinlashtirish uchun uzunligi bir necha raqam bilan farqlanadi. A yordamida butun sonlarni samarali topish mumkin dastlabki sinov.
p va q sir saqlanadi.
Hisoblash n = pq.
n sifatida ishlatiladi modul ham ochiq, ham shaxsiy kalitlar uchun. Uning uzunligi, odatda bit bilan ifodalangan, kalit uzunligi.
n ochiq kalitning bir qismi sifatida chiqariladi.
Hisoblash λ(n), qaerda λ bu Karmaylning totient funktsiyasi. Beri n = pq, λ(n) = lcm(λ(p),λ(q)) va beri p va q asosiy, λ(p) = φ(p) = p - 1 va shunga o'xshash λ(q) = q - 1. Demak λ(n) = lcm (p − 1, q − 1).
Butun sonni tanlang e shu kabi 1 < e < λ(n) va gcd(e, λ(n)) = 1; anavi, e va λ(n) bor koprime.
e qisqa bit uzunligi va kichik Hamming vazni natijada shifrlash samaraliroq bo'ladi - bu eng ko'p tanlangan qiymat e bu 216 + 1 = 65,537. Uchun eng kichik (va eng tezkor) mumkin bo'lgan qiymat e 3 ga teng, ammo uchun bunday kichik qiymat e ba'zi sozlamalarda xavfsizligi pastligi ko'rsatilgan.[15]
e ochiq kalitning bir qismi sifatida chiqariladi.
Aniqlang d kabi d ≡ e−1 (mod λ(n)); anavi, d bo'ladi modulli multiplikativ teskari ning e modul λ(n).
Buning ma'nosi: uchun hal qilish d tenglama d⋅e ≡ 1 (mod.) λ(n)); d yordamida samarali hisoblash mumkin Kengaytirilgan evklid algoritmi, beri, rahmat e va λ(n) koprime bo'lish, aytilgan tenglama bir shakl Bézout kimligi, qayerda d koeffitsientlardan biridir.
d kabi sir saqlanadi shaxsiy kalit ko'rsatkichi.
Ochiq kalit moduldan iborat n va ommaviy (yoki shifrlash) ko'rsatkichi e. shaxsiy kalit xususiy (yoki parol hal qilish) ko'rsatkichidan iborat d, bu sir tutilishi kerak. p, qva λ(n) sir saqlanishi kerak, chunki ularni hisoblash uchun foydalanish mumkin d. Aslida, ularning hammasi keyin tashlanishi mumkin d hisoblab chiqilgan.
Asl RSA qog'ozida, The Eyler totient funktsiyasi φ(n) = (p − 1)(q − 1) o'rniga ishlatiladi λ(n) xususiy ko'rsatkichni hisoblash uchun d. Beri φ(n) har doim bilan bo'linadi λ(n) algoritm ham ishlaydi. Bu Eyler totient funktsiyasi foydalanish mumkin, shuningdek, natijasi sifatida qaralishi mumkin Lagranj teoremasi ga qo'llaniladi multiplikativ butun sonli modul pq. Shunday qilib har qanday d qoniqarli d⋅e ≡ 1 (mod.) φ(n)) ham qondiradi d⋅e ≡ 1 (mod.) λ(n)). Biroq, hisoblash d modul φ(n) ba'zan zarur bo'lganidan kattaroq natija beradi (ya'ni.) d > λ(n)). RSA dasturlarining aksariyati har qanday usul yordamida hosil qilingan ko'rsatkichlarni qabul qiladi (agar ular xususiy eksponentdan foydalansalar) d optimallashtirilgan parol hal qilish usulidan foydalanish o'rniga Xitoyning qolgan teoremasiga asoslangan quyida tavsiflangan), ammo ba'zi bir standartlar FIPS 186-4 buni talab qilishi mumkin d < λ(n). Ushbu mezonga mos kelmaydigan har qanday "katta hajmdagi" xususiy eksponentlar har doim modul bilan kamaytirilishi mumkin λ(n) kichikroq ekvivalent ko'rsatkichni olish uchun.
Ning har qanday umumiy omillaridan beri (p − 1) va (q − 1) ning faktorizatsiyasida mavjud n − 1 = pq − 1 = (p − 1)(q − 1) + (p − 1) + (q − 1),[17] tavsiya etiladi (p − 1) va (q − 1) faqat zarur bo'lgan 2dan tashqari, juda kichik umumiy omillarga ega.
Izoh: original RSA qog'oz mualliflari tanlov orqali kalitlarni ishlab chiqarishni amalga oshiradilar d va keyin hisoblash e sifatida modulli multiplikativ teskari ning d modul φ(n), aksincha RSA ning quyidagi amaldagi amaldagi dasturlari PKCS №1, teskari tomonni tanlang (tanlang e va hisoblash d). Tanlangan kalit kichik bo'lishi mumkin, ammo hisoblash kaliti odatda bunday emas, RSA qog'oz algoritmi shifrlash bilan taqqoslaganda shifrlashni optimallashtiradi, zamonaviy algoritm esa uning o'rniga shifrlashni optimallashtir
Kalit taqsimoti
Aytaylik Bob ga ma'lumot yubormoqchi Elis. Agar ular RSA-dan foydalanishga qaror qilsalar, Bob xabarni shifrlash uchun Elisning ochiq kalitini bilishi kerak va Elis xabarni parolini ochish uchun uning shaxsiy kalitidan foydalanishi kerak.
Bobga shifrlangan xabarlarini yuborish uchun Elis o'zining ochiq kalitini uzatadi (n, e) Bobga ishonchli, lekin sir emas shart. Elisning shaxsiy kaliti (d) hech qachon tarqatilmaydi.
Do'stlaringiz bilan baham: |
