Openssl kutubxonasidan foydalangan holda ma’lumotlarni rsa algoritmi yordamida shifrlash. Rsa shifrlash algoritmida ma’lumotni shifrlash va deshifrlash

642-20 guruh talabasi Maxsudov Azamxon Yunusxo’ja o’g’li
1-5 amaliy mashg’ulotlari

1- amaliy mashg’ulot
Mavzu: OpenSSL kutubxonasidan foydalangan holda ma’lumotlarni RSA algoritmi yordamida shifrlash. RSA shifrlash algoritmida ma’lumotni shifrlash va deshifrlash
Ishdan maqsad: RSA shifrlash algoritmida deshifrlash haqida nazariy va amaliy ko’nikmalarga ega bo’lish.
Ochiq kalitli kriptotizimlarni bir tomonli funksiyalar ko‘rinishi bo‘yicha farqlash mumkin. Bularning ichida RSA, El-Gamal va Mak-Elis tizimlarini alohida tilga olish o‘rinli. Hozirda eng samarali va kеng tarqalgan ochiq kalitli shifrlash algoritmi sifatida RSA algoritmini ko‘rsatish mumkin.
1976 yilda Uitfild Diffi va Martin Xellmanlar tomonidan chop etilgan “Kriptografiyada yangi yo‘nalish” deb nomlangan maqola kriptografik tizimlar haqidagi tasavvurlarni o‘zgartirib yubordi, ochiq kalitli kriptografiya paydo bo‘lishiga zamin yaratdi. Bu maqolani o‘rganib chiqqan Massachusets texnologiyalar instituti olimlari Ronald Rivest, Adi Shamir va Leonard Adleman 1977 yilda RSA algoritmini yaratdilar.
RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan olingan. Algoritm modul arifmеtikasining darajaga ko‘tarish amalidan foydalanishga asoslangan. 1977 yil avgust oyida Scientific American jurnalida RSA kriptotizimini yoritib berishdi va shu algoritm bilan shifrlangan quyidagi iborani ochishni o‘quvchilarga taklif etishdi:
C=n=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541, e=9007, M=?
Mukofot sifatida 100 AQSh dollari e’lon qilindi. Algoritm avtorlaridan biri Rivest bu shifrni ochishga 40 kvadrillion yil ketishini aytgan bo‘lsa, 1993 yil 3 sentabrdan 1994 yil mart oyigacha 20 ta mamlakatdan 600 ta ko‘ngilli shaxslar 1600 ta kompyuterda parallel ishlab bu shifrni ochishdi – THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE.
1982 yilda Ronald Rivest, Adi Shamir va Leonard Adleman RSA Data Security kompaniyasini tashkil etishdi. 1989 yildan boshlab RSA algoritmi Internetda foydalanila boshlandi. 1990 yildan boshlab AQSh mudofaa vazirligi foydalana boshladi.1993 yilda PKCS1 standartining 1.5 versiyasida RSA algoritmini shifrlash va elektron imzo yaratishda qo‘llash keltirildi. Bu standartning oxirgi versiyalari RFC standartida keltirilgan (RFC 2313 — 1.5, 1993 yil; RFC 2437 — 2.0, 1998 yil; RFC 3447 — 2.1, 2002 yil).
Algoritmni quyidagi qadamlar kеtma-kеtligi ko‘rinishida ifodalash mumkin:
1. Ikkita katta tub son p va q tanlanadi.
2. Kalitning ochiq tashkil etuvchisi n hosil qilinadi: n=p·q.
3. Quyidagi formula bo‘yicha k (Eylеr funksiyasi qiymati) hisoblanadi:
k=(p-1)(q-1).
4. k qiymati bilan o‘zaro tub bo‘lgan katta tub son e tanlab olinadi.
5. Quyidagi shartni qanoatlantiruvchi d soni aniqlanadi:
d =e-1 mod k .
Bu shartga binoan ko‘paytmaning k qiymatga bo‘lishdan qolgan qoldiq 1 ga tеng. e soni ochiq kalitning ikkinchi tashkil etuvchisi sifatida qabul qilinadi. Yopiq kalit sifatida d soni ishlatiladi.
6. Dastlabki axborot uning fizik tabiatidan qat’iy nazar raqamli ikkili ko‘rinishda ifodalanadi. Bitlar kеtma-kеtligi L bit uzunlikdagi bloklarga ajratiladi, bu yerda blok sifatida L < log2(n+1) shartini qanoatlantiruvchi eng katta butun sonni olish tavsiya etiladi. Har bir blok [0, n-1] oraliqqa taalluqli butun musbat son kabi ko‘riladi. Shunday qilib, dastlabki axborot Mi, i= sonlarning kеtma-kеtligi orqali ifodalanadi. I ning qiymati shifrlanuvchi kеtma-kеtlikning uzunligi orqali aniqlanadi.
7. Shifrlangan axborot quyidagi formula bo‘yicha aniqlanuvchi Ci sonlarning kеtma-kеtligi ko‘rinishida olinadi:
Axborotni ochishda quyidagi munosabatdan foydalaniladi:
Bugungi kunda RSA tizimi programma ta’minoti xavfsizligini ta’minlashda va elektron raqamli imzo sxemalarida foydalaniladi. Shifrlash tezligining pastligi sababli (2 GHz protsessorlarda 512 bitli kalit yordamida 30 kb/s tezlikda shifrlaydi) simmetrik algoritmlarning kalitlarini shifrlab uzatishda ko‘proq foydalaniladi.
Misol.
Modul son ko‘paytma bilan o‘zaro tub bo‘lgan e=11 ochiq kalit, shifrlanadigan matn M=BESH so‘zi va matn uzunligi L=8 bit berilgan. Agar L berilmagan bo‘lsa, L=[log2(n+1)] formula orqali topiladi.
Shifrlash:
1. BE SH so‘zini ASCII jadvali yordamida bit ko‘rinishga o‘tkazamiz: 01000010 01000101 01010011 01001000.
2. Bitlardan iborat matnni 8 bitdan bloklarga ajratamiz va har bir blokni o‘nlik sanoq sistemasiga o‘tkazamiz: M1=66, M2=69, M3=83, M4=72.
3. formula yordamida shifrlanadi:
, ,
Hosil bo‘lgan shifrtekst quyidagicha:
Shifrni ochish:
Modul son ko‘paytma bilan o‘zaro tub bo‘lgan e=11 ochiq kalit, matn uzunligi L=8 bit va bizga ma’lum.
1. e sonining modul bo‘yicha teskarisini topamiz:
2. formula yordamida shifrni ochamiz:
3. Mi larni o‘nlikdan ikkilikka o‘tkazib, ASCII jadval yordamida harflarga o‘tamiz va natijada M=BESH so‘zi paydo bo‘ladi
Nazorat savollari
Kalitdan foydalanish usuli bo’yicha kriptografik tizimlar necha turga bo’linadi?
Assimmetrik kriptografik tizimlarda ma’lumotlarni shifrlash va deshifrlash uchun qanday kalitlar shlatiladi?
Ochiq kalit nima?
Yopiq kalit nima?
Tub sonlar deb qanday sonlarga aytiladi.
RSA algoritmida Eyler funksiyasini tushuntirib bering
RSA algoritmi asosi nimadan iborat.
Nima sabadan Ochiq kalitli shifrlash algoritmlarida kalitlarni taqsimlash muammosi mavjud emas.

2- amaliy mashg’ulot

Mavzu: OpenSSL kutubxonasidan foydalangan holda maʼlumotlarni RSA algoritmi yordamida shifrlash. Eyler va Ferma teoremasi
Ishdan maqsad: Talabalarda assismmetril kriptografik algoritmlarni matematik asoslaridan biri bo’lgan Eyler va Ferma teoramalari bilan ko’nikmasiga ega bo’lish
Fermaning kichik teoremasi
Fermatning kichik teoremasi sonlar nazariyasi va kriptografiyasida juda muhim rol o‘ynaydi. Quyida teoremaning ikkita versiyasini beramiz.
versiya
Birinchi versiyada, agar soni tub bo‘lsa va soni soniga bo‘linmaydigan butun son bo‘lsa, u holda o‘rinli.
Ikkinchi versiya
Ikkinchi versiyada a-da cheklov sharti keltirilgan. Uning ta’kidlashicha, agar p tub son bo‘lsa va a butun son bo‘lsa, u holda? .
Ilova
Keyinchalik ushbu ma’ruzada ushbu teoremaning qo‘llanilishini ko‘rib chiqsak ham, teorema ba’zi muammolarni hal qilishda juda foydali.
Eksponentlash. Fermatitning kichik teoremasi eksponentatsiyaga tezda yechim topish uchun ba’zida foydalidir. Buni quyidagi misollar ko‘rsatib turibdi.
Misol 12.12
610 mod 11 qiymatini toping
Yechim
Biz olamiz. Bu Fermataning kichik teoremasining birinchi versiyasi., bu yerda p = 11.
Multiplikativ teskarilash. Agar modul tub son bo‘lsa, Fermat teoremasi bir nechta multiplikativ inversiyalar uchun juda qiziqarli dasturni topdi, agar tub son bo‘lsa va soni soniga bo‘linmaydigan butun son bo‘lsa, u holda togda a-1mod p = ap-2 mod p o‘rinli. Agar tenglikning ikkala tomonini ga ko‘paytirsak va Fermatning kichik teoremasi--ning birinchi versiyasidan foydalansak, buni isbotlash mumkin.

Ushbu ifoda kengaytirilgan Yevklid algoritmidan foydalanmasdan, sonning multiplikativ teskarisini topish imkonini beradi.
Misol 12.14
Butun sonning modul bo‘yicha teskari qiymatini kengaytirilgan Yevklid algoritmidan foydalanmasdan topishimiz mumkin:
a. 8-1 mod 17 = 817-2 mod 17 = 815 mod 17 = 15 mod 17
b. 5 –1 mod 23 = 523-2 mod 23 = 521 mod 23 = 14 mod 23
c. 60101 mod 101 = 60101-2 mod 101 = 6099 mod 101 = 32 mod 101
d. 22 -1 mod 211 = 22 211-2 moda 211 = 22209 mod 211 = 48 mod 211
Eyler teoremasi
Eyler teoremasini Fermaning kichik teoremasini umumlashtirish sifatida ko‘rsatish mumkin. Ferma teoremasida modul bu tub son, Eyler teoremasida modul bu butun son. Ushbu teoremaning ikkita versiyasini taqdim etamiz
Birinchi versiya
Eyler teoremasining birinchi versiyasi Fermatning kichik teoremasining birinchi versiyasiga o‘xshaydi. Agar a va n o‘zaro tub bo‘lsa, u holda o‘rinli.
Ikkinchi versiya
Eyler teoremasining ikkinchi versiyasi Fermatning kichik teoremasining ikkinchi versiyasiga o‘xshash; u soni , bilan o‘zaro tub bo‘lishi kerak degan degan shartni bekor qiladi. Agar bo‘lsa, k — butun son bo‘lsa, u holda  bo‘ladi.
Birinchi versiyaga asoslangan ikkinchi versiyaning zaif dalilini beramiz. (a 1. Agar soni ga yoki sha bo‘linmasa, u holda a va n o‘zaro tub.

2. agar soni p ga bo‘linsa,  , q. Soniga bo‘linmasa.

3. Agar a soni q soniga bshlinsa, ( ), lekin p soniga bo‘linmasa, ikkinchi holatning isboti bir xil, ammo va o‘zaro bir-biriga bog‘langan.
Eyler teoremasining ikkinchi versiyasi RSA kriptografik tizimida foydalaniladi.
Ilova
Garchi bu ma’ruzada keyinchalik Eyler teoremasining ba’zi amaliy dasturlarini ko‘rib chiqamiz. Teorema ba’zi muammolarni hal qilish uchun juda foydali.
Eksponentlash. Euler teoremasi ba’zan eksponensial muammolarni tezda topish uchun foydalidir
Misol12.15
624 mod 35 qiymatini toping.
Yechim
ga ega bo‘lamiz
Misol 12.16
2062 mod 77. Qiymatini toping
Yechim
Agar ikkinchi versiyaga ko‘ra ni kiritsak, unda:
2062 mod 77 = (20 mod 77) mod 77 = (20)(20) mod 77 = 15
Mersenning tub sonlari.
Mersen Mersen raqami deb ataladigan quyidagi formulani taklif qildi. U formulada barcha tub sonlar ro‘yxati borligini aytdi. 
Mp = 2p–1
Agar yuqoridagi formulada asosiy bo‘lsa, u holda bosh darajaga teng bo‘lishi kerak edi. Yillar o‘tib, Mersen formulasi orqali olingan barcha raqamlarning barchasi ham tub sonlar emasligi isbotlandi. Quyida ba’zi Mersenne raqamlarining ro‘yxati keltirilgan.

Ma’lum bo‘lishicha, M11 bu tub son emas. Biroq, Mersenne formulasi bo‘yicha 41 ta raqam tub ekanligi aniqlandi; Mersennening so‘nggi raqamlaridan biri bu M124036583, eng katta raqam 7 253 733 raqamni o‘z ichiga oladi. Qidiruv davom etmoqda.
Fermat tub sonlarni hosil qiluvchi formulani topishga harakat qildi. Ferma raqamlari uchun quyidagi formula keltirilgan:
Mersenne raqami deb nomlangan formulasidagi raqam bosh raqam bo‘lishi mumkin yoki bo‘lmasligi mumkin.
Fermaning tub sonlari
Fermat asosiy sonlarni hosil qilish uchun formulani topishga harakat qildi. U hozirda Fermat formulasi deb ataladigan quyidagi formulani taklif qildi va F0 (n = 0,1, ...) dan F4 gacha bo‘lgan raqamlarni tekshirdi, ammo F4 allaqachon tub son emasligi ma’lum bo‘ldi.

F0 = 3
F1 = 17
F2 = 257
F3 = 65537
. Tub son emas. Aslida, gacha bo‘lgan ko‘plab raqamlar aralash raqamlar ekanligi isbotlangan.
Topshiriq.
Katta sonlarni darajasini hisoblashni Eyler va Ferma teoremalariga asosan amalga oshiring. Mersen va Ferma tub sonlarini hosil qilish dasturini tuzing.
Hisobot quyidagi ma’lumotlardan tarkib topgan bo‘lishi lozim:
Nazariy qismda keltirilgan algoritmning dasturiy ta’minotidan foydalanish jarayonidagi olingan rasmlari va ularga izoh.
Nazorat Savollari
Tub sonlar deb nimaga aytiladi?
Tub sonlarni hosil qilish algoritmlariga misol keltiring?
Fermaning kichik teoremasi?
Eyler teoremasini qanday teorema?
Mersenning tub sonlari qanday hosil qilinadi?

3-amaliy mashg’ulot

Mavzu: OpenSSL kutubxonasidan foydalangan holda maʼlumotlarni RSA algoritmi yordamida shifrlash. Sonlarni tublikka tekshirish algoritmlari. Ferma testi.
Ishdan maqsad: Tub sonlarni hosil qilish va ularni tublikka tekshirish ko’nikmasiga ega bo’lish
Bo‘lish nazariyasi algoritmi
Eng elementar deterministik tub sonlarni tekshirish bu bo‘lish bilan tekshirish. Biz barcha bo‘luvchi sonlar sifatida dan kichiklaridan foydalanamiz. Agar bu sonlardan istalgani ga bo‘linsa, holbuki murakkab. 

Algoritm 12.1.
Algoritm 12.1da bo‘lish bo‘yicha tublikka sinash juda samarali va primitiv formada aks ettirgan. 
Algoritm faqatgina toq sonlarni tekshirsa yanada samarali ishlashi mumkin. U yana 2 va sonlar oralig‘idagi tub sonlar jadvalidan foydalanilsa yanada samarali bo‘lishi mumkin. 12.1 algoritmdagi arifmetik amallar soni —  ga teng. Agar biz har bir arifmetik amal faqat bir bitdagi amallardan foydalanilishini qabul qilsak, u holda 12.1 algoritm razryadli amali murakkabligi ga teng, bu yerda nb – bitlar soni  dagi. Katta tizimlarda, murakkablik ko‘rsatkichi,murakablik eksponensial O(2n) darajada baholanishi mumkin. Boshqa so‘z bilan aytganda bo‘lish sinovi agar nb katta son bo‘lsa samarasiz hisoblanadi.
Primer 12.18
Faraz qilamiz, 200 bitga teng. Qanday sondagi razryad amalini bo‘lish algoritmida amalga oshirish kerak?
Resheniye
Bu algoritm bitli amalining murakkabligi—  . Bu shuni anglatadiki, algoritm bir qancha 2100bit amallarni o‘tkazadi. Agar algoritm sekundiga 230ta amalni bajarish tezligiga ega bo‘lsa, u holda sinovni o‘tkazish uchun 270 soniya kerak bo‘ladi

Ferma testi

Biz muhokama qilayotgan birinchi ehtimollik usuli bu Fermatning tub sonlarni sinab ko‘rishidir.
Agar tub son bo‘lsa, u holda  tenglik o‘rinli.
E’tibor bering, agar n tub bo‘lsa, taqqoslash to‘g‘ri bo‘ladi. Lekin bu, taqqoslash to‘g‘ri bo‘lsa, n bu tub son bo‘ladi degani emas. Butun son tub yoki murakkab bo‘lishi mumkin . Fermat testi sifatida biz quyidagilarni aniqlashimiz
mumkin:
Tub sonlar Fersa testini qanoatlantiradi. Murakkab sonlar ehtimollik bilan ferma testidan o‘tishi mumkin. Yekspopensialni hisoblao‘ kabi, Ferma testining razryadli amallari murakkabligi algoritm murakkabligiga teng. Agar nazorat bir nechta sonlarga bo‘lib yuborilsa, ehtimollik yanada yaxshi bo‘lishi mumkin.
Misol.
561 soni uchun Ferma sinovini o‘tkazing.
Yechim
Asos sifatida 2 sonidag foydalanamiz.
2561-1 = 1 mod 561
Son Ferma testidan o‘tdi, lekin bu tub son emas, nimagaki
.
Topshiriq:
Katta son olib ferma testida uni tub yoki tub emasligini aniqlang.
Hisobot quyidagi ma’lumotlardan tarkib topgan bo‘lishi lozim:
Nazariy qismda keltirilgan algoritmning dasturiy ta’minotidan foydalanish jarayonidagi olingan rasmlari va ularga izoh.
Nazorat Savollari
Tub sonlar qanday hosil qilinadi?
Hamma algoritmlar ham ishonchli tub son hosil qiladimi?
Tublikka tekshirish algoritmlariga misol keltiring?
Ferma testini tushuntiring?

4-amaliy mashg’ulot

Mavzu: OpenSSL kutubxonasidan foydalangan holda ma’lumotlarni RSA algoritmi yordamida shifrlash. Sonlarni tublikka tekshirishning Rabin Miller testi
Ishdan maqsad: Tub sonlarni hosil qilish va ularni tublikka tekshirish ko’nikmasiga ega bo’lish.
Tub sonlarni aniqlaydigan Rabin Miller testi Ferma va Kvadrat ildiz testlarining kombinatsiyasidan iborat. Bu kuchli psevdotasodifiy sonlarni topishning elegant usulidir (kuchli ehtimollik bilan tub son). Bu testda biz toq son ni va 2 ning darajasini topish uchun sifatida ni yozib olamiz .

Fermat testida, a sosda, u quyida ko‘rsatilgandek yozilishi mumkin.
Fermaga asoslangan sonni tublikka tekshirish testi

Boshqacha qilib aytganda, biz bir qadamda an-1 (mod n) ni hisoblashning o‘rniga k + 1 bosqichda bajaramiz. Ushbu dasturning afzalligi nimada? Afzalligi shundaki, kvadrat ildiz sinovini har qadamda bajarish mumkin. Agar kvadrat ildiz shubhali natijalarni ko‘rsatsa, biz to‘xtatamiz va n kompozit sonni e’lon qilamiz. Har bir qadamda, Fermat testi va kvadrat ildiz sinovi, agar u qoniqarli bo‘lsa, qo‘shni barcha juftliklar bo‘yicha qoniqishini ta’minlaymiz.

Initsializatsiya
Asosni tanlaymiz va T = am ni tanlaymiz, v kotorыy m = (n – 1) / 2k.
a. Agar natija +1 yoki -1 ga teng bo‘lsa, ni kuchli psevdotubson deb e’lon qilamiz va jarayonni to‘xtatamiz. Biz sonini Ferma va kvadrat ildiz testidan o‘tdi deya aytishimiz mumkin.
b. Agar T soni boshqa natijaga teng bo‘lsa, biz sonin tub son yoki murakkab son ekanligiga ishonch hosil qila olmaymiz. Demak, jarayon keyingi qadamda davom etadi.
1 Qadam
T sonini kvadratga ko‘taramiz.
a. Agar natija +1 bo‘lsa, biz aniq bilamizki, Fermat testi o‘tgan, chunki T keyingi sinovlar uchun 1 bo‘lib qoladi. Ammo kvadrat ildiz sinovi muvaffaqiyatsiz tugadi. Ushbu bosqichda T 1 bo‘lganligi va oldingi bosqichda (avvalgi bosqichda to‘xtamaganimiz sababi) boshqacha ma’noga ega bo‘lganligi sababli n murakkab ob’ekt deb e’lon qilinadi va jarayon to‘xtaydi.
b. Agar natija (-1)ga teng bo‘lsa, chekli hisobda Ferma testidan o‘tishini bilamiz. Bilamizki, u kvadrat ildiz sinovidan ham o‘tadi, chunki bu qadamda natija (-1)ga teng bo‘ladi va keyinga qadamda 1 bo‘ladi. Biz ni kuchli psevdotasodifiy son deb e’lon qilamiz va jarayonni to‘xtatamiz.
c. Agar T yana qandaydir natijani bersa, tub son bo‘ladi deb ishonch hosil qila olmaymiz va jarayon keyingi qadamda davom etadi.
Qadamlar 2dan k–1 gacha
Bu qadam va qadamgacha 1- qadam kabi bo‘ladi.. Bu qadam muhim emas. Agar biz uni amalga oshirsak va natija olmasak, u bizga naf bermaydi. Agar bu qadam natijasi (-1) bo‘lsa, demak Ferma testidan o‘tadi, lekin oldingi qadam natijvsi sifatida olinmasa, kvadrat ildiz testidan o‘ta olmaydi, Agar jarayon qadam oxirigacha to‘xtamasa,biz ni murakkab son deb e’lon qilamiz.
Test Millera-Rabina trebuyet ot 0 do k–1..
Algoritm 12.2 Rabin Miller testi uchun psevdokodni ko‘rsatadi..

12.2. Millera-Rabin testi uchun psevdokod
Har safar Miller-Rabin testi har bir raqam uchun o‘tkazilganda, "unchalik katta bo‘lmagan" natijani olish ehtimoli 1/4 ni tashkil qiladi. Agar sinovdan o‘tgan bo‘lsa, testning tub bo‘lmaslik bermaslik ehtimoli (1/4) ..

Yechish
2 asosdan foydalanib, , ni olamiz, bu yerda m = 35, k = 4 i a = 2 ni anglatadi.

Primer 12.26
Misol.
Biz bilamizki, 27 tub son emas. Millera-Rabin testini sinab ko‘ramiz.
Yechim
2 ga teng asos, , holbuki  , m = 13, k = 1 i a = 2 ni anglatadi. Bu holda k – 1 = 0 va biz faqat initalizatsiya qadamini bajarishimiz kerak holos:
T = 213 mod 27 = 11 mod 27. Lekin algoritm sifatida biror qadam ham ish bajarmadi, yechimni ishlab chiqamiz “murakkab son”.
Tavsiya etilgan sonlarni tublikka tekshirish testlpri
Bugungi kunda eng mashhur tublik sinovlaridan biri bu bo‘linish nazariyasi va Miller-Rabin testining kombinatsiyasi. Quyidagi amallarni bajarish tavsiya etiladi:
Tub bo‘lmagan sonni tanlang, chunki hamma juft butun sonlar aniq murakkab ob’ektlardir.
1. 2. 3, 5, 7, 11, 13 kabi taniqli oddiy sonlarga bo‘linish nazariyasining ba’zi bir arzimas sinovlarini o‘tkazing: aniq aralash ob’ekt bilan ishlamasligingizga ishonch hosil qilish uchun. Agar ushbu barcha sinovlarda ular bo‘linmasa, keyingi bosqichga o‘ting. Agar tanlangan raqam ushbu testlarning kamida bittasida muvaffaqiyatsiz bo‘lsa, bir qadam orqaga qayting va boshqa toq raqamni tanlang.
Sinov uchun asoslar to‘plamini tanlang. Ko‘p sonli bazalarga afzallik beriladi.
Har bir asosda Miller-Rabin testini o‘tkazing. Agar ulardan biri bajarilmasa, bir qadam orqaga qayting va boshqa toq raqamni tanlang. Agar testlar har qanday sabablarga ko‘ra o‘tgan bo‘lsa, unda bu sonni kuchli soxta premer raqam deb e’lon qiling.
Misol 12.28
Nomer 4033 — murakkab son ( ). Bu raqamlarning tublik sinovini tasdiqlaydimi?
Yechim
1. Tekshirishni bo‘linish nazariyasiga muvofiq amalga oshiramiz. Avval raqamlarni tekshirib ko‘raylik 2, 3, 5, 7, 11, 17 i 23 – ular sonni bo‘luvchi emas 4033.
2. Keyin 2-asos bilan Miller-Rabin sinovini o‘tkazing  , bu yerda m = 63 i k = 6 degan ma’noni anglatadi.

3. Ammo bizni qoniqtirmaydi. Biz boshqa asos bilan davom etamiz - 3.

Topshiriq:
Katta son olib Rabin-Miller testida uni tub yoki tub emasligini aniqlang.
Hisobot quyidagi ma’lumotlardan tarkib topgan bo‘lishi lozim:
Nazariy qismda keltirilgan algoritmning dasturiy ta’minotidan foydalanish jarayonidagi olingan rasmlari va ularga izoh.
Nazorat Savollari
Tub sonlar qanday hosil qilinadi?
Hamma algoritmlar ham ishonchli tub son hosil qiladimi?
Tublikka tekshirish algoritmlariga misol keltiring?
Rabin-Miller testini tushuntiring?

5-amaliy mashg’ulot

Mavzu: OpenSSL kutubxonasidan foydalangan holda ma’lumotlarni RSA algoritmi yordamida shifrlash. OpenSSL kutubxonasidan foydalangan holda RSA algoritmi bilan ishlash.
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), 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 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 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 uchun tenglik oʼrinli boʼlishi kerak.
2. Barchak. 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 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 , 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 munosabat butun son. Eyler funksiyasi bilan o’zaro tub bo’lgan e son tanlab olinadi va talab qilinayotgan munosabat quyidagi shart asosida bajariladi.

Bu quydagi munosabat bilan ekvivalent:


e va d, modul bo’yicha o’zaro teskari son, ya’ni
gcd( .
Yuqorida keltirilgan parametrlar asosida RSA sxemasini quyidagicha tasniflash mumkin:
p va q – tub sonlar (maxfiy, tanlab olinadi),
n=pq (ochiq, hisoblanadi),
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 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
4. Eyler funksiyasi 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. 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 amali hisoblanadi va dastlabki ochiq matn qiymatiga ega bo’linadi, ya’ni 19 ga.
Amaliy qism
Openssl kutubxonasidan foydalanish uchun cmd buyrug‘idan foydalaniladi (pusk va R teng bosiladi):

1.1- rasm. Cmd buyrug‘ini ishga tushiriladi
Cmd oynasidagi joriy papkasidan chiqish uchun cd.. buyrug‘idan foydalaniladi:

1.2- rasm. cd.. buyrug‘idan foydalanish
Openssl kutubxonasi uchun foydalanadigan certificate papkasiga quyidagi buyrug’ orqali ochiq ma’lumotni xosil qilib olamiz:

1.3- rasm. Sertifikat papkaga kirish

1.4- rasm.Ochiq matn faylini yaratish

1.5- rasm. Ochiq matn fayli

1.6- rasm. OpenSSLni ishga tushirish

1.7- rasm. Yopiq kalit hosil qilish

1.8- rasm. Hosil qilingan yopiq kalit

1.9- rasm. Maxfiy kalitdan foydalanib ochiq kalit hosil qilish.

1.10- rasm. Ochiq kalit

1.11- rasm. Ma’lumotni shifrlash

1.12- rasm. Shifr fayl.

1.13- rasm. Shifrlangan ma’lumot

1.14-rasm. Ma’lumotni deshifrlash.

1.15-rasm. Shifrmatnning dastlabki holatga qaytarilgan ko‘rinishi

Topshiriq

RSA shifrlash algoritmida OpenSSL kutubxonasidan foydalangan holda shifrlash jarayonini amalga oshirish lozim (Ism va Familiya ochiq matn sifatida olinadi).
RSA shifrlash algoritmidan foydalangan holda shifrlash jarayonini amalga oshirish lozim (Ism yoki Familiya ochiq matn sifatida olinadi).

№	p	q
	19	11
	17	7
	23	13
	29	5
	19	7
	5	17
	13	11
	31	7
	29	11
	29	17
	19	31
	13	17
	23	19
	7	17
	11	37
	13	23
	23	37
	37	7
	7	29
	11	13
	23	5
	29	7
	31	19

Nazorat savollari

RSA algorimti qanday algoritm?
Ochiq kalit nima uchun ishlatiladi?
Yopiq kalit nima uchun ishlatiladi?
Ochiq kalitli algoritmlar qanday maqsadlarda foydalaniladi?

6-amaliy mashg’ulot

Mavzu: OpenSSL kutubxonasidan foydalangan holda maʼlumotlarni RSA algoritmi yordamida shifrlash. RSA algoritmining shifrlash va deshifrlash dasturini loyihalash.
Ishning maqsadi: RSA algoritmiga oid masalalar yechish va RSA algoritmi dasturiy ta’minotini yaratish.
Nazariy qism. Assimetrik shifrlash usullari ma’lumotlarni shifrlashda va deshifrlashda alohida alohida kalitlardan foydalanadi. Shuning uchun ularda kalitlarni taqsimlash muammosi mavjud.
Assimetrik shirflash algoritmlaridan foydalanib ma’lumotlarni shirflash quyidagi jarayonlardan iborat:
Kalitlar generatsiyasi.
B foydalanuvchi kB maxfiy kalit asosida KB ochiq kalitni generatsiya qiladi. Ochiq kalit KB ochiq tarmoq orqali A foydalanuvchiga yoki tarmoqning boshqa foydalanuvchilariga uzatadi.
Ma’lumotlarni shirflash.
A foydalanuvchi yoki tarmoqning boshqa foydalanuvchisi KB ochiq kalitdan foydalangan holda ochiq ma’lumotni shifrlaydi va uni ochiq tarmoq orqali yuboradi.
Shifrmalumotni deshifrlash.
B foydalanuvchi qabul qilingan shifrmatnni o‘zining kB 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 taklifi bilan 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 C bloki 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, hisoblanadi),
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=3 va q=11.
2. n=p*q=7*17=119 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.
Topshiriq
O’z ismingizni RSA algoritmi yordamida shifrlang va deshifrlang
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.