Ochiq kalitlarni shifrlash algoritmi

Ikkinchi bosqich - ma'lumotlarni shifrlash. Agar A abonenti ba'zi ma'lumotlarni B abonentiga topshirishni istasa, u o'z xabarini raqamli shaklda yuborishi va bloklarga bo'linishi kerak m 1, m 2, m 3, ..., qaerda m i< N . Shifrlangan xabar i bilan bloklardan iborat bo'ladi.

A abonenti o'z xabarlarining har bir blokini formulaga muvofiq shifrlaydi

c i \u003d m i d mod N

foydalanish ochiq imkoniyatlar   foydalanuvchi B foydalanadi va shifrlangan C \u003d (s 1, s 2, s 3, ...) xabarlarini ochiq chiziq orqali yuboradi.

Shifrlangan xabarni olgan B abonenti qabul qilingan xabarning barcha bloklarini formulaga muvofiq shifrlaydi

Shifrlangan bloklarning barchasi A foydalanuvchisining bloklari bilan bir xil bo'ladi.

Barcha xabarlarni aralashtiradigan va barcha ochiq ma'lumotni biladigan tajovuzkor P va Q katta qiymatlarga ega asl xabarni topa olmaydi.

Algoritmni hisoblash misoli

A foydalanuvchisiga B foydalanuvchisiga xabar yuborishni xohlashiga ruxsat bering. Bunday holda, B foydalanuvchisi avval ochiq va shaxsiy kalitlarni tayyorlashi kerak. Unga, masalan, quyidagi parametrlarni tanlashiga ruxsat bering:

P \u003d 3, Q \u003d 11, N \u003d 3x11 \u003d 33.

Keyin f \u003d (P - l) (Q - 1) \u003d (3-1) (11-1) \u003d 20.

Shunda B foydalanuvchisi f bilan umumiy bo'linishlarga ega bo'lmagan har qanday d raqamini tanlaydi (bu shifrlangan xabarni keyinchalik tiklanishi uchun zarurdir). D \u003d 13 bo'lsin. Ushbu raqam ochiq kalitning tarkibiy qismlaridan biri bo'ladi.

Ravest-Shamir-Adleman (RSA) sxemasi hozirda tan olingan va amalda foydalaniladigan ochiq kalitlarni shifrlashning yagona sxemasi hisoblanadi.

RSA sxemasi blokli shifr bo'lib, unda oddiy matn va shifrlangan matn 0 dan 0 gacha bo'lgan butun sonlar bilan ko'rsatilgan. n   - Ba'zilar uchun 1 n

Oddiy matn bloklarda shifrlangan, ularning har birida ikkilamchi berilgan qiymatdan kam n   Bu degani, blokning uzunligi log2 (") dan oshmasligi kerak. Amalda, blokning uzunligi teng tanlanadi 2 ga   bit qaerda 2 - Ryvest, Shamir va Adleman tomonidan ishlab chiqilgan sxemalar darajadagi ifodalarga asoslangan. M tekis matn bloki va C shifr tekst bloki uchun shifrlash va shifrlash quyidagi formulalar ko'rinishida ko'rsatilishi mumkin:

Yuboruvchi ham, qabul qiluvchi ham uning ma'nosini bilishi kerak n   Yuboruvchi uning ma'nosini biladi e   va faqat qabul qiluvchining ma'nosini biladi d.   Shunday qilib, ushbu sxema ochiq kalitlarni shifrlash algoritmi KU \u003d (e, n)   va shaxsiy kalit KR \u003d (d, n).

Ochiq kalitlarni shifrlashda ushbu algoritmdan foydalanish uchun quyidagi talablar bajarilishi kerak:

Bunday qadriyatlar mavjud bo'lishi kerak e, d   va n   nima Ed \u003d   M (mod n)   hamma uchun M p.

IVTni hisoblash uchun nisbatan oson bo'lishi kerak va C s1   M p ning barcha qiymatlari uchun.

Uni aniqlash deyarli imkonsiz bo'lishi kerak d   mavjud bo'lganiga ko'ra uning p.

Avval birinchi talabni tahlil qilamiz va qolganlarini keyinroq ko'rib chiqamiz. Shaklning nisbatlarini topish kerak

Bu erda Eyler teoremasi mutanosibligiga mos keladi: har qanday ikkita tub son uchun bunday p   va q   va shunga o'xshash har qanday ikkita butun son chuqur   nima n \u003d pqn0 va ixtiyoriy butun son ga   quyidagi munosabatlar qondiriladi:

bu erda (φ) qiymati musbat butun sonlar soniga teng bo'lgan Eyler funktsiyasi n   va o'zaro o'zaro n

Oddiy holatda p   va q   bizda f bor (pq) - (p.) - 1 ) (q -   1). Shuning uchun talab qilingan nisbat shart asosida olinadi

Bu quyidagi munosabatlarga tengdir:

ya’ni u d   o'zaro teskari modul φ (π). Esda tutingki, qoldiq sinflarida arifmetika qoidalariga muvofiq, bu faqat qachon sodir bo'lishi mumkin d   (va shuning uchun e)   () ()) bilan nusxa ko'chirish. Muvaffaqiyatli notasida (φ (/ 7), d) \u003d.

Endi bizda RSA sxemasini taqdim etish uchun hamma narsa mavjud. Devren tarkibiy qismlari quyidagilardan iborat: