O’zbekiston Respublikasi Oliy va O’rta Maxsus Ta’lim Vazirligi Mirzo Ulug’bek nomidagi O’zbekiston Milliy Universiteti Amaliy matematika va Intellektual texnologiyalar fakulteti

O’zbekiston Respublikasi Oliy va O’rta Maxsus Ta’lim Vazirligi
Mirzo Ulug’bek nomidagi O’zbekiston Milliy Universiteti
Amaliy matematika va Intellektual texnologiyalar fakulteti
“Axborot xavfsizligi” kafedrasi

“ RSA algoritmi va uning kriptotahlili. Rabin algoritmi va uning kriptotahlili”

mavzularidagi
KURS ISHI


Bajardi:Ne’matova Nozima
Tekshirdi: Boltayev Sherzod

Toshkent 2022

RSA shifrlash algoritmi. Diffi va Xelman kritografiya sohasida yangicha yondashishni targ‘ib qilib, ochiq kalitli kriptotizimlarning barcha talablariga javob beradigan kriptografik algoritm yaratish taklifi bilan chiqdi. Birinchilardan bo‘lib bunga javoban 1978 yil Ron Rayvets (Ron Rivest), Adi Shamir (Adi Shamir) va Len Adlmen (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[6].
Rayvest, Shamir va Adlmen tomonidan yaratilgan sxema daraja ko‘rsatkichiga asoslangan. Ochiq matn bloklarga ajratilib shifrlanadi, har bir blok ba’zi berilgan n sonidan kichik bo‘lgan ikkilik qiymatga ega bo‘ladi. Bundan kelib chiqadiki blok uzunligi log₂ (n) dan kichik yoki teng bo‘lishi kerak. Umuman olganda amaliyotda blok uzunligi 2^k  ga teng deb olinadi, bu yerda 2^k < n≤ 2^k+1. Ochiq matn - M bloki va shifrlangan matn - С bloki uchun shifrlash va deshifrlash quyidagi formula bilan hisoblanishi mumkin.
M=M^e mod(n), M=C^d mod(n)= (M^e )^dmod(n)=M^ed mod(n)
Jo‘natuvchi ham, qabul qiluvchi ham n 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[4,5,6,8].

1. 
   Shunday e, d va n qiymatlar mavjud bo‘lish kerakki, barcha M uchun M^ed= M mod ( n) tenglik o‘rinli bo‘lishi kerak.
   
2. 
   Barcha M < n uchun M^e va C^d ni hisoblash oson bo‘lishi kerak.
   
3. 
   Amaliy jihatdan e va n ni bilmasdan turib d ni qiymatini bilish mumkin bo‘lmasligi kerak.
   

Birinchi shartga binoan quyidagi munosabatni topish kerak
M^ed = M mod (n)
Eyler funksiyasiga asosan: har qanday ikkita p va q tub son va har qanday n va m butun sonlar uchun, n=pq va 0 <m < n, va ixtiyoriy k butun son uchun quyidagi munosabat bajariladi.
m ^{k (n) +1}= m ^{k (p-1) (q-1) +1}=m mod(n),
Bu yerda Eyler funksiyasi bo‘lib, n dan kichik va n bilan o‘zaro tub bo‘lgan musbat butun son. Eyler funksiyasi bilan o‘zaro tub bo’lgan e son tanlab olinadi va talab qilinayotgan munosabat quyidagi shart asosida bajariladi.
ed=k +1
Bu quyidagi munosabat bilan ekvivalent:
ed=1 mod
d=e^-1 mod e va d, modul bo‘yicha o‘zaro teskari son, ya’ni
gcd( e) = 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( e) = 1, 1 < e, (ochiq, tanlab olinadi);
  
• 
  d=e^-1 mod   (maxfiy hisoblanadi).
  

Maxfiy kalit {d,n} dan, ochiq kalit esa {e,n} dan iborat bo‘ladi. Faraz qilaylik, A foydalanuvchi ochiq kalitini e’lon qildi va B foydalanuvchi unga M xabarni jo‘natishi kerak. B foydalanuvchi C=M^e mod(n),  hisoblab C ni jo‘natadi. Shifrlangan matnni qabul qilgan A foydalanuvchi M=C^d mod(n), yordamida deshifrlab dastlabki ochiq matnga ega bo‘ladi[8].
Quyida keltirilgan misolda RSA algoritmini amaliy qo‘llash ko‘rsatilgan.

1. 
   Ikkita tub son tanlab olinadi, p=7 va q=17.
   
2.