MD5

Trong mật mã học, MD5 (viết tắt của tiếng Anh Message-Digest algorithm 5, giải thuật Tiêu hóa tin 5) là một hàm băm mật mã học được sử dụng phổ biến với giá trị Hash dài 128-bit. Là một chuẩn Internet (RFC 1321), MD5 đã được dùng trong nhiều ứng dụng bảo mật, và cũng được dùng phổ biến để kiểm tra tính toàn vẹn của tập tin. Một bảng băm MD5 thường được diễn tả bằng một số hệ thập lục phân 32 ký tự.
MD5 được thiết kế bởi Ronald Rivest vào năm 1991 để thay thế cho hàm băm trước đó, MD4. Vào năm 1996, người ta phát hiện ra một lỗ hổng trong MD5; trong khi vẫn chưa biết nó có phải là lỗi nghiêm trọng hay không, những chuyên gia mã hóa bắt đầu đề nghị sử dụng những giải thuật khác, như SHA-1 (khi đó cũng bị xem là không an toàn). Trong năm 2004, nhiều lỗ hổng hơn bị khám phá khiến cho việc sử dụng giải thuật này cho mục đích bảo mật đang bị đặt nghi vấn.

Ứng dụng

Các đồng hóa MD5 được dùng rộng rãi trong các phần mềm trên toàn thế giới để đảm bảo việc truyền tập tin được nguyên vẹn. Ví dụ, máy chủ tập tin thường cung cấp một checksum MD5 được tính toán trước cho tập tin, để người dùng có thể so sánh với checksum của tập tin đã tải về. Những hệ điều hành dựa trên nền tảng Unix luôn kèm theo tính năng MD5 sum trong các gói phân phối của họ, trong khi người dùng Windows sử dụng ứng dụng của hãng thứ ba.
Tuy nhiên, hiện nay dễ dàng tạo ra xung đột MD5, một người có thể tạo ra một tập tin để tạo ra tập tin thứ hai với cùng một checksum, do đó kỹ thuật này không thể chống lại một vài dạng giả mạo nguy hiểm. Ngoài ra, trong một số trường hợp checksum không thể tin tưởng được (ví dụ, nếu nó được lấy từ một lệnh như tập tin đã tải về), trong trường hợp đó MD5 chỉ có thể có chức năng kiểm tra lỗi: nó sẽ nhận ra một lỗi hoặc tải về chưa xong, rất dễ xảy ra khi tải tập tin lớn.
MD5 được dùng rộng rãi để lưu trữ mật khẩu. Để giảm bớt sự dễ thương tổn đề cập ở trên, ta có thể thêm salt vào mật khẩu trước khi băm chúng. Một vài hiện thực có thể áp dụng vào hàm băm hơn một lần-xem làm mạnh thêm khóa.

Mã giả Hồng Đơ

Mã giả cho giải thuật MD5 như sau.
//Chú ý: Tất cả các biến đều là biến không dấu 32 bit và bao phủ mô đun 2^32 khi tính toánvar int[64] r, k

//r xác định số dịch chuyển mỗi vòng
r[ 0..15]:= {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22} 
r[16..31]:= {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47]:= {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63]:= {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}

//Sử dụng phần nguyên nhị phân của sin của số nguyên làm hằng số:for i from 0 to 63
    k[i]:= floor(abs(sin(i + 1)) × (2 pow 32))

//Khởi tạo biến:var int h0:= 0x67452301
var int h1:= 0xEFCDAB89
var int h2:= 0x98BADCFE
var int h3:= 0x10325476

//Tiền xử lý:append "1" bit to message
append "0" bits until message length in bits ≡ 448 (mod 512)
append bit (bit, not byte) length of unpadded message as 64-bit little-endian integer to message

//Xử lý mẩu tin trong đoạn 512-bit tiếp theo:for each 512-bit chunk of message
    break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15

    //Khởi tạo giá trị băm cho đoạn này:
    var int a:= h0
    var int b:= h1
    var int c:= h2
    var int d:= h3

    //Vòng lặp chính:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            f:= (b and c) or ((not b) and d)
            g:= i
        else if 16 ≤ i ≤ 31
            f:= (d and b) or ((not d) and c)
            g:= (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            f:= b xor c xor d
            g:= (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            f:= c xor (b or (not d))
            g:= (7×i) mod 16
 
        temp:= d
        d:= c
        c:= b
        b:= b + leftrotate((a + f + k[i] + w[g]), r[i])
        a:= temp

    //Thêm bảng băm của đoạn vào kết quả:
    h0:= h0 + a
    h1:= h1 + b 
    h2:= h2 + c
    h3:= h3 + d

var int digest:= h0 append h1 append h2 append h3 //(expressed as little-endian)  //định nghĩa hàm dịch trái
  leftrotate (x, c) 
      return (x << c) or (x >> (32-c));
Ghi chú: Thay vì hàm hóa RFC 1321 gốc như trên, phần sau có thể được dùng để tăng độ hiệu quả (hữu ích nếu ngôn ngữ assembly được dùng - còn không, chương trình dịch sẽ tự động tối ưu hóa đoạn mã ở trên):
(0  ≤ i ≤ 15): f:= d xor (b and (c xor d))
(16 ≤ i ≤ 31): f:= c xor (d and (b xor c))

Các bảng băm MD5

Bảng băm MD5 128 bit (16 byte) (còn được gọi là message digests) được biểu diễn bằng chuỗi 32 số thập lục phân. Sau đây cho thấy đầu vào ASCII 43 byte và bảng băm MD5 tương ứng:
 MD5("The quick brown fox jumps over the lazy dog") 
  = 9e107d9d372bb6826bd81d3542a419d6
Thậm chí một sự thay đổi nhỏ trong mẩu tin cũng dẫn đến thay đổi hoàn toàn bảng băm, do hiệu ứng thác. Ví dụ, thay d thành e:
 MD5("The quick brown fox jumps over the lazy eog") 
  = ffd93f16876049265fbaef4da268dd0e
Bảng băm của một chuỗi rỗng là:
 MD5("") 
  = d41d8cd98f00b204e9800998ecf8427e