Giới thiệu dự án
Sự bùng nổ của hạ tầng điện toán đám mây và giao dịch số toàn cầu đặt nền tảng an ninh thông tin vào các thuật toán mã hóa công khai bất đối xứng, tiêu biểu là RSA (Rivest–Shamir–Adleman) và mật mã đường cong elliptic (ECC). Hiện nay, hơn 90% lưu lượng Internet, hệ thống xác thực giao dịch tài chính, ngân hàng và chữ ký số quốc gia được bảo vệ bởi các hệ mật mã xây dựng trên bài toán toán học khó: bài toán phân tích một hợp số nguyên lớn $N = p \times q$ thành tích của hai số nguyên tố bí mật. Với máy tính cổ điển, các thuật toán sàng lọc số nguyên tiên tiến nhất như General Number Field Sieve (GNFS) đòi hỏi thời gian tính toán cận hàm mũ $O\left(\exp\left(c \cdot (\ln N)^{1/3} (\ln \ln N)^{2/3}\right)\right)$. Đối với các khóa RSA-2048 bit hoặc RSA-4096 bit, thời gian tính toán phá mã thực tế vượt qua hàng triệu năm, đảm bảo tính an toàn gần như tuyệt đối trước kiến trúc máy tính Von Neumann truyền thống.
Tuy nhiên, sự phát triển vượt bậc của công nghệ thông tin lượng tử với các mốc đầu tư toàn cầu đạt 24,4 tỉ USD (năm 2021) cùng lộ trình chế tạo bộ xử lý 100.000 qubit vào năm 2033 của IBM đã tạo ra mối đe dọa trực tiếp đến các hạ tầng bảo mật này. Thuật toán lượng tử Shor (Shor's Algorithm), được Peter Shor đề xuất năm 1994, chứng minh khả năng giải quyết bài toán phân tích thừa số nguyên tố trong thời gian đa thức $O((\log N)^3)$. Khóa luận tốt nghiệp "Nghiên cứu thuật toán lượng tử Shor" của tác giả Huỳnh Phương Anh (Khoa Vật lí, Trường Đại học Sư phạm – Đại học Đà Nẵng, dưới sự hướng dẫn của TS. Dụng Văn Lữ) tập trung giải mã bản chất cơ học lượng tử, mô hình toán học và triển khai mô phỏng thực thi thuật toán Shor trên nền tảng điện toán lượng tử IBM Qiskit.
+------------------------------------------------------------------------------------+
| BÀI TOÁN PHÂN TÍCH HỢP SỐ N = p * q |
+------------------------------------------------------------------------------------+
| |
v (Máy tính cổ điển - Thuật toán GNFS) v (Máy tính lượng tử - Thuật toán Shor)
+----------------------------------------------+ +----------------------------------------------+
| Độ phức tạp: Cận hàm mũ | | Độ phức tạp: Thời gian đa thức |
| O(exp((ln N)^(1/3) * (ln ln N)^(2/3))) | | O((log N)^3) |
| Thời gian phá mã RSA-2048: Hàng triệu năm | | Thời gian phá mã RSA-2048: Vài giờ/ngày |
+----------------------------------------------+ +----------------------------------------------+
Mục tiêu dự án
- Hệ thống hóa cơ sở lý thuyết điện toán lượng tử: Khảo sát các nguyên lý nền tảng gồm lưỡng tính sóng - hạt, nguyên lý chồng chất lượng tử (Quantum Superposition), tính vướng víu lượng tử (Quantum Entanglement) và hệ thống cổng logic lượng tử đơn/đa qubit ($H, X, Y, Z, \text{CNOT}$).
- Phân tích cơ chế toán học của thuật toán Shor: Làm rõ quy trình chuyển đổi bài toán phân tích thừa số nguyên tố sang bài toán tìm chu kỳ (Period Finding) của hàm tuần hoàn modulo $f(x) = a^x \pmod N$.
- Hiện thực hóa và tối ưu thuật toán trên nền tảng mô phỏng: Xây dựng mạch lượng tử hoàn chỉnh phân tích hợp số $N = 15$ với cơ số ngẫu nhiên $a = 2$, kết hợp toán tử biến đổi Fourier lượng tử nghịch đảo ($\text{QFT}^\dagger$).
- Xây dựng giải thuật hậu xử lý cổ điển tự động: Phát triển mô-đun phân tích liên phân số (Continued Fractions) và bộ lọc ước chung lớn nhất (GCD) để tự động xuất ra các thừa số nguyên tố $(p, q)$ chuẩn xác, khắc phục nhiễu lượng tử.
Phạm vi và giới hạn
- Đối tượng nghiên cứu: Khung toán học của thuật toán Shor và bài toán phá mã hệ mật RSA.
- Phạm vi kỹ thuật: Mạch lượng tử 12-qubit (gồm 8 qubit thanh ghi đếm và 4 qubit thanh ghi mục tiêu) thực thi phân tích số $N = 15$ trên môi trường giả lập
aer_simulator thuộc SDK Qiskit (Python).
Phân tích và thiết kế giải pháp
Phân tích hiện trạng
Trong mật mã học truyền thống, độ an toàn của thuật toán RSA phụ thuộc hoàn toàn vào độ phức tạp tính toán một chiều của phép nhân modulo. Việc nhân hai số nguyên tố $p, q$ có độ dài 1024-bit diễn ra trong vài micro-giây, nhưng phân tích ngược lại từ $N$ là bất khả thi với máy tính cổ điển.
| Phương pháp giải thuật |
Loại hình xử lý |
Độ phức tạp thời gian |
Đánh giá khả thi với RSA-2048 |
| Vét cạn / Thử phép chia (Trial Division) |
Cổ điển tuần tự |
$O(\sqrt{N}) \approx O(2^{n/2})$ |
Hoàn toàn bất khả thi |
| Pollard's Rho Algorithm |
Cổ điển ngẫu nhiên |
$O(N^{1/4}) \approx O(2^{n/4})$ |
Hoàn toàn bất khả thi |
| Sàng trường số tổng quát (GNFS) |
Cổ điển phân tán |
$O\left(e^{\sqrt[3]{\frac{64}{9}}(\ln N)^{\frac{1}{3}}(\ln\ln N)^{\frac{2}{3}}}\right)$ |
Mất hàng tỷ năm tính toán |
| Thuật toán lượng tử Shor |
Lai ghép Lượng tử - Cổ điển |
$O((\log N)^2 (\log \log N) (\log \log \log N))$ |
Khả thi trong thời gian đa thức |
MÔ HÌNH PHÂN HẠNG YÊU CẦU HỆ THỐNG (MoSCoW)
+------------------------------------------------------------------------+
| MUST HAVE: |
| - Mạch tạo chồng chất đồng đều (Hadamard register) |
| - Toán tử lũy thừa Modulo có điều khiển (Controlled-U_f) |
| - Khối biến đổi Fourier lượng tử nghịch đảo (Inverse QFT) |
| - Bộ giải mã phân số liên tục (Continued Fraction Expander) |
+------------------------------------------------------------------------+
| SHOULD HAVE: |
| - Vòng lặp tự động hóa kiểm tra điều kiện chẵn/lẻ của chu kỳ r |
| - Bộ lọc ước chung lớn nhất (Euclid GCD) khử nghiệm tầm thường |
+------------------------------------------------------------------------+
| COULD HAVE: |
| - Mô hình tích hợp cổng khử nhiễu lượng tử (Noise mitigation) |
+------------------------------------------------------------------------+
| WON'T HAVE (Hiện tại): |
| - Phân tích khóa thực tế 2048-bit (do hạn chế phần cứng NISQ vật lý) |
+------------------------------------------------------------------------+
Thiết kế hệ thống
Kiến trúc giải pháp được thiết kế theo mô hình tính toán lai (Hybrid Quantum-Classical Architecture), trong đó tài nguyên tính toán được phân bổ tối ưu: máy tính cổ điển xử lý tiền/hậu số học, máy tính lượng tử đảm nhận tác vụ tìm chu kỳ có độ phức tạp cao nhờ tính song song lượng tử.
Ngăn xếp công nghệ (Technology Stack)
- Ngôn ngữ lập trình cốt lõi: Python 3.10+
- Framework tính toán lượng tử: IBM Qiskit Core v0.45.0+ / Qiskit Aer v0.12.0+
- Thư viện toán học và xử lý dữ liệu: NumPy 1.24+, Pandas 2.0+, SymPy 1.12+
- Môi trường giả lập Backend:
AerSimulator (Mô phỏng máy ảo lượng tử độ chính xác trạng thái vector đầy đủ - Statevector Simulator)
- Công cụ trực quan hóa dữ liệu: Matplotlib 3.7.2+, Qiskit Visualization Circuit Drawer
Phương pháp nghiên cứu (Methodology)
Nghiên cứu áp dụng phương pháp Thực nghiệm Kỹ thuật Lượng tử (Quantum Software Engineering):
- Giai đoạn 1 (Lý thuyết toán tử): Thiết lập không gian vector Hilbert $\mathcal{H} = \mathcal{H}_1 \otimes \mathcal{H}_2$, tính toán kích thước không gian pha $Q = 2^n$ thỏa mãn điều kiện tối ưu $N^2 \le Q < 2N^2$. Với $N = 15 \Rightarrow 225 \le 256 < 450 \Rightarrow n = 8 \text{ qubits}$.
- Giai đoạn 2 (Thiết kế cổng): Tổng hợp toán tử đơn nguyên $U_f|y\rangle = |(a \cdot y) \pmod N\rangle$ thành chuỗi các cổng logic khả nghịch gồm $\text{SWAP}$, $\text{CNOT}$ và cổng điều khiển pha $CP(\theta)$.
- Giai đoạn 3 (Xây dựng mô phỏng & Đánh giá rủi ro): Đánh giá xác suất suy sụp lượng tử, phân tích hiện tượng mất kết hợp pha (Decoherence) và sai số do xấp xỉ liên phân số.
Triển khai thực nghiệm và kết quả
Quy trình phát triển (Development Process)
Hệ thống mạch lượng tử được xây dựng gồm hai thanh ghi chính:
- Thanh ghi 1 (Counting Register): Gồm 8 qubit ($q_0 \to q_7$) khởi tạo ở trạng thái $|0\rangle^{\otimes 8}$, sau đó đưa qua các cổng Hadamard ($H^{\otimes 8}$) để tạo trạng thái chồng chất đồng đều của $2^8 = 256$ trạng thái:
$$|\psi_1\rangle = \frac{1}{\sqrt{256}} \sum_{x=0}^{255} |x\rangle |0\rangle^{\otimes 4}$$
- Thanh ghi 2 (Auxiliary/Target Register): Gồm 4 qubit ($q_8 \to q_{11}$) biểu diễn giá trị của hàm $f(x) = 2^x \pmod{15}$.
import numpy as np
from qiskit import QuantumCircuit, Aer, transpile, assemble
from qiskit.visualization import plot_histogram
from math import gcd
import pandas as pd
from fractions import Fraction
def c_amod15(a, power):
"""Tạo cổng đơn nguyên có điều khiển U áp dụng: a^(2^j) mod 15"""
if a not in [2, 7, 8, 11, 13]:
raise ValueError("'a' phải là số nguyên tố cùng nhau với 15")
U = QuantumCircuit(4)
for iteration in range(power):
if a in [2, 13]:
U.swap(0, 1)
U.swap(1, 2)
U.swap(2, 3)
if a in [7, 8]:
U.swap(2, 3)
U.swap(1, 2)
U.swap(0, 1)
if a == 11:
U.swap(1, 3)
U.swap(0, 2)
if a in [7, 11, 13]:
for q in range(4):
U.x(q)
U = U.to_gate()
U.name = f"{a}^{power} mod 15"
c_U = U.control()
return c_U
def qft_dagger(n):
"""Mạch biến đổi Fourier lượng tử nghịch đảo (Inverse QFT) cho n qubit"""
qc = QuantumCircuit(n)
for qubit in range(n//2):
qc.swap(qubit, n-qubit-1)
for j in range(n):
for m in range(j):
qc.cp(-np.pi/float(2**(j-m)), m, j)
qc.h(j)
qc.name = "QFT†"
return qc
Mạch hoàn chỉnh ghép nối toàn bộ khối điều khiển modular và biến đổi $\text{QFT}^\dagger$, sau đó đưa qua quy trình đo lường tự động:
# Thiết lập mạch lượng tử: 8 counting qubits + 4 target qubits
n_count = 8
a = 2
N = 15
qc = QuantumCircuit(n_count + 4, n_count)
# Bước 1: Tạo trạng thái chồng chất trên thanh ghi 1
for q in range(n_count):
qc.h(q)
# Khởi tạo thanh ghi mục tiêu ở trạng thái |1> (qubit index n_count tương ứng |0001>)
qc.x(n_count)
# Bước 2: Áp dụng chuỗi cổng Modular Exponentiation có điều khiển
for q in range(n_count):
qc.append(c_amod15(a, 2**q), [q] + [i+n_count for i in range(4)])
# Bước 3: Áp dụng Biến đổi Fourier lượng tử nghịch đảo
qc.append(qft_dagger(n_count), range(n_count))
# Bước 4: Đo thanh ghi 1
qc.measure(range(n_count), range(n_count))
Kiểm thử và Đánh giá (Testing & Validation)
Mạch được thực thi trên AerSimulator với 1024 shots mô phỏng. Kết quả thu được 4 đỉnh xác suất phân bố đều trên thanh ghi đo:
+-------------------------------------------------------------------------------+
| PHỔ XÁC SUẤT ĐO ĐƯỢC TRÊN REGISTER 1 |
+-------------------------------------------------------------------------------+
Xác suất (%)
30% | [25%] [25%] [25%] [25%]
20% | | | | |
10% | | | | |
0% +------------|------------------|------------------|------------------|----+
|00000000> (0) |01000000> (64) |10000000> (128) |11000000> (192)
- Trạng thái $|00000000\rangle_2 \equiv 0_{10}$: $\text{Pha } \phi = 0/256 = 0.00 \to s/r = 0/1 \to r = 1$ (Nghiệm tầm thường, loại bỏ).
- Trạng thái $|01000000\rangle_2 \equiv 64_{10}$: $\text{Pha } \phi = 64/256 = 0.25 \to s/r = 1/4 \to r = 4$.
- Trạng thái $|10000000\rangle_2 \equiv 128_{10}$: $\text{Pha } \phi = 128/256 = 0.50 \to s/r = 1/2 \to r = 2$.
- Trạng thái $|11000000\rangle_2 \equiv 192_{10}$: $\text{Pha } \phi = 192/256 = 0.75 \to s/r = 3/4 \to r = 4$.
# Thuật toán cải tiến tự động hóa tìm thừa số nguyên tố hoàn chỉnh
while True:
aer_sim = Aer.get_backend('aer_simulator')
t_qc = transpile(qc, aer_sim)
qobj = assemble(t_qc)
results = aer_sim.run(t_qc).result()
counts = results.get_counts()
rows, measured_phases = [], []
for output in counts:
decimal = int(output, 2)
phase = decimal / (2**n_count)
measured_phases.append(phase)
frac = Fraction(phase).limit_denominator(15)
r = frac.denominator
# Kiểm tra điều kiện chu kỳ r hợp lệ
if r % 2 == 0:
p = gcd(a**(r//2) - 1, 15)
q = gcd(a**(r//2) + 1, 15)
if p != 1 and q != 1 and p * q == 15:
print(f">> TÌM THẤY THỪA SỐ: p = {p}, q = {q} (với chu kỳ r = {r}, Pha = {phase})")
break
else:
continue
break
Kết quả đạt được
Hệ thống đã phân tích hoàn toàn thành công hợp số $N = 15$:
- Chu kỳ cơ sở xác định chính xác: $r = 4$.
- Thừa số nguyên tố thứ nhất: $p = \gcd(2^{4/2} - 1, 15) = \gcd(3, 15) = 3$.
- Thừa số nguyên tố thứ hai: $q = \gcd(2^{4/2} + 1, 15) = \gcd(5, 15) = 5$.
- Tỷ lệ thành công của thuật toán sau vòng lặp hậu xử lý: 100%.
Đổi mới và đóng góp
- Tự động hóa hoàn toàn quy trình phân tích liên phân số và lọc nghiệm: Trong các nghiên cứu trước đây (như công trình của Poornashree S J & Prameela Kumari N., 2020), kết quả đo từ Qiskit thường chỉ dừng lại ở đồ thị histogram pha, đòi hỏi người nghiên cứu phải tính toán thủ công các giá trị $\gcd(a^{r/2} \pm 1, N)$. Đồ án đã cải tiến cấu trúc vòng lặp điều kiện kín
while-loop, kết hợp hàm limit_denominator(15) tự động bẻ khóa và xuất thẳng hai số nguyên tố $p=3, q=5$.
- Tối ưu hóa độ sâu mạch lượng tử (Circuit Depth): Khối toán tử $U_f$ được xây dựng bằng cấu trúc hoán vị bit tối thiểu ($\text{SWAP}$ cascade), giảm thiểu số lượng cổng $CNOT$ không cần thiết, giúp hạn chế tích lũy sai số pha trong các bước quay $CP(\theta)$.
- Đóng góp học thuật thực tế: Kết quả nghiên cứu của đề tài đã được công bố chính thức qua bài báo khoa học: "Thuật toán lượng tử phá mã RSA", đăng trên Tạp chí Khoa học và Công nghệ – Đại học Đà Nẵng, Vol 21, Số 3, 2023, khẳng định giá trị nghiên cứu lý thuyết lẫn thực nghiệm.
Ứng dụng thực tế và triển khai
Tình huống ứng dụng thực tế
- Đánh giá lỗ hổng hệ thống mật mã công khai: Cho phép các tổ chức tài chính, ngân hàng và cơ quan an ninh mạng mô phỏng mức độ rủi ro đối với các chứng chỉ số SSL/TLS và chuẩn mã hóa RSA/ECC khi máy tính lượng tử đạt ngưỡng mở rộng (Quantum Supremacy).
- Chuẩn bị chuyển dịch sang Mật mã Hậu Lượng tử (PQC - Post-Quantum Cryptography): Cung cấp cơ sở thực nghiệm để các doanh nghiệp công nghệ chuyển hướng tích hợp các thuật toán kháng lượng tử theo chuẩn NIST (như Kyber, Dilithium, Falcon dựa trên bài toán mạng tinh thể - Lattice-based cryptography).
Lộ trình mở rộng quy mô (Scalability Analysis)
+---------------------------------------------------------------------------------------+
| LỘ TRÌNH QUY MÔ PHẦN CỨNG ĐỂ PHÁ MÃ RSA THỰC TẾ |
+---------------------------------------------------------------------------------------+
| Khóa RSA | Qubit Logic cần thiết | Qubit Vật lý (sửa lỗi bề mặt) | Thời gian ước tính |
+-------------+-----------------------+-------------------------------+---------------------+
| RSA-15 | 12 qubits (mô phỏng) | 12 qubits | < 1 giây (đạt được) |
| RSA-512 | ~1,024 qubits | ~1,000,000 qubits | Vài phút |
| RSA-1024 | ~2,048 qubits | ~2,000,000 qubits | Vài giờ |
| RSA-2048 | ~4,096 qubits | ~4,000,000 qubits | 8 - 24 giờ |
+---------------------------------------------------------------------------------------+
Hạn chế và hướng phát triển
Hạn chế kỹ thuật
- Nhiễu phần cứng lượng tử (NISQ Era): Trên các bộ xử lý lượng tử vật lý hiện nay, hiện tượng Decoherence (mất đồng pha) do tương tác nhiệt và từ trường môi trường làm suy giảm độ chính xác của cổng lượng tử khi độ sâu mạch tăng cao.
- Giới hạn mô phỏng cổ điển: Việc giả lập trên máy tính cá nhân bị giới hạn bởi bộ nhớ RAM. Do trạng thái của $n$ qubit yêu cầu $2^n$ biên độ xác suất số phức (16 bytes mỗi trạng thái), một hệ thống 30 qubit đòi hỏi tối thiểu 16 GB RAM, khiến việc mô phỏng vượt quá $N=15$ gặp thách thức lớn trên máy tính thông thường.
Hướng phát triển
- Mở rộng triển khai thuật toán trên phần cứng lượng tử thật thông qua IBM Quantum Cloud API, áp dụng kỹ thuật giảm thiểu lỗi đo lường (Measurement Error Mitigation).
- Nghiên cứu ứng dụng thuật toán Shor mở rộng vào bài toán logarit rời rạc (Discrete Logarithm Problem) nhằm đánh giá mức độ an toàn của hệ thống mật mã ElGamal và trao đổi khóa Diffie-Hellman.
Đối tượng hưởng lợi
- Sinh viên & Học viên chuyên ngành Vật lý/Khoa học Máy tính: Có được tài liệu tham khảo hoàn chỉnh, chuẩn hóa bằng tiếng Việt về mô hình toán học lượng tử và hướng dẫn lập trình thực chiến trên Qiskit.
- Kỹ sư An toàn Thông tin & Lập trình viên: Nắm bắt cơ chế suy thoái của mã hóa RSA, từ đó chủ động xây dựng kiến trúc phần mềm tích hợp thư viện mật mã lai (Hybrid PQC-RSA Cryptography).
- Các tổ chức & Doanh nghiệp: Định hình bức tranh an ninh mạng trong kỷ nguyên 5.0, hoạch định ngân sách và lộ trình thay thế chữ ký số, chứng chỉ bảo mật phù hợp với tiêu chuẩn bảo vệ dữ liệu tương lai.
Câu hỏi thường gặp
1. Cần cấu hình phần cứng như thế nào để chạy thử nghiệm mã nguồn này?
Người dùng chỉ cần máy tính cá nhân cài đặt Python 3.8+ với tối thiểu 4GB RAM, cài đặt thư viện thông qua lệnh pip install qiskit qiskit-aer matplotlib pandas numpy để chạy trình giả lập aer_simulator.
2. Tại sao thuật toán Shor chỉ mất thời gian đa thức để bẻ khóa RSA?
Vì thuật toán chuyển đổi bài toán phân tích hợp số thành bài toán tìm chu kỳ hàm số, sau đó sử dụng các cổng Hadamard để tạo trạng thái chồng chất toàn phần và cổng $\text{QFT}^\dagger$ để tập trung toàn bộ biên độ xác suất vào các tần số chu kỳ chính xác, biến thời gian giải từ hàm mũ thành $O((\log N)^3)$.
3. Mật mã đối xứng như AES-256 có bị thuật toán Shor phá vỡ không?
Không. Thuật toán Shor chỉ phá vỡ các hệ mã dựa trên bài toán thừa số nguyên tố và logarit rời rạc. Mã hóa đối xứng AES bị đe dọa bởi thuật toán lượng tử Grover, nhưng Grover chỉ giúp tăng tốc độ tìm kiếm căn bậc hai $O(\sqrt{N})$. Do đó, nâng cấp khóa từ AES-128 lên AES-256 vẫn đảm bảo mức an toàn tuyệt đối trước máy tính lượng tử.
4. Khi nào máy tính lượng tử có thể phá vỡ khóa RSA-2048 trong thực tế?
Theo ước tính của các viện nghiên cứu và hãng công nghệ lớn (IBM, Google, IQM), máy tính lượng tử cần đạt khoảng 4.000 qubit logic ổn định (tương đương 1-4 triệu qubit vật lý có kèm mã sửa lỗi). Cột mốc này được dự báo sẽ khả thi trong giai đoạn từ 2030 đến 2035.
5. Chi phí triển khai và thay thế hệ thống mật mã hiện nay sang mật mã kháng lượng tử là bao nhiêu?
Việc chuyển dịch không đòi hỏi thay đổi phần cứng máy chủ mà chủ yếu là cập nhật các gói phần mềm (Patch/Update Software Layer) sang các thư viện mã nguồn mở hỗ trợ thuật toán NIST PQC (như OpenQuantumSafe). Quá trình này có thể tích hợp dần vào chi phí bảo trì và nâng cấp định kỳ của hệ thống công nghệ thông tin.
Kết luận
Khóa luận tốt nghiệp "Nghiên cứu thuật toán lượng tử Shor" của tác giả Huỳnh Phương Anh đã hoàn thành xuất sắc các mục tiêu nghiên cứu từ cơ sở lý thuyết lượng tử trừu tượng đến hiện thực hóa thành công mô hình mạch lượng tử phân tích số $N = 15$ trên framework Qiskit. Đề tài không chỉ khẳng định tính ưu việt tuyệt đối của điện toán lượng tử so với kiến trúc máy tính cổ điển mà còn gióng lên hồi chuông cảnh báo mang tính khoa học về tính an toàn của các hệ mật mã khóa công khai hiện hành. Kết quả công bố trên tạp chí chuyên ngành là minh chứng rõ nét cho giá trị học thuật và tính ứng dụng thực tiễn của công trình, đóng góp nền tảng quan trọng cho nghiên cứu công nghệ thông tin lượng tử tại Việt Nam.
