lOMoARcPSD|18946110 Ch06 ATTT Ham Bam Chu Ky Dien Tu nguyên lí kế toán (Trường Đại học Công nghiệp Thành phố Hồ Chí Minh) Studocu is not sponsored or endorsed by any college or university Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Chương 6: HÀM BĂM – CHỮ KÝ SỐ (Hash Function - DIGITAL SIGNATURES) Bộ môn Hệ thống thông tin 1 Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 HÀM BĂM (Hash Function) 2 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Nhu cầu toàn vẹn thông tin Các ứng dụng chú trọng mục tiêu Toàn vẹn Tài liệu được sử dụng giống hệt tài liệu lưu trữ Các thông điệp trao đổi trong một hệ thống an toàn không bị thay đổi/sửa chữa “Niêm phong” tài liệu/thông điệp “Niêm phong” không bị sửa đổi/phá hủy đồng nghĩa với tài liệu/thông điệp toàn vẹn “Niêm phong”: băm (hash), tóm lược (message digest), đặc số kiểm tra (checksum) Tạo ra “niêm phong”: hàm băm 3 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Hàm băm Mục tiêu an toàn Toàn vẹn (Integrity) 4 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail. Hàm băm (Hash Function) 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ụ 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.
5 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail. Hàm băm (Hash Function) Input: M có kích thước bất kỳ Output – giá trị h có kích thước cố định, ngắn. H(x) – hàm một chiều (“Khó để tính nghịch đảo”) 6 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail. Hàm băm (Hash Function) 7 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.
Hàm băm (Hash Function) x1 x2 Thông điệp y1 x3 Thông điệp rút gọn y2 Không gian thông điệp Không gian8 giá trị băm Không gian giá trị Băm nhỏ hơn rất nhiều so với Không gian thông điệp về mặt kích thước chắc chắn sẽ tồn tại đụng độ (trùng), nghĩa là có hai tin x và x” mà giá trị Băm của chúng là giống nhau, tức là h(x) = h(x”) Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Tính chất hàm băm 1. Tính chống tiền ảnh (Preimage resistant – one-way property): Cho trước giá trị băm h việc tìm x sao cho H(x)=h là rất khó 2. Tính chống tiền ảnh thứ hai (Second preimage resistant – weak collision resistant – Tính chống trùng yếu): Cho thông điệp đầu vào x, việc tìm một thông điệp x’ với (x’ x) sao cho h(x’)=h(x) là rất khó 3. Tính chống trùng mạnh (Strong Collision resistant): Không thể tính toán để tìm được hai thông điệp đầu vào x1 x2 sao cho chúng có cùng giá trị băm (Nghịch lý ngày sinh – Birthday paradox) 9 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Nghịch lý ngày sinh (birthday paradox) Bài toán 1: Giả sử trong phòng có M sinh viên.
Vậy xác suất để có hai SV có cùng ngày sinh là bao nhiêu phần trăm? (1 năm 365 ngày khác nhau) Theo nguyên lý chuồng bồ câu Dirichlet: cần có 365+1 = 366 người để tìm thấy 2 người có cùng ngày sinh với xác suất 100%. Vì vậy với 30 người thì xác xuất này rất nhỏ. Rất nhỏ, đúng không Tính theo xác suất thống kê toán học thì M(M-1) >=2 x 365 x loge2 (*) chỉ cần 23 người là đủ để xác suất hơn 50%. Vì vậy bài toán này gọi là nghịch lý ngày sinh 10 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Nghịch lý ngày sinh (birthday paradox) Điều này muốn nói lên rằng, trong nhiều trường hợp xác suất để hai mẩu tin có cùng bản Hash là không nhỏ như chúng ta nghĩ.
Tính chống trùng mạnh 11 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Nghịch lý ngày sinh (birthday paradox) Bài toán 2: Giả sử bạn đang ở trong một lớp học với M sinh viên. Hỏi M tối thiểu là bao nhiêu để tồn tại một bạn khác có cùng ngày sinh với bạn với xác suất (XS) lớn hơn 50%? XS để 1 người khác ngày sinh với bạn là 364/365. XS để M người đều khác ngày sinh với bạn là (364/365)M. XS để tồn tại ít nhất một người có cùng ngày sinh với bạn là: 1-(364/365)M Để XS này >50% M>=253 người Tính chống trùng yếu 12 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Nghịch lý ngày sinh (birthday paradox) 13 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Nghịch lý ngày sinh (birthday paradox) Để tìm ra hai thông điệp có cùng giá trị băm (vét cạn) thì phải thử bao nhiêu thông điệp khác nhau? Phải thử khoảng 2n/2 thông điệp khác nhau (xác suất > 50%) Ví dụ: Nếu n=128 thì phải thử 264 thông điệp (khá lớn), nghĩa là hàm hăm đạt được tính chống trùng mạnh (tương được tấn công vét cạn khóa của DES) 14 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.
Ứng dụng hàm băm Chứng thực thông điệp (Message Authentication) Chữ ký số (Digital Signatures) Các ứng dụng khác (Other Applications) 15 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.1 Message Authentication Là một cơ chế/dịch vụ được dùng để kiểm tra tính toàn vẹn của một thông điệp. Đảm bảo rằng dữ liệu nhận được là chính xác như khi được gửi (không bị chỉnh sửa, chèn, hoặc thay thế) Trong nhiều trường hợp, có một yêu cầu là cơ chế chứng thực phải hỗ trợ nhận dạng người gửi (sender) là hợp pháp. Hàm băm dạng này, giá trị băm (h) được gọi là tóm tắt thông điệp hoặc cốt thông điệp (message digest) 16 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.1 Message Authentication Ví dụ cơ chế chứng thực đơn giản 17 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.1 Message Authentication Ví dụ cơ chế chứng thực đơn giản (tt) 18 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.2 Digital Signatures Giá trị băm của thông điệp được mã hóa bằng private key của user, bất kỳ ai biết public key của user thì có thể thẩm tra thông điệp mà được gắn kết với chữ ký số. Kẻ tấn công muốn hiệu chỉnh thông điệp thì sẽ cần phải biết private key của user.
19 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.2 Digital Signatures Ví dụ: 20 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.3 Other Applications Dùng lưu trữ mật khẩu (băm password): Hàm băm được dùng để tạo one-way password file, trong cơ chế này giá trị băm của password được lưu, điều này tốt hơn là lưu chính bản rõ password. password không bị truy xuất bởi kẻ tấn công nơi chứa password. Khi user nhập vào một password, thì giá trị băm của password được so với giá trị băm được lưu để kiểm tra. 21 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.3 Other Applications Dùng nhận diện xâm hại (intrusion detection) và nhận diện virus (virus detection).
Tính, lưu và bảo mật giá trị băm H(F) của các tập tin trong hệ thống (thể lưu trên CD-R) Kẻ xâm hại cần phải hiệu chỉnh F mà không thay đổi H(F) 22 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.3 Other Applications Dùng: Xây dựng hàm ngẫu nhiên giả (pseudorandom function - PRF) hoặc Phát sinh số ngẫu nhiên giả (pseudorandom number generator - PRNG) 23 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 SHA-1 SHA = Secure Hash Algorithm Được đề xuất và bảo trợ bởi NIST Dùng trong hệ DSS (Digital Signature Standard) của NIST Được sử dụng rộng rãi SSL, PGP, SSH, S/MIME, IPSec Đầu vào bội số của 512 bit Giá trị băm 160 bit 80 vòng lặp tính toán 24 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 MD5 MD = Message Digest MD5 được đề xuất bởi Rivest vào năm 1991 Được sử dụng rộng rãi Truyền tập tin Lưu trữ mật khẩu 25 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 CHỮ KÝ SỐ (DIGITAL SIGNATURES) GV: Nguyễn Thị Hạnh 26 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Nội dung chính 1. Khái niệm về chữ ký số (Digital Signature) 2. Các dịch vụ bảo mật cung cấp bởi chữ ký số 3. Một vài chữ ký số thông dụng 4.
Mô tả vài áp dụng thực tế của chữ ký số (Cryptography & Network Security. McGraw-Hill, Inc., Chapter 13) 27 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail. Khái niệm về chữ ký số 1976, Diffie & Hellman lần đầu tiên đề cập đến khái niệm Chữ ký số là một trong ứng dụng quan trọng nhất của mã hóa khóa công khai. 1989, phiên bản thương mại Chữ ký số đầu tiên trong Lotus Notes, dựa trên RSA Ứng dụng: Hợp đồng số Bầu cử điện tử Giao dịch ngân hàng ….
28 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail. Khái niệm về chữ ký số Mục tiêu: Xác thực (Authentication) Chống phủ nhận (Non-repudiation) Chữ ký số không những giúp xác thực thông điệp mà còn bảo vệ mỗi bên khỏi bên kia. 29 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail. Khái niệm về chữ ký số Chữ ký số được xây dựng dựa trên mật mã khóa công khai.
Nhằm bảo đảm vấn đề toàn vẹn dữ liệu, và chống sự chối bỏ trách nhiệm khi đã ký. Chữ ký điện tử và chữ ký tay đều có chung đặc điểm là rất khó có thể tìm được hai người có cùng một chữ ký. Chữ ký điện tử được người ký tạo ra bằng Khoá riêng và phần có đặc tính duy nhất của văn bản được ký.” 30 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Quy trình sử dụng chữ ký số Người gửi dùng một thuật toán tạo chữ ký (signing algorithm) để ký thông điệp. Thông điệp và chữ ký được gửi cho người nhận.
Người nhận dùng thuận toán thẩm tra chữ ký (Verifying algorithm) để thẩm tra. Nếu đúng, thông điệp được chấp nhận, ngược lại sẽ từ chối thông điệp 31 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.com) lOMoARcPSD|18946110 Quy trình sử dụng chữ ký số 32 Bộ môn Hệ thống thông tin Downloaded by Trang Nguy?n (trangtrang1102001@gmail.