Preface

ps: 各种实验ddl期间- -不定期更新(🕊)

Basis

1.1 Elliptic Curve in Finite Field

(a) 若$x_{1}=x_{2},y_{1}+y_{2}+a_{1}x_{1}+a_{3}$，则$P_{1}+P_{2}=O$，否则

(b) 一般性如图所示：

[Hasse定理] - 如果$E_{p}(a,b):y^{2}=x^{3}+ax+b\ (4a^{3}+27b^{2}\neq 0)$是定义在$F_{p}$上的椭圆曲线，则有

• 计算椭圆曲线E的阶 N(#E).
• 选择一子群的阶n（n为素数），辅因子$h=\frac{N}{n}$.
• 在E上选择一随机点P，如果G=hp为0，则重新选取P，此时G即为基点（阶为n）.

Attacking the Discrete Logarithm Problem

2.2 Pollard’s ρ-Method

[Theorem]

$a_{i+1}=a_{i}+a[x_{i}\%psize],b_{i+1}=b_{i}+b[x_{i}\%psize]$

ps: sage上的discrete_log_rho直接做了如下判断：

2.3 Pollard’s λ-Method

[Theorem]

• $l=b-a,J=\lfloor log_{2}(l)\rfloor$，令$S=\{randrange(1,p),…,randrange(1,p)\}=\{s(0),s(1),…,s(J-1)\}$.

• Let’s begin with our tame kangaroo T. 令T从已知起始点开始跳跃，即令$t_{0}=\alpha^{b}(mod\ p)$, 跳跃路径如下：

T在跳跃n次后停止，且有n次后的跳跃距离(指数)如下：

因此$t(n)\equiv \alpha^{b+d(n)}\ mod\ p$.

• Now we have to deal with the wild kangaroo W. W起始点$w_{0}=\alpha^{x}$，则类似T有：

$w(j)\equiv \alpha^{x+D(j)}\ mod\ p.$

• 当碰撞发生在$t(i)=w(j)$时，此点向后均$t(s)=w(r)\quad (s-i=r-j\geq 0)$. 即有

即$x=b+d(n)-D(m)$.

ps：将跳跃步数n取作$\lceil\sqrt{b-a}\rceil$将使n次后已碰撞的概率趋于1，求解失败则改变S重新求解.

2.4 The Pohlig-Hellman Method

[Theorem]

$G=Zmod(n)$，$\alpha,\beta\in G$，满足$\alpha^{x}=\beta.$ 则假设$\alpha$的阶为$ord$，且可表示为

$x(\frac{ord}{p^2})\equiv x_{0}(\frac{ord}{p^2})+x_{1}(\frac{ord}{p})+ord\cdot m’$.

$\beta_2=\beta\alpha^{-x_0-x_1p}$，…，即升幂得到$x\ mod\ p^{r}$.

Attacking the Elliptic Curve Discrete Logarithm Problem

Attacks on the ECDLP can be split into two main categories:

1. attacks that work in the general setting regardless of properties of a given elliptic curve.
2. attacks that use specific properties of the elliptic curve to develop a different approach.

3.1 General Attacks

3.1.4 The Pohlig-Hellman Method

[Theorem]

$Q,P\in E(F_{p}),Q=kP$. 令n为P生成子群的阶，$n=\prod_{i=1}^{k}p_{i}^{r_{i}}$.

$k\equiv x_{0}+x_{1}p+x_{2}p^{2}+…+x_{r-1}p^{r-1}\quad mod\ p^{r}$，$0\leq x_{i}\leq p-1.$

$\frac{n}{p_{i}}Q=\frac{n}{p_{i}}([x_{0}+x_{1}p_{i}+x_{2}p_{i}^2+…+x_{r-1}p_{i}^{r-1}]P)=x_{0}\frac{n}{p_{i}}P+nmP=x_{0}\frac{n}{p_{i}}P.$