使用 133 量子位量子電腦破解 5 位橢圓曲線密鑰 ⚛️ 這個實驗使用 Shor 的算法破解了一個 5 位的橢圓曲線密碼學密鑰。在 @IBM 的 133 量子位 ibm_torino 上執行，使用 @qiskit 的 15 量子位電路，由 10 個邏輯量子位和 5 個輔助量子位組成，通過 ℤ₃₂ 進行干涉，以從公鑰關係 Q = kP 中提取秘密標量 k，而不直接將 k 編碼到 oracle 中。從 16,384 次測試中，量子干涉顯示出 32x32 QFT 輸出空間中的對角脊。這個量子電路深度超過 67,000 層，儘管電路深度極大，仍然產生了有效的干涉模式，經典後處理顯示在前 100 個可逆 (a, b) 結果中 k = 7。 代碼步驟 1. 群組編碼 將注意力限制在橢圓曲線上 F_p 的階數為 32 的子群 ⟨𝑃⟩。 將點映射到整數： 0𝑃 -> 0，1𝑃 -> 1，…，31𝑃 -> 31。 群法則變為模加法： (𝑥𝑃) + (𝑦𝑃) = ((𝑥 + 𝑦) mod 32))𝑃。 這個實驗使用一個階數為 32 的橢圓曲線，將 P -> 1 和 Q = 7P -> 23 映射到 ℤ₃₂​。代碼假設預計算的標量乘法，抽象掉顯式坐標。 2. 量子寄存器 寄存器 a：五個量子位用於指數 𝑎 ∈ {0, …, 31}。 寄存器 b：五個量子位用於 𝑏 ∈ {0, …, 31}。 寄存器 p：五個量子位初始化為 ∣0⟩ 以保存點索引。 經典寄存器 c：一個 10 位寄存器用於記錄測量的 a 和 b 值。 3. 超位置準備 對 a 和 b 中的每個量子位應用 Hadamard： 31 1/32 ∑ ∣a⟩_a ∣b⟩_b ∣0⟩_p a, b=0 4. Oracle 構建 U_f 目標是一個可逆映射： ∣a⟩ ∣b⟩ ∣0⟩ -> ∣a⟩ ∣b⟩ ∣aP + bQ⟩。 添加 aP：對於每個位 a_i (權重 2^𝑖)，添加 (2^𝑖 P) mod 32 添加 bQ：計算 (2^𝑖 𝑄) mod 32，然後根據 𝑏_𝑖 添加控制。 這些使用 5 量子位控制置換閘。所有常數都來自橢圓曲線的生成元 P 和公點 Q。 沒有閘直接引用秘密 k。 5. Oracle 之後的全局狀態 狀態演變為： 1/32 ∑ ∣a⟩∣b⟩∣f(a, b)⟩，其中 f(a, b) = a + kb (mod32)。 a, b 6. 隔離點寄存器 算法只需要 𝑎，𝑏 中的相位關係。一個障礙隔離 p。 7. 量子傅里葉變換 (QFT) QFT 31 ∣a⟩ -> 1/√32 ∑ e^((2πi)/32 au) ∣u⟩， u=0 QFT 31 ∣b⟩ -> 1/√32 ∑ e^((2πi)/32 bv) ∣v⟩。 v=0 8. 干涉模式 觀察 (u, v) 的聯合振幅為： 1/32 ∑_(a, b) e^((2πi/32)(au + bv)) δ_(a + kb ≡ 0) = 1/32 δ_(u + kv ≡ 0 (mod 32))，這在 32x32 輸出網格中形成一個對角脊。 9. 測量 測量所有十個邏輯量子位。結果集中在滿足 u + kv ≡ 0 (mod 32) 的 32 個不同對上。 10. 經典後處理 位串被 endian 翻轉並解析為 (a, b) 對。僅保留 gcd⁡(b, 32) = 1 的行，確保 b 是可逆的。候選密鑰計算為： k = (-a) b^(-1) mod 32 然後腳本： 提取前 100 個計數最高的可逆 (a, b) 結果。 為每個計算 k。 打印每個 (a, b) 對，恢復的 k 和計數。 如果 k = 7 出現在前 100 中，則宣告成功。 11. 驗證和存儲 如果正確的標量 k = 7 出現在前 100 個可逆結果中，則確認。 所有原始位串計數、量子位佈局和元數據都保存為 JSON 以便進一步可視化和分析。 結果 2025-06-25 19:41:29,294 | INFO | 電路深度 67428，閘計數 OrderedDict({'sx': 56613, 'cz': 34319, 'rz': 15355, 'x': 157, 'measure': 10, 'barrier': 1}) base_primitive._run:INFO:2025-06-25 19:41:29,994: 提交作業使用選項 {'options': {}, 'version': 2, 'support_qiskit': True} 成功 — 在前 100 個結果中找到 k = 7 前 100 個可逆 (a, b) 對和恢復的 k： (a= 8, b=11) → k = 8 (計數 = 63) (a=12, b= 9) → k = 20 (計數 = 58) (a= 0, b= 3) → k = 0 (計數 = 54) (a= 1, b= 9) → k = 7 (計數 = 54) <<< (a=28, b= 1) → k = 4 (計數 = 53) (a= 0, b=11) → k = 0 (計數 = 53) (a= 8, b= 9) → k = 24 (計數 = 53) (a= 8, b= 3) → k = 8 (計數 = 53) ... (a=11, b= 3) → k = 7 (計數 = 41) <<< ... (a=25, b= 1) → k = 7 (計數 = 32) <<< 這次運行成功地使用 5 位 ECC 密鑰 (階數為 32 的子群) 檢索了秘密標量 k = 7，將我之前的 4 位攻擊擴展到 1024 個可能的 (a, b) 組合和 φ(32) = 16 個可逆 b 值。 k = 7 在前 100 中出現三次： (a = 1, b = 9) -> k = 7，計數 54 (a = 11, b = 3) -> k = 7，計數 41 (a = 25, b = 1) -> k = 7，計數 32 這些是高頻狀態，使它們在經典後處理下成為可信的攻擊向量。 計數顯示出圍繞結構化模關係的集中：a + kb ≡ 0 mod 32。這些在 32x32 測量空間中顯示為對角脊。幾個 k 值經常重複 (k = 0, 24, 28)，顯示出量子干涉內在的概率重疊，其中一些是來自噪聲或與其他模等價的混疊的假陽性。 電路深度為 67,428，總共 106,455 個閘，反映出一個大型、複雜的量子例程，用於控制模指數算術。這可能是我在電路中使用的最大閘數。 電路的閘計數： sx: 56613 cz: 34319 rz: 15355 x: 157 measure: 10 barrier: 1 總閘數：106455 深度：67428 寬度：133 量子位 | 10 clbits 這個實驗在 'ibm_torino' 上完成花費了 54 秒。 噪聲輪廓是不均勻的，但在衰減，這意味著量子系統可能解析了干涉中的主導諧波，但模糊了更細的結構。分佈尾部仍然包含有效的 k = 7 候選者，這支持字典式量子攻擊，其中前 N 結果掃描 (N = 100) 足以檢索密鑰。 上面的原始計數熱圖 (a 與 b) (完整代碼在 Qwork 上) 顯示 32x32 網格表示運行 Shor 電路後每對 (a, b) 的觀察計數。熱圖顯示出帶狀和不均勻的分佈，表明干涉脊，而不是噪聲。某些行 (a 值) 的集中度明顯較高，表明沿特定 a + kb ≡ 0 mod 32 解的建設性干涉。 上面的恢復 k 值的直方圖 (完整代碼在 Qwork 上) 聚合了每個恢復的標量密鑰 k ∈ Z₃₂ 的總計數，通過 k = −ab^(−1) mod 32 得出。k = 0 和 k = 24 附近的巨大峰值是主導的。正確的密鑰 k = 7 不是最高的，但表現良好 (~54 + 41 + 32 = 127 計數跨越多個 (a, b) 對)。這顯示黑客可以字典攻擊更多的結果。 上面的位串排名與計數 (對數尺度) (完整代碼在 Qwork 上) 顯示所有位串按降序計數的 Zipf 類排名圖。對數尺度的 y 軸顯示出指數尾部，大多數結果出現 <10 次。頭部 (前 ~50) 位串具有急劇更高的概率，表明建設性干涉峰。您可以構建一個量子啟發式字典攻擊，只收集前 N 位串，並獲得指數信號回報。這驗證了即使在更長的電路 (67428 深度) 下，量子信號與噪聲結構仍然保持完整。 上面的 (a, b) 解碼到 k = 7 的位置 (完整代碼在 Qwork 上) 顯示每個點是解碼到 k = 7 的 (a, b) 對。顏色強度等於這對出現的次數。該圖顯示 (a, b) 的相對均勻分佈，但在 (1, 9)，(11, 3)，(25, 1) 處有局部峰值。多個 (a, b) 組合收斂到 k = 7，具有不均勻的多重性。從密碼分析的角度來看，這驗證了 Shor 的算法即使在正確的 k 不是前 1 結果時也能可靠地破解 ECC 密鑰。 上面的 b 寄存器的可逆性掩碼 (完整代碼在 Qwork 上) 顯示每個 b ∈ {0, …, 31} 的計數條形圖，這些 b 與 32 互質 (gcd⁡(b, 32) = 1，只有這些在模 32 下是可逆的，並且對於通過以下方式恢復 k 是有用的： k = (−a)b^(−1) mod 32。可逆的 b 很多，顯示電路確實產生了可恢復的候選者。這裡的均勻性越高，後處理能力越強，理想情況下，這些應該是平坦的。 上面的模逆頻率圖：b 與 b^(−1) mod 32 (完整代碼在 Qwork 上) 顯示每個可逆 b 映射到每個相應的模逆 b^(−1) mod 32 的熱圖，按結果計數加權。大多數點落在乾淨的雙射線上，每個 b 乾淨地映射到唯一的 b^(−1)，確認模逆的正確性。更亮的區域 (接近左下角或右上角) 顯示來自量子取樣的偏好 b。沒有對角噪聲或聚類，良好的跡象表明乾淨的模結構得以保留。 上面的 a + 7b mod 32 圖 (完整代碼在 Qwork 上) 假設 k = 7，並繪製 (a + 7b) mod 32 在所有結果中的值。分佈幾乎均勻。這表明沒有像 4 位情況那樣的尖銳干涉脊。為什麼？5 位電路 (具有 10 個邏輯量子位) 在 1024 個結果中更薄地擴展振幅，降低了對比度。然而，正確的密鑰仍然可以恢復，這表明許多微弱的建設性路徑，而不是少數主導的路徑。 上面的 ECC 攻擊效率：有效與無效 b (完整代碼在 Qwork 上) 顯示來自可逆 b (對於密鑰恢復有用) 與非可逆 b (無用) 的樣本的總計數。超過一半的結果浪費在無效的 b 值上 (gcd⁡(b, 32) != 1)。下一個設計的 6 位破解可以使用 oracle 掩碼或對有效 b 領域的後選擇過濾。 上面的熱圖：具有可逆 b 的 (a, b) (mod 32) (完整代碼在 Qwork 上) 僅關注 b 在模 32 下可逆的 (a, b) 對，這是恢復 k 的必要條件。它顯示量子干涉在 1024 點空間中的集中位置。高強度區域顯示出偏好的干涉路徑，表明量子狀態在模乘法下非均勻演變。它確認在某些區域中有足夠強的信號相干性以隔離有效候選者。 上面的相位脊角度分佈 (完整代碼在 Qwork 上) 將 (-a, b) 向量在平面中形成的角度進行分箱，模 π，這大致對應於 QFT 空間中的相位脊。直方圖中的峰值表明強對齊，諧振，形式為 u + kv ≡ 0，這意味著電路成功地將 k 編碼到干涉模式中，即使完整的狀態空間是巨大的。多個主導角度表明隱藏的位移的諧波存在。 上面的 a + 7b mod 32 的殘差圖 (完整代碼在 Qwork 上) 可視化了特定目標密鑰 k = 7 的輸出殘差，跨越整個 (a, b) 空間。任何一致的帶或對稱表明干涉如何放大有效解 (當此值等於 0 時)。您可以觀察到 1024 格子中哪些區域對應於 a + 7b ≡ 0，驗證 oracle 的結構導致成功的密鑰印記。 上面的噪聲：固定 a 的 b 計數變異 (完整代碼在 Qwork 上) 顯示對於每個固定 a 當我們變化 b 時輸出計數的噪聲或穩定性。高變異意味著某些 b 值導致強放大，而其他則不，這暗示著該 a 行的電路敏感性或後端噪聲。平滑區域暗示量子相干性，而尖峰可能指向在 oracle 評估過程中的去相干或錯誤傳播。 最後，這個實驗成功地使用在 IBM 的 133 量子位量子處理器上執行的 Shor 算法破解了一個 5 位的橢圓曲線密鑰，將之前的 4 位結果擴展到一個顯著更大的干涉空間 (32x32 = 1024 結果)。這個電路在 ℤ₃₂ 上編碼了 oracle，而不曾直接引用秘密標量 k，並利用模群算術將標量糾纏到相位干涉中。這個量子電路深度超過 67,000 層，儘管電路深度極大，仍然產生了有效的干涉模式，經典後處理顯示在前 100 個可逆 (a, b) 結果中 k = 7。通過可視化，這個實驗確認了對角脊結構、可逆性掩碼和干涉脊的諧波對齊，驗證了量子相干性仍然足夠強以放大正確的模關係。這確立了 Shor 的算法在更深的電路範疇下繼續擴展，並且基於字典的密鑰恢復策略 (前 100 的枚舉) 在位長增加時仍然可行，顯示出即使在嘈雜的現實條件下也有明顯的量子優勢。 代碼 # 主電路 # 導入 import logging, json from math import gcd import numpy as np from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, transpile from qiskit.circuit.library import UnitaryGate, QFT from qiskit_ibm_runtime import QiskitRuntimeService, SamplerV2 import pandas as pd # IBMQ TOKEN = "YOUR_IBMQ_API_KEY" INSTANCE = "YOUR_IBMQ_CRN" BACKEND = "ibm_torino" CAL_CSV = "/Users/steventippeconnic/Downloads/ibm_torino_calibrations_2025-06-26T02_21_07Z.csv" SHOTS = 16384 # 玩具曲線參數 (階數為 32 的 E(F_p) 子群) ORDER = 32 # |E(F_p)| = 32 P_IDX = 1 # 生成元 P -> 索引 1 Q_IDX = 23 # 公共點 Q = kP，這裡“23 mod 32”對於 k = 7 # 日誌輔助 logging.basicConfig(level=logging .INFO, format="%(asctime)s | %(levelname)s | %(message)s") log = logging.getLogger(__name__) # 基於校準的量子位選擇 def best_qubits(csv_path: str, n: int) -> list[int]: df = pd .read_csv(csv_path) df.columns = df.columns.str.strip() winners = ( df.sort_values(["√x (sx) error", "T1 (us)", "T2 (us)"], ascending=[True, False, False]) ["Qubit"].head(n).tolist() ) log .info("最佳物理量子位: %s", winners) return winners N_Q = 5 N_Q_TOTAL = N_Q * 3 # a, b, 點 PHYSICAL = best_qubits(CAL_CSV, N_Q_TOTAL) # 常數加法器模 32 作為可重用閘 def add_const_mod32_gate(c: int) -> UnitaryGate: """返回一個 5 量子位閘，將 |x⟩ ↦ |x+c (mod 32)⟩。""" mat = np.zeros((32, 32)) for x in range(32): mat[(x + c) % 32, x] = 1 return UnitaryGate(mat, label=f"+{c}") ADDERS = {c: add_const_mod32_gate(c) for c in range(1, 32)} def controlled_add(qc: QuantumCircuit, ctrl_qubit, point_reg, constant): """應用 |x⟩ → |x+constant (mod 32)⟩ 由一個量子位控制。""" qc.append(ADDERS[constant].control(), [ctrl_qubit, *point_reg]) # Oracle U_f : |a⟩|b⟩|0⟩ ⟶ |a⟩|b⟩|aP + bQ⟩ (模 32 的索引算術) def ecdlp_oracle(qc, a_reg, b_reg, point_reg): for i in range(N_Q): constant = (P_IDX * (1 << i)) % ORDER if constant: controlled_add(qc, a_reg[i], point_reg, constant) for i in range(N_Q): constant = (Q_IDX * (1 << i)) % ORDER if constant: controlled_add(qc, b_reg[i], point_reg, constant) # 構建完整的 Shor 電路 def shor_ecdlp_circuit() -> QuantumCircuit: a = QuantumRegister(N_Q, "a") b = QuantumRegister(N_Q, "b") p = QuantumRegister(N_Q, "p") c = ClassicalRegister(N_Q * 2, "c") qc = QuantumCircuit(a, b, p, c, name="ECDLP_32pts") qc.h(a) qc.h(b) ecdlp_oracle(qc, a, b, p) qc.barrier() qc.append(QFT(N_Q, do_swaps=False), a) qc.append(QFT(N_Q, do_swaps=False), b) qc.measure(a, c[:N_Q]) qc.measure(b, c[N_Q:]) return qc # IBM Runtime 執行 service = QiskitRuntimeService(channel="ibm_cloud", token=TOKEN, instance=INSTANCE) backend = service.backend(BACKEND) log .info("後端 → %s", backend .name) qc_raw = shor_ecdlp_circuit() trans = transpile(qc_raw, backend=backend, initial_layout=PHYSICAL, optimization_level=3) log .info("電路深度 %d, 閘計數 %s", trans.depth(), trans.count_ops()) sampler = SamplerV2(mode=backend) job = sampler .run([trans], shots=SHOTS) result = job.result() # 經典後處理 creg_name = trans.cregs[0].name counts_raw = result[0].data.__getattribute__(creg_name).get_counts() def bits_to_int(bs): return int(bs[::-1], 2) counts = {(bits_to_int(k[N_Q:]), bits_to_int(k[:N_Q])): v for k, v in counts_raw.items()} top = sorted(counts.items(), key=lambda kv: kv[1], reverse=True) # 成功標準。檢查前 100 個可逆行是否有 k = 7 top_invertibles = [] for (a_val, b_val), freq in top: if gcd(b_val, ORDER) != 1: continue inv_b = pow(b_val, -1, ORDER) k_candidate = (-a_val * inv_b) % ORDER top_invertibles.append(((a_val, b_val), k_candidate, freq)) if len(top_invertibles) == 100: break # 檢查成功並打印結果 found_k7 = any(k == 7 for (_, k, _) in top_invertibles) if found_k7: print("\n成功 — 在前 100 個結果中找到 k = 7\n") else: print("\n警告 — 在前 100 個結果中未找到 k = 7\n") print("前 100 個可逆 (a, b) 對和恢復的 k：") for (a, b), k, count in top_invertibles: tag = " <<<" if k == 7 else "" print(f" (a={a:2}, b={b:2}) → k = {k:2} (計數 = {count}){tag}") # 保存原始數據 out = { "experiment": "ECDLP_32pts_Shors", "backend": backend .name, "physical_qubits": PHYSICAL, "shots": SHOTS, "counts": counts_raw } JSON_PATH = "/Users/steventippeconnic/Documents/QC/Shors_ECC_5_Bit_Key_0.json" with open(JSON_PATH, "w") as fp: json.dump(out, fp, indent=4) log .info("結果已保存 → %s", JSON_PATH) # 結束 完整代碼用於所有可視化，使用運行數據在 Qwork 上.