home

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

Hill Cipher โดนโจมตี Chosen Plaintext ได้อย่างไร? หลักการและการวิเคราะห์

Hill Cipher เป็นรหัสพหุตัวอักษร (polyalphabetic cipher) ที่เลสเตอร์ เอส. ฮิลล์ (Lester S. Hill) สร้างขึ้น ใช้แนวคิดเมทริกซ์ร่วมกับสมการคงเหลือเชิงเส้น (linear congruence) ในการเข้ารหัสและถอดรหัส

ลักษณะสำคัญ

  • ไม่แทนที่ตัวอักษรเดิมด้วยตัวอักษรเดียวกันเสมอ (ไม่ใช่ monoalphabetic)
  • ใช้การคูณเมทริกซ์ จึงจัดเป็น Block Cipher — ข้อความถูกแบ่งเป็นบล็อกขนาดคงที่
  • ตัวอักษรในบล็อกเดียวกันจะมีผลต่อกันระหว่างเข้ารหัส/ถอดรหัส ทำให้ตัวอักษรเดียวกันไม่ถูกแมปไปตัวอักษรเดียวกันซ้ำ

โครงสร้างคีย์

คีย์คือเมทริกซ์สี่เหลี่ยมจัตุรัส K ขนาด m × m (m = ขนาดบล็อก) ต้องเป็น เมทริกซ์ผกผันได้ (invertible matrix) เพราะต้องใช้ K-1 ในการถอดรหัส

$$K = \begin{bmatrix} K_{11} & K_{12} & \cdots & K_{1m} \\ K_{21} & K_{22} & \cdots & K_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ K_{m1} & K_{m2} & \cdots & K_{mm} \end{bmatrix}$$

สมการเข้ารหัส/ถอดรหัส

สำหรับบล็อกขนาด m ตัวอักษร ให้ P = คอลัมน์เวกเตอร์ข้อความต้นฉบับ C = คอลัมน์เวกเตอร์ข้อความเข้ารหัส:

$$C = K \cdot P \pmod{26}$$

$$P = K^{-1} \cdot C \pmod{26}$$

ช่องโหว่: Known-Plaintext Attack (KPA)

Hill Cipher แข็งแกร่งต่อ Ciphertext-Only Attack แต่ เปราะบางมากต่อ Known-Plaintext Attack หากโจมตีมีคู่ plaintext-ciphertext เพียงพอ:

  1. สมมติมีคู่ (Pi, Ci) จำนวน m คู่ โดยแต่ละคู่ยาว m ตัวอักษร
  2. จัด Pi และ Ci ให้เป็นเมทริกซ์ m × m คือ P และ C
  3. จากสมการ C = K · P (mod 26) สามารถหาคีย์ K ได้โดย:

$$K = C \cdot P^{-1} \pmod{26}$$

เมื่อได้ K แล้ว สามารถถอดรหัสข้อความอื่นๆ ที่เข้ารหัสด้วยคีย์เดียวกันได้ทันที

Chosen-Plaintext Attack (CPA)

ในโจมตีแบบ Chosen-Plaintext โจมตีสามารถ เลือก plaintext เองได้ ทำให้การสร้างเมทริกซ์ P ที่ invertible ได้ง่ายขึ้น (เช่นเลือก plaintext ที่ทำให้ P เป็นเมทริกซ์เอกลักษณ์หรือเมทริกซ์ที่คำนวณผกผันง่าย) จึงทำให้การคำนวณ K = C · P-1 ง่ายและรวดเร็วกว่า KPA มาก

สรุป

Hill Cipher เป็นรหัสคลาสสิกที่น่าสนใจทางคณิตศาสตร์ แต่ ไม่ปลอดภัยสำหรับการใช้งานจริง เนื่องจากโจมตี Known-Plaintext และ Chosen-Plaintext สามารถค้นหาคีย์ได้ในเวลา polynomial (แก้ระบบสมการเชิงเส้น) รหัสสมัยใหม่ใช้การผสมผสานระหว่าง substitution และ permutation (SP-network) พร้อมกับ S-boxes ที่ไม่เชิงเส้น เพื่อป้องกันการโจมตีแบบนี้