Mã hóa RSA sẽ bị phá mã hóa vào năm 2023 bởi một máy tính lượng tử?

Khái niệm cơ bản về lượng tử

Về mặt lý thuyết, một máy tính lượng tử có thể thực hiện phân tích cực nhanh các số nguyên khổng lồ với sự trợ giúp của các thừa số nguyên tố và tìm ra cho một thuật toán mã hóa phi đối xứng trong đó có mã hóa RSA. Cho đến nay, tất cả các chuyên gia đều đồng ý rằng một máy tính lượng tử đủ lớn để bẻ RSA có thể sẽ được chế tạo không sớm hơn vài thập kỷ nữa. Thuật toán Shor [2] cần được chạy trên một máy tính lượng tử với hàng triệu qubit (bit lượng tử) để phân tích một số nguyên dài 2048 bit (thường được sử dụng làm RSA). Điều này không xảy ra trong tương lai gần vì các máy tính lượng tử tốt nhất hiện nay hoạt động ở mức 300–400 qubit, đây là kết quả của nhiều thập kỷ nghiên cứu.

Các chuyên gia bảo mật đã yêu cầu áp dụng mật mã hậu lượng tử, nghĩa là các thuật toán có khả năng chống lại các máy tính lượng tử. Các nhà nghiên cứu đã đầu tư để giải quyết vấn đề này có thể sẽ xảy ra trong tương lai. Quá trình chuyển đổi thường mất một thập kỷ hoặc hơn nữa để diễn ra suôn sẻ. Do đó, tin tức về việc RSA-2048 có thể ngừng hoạt động sớm nhất là vào năm 2023 đã đến như một tia chớp bất ngờ.

Tin tức từ Trung Quốc

Máy tính lượng tử 10 qubit đã được các nhà nghiên cứu Trung Quốc sử dụng để phân tích một 48-bit. Họ đã tính toán rằng có thể mở rộng quy mô thuật toán của họ để sử dụng với các 2048 bit bằng máy tính lượng tử chỉ có 372 qubit.

Công trình khoa học "Factoring integers with sublinear resources on a superconducting quantum processor" của các nhà mật mã Trung Quốc (Bao Yan và các cộng sự) [3] được phát triển vào ngày 23 tháng 12 năm 2022. Một bước đột phá đã được hứa hẹn bằng cách kết hợp thuật toán Schnorr [4] với một bước thuật toán tối ưu hóa gần đúng lượng tử QAOA (quantum approximate optimization algorithm) bổ sung.

 

Lược đồ được đề xuất của thuật toán phân tích số hỗn hợp.

"Fast Factoring Integers by SVP Algorithms" là tên được đặt cho bài báo của Claus Peter Schnorr, được xuất bản lần đầu tiên vào năm 2021. Thuật toán của Schnorr được sử dụng để phân tích các số nguyên được cho là hiệu quả hơn bằng cách sử dụng các tính toán cổ điển. Nhóm các nhà nghiên cứu Trung Quốc đề xuất áp dụng tối ưu hóa lượng tử ở giai đoạn tính toán cần nhiều phép tính nhất trong công việc của họ.

Chẳng hạn, IBM hiện đang sử dụng một máy tính lượng tử có quy mô khoảng 400 qubit. Mặc dù thực tế là nhu cầu thay thế hệ thống mật mã Internet đột ngột một ngày nào đó không còn là điều gì quá xa trong tương lai, nhưng nó chưa thực sự được xem xét một cách nghiêm túc.

Hệ thống 'IBM Osprey' Processor Dario Gil, Jay Gambetta và Dario Gil giữ 433 qubit mới. Các 433 qubit mới của "IBM Osprey" được giữ bởi Dario Gil, Jay Gbetta và Jerry Chow.

Câu hỏi mở

Cộng đồng toán học đã phản ứng với sự hoài nghi nhất định đối với thuật toán của Schnorr. Trong phần mô tả nghiên cứu đã được xem xét kỹ lưỡng và không đứng vững, tác giả tuyên bố rằng "nó sẽ phá hệ thống mật mã RSA." Chẳng hạn, Bruce Schneier, một nhà mật mã học nổi tiếng, đã nói rằng nó "hoạt động tốt với các mô-đun nhỏ hơn có cùng bậc giống như các mô-đun mà nhóm nhà khoa học Trung Quốc đã thử nghiệm nhưng lại thất bại ở kích thước lớn hơn." Không ai thành công trong việc chứng minh rằng thuật toán này có thể mở rộng trong thực tế.

Mặc dù việc áp dụng tối ưu hóa lượng tử cho phần "nặng nhất" của thuật toán có vẻ là một ý tưởng hay, nhưng các chuyên gia tính toán lượng tử vẫn nghi ngờ rằng tối ưu hóa QAOA liệu có hiệu quả trong việc giải quyết bài toán tính toán này hay không. Có thể sử dụng máy tính lượng tử ở đây, nhưng nó có thực sự giúp tiết kiệm thời gian không? Bản thân các tác giả của công trình [3] đã cẩn thận đề cập đến điểm quan trọng đáng ngờ này ở phần cuối của báo cáo của họ, trong phần kết luận: Cần chỉ ra rằng việc tăng tốc lượng tử của thuật toán là chưa rõ do sự hội tụ không rõ ràng của QAOA.

Do đó, có vẻ như ngay cả khi người dùng triển khai thuật toán lai ghép này trên hệ thống lượng tử truyền thống, việc tìm kiếm RSA cũng sẽ mất nhiều thời gian như với máy tính truyền thống. Vẫn còn một chặng đường dài để phá vỡ RSA lượng tử, tốc độ tăng tốc lượng tử vẫn chưa được biết.

Đáng chú ý, ngoài số lượng qubit, còn có các thông số quan trọng khác của máy tính lượng tử, bao gồm mức độ nhiễu và lỗi cũng như số lượng cổng. Ngay cả những máy tính hứa hẹn nhất của năm 2023-2024 cũng không phù hợp để chạy thuật toán Trung Quốc ở quy mô cần thiết khi đánh giá bằng cách kết hợp các tham số cần thiết.

Bài học thực tế

Trong khi cuộc cách mạng mật mã một lần nữa bị trì hoãn, hai vấn đề liên quan đến bảo mật đã được thảo luận xung quanh nghiên cứu này. Các kỹ thuật đại số mới như thuật toán Schnorr cần được nghiên cứu cẩn thận trước khi chọn một thuật toán kháng lượng tử trong số rất nhiều đề xuất cho một "tiêu chuẩn hậu lượng tử". Điều này cũng đòi hỏi phải chắc chắn tăng mức độ ưu tiên của các dự án để chuyển đổi sang mật mã hậu lượng tử.

Cập nhật tin tức công nghệ mới nhất tại fanpage Công nghệ & Cuộc sống