เอ็มดี5

เอ็มดี5 (อังกฤษ: Message-Digest algorithm 5: MD5) เป็นฟังก์ชันแฮชในวิทยาการเข้ารหัสลับ เช่นการเก็บรหัสผ่าน และนอกจากนี้ยังมีการนำมาใช้ในการตรวจสอบความสมบูรณ์ของไฟล์ (Md5sum) แต่ถึงกระนั้นก็มีการพบว่า MD5 นั้นไม่เป็นแฮชฟังก์ชันที่ป้องกันการทับซ้อน (collision resistant) จึงไม่เหมาะสมที่จะนำมาใช้ในแอปพลิเคชันบางอย่างเช่น SSL หรือ Digital Signature

ขั้นตอนวิธี

เราจะเริ่มจากการสมมติให้มีอินพุทเป็นข้อความ M ขนาด b-bit ซึ่ง b เป็นจำนวนเต็มที่ไม่ติดลบ ไม่จำเป็นต้องหาร 8 ลงตัว และมีความยาวได้ไม่จำกัด ซึ่งจะเขียนใหม่ได้เป็น m_0 m_1 m_2 … m_b-1 จากนั้นจะทำการหา MD5 โดยการผ่านขั้นตอนต่อไปนี้

เติมบิตท้าย

เติม “ 10 ” ท้ายข้อความแล้ว เติม “ 0 ” ไปเรื่อยๆ จนกว่าข้อความจะมีขนาดที่คอนกลูเอนกับ 448 (mod 512)

เติมขนาดข้อความ

เติมขนาดของข้อความความยาว 64 บิต ท้ายข้อความ หากขนาดของข้อความใหญ่เกินที่ 64 บิตจะเก็บได้ก็ให้ใช้ 64 บิตหลังของขนาดเท่านั้น สุดท้ายจะได้ข้อความที่แต่งเติมแล้วมีขนาดที่สามารถหาร 512 ลงตัวพอดี นั่นคือจะสามารถแบ่งข้อความได้เป็นชุด ชุดละ 512 บิต หรือ 32 ไบต์ หรือ 16-word block

กำหนดค่าเริ่มต้นของ MD Buffer

ตั้งค่าเริ่มต้นของ buffer ขนาด 32 บิต 4 ตัวดังนี้

A = 0x67452301 , B = 0xEFCDAB89 , C =0x98BADCFE , D = 0x76543210

คำนวณข้อความใน 16-word block

ลำดับแรกเราจะกำหนดฟังก์ชันรับอินพุท 32 บิต และเอาต์พุต 32 บิต ดังนี้

${\displaystyle F(X,Y,Z)=(X\wedge {Y})\vee (\neg {X}\wedge {Z})}$ 

${\displaystyle G(X,Y,Z)=(X\wedge {Z})\vee (Y\wedge \neg {Z})}$ 

${\displaystyle H(X,Y,Z)=X\oplus Y\oplus Z}$ 

${\displaystyle I(X,Y,Z)=Y\oplus (X\vee \neg {Z})}$ 

${\displaystyle \oplus ,\wedge ,\vee ,\neg }$  แทนการดำเนินการ XOR, AND, OR และ NOT ในขั้นตอนนี้ยังต้องใช้ ตารางขนาด 64 ช่อง T[1…64] ซึ่ง T[i] สามารถหาค่าได้จาก ⌊ 2^32 x |sin ⁡i | ⌋ โดย i มีค่าเป็นเรเดียน จากนั้นทำตามขั้นตอนวิธีดังนี้

 //ดำเนินการทุก 16-word block  For i = 0 to N/16-1 do //คัดลอก block ที่ i เก็บไว้ที่ X For j = 0 to 15 do Set X[j] to M[i*16+j]. end /* of loop on j */ 

 // เก็บ A ใน AA, B ใน BB, C ใน CC, และ D ใน DD AA = A BB = B CC = C DD = D 

  // รอบที่ 1 /* ให้ [abcd k s i] แทน a = b + ((a + F (b,c,d) + X[k] + T[i]) <<< s) สัญลักษณ์ <<< แทน left rotate */ // ดำเนินการ 16 ครั้งดังนี้  [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] 

  // รอบที่ 2 /* ให้ [abcd k s i] แทน a = b + ((a + G (b,c,d) + X[k] + T[i]) <<< s) */ // ดำเนินการ 16 ครั้งดังนี้  [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] 

  // รอบที่ 3 /* ให้ [abcd k s i] แทน a = b + ((a + H (b,c,d) + X[k] + T[i]) <<< s) */ // ดำเนินการ 16 ครั้งดังนี้  [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48] 

  // รอบที่ 4 /* ให้ [abcd k s i] แทน a = b + ((a + I (b,c,d) + X[k] + T[i]) <<< s) */ // ดำเนินการ 16 ครั้งดังนี้. [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52] [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56] [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64] 

  //นำค่าที่ได้กลับไปบวกกับค่าเดิม  A = A + AA B = B + BB C = C + CC D = D + DD end // ของวงวน i  

แสดงเอาต์พุต

ค่ารหัสที่ได้จะเก็บอยู่ในสมารถแสดงได้โดยนำเลขฐาน 16 ของ A, B, C, D มาต่อกัน

อ้างอิง

• วรเศรษฐ์ สุวรรณิก (2553). วิทยาการรหัสลับ Cryptography. กรุงเทพฯ: วรรณิก. pp. 123–139. ISBN 978-616-90224-2-8. Check date values in: |year= (help)

แหล่งข้อมูลอื่น

• RFC 1321 The MD5 Message-Digest Algorithm
• W3C recommendation on MD5

• REXX MD5 test suite covers MD5 examples in various RFCs (incl. errata)
• Source Code for Cryptography (Just a touch)