Mã hóa

10.*Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Chương 6Mã hóa Cryptography10.*Objectives Phân biệt mã hóa đối xứng và mã hóa bất đối xứng Giới thiệu về hàm một chiều trong mã hóa bất đối xứng Mã hóa RSAChapter 1010.*10-1 INTRODUCTIONMã hóa đối xứng và mã hóa bất đối xứng là hai cách tiếp cận cùng tồn tại song song trong lĩnh vực mã hóaMã hóa đối xứng: cùng chia sẻ bí mậtví dụ mật mã Caesar k=3 ABCDEFZ DEFGHIC Mã hóa bất đối xứng: bí mật cá nhânMã hóa: khóa công khaiGiải mã: khóa bí mật10.*Mã hóa bất đối xứng dùng hai khóa:Một khóa công khai (public key)Một khóa bí mật (private key)10.1.1 KeysFigure 10.1 khóa và mở khóa trong hệ mã bất đối xứng10.*10.1.2 General IdeaFigure 10.2 ý tưởng chính của hệ mã bất đối xứng10.*Bản rõ và bản mã (Plaintext/Ciphertext)Bản rõ (P) là bản chưa mã hóaBản mã (C) là bản đã mã hóa10.1.2 ContinuedC = f (Kpublic , P) P = g(Kprivate , C) Mã hóa và giải mã (Encryption/Decryption) trong hệ mã bất đối xứng dùng hai hàm và hai khóa riêng biệt 10.*Hệ mã bất đối xứng dùng hàm bẫy một chiều (trapdoor one-way function).10.1.4 Trapdoor One-Way FunctionHàm Figure 10.3 hàm là một qui tắc ánh xạ một miền xác định vào một miền giá trị 10.*Hàm bẫy một chiều (Trapdoor One-Way Function (TOWF))10.1.4 ContinuedHàm một chiều (One-Way Function (OWF))1. f dễ dàng tính được. 2. f −1 tính cực kỳ khó (không thể tính được). 3. Cho y và một cái bẫy thì x tính được dễ dàng10.*10.1.4 ContinuedVí dụ 10. 1Ví dụ 10. 2Khi n đủ lớn, n = p × q là hàm một chiều. Cho p và q , tính n dễ dàng;Cho n, rất khó để tính được p và q.Khi n đủ lớn, y = xk mod n là một hàm bẫy 1 chiều. Cho x, k và n, dễ dàng tính y.Cho y, k và n, rất khó tính x. Tuy nhiên nếu biết cái bẫy k′ sao cho k × k ′ = 1 mod f(n)Ta tính được x dễ dàng x = yk′ mod n. 10.*10-2 RSA CRYPTOSYSTEMHệ mã RSARSA lấy tên của những người phát minh (Rivest, Shamir, and Adleman).10.2.1 Introduction10.2.2 Procedure10.2.3 Some Trivial Examples10.2.4 Attacks on RSA10.2.5 Recommendations10.2.6 Optimal Asymmetric Encryption Padding (OAEP)10.2.7 ApplicationsTopics discussed in this section:10.*10.2.1 Giới thiệuFigure 10.5 độ phức tạp trong thuật toán RSA10.*10.2.2 Qui trìnhFigure 10.6 mã hóa, giải mã và sinh khóa trong RSA10.*10.2.2 Sinh khóa RSA10.*Mã hóa (Encryption)10.2.2 Continued10.*Giải mã (Decryption)10.2.2 Continued10.*Proof of RSA10.2.2 Continued10.*10.2.3 ví dụ đơn giảnVí dụ 10. 5Bob chọn p=7 và q=11, tính được n = pxq = 77. Tính f(n) = (7 − 1)(11 − 1) = 60. Bob chọn e và d trong Z60∗ sao cho ed = 1 mod 60.(ví dụ e = 13, d = 37) Bob công bố khóa công khai (13,77) giữ bí mật d = 37Alice muốn gởi P= 5 tới Bob. Cô ta dùng e=13 để mã hóa 5.Bob nhận C=26 từ AliceBob dùng d = 37 để giải mã: ví dụ đơn giản (tt)Ví dụ 10. 6Bob nhận được C = 28 và dùng khóa bí mật d = 37 để giải mã:Giả sử John muốn gởi nội dung P=63 cho Bob.John dùng khóa công khai của Bob đã công bố (13,77)10.*10.2.3 ví dụ cách áp dụngExample 10. 7Ted muốn gởi thông báo “NO” cho Jennifer. Anh ta đổi kí tự ra số Ví dụ ABC..Z đổi thành số 025  NO=1314. Vậy xem như là số P=1314Jennifer chọn p = 397 và q = 401. Cô ta tính được n = 159197 và f(n) = 158400Cô ta chọn e = 343 và tính d = 12007. Jennifer công bố (343,159197) là khóa công khaiGiữ bí mật d=1200710.*10.2.3 ContinuedFigure 10.7 mã hóa và giải mã trong ví dụ 10.*10.2.6 ví dụ áp dụng thuậtExample 10. 8Giả sử ta chọn p và q là hai số 512-bit Tính n và f(n), Chọn e và kiểm tra nguyên tố cùng nhau với f(n). Tính d. Dùng khóa công khai (e,n) để mã hóa Dùng khóa bí mật (d,n) để giải mã.10.*10.2.6 ví dụ áp dụng thật (tt)Ví dụ 10. 8 (tt)n = p × q, n có 309 số.f(n) = (p − 1)(q − 1) có 309 số.10.*10.2.6 ví dụ áp dụng thật (tt)Ví dụ (tt)Bob chọn e = 35535 và kiểm tra tính nguyên tố cùng nhau với f(n). Tính d.10.*10.2.6 ví dụ áp dụng thật (tt)Ví dụ 10. 8 (tt)Alice muốn gởi “THIS IS A TEST”, và đổi thành số với bảng mã 00−26.Alice mã hóa C = Pe, đó là:10.*10.2.6 ví dụ áp dụng thật (tt)Ví dụ 10. 8 (tt)Bob nhận được C và giải mã P = Cd, đó làĐổi ngược lại thành “THIS IS A TEST” với bảng mã 00-26 tương ứng với A..Z.