Mật mã sau khi có máy tính lượng tử
Từ năm 2006 đến nay, người ta đã tổ chức hội nghị quốc tế thường niên về PQCrypt. Bài báo sẽ giới thiệu sơ bộ về Mật mã sau khi có máy tính lượng tử và sự cần thiết phải đầu tư nghiên cứu về vấn đề này.
Những thay đổi của mật mã sau khi có máy tính lượng tử
Có một dự đoán là sau 15 năm nữa người ta có thể kiến thiết thành công một máy tính lượng tử lớn. Báo chí sẽ đăng trên trang nhất thông báo rằng tất cả các thuật toán khóa công khai đã được sử dụng để bảo mật trên Internet đã bị phá khiến người sử dụng hết sức lo lắng. Thực chất, điều gì sẽ xảy ra đối với mật mã?
Có thể, sau khi thấy rằng các máy tính lượng tử phá hủy các hệ mật RSA, DSA và ECDSA, người sử dụng Internet sẽ đi đến suy nghĩ rằng mật mã đã đến hồi cáo chung; sẽ không có hy vọng dùng phương pháp xáo trộn thông tin để làm cho người khác không hiểu được và những kẻ tấn công không làm giả mạo được; việc lưu trữ và truyền đi thông tin một cách an toàn có nghĩa là sử dụng các “lá chắn” vật lý để ngăn chặn những kẻ tấn công khỏi thấy được thông tin- ví dụ, giấu các USB bên trong một va- ly được khóa và xích vào cổ tay một người mang tin tin cậy.
Tuy nhiên, trong tương lai gần sẽ thấy rằng, rất khó có bước phát triển đột ngột từ “các máy tính lượng tử phá hủy RSA, DSA và ECDSA” thành “các máy tính lượng tử tiêu hủy mật mã học”. Hiện tại vẫn còn nhiều lớp các hệ thống mật mã quan trọng vượt qua được các hạn chế của RSA, DSA và ECDSA, ví dụ như:
- Mật mã dựa trên hàm băm (Hash - based cryptography). Ví dụ, hệ chữ ký khóa công khai cây- băm của Merkle (1979), được xây dựng dựa trên ý tưởng chữ ký của Lamport và Diffie.
- Mật mã dựa trên mã hóa (code - based cryptography). Ví dụ, hệ mã khóa công khai dựa trên mã Goppa ẩn của McEliece (1978).
- Mật mã dựa trên lưới (Lattice - based cryptography). Ví dụ là hệ mã khóa công khai “NTRU” của Hoffstein - Pipher - Silverman (1998).
- Mật mã của các phương trình bậc hai nhiều biến (Multivariate- quadratic- equations cryptography). Một trong những ví dụ là hệ chữ ký khóa công khai “HFEv- ” của Patarin (1996), nó tổng quát hóa một đề xuất của Matsumoto và Imai.
- Mật mã khóa bí mật (Secret - key cryptography). Ví dụ mã pháp “Rijndael” của Daemen- Rijmen (1998), sau này được gọi là “AES”.
Tất cả các hệ thống này được tin là kháng lại các máy tính kinh điển và các máy tính lượng tử. Chưa ai chứng minh được là thuật toán Shor dùng cho máy tính lượng tử phá được RSA, DSA, và ECDSA lại có khả năng phá được một trong các hệ mật nêu trên. Một thuật toán lượng tử khác, “thuật toán của Grover”, có các tác động nào đó đối với các hệ mật này, nhưng không đủ nhanh như thuật toán Shor nên các nhà lập mã có thể vô hiệu hóa nó bằng cách chọn kích thước khóa lớn hơn.
Liệu có một tấn công mạnh hơn lên các hệ thống này không? Điều đó cũng có thể xảy ra. Đó là lý do tại sao cộng đồng đã đầu tư một lượng lớn thời gian và kinh phí vào thám mã. Đôi khi các nhà mã thám tìm ra được một tấn công mạnh và họ chỉ ra một hệ mật nào đó là không áp dụng được vào mật mã. Ví dụ, mỗi một lựa chọn tiện lợi về tham số cho hệ mật xếp ba lô của Merkle- Hellman đều dễ dàng bị phá. Cũng có khi các nhà thám mã tìm thấy các tấn công không có sức mạnh như vậy, nhưng để đảm bảo an toàn vẫn phải dùng các khóa có kích thước lớn hơn. Đôi khi các nhà thám mã nghiên cứu hệ mật nhiều năm mà không tìm thấy tấn công tốt hơn nào, và cộng đồng mật mã bắt đầu hình thành niềm tin rằng tấn công có thể tốt nhất đã được tìm thấy - hoặc ít nhất là những kẻ tấn công ở thế giới thực sẽ không thể đi đến một kết quả nào khả dĩ hơn.
Dưới đây là 3 ví dụ về tấn công phân tích số chống lại RSA:
- Năm 1978: Bài báo nguyên thủy của Rivest, Shamir và Adleman đã nhắc tới một thuật toán mới, “sàng tuyến tính” của Schroeppel, nó phân tích số n là modulus RSA bất kỳ và có nghĩa là phá vỡ RSA– bằng cách sử dụng 2(1+o(1))(lg n)1/2(lglg n)1/2 phép toán đơn giản. Ở đây lg = log2. Nếu chọn n có ít nhất (0,5+o(1))1b2/lgb bit sẽ buộc sàng tuyến tính sử dụng ít nhất 2b phép toán.
- Năm 1988: Pollard đưa ra một thuật toán phân tích số mới, “sàng trường số”. Thuật toán này, sau này được tổng quát hóa bởi Buhler, Lenstra và Pomerance, phân tích n là modulus RSA bất kỳ bằng cách dùng 2(1,9...+o(1))(lgn)1/3(lglg n)2/3 phép toán đơn giản. Nếu chọn n có ít nhất (0,016...+o(1))1b3/(lgb)2 thì sẽ buộc sàng trường số sử dụng ít nhất 2b phép toán. Ngày nay, sau 20 năm, các thuật toán phân tích tốt nhất được biết đến đối với các máy tính kinh điển vẫn sử dụng 2(constant...+o(1))(lgn)1/3(lglg n)2/3phép toán. Có một số cải tiến nào đó về hằng số và chi tiết của o(1); nhưng người ta đoán rằng 1/3 là tối ưu và việc chọn n có khoảng b3 bit sẽ kháng lại tất cả các tấn công có thể bởi các máy tính kinh điển.
- Năm 1994: Shor đưa ra thuật toán phân tích n là RSA modulus bất kỳ bằng cách dùng (lg n)2+o(1)trên máy tính lượng tử có kích thước (lg n)1+o(1).
Để so sánh, hãy xét các tấn công lên một hệ mật khóa công khai khác có từ 30 năm trước, đó là hệ mã hóa dựa trên mã Goppa ẩn của
McEliece. Bài báo ban đầu của McEliece đã trình bày một tấn công đã phá được các mã có “độ dài n” và “số chiều n/2” bằng cách dùng 2(0,5+o(1))n/lg n phép toán. Việc tấn công này sử dụng 2b phép toán đồng nghĩa với việc chọn n ít nhất bằng (2+ o(1))b lgb. Một số bài báo sau đó đã rút gọn số các phép toán của tấn công bởi một nhân tử lớn, khoảng nlgn= 2(lgn)2, nhưng (lgn)2 là nhỏ hơn nhiều so với 0,5n/lgn nếu n lớn; tấn công đã được cải tiến vẫn sử dụng 2(0,5+o(1))n/lgn phép toán. Các máy tính lượng tử dường như không tạo ra khác biệt nhiều, ngoại trừ việc rút gọn hằng số 0,5.
Nếu hệ mật của McEliece đứng vững chống lại các tấn công như vậy, thì tại sao chúng ta không sử dụng nó thay cho RSA? Câu trả lời ngắn gọn là tính hiệu quả, đặc biệt là kích thước khóa. Khóa công khai của McEliece sử dụng khoảng n2/4.b2(lgb)2 bit, trong khi khóa công khai RSA - với giả thiết rằng sàng trường số là tối ưu và bỏ qua mối đe dọa của máy tính lượng tử - sử dụng khoảng (0,016...)b3 /(lgb)2bit. Nếu b là cực lớn thì b2 + o(1) của McEliece sẽ nhỏ hơn nhiều so với b3 + o(1) bit cho RSA; nhưng các mức an toàn của thế giới thực chẳng hạn như b = 128 cho phép các kích thước khóa của RSA có khoảng vài nghìn bit, trong khi các kích thước khóa McEliece gần tới 1 triệu bit.
Mật mã sau khi có máy tính lượng tử không phải là mật mã lượng tử, nó là mật mã thông thường trong điều kiện của máy tính lượng tử. Vì vậy quá trình thiết kế, phân tích và tối ưu hóa mật mã kinh điển và mật mã sau khi có máy tính lượng tử đều có thể diễn ra theo kịch bản sau:
- Các nhà mật mã học thiết kế ra các hệ mật để xáo trộn và giải mã dữ liệu.
- Các nhà thám mã phá vỡ một số hệ mật.
- Các nhà thiết kế và những người cài đặt thuật toán tìm các hệ mật nhanh nhất mà không bị phá vỡ.
Sự khác nhau cơ bản là mật mã sau lượng tử phải đối mặt với những thách thức của máy tính lượng tử. Ví dụ, đối với mật mã kinh điển các nhà thám mã sử dụng sàng trường số để phân tích số, thuật toán Lenstra - Lenstra-Lovasz để rút gọn cơ sở lưới, các thuật toán Faugère để tính cơ sở Grobner và nhiều thuật toán tấn công thú vị khác. Đối với mật mã sau khi có máy tính lượng tử, các nhà thám mã đã có sẵn tất cả các công cụ đó, cộng thêm các thuật toán lượng tử, nổi bật là thuật toán Shor và thuật toán Grover.
Các thách thức trong mật mã sau khi có máy tính lượng tử
Cũng như các hệ mật thông thường, mật mã sau khi có máy tính lượng tử phải đảm bảo về tính hiệu quả, độ tin cậy và tính hữu dụng trong những điều kiện mới.
Tính hiệu quả
Các hệ chữ ký số đường cong ellip với các chữ ký O(b)- bit và các khóa O(b)- bit dường như cung cấp độ an toàn b bit chống lại các tấn công từ máy tính kinh điển. Các thuật toán ký
và các thuật toán kiểm tra tốt nhất chiếm thời gian b2+o(1).
Các hệ chữ ký khóa công khai của mật mã sau khi có máy tính lượng tử có thể đạt được các mức hiệu suất tương tự hay không? Hai ví dụ ở trên về các hệ chữ ký với các chữ ký có độ dài b2+o(1) và b3+o(1) chắc chắn không còn đáp ứng. Có nhiều đề xuất khác cho các hệ chữ ký của mật mã sau khi có máy tính lượng tử, nhưng chưa có một đề xuất nào có các chữ ký O(b)- bit với các khóa O(b) bit cùng thời gian ký và kiểm tra đều là đa thức.
Có thể một số người không quan tâm đến tính hiệu quả của mật mã, nhưng đối với các máy chủ Internet luôn xử lý hàng nghìn máy trạm mỗi giây thì điều đó lại rất quan trọng. Ngày nay, nếu bạn tạo một kết nối an toàn tới https://www.google.com thì Google chuyển hướng trình duyệt của bạn về http://www.google.com một cách có chủ ý tắt bảo vệ mật mã đi. Google có một số các trang web được bảo vệ mật mã nhưng rõ ràng không thể bảo vệ các trang web được sử dụng nhiều nhất. Nếu Google đã có những khó khăn bởi tốc độ chậm của phần mềm mật mã hiện nay, chắc chắn nó sẽ có khó khăn không ít hơn với tốc độ của phần mềm mật mã sau khi có máy tính lượng tử.
Các ràng buộc về không gian và thời gian luôn đặt ra các yêu cầu nghiên cứu cho các nhà mật mã học và sẽ tiếp tục đặt ra các thách thức sau khi có máy tính lượng tử. Hoạt động nghiên cứu trong mật mã đã tạo ra nhiều bước ngoặt quan trọng, và người ta có thể hy vọng rằng các nỗ lực nghiên cứu được tăng cường trong mật mã sau khi có máy tính lượng tử sẽ tiếp tục tạo ra các đột phá ấn tượng.
Độ tin cậy
Cả hệ chữ ký khóa công khai Cây - băm của Merkle và hệ mã khóa công khai dựa trên mã Goppa của McEliece đều đã được đề xuất trên 30 năm trước đây và về thực chất vẫn không bị phá vỡ bất chấp có các nỗ lực thám mã.
Nhiều dự tuyển mới khác là mật mã dựa trên hàm băm, mật mã dựa trên từ mã, mật mã nhiều biến bậc 2 và mật mã dựa trên lưới ... đã tạo ra sự đa dạng cho mật mã sau khi có máy tính lượng tử. Có thể một số hệ mật mới sẽ bị phá nếu như nhà thám mã có thời gian để xem xét chúng.
Người ta có thể vẫn sử dụng các hệ mật kinh điển đã trải qua nhiều năm xem xét. Nhưng thường thì người dùng mong muốn sử dụng các hệ mật mới hơn, nhanh hơn, gọn hơn mà có ưu thế hơn về tính hiệu quả của mật mã.
Để xây dựng niềm tin vào các hệ mật này, người sử dụng cần tin chắc rằng các nhà thám mã đã có thời gian để nghiên cứu các tấn công lên các hệ mật đó mà chưa có kết quả. Các nhà thám mã, đến lượt mình, cần làm quen với mật mã sau khi có máy tính lượng tử và kinh nghiệm thám mã mới.
Tính hữu dụng
Hệ mã khóa công khai RSA đã bắt đầu không khác một hàm một chiều có cửa sập, “lập phương modulo n”. Nhưng người ta không thể sử dụng một cách đơn thuần một hàm một chiều có cửa sập như một hàm mã hóa an toàn. Mã hóa RSA hiện đại không đơn thuần là phép lập phương một thông báo theo modulo n; trước hết, nó cần phải ngẫu nhiên hóa và đệm (pad) thông báo. Hơn thế nữa, để xử lý các thông báo dài, nó mã hóa một chuỗi ngẫu nhiên ngắn thay cho thông báo, và sử dụng chuỗi ngẫu nhiên này như là khóa cho một mã pháp đối xứng để bảo mật và xác thực thông báo ban đầu. Hạ tầng cơ sở xung quanh RSA này đã mất nhiều năm để phát triển, với nhiều khó khăn, chẳng hạn như chuẩn đệm dữ liệu
PKCS#1 v1.5” đã bị phá bởi Bleichenbacher vào năm 1998.
Thậm chí nếu hàm mã hóa an toàn đã được định nghĩa và chuẩn hóa, nó cần các cài đặt phần mềm và có thể cả các cài đặt phần cứng thích hợp để tích hợp vào nhiều dạng ứng dụng. Những người thực thi cài đặt cần phải thận trọng không chỉ để đạt được tính chuẩn xác và tốc độ mà cũng cần tránh các rò rỉ kênh kề. Vài năm trước đây, một số cài đặt của RSA và AES đã bị phá bởi các tấn công cache - timing.
Đã có những tài liệu mô tả các kỹ thuật đệm và ngẫu nhiên hóa cho một số hệ mật của mật mã sau khi có máy tính lượng tử, nhưng còn nhiều vấn đề cần phải nghiên cứu tiếp. Mật mã sau khi có máy tính lượng tử, giống như phần còn lại của mật mã học, cần các hệ pha trộn hoàn chỉnh, cần các chuẩn đã được chi tiết hóa và các cài đặt có tốc độ nhanh và không bị lộ lọt thông tin.
Kết luận
Chúng ta hãy xem xét viễn cảnh: Một số hệ mật, chẳng hạn như RSA với khóa 4 nghìn bit, được tin là kháng lại các tấn công bởi các máy tính kinh điển lớn, nhưng không kháng lại các tấn công bởi các máy tính lượng tử lớn. Một số hệ mật khác, chẳng hạn như mã hóa McEliece với khóa 4 triệu bit, được tin là kháng lại các tấn công bởi các máy tính kinh điển lớn và các tấn công bởi các máy tính lượng tử lớn.
Vậy tại sao chúng ta cần phải quan tâm ngay từ bây giờ về hiểm họa đối với mật mã của các máy tính lượng tử? Tại sao không tiếp tục tập trung vào RSA và ECDSA? Nếu ai đó công bố kiến thiết thành công một máy tính lượng tử lớn sau đây 15 năm nữa thì tại sao khi đó không đơn thuần chuyển về dùng McEliece?
Ở đây sẽ đưa ra 3 câu trả lời - ba lý do quan trọng rằng tại sao cộng đồng mật mã đã bắt đầu tập trung sự chú ý vào mật mã sau khi có máy tính lượng tử:
- Cần thời gian để cải tiến tính hiệu quả PQCrypt.
- Cần thời gian để xây dựng niềm tin vào PQCrypt.
- Cần thời gian để hoàn thiện tính hữu dụng của PQCrypt.
