Đề tài tìm hiểu hàm băm (Hash function)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (787.78 KB, 20 trang )
ĐỀ TÀI: TÌM HIỂU HÀM BĂM ( HASH
FUNCTION)
Nội dung:
1. Giới thiệu hàm Hash
2. Ứng dụng hàm hash
3. Thuật toán
4. Tổng kết
Giới thiệu hàm HASH
Giới thiệu:
Hàm băm (Hash function) là thuật toán nhằm chuyển đổi một
thông điệp đầu vào có độ dài bất kỳ thành một dãy bit có độ dài
cố định (tuỳ thuộc vào thuật toán băm). Dãy bit này được gọi là
thông điệp rút gọn (message digest) hay giá trị băm (hash
value), đại diện cho thông điệp ban đầu.
Hàm băm (hash function) là hàm một chiều mà nếu đưa một
lượng dữ liệu bất kì qua hàm này sẽ cho ra một chuỗi có độ dài
cố định ở đầu ra
Giới thiệu hàm HASH
Giới thiệu hàm HASH
Tính chất cơ
bản của hàm
Hash
Tính một chiều: không
thể suy ra dữ liệu ban
đầu từ kết quả, điều này
tương tự như việc bạn
không thể chỉ dựa vào
một dấu vân tay lạ mà
suy ra ai là chủ của nó
được.
Tính duy nhất: xác
suất để có một vụ va
chạm (hash collision),
tức là hai thông điệp
khác nhau có cùng
một kết quả hash, là
cực kỳ nhỏ
Giới thiệu hàm HASH
Các hàm băm mật mã học phổ biến:
MD5
SHA-1
SHA-256/224
SHA-512/384
Ngoài ra còn rất nhiều hàm băm mật mã học nữa. Hàm
băm SHA-1 được sử dụng rộng rãi nhất ở Việt Nam.
Ứng dụng của hàm Hash
Xác thực mật khẩu
Xác thực thông điệp (Message authentication – Thông
điệp tóm tắt -message digests)
Bảo vệ tính toàn vẹn của tập tin, thông điệp được gửi
qua mạng.
Tạo chữ ký điện tử (Digital signatures)
Thuật toán
Giới thiệu hàm băm MD5
MD5 (Message-Digest algorithm 5) là một hàm băm để mã hóa với giá trị
băm là 128 bit.
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.
MD5 thường dùng để mã hóa mật khẩu.
Phát triển bởi Ron Rivest tại MIT năm 1991 để thay thế cho MD4
Thuật toán
Input: thông điệp với độ dài bất kỳ
Output: thông điệp rút gọn (message digest) có độ dài 128 bits
Giải thuật gồm 5 bước trên khối 512 bits
Bước 1: Nhồi dữ liệu
Thông điệp được nhồi thêm các bit sao cho độ dài L mod 512
luôn đồng dư là 448 hay l = n*512 + 448 (n,l nguyên ).
Thông điệp luôn luôn được nhồi thêm các bit
Số bit nhồi thêm phải nằm trong khoảng 1-512
Phần thêm vào cuối dữ liệu gồm 1 bit 1 và theo sau là các bit
0
Bước 2: Thêm độ dài
Độ dài khối dữ liệu ban đầu sẽ được biểu diễn dưới dạng nhị
phân 64 bít và được thêm cuối chuỗi nhị phân mà ta thu được ở
bước 1.
Độ dài được biểu diễn dưới dạng nhị phân 64 bit. Nếu độ dài
của khối dữ liệu ban đầu >264 chỉ 64bit thấp được áp dụng,
nghĩa là giá trị được thêm vào bằng K mod 264.
Kết quả thu được từ 2 bước là một khối dữ liệu có độ dài là bội
số của 512. ( Với cứ 512 bit là một khối dữ liệu)
Bước 3: Khởi tạo bộ đệm MD ( MD buffer)
Tạo 1 bộ đệm 128 bit gồm 4 thanh ghi mỗi thanh 32 bit được dùng
lưu trữ giá trị băm trung gian và kết quả. 4 thanh ghi của bộ đệm
được đặt tên là A, B,C,D với các giá trị khởi tạo ở dạng littleendian(byte có trọng số nhỏ nhất trong từ nằm ở địa chỉ thấp nhất)
như sau:
Bước 4: Xử lý các khối dữ liệu 512 bit
•Trọng tâm của giải thuật là hàm
nén(compression function)gồm 4 vòng xử
lý. Các vòng này có cấu trúc giống nhau
nhưng sử dụng các hàm luận lý khác nhau
gồm F,G,H,I
•Mảng 64 phần tử được tính theo công
thức : S[i]=232 x abs(sin(i)), được tính
theo radian.
•Kết quả của 4 vòng được cộng theo công
thức modulo 232 với đầu vào CVq để tạo
CVq+1
Hàm nén (compression function)
Bước 5: Xuất kết quả
Kết quả ra là đoạn mã có độ dài 128bit, được thu gọn từ
thông điệp ban đầu có độ dài l bit. Đoạn mã này thu được từ
4 thanh ghi A,B,C,D bắt đầu từ bit thấp của thanh ghi A cho
đến byte cao của thanh ghi D
Tổng kết
Ưu điểm
Có nhiều ứng dụng quan
trọng trong việc đảm bảo
an toàn và bảo mật hệ
thống thông tin.
Được sử dụng rộng rãi
hiện nay.
Nhược điểm
Kể từ năm 2005, các hàm
mật mã của hash đã không
còn đảm bảo được tính
bảo mật tuyệt đối nữa.
AN TOÀN BẢO MẬT HỆ THỐNG THÔNG TIN
ĐỀ TÀI: TÌM HIỂU HÀM BĂM ( HASH FUNCTION)
