Thuật toán Shor và mối đe dọa lượng tử với mật mã đường cong elliptic

Thuật toán Shor, công bố năm 1994, chứng minh rằng một máy tính lượng tử đủ mạnh có thể giải bài toán phân tích nhân tử và bài toán logarit rời rạc trong thời gian đa thức, phá vỡ hoàn toàn RSA, Diffie–Hellman và mật mã đường cong elliptic mà không ảnh hưởng đến bảo mật của các sơ đồ dựa trên mạng lưới như LWE và Kyber.

Giới thiệu

Bài viết này phân tích thuật toán Shor – phát kiến của Peter Shor (1959–) tại Bell Labs năm 1994 được coi là một trong những kết quả lý thuyết có ảnh hưởng thực tiễn sâu rộng nhất trong lịch sử khoa học máy tính. Thuật toán Shor chứng minh rằng nếu có một máy tính lượng tử với đủ qubit chất lượng cao, bài toán phân tích nhân tử số nguyên lớn và bài toán logarit rời rạc – nền tảng của RSA, Diffie–Hellman và mật mã đường cong elliptic – có thể giải trong thời gian đa thức. Trong thế giới mà một trong những cơ sở hạ tầng bảo mật quan trọng nhất của internet dựa hoàn toàn vào độ khó của hai bài toán đó, Shor’s algorithm đặt ra một mối đe dọa tiềm tàng có quy mô chưa từng có.

Tầm quan trọng của thuật toán Shor không chỉ nằm ở kết quả kỹ thuật mà ở những gì nó tiết lộ về bản chất của bảo mật mật mã học: toàn bộ RSA, Diffie–Hellman và ECC – các hệ thống đã bảo vệ hầu hết giao tiếp điện tử trong nhiều thập kỷ – dựa trên giả định rằng một mô hình tính toán cụ thể (máy tính cổ điển Turing) không thể giải hiệu quả một số bài toán nhất định. Thuật toán Shor chứng minh giả định này là sai trong mô hình tính toán mở rộng hơn (máy tính lượng tử), buộc cộng đồng mật mã phải tìm kiếm các bài toán khó hơn – khó ngay cả với mô hình tính toán mạnh nhất có thể hình dung – làm nền tảng mới cho bảo mật. Đó là nguồn gốc của bài toán LWE, CRYSTALS-Kyber và toàn bộ ngành mật mã hậu lượng tử mà series này đề cập.

Bài viết này xây dựng từ nền tảng điện toán lượng tử cần thiết, qua cơ chế thuật toán Shor và phân tích cụ thể cho RSA và ECC, đến trạng thái hiện tại của điện toán lượng tử, chiến lược tấn công thực tế và lý do tại sao LWE/Module-LWE không bị ảnh hưởng. Mục tiêu là cung cấp hiểu biết đủ sâu để đánh giá đúng mức độ thực sự của mối đe dọa và lý do chọn lọc của Signal Protocol trong việc tích hợp Kyber vào PQXDH.

Nền tảng điện toán lượng tử

Để hiểu thuật toán Shor, cần nắm tối thiểu bốn khái niệm của điện toán lượng tử: qubit và chồng chập, vướng víu lượng tử, phép biến đổi lượng tử và đo lường. Phần này trình bày các khái niệm ở mức đủ cho mục đích hiểu thuật toán Shor, không đi sâu vào cơ học lượng tử đầy đủ.

Qubit, chồng chập và sức mạnh tính toán song song

Bit cổ điển có hai trạng thái: 0 hoặc 1. Qubit (quantum bit) tổng quát hóa điều này bằng cơ học lượng tử: trạng thái của một qubit là một vector đơn vị trong không gian phức hai chiều, thường ký hiệu là |ψ⟩ = α|0⟩ + β|1⟩ trong đó α, β là số phức thỏa mãn |α|² + |β|² = 1. Khi đo qubit, kết quả là 0 với xác suất |α|² và 1 với xác suất |β|² – sau khi đo, qubit sụp đổ (collapse) về trạng thái tương ứng. Trước khi đo, qubit đồng thời ở chồng chập (superposition) của cả hai trạng thái.

Hệ n qubit có không gian trạng thái là không gian tích tensor n chiều với 2^n trạng thái cơ sở: |ψ⟩ = Σ{x ∈ {0,1}^n} α_x |x⟩_ với Σ|α_x|² = 1. Điều này có nghĩa hệ n qubit có thể đồng thời ở chồng chập của 2^n trạng thái cơ sở – với n = 300, đây là số lớn hơn số nguyên tử trong vũ trụ quan sát được. Sức mạnh tính toán của máy tính lượng tử đến từ khả năng áp dụng biến đổi lượng tử trên toàn bộ chồng chập 2^n trạng thái đồng thời trong một thao tác – dạng song song hóa vô song mà máy tính cổ điển không thể sánh kịp.

Tuy nhiên, có một giới hạn quan trọng: đo lường phá hủy chồng chập. Dù hệ đang ở chồng chập của 2^n trạng thái, đo lường chỉ cho một kết quả cụ thể với xác suất |α_x|². Không thể đọc ra tất cả 2^n giá trị cùng lúc. Nghệ thuật thiết kế thuật toán lượng tử là sắp xếp biên độ chồng chập sao cho trạng thái mong muốn (đáp án đúng) có biên độ lớn và các trạng thái không mong muốn bị triệt tiêu (giao thoa hủy, destructive interference) khi đo lường – đây là kỹ thuật gọi là tăng cường giao thoa (constructive interference) và triệt tiêu giao thoa (destructive interference).

Biến đổi lượng tử Fourier và bài toán tìm chu kỳ

Biến đổi lượng tử Fourier (QFT – Quantum Fourier Transform) là thành phần trung tâm của thuật toán Shor. QFT là phiên bản lượng tử của biến đổi Fourier rời rạc (DFT), ánh xạ cơ sở tính toán sang cơ sở Fourier. QFT trên N chiều định nghĩa bởi:

QFT|j⟩ = (1/√N) Σ_{k=0}^{N-1} e^(2πijk/N) |k⟩

QFT có thể được thực hiện trên máy tính lượng tử với O(log²N) phép cổng lượng tử – so với O(N log N) của FFT cổ điển. Điều này không có nghĩa QFT nhanh hơn FFT (vì FFT đã chạy trên N điểm còn QFT chỉ cần log N qubit), nhưng có nghĩa QFT cho phép thực hiện biến đổi Fourier trên chồng chập của N trạng thái trong thời gian O(log²N).

Bài toán tìm chu kỳ (period finding) là bài toán QFT giải quyết hiệu quả: cho hàm f: Z → Z có chu kỳ r (tức là f(x + r) = f(x) cho mọi x), hãy tìm r. Thuật toán lượng tử giải bài toán này như sau: chuẩn bị chồng chập đồng đều của tất cả đầu vào |x⟩; tính f(x) vào thanh ghi thứ hai (entangle hai thanh ghi); đo thanh ghi thứ hai (sụp đổ thanh ghi đầu tiên về chồng chập của tất cả x có cùng giá trị f(x)); áp dụng QFT lên thanh ghi đầu tiên; đo và lấy kết quả – với xác suất cao, kết quả gần bội số của N/r, cho phép suy ra r bằng phân số tiếp liên (continued fractions). Toàn bộ quá trình cần O(log³N) phép cổng lượng tử – thời gian đa thức trong độ dài bit của N. Đây là bước đột phá: tìm chu kỳ hàm theo cách cổ điển cần thời gian O(√r) phép tính (tương đương tấn công sinh nhật) – theo cấp số mũ khi r lớn. QFT giảm từ cấp số mũ về đa thức nhờ giao thoa lượng tử.

Vướng víu lượng tử và vai trò trong tính toán

Vướng víu lượng tử (quantum entanglement) là hiện tượng hai hay nhiều qubit có trạng thái không thể mô tả độc lập với nhau. Trạng thái Bell (|00⟩ + |11⟩)/√2 là ví dụ đơn giản: đo qubit đầu tiên cho kết quả 0 hay 1 với xác suất bằng nhau, nhưng bất kể kết quả là gì, đo qubit thứ hai ngay lập tức cho cùng kết quả – dù hai qubit có thể cách xa nhau về mặt vật lý.

Trong thuật toán Shor, vướng víu được sử dụng để liên kết thanh ghi đầu vào và thanh ghi hàm: sau khi tính f(x) cho tất cả x đồng thời, hai thanh ghi bị vướng víu – biết giá trị của thanh ghi hàm xác định ngay chồng chập nào của thanh ghi đầu vào còn lại. Khi đo thanh ghi hàm và nhận một giá trị cụ thể y = f(x₀), thanh ghi đầu vào sụp đổ về chồng chập đồng đều của tất cả x thỏa mãn f(x) = y – tức là tất cả các phần tử trong một lớp tương đương modulo chu kỳ r. Đây là bước chuẩn bị hoàn hảo cho QFT để trích xuất thông tin chu kỳ.

Thuật toán Shor và ứng dụng phá RSA

Thuật toán Shor không trực tiếp giải bài toán phân tích nhân tử hay logarit rời rạc, mà quy giảm chúng về bài toán tìm chu kỳ mà QFT giải hiệu quả.

Phá RSA bằng thuật toán Shor

Bảo mật RSA dựa trên độ khó phân tích một số N = p × q (tích hai số nguyên tố lớn) thành các nhân tử p và q. Shor chứng minh rằng phân tích nhân tử có thể quy giảm về tìm chu kỳ theo cách sau:

Bước 1: Chọn ngẫu nhiên a ∈ [2, N-1]. Nếu gcd(a, N) > 1, ta đã tìm được nhân tử của N (trường hợp hiếm, thực tế bỏ qua). Ngược lại, xét hàm f(x) = aˣ (mod N) – hàm này tuần hoàn với chu kỳ r là bậc nhỏ nhất của a modulo N.

Bước 2: Dùng QFT trên máy tính lượng tử để tìm r trong thời gian đa thức.

Bước 3: Nếu r là số lẻ hay a^(r/2) ≡ –1 (mod N), thử lại với a khác. Ngược lại, với xác suất ít nhất 1/2 (có thể chứng minh), ít nhất một trong gcd(a^(r/2) – 1, N) hay gcd(a^(r/2) + 1, N) là nhân tử không tầm thường của N. Tính toán GCD này mất thời gian O(log²N).

Tổng cộng, thuật toán cần O(log³N) phép tính lượng tử để tìm nhân tử của N – thời gian đa thức trong số bit của N. So sánh với thuật toán phân tích nhân tử cổ điển tốt nhất (General Number Field Sieve – GNFS) có độ phức tạp exp(O((log N)^(1/3) × (log log N)^(2/3))) – theo cấp số mũ phụ. Đây là sự cải thiện theo cấp số mũ: RSA-2048 cần khoảng 2^100 phép tính với GNFS nhưng chỉ cần khoảng log³(2^2048) ≈ (2048)³ ≈ 10^10 phép tính lượng tử – hoàn toàn khả thi với phần cứng lượng tử tương lai.

Chứng minh tại sao bước 3 hoạt động dựa trên lý thuyết số sơ cấp: nếu r là bậc của a modulo N = p × q, và nếu r chẵn với a^(r/2) ≢ –1 (mod N), thì theo Bổ đề Trung Hoa (Chinese Remainder Theorem), a^(r/2) là căn bậc hai không tầm thường của 1 modulo N. Trong Zₙ, phương trình x² ≡ 1 (mod N) có bốn nghiệm: x ≡ ±1 (mod p) và x ≡ ±1 (mod q), tương ứng với bốn nghiệm trong Zₙ. Nếu a^(r/2) là một trong hai nghiệm không tầm thường (tức là ≢ ±1 (mod N)), thì gcd(a^(r/2) ± 1, N) cho nhân tử p hay q.

Phá Diffie–Hellman và ECC bằng thuật toán Shor

Bảo mật của Diffie–Hellman và ECC dựa trên bài toán logarit rời rạc: cho nhóm G (nhóm nhân modulo số nguyên tố, hay nhóm điểm trên đường cong elliptic), phần tử sinh g và h = g^x, hãy tìm x. Thuật toán Shor giải bài toán logarit rời rạc bằng một biến thể tương tự phân tích nhân tử:

Bài toán logarit rời rạc tương đương tìm chu kỳ của hàm f(j, k) = g^j × h^(−k) (mod p) trên nhóm Z × Z. Hàm này có chu kỳ (r, x) trong đó r là bậc của g. Bằng cách chuẩn bị chồng chập đồng đều trên hai chiều và áp dụng QFT hai chiều, Shor tìm được (r, x) trong thời gian O(log³p) – đủ để phục hồi x = log_g(h). Với |G| = q (bậc nhóm), thuật toán Shor giải logarit rời rạc trong O(log³q) phép tính lượng tử.

Với ECC trên Curve25519 (q ≈ 2^252), thuật toán Shor cần khoảng (252)³ ≈ 10^7 phép tính lượng tử – trong khi tấn công brute-force cổ điển cần 2^126 phép tính. Đây là sự cải thiện theo cấp số mũ khổng lồ. Thuật toán Shor cần khoảng 2330 qubit lý tưởng không có lỗi để giải logarit rời rạc ECC 256 bit; với qubit vật lý có tỷ lệ lỗi hiện tại (~0.1%), cần khoảng 3–20 triệu qubit vật lý để chạy thuật toán Shor đủ tin cậy.

Điểm mấu chốt là thuật toán Shor thực sự áp dụng được cho cả phân tích nhân tử và logarit rời rạc – cả hai đều có cấu trúc ẩn dạng chu kỳ trong nhóm Abel mà QFT có thể khai thác. Đây không phải giả thuyết lý thuyết mà là kết quả toán học được chứng minh chặt chẽ. Dù phần cứng lượng tử hiện tại chưa đủ mạnh để tấn công ECC thực tế, tính đúng đắn của thuật toán là không có nghi ngờ.

Tại sao Shor không tấn công được LWE và Kyber

Câu hỏi then chốt trong context Signal Protocol: tại sao thuật toán Shor phá vỡ ECC (nền tảng của X3DH) nhưng không phá vỡ Module-LWE (nền tảng của Kyber trong PQXDH)?

Cấu trúc nhóm ẩn và điều kiện áp dụng Shor

Thuật toán Shor là một thuật toán đặc biệt cho bài toán Tìm Nhóm Con Ẩn (Hidden Subgroup Problem – HSP) trên nhóm Abel. Cho nhóm Abel G và hàm f: G → S hằng số trên các lớp tương đương (cosets) của một nhóm con ẩn H < G, bài toán HSP hỏi tìm H. QFT trên nhóm Abel G có thể giải bài toán này trong thời gian đa thức.

Bài toán phân tích nhân tử quy về HSP trên Z (nhóm số nguyên cộng): bậc của a modulo N là chu kỳ của f(x) = aˣ (mod N), tương ứng nhóm con ẩn H = rZ < Z. Bài toán logarit rời rạc quy về HSP trên Z × Z: nhóm con ẩn là H = {(j, k): g^j × h^(−k) = 1} < Z × Z, được tạo ra bởi vector (r, x). Cả hai đều là HSP trên nhóm Abel và QFT giải được.

Bài toán LWE không có cấu trúc nhóm con ẩn. LWE hỏi phân biệt phân phối (A, As + e) với (A, b_random) – đây không phải bài toán về chu kỳ hay nhóm con. Không có cách tự nhiên nào để xây dựng một hàm f có chu kỳ từ bài toán LWE. Kẻ tấn công không thể đặt LWE dưới dạng HSP và do đó QFT không giúp ích gì. Sức mạnh của thuật toán Shor hoàn toàn đến từ cấu trúc nhóm ẩn – không có cấu trúc đó, Shor là vô dụng.

Bài toán SVP (Shortest Vector Problem) trên mạng lưới cũng không có cấu trúc nhóm con ẩn theo nghĩa có thể giải được bằng QFT. Đã có một số nỗ lực quy SVP về dạng HSP trên các nhóm không Abel (non-abelian HSP) – Regev và Wittek chứng minh năm 2012 rằng SVP có thể quy về dạng dihedral HSP – nhưng không có thuật toán lượng tử hiệu quả nào được biết cho non-abelian HSP, kể cả dihedral HSP.

Thuật toán Grover và giới hạn tác động

Thuật toán Grover (Lov Grover, 1996) là thuật toán lượng tử tổng quát tăng tốc tìm kiếm không gian ngẫu nhiên từ O(N) về O(√N). Đây là cải thiện bậc hai, không phải cải thiện theo cấp số mũ như Shor. Grover áp dụng được cho bất kỳ bài toán tìm kiếm không gian ngẫu nhiên nào, bao gồm brute-force trên khóa đối xứng, băm và LWE.

Ảnh hưởng của Grover lên LWE: tấn công brute-force trên vector bí mật s ∈ Zq^n cần O(q^n) phép tính cổ điển nhưng chỉ O(q^(n/2)) phép tính lượng tử với Grover. Tuy nhiên, với n = 1024 và q = 3329 trong Kyber-1024, cả q^1024 lẫn q^512 đều không thể tính được trong thực tế – khoảng cách là theo cấp số mũ của n, không phải hệ số cố định. Grover chỉ giảm mức bảo mật ước tính theo hệ số một nửa số bit – Kyber-1024 từ 256 bit cổ điển xuống khoảng 128 bit lượng tử (chính xác hơn, khoảng 178–230 bit tùy theo cách tính, do các thuật toán tấn công mạng lưới tốt nhất không phải là brute-force đơn giản).

Điều quan trọng cần phân biệt: tác động của Shor lên ECC là từ an toàn thực tiễn (2^126 phép tính, không thể thực hiện) sang không an toàn (2^7 phép tính, hoàn toàn khả thi) – giảm theo cấp số mũ. Tác động của Grover lên Kyber là từ an toàn thực tiễn (2^256 phép tính) sang vẫn an toàn thực tiễn (2^128 phép tính) – giảm hệ số nhưng vẫn hoàn toàn ngoài tầm với. Đây là sự khác biệt về loại (qualitative difference), không chỉ về lượng: Shor đặt ECC vào mối đe dọa thực sự; Grover chỉ đòi hỏi chọn tham số LWE lớn hơn một chút.

Thuật toán Simon và giới hạn đối với mật mã đối xứng

Thuật toán Simon (Daniel Simon, 1994) là một thuật toán lượng tử giải bài toán chu kỳ đặc biệt trong thời gian tuyến tính, exponentially nhanh hơn bất kỳ thuật toán cổ điển nào cho cùng bài toán. Simon quan trọng trong lý thuyết độ phức tạp lượng tử vì nó là bài toán đầu tiên chứng minh separation rõ ràng giữa BPP (đa thức cổ điển xác suất) và BQP (đa thức lượng tử).

Thuật toán Simon có tác động tiềm tàng lên một số sơ đồ mật mã đối xứng trong mô hình tấn công lượng tử mạnh nhất – mô hình quantum superposition access (QSA) trong đó kẻ tấn công có thể truy vấn oracle mã hóa bằng các trạng thái lượng tử siêu vị. Một số phân tích cho thấy AES, GHASH (trong AES-GCM) và một số sơ đồ MAC có thể bị phân biệt hay giả mạo trong mô hình QSA. Tuy nhiên, mô hình QSA là mô hình tấn công phi thực tế: kẻ tấn công trong thực tế quan sát lưu lượng mạng cổ điển, không có khả năng truy vấn oracle mã hóa bằng trạng thái lượng tử. Trong mô hình tấn công thực tiễn hơn (quantum access to public data, classical access to oracle), thuật toán Simon không áp dụng được và AES-256 vẫn an toàn ở mức 128 bit lượng tử nhờ Grover.

LWE trong mô hình QSA cũng được phân tích bởi một số nhà nghiên cứu; kết quả hiện tại cho thấy không có tấn công QSA nào hiệu quả hơn đáng kể so với các thuật toán tấn công mạng lưới cổ điển tốt nhất. Đây là tính chất bảo thủ của LWE: không chỉ an toàn trong mô hình tấn công thực tế mà còn kháng cự tốt trong các mô hình tấn công lý thuyết mạnh hơn.

Trạng thái hiện tại của điện toán lượng tử

Hiểu đúng mức độ thực sự của mối đe dọa đòi hỏi nhìn nhận thực tế về khoảng cách giữa máy tính lượng tử hiện tại và ngưỡng cần thiết để chạy thuật toán Shor phá vỡ ECC.

Khoảng cách từ lý thuyết đến thực hành

Thuật toán Shor yêu cầu: qubit số lượng lớn; tỷ lệ lỗi qubit cực thấp; tính kết hợp lượng tử (coherence time) đủ dài để chạy thuật toán; và mạch lượng tử (quantum circuit) sâu đủ để thực hiện QFT và oracle hàm. Khoảng cách giữa yêu cầu và thực tế hiện tại là rất lớn.

Để chạy thuật toán Shor phá RSA-2048 hay ECC-256, cần khoảng 2000–4000 qubit logic không có lỗi. Qubit logic được xây dựng từ nhiều qubit vật lý thông qua mã sửa lỗi lượng tử (Quantum Error Correction – QEC). Với tỷ lệ lỗi qubit vật lý điển hình (~0.1–1%) và mã surface code phổ biến nhất, cần khoảng 1000–10000 qubit vật lý cho mỗi qubit logic – tổng khoảng 3–20 triệu qubit vật lý để chạy Shor phá ECC-256.

Máy tính lượng tử thực tế lớn nhất năm 2024: IBM Condor (1121 qubit vật lý), IBM Heron (133 qubit, tỷ lệ lỗi thấp hơn đáng kể). Google Willow (105 qubit) chứng minh QEC có thể giảm tỷ lệ lỗi exponentially khi thêm qubit – một bước đột phá quan trọng về chứng minh nguyên lý. Tuy nhiên, khoảng cách từ vài trăm qubit vật lý hiện tại đến 3–20 triệu qubit vật lý cần thiết là khoảng cách rất lớn. Ngay cả với tốc độ phát triển lạc quan nhất (số qubit tăng gấp đôi mỗi 18 tháng, tương tự Định luật Moore), máy tính lượng tử đủ mạnh để phá ECC-256 chỉ có thể xuất hiện sớm nhất vào cuối những năm 2030 hay đầu những năm 2040 – và đây là ước tính lạc quan, không phải dự báo.

Chiến lược thu thập trước giải mã sau

Dù mối đe dọa trực tiếp còn xa về mặt thời gian, chiến lược thu thập trước, giải mã sau (harvest now, decrypt later – HNDL) tạo ra mối đe dọa thực sự ngay từ hôm nay. Các tổ chức tình báo quốc gia hay tội phạm mạng có thể đang ghi lại tất cả lưu lượng TLS, SSH và tin nhắn mã hóa hiện tại với hi vọng giải mã chúng khi máy tính lượng tử đủ mạnh xuất hiện.

Mối đe dọa này đặc biệt nghiêm trọng với dữ liệu có thời gian bảo mật dài (long security horizon): thông tin tình báo nhà nước có thể cần bảo mật 20–30 năm; dữ liệu y tế cần bảo mật suốt đời người; sở hữu trí tuệ cần bảo mật cho đến khi sản phẩm ra thị trường. Nếu máy tính lượng tử đủ mạnh xuất hiện trong 20 năm, thông tin bảo mật bằng ECC ngày hôm nay có thể bị lộ trong vòng 20 năm đó – quá dài với nhiều ứng dụng nhạy cảm.

Signal Protocol và các ứng dụng nhắn tin nói chung đối mặt với mối đe dọa HNDL theo cách đặc biệt: mặc dù nội dung từng tin nhắn có thể không nhạy cảm sau nhiều năm, siêu dữ liệu (ai đã nói chuyện với ai, khi nào, tần suất) có thể vẫn nhạy cảm và lộ qua phân tích lưu lượng ngay cả khi nội dung được bảo mật. Đây là lý do tại sao Signal Foundation quyết định tích hợp Kyber vào PQXDH ngay bây giờ thay vì chờ đến khi mối đe dọa lượng tử trở nên gần hơn – bảo vệ hôm nay chống lại ghi lại hôm nay là cách duy nhất ngăn chặn HNDL.

Xu hướng phát triển và mốc thời gian

Phát triển điện toán lượng tử đang tăng tốc theo nhiều chiều. Về qubit vật lý: IBM cam kết lộ trình đạt 100.000 qubit vào năm 2033. Google chứng minh QEC giảm lỗi theo cấp số mũ khi thêm qubit vật lý trong chip Willow năm 2024 – bước đột phá quan trọng chứng tỏ QEC thực sự hoạt động, không chỉ trên lý thuyết. Các công ty mới như PsiQuantum (photonic qubit), IonQ (trapped ion), Quantinuum (ion trap) và Microsoft (topological qubit) đang phát triển kiến trúc qubit khác nhau với đặc tính lỗi và coherence time khác nhau.

Tuy nhiên, số qubit là một trong nhiều yếu tố. Các thách thức kỹ thuật khác chưa giải quyết hoàn toàn bao gồm: coherence time đủ dài để chạy mạch sâu (hiện tại tính bằng mili giây đến giây, cần kéo dài đáng kể); kết nối giữa các qubit (hiện tại hầu hết kiến trúc chỉ cho phép qubit gần nhau kết nối trực tiếp, mạch sâu cần nhiều swap gates làm tăng lỗi); và overhead của QEC (tỷ lệ qubit vật lý/logic cần giảm xuống để đạt quy mô thực tiễn).

Thực tế nhất là dự báo của nhiều chuyên gia mật mã và vật lý lượng tử: máy tính lượng tử đủ mạnh để phá RSA-2048 và ECC-256 có thể xuất hiện trong khoảng 2035–2050 nếu phát triển tiếp tục với tốc độ hiện tại, nhưng có thể trễ hơn đáng kể nếu gặp trở ngại kỹ thuật lớn. Không thể loại trừ cả hai khả năng: xuất hiện sớm hơn dự kiến hay không xuất hiện trong vài thập kỷ tới do khó khăn kỹ thuật chưa được nhận ra.

Phản ứng của cộng đồng mật mã

Mối đe dọa từ thuật toán Shor đã kích hoạt một trong những nỗ lực chuẩn hóa lớn nhất trong lịch sử mật mã học, với kết quả là các tiêu chuẩn mật mã hậu lượng tử đầu tiên được công bố năm 2024.

Cuộc thi NIST và kết quả

Năm 2016, NIST chính thức phát động cuộc thi tiêu chuẩn hóa mật mã hậu lượng tử với mục tiêu tìm kiếm các thuật toán KEM và chữ ký số an toàn trước tấn công lượng tử. Cuộc thi nhận 69 đề xuất ban đầu từ các nhóm nghiên cứu khắp thế giới, trải qua bốn vòng phân tích kỹ lưỡng trong bảy năm. Tháng 8 năm 2024, NIST công bố ba tiêu chuẩn đầu tiên:

FIPS 203 (ML-KEM / CRYSTALS-Kyber): cơ chế đóng gói khóa dựa trên Module-LWE, dùng trong PQXDH. FIPS 204 (ML-DSA / CRYSTALS-Dilithium): sơ đồ chữ ký số dựa trên Module-LWE và Module-SIS. FIPS 205 (SLH-DSA / SPHINCS+): sơ đồ chữ ký số dựa trên hàm băm, không dựa trên mạng lưới – cung cấp đa dạng hóa nền tảng bảo mật.

Ngoài ba tiêu chuẩn trên, NIST cũng đang tiêu chuẩn hóa FALCON (chữ ký dựa trên NTRU lattice) và tiếp tục phân tích một số ứng viên KEM bổ sung như HQC (dựa trên mã sửa lỗi) để cung cấp đa dạng hóa. Sự đa dạng hóa là ý thức chiến lược: nếu sau này phát hiện điểm yếu trong một họ bài toán (ví dụ tấn công mạng lưới bất ngờ hiệu quả hơn dự kiến), hệ sinh thái mật mã vẫn có các lựa chọn thay thế dựa trên nền tảng khác.

Triển khai và khó khăn thực tiễn

Chuyển đổi từ mật mã cổ điển sang mật mã hậu lượng tử là bài toán kỹ thuật và hậu cần phức tạp ở quy mô toàn cầu. TLS – giao thức bảo mật internet phổ biến nhất – cần cập nhật để hỗ trợ các thuật toán KEM mới với kích thước khóa và bản mã lớn hơn nhiều. Các thiết bị nhúng (embedded devices), thiết bị IoT và phần cứng cũ có thể không đủ tài nguyên để chạy Kyber-1024. Các hệ thống cần thay thế đồng thời khóa đối xứng, khóa không đối xứng và chữ ký số – một quá trình có thể kéo dài 5–10 năm.

Signal Protocol và Signal Foundation đã đi đầu trong quá trình này: PQXDH được tích hợp vào Signal app từ năm 2023, bảo vệ các phiên mới ngay từ hôm nay. Phương pháp hybrid (kết hợp ECC cổ điển và Kyber hậu lượng tử) là cách tiếp cận đúng đắn trong giai đoạn chuyển tiếp: duy trì bảo mật hiện tại trước mọi đối thủ cổ điển trong khi bổ sung bảo vệ trước đối thủ lượng tử thụ động, không đánh đổi bảo mật cổ điển để đạt bảo mật lượng tử.

Tính linh hoạt mật mã (Crypto Agility)

Một bài học quan trọng từ thuật toán Shor là thiết kế hệ thống mật mã cần có tính linh hoạt mật mã (crypto agility) – khả năng thay thế thuật toán mật mã khi cần thiết mà không phải thiết kế lại toàn bộ hệ thống. Signal Protocol thể hiện điều này qua các tham số: pqkem là tham số có thể thay đổi, cho phép chuyển từ Kyber sang thuật toán KEM khác trong tương lai nếu cần; curve là tham số cho phép chuyển đổi đường cong; hash và aead tương tự.

Crypto agility quan trọng vì bảo mật mật mã không bao giờ là vĩnh viễn: RSA-512 từng được coi là đủ an toàn, rồi phải nâng lên RSA-1024, RSA-2048 và hiện tại RSA-3072; MD5 và SHA-1 từng được tin dùng rộng rãi, nay đã bị loại bỏ. Mật mã hậu lượng tử cũng sẽ trải qua quá trình tương tự khi cộng đồng mật mã hiểu sâu hơn về các thuật toán tấn công mạng lưới và khi máy tính lượng tử thực tế xuất hiện cung cấp các benchmark thực nghiệm. Hệ thống được thiết kế với crypto agility có thể thích ứng; hệ thống thiết kế thuật toán hardcode sẽ gặp khó khăn nghiêm trọng.

Kết luận

Thuật toán Shor là một trong những kết quả lý thuyết quan trọng nhất trong lịch sử khoa học máy tính: nó chứng minh rằng nếu thay thế mô hình tính toán cổ điển bằng máy tính lượng tử, bảo mật của toàn bộ hạ tầng khóa công khai hiện đại – RSA, Diffie–Hellman, ECC – sụp đổ hoàn toàn. Không phải suy yếu, mà sụp đổ: từ bảo mật 2^128 phép tính xuống 2^7 phép tính – một sự thay đổi theo cấp số mũ không thể bù đắp bằng cách tăng kích thước khóa.

Mối đe dọa này hiện tại chưa thực sự xảy ra vì phần cứng lượng tử còn thiếu 3–20 triệu qubit vật lý chất lượng cao so với ngưỡng cần thiết. Nhưng chiến lược HNDL – ghi lại hôm nay, giải mã sau – tạo ra mối đe dọa thực sự ngay từ bây giờ với mọi thông tin cần bảo mật trong nhiều thập kỷ. Đây là lý do tại sao PQXDH và Kyber-1024 quan trọng không phải vì máy tính lượng tử đã ở ngưỡng cửa, mà vì bảo vệ hôm nay là cách duy nhất ngăn chặn giải mã ngày mai.

Điều quan trọng nhất để hiểu: Shor không phá vỡ mọi mật mã – nó phá vỡ đúng các sơ đồ có cấu trúc nhóm con ẩn mà QFT có thể khai thác. Module-LWE không có cấu trúc đó. Không có thuật toán lượng tử nào được biết giải Module-LWE hiệu quả hơn đáng kể so với tấn công brute-force, và Grover chỉ giảm mức bảo mật theo hệ số một nửa số bit – đủ để tham số Kyber-1024 vẫn an toàn ở mức 230+ bit lượng tử. Đây là căn cứ lý thuyết và thực tiễn cho quyết định của Signal Protocol: tích hợp Kyber không phải vì Shor là mối đe dọa ngay lập tức, mà vì HNDL là mối đe dọa thực sự hôm nay và Kyber là giải pháp kỹ thuật tốt nhất hiện có.