HỌC VIỆN KỸ THUẬT MẬT MÃ
KHOA AN TOÀN THÔNG TIN

BÁO CÁO BÀI TẬP LỚN MÔN HỌC
MẬT MÃ HỌC NÂNG CAO
Chủ đề số 20
CÀI ĐẶT THUẬT TOÁN RIPEMD
Giảng Viên: TS.Trần Tuấn Anh
Thực hiện: Sinh viên AT8C
1. Lê Xuân Đoàn
2. Bùi Đức Thiện
1
Ý KIẾN GIẢNG VIÊN

Hiểu theo nghĩa đơn giản, hàm băm là hàm cho tương ứng một mảng dữ liệu
lớn với một mảng dữ liệu nhỏ hơn mà được dùng rộng rãi trong nhiều ứng dụng
tin học, không chỉ thuộc phạm vi mật mã. Ở đây, chúng ta chỉ xét đến các hàm
băm trong phạm vi các hàm băm mật mã, xem xét cụ thể đến các ứng dụng của
chúng trong việc đảm bảo tính toàn vẹn của dữ liệu.
Các hàm băm nhận đầu vào là một chuỗi bit có chiều dài hữu hạn tùy ý và
tạo ra một chuỗi bit có chiều dài cố định bằng n bit (n > 0) gọi là mã băm (hash
code).
Trong mã hóa, mã băm được xem như là ảnh đại diện thu gọn (compact
representative image) của một chuỗi bit có độ dài hữu hạn tùy ý và được dùng
để nhận diện cho chuỗi bit đó. Kết hợp với công cụ tạo chữ ký số, các hàm băm
được dùng cho việc đảm bảo tính toàn vẹn của dữ liệu. Trong lược đồ chữ ký số,
mã băm của chuỗi bit được tính ở thời điểm T
1
và được bảo vệ để chống lại mọi
sự thay đổi bất hợp pháp. Tại thời điểm T
2
sau đó, để kiểm tra xem chuỗi bit x có
bị thay đổi hay không, người ta thường tính giá trị hàm băm của chuổi bit này tại
thời điểm T
2
, mà ta ký hiệu là x
T2
, sau đó so sánh giá trị vừa tính với mã băm tại
thời điểm T1. Nếu 2 giá trị bằng nhau thì người ta chấp nhận chuổi bit tại thời
điểm T2 trùng khớp với chuổi bit tại thời điểm T1, tức chuỗi bit x vẫn chưa bị thay
đổi. Như vậy vấn đề bảo đảm tính toàn vẹn của chuỗi bit có chiều dài tùy ý được
thay bằng việc bảo vệ sự toàn vẹn của chuỗi bit có chiều dài cố định.
1.2 Định nghĩa tổng quát của hàm băm
Hàm h(x) được gọi là một hàm băm nếu nó thoả mãn hai tính chất sau:

Trong lớp các hàm băm không sử dụng khoá thì MDCs (Modification
Detection Codes – mã nhận diện sự thay đổi) là lớp con của lớp này. Lớp hàm
này lại tiếp tục phân thành các lớp con nhỏ hơn
5
- Hàm băm một chiều (One-Way Hash Functions - OWHFs): các
hàm trong lớp này đều thoã tính chất là với mọi mã băm biết trước, không
thể tính toán để tìm được chuỗi bit đầu vào có mã băm bằng với mã băm
đã cho.
- Hàm băm kháng xung đột (Collision Resistant Hash Functions -
CRHFs): các hàm trong lớp này thoã mãn tính chất không thể tính
toán để tìm ra hai chuỗi bit có cùng giá trị băm.
1.5 Cấu trúc của thuật toán hàm băm
Khối dữ liệu đầu vào x có chiều dài tuỳ ý sẽ được phân thành các khối con liên
tiếp x1, x2, …, xm (với xi có chiều dài cố định là r). Tuy nhiên do chiều dài khối ban
đầu là tùy ý nên ta cần thêm vào dữ liệu ban đầu một số bit phụ sao cho tổng số bit
của khối dữ liệu x sau khi thêm vào sẽ là bội số của r. Ngoài ra số bit phụ thêm vào
thường chứa một khối bit xác định chiều dài thực sự của khối dữ liệu khi chưa thêm
các bit phụ. Sau đó ta lần lượt cắt từng khối con r bit từ khối x.
Mỗi khối con r bit xi ta thực hiện một hàm nén của hàm băm h(x) được ký hiệu
là f. Tại bước thứ i, hàm nến f nhận dữ liệu đầu vào là xi và kết quả trung gian của
bước trước đó để tạo đầu ra là kết quả trung gian bước thứ i, ký hiệu là Hi. Kết quả
trung gian tại mỗi bước Hi là một chuổi bit có độ dài cố định bằng n>0. Nếu ký hiệu
IV (init value) là giá trị khởi tạo ban đầu cho H0, thì quá trình lặp xử lý dãy các khối
con x1,x2,…, xm được mô tả như sau:
H
0
=IV
H
1
= f(H

Một ứng dụng quan trọng khác của các hàm băm bảo mật là sự kiểm tra tính
toàn vẹn của thông điệp. Ví dụ, việc xác định xem một file hay một thông điệp có bị
sửa đổi hay không có thể thực hiện bằng cách so sánh tóm tắt được tính trước và sau
khi gửi (hoặc một sự kiện bất kỳ nào đó). Còn có thể dùng tóm tắt thông điệp làm
một phương tiện đáng tin cậy cho việc nhận dạng file.
Một ứng dụng có liên quan là kiểm tra mật khẩu. Mật khẩu thường khôngđược
lưu dưới dạng văn bản rõ (clear text), mà ở dạng tóm tắt. Để xác thực một người
dùng, mật khẩu do người đó nhập vào được băm và so sánh với kết quả băm được
lưu trữ.
Do các lý do cả về bảo mật và hiệu năng chương trình, đa số các thuật toán
chữ ký số nói rằng chỉ có tóm lược của thông điệp, chứ không phải toàn văn thông
điệp, được "ký". Các hàm băm còn có thể được dùng để tạo các bit giả ngẫu nhiên
(pseudorandom).
1.7 Các hàm băm mật mã hiện nay
Trong danh sách dài các hàm băm mật mã dưới đây, có một số hàm băm được
cho là dễ bị tổn thương và không nên sử dụng. Ngay cả khi một hàm băm chưa bị
phá vỡ, một tấn công thành công đối với một biến thể yếu đó có thể làm giảm sự tự
tin của các chuyên gia và dẫn đến loại bỏ nó. Ví dụ, vào tháng 8 năm 2004 người ta
đã tìm ra những điểm yếu của một vài hàm băm phổ biến vào thời đó, bao gồm SHA-
0, RIPEMD, và MD5. Điều này đã đặt ra câu hỏi an ninh lâu dài của các thuật
toán sau này được bắt nguồn từ những hàm băm này - đặc biệt, SHA-1 (một phiên
7
bản mạnh của SHA-0), RIPEMD-128, và RIPEMD-160 (cả hai phiên bản mạnh của
RIPEMD). Vì vậy, cả SHA-0 và RIPEMD đều không được sử dụng rộng rãi kể từ
khi chúng được thay thế bởi các phiên bản mạnh.
Thuật toán Kích thước đầu ra Kíc
h
thước
trạng
thái

160/320 160/320 512 64 32 Khôn
g
SHA-0 160 160 512 64 32 Có
8
Bảng 1: Các hàm băm mật mã
9
CHƯƠNG 2
HÀM BĂM RIPEMD
2.1 Tổng quan về hàm băm RIPEMD
RIPEMD (RACE Integrity Primitives Evaluation Message Digest) là một họ
của hàm băm mật mã được phát triển ở Leuven- Bỉ bởi Hans Dobbertin, Antoon
Bosselaers và Bart Preneel tại nhóm nghiên cứu COSIC tại Katholieke Universiteit
Leuven và lần đầu tiên được xuất bản vào năm 1996. RIPEMD được dựa trên các
nguyên tắc thiết kế được sử dụng trong MD4, nhưng hiệu năng hoạt động phổ biến
hơn MD4
2.2 RIPEMD-128
RIPEMD - 128 là một hàm băm 128 -bit sử dụng xây dựng như mở rộng của
Thuật toán Merkle Damgard : hàm băm được xây dựng bằng cách duyệt một chức
năng nén 128 -bit mà mất như một đầu vào 512 -bit với đẩu ra là 128 bit.
Các chức năng nén RIPEMD - 128 dựa trên MD4 , với các đặc thù mà nó sử
dụng hai trường hợp song song của nó, Chúng ta phân biệt hai chi nhánh tính toán của
nhánh trái và nhánh phải và chúng ta hiển thị bởi X
i
(resp. Y
i
) 32 bit của nhánh trái
(resp. right branch).Quá trình này sẽ được cập nhật trong bước i của hàm nén .Quá
trình này bao gồm 64 bước chia thành 4 vòng 16 bước từng ở cả hai chi nhánh cụ thể
về quá trình:
Khởi tạo: Các đầu vào 128 -bit chuỗi cv

an toàn cho các hàm băm 128-bit MD4 , MD5 và RIPEMD . MD4 và MD5 được phát
triển bởi Ron Rivest cho RSA Data Security, trong khi RIPEMD được phát triển trong
khuôn khổ của dự án RIPE EU ( RACE Integrity Primitives Evaluation, 1988-1992 ) .
Có ba lý chính để xem đây là một sự thay đổi tốt :
• Một kết quả băm 128 -bit không cung cấp đủ bảo vệ nữa, một cuộc tấn công
brute force vào hàm 128 bit chỉ đòi hỏi 2
64
hoặc 2.10
19
giá trị của hàm. Năm
1994 Paul van Oorschot và Mike Wiener cho thấy việc brute- lực lượng này có
thể được thực hiện trong vòng chưa đầy một tháng với một khoản đầu tư $
10.000.000
• Trong nửa đầu năm 1995 Hans Dobbertin tìm thấy va chạm đối với một phiên
bản của RIPEMD hạn chế đến hai vòng cùng của ba .Sử dụng kỹ thuật tương tự
được sản xuất Hans vào mùa thu năm 1995 cho các va chạm (tất cả 3 vòng )
11
MD4 . Cuộc tấn công vào MD4 chỉ đòi hỏi một vài giây trên một máy tính , và
vẫn còn để lại một ít tự do để lựa chọn các tin nhắn, cầm quyền rõ ràng ra MD4
như là một hàm băm kháng va chạm . Ngay sau đó , vào mùa xuân năm 1996,
Hans cũng tìm thấy va chạm cho các chức năng nén MD5 . Mặc dù chưa được
mở rộng đến va chạm với MD5 bản thân , cuộc tấn công này phôi nghi ngờ
nghiêm trọng về sức mạnh của MD5 là một vụ va chạm
• Crypto 2004 Xiaoyun Wang , Dengguo Feng , Xuejia Lai và Hongbo Yu tìm
thấy sự xung đột trong: MD4, MD5, RIPEMD, and the 128-bit version of
HAVAL.
RIPEMD - 160 là một phiên bản được tăng cường của RIPEMD với một kết
quả băm 160 -bit , và dự kiến sẽ được an toàn trong mười năm tới hoặc hơn . Triết lý
thiết kế là xây dựng càng nhiều càng tốt về kinh nghiệm thu được bằng cách đánh giá
MD4 , MD5 , và RIPEMD . Giống như người tiền nhiệm của nó , RIPEMD - 160

Ở đây
<<s
biểu thị sự thay đổi theo chu kì (xoay) theo vị trí s trên bit
2 :
Thứ tự của các tin nhắn,theo hoán vị sau
Xác định rõ hơn các hoán vị π bằng cách thiết lập π (i) = 9i + 5 (mod 16). Thứ tự của
các thông điệp được cho bởi bảng sau:
14
Các hàm Logic được xác định như sau
Các hàm Logic được áp dụng như sau
4 :
Những thay đổi

5 :
15
Các hằng số
Phân tích thuật toán RIPEMD-128
RIPEMD-128 có 1 vài sự thay đổi đối với RIPEMD-160
Thông điệp đầu vào sẽ được xử lí qua 4 vòng song song .Kết quả của RIPEMD-
128 được chứa trong 4 từ 32 bit
1:
A := (A + f (B; C; D) + X + K)
<<s
2: Hàm Logic
3: Hằng số
3.2 Thiết kế
1: Khai báo giá trị các thanh ghi dùng trong xử lí
Mỗi thanh ghi có độ dài 32 bit,các thanh ghi này được khởi tạo bằng giá trị hecxa
RIPEMD -160
dword AA = AAA = 0x67452301UL;

"a"
0bdc9d2d256b3ee9daae347be6f4dc835a467ffe
"abc"
8eb208f7e05d987a9b044a8e98c6b087f15a0bfc
"message digest"
5d0689ef49d2fae572b881b123a85ffa21595f36
"abcdefghijklmnopqrstuvwxyz"
f71c27109c692c1b56bbdceb5b9d2865b3708dbc
"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
12a053384a9c0c88e405a06c27dcf49ada62eb2b
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz012345678
9"
b0e20b6e3116640286ed3a87a5713079b21f5189
8 times "1234567890"
9b752e45573d4b39f4dbd3323cab82bf63326bfb
1 million times "a"
52783243c1697bdbe16d37f97f68f08325dc1528
RIPEMD-128:
""
cdf26213a150dc3ecb610f18f6b38b46
"a"
86be7afa339d0fc7cfc785e72f578d33
"abc"
20
c14a12199c66e4ba84636b0f69144c77
"message digest"
9e327b3d6e523062afc1132d7df9d1b8
"abcdefghijklmnopqrstuvwxyz"
fd2aa607f71dc8f510714922b371834e
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz012345678

byte[] r = "a".getBytes("US-ASCII");
RIPEMD160Digest d = new RIPEMD160Digest();
d.update (r, 0, r.length);
byte[] o = new byte[d.getDigestSize()];
d.doFinal (o, 0);
System.out.println("RIP-160");
Hex.encode (o, System.out);
System.out.println(); byte[] r2 = "a".getBytes("US-ASCII");
RIPEMD128Digest d2 = new RIPEMD128Digest();
d2.update (r2, 0, r2.length);
byte[] o2 = new byte[d2.getDigestSize()];
d2.doFinal (o2, 0);
System.out.println("RIP-128");
Hex.encode (o2, System.out);
System.out.println();
}
}
Chương trình thực hiện băm thông điệp đầu vào là “a” và kết quả băm trả về tương
ứng cho RIPEMD-160 và RIPEMD -128 là
RIP-160
0bdc9d2d256b3ee9daae347be6f4dc835a467ffe
RIP-128
86be7afa339d0fc7cfc785e72f578d33
23
KẾT LUẬN
Sau thời gian tìm hiểu nhóm đã tìm hiểu được tổng quan về hàm băm và Hàm băm
RIPEMD, đi sâu phân tích và thiết kế phần mềm băm dựa trên thuật toán của