九思札记 · 探索区块链 · AI

量子计算不"加速一切"——它只加速少数特定数学问题。但不幸的是，这些少数问题恰好是区块链安全最依赖的基石：椭圆曲线离散对数和整数素因数分解。这节将精确计算"到底多危险"。

11.2.1 Shor 算法：公钥密码的末日

问题背景

现代非对称密码（ECDSA、RSA、Ed25519）都基于同一个数学难题：

\text{给定 } P = xG \text{ 和 } G, \text{ 求 } x

即离散对数问题（DLP）。在经典计算机上，最佳已知算法（BSGS、Pollard's Rho）需要：

T_{\text{classical}} = O(\exp((\log N)^{1/3}(\log \log N)^{2/3})) \approx O(2^{n/2})

当 $n=256$ 时（secp256k1）， $T_{\text{classical}} \approx 2^{128}$ 操作——宇宙也跑不完。

Shor 算法：量子多项式时间

Shor 算法（1994）通过量子傅里叶变换在量子计算机上将 DLP 降为：

T_{\text{Shor}} = O((\log N)^3) = \text{poly}(n)

具体而言，256 位 ECDSA 在量子计算机上的破解时间：

\text{量子位需求: } n_q \approx 2n + \lceil \log_2(2n) \rceil + C \approx 2330 \text{ 逻辑量子位（最小估计）}

而当前最先进的量子计算机（IBM Osprey: 433 物理量子位，2023）还需扩展数千倍。

威胁时间线评估

里程碑	逻辑量子位	进展估计
当前领先	~50-100	2024 年（纠错后约 50 有效）
IBM 路线图	1000（2029）	2030-2035
学术共识（乐观）	100,000	2040 年后
足够破解 ECDSA	2,000+	2045-2050?

gantt
    title 量子威胁时间线
    dateFormat YYYY
    section 量子硬件
    100 逻辑量子位 :done, 2024, 2026
    1000 逻辑量子位 :active, 2029, 2032
    稳定性和纠错突破 :2032, 2035
    足够破解 ECC :crit, 2040, 2050
    section 区块链
    后量子标准完成 :done, 2024, 2025
    主流公链迁移 :active, 2030, 2040
    抗量子签名激活 :2035, 2045

11.2.2 Grover 算法：哈希函数的二次加速

对称密码的减半危机

Grover 算法（1996）提供通用搜索二次加速：

T_{\text{Grover}} = O(\sqrt{N}) = O(2^{n/2})

这意味着 $n$ -bit 哈希的抗碰撞强度从 $2^n$ 降低到 $2^{n/2}$ 。但更重要的是——用于工作量证明的哈希搜索：

\text{挖矿难度 } D \propto 2^{n}\quad \Rightarrow \quad T_{\text{Grover}} \propto 2^{n/2}

但这只是二次加速，而非 Shor 的指数加速。对于 256 位哈希：

\text{经典密码安全级别: } 2^{256}\quad \xrightarrow{\text{Grover}}\quad 2^{128}

$2^{128}$ 仍然是天文数字。结论：哈希函数和 PoW 只需要更长位数（从 256 到 512 位），而公钥密码需要完全更换算法。

11.2.3 "先收集，后解密"（Harvest Now, Decrypt Later）

最实际的威胁

即使功能性量子计算机要到 2040 年才出现，威胁现在已经存在：

今日记录：攻击者存储所有链上交易和公钥
未来破解：一旦量子计算机可用，立即用 Shor 算法恢复所有历史私钥
时间上的单向灾难：即使未来切换了抗量子签名，历史暴露的数据已无法收回

这就要求：公链必须在第一条足够强大的量子计算机出现之前，完成大规模密码学迁移。

sequenceDiagram
    participant A as 攻击者（Today）
    participant C as 区块链
    participant Q as 量子计算机
    
    A->>C: 持续记录所有交易 + 公钥
    A->>A: 存储加密数据
    
    Note over A,Q: 15-20 年后
    
    Q->>A: 足够计算能力
    A->>A: 对历史公钥运行 Shor 算法
    A->>C: 恢复所有历史私钥 -> 窃取资产
    
    Note over C: 即使此时已升级签名<br/>历史交易数据已永久暴露

11.2.4 威胁评估：数据与后果

当前区块链的暴露面

系统	受 Shor 影响	受 Grover 影响	攻击后果
比特币	地址公钥（已花费）	PoW 挖矿	历史私钥暴露但无法双花，但隐私泄露
以太坊	地址公钥（所有）	PoS 签名	私钥恢复 = 全部资产盗窃
TLS/HTTPS	握手期间所有公钥	不适用	全部历史通信解密
Tor 网络	握手期间	不适用	去匿名化历史流量

紧迫性评估

typescript

/**
 * 量子威胁时间线评估模型
 * 评估不同密码学基元在量子计算下的预计"安全期"
 */
interface Cryptosystem {
  name: string;
  classicalSecurity: number;  // 经典安全位数
  quantumResistance: "broken" | "halved" | "intact";
  threatModel: string;
  migrationUrgency: "critical" | "high" | "medium" | "low";
}

function assessQuantumThreat(cs: Cryptosystem): {
  safeYears: number;       // 预计安全年限
  recommendedAction: string;
} {
  const threatYears = {
    "critical": { min: 15, max: 25, action: "立即开始迁移，历史数据暴露不可逆" },
    "high": { min: 20, max: 35, action: "制定迁移路线图，预留充足时间" },
    "medium": { min: 30, max: 50, action: "关注标准进展，准备基础设施" },
    "low": { min: 50, max: 100, action: "持续监控，无需立即行动" },
  };
  
  const urgency = threatYears[cs.migrationUrgency];
  return {
    safeYears: Math.round((urgency.min + urgency.max) / 2),
    recommendedAction: urgency.action,
  };
}

const systems: Cryptosystem[] = [
  { name: "ECDSA (secp256k1)", classicalSecurity: 128, quantumResistance: "broken", threatModel: "Shor 算法多项式破解", migrationUrgency: "critical" },
  { name: "RSA-2048", classicalSecurity: 112, quantumResistance: "broken", threatModel: "Shor 多项式破解", migrationUrgency: "critical" },
  { name: "SHA-256 哈希", classicalSecurity: 256, quantumResistance: "halved", threatModel: "Grover 二次加速", migrationUrgency: "medium" },
  { name: "EdDSA (Ed25519)", classicalSecurity: 128, quantumResistance: "broken", threatModel: "Shor 变种", migrationUrgency: "critical" },
  { name: "ECC 密钥交换 (TLS)", classicalSecurity: 128, quantumResistance: "broken", threatModel: "Shor 破解", migrationUrgency: "critical" },
  { name: "AES-256-GCM", classicalSecurity: 256, quantumResistance: "halved", threatModel: "Grover 降至 128 位", migrationUrgency: "medium" },
  { name: "zk-SNARK (配对)", classicalSecurity: 128, quantumResistance: "broken", threatModel: "配对被量子破解", migrationUrgency: "high" },
  { name: "zk-STARK (哈希)", classicalSecurity: 128, quantumResistance: "intact", threatModel: "哈希抗碰撞假设", migrationUrgency: "low" },
];

console.log("量子威胁评估");
console.log("系统 | 经典安全 | 量子状态 | 安全期 | 建议");
for (const s of systems) {
  const a = assessQuantumThreat(s);
  console.log(` ${s.name.padEnd(25)} |$ {s.classicalSecurity.toString().padStart(4)} |  ${s.quantumResistance.padStart(8)} |$ {a.safeYears.toString().padStart(5)}年 | ${a.recommendedAction}`);
}

11.2.5 知识地图

mindmap
  root((量子威胁))
    Shor 算法
      因子分解
      离散对数
      poly(log N)
      2,330 逻辑量子位需求
    Grover 算法
      通用搜索 sqrt(N)
      哈希安全减半
      2^256 → 2^128
    先收集后解密
      今日记录
      未来破解
      不可逆暴露
    紧迫性评估
      公钥: 关键
      哈希: 中等
      AES: 中等
      ZK 配对: 高
      ZK 哈希: 低

> ← 上一节：11.1 AI × 区块链 | 前往 → 11.3 后量子密码学标准 |*

本页目录