Bài giảng Mật mã ứng dụng: Hệ mật RSA - Đại học Bách khoa Hà Nội

Bài giảng "Mật mã ứng dụng: Hệ mật RSA" trình bày các nội dung chính sau đây: Mật mã khóa công khai; Xây dựng hệ mật mã khóa công khai dựa trên hàm cửa sập; Hệ mật mã RSA. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Mật mã ứng dụng: Hệ mật RSA - Đại học Bách khoa Hà NộiMật mã khóa công khai Hệ mật RSANội dung• Mật mã khóa công khai• Xây dựng hệ mật mã khóa công khai dựa trên hàm cửa sập• Hệ mật mã RSAMật mã khóa công khaiBob: sinh cặp khóa (pk, sk) và đưa pk cho Alice Alice Bob m c c m E D pk sk Ứng dụngThiết lập khóa phiên Alice pk Bob Sinh khóa (pk, sk) chọn x ngẫu nhiên E(pk, x) (VD. 48 bytes) xỨng dụng không cần tương tác: (VD. Email)• Bob gửi email được mã hóa với pkalice cho Alice• Chú ý: Bob cần biết pkalice (quản lý khóa công khai)Nội dung• Mật mã khóa công khai• Xây dựng hệ mật mã khóa công khai dựa trên hàm cửa sập• Hệ mật mã RSA Mã hóa khóa công khaiĐN: một hệ mật mã khóa công khai là bộ ba thuật toán (G, E, D)• G(): thuật toán ngẫu nhiên output cặp khóa (pk, sk)• E(pk, m): thuật toán ngẫu nhiên nhận m∈M và output c ∈C• D(sk,c): thuật toán đơn định nhận c∈C và outputs m∈M hoặc ⊥Tính đúng đắn: ∀(pk, sk) được sinh bởi G : ∀m∈M: D(sk, E(pk, m) ) = m Hàm cửa sập (Trapdoor functions - TDF)ĐN: hàm cửa sập X⟶Y là bộ ba thuật toán hiệu quả (G, F, F-1)• G(): thuật toán ngẫu nhiên output cặp khóa (pk, sk)• F(pk,⋅): thuật toán đơn định định nghĩa một hàm X ⟶ Y• F-1(sk,⋅): hàm từ Y ⟶ X tính nghịch đảo F(pk,⋅) Cụ thể: ∀(pk, sk) sinh bởi hàm G ∀x∈X: F-1(sk, F(pk, x) ) = xHàm cửa sập an toàn(G, F, F-1) là an toàn nếu F(pk, ⋅) là hàm “một chiều” : có thể tính xuôi, nhưng không thể tính nghịch đảo mà khôngcó sk Chal. Adv. A (pk,sk)¬G() R x⟵X pk, y ¬ F(pk, x) x’ĐN: (G, F, F-1) là TDF an toàn nếu với mọi thuật toán hiệu quả A: AdvOW [A,F] = Pr[ x = x’ ] < “cực nhỏ” Xây dựng hệ mật khóa công khai từ TDFs• (G, F, F-1): TDF an toàn X ⟶ Y• (Es, Ds) : hệ mật mã khóa đối xứng an toàn trên (K,M,C)• H: X ⟶ K: hàm bămTa xây dựng hệ mật khóa công khai (G, E, D): Sinh khóa G: giống như G cho TDF Hệ mật mã khóa công khai từ TDFs• (G, F, F-1): TDF an toàn X ⟶ Y• (Es, Ds) : hệ mã hóa đối xứng an toàn trên (K,M,C)• H: X ⟶ K: hàm băm E( pk, m) : D( sk, (y,c) ) : x ⟵ X, R y ⟵ F(pk, x) x ⟵ F-1(sk, y), k ⟵ H(x), c ⟵ Es(k, k ⟵ H(x), m ⟵ Ds(k, m) c) output (y, c) output mSử dụng không đúng hàm Cửa sập (TDF) Không mã hóa bằng cách áp dụng F để mã hóa bản rõ: E( pk, m) : D( sk, c ) : output c ⟵ F(pk, m) output F-1(sk, c) Vấn đề: • Đây là hệ mã đơn định: không an toàn ! • Tồn tại nhiều cách tấn côngNội dung• Mật mã khóa công khai• Xây dựng hệ mật mã khóa công khai từ hàm cửa sập• Hệ mật mã RSA Nhắc lại: Số học modun hợp sốXét N = p×q với p,q là các số nguyên tố ZN = {0,1,2,…,N-1} ; (ZN)* = {các phần tử khả nghịch trongZN}Bổ đề: x Î ZN là khả nghịch Û gcd(x,N) = 1 • Số các phần tử của (ZN)* là j(N) = (p-1)(q-1) = N-p-q+1 • Định lý Euler: xÎ (ZN)* : xj(N) = 1 Hoán vị cửa sập RSA Ronald Rivest, Adi Shamir, và Leonard AdlemanCông bố: Scientific American, 8/1977.Được sử dụng rộng rãi trong:• SSL/TLS: chứng thư số và trao đổi khóa• e-mail và hệ thống file an toàn … và nhiều hệ thống khác Hoán vị cửa sập RSAG(): chọn hai số nguyên tố p,q »1024 bits. Đặt N=pq. chọn các số nguyên e , d thoả mãn e⋅d = 1 (modj(N) ) output pk = (N, e) , sk = (N, d)F( pk, x ): ; RSA(x) = xe (in ZN) kj(N)+1 j(N) kF-1( sk, y) = yd ; yd = RSA(x) d ed = x = x = (x ) ×x = xGiả sử RSAGiả sử RSA: RSA là hoán vị “một chiều” Với mọi kẻ tấn công (thuật toán hiệu quả) A: [ Pr A(N,e,y) = y 1/e ] < “cực nhỏ” R ở đó p,q ¬ số nguyên tố n-bit, N¬pq, y¬ZN* RNhắc lại: Hệ mật mã RSA (chuẩn ISO)(Es, Ds): hệ mật mã đối xứng an toàn.H: ZN ® K với K là không gian khóa của (Es,Ds)• G(): sinh tham số RSA : pk = (N,e), sk = (N,d)• E(pk, m): (1) chọn số ngẫu nhiên x thuộc ZN (2) y ¬ RSA(x) = xe , k ¬ H(x) (3) output (y , E ...