Thuật toán lượng tử Shor và Grover: Đe dọa và cơ hội cho mật mã học
Hai thuật toán lượng tử nổi tiếng nhất – Shor’s algorithm và Grover’s algorithm – đã thay đổi cách chúng ta hiểu về an toàn thông tin và khả năng tính toán. Thuật toán Shor có thể phá vỡ hệ thống mật mã khóa công khai như RSA, Diffie-Hellman và ECC trong thời gian đa thức, trong khi thuật toán Grover cung cấp tốc độ tăng lên bậc hai cho các bài toán tìm kiếm không có cấu trúc.
Thuật toán Shor: Người phá vỡ mật mã bất đối xứng
Năm 1994, Peter Shor tại AT&T Bell Labs đã phát minh ra thuật toán lượng tử đầu tiên có ứng dụng thực tế hấp dẫn: phân tích thành thừa số một số nguyên lớn N trong thời gian đa thức. Trên máy tính cổ điển, bài toán này được giải quyết tốt nhất bởi thuật toán sàng trường số chung (General Number Field Sieve) với độ phức tạp dưới mũ. Thuật toán Shor thì chỉ cần O((log N)²(log log N)(log log log N)) cổng lượng tử.
Hệ quả trực tiếp: hệ thống RSA – nền tảng của hầu hết giao thức bảo mật internet hiện nay (TLS/SSL, HTTPS, chữ ký số, mã hóa email) – trở nên vô hiệu nếu có một máy tính lượng tử đủ lớn và đủ ổn định. Shor’s algorithm cũng phá vỡ Diffie-Hellman trên trường hữu hạn và Elliptic Curve Diffie-Hellman (ECDH) vì cả hai đều dựa trên bài toán rời rạc (discrete logarithm) mà thuật toán Shor cũng giải quyết được.
Thuật toán Grover: Tăng tốc tìm kiếm không cấu trúc
Năm 1996, Lov Grover đã đưa ra thuật toán lượng tử cho bài toán tìm kiếm trong cơ sở dữ liệu không có cấu trúc. Trong khi máy tính cổ điển cần O(N) phép toán để tìm một mục trong N mục, thuật toán Grover chỉ cần O(√N). Mặc dù đây chỉ là tăng tốc bậc hai (quadratic speedup) chứ không phải tăng tốc mũ như Shor, nhưng nó có ý nghĩa lớn đối với mật mã đối xứng (symmetric cryptography).
Cụ thể, Grover’s algorithm có thể brute-force khóa AES-128 trong ~2⁶⁴ phép toán thay vì 2¹²⁸, và AES-256 trong ~2¹²⁸ thay vì 2²⁵⁶. Điều này có nghĩa là để duy trì cùng mức độ bảo mật như trước, độ dài khóa của mật mã đối xứng cần phải gấp đôi (từ 128-bit lên 256-bit, từ 256-bit lên 512-bit).
Cơ chế cốt lõi của thuật toán Shor
Thuật toán Shor bao gồm hai phần:
- Phần cổ điển: Giảm bài toán phân tích thừa số thành bài toán tìm chu kỳ (order-finding) modulo N. Chọn một số ngẫu nhiên a < N, tính gcd(a, N). Nếu không phải 1, đã tìm thấy thừa số. Nếu là 1, tìm bậc r của a modulo N (số nguyên dương nhỏ nhất sao cho aʳ ≡ 1 (mod N)).
- Phần lượng tử: Sử dụng thuật toán ước lượng pha lượng tử (Quantum Phase Estimation) để tìm bậc r. Phần này cần ~2n qubit cho thanh ghi đầu tiên và n qubit cho thanh ghi thứ hai (n = log₂ N).
Sau khi có r, nếu r chẵn và a^(r/2) ≢ -1 (mod N), thì gcd(a^(r/2) – 1, N) và gcd(a^(r/2) + 1, N) sẽ là thừa số không tầm thường của N.
Cơ chế cốt lõi của thuật toán Grover
Thuật toán Grover hoạt động thông qua một vài bước lặp lại:
- Ban đầu, chuẩn bị một siêu vị đồng nhất (uniform superposition) của tất cả trạng thái: |s⟩ = (1/√N) Σₓ |x⟩.
- Áp dụng “Grover iterate”: kết hợp oracle U_ω (phản ứng -1 cho trạng thái đúng) và phép biến đổi phản xạ (diffusion operator U_s = 2|s⟩⟨s| – I).
- Lặp lại khoảng √N/2 lần, sau mỗi lần xác suất đo được trạng thái đúng tăng lên.
- Đo bản ghi, thu được kết quả với xác suất cao.
Nhờ cách tiếp cận này, Grover đã mở ra hướng đi mới trong thiết kế mật mã đối xứng, nơi độ dài khóa cần được điều chỉnh để duy trì độ bền vững.
Trạng thái hiện tại và triển vọng
Đến năm 2026, các máy tính lượng tử hiện hữu (IBM, Google, IonQ, Rigetti) vẫn chỉ có vài chục đến vài trăm qubit vật lý với tỷ lệ lỗi cao (10⁻³ đến 10⁻⁴). Để thực hiện thuật toán Shor cho RSA-2048, ước tính cần khoảng 20 triệu qubit vật lý với tỷ lệ lỗi dưới 10⁻⁵ sau khi áp dụng quantum error correction. Đây vẫn là mục tiêu xa vời.
Tuy nhiên, cộng đồng mật mã học không chờ đợi. Tiêu chuẩn post-quantum cryptography (PQC) đã được NIST đưa ra từ năm 2022-2024, bao gồm CRYSTALS-Kyber (key encapsulation), CRYSTALS-Dilithium (chữ ký số), SPHINCS+ (chữ ký dựa trên hash) và FALCON. Các trình duyệt, hệ điều hành và thư viện mật mã đã bắt đầu triển khai các thuật toán này trên nền tảng hybrid xây dựng paralel.
Trong thực tế, các công ty công nghệ lớn như Google Cloud, AWS và Microsoft Azure đã bắt đầu cung cấp các công cụ lập lượng tử post-quantum như Quantum-Safe TLS và các API key management hỗ trợ hybrid cryptography. Đây là bước chuyển đổi quan trọng giúp các hệ thống hiện tại có thể nâng cấp dần sang bảo mật lượng tử mà không gián đoạn dịch vụ.
Trong khi đó, Grover’s algorithm cũng đòi hỏi chúng ta cập nhật các thuật toán mật mã đối xứng. Với sự tiến lên của máy tính lượng tử, lỗ hổng tiềm tàng trong mật khẩu yếu, hash function không đủ mạnh, hoặc khóa mã hóa ngắn sẽ bị khai thác nhanh hơn. Đây là lý do tại sao các tổ chức cần dịch chuyển sang mật mã hậu lượng tử ngay hôm nay.
Kết luận
Thuật toán Shor và Grover không chỉ là những kỳ quan lý thuyết – chúng là lời nhắc nhở rằng bảo mật số hiện tại có hạn sử dụng. Sự chuyển dịch sang mật mã hậu lượng tử (post-quantum cryptography) đang diễn ra ngay bây giờ. Các tổ chức cần bắt đầu kiểm kê hệ thống mật mã của mình, ưu tiên chuyển đổi các hệ thống quan trọng và theo dõi tiến độ chuẩn hóa của NIST để không bị động khi máy tính lượng tử đủ mạnh xuất hiện.
Nguồn tham khảo: Wikipedia – Shor’s algorithm, Wikipedia – Grover’s algorithm, NIST Post-Quantum Cryptography, Gidney & Ekerå – How to factor 2048-bit RSA integers
