RSA algoritmiga asoslangan demo dasturi
Rivest-Shamir-Adleman (RSA) sxemasi hozirda amalda yagona keng tarqalgan ochiq kalit shifrlash sxemasi hisoblanadi.
RSA sxemasi blokli shifr bo'lib, unda ochiq matn ham, shifrlangan matn ham 0 dan butun sonlardir. P- Ba'zilar uchun 1 P.
Oddiy matn bloklarda shifrlangan bo'lib, ularning har biri ma'lum bir raqamdan kamroq ikkilik qiymatni o'z ichiga oladi P. Bu shuni anglatadiki, blok uzunligi log2 (") dan oshmasligi kerak. Amalda blok uzunligi teng tanlanadi 2 k bit qaerda 2k Rivest, Shamir va Adleman tomonidan ishlab chiqilgan sxema kuch ifodalariga asoslangan. Oddiy matn bloki M va shifrlangan matn bloki C uchun shifrlash va shifrni ochish quyidagi formulalar shaklida ifodalanishi mumkin:
Yuboruvchi ham, qabul qiluvchi ham qiymatni bilishi kerak P. Yuboruvchi ma'nosini biladi e, va faqat qabul qiluvchining qiymatini biladi d. Shunday qilib, bu sxema ochiq kalitli shifrlash algoritmi KU= (e, p), va shaxsiy kalit KR = (d, p).
Ushbu algoritm ochiq kalitni shifrlashda ishlatilishi uchun quyidagi talablar bajarilishi kerak:
Qadriyatlar bo'lishi kerak e, d Va P, nima M ed = M (mod P) hamma uchun M n.
IVT hisoblash nisbatan oson bo'lishi kerak va c1 dan M p ning barcha qiymatlari uchun.
Aniqlash deyarli imkonsiz bo'lishi kerak d mavjud uning p.
Avval birinchi talabni tahlil qilamiz, qolganlarini keyinroq ko'rib chiqamiz. Shaklning munosabatini topish kerak
Bu erda Eyler teoremasidan olingan xulosa to'liq mos keladi: har qanday ikkita tub son uchun R Va q va har qanday ikkita butun son Pit, nima n=pqn0 va ixtiyoriy butun son uchun quyidagi munosabatlar mavjud:
bu yerda ph(n) Eyler funksiyasi, uning qiymati musbat butun sonlar soniga teng. P va bilan tenglashing P.
Oddiy holatda R Va q bizda f (pq) - (s - 1 )(q - biri). Shuning uchun shart ostida kerakli nisbat olinadi
Bu quyidagi munosabatlarga teng:
bular. uning d o'zaro teskari modul ph(n). E'tibor bering, qoldiq sinflarida arifmetika qoidalariga ko'ra, bu faqat shunday bo'lishi mumkin. d(va shuning uchun e) ph(u) bilan ko'paytiriladi. Ekvivalent yozuvda (f(/7), d)=.
Endi bizda RSA sxemasini ifodalash uchun hamma narsa bor. Devren komponentlari quyidagilardir:
R Va q- ikkita tub son (maxfiy, tanlangan);
p-pq(ochiq, hisoblangan);
shunday e, bu (f(i), e)= 1.1 e
d = e l(mod f(/?)) (maxfiy, hisoblangan).
Shaxsiy kalit quyidagilardan iborat (d, n), va dan oching (e, p). Aytaylik, A foydalanuvchisi o'zining ochiq kalitini e'lon qildi va endi B foydalanuvchisi unga M xabarini yubormoqchi.
Keyin B foydalanuvchisi shifrlangan xabarni hisoblab chiqadi
Ushbu shifrlangan matnni olgan A foydalanuvchisi uni hisoblash yo'li bilan shifrini ochadi
Bu erda ushbu algoritm uchun mantiqiy ma'lumot berish mantiqan. Tanlanganlar uning d shu kabi
Demak, shunday ko'rinadi kc>(n)+. Ammo Eyler teoremasining natijasiga ko'ra, har qanday ikkita tub son uchun R Va qu butun sonlar n = pqn M bu O munosabatlar bajariladi
Shunung uchun
Endi bizda bor
10.1-jadvalda RSA algoritmi umumlashtirilgan va shakl. 10.1 uni qo'llash misolini ko'rsatadi. Ushbu misolda kalitlar quyidagicha hisoblanadi:
1. Ikki tub son tanlangan: p-7 wq- 17.
2. Hisoblangan p =pq= 7 x 17=119.
3. f ni hisoblang (n) - (p -) (q - 1) = 96.
4. Tanlangan e, ph bilan tenglashtiring (P)= 96 va f(i) dan kichik; bu holda = 5.
5. Bu aniqlangan d, nima de= 1 (mod 96) va d 96. Tegishli qiymat bo'ladi d= 77, chunki 77 x 5 = 385 = 4 x 96 + 1.
6. Natijada ochiq kalit KU= (5, 119) va yopiq kalit KR = (77, 119).
Bu misol M = 19 ochiq matn kiritish bilan ushbu kalitlardan foydalanishni ko'rsatadi. Shifrlash uchun 19 beshinchi darajaga ko'tariladi, natijada 2 476 099 bo'ladi. 119 ga bo'lish 66 ning qoldig'iga olib keladi. Shuning uchun, 19 119) va shuning uchun shifrlangan matn 66 bo'ladi. Shifrni hal qilgandan so'ng, shunday bo'ladi
Guruch. 10.1.
|
