Learning of Elliptic Curve

Preface

椭圆曲线密码相关咕了挺久了ojz，也没系统做过总结，谨以此文作为学习记录，以便日后翻阅

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

Basis

1.1 Elliptic Curve in Finite Field

设p为一素数，n为正整数，$q=p^{n}$，则$F_{q}$上的Weierstrass方程式

$$y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6},\quad a_{i}\in F_{q}$$

决定的曲线再添加上无穷远点后，即得到射影平面$P^{2}(\bar{F_{q}})$上的一条曲线E，若非奇异，则称其为一条椭圆曲线，当且仅当$\Delta\neq 0$.

给定一条$F_{q}$上的椭圆曲线E，及其上任意两点P和Q，连接P和Q的直线与E交于第三个点R，由R和无穷远点O可决定一直线，该直线与E的第三个交点定义为P和Q的和，记作$P\oplus Q$. 且易证得该加法定义下满足阿贝尔群.

给出具体的加法公式如下：

设$P_{1}+P_{2}=P_{3},\quad P_{i}=(x_{i},y_{i})\in E.$

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

(b) 一般性如图所示：

但要注意的是，在$F_{q}$上，该直线PQ不同于实数域，可表示为

$$ax+by+c\equiv 0(mod\ q)$$

另外，可以证明，$p\neq 2,3$时，每一条$F_{q}$上的椭圆曲线都同构于

$$E:y^{2}=x^{3}+ax+b,\quad a,b\in F_{q}$$

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

$$|\#E-(p+1)|\leq 2\sqrt{p}$$

注：特别的，在$p\equiv 3(mod\ 4)$时，

$$\#E_{p}(a,0)=p+1.$$

在ECC等体制中寻找基点的算法：

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

Attacking the Discrete Logarithm Problem

在进入ECDLP前，我们首先介绍DLP及各种可用的攻击方法（没跑题- -拍打.jpg）：

2.1 Baby-Step, Giant-Step Algorithm

[Theorem]

北上广深算法- -算法优化思路可看作中间相遇，复杂度$O(\sqrt{n})$.

假设$\alpha^{x}=\beta$，G是n阶循环群，令$m=\lceil \sqrt{n}\rceil$. 则可以将x表示为$im+j(0\leq i,j\leq m)$. 有

$$\beta=\alpha^{x}=\alpha^{im+j}=\alpha^{im}\alpha^{j}\\ \beta(\alpha^{-m})^{i}=\alpha^{j}$$

先遍历$j\in [0,m]$，存储对应的所有$\alpha^{j}$. 再去遍历$i\in [0,m]$，找到碰撞即可.

[Code]

#!/usr/bin/env sage
def bsgs(alpha, beta, p):
    res = []
    m = ceil(sqrt(p - 1))
    S = {pow(alpha, j, p):j for j in range(m + 1)}
    gs = pow(alpha, p - 1 - m, p)
    for i in range(m + 1):
        if beta in S:
            res.append(i * m + S[beta])
        beta = (beta * gs) % p
    return res

2.2 Pollard’s ρ-Method

[Theorem]

和大数分解的Pollard’s ρ有类似之处（生日悖论）

假设$\alpha^{x}=\beta$，G是n阶循环群，将其划分为psize个等价类，$S_{1},S_{2},…,S_{psize}$. 接着再定义G上的序列$\{x_i\}$，每个$x_{i}$均能表示作$\alpha^{a_{i}}\beta^{b_{i}}$.

并生成mod n上的随机序列$a,b$，有递推式如下：

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

则令初始值$x_{0}$为$\alpha^{ax}$（ax随机），也可表示为$a_{0}=ax,b_{0}=0$，同时令$y_{0}=x_{0}$，按照上述进行递推，令$y_{i}=x_{2i}$，则发生碰撞时，我们有

$$\alpha^{ax}\beta^{bx}=\alpha^{ay}\beta^{by}\\ \alpha^{ay-ax}=(\alpha^{res})^{bx-by}$$

在$GCD(bx-by,n)=1$时，存在逆元，易求得$res=(bx-by)^{-1}(ay-ax)$.

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

ord = base.multiplicative_order()
...
if not ord.is_prime():
    raise ValueError("for Pollard rho algorithm the order of the group must be prime")

啊这- -如果$G=F_{p}$，且阶恰好为$p-1$时，显然会直接抛出错误，因此我做了魔改，在最后求解res的时候再进行判断，代码如下：

[Code]

#!/usr/bin/env sage
from tqdm import tqdm


def pollard_rho(beta, alpha, N):
    ord = Mod(alpha, N).multiplicative_order()
    partition_size = 10
    upper_bound = 8 * isqrt(ord)
    I = IntegerModRing(ord)
    for s in tqdm(range(10)):
        a = [I.random_element() for i in range(partition_size)]
        b = [I.random_element() for i in range(partition_size)]
        c = [power(Mod(alpha, N), a[i]) * power(Mod(beta, N), b[i]) for i in range(partition_size)]
        ax = I.random_element()
        bx = I(0)
        x = power(Mod(alpha, N), ax) # ini
        ay, by, y = ax, bx, x
        for i in range(upper_bound):
            j = Integer(x) % partition_size
            (x, ax, bx) = (x * c[j], ax + a[j], bx + b[j])
            k = Integer(y) % partition_size
            (y, ay, by) = (y * c[k], ay + a[k], by + b[k])
            k = Integer(y) % partition_size
            (y, ay, by) = (y * c[k], ay + a[k], by + b[k])
            if x == y:
                if ax == ay:
                    continue
                try:
                    res = Integer((ay - ax) / (bx - by))
                    return res
                except:
                    pass
    print("[-] Failed.")
    return None

2.3 Pollard’s λ-Method

[Theorem]

即Pollard’s Kangaroo Method，算法具体流程如下：

假设$G(=Z_{p})$是n阶循环群，$\alpha,\beta\in G$，满足$\alpha^{x}=\beta.$ 且我们知道$x\in [a,b]\subset [0,p-1]$.

• $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(i+1)\equiv t(i)\alpha^{s(t(i)\ mod\ J)}$$

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

  $$d(n)=\sum_{i=0}^{n-1}s(t(i)\ mod\ J)$$

  因此$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有：

  $$D(j)=\sum_{k=0}^{j-1}s(w(k)\ mod\ J),D(0)=0$$

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

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

  $$\alpha^{x+D(m)}\equiv \alpha^{b+d(n)}\ mod\ p$$

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

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

[Code]

from math import sqrt, log2, floor, ceil
from Crypto.Util.number import *


def pollard_lambda(beta, alpha, N):
    a, b = 0, N - 1
    l = N - 1
    J = floor(log2(l))
    n = ceil(sqrt(N))
    for i in tqdm(range(10)): #求解次数上限
        S = []
        for j in range(J):
            r = getRandomRange(1, l)
            S.append((r, pow(alpha, r, N)))
        # tame kangaroo T
        dt, t = b, pow(alpha, b, N)
        for j in range(n):
            r, e = S[t % J]
            dt += r
            t = (t * e) % N
        # wild kangaroo W
        dw, w = 0, beta
        while dt - dw >= 0:
            if w == t:
                return dt - dw
            r, e = S[w % J]
            dw += r
            w = (w * e) % N
    print("[-] Failed.")
    return None

2.4 The Pohlig-Hellman Method

[Theorem]

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

$$ord=\prod_{i=1}^{k}p_{i}^{r_{i}}$$

则对于$p^{r}$，有$x\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.$

变换得$x(\frac{ord}{p})\equiv x_{0}(\frac{ord}{p})+ord\cdot m$，$m\in Z.$

即$\beta^{\frac{ord}{p}}\equiv \alpha^{x_{0}(\frac{ord}{p})+ord\cdot m}\equiv \alpha^{x_{0}(\frac{ord}{p})}\quad mod\ n.$

而这里的$x_{0}$则只要在$[0,p-1]$上枚举即可.

得到$x_{0}$以后，我们用类似的trick进行$x_{1}$的求解，有

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

令$\beta_1=\beta\alpha^{-x_{0}}$，则有$\beta_1^{\frac{ord}{p^{2}}}\equiv (\alpha^{x}\alpha^{-x_{0}})^{\frac{ord}{p^{2}}}\equiv \alpha^{x_{1}(\frac{ord}{p})+ord*m’}\equiv \alpha^{x_{1}(\frac{ord}{p})}\quad mod\ n$.

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

最后对所有结果CRT即可.（对于$p^{r}$上的求解可采用BSGS进一步减小时间复杂度）

[Code]

#!/usr/bin/env sage
def bsgs(alpha, beta, modulus, upper_bound=None):
    if not upper_bound:
        upper_bound = Mod(alpha, modulus).multiplicative_order()
    m = ceil(sqrt(upper_bound))
    S = {pow(alpha, j, modulus):j for j in range(m + 1)}
    gs = Mod(alpha, modulus)^(-m)
    for i in range(m + 1):
        if beta in S:
            return (i * m + S[beta])
        beta = (beta * gs) % modulus
    return None

def pohlig_hellman(beta, alpha, N):
    beta, alpha = Mod(beta, N), Mod(alpha, N)
    ord = alpha.multiplicative_order()
    f = ord.factor()
    prime_order_mod = [0] * len(f)
    for i, (p, r) in enumerate(f):
        for j in range(r):
            pmod = bsgs(alpha**(ord // p), (beta / alpha**prime_order_mod[i])**(ord // p**(j+1)), N, p - 1)
            prime_order_mod[i] += pmod * (p**j)
    return crt(prime_order_mod, [p**r for (p, r) in f])

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

对于求解DLP/ECDLP的一般性方法，本文里的代码大多有对sage源码进行参考（且sage有轮子），但作为原理性文章，仍自己编写以加深理解or灵活修改（总不会特殊情况下有人莽到直接改sage源码吧不会吧不会吧

3.1.1 Baby-Step, Giant-Step Algorithm

[Theorem]

阶为n的基点P生成$E(F_{p})$，且$Q\in E(F_{p})$，Q=kP.

令$m=\lceil n\rceil$，即可将k表示为$im+j(0\leq i,j\leq m)$. 有

$$Q=kP=(im+j)P=imP+jP\\ Q-i(mP)=jP$$

与BSGS的DLP问题一样，建立$j\in [0,m]$的jP字典，再遍历i寻找碰撞即可.

[Code]

3.1.2 Pollard’s ρ-Method

3.1.3 Pollard’s λ-Method

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}}$.

类比DLP上的Pohlig-Hellman，我们同样要去寻找$k_{i}\equiv k(mod\ 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.$

令集合$T_{i}=\{j\frac{n}{p_{i}}P:0\leq j\leq p_{i}-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.$

即可在$T_{i}$中寻找碰撞，从而得到$x_{0}$.

再令$Q_{1}=Q-x_{0}P$. 计算$\frac{n}{p_{i}^2}Q_{1}$与$T_{i}$的碰撞，得到$x_{1}$，继续升幂即可. 最后CRT.

[Code]

3.2 Specialized Attacks

3.2.1 Anomalous Curves

3.2.2 The MOV Attack

3.2.3 Weil Descent and the GHS Attack