Of cryptography

Kompozit kvadratik moslik moduli

Kompozitning kvadratik moslik moduli moduli tub to‘plamni yechish orqali amalga oshirilishi mumkin. Boshqacha qilib aytganda, agar bizda n ning faktorizatsiyasi mavjud bo'lsa, biz x2 ≡ a (mod n) ni parchalashimiz mumkin. Endi biz har bir parchalangan tenglamani (agar yechish mumkin bo'lsa) yechishimiz va 9.5-rasmda ko'rsatilganidek, x uchun k juft javobni topishimiz mumkin.




x² ≡ a mod (n)
n = p₁ × p₂ × . . . × p_k

x² ≡ a₁ (mod p₁) x² ≡ a₂ (mod p₁)


x² ≡ a_k (mod p_k)

x₁ ≡ ± b₁ (mod p₁) x₂ ≡ ± b₂ (mod p₁)


x_k ≡ ± b_k (mod p_k)
9.5-rasm. Kompozitsiyaning moslik modulining parchalanishi
K juft javobdan biz x uchun 2k qiymatni topish uchun Xitoy qoldiq teoremasi yordamida yechish mumkin bo'lgan 2k tenglamalar to'plamini yaratishimiz mumkin. Kriptografiyada odatda n shunday qilinadiki, n = p × q, bu k = 2 degan ma'noni anglatadi va bizda faqat to'rtta jami javob bor.


Misol 9.44
X2 ≡ 36 (mod 77) deb faraz qiling. Biz 77 = 7 × 11 ekanligini bilamiz. Biz yozishimiz mumkin


x² ≡ 36 (mod 7) ≡ 1 (mod 7) and x² ≡ 36 (mod 11) ≡ 3 (mod 11)

E'tibor bering, biz 3 va 7 ni 4k + 3 ko'rinishida tanladik, shuning uchun biz oldingi muhokama asosida tenglamalarni yechamiz. Bu tenglamalarning ikkalasi ham o'z to'plamlarida kvadrat qoldiqlarga ega. Javoblar x ≡ +1 (mod 7), x ≡ - 1 (mod 7), x ≡ + 5 (mod 11) va x ≡ - 5 (mod 11). Endi biz ulardan to'rtta tenglamalar to'plamini yaratishimiz mumkin:

Set 1: x ≡ +1 (mod 7) x ≡ + 5 (mod 11)
Set 2: x ≡ +1 (mod 7) x ≡ − 5 (mod 11)
Set 3: x ≡ −1 (mod 7) x ≡ + 5 (mod 11)
Set 4: x ≡ −1 (mod 7) x ≡ − 5 (mod 11)

Javoblar x = ± 6 va ± 27.

Murakkablik
Kvadrat moslik modulini kompozitsiyani yechish qanchalik qiyin? Asosiy vazifa modulni faktorizatsiya qilishdir. Boshqacha qilib aytganda, kompozitsiyaning kvadratik moslik modulini yechishning murakkabligi kompozit butun sonni faktorlarga ajratish bilan bir xil. Ko'rib turganimizdek, agar n juda katta bo'lsa, faktorizatsiya qilish mumkin emas.

Kvadrat moslik modulini kompozitsiyani yechish modulni faktorizatsiya qilish kabi qiyin..

5.