ECC

數學時間

橢圓曲線

• Weierstrass方程式
  • $y^2 = x^3+ax+b$
• 橢圓加法
  • $P+Q=R$
  • 則-R是PQ線段延伸的焦點
  • R是對稱軸
• 橢圓乘法
  • 因為$2*P = P+P$，所以可以看成P點切線，剩下定義差不多了

橢圓曲線與$GF(p)$

給定質數p，可以滿足$y^3 = x^2+ax+b \mod p$且 $4·a^3 + 27·b^2 \neq 0$ 令$P(x_1, y_1), Q(x_2, y_2), R(x_3, y_3)$

• $P + Q = R$
  • $x_3 = s^2 - x_1 - x_2 \mod p$
  • $y_3 = s(x_1 - x_3) - y_1 \mod p$
  • $s$的部分
    • 當$P=Q$: $\frac{3x_1^2+a}{2y_1} \equiv (3x_1^2+a)(2y_1)^{-1}$
    • 當$P\neq Q$: $\frac{y_2-y_1}{x_1-x_2} \equiv (y_2-y_1)(x_1-x_2)^{-1}$
  • 證明先跳過

密碼學時間

一些名詞

• 點加法：上面那一堆就是
• 標量乘法：看成$2P = P + P$就可以
• 基點：選擇曲線上的一個點作為基點G，所有操作都基於這個點
• 階：最小的正整數n，使得nG = O（O是無窮遠點）

應用

• ECIES：橢圓曲線加解密演算法
• ECDSA：橢圓曲線簽名演算法
• ECDH：金鑰交換

ECIES：橢圓曲線加解密演算法

前言

• 明文M：要先將明文編碼成點
• r : 隨機數
• 密文C: 兩點(橢圓曲線上)的集合

密鑰生成

• 橢圓曲線表達
  • ${a, b, p, G, n}$
    • $a, b$: 橢圓曲線兩常數
    • $p$: 有限域
    • $G$: 基點
    • $n$: 階
• 公鑰私鑰
  • 私鑰k: random value，通常是512 bits
  • 公鑰K: $K = kG$

加密

• $C_1 = rG$
• $C_2 = M + rK$
• 所成點對${C_1, C_2}$就是密文C

解密

• $M = C_2 - kC_1$
• pf:
  • 因$C_2 = M + rK$，而$K = kG$，故$C_2 = M + rK = M + rkG$
  • 因此$C_2 - kC_1 = M + rkG - krG = M$

ECDSA：橢圓曲線簽名演算法

簽章

• 選定隨機值$e ,e\in [1, n-1]$
• $r = (eM).x$ (r是eM的x座標)
• $s = \frac{H(M) + k r}{e} = (H(M) + k r) e^{-1} \bmod p$
• 簽章：${r, s}$

驗章

• $u_1 = H(M) * s^{-1} \mod p$
• $u_2 = r * s^{-1} \mod p$
• 則$R = u_1G+ u_2K$
• 只要驗證R的x座標是否共餘r，如果是就是正確的簽章

ECDH：金鑰交換

• 講簡單點就是Diffie-Hellman ECC版
• 一開始要溝通好橢圓曲線
• Alice
  • PRI: $k_1$ => 整數
  • PUK: 生成點$Q_1 = k_1G$
• Bob
  • PRI: $k_2$ => 整數
  • PUK: 生成點$Q_2 = k_2G$
• 雙方把自己的公鑰傳給對方
• 最後
  • Alice: $(x_k, y_k) = k_1Q_2$
  • Bob : $(x_k, y_k) = k_2Q_1$
• 接著AB就有它們的秘密$x_k$
• 比較

---

• Previous
  CVE-2017-17215

---