Trêng §¹i häc S ph¹m kü thuËt Hng Yªn
Khoa C«ng nghÖ th«ng tin

TiÓu luËn
Môn: AN TOÀN VÀ BẢO MẬT THÔNG TIN
Đề tài: Nghiên cứu về các thuật toán băm dữ liệu từ đó
viết đặc tả và vẽ lưu đồ thuật toán
Giảng viên hướng dẫn: Nguyễn Duy Tân
Sinh viên thực hiện : Trần Thị Thu
Lớp : TK6LC_1
Hng yªn 01/2010
1
I.Các hàm Hash ( hay còn gọi là hàm băm)
I.1 Các yêu cầu
Nén mẩu tin bất kỳ về kích thước cố định và giả thiết hàm hash là công khai
và không dung khóa Hash chỉ phụ thuộc mẩu tin.
Hash được sử dụng để phát hiện thay đổi của mẩu tin Hash có thể sử dụng
nhiều cách khác nhau với mẩu tin, Hash thường được kết hợp dùng để tạo chữ ký
trên mẩu tin.
Hàm hash có các tính chất sau:
+ Tạo nên dấu vân tay ( tức là thong tin đặc trưng) của
một tệp, mẩu tin hay dữ liệu h = HCM.
+ Nén mẩu tin có kích thước tùy ý về dấu vân tay có
kích thước cố định. Hàm hash được giả thiết là công khai, mọi nguời đều
biết cách sử dụng.
Các yêu cầu của hàm Hash:
+ Có thể áp dụng cho mọi mẩu tin có kích thước tùy ý.
Tuy nhiên phải tạo đầu ra h có kích thước cố định, thường là 128 bit đến
1024 bit.
+ Dễ tính h = HCM cho mọi mẩu tin M, hàm H tính
toán nhanh, hiệu quả phụ thuộc chặt vào mẩu tin M và không tính tóan

/ 365
k
Do đó, xác suất p để có ít nhất 2 người trùng ngày sinh nhật là:
P= 1 – q = 1 - C
k
365
/ 365
k
Để p > 0,5 thì k > 22 hay k = 23, cụ thể khi đó p = 0,5073. Khi chưa tính toán
chi tiết chúng ta nghĩ là trong lớp phải có ít nhất khoảng 365/2 tức 184 sinh viên.
Nhưng dựa trên thực tế con số đó ít hơn rất nhiều chỉ cần 23 sinh viên, chính vì vậy
ta gọi đây là nghịch lý ngày sinh nhật.
3
Điều đó muốn nói lên rằng trong nhiều trường hợp xác suất để 2 mẩu tin có
cùng bản hash là không nhỏ như chúng ta tưởng.
Tấn công ngày sinh nhật hoạt động như sau:
Kẻ thám mã tạo ra 2
m/2
biến thể của mẩu tin đúng mà tất cả đều có bản chất
ngữ nghĩa như nhau, với m ở đây là độ dài của bản mã hash.
Kẻ thám mã cũng có thể tạo ra 2
m/2
biến thể khác nhau của mẩu tin lừa dối, là
có ngữ nghĩa ngược lại.
Hai tập tin được so sánh với nhau để tìm cặp có cùng bản hash( xác suất
>=0,5 dựa vào nghịch lý ngày sinh nhật)
Người dùng kí vào mẩu tin đúng, sau đó bị thay thế bằng mẩu tin giả mà cũng
có chữ ký đúng.
I.3. Mã khối như hàm hash
Có thể sử dụng mã khối như hàm hash

4
phần cứng. Nhưng có thể tìm được va chạm sau 24 ngày. Do đó có thể coi là hash
128 bit có thể có lỗ hổng, không an toàn, tốt hơn dùng hash 160 bit.
Thám mã tấn công có cấu trúc:
Giống như mã khối muốn dùng tấn công vét cạn có một số các tấn công thám
mã là lựa chọn tôt nhất hiện có.
Chẳng hạn:
Nếu CV
i
= f [CV
i – 1
,M
i
] ; H(M) = CV
N

Thì ở đây thong thường khai thác sự va chạm của hàm f.
Giống mã khối thường gồm 1 số vòng lặp
Khi đó tấn công sử dụng các tính chất có hàm vòng.
II.Các thuật tóan Hash
Hàm hash: thực hiện việc nén mẩu tin về kích thước cố định bằng cách xử lí
mẩu tin theo từng khối dùng một hàm nén nào đó mà có thể sử dụng mã khối dùng
một hàm nén nào đó và chỉ có thể sử dụng mã khối.
Cấu trúc thuật toán Hash
5
II.1 Thuật toán Hash an toàn SHA ( Secure Hash Algorithm)
SHA có nguồn gốc từ Viện chuẩn công nghệ quốc gia Hoa Kì – NIST & NSA
vào năm 1993, sau đó được nâng cấp vào năm 1995 theo chuẩn US và chuẩn là
FIPS 180 – 11995 và Internet RFC3174, được nhắc đến như SHA – 1. Nó được sử
dụng với sơ đồ chữ kí điện tử DSA ( Digital Signature Algorithm).

là từ j trong giá trị băm ở lần lặp i với
0≤i≤N ( số block có được sau khi chia văn bản được đệm) và 0≤j≤( số từ trong giá
trị băm - 1). Trước khi thực hiện giá trị băm, với mỗi thuật toán băm an toàn, giá
trị băm ban đầu H(0) phải được thiết lập. Kích thước và số lượng từ trong H(0) tùy
thuộc vào kích thước thông điệp rút gon.
SHA -1 sử dụng dãy hằng số K(0),…,K(79) có giá trị như sau:
K(t) = 5A827999 (0≤t≤19)
K(t) = 6ED9EBA1 (20≤t≤39)
K(t) = 8F1BBCDC (40≤t≤59)
K(t) = CA6 2C1D6 (60≤t≤79)
II.1.1.3 Thuật toán cuả bước tính giá trị băm SHA – 1
SHA – 1 được sử dụng để băm thông điệp M có độ dài l bit thỏa mãn điều
kiện 0≤l≤2
64
. Thuật toán sử dụng :
- Một bảng phân bố thông điệp gồm 80 từ 32 bit
- 5 biến 32 bit
- Một giá trị băm gồm 5 từ 32 bit
Kết quả của SHA – 1 là một thông điệp rút gọn có độ dài 160 bit. Các từ của
bảng phân bố thông điệp được kí hiệu W(0), W(1),…,W(79). 5 biến được kí hiệu là
a,b,c,d,e. Các từ của giá trị băm kí hiệu H
0
(i)
, H
1
(i)
, H
2
(i)
, H

30
(b); b = a; a = TEMP
− Đặt H0 = H0 + a, H1 = H1 + b, H2 = H2 + c, H3 = H3 + d, H4 = H4 + e
Sauk hi tính toán được hết M(n), thông điệp rút gọn là chuỗi 160 bit biểu diễn
của 5 từ:
H0 H1 H2 H3 H4
II.1.1.4 Đánh giá thuật toán
− SHA – 1 được xem như là an toàn đối với trường hợp đụng độ vì
rất khó tìm đuợc 2 thông điệp khác nhau có gía trị băm giống nhau.
− SHA -1 được coi là chuẩn của việc bảo vệ các kênh liên lạc trực
tuyến tồn tại trong 9 năm qua.
− SHA – 1 được thiết kế cho bộ xử lí 32 bit, thế hệ sắp tới cuả máy
tính dùng bộ xử lí 64 bit mà SHA – 1 không hiệu quả trên bộ xử lí này.
− Tháng 2 năm 2005 SHA -1 bị tấn công bởi 3 chuyên gia người
Trung Quốc. Thuật toán này đã bị giải mã thông qua phương pháp tính phân
bổ.
II.1.1.4 Các phiên bản
8
Viện chuẩn công nghệ quôc gia NIST xuất bản sửa FIPS 180 -2 vào năm
2002, đề nghị bổ sung 3 phiên bản mới của SHA : SHA – 256, SHA – 384, SHA –
512. Các phiên bản trên được thiết kế tương thích với việc tăng độ an toàn cung cấp
bởi chuẩn mã nâng cao AES. Về cấu trúc và chi tiết giống SHA -1, suy ra việc phân
tích cũng tương tự, nhưng mức độ an toàn cao hơn nhiều so với SHA – 1.
So sánh các phiên bản SHA
Các giá trị có đơn vị là bit
III. Tổng quan về SHA – 512
512384256160Kích thước giá trị băm
25619212880Độ an toàn
80806480Số bước mã hóa
64643232Kích thước Word

SHA-512 Round Function
12
IV. Thuật toán MD5
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.
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ũng do ông thiết kế, trước đó nữa là MD2)
MD5 có hai ứ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 1 đ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àm nản lòng các hacker)
IV.1 Thuật giải
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ó chia hết cho 512 )
Bộ đệm hoạt động như sau:
-Trước tiên nó được 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ội
số của 512 mộ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ều
dài ban đầu của thông điệp
13

điều kiện để kẻ xấu cài những chương trình cửa sau (backdoor) bí mật vào trong
mã máy tính, hoặc giả mạo chữ kí điện tử. Trừ phi một thuật toán mới bảo mật hơn
được xây dựng và đưa vào sử dụng.
Một phát hiện thứ ba, được đón đợi và đánh giá rất cao được công bố trong
hội thảo Grypto. Hai nhà nghiên cứu EliBiham và Rafi Chen của viện công nghệ
Israel đã diễn thuyết vễ cách nhận dạng các hình thức tấn công vào chức năng bảo
mật của thuật toán SHA – 0 một thuật toán có sơ hở.
Những lỗ hổng bảo mật được cho là “ nghiêm trọng” bên trong thuật toán
SHA – 1, tùy thuộc vào mức độ chi tiết của phần trình bày, có thể làm chấn động cả
nghành bảo mật. Từ trước tới nay, SHA – 1 vẫn được coi là chuẩn mực “vàng” về
thuật toán. Nó được tích hợp bên trong rất nhiều chương trình thông dụng như PGP
và SSL, được chứng thực bởi viện công nghệ quốc gia và là thuật toán chữ ký điện
tử duy nhất được cơ quan Chuẩn Chữ kí số của chính phủ Mĩ phê chuẩn.
Cả ba thuật toán MD5,SHA – 0 và SHA – 1 đều được giới khoa học máy tính
coi là “ đa chức năng”. Chúng có thể nhận mọi dạng dữ liệu đầu vào, từ tin nhăn
email cho đến hạt nhân(kernel) của hệ điều hành, cũng như tạo ra một dấu vân tay
số duy nhất chỉ thay đổi một kí tự bất kì bên trong file đầu vào cũng tạo ra dấu vân
tay hoàn toàn khác nhau. Các ứng dụng bảo mật đều dựa vào tính năng “dấu vân
tay duy nhất” này làm nền. Tuy nhiên, nếu kẻ tấn công có thể tạo ra một dấu vân
tay “Dolly” với một dòng dữ liệu đầu vào khác, dấu vân tay “ sinh sản vô tính” này
sẽ khiến phần mềm bị gài backdoor nhận dạng nhầm. Kết quả là chúng có thể tạo ra
chữ kí giả để vét sạch tài khoản ngân hang của người sử dụng không may.
Tất nhiên từ rất lâu, giới nghiên cứu đã hiểu rằng không có thuật toán mã hóa
thực tiễn nào là tuyệt đối an toàn và bảo mật. Tuy vậy, họ vẫn nỗ lực thiết kế ra
những thuật toán mà thời gian cần để tạo ra một dấu vân tay “ Dolly” là vô tận, với
15
hy vọng kẻ tấn công sẽ nản lòng. Thế nhưng nếu những sơ hở tương tụ như của
SHA – 0 cũng được tìm thấy trong SHA – 1, điều này đồng nghĩa với việc tốc độ
giả mạo một dấu vân tay sẽ được đẩy nhanh lên…500 triệu lần, hoàn toàn trong
tầm tay của một mạng máy tính tốc độ cao.

lượng 8 bit. Một dãy các bit có thể được xem như 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 module 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.
IV.4 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ố 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}.
17
Mã số thông điệp được tính qua 5 bước sau:
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 thực hiện như sau: Thêm bit “1“ được vào sau thông điệp.
Tiếp đó 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.

/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M.
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) <<< 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]
19
[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) <<< 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) <<< s). */
/* Thực hiện :*/

tìm được một thông điệp với mã số cho trước là 2
18
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.
IV.6 Sự khác nhau giữ MD4 và MD5
− Vòng 4 đã được thêm vào
− Mỗi bước đều được thêm vào một hằng số duy nhất
− Hàm G ở vòng 2 được đổi từ (XY v XZ v YZ ) thành ( XZ vY not
( Z )) để làm giảm sự đối xứng trong G
− 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 truyền ” nhanh hơn
21
− Thứ tự các word đầu vào ở vòng 2 và 3 được thay đổi, để làm cho
hai mẫu này ít giống nhau hơn
− Số bit dịch chuyển ở mỗi vòng được tối ưu hóa, để tạo ra “ hiệu
ứng dây truyền ” nhanh hơn. Lượng dịch chuyển ở mỗi vòng là khác nhau.
IV.7 Đánh giá thuật toán MD5
Về tốc độ sinh ra chuỗi cốt yếu thì MD5 chậm hơn so với MD4 nhưng nó lại
an toàn hơn rất nhiều so với MD4. 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 giá trị băm 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 giá trị băm là khoảng 2
64
bước tính,
và độ khó để tìm được một thông điệp với giá trị băm cho trước là 2
128
bước tính.
Tuy nhiên lỗ hổng mới phát hiện trong thuật toán MD5 sẽ cho phép kẻ tấn công có
thể tạo ra file giả mạo trong vòng vài giờ với loại máy tính đạt chuẩn.
IV.7 Chuẩn Hash an toàn nâng cao