Nov 16, 2010

Cryptography ตอนที่ 1 ธรรมชาติของการเข้ารหัส (อย่างง่าย)

เมื่อเราลองวิเคราะห์ระบบรหัสลับนั้น เราจะกล่าวได้ว่ามันเป็น (P, C, K, E, D) 5-tuple
เริ่มมาก็งงเลยใช่ปะละ (คนแปลก็งงเหมือนกัน) งั้นเราค่อยๆ ดูกันไปทีละส่วนละกันครับ

tuple คำนี้อาจไม่คุ้นเคยและดูยุ่งยาก แต่ที่จริงแล้วมันเป็นเพียงวิธีการเขียนเรียงลำดับสมาชิกเท่านั้นเอง (ต่างจากเซตที่สมาชิกแต่ละตัวไม่มีความสำคัญในเรื่องลำดับ)
โดยสมาชิกของ tuple นั้นจะต้องมีจำนวนจำกัด n ตัวเสมอ n-tuple ที่เราคุ้นเคยกันดีก็คือ 2-tuple ที่อยู่ในรูป (x, y) หรือเรียกติดปากกันว่าคู่อันดับนั่นเอง
ดังนั้นการที่กล่าวได้ว่าระบบรหัสลับเป็น 5-tuple ก็หมายความว่าระบบนี้มีสิ่งที่สำคัญประกอบอยู่ 5 อย่างนั่นเอง ซึ่งมีความสัมพันธ์กันดังนี้

1. P (Plaintext) คือเซตจำกัดของข้อความอ่านออกที่เป็นไปได้
2. C (Ciphertext) คือเซตจำกัดของข้อความเข้ารหัสที่เป็นไปได้
3. K (Key) คือเซตจำกัดของกุญแจการเข้ารหัสที่เป็นไปได้
4. สำหรับแต่ละ k ที่เป็นสมาชิกของ K (ในทางคณิตศาสตร์ ตัวพิมพ์ใหญ่คือเซต ตัวพิมพ์เล็กคือสมาชิกของเซตนั้นๆ) จะมีวิธีการใช้กุญแจเข้ารหัส (Encryption) eK ที่เป็นสมาชิกของ E และมีวิธีใช้กุญแจถอดรหัส (Decryption) dK ที่เป็นสมาชิกของ D โดยที่ eK : P -> C (eK เป็นฟังก์ชันจาก P ไปยัง C หรือกล่าวง่ายๆ ว่าฟังก์ชัน eK นี้มี P เป็น input ส่วน C เป็น output นั่นเอง) และ dK : C -> P โดยที่ p = dK(eK(p))

จากข้อ 4 นี้ จะหมายความว่า dK เป็นอินเวอร์สของ eK เสมอ และเขียนได้ว่า dK = eK-1
นอกจากนี้ eK และ dK ยังต้องเป็นฟังก์ชันแบบ 1-1 อีกด้วย (จับคู่กันและกันแค่คู่ต่อคู่เท่านั้น) เพราะถ้าไม่เป็นฟังก์ชัน 1-1 แล้ว เมื่อเราต้องการถอดรหัสกลับเป็นข้อความธรรมดา เราอาจไม่รู้เลยว่าคำที่ถูกต้องคืออะไรกันแน่ เพราะ 1 คำอาจถอดรหัสกลับได้หลายแบบนั่นเอง

จากที่เกริ่นมานี้หมายความว่า ถ้าเราสามารถล่วงรู้ eK ได้ เราก็จะหา dK เพื่อถอดรหัสลับได้เช่นกัน
หรือว่าถ้าเราสามารถดักจับข้อความลับ c ได้ และล่วงรู้ข้อความถูกต้อง p บางส่วน เราอาจทดลองหา k ที่ทำให้ c = ek(p) จนสำเร็จ และหา dk ได้ด้วย