Bài viết này giới thiệu một cách sơ bộ về Thuật toán lượng tử Shor: phá mã RSA
Phải chăng, gắn liền với mật mã là quyền lực, gắn liền với phá mã là tương lai vô tiền khoáng hậu của loài người; - ad -
PHÁ MÃ RSA - THUẬT TOÁN MILLER
RSA một thuật toán theo Hệ mật mã khóa công khai, đặt tên theo ba người sáng chế ra nó: Rivest, Shamir và Adleman. RSA được sử dụng rất rộng rãi trong thư tín mã hóa ngày nay.
Trước đó, vào năm 1973, Clifford Cocks, một nhà toán học người Anh đã mô tả một thuật toán tương tự. Với năng lực điện toán tại thời điểm đó thì thuật toán này được cho là không khả thi và chưa bao giờ được thực nghiệm. Tuy nhiên, phát minh này chỉ được công bố vào năm 1997 vì được xếp vào loại tuyệt mật.
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ý.
Victor Saul Miller, là một nhà toán học người Mỹ tại CCR (Trung tâm Nghiên cứu Truyền thông) thuộc Viện Phân tích Quốc phòng ở Princeton, New Jersey, Hoa Kỳ; đã đề xuất thuật toán Miller phá mã RSA theo phương pháp phân tích thừa số nguyên tố.
Thuật toán Miller phá mã RSA gồm các bước sau:
- Bước 1: Chọn một số ngẫu nhiên a < N.
- Bước 2: Tìm ƯCLN(a, N), có thể dùng thuật toán Ơclit cho bước này.
- Bước 3: Nếu ƯCLN(a, N) ≠ 1, thì p = ƯCLN(a, N) và q = N / p.
- Bước 4: Nếu không thì tìm chu kỳ r của hàm f(x) = a^x mod N, tức là f(x+r) = f(x).
- Bước 5: Nếu r lẻ, thì quay lại bước đầu tiên. Nếu r chẵn: r2 = r/2 là 1 số nguyên
- Bước 6: Nếu a^r2 ≡ −1 (mod N), thì quay lại bước đầu tiên.
- Bước 7: tìm được: p = ƯCLN(a^r2 + 1, N) và q = ƯCLN(a^r2 - 1, N).
p và q chính là các chìa khóa để giải mã công khai N
Nhưng, bước 4 tìm chu kỳ r của hàm f(x) = a^x mod N tiêu tốn rất nhiều tài nguyên tính toán. Với các số nửa nguyên tố trong mã hóa RSA hiện đại thường có 200 chữ thập phân hay nhiều hơn nữa. Với những số nửa nguyên tố lớn như vậy thì thuật toán Miller thường cần lượng thời gian để phân tích là lớn, đến mức cần tới hàng nghìn năm với năng lực điện toán của một Nền văn minh cấp 1 trong Thang đo Kardashev để thực thi - trong khi Trái Đất hiện đang ở cấp 0.75, tức là RSA vẫn an toàn.
PHÁ MÃ RSA - THUẬT TOÁN LƯỢNG TỬ SHOR
Tuy nhiên, khi Shor đề xuất thuật toán lượng tử Shor, áp dụng thuật toán Miller trên máy tính lượng tử có thể thực hiện trong thời gian ngắn hơn nhiều, cho phép về lý thuyết có thể phá mã RSA với tốc độ lượng tử, một cánh cửa mở ra chân trời mới đã xuất hiện, điện toán lượng tử ứng dụng, truyền cảm hứng cho các nhà sáng chế mới tìm kiếm kho báu trong miền đất của tri thức, cũng đồng thời kích hoạt các hoạt động sáng chế mật mã hậu lượng tử - mật mã chống lại điện toán lượng tử.
Thuật toán lương tử Shor cơ bản phát triển từ Thuật toán Miller phá mã RSA như đã nêu ở trên. Trong đó tập trung giải quyết Bước 4: tìm chu kỳ r của hàm f(x) = a^x mod N, tức là f(x+r) = f(x).
Ý tưởng chính là sử dụng biến đổi Furier Lượng tử cho hàm f(x) để tìm chu kỳ r;
Chúng ta đều biết rằng, hoặc có thể bạn chưa biết, biến đổi Furier cho phép phân tích tín hiệu trong miền tần số, tần số chính là nghịch đảo của chu kỳ; bởi thế biến đổi Furier Lượng tử của hàm f(x) ngay lập tức cho biết chu kỳ r;
biến đổi Furier Lượng tử hàm f(x), có bản chất là coi hàm f(x) là một tín hiệu số m bít có thể mang N = 2^m giá trị khác nhau, biến đổi trên miền phức bằng ma trận [n, n] (với n = logN = m*log2); mỗi 1 qubit chịu trách nhiệm chứa chấp thông tin của 1 phần tử; 1 qubit đại diện cho mọi khả năng có thể xảy ra - thay vì 0:1 của 1 bit thông thường; và có thể được triển khai vật lý dưới dạng trạng thái của 1 hạt cơ bản với phương trình Schrödinger của nó;
Để triển khai thuật toán Shor trong miền giá trị N cần khoảng O((n^2)(log n)(log log n)) qubit
Tức là để triển khai:
- phá mã RSA m=512 bít cần 17.672 Qubit,
- phá mã RSA m=1024 bít cần 93.656 Qubit,
- phá mã RSA m=4096 bít cần 2.303.108 Qubit,
Sycamore
Ngày 23/10/2019, CEO Google Sundar Pichai đích thân viết bài giới thiệu về máy tính lượng tử dành cho tương lai. Ông khẳng định Sycamore chỉ mất 200 giây để giải xong bài toán khó tới mức siêu máy tính mạnh nhất thế giới hiện nay phải mất hàng nghìn năm mới có thể giải quyết. Sycamore làm máy tính lượng tử đầu tiên chiếm được "ưu thế lượng tử" và có 53 qubit (được thiết kế với 54 qubit nhưng bị hỏng 1 qubit).
nếu lấy đơn vị tính là 1 máy Sycamore 53 Qubit (sau đây tạm gọi là S53Q), thì tức là để triển khai:
- phá mã RSA m= 512 bít cần 333 máy S53Q,
- phá mã RSA m=1024 bít cần 1.767 máy S53Q,
- phá mã RSA m=4096 bít cần 43.455 máy S53Q,
Nếu bạn ước tính được giá thành của 1 máy S53Q, thì bạn biết rồi đấy, sẽ cần 43.455 máy như thế để cố tình giải mã 1 bức email bạn vừa gửi đi, bởi vì RSA bây giờ nói chung là dùng 4096 bít. Google không công bố chi phí phát triển Sycamore 53Q nhưng Ad thì ước tính mỗi qubit trong trong máy đó có giá thành khoảng 100 triệu đô la, còn trị giá không định lượng được 
Và đấy chỉ cần thế thôi, thuật toán chuẩn đã có, S53Q cho thấy tính khả thi, chỉ cần rót đủ nguồn lực là a-lê-hấp, một tương lai sáng lạn hiện ra thay vì tiêu tốn nhiều tỉ năm để phá mã RSA theo các phương án điện toán cũ bất khả thi.
Các tính toán trên đây được ước tính sơ bộ cho việc triển khai thuật toán Shor, tuy nhiên, trong tương lai có thể có nhiều thuật toán khác hiệu quả tốt hơn nữa được phát minh ra. Tuy nhiên, với cơ sở lý thuyết, và thành tựu của máy tính lượng tử đầu tiên, chúng ta hoàn toàn có quyền hứng khởi về một tương lai điện toán lượng tử với năng lực vô tiền khoáng hậu chưa từng có, một thời đại mới của loài người.
Thông tin thêm về RSA các bạn có thể xem thêm trên wiki: https://vi.wikipedia.org/wiki/RSA_(mã_hóa)
Thông tin thêm về thuật toán Shor các bạn có thể xem thêm trên wiki: https://vi.wikipedia.org/wiki/Thuật_toán_Shor hoặc tham khảo các tài liệu chuyên ngành; để hiểu sâu thuật toán Shor, cần thêm 1 cơ số kiến thức cơ bản về cơ học lượng tử, nếu được ủng hộ và có thời gian thì ad sẽ soạn thêm 1 bài về chủ đề đó.
[Xem thêm: Seri Mật Mã]
Phần 1: Phá mã Enigma - Alan Turing
Video dưới đây giới thiệu kỹ hơn nội dung thuật toán Shor phá mã RSA, do PBS thực hiện trong seri Vô hạn:
