|
|
Thời gian gởi : 30-04-2004
Bài viết này cung cấp thông tin cho cộng đồng Internet. Nó không xác định một chuẩn Internet. Sự phát hành của bài viết này là không giới hạn...
Vị trí của bài viết này
Bài viết này cung cấp thông tin cho cộng đồng Internet. Nó không xác định một chuẩn Internet. Sự phát hành của bài viết này là không giới hạn
Lời cảm ơn
Chúng tôi muốn cám ơn Don Coppersmith, Burt Kaliski, Ralph Merkle, David Chaum, và Noam Nisan vì rất nhiều đề xuất và góp ý có ích
Nội dung
1. Mục đích
2. Thuật ngữ và ký hiệu
3. Mô tả thuật toán MD5
4. Tổng kết
5. Sự khác nhau giữa MD4 và MD5
Tài liệu tham khảo
Phụ lục A - Mã nguồn tham khảo
Xem xét về tính bảo mật
Liên hệ với tác giả
1. Mục đích
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
3.4 - Bước 4 : Xử lý thông điệp theo từng khối 16 word
Trước hết ta định nghĩa các hàm phụ, các hàm này nhận đầu vào là 3 word 32 bit và tạo ra một word 32 bit.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z)= XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
Với mỗi bit, F hoạt động như một điều kiện : nếu X thì Y nếu không thì Z. Hàm F có thể định nghĩa bằng phép + thay vì v bởi vì XY và not(X)Z không bao giờ có ``1`` ở cùng 1 vị trí bit.Các hàm G,H và I tương tự như F, ở chỗ chúng tác động theo từng bit tương ứng để tạo ra kết quả từ các bit của X,Y và Z
Bước này sử dụng một bảng 64 giá trị T[1 .. 64] được tạo ra từ hàm sin. Gọi T[i] là phần tử thứ i của bảng, thì T[i]là phần nguyên của 4294967296*|sin(i)| , i được tính theo radian.
Làm như sau :
/* Xử lý mỗi khối 16 word */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */
/* Lưu A vào AA, B vào BB, C vào CC, D và DD . */
AA = A
BB = B
CC = C
DD = D
/* Vòng 1. */
/* Ký hiệu [abcd k s i] nghĩa là thực hiện như sau :
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Thực hiện : */
[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]
/* Vòng 2. */
/*Ký hiệu [abcd k s i] nghĩa là thực hiện như sau
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Thực hiện : */
[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]
/* Vòng 3. */
/* Ký hiệu [abcd k s t] nghĩ là làm như sau
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Thực hiện :*/
[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]
/* Vòng 4. */
/* Ký hiệu [abcd k s t] nghĩa là làm như sau
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Thực hiên: */
[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]
/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block was started.) */
/* Sau đó làm các phép cộng sau. ( Nghĩa là cộng vào mỗi thanh ghi giá trị của nó trước khi vào vòng lặp ) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end /* of loop on i */
3.5 - Bước 5 : In ra
Mã số thông điệp được tạo ra là A,B,C,D. Nghĩa là chúng ta bắt đầu từ byte thấp của A, kết thúc với byte cao của D.
Đến đây đã mô tả xong thuật toán MD5. Mã nguồn tham khảo viết bằng C có thể tìm thấy ở phụ lục.
4. Tổng kết
Thuật toán số hóa thông điệp MD5 khá đơn giản để thực hiện, cung cấp một dạng ``vân tay`` hay mã số của thông điệp với độ dài tùy ý. Người ta cho rằng độ khó để tìm được 2 thông điệp có cùng mã số là khoảng 2^64 bước tính, và độ khó để tim được một thông điệp với mã số cho trước là 2^128 bước tính. Thuật toán MD5 đã được dò tìm điểm yếu một cách cẩn thận. Tuy nhiên đây là một thuật toán tương đối mới ( ! ) và việc phân tích cẩn thận về sự an toàn là cần thiết.
5. Sự khác nhau giữa MD4 và MD5
Sau đây là sự khác nhau giữa MD4 và MD5 :
1. Vòng 4 đã được thêm vào
2. Mỗi bước đều được thêm vào một hằng số duy nhất
3. Hàm G ở vòng 2 được đổi từ (XY v XZ v YZ) thành (XZ v Y not(Z)) để làm giảm sự đối xứng trong G.
4. Mỗi bước đều sử dụng kết quả từ bước trước . Điều này nhằm tạo ra ``hiệu ứng dây chuyền`` nhanh hơn
5. Thứ tự các word đầu vào ở vòng 2 và vòng 3 được thay đổi, để làm cho hai mẫu này ít giống nhau hơn
6. Số bit dịch chuyển ở mỗi vòng được tối ưu hóa, để tạo ra ``hiệu ứng dây chuyền`` nhanh hơn. Lượng dịch chuyển ở mỗi vòng là khác nhau.
Tài liệu tham khảo
[1] Rivest, R., ``The MD4 Message Digest Algorithm``, RFC 1320, MIT and
RSA Data Security, Inc., April 1992.
[2] Rivest, R., ``The MD4 message digest algorithm``, in A.J. Menezes
and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO `90
Proceedings, pages 303-311, Springer-Verlag, 1991.
[3] CCITT Recommendation X.509 (1988), ``The Directory -
Authentication Framework.``
Xem xét về tính bảo mật
Độ bảo mật bàn đến trong bài viết này được coi là đủ để tạo ra những mô hình chữ ký điện tử kết hợp giữa MD5 và một hệ mã hóa công khai
Liên hệ với tác giả
Ronald L. Rivest
Massachusetts Institute of Technology
Laboratory for Computer Science
NE43-324
545 Technology Square
Cambridge, MA 02139-1986
Phone: (617) 253-5880
EMail: rivest@theory.lcs.mit.edu
(Biên dịch: Popeye - HVA Translator)