---
lang: zh-tw
tags: NTHU, Notes, Cryptocurrency
date: 20210318
robots: noindex, nofollow
license: GPL-3.0
---

Elliptic Curve 與 secp256k1 筆記
===
Introduction
---
- 本文把 elliptic curve 簡記為 EC
- secp256k1
- 定義對於 EC 的參數選擇，跟 ECC 演算法要怎麼實作無關
- sec：**S**tandard for **E**fficient **C**ryptography
- p：recommended EC domain **P**arameters
- 256：bit length of the field order $p$
- k：曲線與 Koblitz curve 有關
- 1：一系列的 EC 曲線的 spec 的序號
- Domain parameters 與 Koblitz curve 有關聯
- $E/K$
- An elliptic curve defined over a field $K$
- EC 上面的點的 x、y 座標要使用 field $K$ 運算
- $E(K)$：The **set of** ($K$-rational) **points** on the curve $E$
- A $K$-rational point is a point $(x,\ y)$ on an algebraic curve $f(x,\ y)=0$
- $\#E(K)$：The number of points on $E$
- **這個數值不等於** $p$，而且會大於 $p$
- 不要亂想每個 x 值都有 y！！！
- 選擇 $\#E(\mathbb{F}_p)=p$ 的 EC 會有攻擊[弱點](https://wstein.org/edu/2010/414/projects/novotney.pdf)！
- 選擇 $\#E(\mathbb{F}_p)\mathrm{\ is\ not\ a\ prime}$ 的 EC 會有攻擊[弱點](https://en.wikipedia.org/wiki/Small_subgroup_confinement_attack)！

secp256k1 參數設定
---
- 取 sextuple $T=(p, a, b, G, n, h)$ 定義橢圓曲線 secp256k1
- $p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1\ {\approx}1.15{\times}10^{77}$
- `0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f`
- 有些文件會用 $q$ 表達，通常這時候就是有探討基於 $q=2^m$ 的曲線
- $a=0$ and $b=7$
- EC 即為 $y^2=x^3+7$
- $G$：base point (aka the generator of the group)
- In uncompressed form
<img src="https://i.imgur.com/cvXWs1d.jpg" width="500"/>
- That is `04 <x-coor> <y-coor>` where each `<coordinate>` has 64 hex-digits.
- In compressed form
<img src="https://i.imgur.com/YVt2JUt.jpg" width="500"/>
- 注意：base point 和 EC identity element $\mathcal{O}$ 完全不同，不可搞混
- $n$：(additive) order of the base point $G$
- `0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141`
- $n$ is a prime.
- Length of $n$ is 256 bits.
- $h=1$：cofactor
- $h=\#E(\mathbb{F}_p)/n$, so this means the subgroup ${\langle}G{\rangle}=E(\mathbb{F}_p)$
- 一些附註
- Additive **group** of integers modulo $n$
- 記做：「$\mathbb{Z}^{+}_n$」或「$\mathbb{Z}_n$」或「$\mathbb{Z}/n\mathbb{Z}$」
- （這個符號最不易混淆 →）$\mathbb{Z}^{+}_n=\{0,1,2,{\dots},n-1\}$
- Multiplicative **group** of integers modulo $n$
- 記做：「$\mathbb{Z}^{*}_n$」或「$\mathbb{Z}^{\times}_n$」或「$(\mathbb{Z}/n\mathbb{Z})^{\times}$」或「$(\mathbb{Z}/n\mathbb{Z})^{*}$」
- $\mathbb{Z}^{*}_n=\{x\ {\in}\ \mathbb{Z}^{+}_n\ :\ x\mathrm{\ is\ coprime\ with\ }n\}$，所以 $0$ 自然不會包含在乘法群當中
- **Ring** of integers modulo $n$
- 記做：「$\mathbb{Z}_n$」或「$\mathbb{Z}/n\mathbb{Z}$」（←跟前述的符號[打架](https://math.stackexchange.com/a/3625646) QAQ，所以要看前後文判斷）
- 定義兩個二元運算符號 $+$ 和 $\times$
- $\mathbb{Z}^{+}_n=\{[0],[1],[2],{\dots},[n-1]\}$
- $\mathbb{Z}^{*}_n=\{x\ {\in}\ \mathbb{Z}^{+}_n\ :\ x\mathrm{\ is\ coprime\ with\ }n\}$
- $[\ \ ]$ 是 equivalence class 的意思
- Galois field $\mathbb{F}_p$
- order：$ord(\mathbb{F}_p)=p$
- characteristic：$char(\mathbb{F}_p)=p$
- Order (of a field)
- \# of elements in the field
- $ord(a)=$ the smallest number $n$ such that $a^{n} = e$
- The order of any field is a prime power $p^k$ where $k\in \mathbb{Z}^+$.
- In a field of order $p^k$, the characteristic of the field is $p$.
- Order (of an element in the group)
- The smallest positive integer $n$ such that $ng=\mathbf{0}$ (in $+$) or $g^n=\mathbf{1}$ (in $\times$)
- 也可以看成：以 $g$ 為生成子的 subgroup ${\langle}g{\rangle}$ 的元素個數（此定義只適用 cyclic group）
- 如果在講 field，可能會有兩種 order：additive order、multiplicative order
- Characteristic (of a field)
- \# of additions applied to $\mathbf{1}$ to get the $\mathbf{0}$
- $\mathbf{1}$：multiplicative identity
- $\mathbf{0}$：additive identity
- The char. of any field is either 0 or a prime number.
- Hasse's theorem：給出 EC 總點數的上界
- $|\#E(\mathbb{F}_q)-q-1| \leq 2{\sqrt{q}}$

Point Operation
---
### Point at Infinity
- 抓一個無限遠點當作 identity element $\mathcal{O}$ 包含在 $E(K)$ 當中
- 運算規則
- $\mathcal{O}+\mathcal{O}=\mathcal{O}$
- $P+\mathcal{O}=P$
- $P+(-P)=\mathcal{O}$：point negation

### Point Addition
- 給定 EC 上的三點 $P$、$Q$、$R$
- $R$ 可被稱為 $P$ 加 $Q$ 的結果 ${\iff}\ P+Q+R=\mathcal{O}$
- 也可以看做 $P+Q=-R$
- 如果 EC 是以 $y^2=x^3+ax+b$ 定義的，則具有幾何意義：兩點之和等於兩點連線和 EC 交點的 x 軸對稱點
<img src="https://upload.wikimedia.org/wikipedia/commons/c/c1/ECClines.svg" width="700"/>

### Point Multiplication (by an Integer $s$)
- 又稱作 scalar multiplication
- 反正一定是一個常數乘以一個 EC 點，沒有兩個 EC 點互乘這件事 (operation not defined)
- $[s]Q=Q+Q+\dots+Q\ \mathrm{(add\ }s\mathrm{\ times)}$ over $E(\mathbb{F}_p)$
- 可以用 double-and-add 技巧加速計算
- 若 $[a]P=Q$，則 $P=[a^{-1}]Q$ where $a^{-1}$ is the inverse of $a$ over the field $K$
- 已知 $aa^{-1}=1$ 且 $P=[1]P$

Private Key and Public Key
---
- $k$
- private key
- a scalar ${\in}[1,\ 2^{256}]$ which is **randomly** chosen by user
- $K$
- public key
- $K=[k]G\ {\in}\ E(\mathbb{F}_p)$
- 表示法除了可以直接列出 x 和 y 座標，也有 compressed 和 uncompressed form，詳見下面說明

EC 點的座標的 Compression Method
---
- 請見第二個 reference 的圖一和圖二
- 想法
- 因為 EC 對稱於 x 軸，所以只需把 x 代入 EC 方程式並事前決定取正或負，即可推得 y 座標
- 總共有三種格式，以 `0x02`、`0x03`、`0x04` 開頭來區分
- `0x02`：y 座標取偶數的那個
- `0x03`：y 座標取奇數的那個
<img src="https://i.imgur.com/dx6uJ0C.png" width="500"/>
- `0x04`：uncompressed form
<img src="https://i.imgur.com/SuOVy23.png" width="500"/>
- 為什麼前面說「y 取正負」，後面又只規定「y 取奇偶」？
- Ans：兩件事情是同一件
- 首先：我們知道 $-y$ 就是 $p-y$ 的簡記 ( $p-y\ {\in}\ [0,\ p-1]$ )
- 接著：我們知道 $p$ 一定是奇數 (沒有人會選 over $\mathbb{F}_2$)
- 最後：如果 $y$ 是奇數，則 $p-y$ 必為偶數，反之亦然
- 注意：根據 Chinese Remainder Theorem，用 $y+(-y)=0\ mod\ p$ 開始思考這個問題，會得到完全錯誤的推導過程與答案
- Quadratic residue
- 如果 ${\exists}\ x\ {\in}\ \mathbb{Z}^{+}\cup\{0\}$ 使得 $x^2\ {\equiv}\ a$ $\mathrm{mod}\ n$，則 $a$ 被稱為 *quadratic residue* modulo $n$
- 白話來說，quadratic residue 就代表 $a$ 是「某人平方之後 mod $n$ 的渣渣」
- 這個「平方」的概念，也可以想成「$\sqrt{a}$」是某人

Reference
---
- https://www.secg.org/sec1-v2.pdf
- SEC 1: Elliptic Curve Cryptography
- https://www.secg.org/sec2-v2.pdf
- SEC 2: Recommended Elliptic Curve *Domain Parameters*
- https://doi.org/10.1109/SYNASC.2010.23
- An x-Coordinate Point Compression Method for Elliptic Curves over Fp
- https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/modk-add.html
- Elliptic Curve Point Addition over $\mathbb{F}_p$ Demo
- https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf
- An Introduction to Bitcoin, Elliptic Curves and theMathematics of ECDSA
- https://learnmeabitcoin.com/technical/public-key
- Learn me a bitcoin - Public Key
- https://andrea.corbellini.name/ecc/interactive/modk-add.html

Miscellanea
---
- $1234567890133$ is a prime.
- $1234567890139 = 15187 \times 81291097$
- One hex digit $=$ 4 bits

Further Reading
---
- ECDSA Signature Generation & Verification
- https://hackmd.io/Q2KytbDZTcifdfkEn_e2_Q
- Schnorr Signature Generation & Verification
- https://hackmd.io/S4VkJObyRB6sdMauNLusYQ