Chương 8 Mật mã khóa công khai

Chương 8 MẬT MÃ KHÓA CÔNG KHAI Tổng quan về mật mã công khai Trong chương trước chúng ta đã tìm hiểu về mật mã đối xứng. Chúng ta rõ rằng các bên tham gia cần có một khóa mật để mã hóa và giải mã. Điều này đồng nghĩa với việc trao đổi khóa mật qua kênh. Việc giữ bí mật khóa mật đồng nghĩa với việc giữ mật thông tin. Nên việc trao đổi khóa chỉ diễn ra trên kênh mật thì mới đảm bảo được, thế nhưng việc trao đổi này cung không phải dễ để đảm bảo độ an toàn cao. Từ đây hình thành nên ý tưởng của mật mã công khai. Tức là không cần phải trao đổi khóa mật qua kênh nữa. Ý tưởng của hệ mật công khai được Diffie và Hellman đưa ra năm 1976. Còn việc thực hiện hệ mật công khai thì do Rivest, Shamir và Adleman đưa ra đầu tiên năm 1977, họ đề xuất một hệ mật RSA nổi tiếng. Và kể từ đó có một số hệ mật khác được công bố, độ mật của chúng dựa trên bài tính toán khác nhau, như dựa trên độ khó của bài toán phân tích thành nhân tử như hệ mật RSA, dựa vào độ khó logarithm rời rạc như hệ mật ElGamal, hay dựa trên đường cong Elliptíc. Chúng ta đi tìm hiểu cụ thể các hệ mật này trong các phần sau. Nhưng trước tiên chúng ta đi tìm hiểu sơ đồ và nguyên tắc mã và giải mã của hệ mật công khai. Sơ đồ của hệ mã công khai được cho ở hình 8.1. Hình 8.1. Sơ đồ mã hóa công khai Hệ mã công khai sử dụng hai khóa có quan hệ toán học với nhau, tức là một khóa này được hình thành từ khóa kia: Người muốn nhận bản mã (Alice) tạo ra một khóa mật (private key) và từ khóa mật tính ra khóa công khai (public key) với một thủ tục không phức tạp, còn việc tìm khóa mật khi biết khóa công khai là bài toán khó giải được. Khóa công khai sẽ đưa đến cho người gởi bản tin (Bob) qua kênh công cộng. Và bản tin được Bob mã hóa bằng khóa công cộng. Bản mã truyền đến Alice, và nó được giải mã bằng khóa mật. Hệ mật RSA Lịch sử hình thành Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT). Tên của thuật toán lấy từ 3 chữ cái đầu của tên 3 tác giả. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. Thuật toán RSA được MIT đăng ký bằng sáng chế tại Hoa Kỳ vào năm 1983 (Số đăng ký 4,405,829). Bằng sáng chế này hết hạn vào ngày 21 tháng 9 năm 2000. Tuy nhiên, do thuật toán đã được công bố trước khi có đăng ký bảo hộ nên sự bảo hộ hầu như không có giá trị bên ngoài Hoa Kỳ. Ngoài ra, nếu như công trình của Clifford Cocks đã được công bố trước đó thì bằng sáng chế RSA đã không thể được đăng ký. Thuật toán dựa trên độ khó của bài toán phân tích một số thành nhân tử. Quá trình tạo khóa cho hệ mật RSA. Giả sử Alice và Bob cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, Alice đầ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 6 bước sau: Chọn 2 số nguyên tố lớn khác nhau p, q thỏa mãn điều kiện Tính tích của nó . Tính giá trị hàm Phi Euler của n: . Chọn số nguyên d, sao cho và gcd(d,)=1. Tính giá trị e thỏa mãn điều kiện:. Khóa công khai bao gồm: n và e. Khóa mật:d còn p,q và thường là xóa sau khi tính toán khóa. Quá trình mã hóa: Giả sử Bob muốn gửi đoạn thông tin m<n cho Alice, thì Bob tính bản mã như sau. Cuối cùng Bob gửi c cho Alice. Quá trình giải mã: Alice nhận c từ Bob và khóa bí mật d. Alice có thể tìm được m từ c theo công thức sau: Quá trình giải mã hoạt động vì ta có Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), theo Định lý Fermat nhỏ nên: Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý phần dư trung hoa, chúng ta có: Hay Ví dụ: 70793 707933 50116700869 50115922144 30483041 5851898625 m 30483041 7523619714 30483041 7523619714 38101458113 7523619714 3487987 4469234330 3487987 754553 45262687896 754553 884545 48968540294 884545 46665533 10037623855 46665533 15657 29531681112 15657 95432 4648093185 95432 4545786 38326603863 4545786 777543 38921288996 777543 45673222 21930948547 45673222 Một số chú ý quan trọng về RSA An ninh: Độ an toàn của hệ thống 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. Nếu 2 bài toán trên là khó (không tìm được thuật toán hiệu quả để giải chúng) thì không thể thực hiện được việc phá mã toàn bộ đối với RSA. Phá mã một phần phải được ngăn chặn bằng các phương pháp chuyển đổi bản rõ an toàn. Bài toán RSA là bài toán tính căn bậc e môđun n (với n là hợp số): tìm số m sao cho me=c mod n, trong đó (e, n) chính là khóa công khai và c là bản mã. Hiện nay phương pháp triển vọng nhất giải bài toán này là phân tích n ra thừa số nguyên tố. Khi thực hiện được điều này, kẻ tấn công sẽ tìm ra số mũ bí mật d từ khóa công khai và có thể giải mã theo đúng quy trình của thuật toán. Nếu kẻ tấn công tìm được 2 số nguyên tố p và q sao cho: n = pq thì có thể dễ dàng tìm được giá trị (p-1)(q-1) và qua đó xác định d từ e. Trong chương số học chúng ta đã biết chưa có một phương pháp nào được tìm ra trên máy tính để giải bài toán này trong thời gian đa thức (polynomial-time). Tuy nhiên người ta cũng chưa chứng minh được điều ngược lại (sự không tồn tại của thuật toán). Tốc độ: RSA có tốc độ thực hiện chậm hơn đáng kể so với các thuật toán mã hóa đối xứng. Trên thực tế, Bob sử dụng một thuật toán mã hóa đối xứng nào đó để mã hóa văn bản cần gửi và chỉ sử dụng RSA để mã hóa khóa để giải mã (thông thường khóa ngắn hơn nhiều so với văn bản). Phương thức này cũng tạo ra những vấn đề an ninh mới. Một ví dụ là cần phải tạo ra khóa đối xứng thật sự ngẫu nhiên. Nếu không, kẻ tấn công (thường ký hiệu là Eve) sẽ bỏ qua RSA và tập trung vào việc đoán khóa đối xứng. Chiều dài khóa: Số n cần phải có kích thước không nhỏ hơn 512 bít. Năm 2006 hệ mật RSA được cho là hiệu quả với kích thước n phải từ 1024. Và họ khuyến cáo là tương lai thì chiều dài n phải từ 2024 bít. Chọn tham số công khai: Để nâng cao tốc độ mã hóa, thì chúng ta nên chọn e với giá trị không lớn, thường là 3, 7 hay 65537. Các số này khi biểu diễn ở dạng nhị phân chỉ có 2 chữ số 1, nên khi thực hiện lệnh lũy thừa sẽ giảm đi lệnh nhân. Chọn tham số mật. p và q còn cần được chọn không quá gần nhau để phòng trường hợp phân tích n bằng phương pháp phân tích Fermat. Ngoài ra, nếu p-1 hoặc q-1 có thừa số nguyên tố nhỏ thì n cũng có thể dễ dàng bị phân tích theo phương pháp p-1 Pollaid và vì thế p và q cũng cần được thử để tránh khả năng này. Chúng ta có thể chọn như sau. Trước tiên tìm số nguyên tố p1 sao cho p=2p1+1 cũng là số nguyên tố, tương tự chọn số nguyên tố lớn q1 sao cho q=2q1+1 cũng là số nguyên tố. Giá trị d cần phải đủ lớn. Năm 1990 Michael J. Wiener đã chứng minh rằng nếu như và , thì có phương pháp hiệu quả để tính d theo n và e. Hệ mật Elgama Hệ mật Elgama hình thành trên cơ sở bài toán logarith rời rạc. Được đề xuất năm 1984. Sau đó chuẩn chữ ký điện tử của Mỹ và Nga hình thành trên cơ sở hệ mật này. Hình thành khóa: Giả sử Alice và Bob muốn trao đổi thông tin mật với nhau bằng hệ mật Elgamma. Thì trước tiên Alice thực hiện qúa trình hình thành khóa như sau: Chọn số nguyên tố đủ lớn p có chiều dài là k sao cho bài toán logarithm trong là khó giải Chọn là phần tử nguyên thủy. Chọn x là số ngẫu nhiên sao cho 1<x<p. Tính giá trị y thỏa mãn công thức: Khóa mật là x, còn khóa mở là 3 số (,p,y). Quá trình mã hóa bản tin T: Chọn số ngẫu nhiên . (chọn k) Tính:. () Sử dụng khóa mở tính: , () Bob gởi bản mã gồm đến Alice (C,r) Quá trình giải mã: Tính giá trị: . () Tính gía trị nghịch đảo của Z: . () Giải mã theo bản mã : . ( Chúng ta kiểm chứng lại quá trình giải mã là đúng như sau: Ví dụ: 707933 203 765 371696 T R C’ C’’ Z T’ 455 457 381267 181064 263892 181064 168667 455 2222 333 309977 545579 295242 545579 313868 2222 554 2224 114192 394828 691348 394828 530064 554 6878 1175 413040 351963 378587 351963 684082 6878 34333 95453 77756 698244 76073 698244 194793 34333 332 545 417805 231659 454024 231659 89120 332 978 9996 618551 527400 421976 527400 247794 978 8656 778645 305246 305321 144687 305321 329172 8656 1233 7564 558848 523937 379425 523937 419571 1233 8965 3434 239368 658412 626159 658412 701743 8965 Hệ mật Rabin Đây là hệ mật dựa trên độ phức tạp của việc tính căn bậc hai theo hợp số. Đây là hệ mật có độ an toàn về mặc tính toán chống lại được tấn công bản rõ lựa chọn và không có khả năng phân tích được n=pq. Thuật toán được ứng dụng rất nhiều trong thực tế. Thuật toán hệ mật Rabin Quá trình tạo khóa: Để tạo ra khóa Alice cần phải thực hiện các thao tác sau: Chọn 2 số nguyên tố ngẫu nhiên p và q, thỏa mãn điều kiện sau: . Tính tích p và q: . Chọn số ngẫu nhiên b. Sử dụng cặp (n,b) làm cặp khóa công cộng và cặp (p,q) làm khóa mật. Quá trình mã hóa: Để gởi thông tin mật cho Alice, Bob cần tạo ra bảng mã c như sau: Qúa trình giải mã: Để giải mã bản mã c, Alice giải phương trình bậc hai sau: Với M<n. Chúng ta chứng minh thuật toán xxx này là một hệ mật, có nghĩa là quá trình giải mã được thực hiện bởi Alice sẽ khôi phục lại bản rõ được mã hóa bới Bob. Giải phương trình bậc 2, chúng ta có nghiệm chung dạng: , ở đây bởi vì c phụ thuộc vào phần tử , nên phương trình bậc hai: , Có nghiệm trong . Một trong các nghiệm của nó là số m, được gởi bởi Bob. Từ đây dẫn đến phải là thặng dư bậc hai theo modulo n, hay là phần tử của nhóm QRn. Việc tính toán để mã hóa, cần phải lấy căn bậc hai theo modulo N. Bài toán này tương đương với bài toán phân tích thành nhân tử của số n. Alice là người duy nhất có thể tính được căn này, bởi vì Alice biết được thừa số của n, Alice có thể tính căn của (xem cách tính căn trong chương số học). Chúng ta thấy rằng có 4 nghiệm được lấy ra khi giải mã. Điều này cần có thông tin phụ để Alice có thể nhận ra được bản nào là bản tin mà Bob gởi. Khi n là số nguyên Blum, có nghĩa là n=pq, với . Chúng ta có thể tính toán dể dàng hơn như sau: Đặt m=M+b/2, thế vào phương trình bậc hai chúng ta có: Đặt , thì phương trình trên có thể viết lại Chúng ta đi giải phương trình này: ; Theo tiêu chuẩn Euler chúng ta có: Dẫn đến: Dẫn đến căn bậc hai của C theo modulo p và q lần lượt là: Đặt: ; ; Ta rút ra được 4 nghiệm như sau: ; ; ; ; Ví dụ: p=13327 q=1567 n=20883409 m 7771 18621623 7771 5556 64 1503 3019673 7771 20875638 17863736 Hệ mật Merkle-hellman Hệ mật xếp ba lô Merkle-hellman được Merkle-hellman miêu tả năm 1978. Hệ mật này bị phá vở năm 1980, sau đó có một số biến thể của nó ra đời. Mặc dầu nó bị phá nhưng nó cho chúng ta thấy một sự tinh tế trong thiết kế hệ mật. Bài toán này dựa trên bài toán tổng các tập con. Bài toán được phát biểu như sau Bài toán về tổng các tập con. Cho tập trong đó, và S là các số nguyên dương. Các si gọi là các cỡ, S gọi là tổng đích. Bài toán đặt ra vấn đề là liệu có tồn tại một véct tơ nhị phân sao cho: . Bài toán tìm kiếm này thuộc bài toán NP đầy đủ. Và người ra đã tìm ra rằng nếu dãy là một dãy siêu tăng, nghĩa là với , thì bài toán tìm kiếm dể dàng giải được với chi phí thời gian O(n) và nếu tìm được x (nếu tồn tại) là duy nhất. Thuật toán này miêu tả như sau: Đầu vào là dãy siêu tăng Begin For i=n downto 1 do If Ssi then S=S-si xi=1 else xi=0 if then là giải pháp cần tìm Else Không tồn tại giải pháp nào. End Dựa trên thực giải này Merle-Hellman đi xây dựng thuật toán của mình. Ý tưởng thuật toán là, dùng dãy siêu tăng để giải mã, và giải mã bằng một dãy không phải siêu tăng, tức là dãy siêu tăng đóng vai trò là khóa mật, còn dãy không siêu tăng đóng vai trò là khóa công cộng. Từ đây họ đưa ra cách để biến dãy siêu tăng thành dãy không có tính đó, và việc tìm dãy siêu tăng theo khóa công cộng là bài toán khó. Một cách biến đổi mà Merle-Hellman nêu ra là biến đổi dãy siêu tăng theo modulo nguyên tố p, sao cho: , Và phép biến đổi như sau. Chọn số a thỏa mãn . Sau đó xác định thành phần của dãy: Với . Dãy là khóa công khai. Các giá trị a và p dùng để biến đổi dãy được giữ mật. Hệ mật Herkle-Hellman Alice và Bob muốn trao đổi thông tin mật cho nhau, thì Alice phải thực hiện quá trình hình thành khóa. Alice chọn dãy siêu tăng làm khóa mật, sau đó Alice đi tính khóa công cộng , với . Alice gởi t cho Bob qua kênh mật. Quá trình mã hóa: Bob muốn trao bản tin cho Alice, thì Bob tính bản mã y như sau: , Bob gởi bản y cho Alice. Quá trình giải mã. Alice nhận được bản mã y, thì Alice thực hiện giải mã: Tính Tìm giải pháp x với dãy siêu tăng và tổng là z. Chúng ta đi tìm hiểu ví dụ nhỏ sau về hệ mật Merkle-Hellman Giả sử Alice chọn dãy siêu tăng s=(2,5,9,21,45,103,215,450,946) có 9 phần tử, dùng để mã hóa một số 9 bít và chọn p=2003, a=1289. Alice tính ra khóa công khai t=(575,436,1586,1030,1921,569,721,1183,1570). Gởi t cho Bob qua kênh công cộng. Bob muốn gởi cho Alice bản tin x=(1,0,1,1,0,0,1,1,1). Thì Bob tính bản mã: y=575+1586+1030+721+1183+1570=6665 Bob gởi y cho Alice. Alice nhận được y, và tính =317.6665 mod 2003=1643. Tiếp theo Alice dùng thuật giải trên để tìm ra x. Hệ mật McEliece Hệ mật McEliece được đề xuất năm 1978, tác giả của nó là Robert McEliece. Ý tưởng của bài toán này giống với ý tưởng của hệ mật Merkle-Hellman: Phép giải mã là trường hợp đặc biệt của bài toán NP đầy đủ. Để hiểu được hệ mật này các bạn phải nắm được kiến thức cơ bản về lý thuyết cơ bản về truyền tin, thông tin. Gọi C[n,k] là mã tuyến tính, t là số bít bị sai khi truyền bản mã qua kênh nhiểu, các tham số này có liên quan với nhau bằng các hệ thức:,. Để áp dụng trong thực tế hệ mật công khai McEliece đề nghị chọn 1024, t = 50. Hệ mật McEliece hình thành như sau: Alice và Bob muốn truyền tin mật cho nhau bằng hệ mật McEliece. Trước tiên Alice phải hình thành khóa như sau: Quá trình hình thành khóa: Alice chọn mã tuyến tính C[n,k] có thể sửa được t lỗi. Mã này phải có thuật toán giải mã hiệu quả. Alice tạo ra ma trận sinh G cấp cho mã C. Chọn S là ma trận khả nghịch cấp. Chọn tiếp ma trận hoán vị P cấp . Tính ma trận G’ cấp : G’=SGP. Alice công khai khóa công cộng (G’, t) và giử kín khóa mật (G,P,S). Quá trình mã hóa: Bob muốn gởi thông tin mật m cho Alice, Bob sử dụng khóa công cộng (G’,t) và tiến hành mã hóa theo các bước sau: Mã hóa bản tin x ở dạng nhị phân chiều dài k. Tính véc tơ c’=xG’. Tạo ra một véc tơ ngẫu nhiên e, có trọng số t và chiều dài n. Hình thành bản mã: y=c’+e. Quá trình giải mã: Tính ma trận khả nghịch của P là P-1. Tính . Sử dụng thuật toán giải mã code C để giải mã y’ thành y”. Tính toán bản rõ: x= Chúng ta tìm hiểu rõ hơn về phần giải mã, chúng ta có: =(c’+e)P-1=(xSGP+e)P-1=xSG+e’, ở đây e’ là véc tơ có trọng số là t. Alice dùng thuật toán giải mã của mình để véc cạn các gía trị có thể của e’. Và từ đó tìm xSG và từ đây chúng ta tính x dễ dàng bằng cách nhân với ma trận nghịch đảo. Ví dụ: Chúng ta xem mã Hamming (7,4). Ma trận sinh của mã này là G, được cho như sau: giả sử Alice chọn ma trận S và P như sau: Alice tính ma trân công cộng G’: Bây giờ Bob muốn mã hóa thông điệp x=(1,1,0,1) bằng cách dùng véc tơ sai ngẫu nhiên có trọng số là 1 dạng: e=(0,0,0,0,1,0,0), và tính bản mã: Alice nhận được bản mã y, trước hết Alice tính P-1 và tính y’=yP-1, ở đây Và tính ra y’=(1000111). Alice dùng thuật toán giải mã để tìm lỗi và tìm ra lỗi ở vị trí số 7. Nên y’’=(1000110). Từ đây suy ra xS=(1000). Để giải mã Alice tính S-1, Tính xS.S-1=(1,1,0,1). Đây chính là bản rõ của Bob. Hệ mật bất đối xứng trên cơ sỡ đường cong Elliptic Lý thuyết về đường cong elliptic chúng ta đã tìm hiểu ở phần trường số hữu hạn. Bây giờ chúng ta xem ứng dụng của nó đối với hệ mật bất đối xứng. Chúng ta đi tìm hiểu hệ mật như sau. Giả sử Alice và Bob muốn trao đổi thông tin mật cho nhau trên cơ sở đường cong Elliptíc, thì Alice và Bob chọn đường cong Elliptic E với các hệ số a, b, modulo p và điểm khởi tạo G, , G có bậc là n (nG=0). Alice hình thành khóa mật và khóa công cộng qua các bước sau: Chọn d là số ngẫu nhiên làm khóa mật thỏa mãn . Công bố khóa công cộng PA=dG. Quá trình mã hóa: Bob muốn gởi thông tin mật m cho Alice, Bob thực hiện: Chọn số ngẫu nhiên . Và tính điểm Gk(x1,y1)=kG. Tính giá trị PAk(x,y)=kPA. Để mã hóa, Bob chọn tọa độ của điểm PAk để mã hóa. Ví dụ như chọn tọa độ x, và mã hóa thông điệp m: c=m.x (mod p). Gởi cặp (Gk(x1,y1), c) cho Alice. Quá trình giải mã: Nhận được cặp (Gk(x1,y1), c) từ Bob. Alice tiến hành giải mã qua các bước sau: Tính PBk(x’,y’)=dGk Chọn tọa độ x của điểm PBk và tìm phần tử nghịch đảo của x’ là và tính giá trị m bằng biểu thức: m= Chúng ta kiểm tra tính đúng đắn của hệ. Từ bước 1 của quá trình giải mã chúng ta thấy dGk=k.dG= kPA= PAk(x,y), nên x’=x. Và quá trình giải mã là đúng.