О‘zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi
Yüklə 5,01 Kb. Pdf görüntüsü
|
|
2.3.1. Modul arifmetikasi
Ochiq kalitli kriptotizimlarni chuqur o’rganishdan oldin ularning asosi hisoblangan sonlar nazariyasi bilan yaqindan tanishib chiqish muhim hisoblanadi. Ochiq kalitli kriptotizimlar asosan modul arifmetikasiga asoslangani bois, dastlab ularga to’xtalib o’tiladi. Har qanday butun sonni 𝑆𝑆 ∈ 𝑧𝑧 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. Kriptografiyada 𝑎𝑎 sonni 𝑎𝑎 songa bo’lgandagi qoldiq 𝑆𝑆 ga teng bo’lsa, u quyidagicha belgilanadi: 𝑎𝑎𝑆𝑆𝑒𝑒𝑑𝑑𝑎𝑎 ≡ 𝑆𝑆 . Dasturlash tillarida esa 𝑎𝑎 % 𝑎𝑎 kabi belgilanadi. Quyida qoldiq arifmetikasiga oid bir qancha misollar keltirilgan: − 7 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ (3 ∗ 2) 𝑆𝑆𝑒𝑒𝑑𝑑 3 + 1 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ 0 + 1 ≡ 1 − 14 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ (3 ∗ 4) 𝑆𝑆𝑒𝑒𝑑𝑑 3 + 2 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ 0 + 2 ≡ 2 − 2 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ (0 ∗ 3) 𝑆𝑆𝑒𝑒𝑑𝑑 3 + 2 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ 2 − 5 𝑆𝑆𝑒𝑒𝑑𝑑 7 ≡ 5 − − 2 𝑆𝑆𝑒𝑒𝑑𝑑 5 ≡ ( − 2 + 5) 𝑆𝑆𝑒𝑒𝑑𝑑 5 ≡ 3 𝑆𝑆𝑒𝑒𝑑𝑑 5 ≡ 3 − − 7 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ ( − 7 + 3) 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ − 4 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ ( − 4 + 3) 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ − 1 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ ( − 1 + 3) 𝑆𝑆𝑒𝑒𝑑𝑑 3 ≡ 2 Bundan tashqari ochiq kalitli kriptografiyada sonning modul bo’yicha teskarisini hisoblash muhim hisoblanadi. Masalan, odatiy matematikada 𝑎𝑎 sonining teskarisi 1 𝑎𝑎 ga teng bo’ladi. Modul arifmetikasida esa 𝑎𝑎 sonining 𝑛𝑛 modul bo’yicha teskarisi 𝑎𝑎 −1 𝑆𝑆𝑒𝑒𝑑𝑑𝑛𝑛 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, 𝑎𝑎 −1 𝑆𝑆𝑒𝑒𝑑𝑑𝑛𝑛 ≡ 𝑎𝑎 bo’lsa, u holda ( 𝑎𝑎 ∗ 𝑎𝑎 ) 𝑆𝑆𝑒𝑒𝑑𝑑𝑛𝑛 ≡ 1 tenglik o’rinli bo’ladi. 47 Izoh. Kriptografiyada modul sifatida (ya’ni, bo’luvchi) faqat tub sonlardan foydalanish talab etiladi. Ya’ni, amodn tenglikdagi n har doim tub bo’lishi talab etiladi. Misol tariqasida, 3 sonining 7 maydondagi teskarisini topish talab etilsin. Ya’ni, 𝑥𝑥 ni topish talab etilsin: 3 −1 𝑆𝑆𝑒𝑒𝑑𝑑 7 ≡ 𝑥𝑥 . Yuqoridagi tenglik (3 ∗ 𝑥𝑥 ) 𝑆𝑆𝑒𝑒𝑑𝑑 7 ≡ 1 dan foydalanib, 𝑥𝑥 ning o’rniga son qo’yib natijani hisoblash mumkin. Lekin ushbu jarayon ko’p vaqt talab etadi (ayniqsa katta sonlarda juda ham ko’p vaqt talab etiladi). Ushbu muammoni yechishning ko’plab usullari mavjud bo’lib, quyida ulardan biri bo’lgan qoldiqlar to’g’risidagi Yevklidning kengaytirilgan algoritmi dan foydalanib yechish usuli keltirilgan. Kengaytirlgan Yevklid algoritmi. Kengaytirlgan Yevklid algoritmi RSA kriptotizimi ochiq kaliti « ye » - ni topishda 𝑑𝑑 ∗ 𝑒𝑒 ≡ 1( 𝑆𝑆𝑒𝑒𝑑𝑑 ϕ ( 𝑛𝑛 )) tenglamaga duch kelinib, uni yechish bevosita 𝑎𝑎𝑥𝑥 + 𝑎𝑎𝑦𝑦 = 𝑑𝑑 , 𝑑𝑑 = EKUB( 𝑎𝑎 , 𝑎𝑎 ) tenglamaning butun yechimlarini topish masalasiga ekvivalent hamda bu algoritmga ko’ra berilgan a – soniga m 𝑒𝑒𝑑𝑑𝑛𝑛 bo’yicha teskari elementni topish imkonini beradi. Shuning uchun ham bu algoritm ishlash prinsiplarini keltirish muhim. Yüklə 5,01 Kb. Dostları ilə paylaş:
|