2- amaliy ish Mavzu: Maʼlumotlarni rsa algoritmi yordamida shifrlash. Ishdan maqsad

---

2- amaliy ish 
Mavzu: Maʼlumotlarni RSA algoritmi yordamida shifrlash. 
Ishdan maqsad: RSA shifrlash algoritmi va uning matematik asosi, tub 
sonlar va ularni generatsiyalash usullari haqida nazariy va amaliy ko‘nikmalarga ega 
bo‘lish. 
Nazariy qism 
Diffi va Xelman kriptografiya sohasida yangicha yondashishni targʼib qilib, 
ochiq kalitli kriptotizimlarning barcha talablariga javob beradigan kriptografik 
algoritm yaratish taklifi bilan chiqdi. Birinchilardan boʼlib bunga javoban 1997 yil 
Ron Rayvets (Ron Rivest), Аdi Shamir (Adi Shamir) va Len Аdlmen (Len 
Adlmen)lar shu vaqtgacha tan olingan va amaliy keng qoʼllanib kelingan ochiq 
kalitli shifrlash algoritm sxemasini taklif qildi va bu algoritm ularning nomi 
sharafiga RSA algoritmi deb ataldi. RSA algoritmi faktorlash murakkabligiga 
asoslangan shifrlash algoritmi hisoblanadi. 
Rayvest, Shamir va Аdlmen tomonidan yaratilgan sxema daraja 
koʼrsatkichiga asoslangan. Ochiq matn bloklarga ajratilib shifrlanadi, har bir blok 
baʼzi berilgan 𝑛 sonidan kichik boʼlgan ikkilik qiymatga ega boʼladi. Bundan kelib 
chiqadiki blok uzunligi 
𝑙𝑜𝑔
2
(𝑛) dan kichik yoki teng boʼlishi kerak. Umuman 
olganda amaliyotda blok uzunligi 
2
𝑘
ga teng deb olinadi, bu yerda 
2
𝑘
< 𝑛 ≤ 2
𝑘+1
. 
Ochiq matn M bloki va shifrlangan matn C bloki uchun shifrlash va deshifrlash 
quyidagi formula bilan hisoblash mumkin. 
𝑀 = 𝑀
𝑒
𝑚𝑜𝑑𝑛, 
𝑀 = 𝐶
𝑑
𝑚𝑜𝑑𝑛 = (𝑀
𝑒
)
𝑑
𝑚𝑜𝑑𝑛 = 𝑀
𝑒𝑑
𝑚𝑜𝑑𝑛. 
Joʼnatuvchi ham, qabul qiluvchi ham 𝑛 ni qiymatini bilishi kerak. Joʼnatuvchi 
e ni qiymatini, qabul qiluvchi esa faqat d ni qiymatini bilishadi. Ushbu sxema ochiq 
kalitli shifrlash algoritmi hisoblanadi, KU={e,n}- ochiq kalit va KR={d,n}- maxfiy 
kalit hisoblanadi. Bu algoritm ochiq kalit yordamida shifrlanishi uchun, quyidagi 
talablar bajarilishi kerak.
1. Shunday e, d  va  n  qiymatlar mavjud boʼlish kerakki, barcha 
𝑀 < 𝑛 учун 

---

𝑀
𝑒𝑑
= 𝑀𝑚𝑜𝑑𝑛 tenglik oʼrinli boʼlishi kerak. 
2. Barchak. 
𝑀 < 𝑛 uchun 𝑀
𝑒
va 
𝐶
𝑑
ni hisoblash oson boʼlishi kerak. 
3. Аmaliy jihatdan e va n ni bilmasdan turib d ni qiymatini bilish mumkin 
bo’lmasligi kerak. 
Birinchi shartga binoan quyidagi munosabatni toppish kerak
𝑀
𝑒𝑑
= 𝑀𝑚𝑜𝑑𝑛. 
Eyler funksiyasiga asosan: har qanday ikkita p va q tub son va har qanday n 
va m butun sonlar uchun, n=pq va 
0 < 𝑚 < 𝑛, va ixtiyoriy k butun son uchun 
quyidagi munosabat bajariladi. 
𝑚
𝑘𝜑(𝑛)+1
= 𝑚
𝑘(𝑝−1)(𝑞−1)+1
≡ 𝑚𝑚𝑜𝑑𝑛,  
Bu yerda 
𝜑(𝑛) Eyler funksiyasi bo’lib, n dan kichik va n bilan o’zaro tub 
bo’lgan munosabat butun son. Eyler funksiyasi 𝜑(𝑛) bilan o’zaro tub bo’lgan e son 
tanlab olinadi va talab qilinayotgan munosabat quyidagi shart asosida bajariladi. 
𝑒𝑑 = 𝑘𝜑(𝑛) + 1. 
Bu quydagi munosabat bilan ekvivalent: 
𝑒𝑑 ≡ 1 𝑚𝑜𝑑𝜑(𝑛), 
𝑑 ≡ 𝑒
−1
𝑚𝑜𝑑𝜑(𝑛), 
e va d, 
𝜑(𝑛) modul bo’yicha o’zaro teskari son, ya’ni
gcd(
𝜑(𝑛), 𝑒) = 1. 
Yuqorida keltirilgan parametrlar asosida RSA sxemasini quyidagicha 
tasniflash mumkin: 
p va q – tub sonlar (maxfiy, tanlab olinadi), 
n=pq (ochiq, hisoblanadi), 
shunday e, gcd(
𝜑(𝑛), 𝑒) = 1, 1 < 𝑒, 𝜑(𝑛) (ochiq, tanlab olinadi),
𝑑 ≡ 𝑒
−1
𝑚𝑜𝑑𝜑(𝑛) (maxfiy, hisoblanadi). 
Maxfiy kalit {d,n} dan, ochiq kalit esa {e,n} dan iborat boʼladi. Faraz qilaylik 
A foydalanuvchi ochiq kalitini elon qildi va B foydalanuvchi unga M xabarni 
joʼnatmoqchi. B foydalanuvchi 𝐶 = 𝑀
𝑒
(𝑚𝑜𝑑𝑛) hisoblab C ni joʼnatadi. Shifrlangan 
matnni qabul qilgan A foydalanuvchi 
𝑀 = 𝐶
𝑑
(𝑚𝑜𝑑𝑛) yordamida deshifrlab 
dastlabki ochiq matnga ega boʼladi.Misol. 

---

1. Ikkita tub son tanlab olinadi, p=7 va q=17. 
2. n=p*q=7*17 hisoblanadi. 
3. Eyler funksiyasi hisoblanadi 
𝜑(𝑛) = (𝑝 − 1)(𝑞 − 1) = 96. 
4. Eyler funksiyasi
𝜑(𝑛) = 96 bilan oʼzaro tub boʼlgan va undan kichkina 
boʼlgan e tanlab olinadi; bizni, misolimizda e=5. 
5. de=1mod 96 va d<96 shartni qanoatlantiruvchi d soni topiladi. d=77, 
77*5=385=4*96+1. 
Natijada ochiq kalit KU={5,119} va yopiq kalit KR={77,119}= hosil bo’ladi. 
Yuqoridagi misolda ochiq matn qiymati M=19 olingan. Shifrlash formulasiga ko’ra 
ochiq matn qiymati ochiq kalit qiymati yordamida darajaga ko’tarilib, n modul 
bo’yicha qiymati olinadi, ya’ni 19 soni 5 darajaga ko’tariladi, natijada 2476099 hosil 
bo’ladi. Natijani 119 ga bo’linsa, qoldiq 66 ga teng bo’ladi. 19
5
= 66 𝑚𝑜𝑑 119 va 
shuning uchun ham shifrlangan matn 66 ga teng bo’ladi. Deshifrlash uchun esa 
shifrlangan matn qiymati maxfiy kalit qiymati yordamida darajaga ko’tarilib, n 
modul bo’yicha qiymati olinadi, ya’ni 66
77
= 19 𝑚𝑜𝑑 119 amali hisoblanadi va 
dastlabki ochiq matn qiymatiga ega bo’linadi, ya’ni 19 ga.