7-Ma’ruza Mavzu: Ochiq kalitli kriptotizimlar Reja

Modul arifmetikasi. Ochiq kalitli kriptotizimlar, asosan modul arifmetikasiga asoslangani bois, dastlab unga to‘xtalib o‘tiladi.
Har qanday butun sonni m z ga bo‘lsak, bu songa tayin bir qoldiq to‘g‘ri keladi. Masalan, 5/2=2*2+1 bo‘lib, unda qoldiq 1 ga va butun qism 2 ga teng bo‘ladi. Kriptografíyada a sonni b songa bo‘lgandagi qoldiq r ga teng bo‘lsa, u quyidagicha belgilanadi: a mod b = r. Dasturlash tillarida esa a%b kabi belgilanadi.
Quyida qoldiq arifmetikasiga oid bir qancha misollar keltirilgan:
7mod3 = (3*2)mod3+1mod3 = 0+1 =1;
14mod3 = (3*4)mod3+2mod3 = 0+2 = 2;
2mod3 = (0*3)mod3+2mod3 = 2;
Smod7 = 5;
Bundan tashqari ochiq kalitli kriptografíyada sonning modul bo‘yicha teskarisini hisoblash muhim hisoblanadi. Masalan, odatiy matematikada a sonining teskarisi 1/a ga teng bo‘lsa, modul arifmetikasida esa a sonining n modul bo‘yicha teskarisi a^-1modn ko‘rinishida belgilanadi. Odatiy matematikada sonni uning teskarisiga ko‘paytmasi birga teng bo‘lgani kabi, modul arifmetikasida ham soning uning teskarisiga moduldagi ko‘paytmasi birga teng bo‘ladi. Ya’ni, a^-1modn = b bo‘lsa, u holda (a * b)modn = 1 tenglik o‘rinli bo‘ladi.
Izoh. Kriptografíyada modul sifatida (ya’ni, bo‘luvchi) faqat tub sonlardan foydalanish talab etiladi. Ya’ni, amodn tenglikdagi n har doim tub bo‘lishi lozim.
Aytaylik, 3 sonining 7 moduldagi teskarisini topish talab etilsin. Ya’ni, x ni topish talab etilsin: 3^-1mod7 = x. Yuqoridagi tenglik (3 * x)mod7 = 1 dan foydalanib, x ning o‘rniga son qo‘yib natijani hisoblash mumkin. Lekin ushbu jarayon ko‘p vaqt talab etadi (ayniqsa katta sonlarda).
Ochiq kalitli kriptosistemalari bir tomonli funksiyalar ko‘rinishi bo‘yicha farqlash mumkin. Bularning ichida RSA, El-Gamal va Mak-Elis sistemalarini aloxida tilga olish o‘rinli. Hozirda eng samarali va keng tarqalgan ochiq kalitli shifrlash algoritmi sifatida RSA algoritmini ko‘rsatish mumkin. RSA nomi algoritmni yaratuvchilari familiyalarining birinchi xarfidan olingan (Rivest, Shamir va Adleman).
Algoritm modul arifmetikasining darajaga ko‘tarish amalidan foydalanishga asoslangan. Algoritmni quyidagi qadamlar ketma-ketligi ko‘rinishida ifodalash mumkin.
1-qadam. Ikkita tub son p va q tanlanadi.
2-qadam. Kalitning ochiq tashkil etuvchisi n hosil qilinadi