�ݺ�ߣ

Hàm Băm MD5 và Ứng Dụng
Giáo viên:

Hoàng Thu Phương

Sinh viên:

Lê Minh Tân

Phạm Văn Thanh
Trương Hồng Thanh
Đặng Tiến Thành
Tạ Việt Thảo

i 17/10/2013

Cơ sở lý thuyết Mật Mã

Nội dung

I.Hàm băm và chữ kí số.

II.Hàm băm MD5 và Ứng dụng.

III.Thuật toán MD5.

.

I.Hàm băm và chữ kí số.
1. Giới thiệu hàm băm.
Hàm băm là các thuật toán không sử dụng khóa để mã hóa,nó có nhiệm vụ “lọc”
(băm) thông điệp được đưa vào theo một thuật toán h một chiều nào đó, rồi đưa ra
một bản băm – văn bản đại diện – có kích thước cố định. Do đó người nhận không
biết được nội dung hay độ dài ban đầu của thông điệp đã được băm bằng hàm băm.

- Giá trị của hàm băm là duy nhất, và không thể suy ngược lại được nội dung
thông điệp từ giá trị băm này.
- Việc sử dụng các hệ mật mã và các sơ đồ chữ ký số, thường là mã hóa và ký
số trên từng bit của thông tin, sẽ tỷ lệ với thời gian để mã hóa và dung lượng
của thông tin.
- Thêm vào đó có thể xảy ra trường hợp: Với nhiều bức thông điệp đầu vào
khác nhau, sử dụng hệ mật mã, sơ đồ ký số giống nhau (có thể khác nhau)
thì cho ra kết quả bản mã, bản ký số giống nhau (ánh xạ N-1: nhiều – một).
Điều này sẽ dẫn đến một số rắc rối về sau cho việc xác thực thông tin.

X

hay

hay

Y

Hình 1: Nhiều thông điệp nguồn cho cùng một kết quả sau mã hóa/ ký số
vậy,giải pháp cho các vấn đề vướng mắc đến chữ ký số là dùng hàm băm để
trợ giúp cho việc ký số.
Vì

Các thuật toán băm với đầu vào là các bức thông điệp có dung lượng, kích thước
tùy ý (vài KB đến vài chục MB thậm chí hơn nữa) – các bức thông điệp có thể là
dạng văn bản, hình ảnh, âm thanh, file ứng dụng v.v… - và với các thuật toán băm:
MD2, MD4, MD5, SHA cho các bản băm đầu ra có kích thước cố định: 128 bit với
dòng MD, 160 bit với SHA.Như vậy, bức thông điệp kích thước tùy ý sau khi băm
sẽ được thu gọn thành những bản băm – được gọi là các “văn bản đại diện” – có
kích thước cố định (128 bit hoặc 160 bit).
Đ

:

- Với mỗi thông điệp đầu vào chỉ có thể tính ra được một văn bản đại diện –
giá trị băm tương ứng – duy nhất.
- Hai thông điệp khác nhau chắc chắn có hai văn bản đại diện khác nhau. Khi
đã có văn bản đại diện duy nhất cho bức thông điệp, áp dụng các sơ đồ chữ
ký số ký trên văn bản đại diện đó.
:
Tính chất 1: Hàm hash h là hàm không va chạm yếu nếu khi cho trước

một bức điện x, không thể tiến hành về mặt tính toán để tìm một bức
điện x

x’ sao cho h (x’) = h(x).

Tính chất 2: Hàm Hash h là không va chạm mạnh nếu không có khả
năng tính toán để tìm ra bức điênk x và x’ sao cho x

x’ và h(x) =

h(x’).
Tính chất 3: Hàm Hash h là một chiều nếu khi cho trước một bản tóm
lược thông báo z, không thể thực hiện về mặt tính toán để tìm bức điện
x sao cho h(x) = z.
2. Chữ kí số.
Chữ kí số là một giao thức tạo ra một hiệu quả tương tự như chữ kí thực:
- Nó là một dấu hiệu mà chỉ có người gửi mới có thể tạo ra nhưng những
người khác có thể nhận thấy được rằng nó là của người gửi.
- Giống như chữ kí thực, chữ kí số dùng để xác nhận nội dung thông bá
Chữ kí số phải thỏa mãn điều kiện sau đây:
- Không thể giả mạo: Nếu P kí thông báo M bằng chữ kí S(P, M) thì không
một ai có thể tạo được cặp [M, S(M,P)]
- Xác thực: Nếu R nhận được cặp [M, S(M,P)] được coi là của P thì R có thể
kiểm tra được rằng chữ kí có thực sự là của P hay không. Chỉ P mới có thể
tạo được chữ kí này và chữ kí được “gắn chặt” với M.
- Không thể thay đổi: sau khi được phát M không thể bị thay đổi bởi S, R
hoặc bởi một kẻ thu trộm nào
- Không thể sử dụng lại: Một thông báo trước đó đã được đưa ra sẽ ngay lập
tức bị R phát hiện
Cách tạo một chữ kí số:

- Cách thẩm định một chữ kí số:

II.Hàm băm MD5 và Ứng dụng
MD5 (Message-Digest algorithm 5) là một hàm băm để mã hóa với giá trị
băm là 128bit. Từng được xem là một chuẩn trên Internet, MD5 đã được s
dụng r ng r i trong các chương trình an ninh mạng, và cũng thường được
dùng để kiểm tra tính nguyên vẹn của tập tin.
đã được sử dụng rộng r i
trong các chương trình an ninh mạng, và cũng thường được dùng để kiểm tra
tính nguyên vẹn của tập tin.MD5 được thiết kế bởi Ronald Rivest vào
năm 1991 để thay thế cho hàm băm trước đó MD4.
Có 2 ứng dụng quan trọng :
-MD5 được sử dụng rộng r i trong thế giới phần mềm để đảm bảo
rằng tập tin tải về không bị hỏng. Người sử dụng có thể so sánh giữa
thông số kiểm tra phần mềm bằng MD5 được công bố với thông số
kiểm tra phần mềm tải về bằng MD5.Hệ điều hành Unix sử dụng
MD5 để kiểm tra các gói mà nó phân phối, trong khi hệ điều hành
Windows sử dụng phần mềm của hãng thứ ba.
- MD5 được dùng để mã hóa mật khẩu. Mục đích của việc mã hóa này
là biến đổi một chu i mật khẩu thành một đoạn mã khác, sao cho từ
đoạn mã đó không thể nào lần trở lại mật khẩu. Có nghĩa là việc giải
mã là không thể hoặc phải mất một khoảng thời gian vô tận (đủ để
làmnản lòng các hacker).
5
MD5 biến đổi một thông điệp có chiều dài bất kì thành một khối có kích
thước cố định 128 bits. Thông điệp đưa vào sẻ được cắt thành các khối 512
bits. Thông điệp được đưa vào bộ đệm để chiều dài của nó sẻ chia hết cho
512.

Bộ đệm hoạt động như sau:
- Trước tiên nó sẽ chèn bit 1 vào cuối thông điệp.
- Tiếp đó là hàng loạt bit Zero cho tới khi chiều dài của nó nhỏ hơn
bộisố của 512một khoảng 64 bit .
- Phần còn lại sẻ được lấp đầy bởi một số nguyên 64 bit biểu diển
chiềudài ban đầu của thông điệp.
Thuật toán chính của MD5 hoạt động trên một bộ 128 bit. Chia nhỏ nó
ra thành 4 từ 32 bit, kí hiệu là A,B,C và D. Các giá trị này là các hằng
số cố định.Sau đó thuật toán chính sẻ luân phiên hoạt động trên các
khối 512 bit. Mỗi khối sẽ phối hợp với một bộ. Quá trình xữ lý một
khối thông điệp bao gồm 4 bước tương tự nhau, gọi là vòng (“round”).
Mỗi vòng lại gồm 16 quá trình tương tự nhau dựa trên hàm một chiều
F, phép cộng module và phép xoay trái…
mô tả một quá trình trong một vòng. Có 4 hàm một chiều F
có thể sử dụng. Mỗi vòng sử dụng một hàm khác nhau.

.

Mặc dù MD4 vẫn chưa bị phá, song các phiên bản yếu cho phép bỏ qua hoặc vòng
thứ nhất hay thứ ba đều có thể bị phá không khó khăn gì. Nghĩa là dễ dàng tìm thấy
các va chạm đối với các phiên bản chỉ có hai vòng. Phiên bản mạnh của dòng MD
là MD5 được công bố năm 1991. MD5 dùng bốn vòng thay cho ba và chậm hơn
30% so với MD4 (khoảng 0,9 MB/giây trên cùng một máy).
Mô tả thuật toán
Input

: Thông điệp (văn bản) có độ dài tùy ý.

Output : Bản băm, đại diện cho thông điệp gốc, đồ dài cố định 128 bit.
Giả sử đầu vào là một xâu a có độ dài b bit (b có thể bằng 0)
Bước 1: Khởi tạo các thanh ghi

Có 4 thanh ghi được sử dụng để tính toán nhằm đưa ra các đoạn mã: A, B, C, D.
Bản tóm lược của thông điệp được xây dựng như sự kết nối của các thanh ghi. Mỗi
thanh ghi có độ dài 32 bit. Các thanh ghi này được khởi tạo giá trị hecxa.
wordA := 67 45 23 01
word B := EF CD AB 89
word C := 98 BA DC FE
word D := 10 32 54 76
Bước 2+3:
Xử lý thông điệp a trong 16 khối word, có nghĩa là xử lý cùng một lúc 16 word =
512 bit (chia mảng M thành các khối 512 bit, đưa từng khối 512 bit đó vào mảng
T[j]). Mỗi lần xử lý một khối 512 bit. Lặp lại N/16 lần.

Bước 4: Thực hiện bốn vòng băm
Các vòng 1, 2, 3 và 4 dùng tương ứng ba hàm F, G, H và I. Mỗi hàm này là một
hàm boolean tính theo bit. Chúng được xác định như sau:
F(X, Y, Z) = (X Y) (( X)
G(X, Y, Z) = (X Z)

Z)

(Y ( Z))

H(X, Y, Z) = X Y Z
I(X, Y, Z) = Y (X ( Z))

Hình 5: Quá trình tạo bản băm của MD5.
ng 1

MD5
1.

2.

A := 67 45 23 01
B := ef cd ab 89
C := 98 ba dc fe
D := 10 32 54 76
for i := 0 to n/16 - 1 do {

3.

for j := 0 to 15 do T[j] = M[16i + j];

4.

AA := A; Mỗi lần xử lý 16 từ, mỗi từ 32 bit, tl:512 bit.

BB := B;
CC := C;
DD := D;
5.
6.
7.
8.

round_1();
round_2();
round_3();
round_4();

9.

A = A + AA
B = B + BB
C = C + CC
D = D + DD

}

6:

MD5

Bốn vòng trong MD5 là hoàn toàn khác nhau. Mỗi vòng (5, 6, 7, 8) gồm một trong
16 word trong T.
MD5 sử dụng thêm một mảng S[1 … 64] được xây dựng từ hàm sin. Với S[i], giá
trị của phần tử thứ i trong mảng S, tương đương với phần nguyên của 4294967296
abs(sin(i)), với i tính theo radian.
 Vòng 1 sử dụng giá trị trong mảng S[1 … 16]

Ta có mảng S[1 … 64] như sau (tất cả đều để ở hệ cơ số 16):
1. D76AA478

17. F61E2562

33. FFFA3942

49. F4292244

2. E8C7B756

18. D040B340

34. 8771F681

50. 432AFF97

3. 242070DB

19. 265E5A51

35. 6D9D6122

51. AB9423A7

4. C1BDCEEE

20. E9B6C7AA

36. FDE5390C

52. FC93A039

5. F57C0FAF

21. D62F105D

37. A4BEEA44

53. 655B59C3

6. 4787C62A

22. 02441453

38. 4BDECFA9

54. 8F0CCC92

7. A8304613

23. D8A1E681

39. F6BB4B60

55. FFEFF47D

8. FD469501

24. E7D3FBC

40. BEBFBC70

56. 85845DD1

9. 698098D8

25. 21E1CDE6

41. 289B7EC6

57. 6FA87E4F

10. 8B44F7AF

26. C33707D6

42. EAA127FA

58. FE2CE6E0

11. FFFF5BB1

27. F4D50D87

43. D4EF3085

59. A3014314

12. 895CD7BE

28. 455A14ED

44. 04881D05

60. 4E0811A1

13. 6B901122

29. A9E3E905

45. D9D4D039

61. F7537E82

14. FD987193

30. FCEFA3F8

46. E6DB99E5

62. BD3AF235

15. A679438E

31. 676F02D9

47. 1FA27CF8

63. 2AD7D2BB

16. 49B40821

32. 8D2A4C8A

48. D4AC5665

64. EB86D391

2

Các phép toán được thực hiện trong bốn vòng tạo ra các giá trị mới trong bốn
thanh ghi. Cuối cùng, bốn thanh ghi được cập nhật ở 3.5 bằng cách cộng ngược
các giá trị lưu trước đó ở 2.3. Phép cộng này được xác định là cộng các số nguyên
dương, được rút gọn theo modulo 232.

Vòng 1 (round_1())Vòng 2(round_2())
1. A = (A + F(B, C, D) + T0] + S[1] <<< 7

1. A = (A + G(B, C, D) + T[1] + S[17] <<< 5

2. D = (D + F(A, B, C) + T[1] + S[2]) <<< 12
3. C = (C + F(D, A, B) + T[2] + S[3]) <<< 17
4. B = (B + F(C, D, A) + T[3] + S[4]) <<< 22
5. A = (A + F(B, C, D) + T[4] + S[5]) <<< 7
6. D = (D + F(A, B, C) + T[5] + S[6]) <<< 12
7. C = (C + F(D, A, B) + T[6] + S[7]) <<< 17
8. B = (B + F(C, D, A) + T[7] + S[8]) <<< 22
9. A = (A + F(B, C, D) + T[8] + S[9]) <<< 7
10. D = (D + F(A, B, C) + T[9] + S[10]) <<< 12
11. C = (C + F(D, A, B) + T[10] + S[11]) <<< 17
12. B = (B + F(C, D, A) + T[11] + S[12]) <<< 22
13. A = (A + F(B, C, D) + T[12] + S[13]) <<< 7
14. D = (D + F(A, B, C) + T[13] + S[14]) <<< 12
15. C = (C + F(D, A, B) + T[14] + S[15]) <<< 17
16. B = (B + F(C, D, A) + T[15] + S[16]) <<< 22

2. D = (D + G(A, B, C) + T[6] + S[18]) <<< 9
3. C = (C + G(D, A, B) + T[21] + S[19]) <<< 14
4. B = (B + G(C, D, A) + T[0] + S[20]) <<< 20
5. A = (A + G(B, C, D) + T[5] + S[21]) <<< 5
6. D = (D + G(A, B, C) + T[10] + S[22]) <<< 9
7. C = (C + G(D, A, B) + T[15] + S[23]) <<< 14
8. B = (B + G(C, D, A) + T[4] + S[24]) <<< 20
9. A = (A + G(B, C, D) + T[9] + S[25]) <<< 5
10.D = (D + G(A, B, C) + T[14] + S[26]) <<< 9
11.C = (C + G(D, A, B) + T[3] + S[27]) <<< 14
12.B = (B + G(C, D, A) + T[8] + S[28]) <<< 20
13.A = (A + G(B, C, D) + T[13] + S[29]) <<< 5
14.D = (D + G(A, B, C) + T[2] + S[30]) <<< 9
15.C = (C + G(D, A, B) + T[7] + S[31]) <<< 14
16.B = (B + G(C, D, A) + T[12] + S[32]) <<< 20

Vòng 3(round_1())Vòng 4(round_4())
1. A = (A + H(B, C, D) + T[5] + S[33]) <<< 4
2. D = (D + H(A, B, C) + T[8] + S[34]) <<< 11
3. C = (C + H(D, A, B) + T[11] + S[35]) <<< 16
4. B = (B + H(C, D, A) + T[14] + S[36]) <<< 23
5. A = (A + H(B, C, D) + T[1] + S[37]) <<< 4
6. D = (D + H(A, B, C) + T[4] + S[38]) <<< 11
7. C = (C + H(D, A, B) + T[7] + S[39]) <<< 16
8. B = (B + H(C, D, A) + T[10] + S[40]) <<< 23
9. A = (A + H(B, C, D) + T[13] + S[41]) <<< 4
10. D = (D + H(A, B, C) + T[0] + S[42]) <<< 11
11. C = (C + H(D, A, B) + T[3] + S[43]) <<<16
12. B = (B + H(C, D, A) + T[6] + S[44]) <<< 23
13. A = (A + H(B, C, D) + T[9] + S[45]) <<< 4
14. D = (D + H(A, B, C) + T[12] + S[46]) <<< 11
15. C = (C + H(D, A, B) + T[15] + S[47]) <<< 16
16. B = (B + H(C, D, A) + T[2] + S[48]) <<< 23

1. A = (A + I(B, C, D) + T[0] + S[49]) <<< 6
2. D = (D + I(A, B, C) + T[7] + S[50]) <<< 10
3. C = (C + I(D, A, B) + T[14] + S[51]) <<< 15
4. B = (B + I(C, D, A) + T[5] + S[52]) <<< 21
5. A = (A + I(B, C, D) + T[12] + S[53]) <<< 6
6. D = (D + I(A, B, C) + T[3] + S[54]) <<< 10
7. C = (C + I(D, A, B) + T[10] + S[55]) <<< 15
8. B = (B + I(C, D, A) + T[1] + S[56]) <<< 21
9. A = (A + I(B, C, D) + T[8] + S[57]) <<< 6
10. D = (D + I(A, B, C) + T[15] + S[58]) <<< 10
11. C = (C + I(D, A, B) + T[6] + S[59]) <<< 15
12. B = (B + I(C, D, A) + T[13] + S[60]) <<< 21
13. A = (A + I(B, C, D) + T[4] + S[61]) <<< 6
14. D = (D + I(A, B, C) + T[11] + S[62]) <<< 10
15. C = (C + I(D, A, B) + T[2] + S[63]) <<< 15
16. B = (B + I(C, D, A) + T[9] + S[64]) <<< 21

Bước 5: Output
Kết quả ra là đoạn mã có độ dài 128 bit, được thu gọn từ thông điệp a có
độ dài b bit. Đoạn mã này thu được từ 4 thanh ghi A, B, C, D: bắt đầu từ
byte thấp của thanh ghi A cho đến byte cao của thanh ghi D.

Hàm băm MD5 (còn được gọi là hàm tóm tắt thông điệp - message degests) sẻ trả
về một chuổi số thập lục phân gồm 32 số liên tiếp. Dưới đây là các ví dụ mô tả các
kết quả thu được sau khi băm.
MD5("cộng hòa xã hội chủ nghĩa việt nam")
= 7b8e76fac176d53c53cb24843e31e759
Thậm ch chỉ cần một thay đổi nhỏ cũng làm thay đổi hoàn toàn kết quả trả về :
MD5(“ Cộng Hòa Xã Hội Chủ Nghĩa Việt Nam “)
= 0634f131b89616154a643be79b61eda4
Ngay cả một chuổi rỗng cũng cho ra một kết quả phức tạp:
MD5(“”)
= d41d8cd98f00b204e9800998ecf8427e

4:
1. Một vòng thứ tư đã được thêm vào.
2. Mỗi bước
.
3. Các chức năng ở vòng 2 đã được thay đổi từ (XY v XZ v YZ) để (XZ v Y
not (Z)) để làm g
ính đối xứng.
4. Mỗi bước bây giờ có thêm trong kết quả của bước trước. Điều này thúc
đẩy nhanh hơn
.
5. Thứ tự từ đầu vào được truy cập trong vòng 2 và 3 là thay đổi, để làm cho
các mô hình nhỏ như nhau.

.

IV.

:

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.

, đây là một thuật toán tương đối mới và việc

phân tích cẩnthận về sự an toàn là cần thiết.
C

5

Dobber

, Dengguo Feng,
, Xiaoyun Wang,
,...

:

“Thông điệp đệm” – messege padding - là một xâu bit có độ dài chia hết cho
512.
“Thông điệp đệm” được lưu trong mảng
M = M[0] M[1] … M[N-1].
Trong đó M[i] là xâu bit có độ dài 32 bit, gọi là word; N mod 16 = 0.
M được xây dựng từ thông điệp a bằng thuật toán:
Bảng 1.7 : Xây dựng thông điệp đệm M từ a
1. d = 447 – (|a| mod 512); (+ 512, trường hợp |a| mod 512 >
447).
2. Giả sử llà kí hiệu biểu diễn nhị phân của |a| mod 264, tl: |l| =
64.
3. M = a || 1 || 0d || l
- Độ dài của xâu a || 1 || 0d

là

|a| + 1 + d = 448 mod 512 .

- Độ dài của “Thông điệp đệm” M là 448 mod 512 + 64 = 512 mod 512.
Ví dụ : Có xâu đầu vào a = “ABC”, ta có kết quả xây dựng M như sau:
a = “ABC” = "01000001 01000010 01000011"
- Độ dài tính theo bit của xâu a:
|a| = 24 bit
=> d = 447 – (|a| mod 512) = 423.
|a| + 1 + d = 24 + 1 + 423 = 448 mod 512.
- Biểu diễn nhị phân của độ dài xâu a là l:
l = |a| mod 264 = 24 mod 264 = 24 = 16 + 8 = ( 00 ..... 11000 )2

 00
59 so

=> Độ dài của l là |l| = | 00 ..... 11000| = 59 + 5 = 64.

 00
59 so

M = a || 1 || 0d ||l

=> M = 01000001 01000010 01000011 || 1 ||

00 ..... 
  00
 
423 so

M = M[0] M[1] … M[N-1], N

|| 00 ..... 00 11000

 
59 so

0 mod 16

M[0] = 01000001 01000010 01000011 10000000
M[1] = M[2] = ….. = M[13] = M[14] = 00 ..... 
  00
 
32 so

M[15] = 00000000 00000000 00000000 00011000
Trong việc xây dựng M, ta gắn số 1 đơn lẻ vào sau a, sau đó thêm tiếp các số
0 vào đủ để độ dài của M đồng dư với 448 modulo 512. Cuối cùng nối thêm 64 bit
(chính là |l|) chứa biểu diễn nhị phân về độ dài ban đầu của x (được rút gọn theo
modulo 264 nếu cần).
Xâu kết quả M có độ dài chia hết cho 512. Vì thế khi chặt M thành các word
32 bit, số word nhận được là N sẽ chia hết cho 16.
Mục đích việc tạo ra mảng M – “thông điệp đệm” – là để các hàm băm xử lý
trên từng khối (block)512 bit, tức là 16 word, cùng một lúc.

--------------------

--------------------------

�ݺ�ߣ

7. tìm hiểu hàm băm md5 và ứng dụng

More Related Content

7. tìm hiểu hàm băm md5 và ứng dụng