65
qanoatlantiruvchi
𝑒 va 𝑑 sonlari mavjud. Shundan so‘ng, 𝑝 𝑣𝑎 𝑞 lar
esdan chiqariladi (o‘chirib tashlanadi).
Bu yerda,
𝑁 modul hisoblanib, (𝑁, 𝑒) ochiq kalit juftini va 𝑑
maxfiy kalitni tashkil etadi. RSA algoritmida
shifrlash va
rasshifrovkalash modul bo‘yicha darajaga oshirish asosida bajariladi.
RSA
algoritmida shifrlash uchun
𝑀 xabarni son ko‘rinishida ifodalash
talab etiladi va
𝑁 modul bo‘yicha 𝑒 darajaga ko‘tariladi, ya’ni
𝐶 = 𝑀
𝑒
𝑚𝑜𝑑 𝑁
.
𝐶 ni rasshifrovkalash uchun uni 𝑁 modul bo‘yicha shaxsiy kalit 𝑑
darajaga ko‘tarish talab etiladi:
𝑀 = 𝐶
𝑑
𝑚𝑜𝑑 𝑁.
Boshqacha aytganda, RSA algoritmida xabar ochiq kalit bilan
shifrlansa va shaxsiy kalit bilan rasshifrovkalansa,
𝑀 = 𝐶
𝑑
𝑚𝑜𝑑 𝑁 =
𝑀
𝑒𝑑
𝑚𝑜𝑑 𝑁 tenglikning to‘g‘riligini isbotlash zarur.
Aytaylik, RSA algoritmida ma’lumotni shifrlash va
rasshifrovkalash amallari tanlab olingan (
𝑝 = 11 𝑣𝑎 𝑞 = 3) “katta”
sonlar ustida amalga oshirish talab qilinsin. Mazkur holda modul
𝑁 = 𝑝 ∗ 𝑞 = 33 ga teng bo‘ladi va 𝜑(𝑁) = (𝑝 − 1)(𝑞 − 1) = 20 ga
teng bo‘ladi. U holda shifrlash uchun zarur bo‘lgan daraja
e ni (
3) ga
teng deb olish mumkin. Sababi, 3 soni
𝜑(𝑁) = 20 bilan o‘zaro tubdir.
Shundan so‘ng, Evklidning kengaytirilgan algoritmi asosida
rasshifrovkalash kaliti
𝑑 = 7 aniqlanadi. Ya’ni, 𝑒𝑑 = 3 ∗ 7 =
1 𝑚𝑜𝑑 20. U holda A tomonning ochiq kalit jufti 𝑁, 𝑒 = 33, 3 va
shaxsiy kaliti
𝑑 esa 7 ga teng bo‘ladi.
Shundan so‘ng, A tomon o‘zining ochiq kalitini barchaga uzatadi.
Biroq, shaxsiy kalitini maxfiy saqlaydi.
Faraz qilaylik, B tomon A tomonga
𝑀 = 15 ma’lumotni shifrlab
yubormoqchi. Buning uchun B tomon A tomonning
ochiq kaliti juftini
𝑁, 𝑒 = 33,3 oladi va shifrmatnni quyidagicha hisoblaydi:
𝐶 = 𝑀
𝑒
𝑚𝑜𝑑 𝑁 = 15
3
= 3375 = 9 𝑚𝑜𝑑 33
va uni A tomonga yuboradi.
66
A tomon
𝐶 = 9 shifrmatnni rasshifrovkalash uchun shaxsiy kalit
𝑑 = 7 dan foydalanadi:
𝑀 = 𝐶
𝑑
𝑚𝑜𝑑 𝑁 = 9
7
= 4782969 = 144938 ∗ 33 + 15 = 15 𝑚𝑜𝑑 33
Agar RSA algoritmida kichik tub sonlardan (
𝑝 𝑣𝑎 𝑞 𝑢𝑐ℎ𝑢𝑛)
foydalanilgan taqdirda, hujumchi ochiq bo‘lgan
𝑁 ni
osonlik bilan ikkita
tub sonning ko‘paytmasi ko‘rinishida yozishi mumkin. Shundan so‘ng,
ochiq kalitning ikkinchi qism
𝑒 dan foydalangan holda, shaxsiy kalit 𝑑
ni hisoblay oladi. Shuning uchun RSA algoritmidan amalda foydalanish
uchun tanlanuvchi tub sonlar uzunligi kamida 2048 bit bo‘lishi talab
etiladi. Bundan tashqari, RSA algoritmini
buzish faqat faktorlash
muammosiga bog‘liqligi isbotlanmagan.
