#crypto Mavzu MOD
1. “mod” nima?
Tasavvur qil: sening 10 ta joyli soating bor (0 dan 9 gacha).
Agar soat 7 bo‘lsa va 6 soat o‘tsa, soat 13 bo‘lishi kerak edi, lekin bizning soatda 3 bo‘ladi.
Bu mod 10 degan gap.
Matematikada:
13 mod 10 = 3
Demak "mod" – bu bo‘lgandagi qoldiq.
2. Misollar
17 mod 5 = 2
(17 ni 5 ga bo‘lsak, 3 marta bo‘linadi, 2 qoldiq qoladi)
25 mod 7 = 4
(25 ni 7 ga bo‘lsak, 3 marta bo‘linadi, 4 qoldiq qoladi)
9 mod 3 = 0
(3 ga bo‘linadi, qoldiq qolmaydi)
3. Amallar
Mod bo‘yicha hisoblashning eng katta foydasi – katta sonlarni kichik sonlar bilan ishlashga aylantiradi.
Qo‘shish:
(a + b) mod m = ((a mod m) + (b mod m)) mod m
Misol: (7 + 9) mod 5 = (2 + 4) mod 5 = 1
Ko‘paytirish:
(a × b) mod m = ((a mod m) × (b mod m)) mod m
Misol: (6 × 8) mod 7 = (6 × 1) mod 7 = 6
Daraja olish (modular exponentiation):
(a^b) mod m – ko‘p kriptografiyada ishlatiladi.
Misol: (3^4) mod 5 = 81 mod 5 = 1
4. Qayerda ishlatiladi?
RSA: (x^e) mod n — shifrlash va (y^d) mod n — deshifrlashda.
Diffie–Hellman: (g^a) mod p va (g^b) mod p — kalit almashishda.
Hash funktsiyalarda: ichki matematik hisoblarda.
5. Senga oddiy qoida
“mod” ishlaganda, hech qachon sonlarni to‘liq hisoblash shart emas – har bir bosqichda qoldiqni olib borish kifoya.
Bu katta sonlar bilan ishlashni osonlashtiradi.
📌 Bugungi vazifa (sodda versiya)
Quyidagilarni hisoblab, o'zingizni sionab ko'ring.
29 mod 5
(123 + 456) mod 17
(13 × 19) mod 7
(3^10) mod 5
@cisco_server
1. “mod” nima?
Tasavvur qil: sening 10 ta joyli soating bor (0 dan 9 gacha).
Agar soat 7 bo‘lsa va 6 soat o‘tsa, soat 13 bo‘lishi kerak edi, lekin bizning soatda 3 bo‘ladi.
Bu mod 10 degan gap.
Matematikada:
13 mod 10 = 3
Demak "mod" – bu bo‘lgandagi qoldiq.
2. Misollar
17 mod 5 = 2
(17 ni 5 ga bo‘lsak, 3 marta bo‘linadi, 2 qoldiq qoladi)
25 mod 7 = 4
(25 ni 7 ga bo‘lsak, 3 marta bo‘linadi, 4 qoldiq qoladi)
9 mod 3 = 0
(3 ga bo‘linadi, qoldiq qolmaydi)
3. Amallar
Mod bo‘yicha hisoblashning eng katta foydasi – katta sonlarni kichik sonlar bilan ishlashga aylantiradi.
Qo‘shish:
(a + b) mod m = ((a mod m) + (b mod m)) mod m
Misol: (7 + 9) mod 5 = (2 + 4) mod 5 = 1
Ko‘paytirish:
(a × b) mod m = ((a mod m) × (b mod m)) mod m
Misol: (6 × 8) mod 7 = (6 × 1) mod 7 = 6
Daraja olish (modular exponentiation):
(a^b) mod m – ko‘p kriptografiyada ishlatiladi.
Misol: (3^4) mod 5 = 81 mod 5 = 1
4. Qayerda ishlatiladi?
RSA: (x^e) mod n — shifrlash va (y^d) mod n — deshifrlashda.
Diffie–Hellman: (g^a) mod p va (g^b) mod p — kalit almashishda.
Hash funktsiyalarda: ichki matematik hisoblarda.
5. Senga oddiy qoida
“mod” ishlaganda, hech qachon sonlarni to‘liq hisoblash shart emas – har bir bosqichda qoldiqni olib borish kifoya.
Bu katta sonlar bilan ishlashni osonlashtiradi.
📌 Bugungi vazifa (sodda versiya)
Quyidagilarni hisoblab, o'zingizni sionab ko'ring.
29 mod 5
(123 + 456) mod 17
(13 × 19) mod 7
(3^10) mod 5
@cisco_server
❤2👍2👏1
#crypto Mavzu: Modular Inverse
🎯 Modular inverse – Teskari son nima va uni qanday topamiz?
Oddiy tushuntirish:
Tasavvur qil, senga m ta stul berildi. Sen shunday sonni topishing kerakki, uni boshqa bir songa ko‘paytirganda qoldiq 1 chiqsin.
💡 Masalan:
7 ta stul bor.
Agar 3 × 5 = 15 bo‘lsa,
15 ni 7 ga bo‘lsak → qoldiq 1 chiqadi.
Demak, 5 – bu 3 ning teskari soni (mod 7).
📏 Umumiy formula:
java
Copy
Edit
(a × x) mod m = 1
Agar bu tenglik to‘g‘ri bo‘lsa, x – bu a ning m bo‘yicha teskari soni.
🔹 Bruteforce (eng sodda) usul
Keling, 7 ning 26 ga teskari sonini topamiz:
📌 Qayerlarda ishlatiladi?
1️⃣ Kriptografiya 🔐
RSA, ElGamal, ECC kabi algoritmlarda kalit yaratish va shifrlash jarayonida teskari sonlar kerak bo‘ladi.
Masalan, RSA’da yopiq kalit (d) ni hisoblashda (e × d) mod φ(n) = 1 formulasi ishlatiladi.
2️⃣ Matematik tenglamalar modulyar ko‘rinishda 📊
Masalan, (a × x) mod m = b tipidagi tenglamani yechish uchun.
Oddiy bo‘lish o‘rniga, x = b × a⁻¹ mod m qilib yechamiz (bu yerda a⁻¹ – teskari son).
3️⃣ Komp'yuter algoritmlari va dasturlash 💻
Fermat yoki Katta sonlar bilan ishlashda tezkor hisoblash.
Masalan, kombinatorika (nCr) formulalarida modul bo‘yicha bo‘lish.
4️⃣ Xitoy qoldiq teoremasi (Chinese Remainder Theorem) 🀄️
Parallel hisoblashlar va katta tenglamalar tizimini yechishda teskari son ishlatiladi.
@cisco_server
🎯 Modular inverse – Teskari son nima va uni qanday topamiz?
Oddiy tushuntirish:
Tasavvur qil, senga m ta stul berildi. Sen shunday sonni topishing kerakki, uni boshqa bir songa ko‘paytirganda qoldiq 1 chiqsin.
💡 Masalan:
7 ta stul bor.
Agar 3 × 5 = 15 bo‘lsa,
15 ni 7 ga bo‘lsak → qoldiq 1 chiqadi.
Demak, 5 – bu 3 ning teskari soni (mod 7).
📏 Umumiy formula:
java
Copy
Edit
(a × x) mod m = 1
Agar bu tenglik to‘g‘ri bo‘lsa, x – bu a ning m bo‘yicha teskari soni.
🔹 Bruteforce (eng sodda) usul
Keling, 7 ning 26 ga teskari sonini topamiz:
7 × 1 mod 26 = 7 ❌
7 × 2 mod 26 = 14 ❌
7 × 3 mod 26 = 21 ❌
7 × 4 mod 26 = 2 ❌
7 × 5 mod 26 = 9 ❌
...
7 × 15 mod 26 = 105 → 105 mod 26 = 1 ✅
📌 Javob: 15
Chunki (7 × 15) mod 26 = 1
📌 Qayerlarda ishlatiladi?
1️⃣ Kriptografiya 🔐
RSA, ElGamal, ECC kabi algoritmlarda kalit yaratish va shifrlash jarayonida teskari sonlar kerak bo‘ladi.
Masalan, RSA’da yopiq kalit (d) ni hisoblashda (e × d) mod φ(n) = 1 formulasi ishlatiladi.
2️⃣ Matematik tenglamalar modulyar ko‘rinishda 📊
Masalan, (a × x) mod m = b tipidagi tenglamani yechish uchun.
Oddiy bo‘lish o‘rniga, x = b × a⁻¹ mod m qilib yechamiz (bu yerda a⁻¹ – teskari son).
3️⃣ Komp'yuter algoritmlari va dasturlash 💻
Fermat yoki Katta sonlar bilan ishlashda tezkor hisoblash.
Masalan, kombinatorika (nCr) formulalarida modul bo‘yicha bo‘lish.
4️⃣ Xitoy qoldiq teoremasi (Chinese Remainder Theorem) 🀄️
Parallel hisoblashlar va katta tenglamalar tizimini yechishda teskari son ishlatiladi.
@cisco_server
❤2
#crypto CRT nima?
Chinese Remainder Theorem (CRT) — bu bir nechta modul bo‘yicha berilgan qoldiqlardan sonni topish usuli.
Misol:
Biror son bor, u quyidagicha:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Savol: x nechchi?
2. Oddiy tushuntirish
CRT shuni aytadi: agar modullar (3, 5, 7) o‘zaro tub bo‘lsa (ya’ni bir-biriga bo‘linmasa), unda yechim yagona va uni oddiy hisob bilan topish mumkin.
3. Misolni yechamiz (qadam-baqadam)
1️⃣ Modullarni ko‘paytiramiz:
N = 3 × 5 × 7 = 105
2️⃣ Har bir modul bo‘yicha N_i topamiz:
N1 = 105 / 3 = 35
N2 = 105 / 5 = 21
N3 = 105 / 7 = 15
3️⃣ Har bir N_i ning teskari sonini (mod mi bo‘yicha) topamiz:
35 × m1 ≡ 1 (mod 3) → m1 = 2 (chunki 35×2 = 70 ≡ 1 mod 3)
21 × m2 ≡ 1 (mod 5) → m2 = 1
15 × m3 ≡ 1 (mod 7) → m3 = 1
4️⃣ Natijani hisoblaymiz:
x = (qoldiq1 × N1 × m1) + (qoldiq2 × N2 × m2) + (qoldiq3 × N3 × m3)
x = (2 × 35 × 2) + (3 × 21 × 1) + (2 × 15 × 1)
x = 140 + 63 + 30 = 233
5️⃣ Umumiy modul bo‘yicha qisqartiramiz:
x mod 105 = 233 mod 105 = 23
✅ Javob: x = 23 (bu son berilgan uchta shartni qanoatlantiradi)
4. Tekshiruv
23 mod 3 = 2 ✅
23 mod 5 = 3 ✅
23 mod 7 = 2 ✅
📌 CTF Crypto’da CRT:
RSA: Agar sen bir xil plaintext’ni bir nechta turli moduluslar bilan shifrlangan holda olsang (lekin exponent bir xil bo‘lsa), CRT yordamida plaintext’ni ochib olishing mumkin.
Optimization: Decryption tezligini oshirish uchun RSA’da p va q bo‘yicha alohida hisoblash, keyin CRT bilan natijani birlashtirish ishlatiladi.
Mustaqil yechish uchun:
x≡1(mod4)
x≡2(mod5)
x≡3(mod7)
x ni toping
@cisco_server
Chinese Remainder Theorem (CRT) — bu bir nechta modul bo‘yicha berilgan qoldiqlardan sonni topish usuli.
Misol:
Biror son bor, u quyidagicha:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Savol: x nechchi?
2. Oddiy tushuntirish
CRT shuni aytadi: agar modullar (3, 5, 7) o‘zaro tub bo‘lsa (ya’ni bir-biriga bo‘linmasa), unda yechim yagona va uni oddiy hisob bilan topish mumkin.
3. Misolni yechamiz (qadam-baqadam)
1️⃣ Modullarni ko‘paytiramiz:
N = 3 × 5 × 7 = 105
2️⃣ Har bir modul bo‘yicha N_i topamiz:
N1 = 105 / 3 = 35
N2 = 105 / 5 = 21
N3 = 105 / 7 = 15
3️⃣ Har bir N_i ning teskari sonini (mod mi bo‘yicha) topamiz:
35 × m1 ≡ 1 (mod 3) → m1 = 2 (chunki 35×2 = 70 ≡ 1 mod 3)
21 × m2 ≡ 1 (mod 5) → m2 = 1
15 × m3 ≡ 1 (mod 7) → m3 = 1
4️⃣ Natijani hisoblaymiz:
x = (qoldiq1 × N1 × m1) + (qoldiq2 × N2 × m2) + (qoldiq3 × N3 × m3)
x = (2 × 35 × 2) + (3 × 21 × 1) + (2 × 15 × 1)
x = 140 + 63 + 30 = 233
5️⃣ Umumiy modul bo‘yicha qisqartiramiz:
x mod 105 = 233 mod 105 = 23
✅ Javob: x = 23 (bu son berilgan uchta shartni qanoatlantiradi)
4. Tekshiruv
23 mod 3 = 2 ✅
23 mod 5 = 3 ✅
23 mod 7 = 2 ✅
📌 CTF Crypto’da CRT:
RSA: Agar sen bir xil plaintext’ni bir nechta turli moduluslar bilan shifrlangan holda olsang (lekin exponent bir xil bo‘lsa), CRT yordamida plaintext’ni ochib olishing mumkin.
Optimization: Decryption tezligini oshirish uchun RSA’da p va q bo‘yicha alohida hisoblash, keyin CRT bilan natijani birlashtirish ishlatiladi.
Mustaqil yechish uchun:
x≡1(mod4)
x≡2(mod5)
x≡3(mod7)
x ni toping
@cisco_server
👍3❤2