Axborot xavfsizligi” kafedrasi «Simmetrik kalitli kriptoalgoritmlarning xavfsizliklari tahlili» mavzusida individual loyihasi 2

RSA algoritmi
RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan olingan (Rivest, Shamir va Adleman). RSA algoritmi modul arifmetikasining darajaga ko’tarish amalidan foydalanishga asoslangan [20]. RSA algoritmida ochiq va shaxsiy kalitlar juftini generasiya qilish uchun ikkita katta uzunlikdagi 𝑝𝑝 va 𝑞𝑞 sonlari tanlanadi va ularning ko’paytmasi hisoblanadi: 𝑁𝑁 = 𝑝𝑝 ∗ 𝑞𝑞. Shundan so’ng 𝜑𝜑(𝑁𝑁) = (𝑝𝑝 − 1) ∗ (𝑞𝑞 − 1) bilan o’zaro tub bo’lgan, 𝑒𝑒 soni tanlanadi (𝜑𝜑(𝑁𝑁) funksiya ma’nosi quyida keltirilgan). Shundan so’ng 𝜑𝜑(𝑁𝑁) modulda 𝑒𝑒 sonining teskarisi hisoblanadi va u 𝑑𝑑 ga teng bo’ladi. Shundan so’ng, ikkita tub sonlarning (𝑝𝑝 va 𝑞𝑞) ko’paytmasi 𝑁𝑁 va 𝑒𝑒𝑒𝑒 = 1 𝑚𝑚𝑚𝑚𝑚𝑚 𝜑𝜑(𝑁𝑁) shartni qanoatlantiruvchi 𝑒𝑒 va 𝑑𝑑 sonlari mavjud. Shundan so’ng, 𝑝𝑝 va 𝑞𝑞 lar esdan chiqariladi (o’chirib tashlanadi). Bu yerda, 𝑁𝑁 modul hisoblanib, (𝑁𝑁, 𝑒𝑒) ochiq kalit juftini va 𝑑𝑑 maxfiy kalitni tashkil etadi. RSA algoritmida shifrlash va deshifrlash modul bo’yicha darajaga 51 oshirish asosida bajariladi. RSA algoritmida shifrlash uchun 𝑀𝑀 xabarni son ko’rinishida ifodalash talab etiladi va 𝑁𝑁 modul bo’yicha 𝑒𝑒 darajaga ko’tariladi, ya’ni 𝐶𝐶 = 𝑀𝑀𝑒𝑒 𝑚𝑚𝑚𝑚𝑚𝑚 𝑁𝑁. S ni deshifrlash uchun uni 𝑁𝑁 modul bo’yicha shaxsiy kalit 𝑑𝑑 darajaga ko’tarish talab etiladi: 𝑀𝑀 = 𝐶𝐶𝑑𝑑 𝑚𝑚𝑚𝑚𝑚𝑚 𝑁𝑁. Boshqacha aytganda RSA algoritmida xabar ochiq kalit bilan shifrlansa va shaxsiy kalit bilan deshifrlansa, 𝑀𝑀 = 𝐶𝐶𝑑𝑑 𝑚𝑚𝑚𝑚𝑚𝑚 𝑁𝑁 = 𝑀𝑀𝑒𝑒𝑒𝑒 𝑚𝑚𝑚𝑚𝑚𝑚 𝑁𝑁 tenglik to’g’riligini isbotlash zarur. Eyler teoremasi. Agar 𝑥𝑥 haqiqiqatdan 𝑛𝑛 bilan o’zaro tub bo’lsa, 𝑥𝑥𝜑𝜑(𝑛𝑛) = 1 𝑚𝑚𝑚𝑚𝑚𝑚 𝑛𝑛 bo’ladi. Bu yerda, 𝜑𝜑(𝑛𝑛) – funksiya, 𝑛𝑛 dan kichik va u bilan o’zaro tub bo’lgan sonlar miqdorini ko’rsatadi. Agar 𝑛𝑛 soni tub bo’lsa, 𝜑𝜑(𝑛𝑛) = 𝑛𝑛 − 1 bo’ladi. Shuning uchun 𝑒𝑒𝑒𝑒 = 1 𝑚𝑚𝑚𝑚𝑚𝑚 𝜑𝜑(𝑁𝑁) = 1 𝑚𝑚𝑚𝑚𝑚𝑚 (𝑝𝑝 − 1)(𝑞𝑞 − 1) tenglik kabi yozish mumkin. Mazkur tenglikning to’liq shakli aslida 𝑒𝑒𝑒𝑒 = 1 𝑚𝑚𝑚𝑚𝑚𝑚 𝜑𝜑(𝑁𝑁) + 𝑘𝑘 𝜑𝜑(𝑁𝑁) ga teng. Ya’ni, 𝑒𝑒𝑒𝑒 ko’paytmani 𝜑𝜑(𝑁𝑁) ga bo’lganda 𝑘𝑘 tadan tegib, bir qoldiq qolgan. Shuning uchun ushbu tenglikni quyidagicha yozish mumkin: 𝑒𝑒𝑒𝑒 − 1 = 𝑘𝑘 𝜑𝜑(𝑁𝑁). Ushbu tengliklardan, RSA algoritmining to’g’ri ishlashini tasdiqlash mumkin: 𝐶𝐶𝑑𝑑 = 𝑀𝑀𝑒𝑒𝑒𝑒 = 𝑀𝑀(𝑒𝑒𝑒𝑒−1)+1 = 𝑀𝑀 ∗ 𝑀𝑀𝑒𝑒𝑒𝑒−1 = 𝑀𝑀 ∗ 𝑀𝑀𝑘𝑘 𝜑𝜑(𝑁𝑁) = 𝑀𝑀 ∗ 1𝑘𝑘 = 𝑀𝑀 𝑚𝑚𝑚𝑚𝑚𝑚 𝑁𝑁. Aytaylik, RSA algoritmida ma’lumotni shifrlash va deshifrlash amallarini tanlab olingan (𝑝𝑝 = 11 va 𝑞𝑞 = 3) “katta” sonlar ustida amalga oshirish talab qilinsin. Mazkur holda modul 𝑁𝑁 = 𝑝𝑝 ∗ 𝑞𝑞 = 33 ga teng bo’ladi va 𝜑𝜑(𝑁𝑁) = (𝑝𝑝 − 1)(𝑞𝑞 − 1) = 20 ga teng bo’ladi. U holda shifrlash uchun zarur bo’lgan daraja e ni (𝑒𝑒 = 3) ga teng deb olish mumkin. Sababi, 3 soni 𝜑𝜑(𝑁𝑁) = 20 bilan o’zaro tubdir. Shundan so’ng, Evklidning kengaytirilgan algoritmi asosida deshifrlash kaliti ( 𝑑𝑑 = 7 ) aniqlanadi. Ya’ni, 𝑒𝑒𝑒𝑒 = 3 ∗ 7 = 1 𝑚𝑚𝑚𝑚𝑚𝑚 20. U holda A tomonning ochiq kalit jufti (𝑁𝑁, 𝑒𝑒) = (33,3) va shaxsiy kaliti esa 𝑑𝑑 = 7 ga teng. 52 Shundan so’ng, A tomon o’zining ochiq kalitini barchaga uzatadi. Biroq, shaxsiy kalitini maxfiy saqlaydi. Faraz qilaylik, B tomon A tomonga 𝑀𝑀 = 15 ma’lumotni shifrlab yubormoqchi. Buning uchun B tomon A tomonning ochiq kaliti juftini (𝑁𝑁, 𝑒𝑒) = (33,3) oladi va shifrmatnni quyidagicha hisoblaydi: 𝐶𝐶 = 𝑀𝑀𝑒𝑒 𝑚𝑚𝑚𝑚𝑚𝑚 𝑁𝑁 = 153 = 3375 = 9 𝑚𝑚𝑚𝑚𝑚𝑚 33 va uni A tomonga yuboradi. A tomon 𝐶𝐶 = 9 shifrmatnni deshifrlash uchun shaxsiy kalit 𝑑𝑑 = 7 dan foydalanadi: 𝑀𝑀 = 𝐶𝐶𝑑𝑑 𝑚𝑚𝑚𝑚𝑚𝑚 𝑁𝑁 = 97 = 4782969 = 144938 ∗ 33 + 15 = 15 𝑚𝑚𝑚𝑚𝑚𝑚 33 Agar RSA algoritmida kichik tub sonlardan (𝑝𝑝 va 𝑞𝑞 uchun) foydalanilgan taqdirda, hujumchi ochik bo’lgan 𝑁𝑁 ni osonlik bilan ikkita tub sonning ko’paytmasi ko’rinishida yozishi mumkin. Shundan so’ng, ochiq kalitning ikkinchi qism 𝑒𝑒 dan foydalangan holda, shaxsiy kalit 𝑑𝑑 ni hisoblay oladi. Shuning uchun RSA algoritmidan amalda foydalanish uchun tanlanuvchi tub sonlar uzunligi kamida 2048 bit bo’lishi talab etiladi. Bundan tashqari, RSA algoritmini buzish faqat faktorlash muammosiga bog’liqligi isbotlanmagan. Boshqacha aytganda, RSA algoritmini buzishning faktorlash muammosini yechishdan tashqari biror usuli aniqlanmagan.