Oʻzbekiston respublikasi axborot texnologiyalari

Modul arithmetic
• Cryptography aa sonni bb songa bўlgandagy koldik rr ga teng bўlsa, u ҳolda kuyidagicha belgilanadi: aaaaaaaabb≡rr.
- Dusturlash tillarida esa aaabb kabi belgilanadi.
• Cryptography modul sifatida (ya'ni, bўluvchi) faqat tub sonlardan foydalanish talab etiladi.
– Ya'ni, aa aaaaaa nn tenglikdaghi nn ҳar doim tub bўlishi talab etiladi.
• Misollar:
• 7𝑎𝑎𝑎𝑎𝑎𝑎𝑚 ≡(𝑚∗2)𝑎𝑎𝑎𝑎𝑎𝑎𝑚+1𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡0+1≡1
• 14𝑎𝑎𝑎𝑎𝑎𝑎𝑚 ≡(𝑚∗4)𝑎𝑎𝑎𝑎𝑎𝑎𝑚+2𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡0+2≡2
• 2𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡(0∗𝑚)𝑎𝑎𝑎𝑎𝑎𝑎𝑚+2𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡2
• 5𝑎𝑎𝑎𝑎𝑎𝑎7≡5
• −2𝑎𝑎𝑎𝑎𝑎𝑎5≡(−2+5)𝑎𝑎𝑎𝑎𝑎𝑎5≡𝑚𝑎𝑎𝑎𝑎𝑎𝑎5≡𝑚
• −7𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡(−7+𝑚)𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡−4𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡(−4+𝑚)𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡
−1𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡(−1+𝑚)𝑎𝑎𝑎𝑎𝑎𝑎𝑚≡2
Modul arithmetic
• 𝟑𝟑^-1 𝒎𝒎𝒎𝒎𝒎𝒎𝒎𝒎≡1/33 𝒎𝒎𝒎𝒎𝒎𝒎𝒎𝒎≡?
• Ushbu muammoni echishda Euclidning kengaitirilgan algorithmidan foydalanish mumkin.
• Agar aa⁻¹aaaaaann≡bb bўlsa,u ҳolda (aa∗bb)aaaaaann≡1 tenglik ўrinli bўladi.
• 𝑚⁻¹𝑎𝑎𝑎𝑎𝑎𝑎7 ≡ 𝑥𝑥
• 7 = 𝑚 ∗ 2 + 1
• 𝑚 = 1 ∗ 𝑚 + 0
• Demak, 1 sony 3 va 7 sonlari uchun ECUB bўladi.
• Ohirgi tenglikdan boshlab kuyidagicha teskari amalga oshiriladi:
• 1=7−𝑚∗2=7+(−2∗𝑚)=7∗1+(−2∗𝑚)
Modul arithmetic
• Tenglikni ikki tomonini modulga (aaaaaa7) olinadi: ((7∗1)aaaaaa7+(−2∗m)aaaaaa7)aaaaaa7≡1aaaaaa 7
Yoki
(−2∗𝑚)𝑎𝑎𝑎𝑎𝑎𝑎7≡1𝑎𝑎𝑎𝑎𝑎𝑎7≡1
• Ushbu tenglikni (m∗xx)aaaaaa7≡1 hectares
xx=−2 ha tengligini yoki −2aaaaaa7=5 ligani topish mumkin.
Ya'ni, (m∗5)aaaaa7≡1 tenglik ўrinli.
RSA algorithms.
• RSA ochiq kalitli cipherlash algorithms mualliflar bўlgan uchta olimlar, Rivest, Shamir va Adleman, sharafiga қўyilgan.
• RSA algorithms katta sonlarni factorlash muammosiga asoslanadi.
• RSA algorithmida kuyidagi zharayonlar mavzhud:
– Kalitni generationalash;
– Ciphrlash;
- Decipher.