SHA-256 抗碰撞性與工作量證明數學基礎：橢圓曲線密碼學的完整推導

概述

比特幣的安全性建立在兩大密碼學支柱之上：SHA-256 哈希函數的碰撞抵抗性（Collision Resistance）和 secp256k1 橢圓曲線離散對數問題（ECDLP）的計算困難性。這兩大支柱共同構成比特幣密碼學安全的數學基礎。本篇文章從形式化數學定義出發，提供完整的密碼學推導，涵蓋 SHA-256 抗碰撞性的理論證明框架、工作量證明（Proof-of-Work）的數學模型、以及 secp256k1 橢圓曲線的群論基礎與離散對數安全性分析。

理解這些數學基礎，對於評估比特幣的長期安全性和理解其密碼學選擇具有決定性意義。

SHA-256 哈希函數的數學結構

Merkle-Damgård 結構

SHA-256 採用 Merkle-Damgård 結構（M-D 結構），這是一種將任意長度輸入轉換為固定長度輸出的通用框架，由 Ralph Merkle 和 Ivan Damgård 於 1989 年分別獨立提出。M-D 結構的核心定理（Merkle-Damgård Theorem）證明：若壓縮函數是碰撞抵抗的，則整個哈希函數也是碰撞抵抗的。

Merkle-Damgård 建構：

設：
- f: {0,1}^c × {0,1}^m → {0,1}^c 為壓縮函數（固定輸入長度）
- IV ∈ {0,1}^c 為初始值（Initial Value，常數）
- pad(x) 為填充函數，使得 |pad(x)| 是 m 的倍數
- x_1, x_2, ..., x_t 為填充後消息的 m 位元組分塊

建構：
H_0 = IV
H_i = f(H_{i-1}, x_i)    // 第 i 個區塊的哈希值
H(x) = H_t                // 最終輸出

填充函數（MD-compliant padding）：
pad(x) = x || 1 || 0^k || len(x)
其中：
- || 為串聯運算
- 1 為一個 1 位元（消息結束標記）
- 0^k 為若干個 0 位元（使總長度 ≡ c (mod m)）
- len(x) 為 x 的長度的 m 位元二進位表示

M-D 結構的安全性歸約（Merkle-Damgård Theorem）：若攻擊者能夠找到兩個不同的消息 x ≠ x' 使得 H(x) = H(x')，則攻擊者可以構造壓縮函數的碰撞。具體來說：

安全性歸約證明框架：

定理：若存在碰撞搜尋算法 A 在 H 上找到碰撞，
則可以構造算法 B 在 f 上找到碰撞。

構造：
1. 設 H(x) = H(x')，x ≠ x'
2. 令 x = x_1 || x_2 || ... || x_t（t 個分塊）
3. 令 x' = x_1' || x_2' || ... || x_t'（t' 個分塊）

令 t 為第一個使得 H_{t-1}(x) ≠ H_{t-1}(x') 的索引（必存在）。
若 x 和 x' 長度相同但內容不同，必有某個位置 i 使得差異發生。

由 M-D 結構定義：
H_i = f(H_{i-1}, x_i)
H_i' = f(H_{i-1}', x_i')

若 H_i = H_i' 且 x_i ≠ x_i'：
→ 找到 (H_{i-1}, x_i) ≠ (H_{i-1}', x_i') 使得
  f(H_{i-1}, x_i) = f(H_{i-1}', x_i')
→ 壓縮函數 f 存在碰撞！

注意：反向不成立——即使 SHA-256 的完整哈希輸出碰撞，
也不能直接推導出其內部壓縮函數的碰撞。

SHA-256 壓縮函數的詳細推導

SHA-256 的核心是 Davies-Meyer 壓縮函數，其安全性建立在橢圓曲線和有限域運算的複雜性之上：

SHA-256 壓縮函數：

輸入：
- H_{i-1} = (H_0^{(i-1)}, ..., H_7^{(i-1)})  // 8 個 32 位元工作變數
- W_i = K_i + M_i                              // 第 i 個擴展區塊 + 常數
  其中 K_i 為 64 個調度常數，M_i 為消息分塊

輸出：
- H_i = Σ_0(a) + Maj(a,b,c) + H_{i-1} + W_i + K_i
- 其中 a 到 h 為 8 個工作變數的旋轉版本

符號定義（32 位元操作）：

ROTR^n(x) = (x >> n) | (x << (32-n))   // 向右旋轉 n 位元
SHR^n(x) = x >> n                       // 向右移位 n 位元
Σ_0(x) = ROTR^2(x) ⊕ ROTR^13(x) ⊕ ROTR^22(x)  // 大 Σ_0
Σ_1(x) = ROTR^6(x) ⊕ ROTR^11(x) ⊕ ROTR^25(x)  // 大 Σ_1
σ_0(x) = ROTR^7(x) ⊕ ROTR^18(x) ⊕ SHR^3(x)    // 小 σ_0
σ_1(x) = ROTR^17(x) ⊕ ROTR^19(x) ⊕ SHR^10(x)  // 小 σ_1
Ch(e,f,g) = (e ∧ f) ⊕ (¬e ∧ g)                 // 選擇函數
Maj(a,b,c) = (a ∧ b) ⊕ (a ∧ c) ⊕ (b ∧ c)       // 多數函數

初始哈希值（IV）的選擇：

SHA-256 的初始哈希值（H0 到 H7）由前 8 個質數（2, 3, 5, 7, 11, 13, 17, 19）的平方根的小數部分的前 32 位元構成。這種選擇方法確保了 IV 沒有特殊的代數結構，防止針對特殊 IV 的預測攻擊：

質數 → 平方根 → 小數部分 → 初始值：

H_0 = floor(√2 × 2^32) mod 2^32 = 0x6a09e667
      √2 = 1.414213562373095...
      × 2^32 = 6074000000...
      小數部分 = 0.0739...
      × 2^32 = 1774986848 = 0x6a09e667 ✓

H_1 = floor(√3 × 2^32) mod 2^32 = 0xbb67ae85
H_2 = floor(√5 × 2^32) mod 2^32 = 0x3c6ef372
H_3 = floor(√7 × 2^32) mod 2^32 = 0xa54ff53a
H_4 = floor(√11 × 2^32) mod 2^32 = 0x510e527f
H_5 = floor(√13 × 2^32) mod 2^32 = 0x9b05688c
H_6 = floor(√17 × 2^32) mod 2^32 = 0x1f83d9ab
H_7 = floor(√19 × 2^32) mod 2^32 = 0x5be0cd19

64 個調度常數（K_i）的選擇：

調度常數由前 64 個質數的立方根的小數部分衍生而來：

K_0 = floor(2^(1/3) × 2^32) mod 2^32 = 0x428a2f98
K_1 = floor(3^(1/3) × 2^32) mod 2^32 = 0x71374491
...
K_63 = floor(311^(1/3) × 2^32) mod 2^32 = 0xb5c0fbcf

設計原理：
- 常數的選擇由數學事實決定（質數的無理性）
- 無人為選擇空間（no human choice）
- 攻擊者無法預先構造對特定 K_i 有利的消息

抗碰撞性的形式化分析

碰撞抵抗性的定義

密碼學哈希函數的碰撞抵抗性（Collision Resistance）從計算複雜度理論的角度定義如下：

定義（碰撞抵抗性）：

Hash Function: H: {0,1}^* → {0,1}^n

碰撞（Collision）:
存在不同的消息 m ≠ m' 使得 H(m) = H(m')

碰撞搜尋問題（Collision Search Problem）:
給定安全參數 λ（通常與 n 成正比），
在輸入空間 {0,1}^* 中找到碰撞。

碰撞抵抗性（Collision Resistance）:
若不存在多項式時間算法能以不可忽略的概率找到碰撞，
則 H 是碰撞抵抗的。

形式化：
∀ PPT 算法 A（Probabilistic Polynomial-Time）：
  Pr[ A(H) = (m, m') 且 m ≠ m' 且 H(m) = H(m') ] < negl(λ)

其中 negl(λ) 為可忽略函數（negligible function），
即隨 λ 多項式倒數的倒數：negl(λ) = O(1 / poly(λ))

生日攻擊的數學推導

生日攻擊（Birthday Attack）是找到哈希碰撞的最通用方法，其效率由生日悖論（Birthday Paradox）決定。

生日悖論分析：

設：
- d = 2^n（哈希輸出空間大小，SHA-256 中 n = 256）
- q = 選擇的消息數量
- p = 至少有一對碰撞的概率

反向分析（避免碰撞）：
- 第一個消息：p_0 = 1
- 第二個消息避免與第一個碰撞：p_1 = 1 - 1/d
- 第三個消息避免與前兩個碰撞：p_2 = 1 - 2/d
- ...
- 第 q 個消息避免與前 q-1 個碰撞：p_{q-1} = 1 - (q-1)/d

所有 q 個消息均無碰撞的概率：
P(no collision) = ∏_{i=0}^{q-1} (1 - i/d)
                ≈ exp(-∑_{i=0}^{q-1} i/d)    // 當 i/d 很小時
                ≈ exp(-q(q-1)/(2d))

因此，至少有一對碰撞的概率：
p = 1 - P(no collision)
  ≈ 1 - exp(-q(q-1)/(2d))
  ≈ q(q-1)/(2d)           // 當 q << √d 時

令 p = 0.5（50% 碰撞概率）：
q(q-1)/(2d) ≈ 1/2
q^2 ≈ d
q ≈ √d

生日攻擊複雜度：O(√d) = O(2^(n/2))
SHA-256: O(2^128) 次哈希計算

生日攻擊的實際可行性分析：

SHA-256 生日攻擊資源需求：

理論複雜度：2^128 次哈希計算
功耗估計（使用最佳 ASIC，約 100 J/TH）:
  - 每次 SHA-256 哈希: 100 pJ
  - 2^128 次哈希: 3.4 × 10^25 J
  - 全球年發電量: ~5.8 × 10^20 J
  - 需要全球發電量約 59,000 年的總產出

時間估計（使用最佳超級計算機）:
  - 假設全球所有計算力用於此攻擊
  - 2^128 / 10^18 FLOPS = 3.4 × 10^20 秒
  ≈ 宇宙年齡（138 億年）的 7,700 倍

經濟成本（比特幣礦機算力竊用估計）:
  - 2024 年比特幣網路算力: ~600 EH/s (6 × 10^20 H/s)
  - 所需時間: 2^128 / 6×10^20 ≈ 5.7 × 10^17 秒
  ≈ 宇宙年齡的 130 倍

差分密碼分析攻擊框架

差分密碼分析（Differential Cryptanalysis）是最強大的通用哈希攻擊方法，由 Biham 和 Shamir 於 1990 年提出用於攻擊 DES。對於 SHA-256，最佳的差分分析攻擊複雜度約為 2^139 次操作，但這仍遠超實際可行性。

差分密碼分析框架：

定義：
- Δx: 兩個輸入的差分（XOR）
- Δy: 兩個輸出的差分（XOR）
- P: 通過的輪數

目標：找到一個高概率差分路徑（特征）
使得 Δx → Δy 的概率最大化

SHA-256 分析結果：
- 全輪（64 輪）差分攻擊：不可行
- 減輪攻擊結果：
  - 31 輪: 2^65 次操作（2013 年）
  - 37 輪: 2^67.5 次操作（2016 年）
  - 46 輪: 2^43.5 次操作（2019 年）

結論：
- 目前無實際可行的全輪攻擊
- SHA-256 的 64 輪設計提供了極大的安全邊界
- 安全邊界約為: log_2(2^256 / 2^139) = 117 位元額外安全

碰撞攻擊對比特幣的實際影響

比特幣的多個層面依賴 SHA-256 的碰撞抵抗性：

比特幣依賴 SHA-256 的關鍵場景：

1. 交易 ID（TXID）碰撞
   - 攻擊：構造兩筆內容不同但 TXID 相同的交易
   - 影響：可能實現雙花（Double Spend）
   - 防禦：隔離見證（SegWit）將交易簽名與 TXID 分離（wtxid）
   - 攻擊複雜度：2^128 SHA-256 操作（不可行）

2. 區塊哈希碰撞
   - 攻擊：構造兩個不同區塊使其具有相同哈希
   - 影響：可能實現區塊重組（Chain Reorganization）
   - 防禦：PoW 要求使碰撞無經濟動機
   - 51% 攻擊成本遠低於碰撞攻擊

3. 公鑰哈希碰撞（位址偽造）
   - 攻擊：找到另一個公鑰使得 RIPEMD-160(SHA-256(PK)) 相同
   - 影響：盜取他人比特幣
   - 防禦：雙重哈希（RIPE160 安全性提供額外保護）
   - 攻擊複雜度：2^160 RIPEMD-160 操作

比特幣的防禦策略是分層保護（Defense in Depth）：即使 SHA-256 被碰撞，攻擊者仍需解決 RIPEMD-160（160 位元輸出空間）。而 SHA-256 的碰撞並不等同於 RIPEMD-160 的碰撞——比特幣位址的第二層哈希提供了額外的安全邊界。

工作量證明的數學模型

工作量證明的形式化定義

比特幣的工作量證明（Proof-of-Work, PoW）是一種利用哈希函數單向性構建的共識機制。其數學形式化定義如下：

工作量證明定義：

目標：找到 nonce 使得 H(BlockHeader || nonce) < Target

其中：
- H: SHA-256D（雙重 SHA-256）
- BlockHeader: 80 位元組的區塊頭
  {
    version: uint32LE,      // 區塊版本（4 位元組）
    prev_block: uint256,    // 前一區塊哈希（32 位元組）
    merkle_root: uint256,   // Merkle 根（32 位元組）
    timestamp: uint32,      // Unix 時間戳（4 位元組）
    bits: uint32,           // 壓縮目標閾值（4 位元組）
    nonce: uint32          // 隨機數（4 位元組，擴展後使用 extra_nonce）
  }
- Target: 動態調整的難度目標（由 bits 字段編碼）

難度目標的數學表達：
- Target 由 bits 字段編碼為指數-尾數形式
- Target = mantissa × 2^(8 × (exponent - 3))
- bits = exponent || mantissa
  （exponent: 高位 1 位元組，mantissa: 低位 3 位元組）

比特幣難度目標示例（2024 年）：
- bits = 0x170d 0e00（十進位：386547056）
- 指數 = 0x17 = 23
- 尾數 = 0x0d0e00 = 851968
- Target = 851968 × 2^(8×(23-3)) 
         = 851968 × 2^160
         ≈ 2.08 × 10^53

有效區塊哈希的條件：
H(BlockHeader || nonce) ∈ [0, Target)
即哈希值的前 N 位元必須為零
其中 N = 256 - log_2(Target)

零位元數（Zeros）:
- 2024 年比特幣網路：~76 個前導零位元
- 對應 Target = 2^(256-76) / D，D 為難度調整參數
- 概率：P = Target / 2^256 = 1 / (D × 2^76)

難度調整演算法的數學分析

比特幣的難度調整演算法（DAA, Difficulty Adjustment Algorithm）確保區塊時間間隔的期望值穩定在 10 分鐘。比特幣歷史上有兩個 DAA 版本：

原始 DAA（2010-2017）：

原始難度調整公式：

Target_{new} = Target_{prev} × (T_actual / T_expected)

其中：
- T_expected = 2016 × 10 分鐘 = 14 天（2 週）
- T_actual = 最近 2016 個區塊實際消耗的時間

問題：
- 算力急劇變化時，調整不及時
- 算力攻擊者可在重組期間操縱難度

現代 DAA（DAA-Cuckoo Filter，2017-至今）：

比特幣現金（BCH）分裂後，BTC 採用了新的難度調整演算法，基於 Cuckoo Filter 確保更平滑的難度調整：

現代難度調整公式（基於指數加權移動平均）：

EWMA 估計：
T_median = Median(T_last_N)  // N 個區塊時間的中位數

調整係數：
K = clamp(T_expected / T_median, 1/4, 4)
  // 單次調整幅度不超過 4 倍

Target_new = Target_prev × K

特性：
- 對單個區塊時間的異常值不敏感
- 平滑響應算力變化
- 防禦自私挖礦（Selfish Mining）

礦工收益與安全預算的形式化模型

比特幣礦工的經濟激勵可以用以下形式化模型描述：

礦工收益模型：

設：
- B_t: t 時期的比特幣區塊獎勵（每區塊 BTC）
  B_t = 50 / 2^{floor(t / 210000)} （減半機制）
- F_t: t 時期的平均交易手續費（BTC/區塊）
- P_btc: 比特幣美元價格
- H_i: 礦工 i 的算力份額
- C_i: 礦工 i 的電費成本（美元/kWh）
- η: 礦機能效（j/TH）
- E_i: 礦工 i 的收益（美元/天）

礦工每日收益：
E_i = 24 × 144 × H_i × (B_t + F_t) × P_btc - 24 × C_i

第一項（區塊獎勵收入）：
- 比特幣網路每日約出塊 144 個（6 blocks/hour × 24 hours）
- 礦工份額 × 每塊收入 × 比特幣價格

第二項（電費成本）：
- 每 TH/s × 每 J/TH = 每秒焦耳數
- 24 小時 × 3600 秒/小時 × η × C_i

礦工利潤最大化條件：
礦工 i 參與挖礦當且僅當 E_i > 0
即：C_i < 6.48 × (B_t + F_t) × P_btc × H_i / η

均衡分析：
- 當礦工利潤 > 0，新礦工進入 → H 上升
- 當礦工利潤 < 0，舊礦工退出 → H 下降
- 均衡時：礦工總算力的邊際成本 = 邊際收益

安全預算的量化分析

比特幣網路的安全性（安全預算）可以量化為攻擊者實施 51% 攻擊的成本與收益比：

51% 攻擊安全預算模型：

攻擊成本（出租算力）：
- 租用市場算力成本：$0.10 - $0.15 / TH/h（2024 年）
- 攻擊 1 小時所需算力：網路總算力的 51%
  ≈ 0.51 × 600 EH/s = 306 EH
- 攻擊 1 小時成本 ≈ 306 × 10^9 TH × $0.12/TH/h
             ≈ $36,720,000 / 小時

攻擊收益（雙花）：
- 假設單筆交易所金額：$10,000,000
- 交易所確認要求：6 個確認（約 60 分鐘）
- 攻擊收益上限：$10,000,000 / 小時

收益/成本比 = $10M / $36.7M ≈ 0.27 < 1

結論：
- 當交易所交易額 < $36.7M/h，51% 攻擊無利可圖
- 比特幣現階段安全性足夠抵禦租用市場攻擊
- 2140 年後：區塊獎勵歸零，安全預算完全依賴手續費

secp256k1 橢圓曲線的數學基礎

橢圓曲線群論

secp256k1 是一條定義在有限域 F_p（p 為質數）上的橢圓曲線，其方程為：

secp256k1 曲線方程：

y^2 = x^3 + ax + b (mod p)

參數：
a = 0
b = 7
p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
  = 115792089237316195423570985008687907853269984665640564039457584007908834671663

p 的十六進位表示：
p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

曲線上的點集合：
E(F_p) = { (x, y) ∈ F_p × F_p | y^2 ≡ x^3 + 7 (mod p) } ∪ { O }
其中 O 為無窮遠點（Identity Element）

階數（Order，趨近點的個數）：
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

n 的十六進位表示：
n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

輔助因子（Cofactor）：
h = n / |G| = 1
這意味著所有非零點都是生成元的倍數——這是 secp256k1 的關鍵特性！

為何 a = 0：secp256k1 的 a = 0 使得曲線方程簡化為 y^2 = x^3 + 7，這降低了計算複雜度，同時保持了安全性。比特幣的曲線選擇與 NIST 曲線（如 P-256）不同，後者使用非零的 a 值。

輔助因子 h = 1 的重要性：當 h = 1 時，曲線群的所有非零元素都是生成元。這避免了在簽名驗證中可能出現的「無效點」問題——在 ECDSA 中，如果計算出的 R 是「無效點」，則簽名會失敗。secp256k1 的 h = 1 特性簡化了實現並減少了潛在的側信道攻擊面。

點加法與標量乘法

橢圓曲線點加法（P ≠ Q）：

給定 P = (x_1, y_1) 和 Q = (x_2, y_2)：
P + Q = R = (x_3, y_3)

其中：
λ = (y_2 - y_1) / (x_2 - x_1) mod p
x_3 = λ^2 - x_1 - x_2 mod p
y_3 = λ × (x_1 - x_3) - y_1 mod p

幾何解釋：
- λ 是 P-Q 連線的斜率（在模 p 算術中）
- R 是該連線與曲線的第三個交點的 x 軸對稱點

特殊情況（切線）：
當 P = Q 時（倍點）：
λ = (3x_1^2) / (2y_1) mod p
x_3 = λ^2 - 2x_1 mod p
y_3 = λ × (x_1 - x_3) - y_1 mod p

離散對數問題的安全性分析

比特幣 ECDSA 簽名的安全性基於離散對數問題（Discrete Logarithm Problem, DLP）：

離散對數問題定義：

設 G 為 secp256k1 的生成元（基點）

給定：
- P = x × G （公鑰）
- G（公開）

求解：
- x ∈ [1, n-1] （私鑰）

計算複雜度：
- 目前無已知多項式時間算法（經典計算機）
- 最好算法：Pollard's Rho，複雜度 O(√n) = O(2^128)
- Grover 算法（量子）：複雜度 O(2^64)（仍不可行）

Pollard's Rho 算法的複雜度推導：

Pollard's Rho 離散對數算法：

設 G 為生成元，P 為目標點，x 為未知私鑰使得 P = x × G

算法思想：
- 使用確定的迭代函數將點序列分為三個集合
- 構造兩個序列 {x_i} 和 {x_j} 使得 x_i ≡ x_j (mod n)
- 由 F(x) 的週期性檢測碰撞

序列構造：
- 若 x mod 3 = 0: x_{k+1} = 2 × x_k mod n
- 若 x mod 3 = 1: x_{k+1} = x_k + 1 mod n  
- 若 x mod 3 = 2: x_{k+1} = P + x_k × G

衝突檢測：
- Floyd 環形探測：x_i = x_{2i} 時找到碰撞
- 此時：x_i × G = x_{2i} × G
- 即：(x_i - x_{2i}) × G = O
- x = (x_{2i} - x_i)^(-1) × (y_{2i} - y_i) mod n

期望碰撞時間：
- 生日悖論：碰撞概率 50% 時需要 O(√n) 步
- n ≈ 2^256
- √n = 2^128 步

2^128 的意義：
- 需要 2^128 次曲線加法運算
- 每秒 10^18 次操作的超級計算機
- 需要 2^128 / (10^18 × 3.15×10^7) ≈ 10^22 年

ECDSA 簽名的安全性分析

比特幣使用的 ECDSA（NIST P-256K1，secp256k1）簽名算法安全性分析：

ECDSA 簽名流程：

金鑰生成：
1. 選擇隨機私鑰 d ∈_R [1, n-1]
2. 公鑰 Q = d × G

簽名生成（消息 m）：
1. 計算 e = H(m)（SHA-256 哈希，取 mod n）
2. 選擇隨機 nonce k ∈_R [1, n-1]
3. 計算 R = k × G = (x_R, y_R)
4. 計算 r = x_R mod n（若 r = 0，重新選擇 k）
5. 計算 s = k^(-1) × (e + r × d) mod n（若 s = 0，重新選擇 k）
6. 簽名：(r, s)

簽名驗證：
1. 計算 e = H(m) mod n
2. 計算 w = s^(-1) mod n
3. 計算 u_1 = e × w mod n
4. 計算 u_2 = r × w mod n
5. 計算 P = u_1 × G + u_2 × Q
6. 若 P = O 或 x_P = 0，則簽名無效
7. 驗證 r = x_P mod n ✓

數學推導（驗證原理）：
由 s = k^(-1)(e + rd) 得：
  k = s^(-1)(e + rd) mod n
  kG = s^(-1)(eG + rQ) = u_1G + u_2Q ✓

Nonce 重用風險的量化分析：

ECDSA 最危險的安全漏洞是 nonce（k 值）的重用。當兩個不同的消息使用相同的 k 簽名時：

若同一私鑰 d 簽署兩個消息 m_1 和 m_2，使用相同的 k：

簽名 1: (r, s_1) 其中 s_1 = k^(-1)(e_1 + r×d) mod n
簽名 2: (r, s_2) 其中 s_2 = k^(-1)(e_2 + r×d) mod n

由兩個簽名推導私鑰：

s_1 - s_2 = k^(-1)(e_1 - e_2) mod n
k = (e_1 - e_2) / (s_1 - s_2) mod n

代入：
d = (s_1 × k - e_1) / r mod n

實際案例：
- 2010 年比特幣客戶端：同一 nonce 被重用
- Sony PlayStation 3 ECDSA：靜態 nonce 導致私鑰泄露
- 多個比特幣錢包：RNG 失敗導致私鑰丢失

防禦：RFC 6979 確定性 nonce（HMAC 構造 k = HMAC(d || m)）

密碼學安全性的長期威脅

量子計算威脅的量化分析

Shor's 算法對離散對數問題的量子加速是比特幣面臨的長期密碼學威脅：

Shor's 算法對 ECDSA 的威脅：

量子計算模型：
- 量子位元（Qubit）：疊加態的基礎單元
- 量子閘：可逆的幺正變換（Unitary Transformation）
- 量子測量：從疊加態中讀取確定性結果

Shor's 算法步驟（離散對數版本）：
1. 準備疊加態：|a⟩|b⟩ 其中 a, b ∈ [0, n-1]
2. 構造 |a⟩|b⟩ → |a⟩|b + a×x⟩（其中 P = x×G）
3. 對第一個暫存器執行 QFT（量子傅立葉變換）
4. 測量，提取週期
5. 利用週期計算 x

複雜度：
- 量子閘複雜度：O((log n)^3) ≈ O(10^4) 量子閘
- 量子位元需求：O(log n) ≈ 256 個量子位元

物理需求（2024 年技術評估）：
- 實用 Shor's 攻擊需要 ~4000 邏輯量子位元
- 每個邏輯量子位元需要 ~1000 物理量子位元（錯誤校正）
- 總需求：~4,000,000 物理量子位元
- 2024 年最先進量子計算機：~1000 物理量子位元（IBM Condor）
- 差距：~4000 倍

Grover 算法對 SHA-256 的威脅：
- 搜索複雜度從 O(2^256) 降低到 O(2^128)
- 需要約 256^2 × log(256) ≈ 70,000 邏輯量子位元
- 同樣存在巨大的物理實現差距

結論

比特幣的密碼學安全性建立在 SHA-256 的抗碰撞性、secp256k1 的 ECDLP 困難性和 ECDSA 的簽名安全性三大支柱之上。形式化分析表明：

1. SHA-256 碰撞攻擊：生日攻擊需要 2^128 次哈希計算，在物理和經濟上均不可行。差分密碼分析的最佳攻擊約為 2^139，仍不可行。

1. 工作量證明：比特幣 PoW 的數學模型確保區塊時間間隔的期望值為 10 分鐘，難度調整機制平滑響應算力變化。礦工收益模型的均衡分析表明，比特幣現階段的安全預算足以抵禦 51% 攻擊。

1. ECDLP 安全性：secp256k1 的離散對數困難性由 Pollard's Rho 算法的 2^128 次操作下界保證。即使是量子計算機，也需要約 4000 邏輯量子位元才能威脅 ECDSA——這在短期內是物理上不可實現的。

1. 後量子遷移：BIP-360 框架代表了比特幣應對量子威脅的初步策略，其混合簽名方案在經典和量子威脅下均保持安全性，為比特幣提供了面向未來的密碼學保障。