›
›

Mã khóa công khai

ppt 122 trang phuongnguyen 6780
Download
Bạn đang xem 20 trang mẫu của tài liệu "Mã khóa công khai", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptma_khoa_cong_khai.ppt

Nội dung text: Mã khóa công khai

  1. MÃ KHÓA CÔNG KHAI MÃ KHÓA CÔNG KHAI HỆ MÃ RSA VÀ RABIN
  2. NHÓM 9 GiỚI THIỆU VỀ MÃ KHÓA CÔNG KHAI HỆ MÃ KHÓA RSA HỆ MÃ KHÓA RABIN 2 Designed by group 9
  3. NỘI DUNG CHÍNH NHÓM 1: ➢ Giới thiệu về mã khóa công khai ➢ So sánh hệ mã công khai với hệ mã bí mật • Cách lập mã • Cách giải mã • Tính bảo mật ➢ Nguyên tắc của hệ mã khóa công khai ➢ Giới thiệu một số hệ mã mới 3 Designed by group 9
  4. NỘI DUNG CHÍNH NHÓM 2: ➢ Giới thiệu về hệ mã RSA ➢ Nguyên tắc sử dụng hệ mã RSA ▪ Giai đoạn chọn khóa. ▪ Giai đoạn mã hóa ▪ Giai đoạn giải mã ➢ Tính chất của hệ mã RSA ▪ Tính khả thi ▪ Tính bảo mật ➢ Phiên bản mở rộng của RSA 4 Designed by group 9
  5. NỘI DUNG CHÍNH NHÓM 3: ➢ Giới thiệu về hệ mã RABIN ➢ Hệ mã hóa RABIN • Sơ đồ hệ mã hóa • Giai đoạn mã hóa • Giai đoạn giải mã ➢ Các đặc trưng của hệ mã RABIN • Tính an toàn của hệ mã • Vấn đề sử dụng dư thừa dữ liệu • Tính hiệu quả của hệ mã. 5 Designed by group 9
  6. NHÓM 1 GIỚI THIỆU VỀ MÃ KHÓA CÔNG KHAI 6 Designed by group 9
  7. NỘI DUNG CHÍNH NHÓM 1: ➢ Giới thiệu về mã khóa công khai ➢ Nguyên tắc của hệ mã khóa công khai ➢ So sánh hệ mã công khai với hệ mã bí mật • Cách lập mã • Cách giải mã • Tính bảo mật ➢ Giới thiệu một số hệ mã khác. 7 Designed by group 9
  8. HỆ MÃ KHÓA CÔNG KHAI 1. Giới thiệu Ta thấy đối với Ceasar, mã khối hay mã mũ thì các khóa lập mã phải được giữ bí mật, nếu khóa lập mã bị lộ thì người ta có thể tìm khóa giải mã trong một thời gian tương đối ngắn. Như vậy nếu trong một hệ thống có nhiều cặp thành viên hoặc nhóm thành viên cần trao đổi thông tin mật với nhau thì số mật mã chung cần giữ bí mật là rất lớn và như thế thì khó có thể đảm bảo được.
  9. HỆ MÃ KHÓA CÔNG KHAI Xuất phát từ nhu cầu thực tế, vào những năm 1970 Diffie và Hellman đã phát minh ra một hệ mã hóa mới được gọi là hệ mã khóa công khai hay hệ mã hóa phi đối xứng.
  10. HỆ MÃ KHÓA CÔNG KHAI Chúng được gọi với tên hệ thống mã khóa công khai bởi vì khóa để mã hóa là công khai, một người bất kỳ có thể sử dụng khóa công khai để mã hóa thông báo, nhưng chỉ có người có khóa giải mã thì mới có khả năng giải mã.
  11. HỆ MÃ KHÓA CÔNG KHAI • Ở đây người ta sử dụng 2 khóa: một khóa cá nhân để giải mã và một khóa công khai để mã hóa, hai khóa này là khác nhau. • Khóa công khai ra đời hỗ trợ thêm để giải quyết một số bài toán an toàn, chứ không phải thay thế khóa bí mật. Cả hai khóa cùng tồn tại, phát triển và bổ sung cho nhau.
  12. SƠ ĐỒ MÃ HÓA CÔNG KHAI Vòng chìa khóa công cộng  Lan  Bình Khóa cá Hoa An nhân của Chìa khóa An công cộng của An   Văn bản đã Văn bản Mã hóa được mã hóa Giải mã Văn bản gốc được gốc được nhập vào xuất ra
  13. NGUYÊN TẮC CỦA HỆ MÃ CÔNG KHAI • Giả sử trong hệ thống có n thành viên cùng trao đổi thông tin với mật nhau. Mỗi thành viên thứ i chọn khóa lập mã K, một công thức mã hóa E được công bố công khai và một khóa cá nhân Dk được giữ bí mật. • Như vậy có n khóa công khai K1, K2, , Kn.
  14. NGUYÊN TẮC CỦA HỆ MÃ CÔNG KHAI • Khi thành viên thứ i muốn gửi thông báo cho thành viên thứ j thì thực hiện theo thứ tự các bước sau: • Số hóa thông báo cần chuyển. • Nhóm thành từng khối với độ dài cho trước. • Mã hóa văn bản bởi công thức Ej của thành viên thứ j (đã thông báo công khai). • Như vậy mỗi khối P được gửi đi dưới dạng khối C= Ej(P,Kj).
  15. NGUYÊN TẮC CỦA HỆ MÃ CÔNG KHAI • Để giải mã thông báo này thành viên thứ j chỉ cần dùng khóa giải mã của riêng mình Dkj và P=D’(Dkj,C).
  16. SO SÁNH 1. Cách lập mã (mã hóa) 2. Cách giải mã 3. Tính bảo mật
  17. CÁCH LẬP MÃ Mã khóa bí mật Mã khóa công khai -Chọn số hoặc là số - Chọn số nguyên tố( số nguyên tố. nguyên tố rất lớn) -Tạo khóa theo công - Tạo khóa theo công thức: E(K,P)=C thức: E (P,K )=C E: là giải thuật mã j j E (P,K ): là hàm mã hóa hóa j j với khóa K công khai K:Khóa j C:là thông điệp C:là thông điệp đã mã đã mã hóa hóa P:là thông điệp P:là thông điệp ban đầu ban đầu
  18. CÁCH GIẢI MÃ Mã khóa bí mật Mã khóa công khai - Giải mã theo công - Giãi mã theo công thức: thức: D(K,C)=P D’(Y,C)=P D(K,C): là giải thuật giải D’(Y,C)là hàm giải mã mã với Khóa K và với khóa riêng Y và thông điệp cần giải thông điệp cần giải mã C mã C P: là thông điệp ban P:là thông điệp ban đầu đầu
  19. TÍNH BẢO MẬT Mã bí mật Mã công khai - Bảo mật được thông - Tính bảo mật cao hơn tin cần gửi . và an toàn hơn. - Dễ bẻ khóa,tốn thời - Khó bẻ khóa,thời gian gian thám mã ít. thám mã rất lâu ( có thể - Chọn khóa,lập mã và vài năm và hơn). giải mã nhanh. - Chọn khóa lâu hơn (vì phải chọn số nguyên tố rất lớn, cần có giải thuật) vì vậy lập mã và giải mã cũng lâu hơn.
  20. NHẬN XÉT Nói tóm lại, mỗi phương pháp đều có ưu và khuyết điểm, tùy thuộc vào nhu cầu bảo mật, mức độ thông tin quan trọng mà ta lựa chọn .
  21. NHÓM 2 HỆ MÃ RSA 21 Designed by group 9
  22. NỘI DUNG CHÍNH NHÓM 2: ➢ Giới thiệu về hệ mã RSA ➢ Nguyên tắc sử dụng hệ mã RSA ▪ Giai đoạn chọn khóa. ▪ Giai đoạn mã hóa ▪ Giai đoạn giải mã ➢ Phiên bản mở rộng của RSA ➢ Tính chất của hệ mã RSA ▪ Tính khả thi ▪ Tính bảo mật ▪ Tính hiệu quả 22 Designed by group 9
  23. HỆ MÃ RSA GIỚI THIỆU VỀ HỆ MÃ RSA 23 Designed by group 9
  24. GIỚI THIỆU VỀ HỆ MÃ RSA • RSA là mã công khai được sáng tạo bởi Ronald Rivest, Adi Shamir và Leonard Adleman ở MIT (Trường Đại học Công nghệ Massachusetts) vào năm 1977. • RSA là mã công khai được biết đến nhiều nhất và sử dụng rộng rãi nhất hiện nay 24 Designed by group 9
  25. GIỚI THIỆU VỀ HỆ MÃ RSA • Ý tưởng về hệ mã công khai được Martin Hellman, Ralph Merkle và Whitfield Diffie tại Đại học Stanford giới thiệu vào năm 1976. • Sau đó, phương pháp Diffie-Hellman của Martin Hellman và Whitfield Diffie đã được công bố. 25 Designed by group 9
  26. GIỚI THIỆU HỆ MÃ RSA • Một hệ mã công khai sử dụng hai loại khóa: ▪ Khóa công khai (public key) được công bố rộng rãi và được sử dụng trong việc mã hóa, ▪ Khóa riêng (private key) chỉ do một người nắm giữ và được sử dụng để giải mã thông tin đã được mã hóa bằng khóa công khai.
  27. GIỚI THIỆU VỀ HỆ MÃ RSA • Năm 1978, R.L.Rivest, A.Shamir và L.Adleman đã đề xuất hệ mã công khai RSA. • Hệ mã RSa cũng dùng ý tưởng hàm một chiều nhưng là hàm một chiều với lối đi bí mật.
  28. GIỚI THIỆU VỀ HỆ MÃ RSA • Đây là dạng đặc biệt của hàm một chiều,nghĩa là ta vẫn có tính chất: cho x dễ dàng tính được f(x),nhưng khó tính được x khi biết f(x).Tuy nhiên,nó có thêm tính chất:nếu biết lối đi bí mật z thì khi có z và f(x) sẽ tính ngay được x.
  29. GIỚI THIỆU VỀ HỆ MÃ RSA Hàm một chiều RSA với lối đi bí mật chính là hàm: e fz(x) = x mod n Trong đó x là số nguyên dương không vượt quá n,lối đi bí mật chình là z = {p,q,e}
  30. HỆ MÃ RSA 1.Nguyên tắc sử dụng 2.Giai đoạn chọn khóa 3.Giai đoạn mã hóa 4.Giai đoạn giải mã 30 Designed by group 9
  31. NGUYÊN TẮC SỬ DỤNG Đầu tiên bạn tạo cặp khóa công khai và khóa bí mật của riêng mình. Khóa công khai thì công bố cho mọi người biết còn khóa bí mật thì giữ lại. Khi một người nào đó muốn gửi văn bản mật cho bạn thì sử dụng khóa công khai mà bạn đã công bố để mã hóa văn bản muốn gửi, sau đó sẽ gửi cho bạn đoạn văn bản đã được mã hóa. Sau đó, bạn dùng khóa bí mật của bạn để giải mã văn bản đó. Đều này giống như là địa chỉ mail của bạn. Tên hộp thư mail thì công bố cho mọi người biết. Còn password đăng nhập thì riêng bạn biết. 31 Designed by group 9
  32. TẠO KHÓA Giả sử Nam và Yến cần trao đổi thông tin bí mật thông qua một kênh không an toàn. Với thuật toán RSA, Nam đầu tiên cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau: 32 Designed by group 9
  33. TẠO KHÓA 1. Chọn 2 số nguyến tố lớn p va q(p không trùng q),lựa chọn ngẫu nhiên và độc lập 2. Tính n = p.q 3. Tính  (n) = (p-1).(q-1) 4. Chọn một số tự nhiên e,sao cho: * 1< e < (n) * (e, (n)) = 1 5. Tính d sao cho: d.e =1(mod (n)) 33 Designed by group 9
  34. TẠO KHÓA ➢Khóa công khai bao gồm: • n • e: số mũ công khai (cũng gọi là số mũ mã hóa). ➢Khóa bí mật bao gồm: • d: số mũ bí mật (cũng gọi là số mũ giải mã). 34 Designed by group 9
  35. GIAI ĐOẠN MÃ HÓA • Giả sử Yến muốn gởi đoạn thông tin M cho Nam.Đầu tiên,Yến chuyển M thành từng khối P với độ dài lớn nhất có thể. • Lúc này Yến có từng khối P và biết n,cũng như e do nam đã gởi trước.Yến sẽ tính các khối C theo công thức: E(P) = C ≡ Pe mod n • Cuối cùng,Yến gởi các khối C cho Nam. 35 Designed by group 9
  36. GIAI ĐOẠN GIẢI MÃ • Nam nhân từng khối C do Yến gởi,với khóa bí mật d đã có,Nam có thể tìm được các khối P theo công thức: P = Cd mod n • Từ các khối P ,Nam có thể tìm được thông điệp mà Yến muốn nói. 36 Designed by group 9
  37. GIAI ĐOẠN GIẢI MÃ • Giả sử Yến muốn gởi đoạn thông tin M cho Nam.Đầu tiên,Yến chuyển M thành từng khối P với độ dài lớn nhất có thể. • Lúc này Yến có từng khối P và biết n,cũng như e do nam đã gởi trước.Yến sẽ tính các khối C theo công thức: E(P) = C ≡ Pe mod n • Cuối cùng,Yến gởi các khối C cho Nam 37 Designed by group 9
  38. GIAI ĐOẠN GIẢI MÃ • Nam nhân từng khối C do Yến gởi,với khóa bí mật d đã có,Nam có thể tìm được các khối P theo công thức: P = Cd mod n Từ các khối P ,Nam có thể tìm được thông điệp mà Yến muốn nói. 38 Designed by group 9
  39. • Bảng chuyển chữ cái thành số: a ă â b c d đ e ê g 01 02 03 04 05 06 07 08 09 10 h i k l m n o ô ơ p 11 12 13 14 15 16 17 18 19 20 q r s t u ư v x y 21 22 23 24 25 26 27 28 29 39 Designed by group 9
  40. CHỨNG MINH • Thật vậy,do e.d ≡1 mod (n) nên s Z sao cho e.d ≡ s.(n)+1 Do đó Cd ≡ Pe.d ≡ Ps.(n)+1≡ P(P(n))s mod n • Theo định lý Euler ,ta có P(n) ≡ 1 mod n Do đó: Cd ≡ P mod n hay P ≡ Cd mod n 40 Designed by group 9
  41. MỘT VÀI VÍ DỤ Cho p = 53, q = 59. => n = 53*59 = 3127 - Ta có: (n) = 52*58 = 3016 - Chọn e = 3 (tất nhiên (e, (n))=1) - Giả sử ta cần mã hóa thông tin sau DAY LA MA RSA 41 Designed by group 9
  42. MỘT VÀI VÍ DỤ Trước tiên ta chuyển các chữ cái thành các chữ số và nhóm chúng lại thành từng khối như sau: 0601 2914 0115 0122 2301 ( lưu ý là khi khối cuối cùng chỉ có một chữ cái ta thêm vào một chữ cái khác sao cho không gây sự hiểu lầm , thường ta thêm vào chữ X ) 42 Designed by group 9
  43. MỘT VÀI VÍ DỤ Mã hóa toàn bộ văn bản ta được văn bản mật sau : 2334 1960 1153 2188 0472 43 Designed by group 9
  44. MỘT VÀI VÍ DỤ Để giải mã,trước tiên ta cần tìm (n) • Từ n = 3127 ta sẽ tìm được p = 53, q = 59 bằng cách phân tích ra thừa số nguyên tố. • Khi có được p và q ,ta dễ dàng tìm được (n) bằng công thức đã biết. • Sau đó ,tìm d bằng công thức e.d ≡ 1 mod( (n)) 44 Designed by group 9
  45. MỘT VÀI VÍ DỤ • Ta tìm được d = 2011(bằng pp euclide mở rộng) • Từ d ta thay vào công thức P ≡ Cd mod n • Thế là ta đã tìm ra được các khối P 0601 2914 0115 0122 2301 • Từ các khối P ta sẽ tìm được nội dung văn bản ban đầu 45 Designed by group 9
  46. MỘT VÀI VÍ DỤ n = 143, e = 7 Giải mã văn bản sau: 106 132 104 14 12 48 3 106 22 104 46 3 10 46 Designed by group 9
  47. HỆ MÃ RSA PHIÊN BẢN MỞ RỘNG CỦA HỆ MÃ RSA 47 Designed by group 9
  48. PHIÊN BẢN MỞ RỘNG CỦA RSA 1.Định lý 2.Chứng minh định lý 3.Một số ví dụ 48 Designed by group 9
  49. ĐỊNH LÝ Cho p, q, r là ba số nguyên tố phân biệt n = pqr N=(p-1)(q-1)(r-1), 1<e<N (e và N là nguyên tố cùng nhau) d = e-1 mod N, 1<d<N, 0 <= m<n Nếu c = me mod n thì m = cd mod n.
  50. CHỨNG MINH Đặt m1 = m mod p c1 = c mod p m2 = m mod q c2 = c mod q m3 = m mod r c3 = c mod r ep = e mod(p-1) dp = d mod(p-1) eq = e mod(q-1) dq= d mod(q-1) er = e mod(r-1) dr = d mod(r-1)
  51. CHỨNG MINH Ta có: c = (c1,c2,c3) = me mod n ep eq er = (m1 mod p, m2 mod q, m3 mod r)
  52. CHỨNG MINH Vậy: d ep eq er c mod n = (c1 mod p, c2 mod q, c3 mod r) dp ep dp c1 mod p= (m1 mod p) mod p ep dp = m1 (mod p)
  53. CHỨNG MINH Do: ed = 1 mod N, ta có ed = 1 (mod(p-1)) Và epdp = ed (mod(p-1)) Vì thế epdp = 1 (mod(p-1))
  54. CHỨNG MINH Tồn tại một số nguyên i thỏa epdp = 1 + i(p-1) Vì thế: dp ep dp c1 mod p = m1 (mod p) 1+i(p-1) = m1 (mod p) (p-1) i = (m1 (mod p))[(m1 (mod p)) (mod p)] = m1 (mod p) = m1 (dùng định lý Fermat)
  55. CHỨNG MINH Tương tự, dq c2 mod q = m2 dr c3 mod r = m3 Cuối cùng: cd mod n = m
  56. NHẬN XÉT Mã hóa: c = me mod n Giải mã: m = cd mod n n và e là khóa công khai d là khóa cá nhân + Để bảo mật thông tin tốt thì ta sử dụng n là số rất lớn và me > n + Để tính được me thì ta nên sử dụng phương pháp bình phương liên tiếp.
  57. VÍ DỤ Mã hóa chuỗi sau: 7332 7679 8669 3289 7985 3270 7982 6986 6982 Với n = 72293 và e = 31111
  58. VÍ DỤ Ta có c = me mod n thay m lần lượt là: 7332 7679 8669 3289 7985 3270 7982 6986 6982 Ta được c tương ứng là: 49140 17117 22011 63401 18086 21690 68198 47614 42810
  59. VÍ DỤ Giải mã chuỗi vừa tìm? Cho N = 64944 Áp dụng thuật giải Bezout Ta được: d = 19111
  60. VÍ DỤ Áp dụng công thức giải mã m = cd mod n Thay c lần lượt là: 49140 17117 22011 63401 18086 21690 68198 47614 42810 Ta được m tương ứng 7332 7679 8669 3289 7985 3270 7982 6986 6982
  61. a ă â b c d đ e ê g 01 02 03 04 05 06 07 08 09 10 h i k l m n o ô ơ p 11 12 13 14 15 16 17 18 19 20 q r s t u ư v x y 21 22 23 24 25 26 27 28 29
  62. HỆ MÃ RSA TÍNH CHẤT CỦA HỆ MÃ RSA 62 Designed by group 9
  63. TÍNH CHẤT CỦA HỆ MÃ RSA 1.Tính khả thi 2.Tính bảo mật 3.Tính hiệu quả 63 Designed by group 9
  64. TÍNH KHẢ THI Trong phần mô tả ở trên, ta giả thiết p, q là hai số nguyên tố rất lớn. Nên n = p.q và φ(n)=(p-1)(q-1) càng lớn hơn. Đồng thời việc tìm khóa giải mã d củng như việc tính Pe mod n, Cd mod n đều trên những số rất lớn. Dù vậy, với tốc độ tính toán của máy tính hiện nay cùng với những thuật toán cho phép ta tìm ra những số nguyên tố rất lớn chỉ trong vài phút hay tính nhanh các phép tính tích, thương, lũy thừa của các số rất lớn.
  65. TÍNH BẢO MẬT Độ an toàn của hệ mã RSA dựa trên 2 vấn đề của toán học: bài toán phân tích ra thừa số nguyên tố các số nguyên lớn và bài toán RSA. Thám mã hệ mã RSA: Vì khóa là công khai nên việc thám mã hệ mã RSA thường dựa vào khóa công khai để xác định được khóa bí mật tương ứng. Người ta thường dùng một số cách sau:
  66. TÍNH BẢO MẬT 1. Tấn công vét cạn 2. Tấn công toán học 3. Tấn công tính toán thời gian 4. Tấn công bản mã 5. Tấn công gây lỗi hệ thống
  67. TÍNH BẢO MẬT TẤN CÔNG TOÁN HỌC ▪ Phân tích n ra thừa số nguyên tố: Nếu có thể phân tích n, ta có thể xác định được p, q, φ(n), từ đó có thể tính được d. Nhưng việc phân tích n ra thừa số nguyên tố là điều không dể dàng. (Năm 2005, số dài nhất có thể phân tích được ra thừa số nguyên tố có độ dài 663 bit, 2008 số nguyên tố lớn nhất tìm thấy có độ dài 12,978,189 chữ số (( )).
  68. TÍNH BẢO MẬT ▪ Tính φ(n) mà không cần phân tích n: nếu biết φ(n), ta có thể tính được p, q thông qua giải hệ 2 phương trình sau: n = p.q φ(n) = (p-1)(q-1) tuy nhiên, việc tính φ(n) có thể dẫn đến bài toán phân tích n. Như vậy, việc tính φ(n) củng khó như phân tích n ra thừa số nguyên tố.
  69. TÍNH BẢO MẬT ▪ Tìm d mà không cần phân tích n hay tính φ(n): ▪ Tấn công dựa trên tính toán lặp lại: Nếu người thám mã biết được n, e và C thì có thể giải phương trình đồng dư: C ≡ Me (mod n) với M=0,1,2, Cho đến khi nào tìm được một M thỏa. Nhưng với n lớn thì việc này hầu như không thể thực hiện.
  70. TÍNH BẢO MẬT ❖Tấn công tính toán thời gian: Người thám mã có thể xác định được khoá bí mật nếu theo dõi thời gian máy tính cần để giải mã các bản tin. ❖Tấn công bản mã: Khai thác tính chất của giải thuật.
  71. TÍNH BẢO MẬT ❖Tấn công gây lỗi hệ thống: Người ta tạo ra một điện thế lớn để gây lỗi hệ thống, từ đó giúp tìm ra khoá bí mật. Bằng cách này họ có thể lấy khoá bí mật RSA 1024 bit chỉ trong vài ngày.(báo cáo của các nhà khoa học thuộc đại học Michigan tại hội nghị DATE 2010)
  72. Tính chất của hệ mã RSA Chú ý: Để giữ an toàn cho bản mã ta cần: - Chọn p, q là số nguyên tố rất lớn. Số e được chọn sao cho gcd (e,φ(n)) =1 vì vậy nên chọn e là số nguyên tố tùy ý lớn hơn p, q và Pe>n. Nếu Pe<n tức là C=Pe< n, để tìm P ta chỉ cần lấy căn bậc e của C. - Để tránh việc n bị phân tích dể dàng, cần chọn p, q sao cho p-1 và q-1 chỉ có các thừa số nguyên tố lớn (p – 1)(q – 1) phải nhỏ. p và q phải có số chữ số trong khai trển thập phân không nhiều
  73. NHÓM 3 HỆ MÃ RABIN 73 Designed by group 9
  74. NỘI DUNG CHÍNH NHÓM 3: ➢ Giới thiệu về hệ mã RABIN ➢ Hệ mã hóa RABIN • Sơ đồ hệ mã hóa • Giai đoạn mã hóa • Giai đoạn giải mã • Một số ví dụ ➢Các đặc trưng của hệ mã RABIN • Tính an toàn của hệ mã • Vấn đề sử dụng dư thừa dữ liệu • Tính hiệu quả của hệ mã. 74 Designed by group 9
  75. SƠ LƯỢC VỀ HỆ MÃ Một đặc điểm quan trọng đáng mong muốn của bất kỳ lược đồ mã hoá nào là nó phải chứng minh được là việc phá khoá (hack) khó tương đương với việc giải một bài toán nào đó đã biết, mà người ta tin tưởng là rất khó, giống như việc phân tích ra thừa số hay giải bài toán logarit rời rạc. 75 Designed by group 9
  76. SƠ LƯỢC VỀ HỆ MÃ Hệ mã hoá RSA, mặc dù được người ta tin là việc phá khoá khó tương đương với việc phân tích ra thừa số theo modulo n, nhưng sự tương đương đó lại chưa được chứng minh. Các hệ thống mã hóa công khai RSA, như bạn biết, sự an toàn của nó có được nhờ vào sự phân tích ra thành nhân tử từ những số lớn. 76 Designed by group 9
  77. SƠ LƯỢC VỀ HỆ MÃ Tuy nhiên, nó còn có một vấn đề bỏ ngỏ đó là: liệu cách duy nhất để phá vỡ hệ thống mã hóa RSA có phải chính là sự phân tích thành nhân tử? Chẳng bao lâu sau sự công bố hệ thống RSA, Michael Rabin đã cho ra đời hệ thống mã hóa công khai của riêng mình. Đó là sự phá vỡ của cái khó khăn mà sự phân tích thành nhân tử của hệ mã hóa RSA đã gặp phải. 77 Designed by group 9
  78. SƠ LƯỢC VỀ HỆ MÃ Hệ mã hoá công khai Rabin là một ví dụ đầu tiên về một lược đồ khoá công khai đã được chứng minh về tính an toàn. Khó khăn mà một người tấn công thụ động gặp phải khi giải mã đó là độ khó tương đương về mặt tính toán với việc phân tích ra thừa số. Nghĩa là với 1 số bất kỳ (n công khai) thì sự giải mã sẽ khó tương đương với giải bài toán phân tích ra thừa số nguyên tố. 78 Designed by group 9
  79. SƠ ĐỒ HỆ MÃ RABIN Sơ đồ hệ mật mã khóa công khai Rabin được cho bởi : S = (P, C, K, E, D) 79 Designed by group 9
  80. SƠ ĐỒ HỆ MÃ RABIN Trong đó: ➢P = C = Zn, với n là một số nguyên Blum, n = p.q, với p và q là 2 số nguyên tố có tính chất p ≡ 3 mod 4, q ≡ 3 mod 4. ➢K = (K’, K”): K’ (khóa công khai) = (n, B) 0 ≤ B ≤ n-1 : K” (khóa bí mật) = (p, q) ➢Các thuật toán E và D được xác định bởi: E(K’,x) = y = x(x,B) mod n D(K”,y) = 80 Designed by group 9
  81. SƠ ĐỒ HỆ MÃ RABIN Trong một mạng truyền tin bảo mật với sơ đồ mật mã Rabin, mỗi người tham gia chọn cho mình các yếu tố n, B, p, q để lập nên khoá công khai và khoá bí mật của mình. 81 Designed by group 9
  82. SƠ ĐỒ HỆ MÃ RABIN Ta chú ý rằng với mỗi bộ khoá K, các thuật toán eK′ = E (K' ,.) và dK′′ = D (K'',.) không lập thành một cặp song ánh, cụ thể là eK′ không phải là một đơn ánh, vì nếu w là một căn bậc hai của 1 theo mod n thì, mà ta có đến 4 căn bậc hai của 1 theo mod n, tức là ta có 4 giá trị khác nhau của đối số x cho cùng một giá trị eK′ (x). 82 Designed by group 9
  83. SƠ ĐỒ HỆ MÃ RABIN Bây giờ nói đến thuật toán giải mã dK′′ = D (K'',.). Đặt C = , ta có dK′′ , do đó để có dK′′ (y), ta cần tính , tức cần giải phương trình z2  C mod n. Phương trình đó tương đương với hệ thống gồm hai phương trình sau đây: (2) 83 Designed by group 9
  84. SƠ ĐỒ HỆ MÃ RABIN vì p và q là các số nguyên tố nên ta có: Theo giả thuyết, p ≡ 3 mod 4 và q ≡ 3 mod 4, nên là các số nguyên; và ta có: 84 Designed by group 9
  85. SƠ ĐỒ HỆ MÃ RABIN Do đó, phương trình Z2 ≡ C mod n hay hệ phương trình (2), có 4 nghiệm theo mod n tương ứng với 4 hệ phương trình sau đây: 85 Designed by group 9
  86. SƠ ĐỒ HỆ MÃ RABIN Cả 4 nghiệm của 4 hệ phương trình đó theo mod n đều được viết chung dưới một ký hiệu là , và vì vậy thuật toán giải mã dK’’(y) thực tế sẽ cho ta 4 giá trị khác nhau theo mod n mà bản rõ là một trong 4 giá trị đó. Việc chọn giá trị nào trong 4 giá trị tìm được làm bản rõ là tùy thuộc vào những được trưng khác của bản rõ àm người giải mã nhận biết (thí dụ: bản rõ dưới dạng số phải có biểu diễn nhị phân là mã của một văn bản tiếng Anh thông thường) 86 Designed by group 9
  87. SƠ ĐỒ HỆ MÃ RABIN Ví dụ: Giả sử p = 7, q = 11 =>n = 77, B = 9. 2 Ta có: eK’(x) = x + 9x mod 77, dK’’ (y) = , Vì 2-1 = 39 mod 77, 9. 2-1 = 9.39 = 43 mod 77 B2 = 4 mod 77, . 2 Với x = 44 ta có eK’(x) = 44 + 9.44 =2332 = 22 mod 77 87 Designed by group 9
  88. II. SƠ ĐỒ HỆ MÃ RABIN Bảng mã tương ứng với x là y= 22. Bây giờ giải mã bản mã y = 22, bằng thủ tục nói trên ta có thể tìm được 4 giá trị của theo mod 77 là 10, 67, 32, 45, từ đó 4 giá trị có thể có của dK’’ (y) là dK’’ = 44, 24, 66, 2. Bản rõ nằm trong 4 giá trị đó, trong trường hợp này là 44. 88 Designed by group 9
  89. GIAI ĐOẠN MÃ HÓA Đầu tiên mỗi bên tạo 1 khóa công khai và 1 khóa bí mật tương ứng. Bên A phải làm các việc sau: 1. Tạo 2 số ngẫu nhiên lớn và khác nhau là p và q. 2. Tính n = p.q 3. Khóa công khai của A là n, khóa bí mật của A là (p,q) 89 Designed by group 9
  90. GIẢI THUÂT MÃ HÓA Sau khi A đã tạo và công khai khóa mã hóa công khai. Lúc đó B muốn gửi một thông điệp cho A thì B sẽ dùng khóa công khai của A để mã hóa, và sau đó A sẽ giải mã thông điệp bằng khóa bí mật tương ứng của mình. Khi đó B cần làm những việc sau: 90 Designed by group 9
  91. GIẢI THUÂT MÃ HÓA 1. Nhận khóa công khai đã được xác thực của A là n 2. Giả sử thông điệp là một số nguyên m trong khoảng [0,1, ,n-1] 3. Tính c = m2 mod n 4. Gửi bản mã hóa c cho A 91 Designed by group 9
  92. GIẢI THUÂT MÃ HÓA Chú ý: Vấn đề chọn p và q thì ta có thể chọn p và q là một số nguyên tố bất kỳ. Nhưng chúng ta có thể chọn p ≡ q ≡ 3 mod 4 để việc giải mã được đơn giản. Khi đó chúng ta có 2 cách để giải mã: 1. Giải mã khi chọn p và q bất kỳ 2. Giải mã khi chọn p ≡ q ≡ 3 mod 4 Cách mã hóa thì vẫn làm như nhau. 92 Designed by group 9
  93. GIẢI THUÂT GIẢI MÃ Sau khi A nhận được thông điệp đã được mã hóa của B. A đã có khóa bí mật là n = p.q, để nhận được bản rõ m từ c thì A phải làm các việc sau: 93 Designed by group 9
  94. GIẢI THUÂT GIẢI MÃ I. Giải mã theo cách chọn p và q là bất kỳ: a. Chọn ngẫu nhiên b ∈ Zp cho đến khi b2 – 4a là 1 số không dư bậc 4 mod p (a quadratic non-residue modulo p), nghĩa là b. Gọi f là 1 đa thức f = x2 – bx + a trong Zp[x]. c. Tính r = c(p+1)/4 mod f (r sẽ là 1 số nguyên) d. Trả lại (r, -r). 94 Designed by group 9
  95. GIẢI THUÂT GIẢI MÃ e. Thực hiện tương tự để tìm 2 căn bậc 2 của a theo mod q. Kết quả sẽ được (s, -s) f. Sử dụng giải thuật Euclidean mở rộng để tìm các số nguyên c và d thỏa: cp + dq = 1 g. Đặt x = ( rdq + scp) mod n và y = ( rdq – scp) mod n h. Kết quả trả về sẽ là: (±x mod n, ±y mod n) 95 Designed by group 9
  96. GIẢI THUÂT GIẢI MÃ II. Giải mã theo cách chọn p ≡ q ≡ 3 mod 4: Nếu p và q được chọn để cả p ≡ q ≡ 3 mod 4 thì thuật toán để tìm 4 căn bậc 2 của c mod n có thể đơn giản như sau: 96 Designed by group 9
  97. GIẢI THUÂT GIẢI MÃ II. Giải mã theo cách chọn p ≡ q ≡ 3 mod 4: 1. Dùng thuật toán Euclide mở rộng tìm 2 số nguyên a và b thoả mãn: ap + bq = 1 2. Tính r = c(p+1)/4 mod p 3. Tính s = c(q+1)/4 mod q 4. Tính x = (aps + bqr) mod n. 5. Tính y = (aps - bqr) mod n. 6. 4 căn bậc 2 của c mod n là x, -x mod n và y, –y mod n. 97 Designed by group 9
  98. VÍ DỤ 1. Tạo khóa: A chọn số nguyên tố p = 331, q = 311 có p ≡ q ≡ 3 mod 4 Và tính n = p.q = 102941 Khóa công khai của A là n = 102941 Khóa bí mật của A là (p = 331, q = 311) 2. Mã hóa: Giả sử 6 bit cuối cùng của thông điệp ban đầu cần phải được lăp lại trước khi mã hóa. Để mã hóa thông điệp 10 bit m = 633(10)= 1001111001(2), B lặp lại 6 bit cuối cùng của m để nhận được thông điệp 16 bit m=1001111001111001. Theo hệ 10 thì m=40569. 98 Designed by group 9
  99. VÍ DỤ Sau đó B tính: c=m2 mod n = 405692 mod 102941=23053 và gửi c cho A 3. . Giải mã: i. Dùng thuật toán Euclide mở rộng tìm 2 số nguyên a, b thỏa mãn: ap + bq = 1 Tìm được a=140, b=-149 ii. Tính r=c(p+1)/4 mod p = 23053(331+1)/4 mod 331 = 144 iii. Tính s=c(q+1)/4 mod q =23053(311+1)/4 mod 311 = 139 iv. Tính x=(aps+bqr) mod n = (6052060-6672816) mod 102941= -25674 v. Tính y=(aps-bqr) mod n = (6052060+6672816) mod 102941= 40569 99 Designed by group 9
  100. VÍ DỤ Bốn căn bậc 2 của c mod n là: x, -x mod n, y, -y mod n m1= 25674(10) = 644A(H) = 0110010001001010(2) m2=77267(10) = 2DD3(H) = 0010110111010011(2) m3=40569(10) = 9E79(H) = 1001111001111001(2) m4=62372(10) = F3A4(H) = 1111001110100100(2) Vì chỉ có m3 có dư thừa dữ liệu yêu cầu, A giải mã c thành m3 (bỏ 6 bit cuối cùng) và phục hồi bản rõ ban đầu là: m = 1001111001(2) = 633(10) 100 Designed by group 9
  101. VÍ DỤ Ví dụ 1: Cho n = 77, thông điệp c = 56 Giãi mã thông điệp trên 101 Designed by group 9
  102. VÍ DỤ Dựa vào thuật toán Euclide mở rộng tìm được a=-8; b = 3 p=7, q =19 Tính: r=c(p+1)/4 mod p = 4(7+1)/4 mod 7 = 2 s=c(q+1)/4 mod q =4(19+1)/4 mod 19 = 17 x=(aps+bqr) mod n = (-952 + 114) mod 133 = 93 y=(aps-bqr) mod n = (-952 – (141) ) mod 133 = 131 m1= x = 93 m2= -x mod n= 40 m3= y = 131 m4= -y mod n = 2 102 Designed by group 9
  103. TÍNH CHẤT CỦA HỆ MÃ RABIN 1. Tính an toàn của hệ mã: (1) Một người tấn công bị động cần phục hồi bản rõ m từ bản mã c. Đây chính là giải bài toán căn bậc 2 ở trên. Vấn đề phân tích ra thừa số số n và tính căn bậc 2 theo module n là tương đương về mặt tính toán. Vì vậy giả sử việc phân tích ra thừa số số n là khó về mặt tính toán thì lược đồ mã hoá công khai Rabin được chứng minh là an toàn đối với một người tấn công bị động. 103 Designed by group 9
  104. TÍNH CHẤT CỦA HỆ MÃ RABIN (2) Trong khi được chứng minh là an toàn đối với một người tấn công bị động, lược đồ mã hoá công khai Rabin lại không chống nổi một cuộc tấn công bản mã lựa chọn(chosen-ciphertext). Một cuộc tấn công như vậy có thể mô tả như sau: 104 Designed by group 9
  105. TÍNH CHẤT CỦA HỆ MÃ RABIN Người tấn công chọn 1 số nguyên m ∈ Z*n và tính c = m2 mod n. Người tấn công sau đó đưa c đến máy giải mã của A, giải mã c và trả lại 1 bản rõ y nào đó. Vì A không biết m, và m được chọn ngẫu nhiên, bản rõ y không nhất thiết phải giống hệt m. Với khả năng ½, y ≢ ± m mod n, khi đó gcd(m-y, n) là một trong các thừa số của n. Nếu y ≡ ±m mod n, người tấn công lại lặp lại với một số m mới. 105 Designed by group 9
  106. TÍNH CHẤT CỦA HỆ MÃ RABIN Lược đồ mã hoá công khai Rabin dễ bị thương tổn bởi những cuộc tấn công tương tự như với các trường hợp của hệ mã hoá RSA. Giống như hệ RSA, các cuộc tấn công (1) và (2) có thể bị thất bại bằng cách biến đổi (salting) bản rõ, trong khi các cuộc tấn công đó có thể tránh được bằng cách thêm dư thừa dữ liệu trước khi mã hoá. 106 Designed by group 9
  107. TÍNH CHẤT CỦA HỆ MÃ RABIN 1. Sử dụng dư thừa dữ liệu: (1) Một nhược điểm của hệ mã hoá công khai Rabin là người nhận phải có nhiệm vụ chọn bản rõ đúng từ 4 khả năng. Sự nhầm lẫn trong việc giải mã có thể vượt qua một cách dễ dàng bằng cách thêm dư thừa dữ liệu vào bản rõ gốc một cách xác định trước khi mã hoá. (ví dụ: 64 bit cuối cùng của thông điệp có thể được lặp lại). 107 Designed by group 9
  108. TÍNH CHẤT CỦA HỆ MÃ RABIN Với khả năng cao, chỉ 1 trong 4 căn bậc 2 của bản mã c là m1, m2, m3, m4 có được dư thừa đó. Người giải mã sẽ chọn bản này làm bản rõ. Nếu không có căn bậc 2 nào của c có dư thừa này, người nhận sẽ từ chối c, vì nó là giả mạo. (2) Nếu sử dụng dư thừa dữ liệu như trên, lược đồ Rabin sẽ không còn dễ bị thương tổn bởi các cuộc tấn công bản mã lựa chọn như nói ở trên. 108 Designed by group 9
  109. TÍNH CHẤT CỦA HỆ MÃ RABIN Nếu người tấn công chọn 1 thông điệp m có dư thừa dữ liệu như yêu cầu và đưa c = m2 mod n vào máy giải mã của A, khả năng rất cao là máy sẽ trả lại bản rõ m cho người tấn công (vì 3 căn bậc 2 của c kia sẽ có khả năng rất cao là không chứa dư thừa dữ liệu như yêu cầu). Không đưa ra thông tin mới nào. Mặt khác, nếu người tấn công chọn một thông điệp m mà không có dư thừa dữ liệu cần thiết, khả năng cao là cả bốn căn bậc 2 của c mod n đều không có dư thừa dữ liệu cần thiết. 109 Designed by group 9
  110. TÍNH CHẤT CỦA HỆ MÃ RABIN Trường hợp này máy giải mã sẽ thất bại việc giải mã c và không trả lời người tấn công. Chú ý rằng việc chứng minh tính tương đương của việc phá khoá lược đồ cải tiến này bởi một người tấn công thụ động với việc phân tích ra thừa số không còn giá trị nữa. Tuy nhiên, nếu giả sử rằng việc giải mã Rabin gồm hai giai đoạn, giai đoạn thứ nhất là tìm bốn căn bậc 2 của c mod n, và giai đoạn thứ hai là lựa chọn căn bậc 2 làm bản rõ thì vẫn chứng minh được tính tương đương. 110 Designed by group 9
  111. TÍNH CHẤT CỦA HỆ MÃ RABIN Vì vậy lược đồ mã hoá khoá công khai Rabin, được sửa đổi một cách thích hợp bằng cách thêm dư thừa dữ liệu, là rất được quan tâm ứng dụng. 111 Designed by group 9
  112. PHẦN MỞ RỘNG MỘT SỐ HỆ MÃ KHÓA CÔNG KHAI KHÁC 112 Designed by group 9
  113. HỆ MÃ ELGAMAL El Gamal: được đề xuất năm 1985 dựa vào độ phức tạp tính toán của bài toán Logarit rời rạc, và sau đó nhanh chóng được sử dụng rộng rãi khong những trong vấn đề bảo mật truyền tin mà còn trong các vấn đề xác nhận về chữ ký diện tử. Được phát triển bởi Taher ElGamal Kích thước key: 512 hoặc 1024 bits,sử dụng giao thức PGP 113 Designed by group 9
  114. HỆ MÃ ELGAMAL Thuật toán: Chọn số nguyên tố p Chọn 1 số ngẫu nhiên k, sao cho ước chung của k và p là 1 Thông thường ta chọn k là một số rất lớn k = 853 Chọn g và x thoả: g< p và x <p Tính y = g x mod p Từ đây, ta có cặp Key (Key Pair) Private Key = (x) 114 Public Key = (y, g, p) Designed by group 9
  115. HỆ MÃ ELGAMAL Quy tắc mã hoá: a = gk mod p b = m* y k mod p Quy tắc giải mã: m = b / (ax) mod p Với: a và b là: văn bản bị mã hoá (Cipher text) m: văn bản chưa bị mã hoá (Plain text) 115 Designed by group 9
  116. HỆ MÃ ELGAMAL Cũng như RSA, El Gamal thực hiện việc mã hoá và giải mã đều trên những con số. Nếu như bị người khác bắt được, thì họ không thể biết và đoán được gì. El Gamal cũng sử dụng key có kích thước lớn, từ 512 đến 1024 bits. Giúp cho dữ liệu được an toàn, bảo mật trên đường truyền. Tốc độ mã hoá và giải mã thì chậm hơn so với RSA, ít được dùng phổ biến và rộng rãi như là RSA 116 Designed by group 9
  117. HỆ MÃ ELLIPTIC CURVE Hiện nay, hệ mật RSA là giải thuật khoá công khai được sử dụng nhiều nhất, nhưng hệ mật dựa trên đường cong Elliptic (ECC) có thể thay thế cho RSA bởi mức an toàn và tốc độ xử lý cao hơn. 117 Designed by group 9
  118. HỆ MÃ ELLIPTIC CURVE ECC thực hiện việc mã hoá và giải mã dựa trên toạ độ của các điểm dựa trên đường cong Elliptic. Xét đẳng thức Q= kP, với Q,P là các điểm nằm trên đường cong Elliptic. Có thể khá dễ dàng tính Q nếu biết k và P, nhưng rất khó xác định k nếu biết Q và P. (Phép nhân được xác định bằng cách cộng liên tiếp cùng điểm P) Ví dụ: 4P = P+P+P+P ; 9P = 2(2(2P)) + P 118 Designed by group 9
  119. HỆ MÃ ELLIPTIC CURVE Hệ mật dựa trên đường cong Elliptic dựa trên độ khó khi biết được điểm P và Q và phải tìm ra giá trị k. Bên cạnh công thức của đường cong Elliptic, thì một thông số quan trọng khác của đường cong Elliptic là điểm G (còn gọi là điểm cơ sở), điểm G đối với mỗi đường cong elliptic là cố định.Trong hệ mật mã ECC thì một số nguyên lớn k đóng vai trò như một khoá riêng, trong khi đó kết quả của phép nhân giữa k với điểm G được coi như là khoá công khai tương ứng. 119 Designed by group 9
  120. HỆ MÃ ELLIPTIC CURVE Việc trao đổi khoá theo Diffie Hellman dựa trên đường cong Elliptic (ECDH – Elliptic Curve Diffie Hellman) và thuật toán chữ ký số dựa trên đường cong Elliptic (ECDSA - Elliptic Curve Digital Signature Algorithm) là những ứng dụng cụ thể của đường cong Elliptic trong lĩnh vực mật mã. 120 Designed by group 9
  121. TÓM LẠI Việc sử dụng ECC mang lại những hiệu quả sau: tăng tốc độ, yêu cầu khả năng tính toán thấp hơn, tiết kiệm dải thông đường truyền, tăng hiệu quả lưu trữ, giảm độ dài các chứng nhận Các ưu điểm trên của hệ mật ECC có thể phát huy hiệu quả trong các ứng dụng mà đường truyền, khả năng tính toán, tốc độ và lưu trữ bị hạn chế. Và các ứng dụng đó được thể hiện rất hiệu quả trong thương mại điện tử, web servers Với cùng một độ dài khoá thì ECC có nhiều ưu điểm hơn so với các giải thuật khác 121 Designed by group 9