Of cryptography

KO'RSATMA VA LOGARIFM

Ko'rsatkich va logarifm bir-biriga teskari hisoblanadi. Quyida ular orasidagi bog'lanish ko'rsatilgan, bunda a ko'rsatkich yoki logarifm asosi deb ataladi.


Ko'rsatkichlar: y = a^x → Logarifm: x = log_a y

Ko'rsatkichlar

Kriptografiyada keng tarqalgan modulli operatsiya eksponentatsiya hisoblanadi. Ya'ni, biz tez-tez hisoblashimiz kerak


y = a ^x mod n

10-bobda muhokama qilinadigan RSA kriptotizimi juda katta ko'rsatkichlar bilan shifrlash va shifrni ochish uchun eksponentatsiyadan foydalanadi. Afsuski, ko'pgina kompyuter tillarida ko'rsatkichni samarali hisoblay oladigan operator yo'q, ayniqsa ko'rsatkich juda katta bo'lsa. Ushbu turdagi hisob-kitoblarni yanada samaraliroq qilish uchun bizga samaraliroq algoritmlar kerak.

Tez eksponentsiya
Kvadrat va ko'paytirish usuli yordamida tez eksponentsiya qilish mumkin. An'anaviy algoritmlarda ko'rsatkichni taqlid qilish uchun faqat ko'paytirish qo'llaniladi, ammo tez ko'paytirish algoritmi kvadrat va ko'paytirishdan foydalanadi. Buning ortidagi asosiy fikr
usul ko'rsatkichni nb bitlarning ikkilik soni sifatida ko'rib chiqishdir (x0 dan xnb - 1 gacha). Masalan, x = 22 = (10110)2. Umuman olganda, x ni quyidagicha yozish mumkin:

b b
x = x_{n − 1} × 2^k−1 + x_{n − 2} × 2^k−2 + ^… + x₂ × 2² + x₁ × 2¹ + x₀ × 2⁰
Endi y = ax ni 9.6-rasmdagidek yozishimiz mumkin.

9.6-rasm. Kvadrat va ko'paytirish usulining g'oyasi

qaysi x_i
0 yoki 1







y = a⁹ = a¹⁰⁰¹² = a⁸ × 1 × 1 × a
Misol:
E'tibor bering, y nb shartlarining mahsulotidir.. Har bir atama 1 (mos keladigan bit 0 bo'lsa) yoki a2i (agar mos bit 1 bo'lsa). I Boshqacha qilib aytganda, a2i atamasi kiritilgan. Agar bit 1 bo'lsa, ko'paytirish, agar bit 0 bo'lsa, u qo'shilmaydi (1 ga ko'paytirish ta'sir qilmaydi). 9.6-rasmda algoritmni qanday yozish haqida umumiy tushuncha berilgan. Biz davom eta olamiz asosini kvadratga aylantiring, a, a2, a4, …, a2nb −1. Agar mos keladigan bit 0 bo'lsa, atama ko'paytirish jarayoniga kiritilmagan; agar bit 1 bo'lsa, u. Algoritm 9.7 aks ettiradi bu ikki kuzatish.



Algoritm 9.7 Kvadrat va ko'paytirish algoritmi uchun psevdokod

Algoritm 9.7 nb iteratsiyasidan foydalanadi. Har bir iteratsiyada u tegishli bitning qiymatini tekshiradi. Bitning qiymati 1 bo'lsa, u joriy bazani natijaning oldingi qiymatiga ko'paytiradi. Keyin keyingi iteratsiya uchun bazani kvadratga aylantiradi. E'tibor bering, oxirgi bosqichda kvadratlashtirish kerak emas (natija ishlatilmaydi).

Misol 9.45
9.7-rasmda 9.7 algoritmidan foydalangan holda y = ax ni hisoblash jarayoni ko'rsatilgan (oddiylik uchun modul ko'rsatilmagan). Bu holda, ikkilik tizimda x = 22 = (10110)2. Ko'rsatkich besh bitga ega.

Rasm 9.7 Kvadrat va ko'paytirish usuli yordamida a22 ni hisoblashni ko'rsatish

Square

Square
_a16 _a8
a4 _a2 _a1

Square

Square
y = a²²
x₄ = 1
x₃ = 0
x₂ = 1
y = a²

Multiply
x₁ = 1
y = 1
x₀ = 0
y = 1
Initiation

Kvadratchalash oxirgisidan tashqari har bir bosqichda amalga oshiriladi. Ko'paytirish faqat mos keladigan bit 1 bo'lsa amalga oshiriladi. 9.7-rasmda y ning qiymatlari y = a22 ga qadar asta-sekin qanday qurilganligi ko'rsatilgan. Qattiq qutilar ko'paytirish e'tiborga olinmasligini va y ning oldingi qiymati keyingi bosqichga o'tkazilishini anglatadi. 9.3-jadvalda y = 1722 mod 21 qiymati qanday hisoblanganligi ko'rsatilgan. Natijada y = 4.
Jadval 9.3 17²² mod 21hisoblash

i	xi	Ko’paytirish (Initialization: y = 1)	Kvadratlashtirish (Initialization: a = 17)
0	0	→	a = 17^2 mod 21 = 16
1	1	y = 1 × 16 mod 21 = 16 →	a = 16^2 mod 21 = 4
2	1	y = 16 × 4 mod 21 = 1 →	a = 4^2 mod 21 = 16
3	0	→	a = 16^2 mod 21 = 4
4	1	y = 1 × 4 mod 21 = 4 →

Murakkablik algoritmi 9.7 maksimal 2nb arifmetik amallardan foydalanadi, bunda nb modulning bitlardagi uzunligi (nb = log2n), shuning uchun algoritmning bit bilan ishlash murakkabligi O(nb) yoki polinom hisoblanadi.

Tez eksponensial algoritmning bit-operatsion murakkabligi polinomdir.

Muqobil algoritm Esda tutingki, 9.7 algoritmi x dagi bitlarning qiymatini o'ngdan chapga (eng muhimdan eng muhimgacha) tekshiradi. Teskari tartibni ishlatish uchun algoritm yozilishi mumkin. Biz yuqoridagi algoritmni tanladik, chunki kvadratlashtirish operatsiyasi ko'paytirish amalidan butunlay mustaqil; ishlov berish tezligini oshirish uchun ular parallel ravishda amalga oshirilishi mumkin. Muqobil algoritm mashq sifatida qoldiriladi.