Đề tài Thuật toán Băm, mã hóa Sha-1, Sha-2

Trường Đại học Dân lập Duy TânKhoa Công nghệ thông tin Giáo viên: Nguyễn Minh Nhật Sinh viên: - Nguyễn Thị Hồng - Nguyễn Trung Thành - Võ Nguyễn Đức Dũng MỤC ĐÍCH CỦA VIỆC MÃ HÓA DỮ LIỆU  Dữ liệu bị đọc trộm Dữ liệu bị thay đổi Mạo danh để xâm nhập => Dữ liệu cần được mã hóa để bảo vệ tính toàn vẹn. CÁC PHƯƠNG THỨC MÃ HÓA DỮ LIỆU Mã hóa đối xứng (Symmetric) Mã hóa bất đối xứng (Asymmetric) Băm (Hash) Bảng băm là cấu trúc dữ liệu thay vì truy cập bằng chỉ số thì truy cập bằng khóa với tốc độ truy cập phần tử rất nhanh (thời gian truy cập là hằng số), thông qua hàm tính địa chỉ gọi là hàm băm. 1. Định nghĩa: BẢNG BĂM HÀM BĂM Hàm băm là hàm biến đổi giá trị khoá (số, chuỗi..) thành địa chỉ, chỉ mục trong bảng băm 1. Định nghĩa: KHÓA HÀM BĂM HÀM BĂM DANH SÁCH LIÊN KẾT Hàm băm dạng bảng tra Hàm băm dùng phương pháp chia Hàm băm dùng phương pháp nhân Phương Pháp xây dựng bảng băm HÀM BĂM Hàm băm dạng bảng tra HÀM BĂM Hàm băm dùng phương pháp chia: h(k) = k mod m Nếu chọn m= 2n , sẽ dùng n bits thấp của k làm địa chỉ Nếu chọn m= 10n ,sẽ dùng n số cuối của k làm địa chỉ  chọn m là nguyên tố gần với 2n hoặc 10n HÀM BĂM Tập khoá là các giá trị số gồm 3 chữ số, vùng nhớ cho bảng địa chỉ có khoảng 100 mục Vd: 325 Mod 100 = 25, 125 Mod 100 = 25... HÀM BĂM Hàm băm dùng phương pháp chia: Hàm băm dùng phương pháp nhân h(k) = floor(m (k A mod 1)) Vấn đề chọn m và A Chọn m = 2n Theo Knuth A = 1/2(sqrt(5) -1)  0.618033987 HÀM BĂM Tập khoá là các giá trị số gồm 3 chữ số, vùng nhớ cho bảng địa chỉ có khoảng 100 mục, A=0.61803 Tính địa chỉ cho khóa 325 h(325) = floor(100 (325*0.61803 mod 1))=86 HÀM BĂM Hàm băm dùng phương pháp nhân Dễ dàng tính giá trị băm với bất kỳ thông điệp cho trước nào. Không thể tìm được một thông điệp từ một giá trị băm cho trước. Không thể sửa được một thông điệp mà không làm thay đổi giá trị băm của nó. Không thể tìm ra 2 thông điệp khác nhau mà có cùng giá trị băm. Tính chất : HÀM BĂM Khởi tạo (Initialize) Kiểm tra rỗng (Empty) Lấy kích thước của bảng băm (Size) Tìm kiếm (Search) Thêm mới phần tử (Insert) Loại bỏ (Remove) Sao chép (Copy) Duyệt (Traverse) CÁC THAO TÁC TRÊN HÀM BĂM: HÀM BĂM TIÊU CHUẨN ĐÁNH GIÁ BẢNG BĂM Tính toán nhanh. Các khoá được phân bố đều trong bảng. Ít xảy ra đụng độ . Xử lý được các loại khóa có kiểu dữ liệu khác nhau HÀM BĂM THUẬT TOÁN BĂM AN TOÀN SHA SHA (Secure Hash Algorithm) là các thuật giải dùng để chuyển một đoạn dữ liệu nhất định thành một đoạn dữ liệu có chiều dài không đổi với xác suất khác biệt cao. Việc tìm lại được đoạn dữ liệu gốc là không khả thi. Việc tìm được hai đoạn dữ liệu nhất định có cùng kết quả băm là không khả thi. Bất cứ thay đổi nào trên đoạn dữ liệu gốc, dù nhỏ, cũng sẽ tạo nên một giá trị băm hoàn toàn khác với xác suất rất cao THUẬT TOÁN BĂM AN TOÀN SHA * SHA-1: Trả lại kết quả 160 bit giá trị băm SHA1("The quick brown fox jumps over the lazy dog") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 Sửa d thành c: SHA1("The quick brown fox jumps over the lazy cog") de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3 SHA-256 SHA256("The quick brown fox jumps over the lazy dog") = d7a8fbb3 07d78094 69ca9abc b0082e4f 8d5651e4 6d3cdb76 2d02d0bf 37c9e592 SHA256("The quick brown fox jumps over the lazy cog") = e4c4d8f3 bf76b692 de791a17 3e053211 50f7a345 b46484fe 427f6acc 7ecc81be THUẬT TOÁN BĂM AN TOÀN SHA * SHA-2: SHA-224, SHA-256, SHA-348, SHA-512 ƯU ĐIỂM CỦA CÁC HÀM BĂM Bảng băm là một cấu trúc dung hòa giữa thời gian truy xuất và dung lượng bộ nhớ: - Nếu không có sự giới hạn về bộ nhớ: có thể xây dựng bảng băm với mỗi khóa ứng với một địa chỉ với mong muốn thời gian truy xuất tức thời. Nếu dung lượng bộ nhớ có giới hạn: tổ chức một số khóa có cùng địa chỉ, tốc độ truy xuất giảm. Các phép toán trên bảng băm hạn chế số lần so sánh, giảm được thời gian truy xuất. ỨNG DỤNG CỦA HÀM BĂM Tạo ra hệ thống tin cậy trong máy tính Kiểm tra tính toàn vẹn của thông điệp Chữ ký số (Digital Signatures) Mã xác thực thông điệp (MACs – Message Authentication Codes) Xác thực mật khẩu Một số dạng xác thực khác (nhận dạng tập tin trên mạng chia sẻ P2P) SÁNH HÀM VỚI CÁC HÀM BĂM KHÁC