Of cryptography

Logarifm

Kriptografiyada modulli logarifmni ham muhokama qilishimiz kerak. Agar biz shifrlash yoki shifrni ochish uchun eksponentsiyadan foydalansak, raqib hujum qilish uchun logarifmdan foydalanishi mumkin. Biz eksponentatsiyani teskari ko'rsatish qanchalik qiyinligini bilishimiz kerak.


To'liq qidiruv
Aqlga kelishi mumkin bo'lgan birinchi yechim x = logay (mod n) ni hal qilishdir. Berilgan y qiymatini topguncha y = ax mod n ni uzluksiz hisoblaydigan algoritm yozishimiz mumkin. 9.8 algoritmi ushbu yondashuvni ko'rsatadi.



Algoritm 9.8 Modulli logarifm uchun to'liq qidiruv


Algoritm 9.8, albatta, juda samarasiz. Bit bilan ishlashning murakkabligi O(2nb) yoki eksponensialdir.


Diskret logarifm
Ikkinchi yondashuv diskret logarifm tushunchasidan foydalanishdir. Ushbu kontseptsiyani tushunish multiplikativ guruhlarning ba'zi xususiyatlarini tushunishni talab qiladi.
Chekli multiplikativ guruh Kriptografiyada biz ko'pincha ko'paytiruvchi chekli guruhdan foydalanamiz: G = bunda operatsiya ko'paytirishdir. Zn* toʻplami n ga nisbatan tub boʻlgan 1 dan n−1 gacha boʻlgan butun sonlarni oʻz ichiga oladi; identifikatsiya elementi e = 1. E'tibor bering, guruhning moduli tub bo'lsa, bizda G = bo'ladi. Bu guruh birinchi guruhning alohida holatidir, shuning uchun biz ushbu bo'limda birinchi guruhga e'tibor qaratamiz.

Guruh tartibi 4-bobda biz |G| sonli guruhning G guruhidagi elementlar soni boʻlish tartibini muhokama qildik. guruh ph(n). Biz ph(n) ni qanday hisoblashni ko'rsatdik, qachonki n ni tub sonlarga ajratish mumkin.

Misol9.46
G = guruhning tartibi qanday? |G| = ph(21) = ph(3) × ph(7) = 2 × 6 =12. Bu guruhda 12 ta element mavjud: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 va 20. Hammasi nisbatan tub elementlardir. 21 bilan.
Elementning tartibi 4-bobda biz ord(a) elementning tartibini ham muhokama qildik. G = da biz bir xil ta'rif bilan davom etamiz. Elementning tartibi a, eng kichik butun i soni bo'lib, ai ≡ e (mod n) bo'ladi. Bu holda e identifikatsiya elementi 1 ga teng.


Misol 9.47
G = dagi barcha elementlarning tartibini toping.
Yechim
Bu guruhda faqat ph(10) = 4 ta element mavjud: 1, 3, 7, 9. Har bir elementning tartibini sinash va xatolik yoʻli bilan topishimiz mumkin. Biroq, 4-bobni eslaylik, elementning tartibi uning tartibini ajratadi
guruh (Lagranj teoremasi). 4 ni bo'ladigan yagona butun sonlar 1, 2 va 4 dir, ya'ni har bir holatda elementning tartibini topish uchun faqat shu kuchlarni tekshirishimiz kerak.
.
a. 1¹ ≡ 1 mod (10) → ord(1) = 1.
b. 3¹ ≡ 3 mod (10); 3² ≡ 9 mod (10); 3⁴ ≡ 1 mod (10) → ord(3) = 4.
c. 7¹ ≡ 7 mod (10); 7² ≡ 9 mod (10); 7⁴ ≡ 1 mod (10) → ord(7) = 4.
d. 9¹ ≡ 9 mod (10); 9² ≡ 1 mod (10) → ord(9) = 2.
Eyler teoremasi Boshqa tegishli teorema Eyler teoremasi (ushbu bobda muhokama qilingan) bo‘lib, agar a G = a'zosi bo‘lsa, aph(n) = 1 mod n
Bu teorema juda foydali, chunki u munosabatlar ai ≡ 1 (mod n) ekanligini ko'rsatadi.
i = ph(n) bo‘lganda ham, i < ph(n) bo‘lganda ham amal qiladi. Boshqacha qilib aytganda, bu munosabat kamida bir marta amalga oshiriladi.


Misol 9.48
9.4-jadvalda G = guruhi uchun ai ≡ x (mod 8) natijasi ko'rsatilgan. E'tibor bering, ph(8) = 4. Elementlar 1, 3, 5 va 7.

Jadval 9.4 9.48-misoldagi elementlarning tartiblarini topish

i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7