Discrete Logarithm Problem (DLP)
โจทย์คณิตศาสตร์ที่ยาก ใช้เป็นพื้นฐานความปลอดภัยของระบบ Public-Key หลายระบบ
นิยามทางคณิตศาสตร์
- ให้ G เป็น Cyclic Group ขนาด n, Generator g
- ทุก h ∈ G เขียนได้เป็น h = gˣ สำหรับ x ∈ Zₙ
- DLP: หา x จาก g, h, G (x = logg h)
ตัวอย่างใน Zp* (Multiplicative Group Modulo Prime)
- p = 17, g = 3 (Generator)
- 3⁴ = 81 ≡ 13 (mod 17)
- DLP: หา k จาก 3ᵏ ≡ 13 (mod 17) → k = 4
- คำตอบไม่唯一: k = 4 + 16t (เพราะ 3¹⁶ ≡ 1 mod 17, Order = 16)
ความยากของ DLP
- ไม่มีอัลกอริทึม Polynomial Time สำหรับ General Groups
- Best Classical Algorithms:
- Generic Groups: Pollard's Rho O(√n) ~ Exponential
- Zp*: Index Calculus, NFS Sub-exponential Lp[1/3]
- ECC (Elliptic Curves): Pollard's Rho O(√n) → Key Size เล็กกว่า RSA/DH
- Quantum (Shor's Algorithm): Polynomial Time → แตก DLP ทุกประเภท (FFC, ECC)
ระบบ Cryptography ที่พึ่งพา DLP
| ระบบ | Group | Key Size (Classical 128-bit Sec) | Quantum |
|---|---|---|---|
| Diffie-Hellman (FFC) | Zp* | 3072 บิต | ❌ |
| DSA | Zp* | 3072 บิต | ❌ |
| ElGamal | Zp* | 3072 บิต | ❌ |
| ECDH / ECDSA | Elliptic Curve Fp | 256 บิต | ❌ |
| EdDSA (Ed25519) | Curve25519 | 256 บิต | ❌ |
| X25519 (ECDH) | Curve25519 | 256 บิต | ❌ |
Diffie-Hellman Key Exchange (1976)
โปรโตคอลแลกกุญแจแรกที่ใช้ DLP
- Alice, Bob ตกลง p, g (Public)
- Alice เลือก a สุ่ม → ส่ง A = gᵃ mod p
- Bob เลือก b สุ่ม → ส่ง B = gᵇ mod p
- Shared Secret: Alice คำนวian Bᵃ = gᵃᵇ, Bob คำนวณ Aᵇ = gᵃᵇ
- โจมตีเห็น p, g, A, B → ต้องแก้ DLP หา a หรือ b
สถานะปัจจุบัน
- Classical: ECC (256-bit) ปลอดภัย, เร็ว, Key สั้น → มาตรฐาน TLS 1.3, SSH, Signal
- Quantum: ทั้ง FFC และ ECC แตกได้ด้วย Shor's Algorithm
- Migration: ใช้ PQC KEM (ML-KEM/Kyber) แทน DH/ECDH, PQC Signature (ML-DSA/Dilithium, SLH-DSA/SPHINCS+) แทน ECDSA/EdDSA
