home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

การใช้ทฤษฎีบทเศษเหลือจีน (Chinese Remainder Theorem) สร้างเลขสุ่มสำหรับความปลอดภัยข้อมูล

Chinese Remainder Theorem (CRT) และการสร้างเลขสุ่ม

CRT: ถ้า m₁, m₂, ..., mₖ หารร่วมได้ 1 คู่ต่อคู่ (Pairwise Coprime) แล้วระบบสมการ:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)

มีคำตอบ เดียว modulo M = m₁×m₂×...×mₖ

การประยุกต์สร้างเลขสุ่ม (Random Number Generation)

แนวคิด

  • เลือก Moduli คู่เฉพาะกัน: m₁, m₂, ..., mₖ
  • สร้าง Residues สุ่ม: aᵢ ∈ [0, mᵢ-1] จาก Entropy Source
  • ใช้ CRT รวม → ได้ x ∈ [0, M-1] ที่กระจาย Uniform
  • M = ผลคูณ mᵢ = ขนาด Range ของเลขสุ่ม

ข้อดี

  • Parallelizable: สร้าง aᵢ แยกกันได้ (Hardware RNG แต่ละตัว)
  • Fault Tolerant: หนึ่ง Moduli ล้มเหลว ยังสร้างได้ (Reduced Range)
  • Efficient Reconstruction: Garner's Algorithm หรือ Standard CRT Formula

การใช้ใน Network Security

Nonce Generation

  • Nonce = Number Used Once (IV, Counter, Challenge)
  • CRT สร้าง Nonce ที่ Unique ต่อ Session
  • Receiver ตรวจสอบ: ถ้า Nonce ซ้ำ → Replay Attack → Reject

Replay Attack Prevention

  1. Sender: สร้าง Nonce ด้วย CRT → ผูกกับ Packet
  2. Receiver: เก็บ Nonce ที่เคยเห็น (Bloom Filter / Sliding Window / Database)
  3. Packet ใหม่: ตรวจ Nonce → ถ้าใหม่ Accept, ถ้าเก่า Reject

การคำนวณ CRT (Standard Formula)

M = ∏mᵢ, Mᵢ = M/mᵢ, yᵢ = Mᵢ⁻¹ mod mᵢ

x = Σ(aᵢ × Mᵢ × yᵢ) mod M

Garner's Algorithm (Efficient, No Large Multiplication)

x = a₁
for i = 2 to k:
    t = (aᵢ - x) × (m₁×...×mᵢ₋₁)⁻¹ mod mᵢ
    x = x + t × (m₁×...×mᵢ₋₁)
return x

ข้อควรระวัง

  • Moduli ต้อง Pairwise Coprime (gcd(mᵢ,mⱼ)=1)
  • Entropy Source ต้องเป็น CSPRNG (Cryptographically Secure PRNG)
  • Nonce Storage: ต้อง Scale ได้ (Bloom Filter, Time-based Expiry)
  • CRT เองไม่สร้าง Entropy → ต้องมี Entropy Input ที่ดี

สรุป

CRT ให้วิธีสร้างจำนวนสุ่มขนาดใหญ่จากส่วนย่อยเล็กๆ ใช้ใน Nonce Generation, Replay Protection, Secret Sharing (Shamir), RSA-CRT Decryption, Parallel RNG