Giáo trình Bảo mật thông tin: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

Tiếp nội dung phần 1, Giáo trình Bảo mật thông tin: Phần 2 cung cấp cho người học những kiến thức như: Các hệ mật mã khoá công khai; Chữ ký điện tử hàm hash và phân phối khoá. Mời các bạn cùng tham khảo để nắm chi tiết nội dung giáo trình!
Nội dung trích xuất từ tài liệu:
Giáo trình Bảo mật thông tin: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định Giáo trình Bảo mật thông tin CHƢƠNG 4: CÁC HỆ MẬT MÃ KHOÁ CÔNG KHAI 4.1. Giới thiệu về mật mã khoá công khai Trong mô hình mật mã cổ điển Alice (ngƣời gửi) và Bob (ngƣời nhận) chọn một cách bí mật khoá K. Sau đó dùng K để tạo luật mã hoá ekvà luật giải mã dk. Trong hệ mật này dk hoặc giống nhƣ ek hoặc dễ dàng tính đƣợc từ ek. Các hệ mật thuộc loại này đƣợc gọi là hệ mật khoá bí mật, nếu để lộ ek thì làm cho hệ thống mất an toàn. Nhƣợc điểm của hệ mật này là nó yêu cầu phải có thông tin về khoá K giữa Alice và Bob qua một kênh an toàn trƣớc khi gửi một bản mã bất kỳ. Trên thực tế điều này rất khó đảm bảo. Chẳng hạn khi Alice và Bob ở cách xa nhau và họ chỉ có thể liên lạc với nhau bằng thƣ tín điện tử (Email). Trong tình huống đó Alice và Bob không thể tạo một kênh bảo mật với giá phải chăng. Ý tƣởng xây dựng một hệ mật khoá công khai (hay khoá dùng chung) là tìm một hệ mật không có khả năng tính toán để xác định dk khi biết ek. Nếu thực hiện đƣợc nhƣ vậy thì quy tắc mã ek có thể đƣợc công khai bằng cách công bố nó trong một danh bạ (bởi vậy nên có thuật ngữ hệ mật khoá công khai). Ƣu điểm của hệ mật khoá công khai là ở chỗ Alice (hoặc bất kì một ai) có thể gửi một bản tin đã mã cho Bob (mà không cần thông tin trƣớc về khoá mật) bằng cách dùng luật mã công khai ek. Ngƣời nhận sẽ là ngƣời duy nhất có thể giải đƣợc bản mã này bằng cách sử dụng luật giải mã bí mật dk của mình. Có thể hình dung hệ mật này tƣơng tự nhƣ sau: Bob tạo hai khóa lập mã Kd và giải mã Ke rồi gửi khóa lập mã cho Alice, Alice dùng khóa lập mã của Bob để mã hóa sau đó gửi bản tin đã mã cho Bob. Bob dùng khóa bí mật của mình để giải mã bản tin nhận đƣợc. Ý tƣởng về một hệ mật khoá công khai đã đƣợc Diffie và Hellman đƣa ra vào năm 1976. Việc hiện thực hoá nó do Rivesrt, Shamir và Adleman đƣa ra đầu tiên vào năm 1977, họ đã tạo nên hệ mật nổi tiếng RSA. Kể từ đó một số hệ mật đƣợc công bố, độ mật của chúng dựa trên các bài toán tính toán khác nhau. 89 Giáo trình Bảo mật thông tin 4.1.1. Một số bài toán cơ bản Phần này giới thiệu một số bài toán số học đƣợc sử dụng khi xây dựng các hệ mật mã khoá công khai Bài toán phân tích số nguyên (thành thừa số nguyên tố): Cho số nguyên dƣơng n , tìm tất cả các ƣớc số nguyên tố của nó, hay là tìm dạng phân tích chính tắc của n = p1 . p2 ... pk , trong đó pi là các số nguyên tố từng cặp 1 2 k khác nhau và các i  1. Bài toán này có liên hệ mật thiết với các bài toán thử tính nguyên tố hay thử tính hợp số của một số nguyên. Trong lý thuyết mật mã, bài toán này thƣờng đƣợc sử dụng với các dữ liệu n là số nguyên Blum, tức các số nguyên dƣơng có dạng tích của hai số nguyên tố lớn nào đó. Bài toán RSA (Rivest-Shamir-Adleman) : Cho số nguyên dƣơng n là tích của hai số nguyên tố lẻ khác nhau, một số nguyên dƣơng e sao cho gcd(e, (n)) = 1, và một số nguyên c, tìm một số nguyên m sao cho me  c (mod n) . Điều kiện gcd(e, (n)) = 1 bảo đảm với mỗi số nguyên c  0, 1,..., n -1 có đúng một số m  0, 1,..., n -1 sao cho me  c (mod n) Nếu biết hai thừa số nguyên tố của n thì sẽ tính đƣợc (n) = (p -1)(q -1). Vì gcd(e, (n)) =1 nên tính đƣợc d = e -1mod (n), do đó sẽ tìm đƣợc m = c d modn. Nhƣ vậy, bài toán RSA có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Bài toán thặng dƣ bậc hai : Cho một số nguyên lẻ n là hợp số, và một số nguyên a Jn ( tập tất cả các số a có ký hiệu Jacobi J(a,n) =1). Hãy quyết định xem a có là thặng dƣ bậc hai theo mod n hay không? Trong lý thuyết mật mã, bài toán này cũng thƣờng đƣợc xét với trƣờng hợp n là số nguyên Blum. Khi đó nếu a Jn , thì a là thặng dƣ bậc hai theo modn khi và chỉ khi J(a,n) =1, điều kiện này có thể thử đƣợc vì nó tƣơng đƣơng với điều kiện a (p -1)/2  1 (modp). Nhƣ vậy, trong trƣờng hợp này, bài toán thặng dƣ bậc hai có thể qui dẫn trong 90 Giáo trình Bảo mật thông tin thời gian đa thức về bài toán phân tích số nguyên. Mặt khác, nếu không biết cách phân tích n thành thừa số nguyên tố thì cho đến nay, không có cách nào giải đƣợc bài toán thặng dƣ bậc hai trong thời gian đa thức. Bài toán tìm căn bậc hai mod n : Cho một số nguyên lẻ n là hợp số Blum, và một số a Qn (tập các thặng dƣ bậc hai theo modn). Hãy tìm một căn bậc hai của a theo modn, nghĩa tìm x sao cho x 2  a (modn). Nếu biết phân tích n thành thừa số nguyên tố n =p*q, thì bằng cách giải các phƣơng trình x 2  a theo các modp và modq, rồi sau đó kết hợp các nghiệm của chúng lại theo định lý số dƣ China sẽ đƣợc nghiệm theo modn, tức là căn bậc hai của a theo modn cần tìm. Vì mỗi phƣơng trình x 2  a theo modp và modq có hai nghiệm (tƣơng ứng theo modp và modq ), nên kết hợp lại thu đƣợc bốn nghiệm, tức bốn căn bậc hai của a theo modn. Ngƣời ta đã tìm đƣợc một số thuật toán tƣơng đối đơn giản (trong thời gian đa thức) giải phƣơng trình x 2  a (modp) với p là số nguyên tố. Nhƣ vậy, bài toán tìm căn bậc hai modn có thể qui dẫn trong thời gian đa thức về bài toán phân tích số nguyên. Ngƣợc lại, nếu có thuật toán  giải bài toán tìm căn bậc hai modn thì cũng có thể xây dựng một thuật toán giải bài toán phân tích số nguyên nhƣ sau: Chọn ngẫu nhiên một số x với gcd(x,n) =1, và tính a = x2modn. Dùng thuật toán  cho a để tìm một căn bậc hai modn của a. Gọi căn bậc hai tìm đƣợc đó là y. Nếu y  x (modn), thì phép thử thất bại, ta phải chọn tiếp một số x khác, nếu y ≢ x (modn) thì gcd(x-y, n) là một ƣớc số không tầm thƣờng của n, cụ thể là p hay là q. Vì n có 4 căn bậc hai modn nên xác suất của thành công ở mỗi lần thử là 1/2, do đó số tru ...