2-ma’ruza Mavzu: Faktorlash muammosi va uni hisoblash; Qoldiq haqidagi Xitoy teoremasi; Sonni tub ko‘paytuvchilarga ajratish

Misol 7. Quyidagi
x ² 7 ( mod 19)
taqqoslama yechimi bor yoki yo‘qligi ko‘rsatilsin.
Yechish. Bizda a =7, r =19 , EKUB (7, 19) =1 bo‘lib, Eyler kriteriyasiga ko‘ra :

5. 
   ^{(19-1) / 2} 1 ( mod 19)
   

bo‘lgani uchun 7 son 19 modul bo‘yicha kvadratik chegirmadir, yani
L( 7/ 19) =1 .

RSA shifrlash algoritmida ma’lumotni shifrlash va deshifrlash.
Assimetrik shifrlash usullari ma’lumotlarni shifrlashda va deshifrlashda alohida alohida kalitlardan foydalanadi. Shuning uchun ularda kalitlarni taqsimlash muammosi mavjud emas (6.1 – rasm).

6.1-rasm. Assimetrik shifrlash usullarining umumiy ko‘rinishi
Assimetrik shirflash algoritmlaridan foydalanib ma’lumotlarni shirflash quyidagi jarayonlardan iborat:
Kalitlar generatsiyasi.
B foydalanuvchi k_B maxfiy kalit asosida K_B ochiq kalitni generatsiya qiladi. Ochiq kalit K_B ochiq tarmoq orqali A foydalanuvchiga yoki tarmoqning boshqa foydalanuvchilariga uzatadi.
Ma’lumotlarni shirflash.
A foydalanuvchi yoki tarmoqning boshqa foydalanuvchisi K_B ochiq kalitdan foydalangan holda ochiq ma’lumotni shifrlaydi va uni ochiq tarmoq orqali yuboradi.
Shifrmalumotni deshifrlash.
B foydalanuvchi qabul qilingan shifrmatnni o‘zining k_B maxfiy kalit bilan deshifrlaydi va ochiq matnga ega bo‘ladi.
Assimetrik shifrlash usullarini yaratish mavjud bo‘lgan biror matematik muammoga asoslanadi. Hozirda quyidagi muammolarga asoslangan asimmetrik shifrlash usullarini foydalaniladi:
katta sonni ikkita tub ko‘paytuvchi shaklida ajratish (RSA algoritmi);
diskret logarifmlash muammosi (El-Gamal algoritmi);
elliptik egri chiziq muammosi.
RSA shifrlash algoritmi. Diffi va Xelman kritografiya sohasida yangicha yondashishni targ‘ib qilib, ochiq kalitli kriptotizimlarning barcha talablariga javob beradigan kriptografik algoritm yaratish taklifibilan chiqdi. Birinchilardan bo‘lib bunga javoban 1997 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.
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 dan kichik yoki teng bo‘lishi kerak. Umuman olganda amaliyotda blok uzunligi ga teng deb olinadi, bu yerda . Ochiq matn M bloki va shifrlangan matn Cbloki uchun shifrlash va deshifrlash quyidagi formula bilan hisoblash mumkin.
,

Jo‘natuvchi ham, qabul qiluvqi 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.
1. Shunday e, d va n qiymatlar mavjud bo‘lish kerakki, barcha uchun tenglik o‘rinli bo‘lishi kerak.
2. Barcha uchun va 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

Eyler funksiyasiga asosan: har qanday ikkita p va q tub sonva har qanday n va m butun sonlar uchun, n=pq va , va ixtiyoriy k butun son uchun quyidagi munosabat bajariladi.

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.

Bu quyidagi munosabat bilan ekvivalent:


e va d, modul bo‘yichao‘zaro teskari son, ya’ni
gcd( .
Yuqorida keltirilgan parametrlar asosida RSA sxemasini quyidagi tasniflash mumkin:
p va q - tub sonlar (maxfiy, tanlab olinadi),
n=pq (ochiq, his oblanadi),
shunday e, gcd( (ochiq, tanlab olinadi),
(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 Cni jo‘natadi. Shifrlangan matnni qabul qilgan A foydalanuvchi yordamida deshifrlab dastlabki ochiq matnga ega bo‘ladi.
Quyida keltirilgan misolda RSA algoritmi amaliy qo‘llash ko‘rsatilgan.
1. Ikkita tub son tanlab olinadi, p=7 va q=17.
2. n=p*q=7*17 hisoblanadi.
3. Eyler funksiyasi hisoblanadi
4. Eyler funksiyasi bilan o‘zaro tub bo‘lgan va undan kichkina bo‘lnag e tanlab olinadi; bizni, misolimizda ­e=5.
5. de=1mod 96 vad<96shartni qanoatlantiruvchi dsoni 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. 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 amalni hisoblanadi va dastlabki ochiq matn qiymatiga ega bo‘linadi, ya’ni 19 ga.
Hisobot quyidagi ma’lumotlardan tarkib topgan bo‘lishi lozim:
Nazariy qismda keltirilgan algoritmning dasturiy ta’minotidan foydalanish jarayonidagi olingan rasmlari va ularga izoh.
Yaratilgan dasturiy ta’minotning dasturiy kodi.
Nazorat savollari
Ochiq kalitli shifrlash algoritmlarining yaratish asoslari nimalardan iborat.
RSA shifrlash algoritmini tushuntiring.
El-Gamal shifrlash algoritmi ketma - ketligini ayting.