Referat shifrlash klassifikasiyasi. Blokli va uzluksiz shifrlash algoritimlari. Farg‘ona 2023 -yil mavzu: Shifrlash klassifikasiyasi. Blokli va uzluksiz shifrlash algoritimlari

RSA algoritmi. RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan olingan (Rivest, Shamir va Adleman). RSA algoritmi modul arifmetikasining darajaga ko‘tarish amalidan foydalanishga asoslangan.
RSA algoritmida ochiq va shaxsiy kalitlar juftini generatsiyalash 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 sonning (𝑝 𝑣𝑎 𝑞) ko‘paytmasi 𝑁 va 𝑒𝑑 = 1 𝑚𝑜𝑑 𝜑⁽𝑁⁾ shartni qanoatlantiruvchi 𝑒 va 𝑑 sonlari mavjud. Shundan so‘ng, 𝑝 𝑣𝑎 𝑞 lar esdan chiqariladi (o‘chirib tashlanadi).
Bu yerda, 𝑁 modul hisoblanib, (𝑁, 𝑒) ochiq kalit juftini va 𝑑 maxfiy kalitni tashkil etadi. RSA algoritmida shifrlash va rasshifrovkalash modul bo‘yicha darajaga oshirish asosida bajariladi. RSA algoritmida shifrlash uchun 𝑀 xabarni son ko‘rinishida ifodalash talab etiladi va 𝑁 modul bo‘yicha 𝑒 darajaga ko‘tariladi, ya’ni

𝐶 = 𝑀^𝑒 𝑚𝑜𝑑 𝑁.

𝐶 ni rasshifrovkalash 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 rasshifrovkalansa, 𝑀 = 𝐶^𝑑 𝑚𝑜𝑑 𝑁 =
𝑀^𝑒𝑑 𝑚𝑜𝑑 𝑁 tenglikning to‘g‘riligini isbotlash zarur.
Aytaylik, RSA algoritmida ma’lumotni shifrlash va rasshifrovkalash amallarini tanlab olingan (𝑝 = 11 𝑣𝑎 𝑞 = 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 rasshifrovkalash 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 bo‘ladi.
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:

𝐶 = 𝑀^𝑒 𝑚𝑜𝑑 𝑁 = 15³ = 3375 = 9 𝑚𝑜𝑑 33

va uni A tomonga yuboradi.
A tomon 𝐶 = 9 shifrmatnni rasshifrovkalash uchun shaxsiy kalit
𝑑 = 7 dan foydalanadi:

𝑀 = 𝐶^𝑑 𝑚𝑜𝑑 𝑁 = 9⁷ = 4782969 = 144938 ∗ 33 + 15 = 15 𝑚𝑜𝑑 33

Agar RSA algoritmida kichik tub sonlardan (𝑝 𝑣𝑎 𝑞 𝑢𝑐ℎ𝑢𝑛) 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. Simmetrik kalitli shifrlarda ochiq matn 𝑃 shifrlansa, shifrmatn 𝐶 hosil bo‘ladi degan shartli belgilash kiritilgan edi. Ochiq kalitli shifrlash tizimlarida esa xabar 𝑀 shifrlansa, shifrmatn 𝐶 hosil bo‘ladi deb shartli belgilash kiritiladi.
Ochiq kalitli kriptografik tizimlardan foydalanish uchun, B tomon ochiq kalit va unga mos bo‘lgan shaxsiy kalit juftiga ega bo‘lishi talab etiladi. B tomonning ochiq kaliti kimga ma’lum bo‘lsa, u ma’lumotni shifrlashi mumkin. Shifrlangan xabarni ochish faqat shaxsiy kalit egasi bo‘lgan B tomonga joiz.
Modul arifmetikasi. Ochiq kalitli kriptotizimlar, asosan modul arifmetikasiga asoslangani bois, dastlab unga to‘xtalib o‘tiladi.
Har qanday butun sonni 𝑚 𝑧 ga bo‘lsak, bu songa tayin bir
qoldiq to‘g‘ri keladi. Masalan, 5 = 2 ∗ 2 + 1 bo‘lib, unda qoldiq 1 ga va
2
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‘lsa, 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.
Izoh. Kriptografiyada 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, 𝑥 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).
RSA algoritmi. RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan olingan (Rivest, Shamir va Adleman). RSA algoritmi modul arifmetikasining darajaga ko‘tarish amalidan foydalanishga asoslangan.
RSA algoritmida ochiq va shaxsiy kalitlar juftini generatsiyalash 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 sonning (𝑝 𝑣𝑎 𝑞) ko‘paytmasi 𝑁 va 𝑒𝑑 = 1 𝑚𝑜𝑑 𝜑(𝑁) shartni qanoatlantiruvchi 𝑒 va 𝑑 sonlari mavjud. Shundan so‘ng, 𝑝 𝑣𝑎 𝑞 lar esdan chiqariladi (o‘chirib tashlanadi).
Bu yerda, 𝑁 modul hisoblanib, (𝑁, 𝑒) ochiq kalit juftini va 𝑑 maxfiy kalitni tashkil etadi. RSA algoritmida shifrlash va rasshifrovkalash modul bo‘yicha darajaga oshirish asosida bajariladi. RSA algoritmida shifrlash uchun 𝑀 xabarni son ko‘rinishida ifodalash talab etiladi va 𝑁 modul bo‘yicha 𝑒 darajaga ko‘tariladi, ya’ni

𝐶 = 𝑀𝑒 𝑚𝑜𝑑 𝑁.

𝐶 ni rasshifrovkalash 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 rasshifrovkalansa, 𝑀 = 𝐶𝑑 𝑚𝑜𝑑 𝑁 =
𝑀𝑒𝑑 𝑚𝑜𝑑 𝑁 tenglikning to‘g‘riligini isbotlash zarur.
Aytaylik, RSA algoritmida ma’lumotni shifrlash va rasshifrovkalash amallarini tanlab olingan (𝑝 = 11 𝑣𝑎 𝑞 = 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 rasshifrovkalash 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 bo‘ladi.
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 rasshifrovkalash uchun shaxsiy kalit
𝑑 = 7 dan foydalanadi:

𝑀 = 𝐶𝑑 𝑚𝑜𝑑 𝑁 = 97 = 4782969 = 144938 ∗ 33 + 15 = 15 𝑚𝑜𝑑 33

Agar RSA algoritmida kichik tub sonlardan (𝑝 𝑣𝑎 𝑞 𝑢𝑐ℎ𝑢𝑛) 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.