thuật toán số hóa thông điệp MD5.docx

Tài liệu này mô tả thuật toán số hóa thông điệp MD5. Thuật toán nhận vào 1 thông điệp độ dài tùy ý và

tạo ra một số 128 bit, là một dạng “vân tay“ hay “mã số thông điệp“ ( message digest ) của đầu vào.

Người ta cho rằng sẽ không khả thi về mặt tính toán để tạo ra 2 thông điệp có cùng mã số thông điệp,

hoặc tạo ra một thông điệp với mã số cho trước.Thuật toán MD5 được dự tính áp dụng cho những ứng

dụng chữ ký điện tử, ở đó một file lớn phải được “nén“ một cách an toàn trước khi mã hóa với một khóa

cá nhân ( private key ) dưới một hệ mã hóa công khai như RSA

Thuật toán MD5 được thiết kế để chạy tương đối nhanh trên các máy 32 bit, có thể được thực hiện một

cách khá gọn.

Thuật toán MD5 là sự mở rộng của thuật toán MD4. MD5 chậm hơn một chút so với MD4 nhưng an toàn

hơn. MD5 được thiết kế vì người ta cảm thấy có thể MD4 đã được chấp nhận trong sử dụng quá nhanh

so với sự đánh giá nó. MD4 được thiết kế để chạy rất nhanh, nó đã “nằm trên ranh giới“ theo cách nói về

nguy cơ của sự thành công trong việc phá mã. MD5 đã lùi lại một chút, từ bỏ một chút tốc độ cho sự bảo

mật. Nó kết hợp một số ý kiến góp ý của các chuyên gia, thuật toán MD5 hiện đang được đánh giá và có

thể được chấp nhận như một chuẩn.

2. Thuật ngữ và ký hiệu

Trong tài liệu này một “word“ là một lượng 32 bit và một “byte“ là một lượng 8 bit. Một dãy các bit có thể

được xem như một dãy các byte, trong đó mỗi nhóm 8 bit liên tiếp được xem như một byte với bit cao

của mỗi byte đặt trước. Tương tự, mỗi dãy các byte có thể xem như một dãy các word 32 bit, trong đõ

mỗi nhóm 4 byte liên tiếp được xem như một word với byte thấp đặt trước.

Ký hiệu x_i nghĩa là phần tử x thứ i (“x sub i“). Nếu số thứ tự đó là một biểu thức ta viết nó trong ngoặc

nhọn, ví dụ như x_{i+1} ; ^ ký hiệu cho số mũ.

Ký hiệu “+“ cho phép cộng các word, nghĩa là cộng theo môđun 2^32.

X <<< s ký hiệu giá trị 32 bit nhận được bằng cách dịch chuyển các bit của X (theo kiểu quay vòng )

sang trái s vị trí.

not(X) ký hiệu phép đối lập (NOT) các bit

X v Y ký hiệu phép OR các bit

X xor Y ký hiệu phép XOR các bit

XY ký hiệu phép AND các bit

3. Mô tả thuật toán MD5

Giả sử chúng ta có thông điệp b bit ở đầu vào, và ta muốn tìm mã số của thông điệp. Ở đây b là số

không âm bất kỳ; b có thể bằng 0 và không cần chia hết cho 8, độ lớn có thể bất kỳ. Tưởng tượng rằng

các bit của thông điệp được viết như sau :

m_0 m_1 m_2 … m_{b-1}

Mã số thông điệp được tính qua 5 bước sau

3.1 – Bước 1 : Các bit gắn thêm

Thông điệp được mở rộng, thêm bit vào phía sau sao cho độ dài của nó ( tính theo bit ) đồng dư với 448

theo môđun 512. Nghĩa là thông điệp được mở rộng sao cho nó còn thiếu 64 bit nữa thì sẽ có một độ dài

chia hết cho 512. Việc này luông được thực hiện ngay cả khi bản thân độ dài thông điệp đã đồng dư với

448 theo môđun 512.

Việc thêm bit này thực hiện như sau : một bit “1“ được thêm vào sau thông điệp, sau đó các bit “0“ được

thêm vào để có một độ dài đồng dư với 448 môđun 512. Trong tất cả các trường hợp, có ít nhất 1 và

nhiều nhất 512 bit được thêm vào.

3.2 – Bước 2 : Gắn thêm độ dài

Dạng biểu diễn 64 bit độ dài b của chuỗi ban đầu được thêm vào phía sau kết quả của bước 1. Trong

trường hợp b lớn hơn 2^64 thì chỉ có 64 bit thấp của b được sử dụng. ( Các bit này được thêm vào phía

sau dưới dạng 2 word 32 bit, gắn word thấp trước theo quy ước ở trên )

3.3 – Bước 3 : Khởi tạo bộ đệm MD

Một bộ đệm 4 word (A,B,C,D) được dùng để tính mã số thông điệp. Ở đây mỗi A,B,C,D là một thanh ghi

32 bit. Những thanh ghi này được khởi tạo theo những giá trị hex sau ( các byte thấp trước ) :

word A : 01 23 45 67

word B : 89 ab cd ef

word C : fe dc ba 98

word D : 76 54 32 10