ECDLP

First Post:

2025-04-14

Last Update:

2025-04-14

ECDLP问题

ECDLP是一个非常经典的难题，我们根据哈斯定理可知，一个椭圆曲线内的点数量(包括无限远点)满足以下式子:
$q+1-2\sqrt q \le N \le q+1+2\sqrt q$
也可以等价为：$|N-(q+1)| \le 2\sqrt q$
其中:

q为有限域大小(q=p^n^)
$2\sqrt q$为哈斯边界
也就是说我们一个素数数量在2^160^范围内的曲线，p的长度就在160位左右
再根据ECDLP定义：给定椭圆曲线E上的点P和Q，找到一个整数使得Q=kP，kP就是标量乘法，也就是P相加k次
如果知道P和Q，且p相对较大时计算k会非常困难，所以ECDLP具有安全性。

目前解决它的办法主要分为通用算法和特殊曲线攻击
一、通用算法（适用于一般曲线）
这些算法对所有椭圆曲线有效，但时间复杂度较高，通常需要群的阶n满足某些条件（如光滑阶）。

Baby-Step Giant-Step（BSGS）

其基本思想就是通过将计算分成两个步骤来减少时间复杂度。
由于我们希望解决 $P=kG$
我们先设置一个参数m=[$\sqrt n$],n为阶
baby step:

计算并储存点G，2G，3G,…,(m-1)G:
将这些值储存在一个哈希表中
Giant step：
计算$H = -mG$
计算$P+iH$,i从0到m-1
检查当前值$P$是否在baby steps里
如果找到匹配的j和i，则可以通过公式求解k：
$k = im + j$，并更新$P=P+G^{-m}$
此算法在sage中使用bsgs函数可以直接调用

Pollard’s Rho 算法
原理：利用随机游走和碰撞检测，避免高空间消耗。
时间复杂度：$O(\sqrt n)$
空间复杂度:$O(1)$
sage中可以使用discrete_log_rho(a,base,ord,operation)函数来进行使用
base为底，a为对数；ord为base的阶,operation可以是+和*
优势：目前最实用的通用算法，常用于实际攻击（如 112 位 ECC 已被破解）
Pohlig-Hellman 算法
原理:将问题分解到子群（若$n$是光滑数，即$n=\prod p_{i}^{e_{i}}$)
时间复杂度:取决于最大素因子$p_{i}$,为$O(\sum e_{i}\sqrt p_{i})$
关键限制：要求群的阶n是光滑数（即所有素因子较小）。
Smart Attack
即我们可以判断一个曲线的阶n是否等于域p，若满足，
则可以使用smart attck

Teichmüller 提升
把曲线和点坐标从$F_p$升到$Z/p^2Z$或$Q_p$，保持同样的多项式方程和数值表示。
构造同态映射
找到从椭圆曲线$E(Q_p)$到p-adic数加法群$(Z_p,+)$的同态映射φ,使得：
$φ(Q)=k·φ(P) \space mod \space p$
$Q=kP$
对于$R∈E(Q_p)$定义映射:
$φ(R)=x(R)/y(R)$
然后在对p-adic分析之后，发现满足该线性关系:
$φ(Q)=k·φ(P) \space mod \space p$
恢复离散对数
将P和Q的坐标提到$Q_p$中来
即可求解离散对数k
$k=(x(Q)/y(Q)·(x(P)/y(P))^{-1}) \space mod \space p$

MOV攻击
MOV攻击的核心思想是将椭圆曲线的离散对数问题转化为有限域中的离散对数问题，从而利用已知的高效算法进行攻击。
攻击思想：
1.选择一个双线性配对e,这里一般选择 Weil 或 Tate 配对，下文实现就是基于 Weil 配对的；
2.P的阶为m，选择一个阶同样为m的Q，并且令Q与P互不相关，也就是不存在$Q=nP$
3.这样e(G,Q)和e(P,Q)就都可以计算了，并且有$e(G,Q)=e(dG,Q)=e(G,Q)^d$所以我
们就将在椭圆曲线群上难以计算的 DLP 问题转化成了在$GF(p^k)$上的DLP问题就好算了

例题：

from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os

# Create a simple Point class to represent the affine points.
Point = namedtuple("Point", "x y")

# The point at infinity (origin for the group law).
O = 'Origin'

FLAG = b'crypto{??????????????????????????????}'


def check_point(P: tuple):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P: tuple):
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P: tuple, Q: tuple):
    # based of algo. in ICM
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R


def double_and_add(P: tuple, n: int):
    # based of algo. in ICM
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R


def gen_shared_secret(Q: tuple, n: int):
    # Bob's Public key, my secret int
    S = double_and_add(Q, n)
    return S.x


def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


# Define the curve
p = 310717010502520989590157367261876774703
a = 2
b = 3

# Generator
g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = Point(g_x, g_y)

# My secret int, different every time!!
n = randint(1, p)

# Send this to Bob!
public = double_and_add(G, n)
print(public)

# Bob's public key
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)

# Calculate Shared Secret
shared_secret = gen_shared_secret(B, n)

# Send this to Bob!
ciphertext = encrypt_flag(shared_secret)
print(ciphertext)

由题可知我们需要得到秘密数字n才能解出这道题，由于B和Q都是由G通过标量乘法得到，也就是
$Gn_1=Q$,$Gn_2=B$,这里用到的是Pohlig-Hellman算法，我们得到阶数n(阶数n就是群G的元素数量)之后，通过因式分解$n=p^{k_1}_1·p^{k_2}_2·p^{k_3}_3···$,,再计算$n_i=n/p^{k_i}_i$,这里还要求$g^{n_i}$和$y^{n_i}$,这里的g和y就是离散对数问题里的$g^x=y$,再去求x，$g^{x_i} \equiv y^{n_i}\space mod \space p^{k_i}_i$求得x，再使用CRT来进行合并，得到唯一解即n，共享密钥就为$n*B$的横坐标

exp:

from sage.all import *
from Crypto.Cipher import AES
import hashlib
def decrypt_flag(shared_secret:int):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]

    iv = bytes.fromhex('07e2628b590095a5e332d397b8a59aa7')
    ciphertext = bytes.fromhex('8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af')
    cipher = AES.new(key,AES.MODE_CBC,iv)

    pt = cipher.decrypt(ciphertext)
    return pt

p = 310717010502520989590157367261876774703
a = 2
b = 3
F = GF(p)
EC = EllipticCurve(F, [a, b])
 
G = EC(179210853392303317793440285562762725654, 105268671499942631758568591033409611165)

# Q = n1 * G
Q = EC(280810182131414898730378982766101210916, 291506490768054478159835604632710368904)

# B = n2 * G
B = EC(272640099140026426377756188075937988094, 51062462309521034358726608268084433317)


# Pohlig Hellman
ordG = G.order()
factors = factor(ordG)
smallres = []
smallmod = []
for f in factors:
    smallmod.append(f[0]^f[1])
    curr = ordG // (f[0]^f[1])
    Q2 = curr * Q
    P2 = curr * G
    if(f[1] != 1):
        smallres.append(discrete_log(Q2, P2, operation='+'))
    else:
        smallres.append(discrete_log_rho(Q2, P2, operation='+'))

n1 = crt(smallres, smallmod)
assert n1*G == Q

print(decrypt_flag((n1*B)[0]))

(2024羊城杯)BabyCurve:

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import os
import hashlib
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import c, b, key, FLAG


def add_curve(P, Q, K):
    a, d, p = K
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 * y2 + y1 * x2) * pow(1 - d * x1 ** 2 * x2 ** 2, -1, p) % p
    y3 = ((y1 * y2 + 2 * a * x1 * x2) * (1 + d * x1 ** 2 * x2 ** 2) + 2 * d * x1 * x2 * (x1 ** 2 + x2 ** 2)) * pow(
        (1 - d * x1 ** 2 * x2 ** 2) ** 2, -1, p) % p
    return x3, y3


def mul_curve(n, P, K):
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_curve(R, P, K)
        P = add_curve(P, P, K)
        n = n // 2
    return R


def AES_encrypt(k):
    key = hashlib.sha256(str(k).encode()).digest()[:16]
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    cipher = cipher.encrypt(pad(FLAG, 16))
    data = {}
    data["iv"] = iv.hex()
    data["cipher"] = cipher.hex()
    return data


a = 46
d = 20
p1 = 826100030683243954408990060837
K1 = (a, d, p1)
G1 = (560766116033078013304693968735, 756416322956623525864568772142)
P1 = mul_curve(c, G1, K1)
Q1 = mul_curve(b, G1, K1)
print("P1 =", P1)
print("Q1 =", Q1)
# P1 = (528578510004630596855654721810, 639541632629313772609548040620)
# Q1 = (819520958411405887240280598475, 76906957256966244725924513645)

p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-c, b])
G = E.gens()[0]
P = G * key
data = AES_encrypt(key)
print("G =", G)
print("P =", P)
print("data =",data)
# G = (584273268656071313022845392380 : 105970580903682721429154563816 : 1)
# P = (401055814681171318348566474726 : 293186309252428491012795616690 : 1)
# data = {'iv': 'bae1b42f174443d009c8d3a1576f07d6', 'cipher': 'ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4'}

这题的曲线似乎是一个Twisted Edwards Curve($a(y^2)+x^2=1+d(x^2y^2)$)，这条Curve可以帮助我们求出最后的ECC的参数c、b，由于我们有G、P两点，所以直接groebner就可以有参数c、b了。

有了曲线参数后还是要解决一个DLP问题，检查一下曲线order的分解发现并不是特别的光滑，最后一个因子有五十多bit，虽然求是可以求的，但肯定很慢。

然而再仔细检查下，会发现说这其实是一条超奇异椭圆曲线，阶是p+1，所以嵌入度是2，所以用MOV attack映射到Fp2上去dlog比较高效。
exp:

import hashlib
from Crypto.Cipher import AES

p = 770311352827455849356512448287
G = (584273268656071313022845392380 , 105970580903682721429154563816)
P = (401055814681171318348566474726 , 293186309252428491012795616690)


########################################################### part1 get c,b
PR.<c,b> = PolynomialRing(Zmod(p))
f1 = G[1]^2 - (G[0]^3 - c*G[0] + b)
f2 = P[1]^2 - (P[0]^3 - c*P[0] + b)
res = Ideal([f1,f2]).groebner_basis()
print(res)
c = -770311352827455849356512448252
b = -770311352827455849356512448189


########################################################### part2 mov attack
if(1):
    E = EllipticCurve(GF(p), [a, b])
    E2 = EllipticCurve(GF(p**2, 'y'), [a, b])

    P2 = E2(G)
    Q2 = E2(P)

    n = E.order()
    R = E2.random_element()
    tP = P2.weil_pairing(R, n)
    tQ = Q2.weil_pairing(R, n)

    key = tQ.log(tP)
    print(key)
key = 2951856998192356


########################################################### part3 get flag
iv = bytes.fromhex('bae1b42f174443d009c8d3a1576f07d6')
c = bytes.fromhex('ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4')
key = hashlib.sha256(str(key).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.decrypt(c))


#DASCTF{THe_C0rv!_1s_Aw3s0me@!!}

以下是一些基础概念的补充:
MOV 映射
为什么要映射？

椭圆曲线离散对数（ECDLP）在曲线群里很难直接解。
但如果能把问题转到有限域乘法群$F_{p^k}^*$上，就可以利用更成熟的算法。
映射怎么做？
一个曲线群里的“辅助点”R，它的阶是$n=#\ E(F_p)$。
计算Weli Pairing
$e_n(R,G)$ 和 $e_n(R,P)$
它们都是里的$F_{p^k}^*$元素。
由于 pairing 有双线性性质：
$e_n(R,xG)$ = $e_n(R,G)^x$
所以如果已知
$a=e_n(R,xG)$ ，$b=e_n(R,G)^x$
就有
$b=a^x \space in \space F_{p^k}^*$
然后我们就得到了一个普通的离散对数问题即已知a，b求x

≡