椭圆曲线算法_攻击

ECC算法

ECC算法是最基础，也是最经典的椭圆曲线算法之一

算法基础过程：
1、选一条椭圆曲线 $E_p(a,b)$ （ECC选取的曲线为 $y^2=x^3+ax+b$），取曲线上一点P，作为基点
2、随机选定一个数k作为私钥，并生成公钥Q = k * P（这里的乘法是曲线上的乘法，不是正常的代数乘法）
3、加密：选取一个随机数r，明文为m，用下面的公式生成密文 c，
加密公式：$c=(rP,m+rQ)$
4、解密：$m+rQ-k(rP)$ = $m+r(kP)-k(rP)$ = $m$

基础（相关公式）：
有限域GF(p)上的椭圆曲线 $y^2=x^3+ax+b$ ,$R = P + Q$ :
$X_r​=(λ^2−X_p​−X_q​)\mod p$
$Y_r​=(λ(X_p​−X_r​)−Y_p​) \mod p$
$λ=(Y_q​−Y_p​)/(X_q​−X_p​) \mod p$ (若p!=Q)
$λ=(3X_p^2​+a)/2Y_p​\mod p$ (若P=Q)

椭圆曲线常用攻击方法

smart’s Attack

原理：攻击异常曲线（阶就等于p的曲线，本身就是个异常子群），smart‘s 攻击利用了椭圆曲线上的点可以通过一个同态映射（有限域同态映射）映射到有限域的模数p的加法群上
在加法群上解ECDLP会简单一点

椭圆曲线的 p-adic 提升与形式群映射:

椭圆曲线点 $P \in E(\mathbb{F}_p)$

↓（提升到 p-adic）

p-adic 点 $P_{\mathbb{Q}_p} \in E(\mathbb{Q}_p)$

↓（乘以 p）

$p \cdot P_{\mathbb{Q}_p} \in E_1(\mathbb{Q}_p)$ [形式群]

↓（取形式参数 $t = -x/y$）

$\phi_P \in p\mathbb{Z}_p \subset \mathbb{Q}_p$

↓（除以 p 并模 p）

最终元素 $\in \mathbb{F}_p^+$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
求私钥的脚本
p =  
A =  
B =  
E = EllipticCurve(GF(p),[A,B])  
P = E(,)  
Q = E(,)  
def SmartAttack(P,Q,p):  
    E = P.curve()  
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])  
    # 有限域提升（提升到p-adic域）  
  
    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)  
    for P_Qp in P_Qps:  
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:  
            break  
  
    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)  
    for Q_Qp in Q_Qps:  
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:  
            break  
    # 上面俩段代码在做点P和点Q的提升（提升到p-adic曲线上）  
  
    p_times_P = p*P_Qp  
    p_times_Q = p*Q_Qp  
  
    x_P,y_P = p_times_P.xy()  
    x_Q,y_Q = p_times_Q.xy()  
  
    phi_P = -(x_P/y_P)  
    phi_Q = -(x_Q/y_Q)  
    # 点的映射  
  
    k = phi_Q/phi_P  
  
    return ZZ(k)  
  
r = SmartAttack(P, Q, p)  
print(r)

# 其他脚本放在pyc中（smart_Attack.py）

Pohlig-Hellman 算法(针对光滑数)

注：生成 p-1 是光滑数和简单光滑数的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def myPrime(bits):  
    while True:  
        n = 2  
        while n.bit_length() < bits:  
            n *= choice(sieve_base)  
        if isPrime(n + 1):  
            return n + 1  
p = print(myPrime(1024))
A = pow(2,a,p)

# sagemath
p = ……
A = ……

G = Zmod(p)
a = discrete_log(G(A),G(2))

Pohlig-Hellman算法思想：

设乘法群 $Z_p^*$，其阶为 $n$。

假设 $p$ 为大质数，所以 $n = \phi(p) = p - 1$

设其质因数分解为：$n = q_1^{e_1} q_2^{e_2} q_3^{e_3} \cdots q_k^{e_k}$

现在有如下等式：

$$
h = g^x \pmod{p}
$$

两边同时求 $\frac{n}{q_i^{e_i}}$ 次幂可以得到：

$$
h^{\frac{n}{q_i^{e_i}}} = (g^x)^{\frac{n}{q_i^{e_i}}} \pmod{p}
$$

右边式子的 $x$ 可以提出来得到：

$$
h^{\frac{n}{q_i^{e_i}}} = \left(g^{\frac{n}{q_i^{e_i}}}\right)^x \pmod{p}
$$

假设 $h_i = h^{\frac{n}{q_i^{e_i}}}$，$g_i = g^{\frac{n}{q_i^{e_i}}}$，可以得到：

$$
h_i = g_i^x \pmod{p}
$$

因为 $g_i$ 的阶为 $q_i^{e_i}$，所以上面的等式就是在一个 $q_i^{e_i}$ 阶的子群上求离散对数，这样这个离散对数的范围就变小了，可以尝试求解这个离散对数，满足等式的解都模 $q_i^{e_i}$ 同余
设其中一个解 $a_i$，那么解可以表示为：

$$
x \equiv a_i \pmod{q_i^{e_i}}
$$

所以对于每一个 $i(1 \leq i \leq k)$，都做上述操作的话，那么就会得到如下的方程组：

$$
\begin{cases}
x \equiv a_1 \pmod{q_1^{e_1}} \
x \equiv a_2 \pmod{q_2^{e_2}} \
\vdots \
x \equiv a_k \pmod{q_k^{e_k}}
\end{cases}
$$

通过剩余定理可以求出方程组的解。

例题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#Alice do this
p=14050339
a=1
b=3243167
E = EllipticCurve(GF(p),[a,b])
G=E(7112688,7410262)
k=random.randrange(1,G.order())
K=k*G
print(K)
#(6562993 : 2753874 : 1)
######################################
######################################
#Bob do this
import random
flag="0xGame{xxxxxxxx}"
table='abcdefghijklmnopqrstuvwxyz'
m=flag[7:-1]
m1=m[:4]
m2=m[4:]
m_1=''
m_2=''
for i in m1:
    s=str(table.index(i)+1)
    if len(s)<2:
        s='0'+s
    m_1+=s
for i in m2:
    s=str(table.index(i)+1)
    if len(s)<2:
        s='0'+s
    m_2+=s
x=int(m_1)
y=int(m_2)
P=E(x,y)
r=random.randrange(1,G.order())
C1=P+r*K
C2=r*G
print(C1)
#(3095063 : 1465594 : 1)
print(C2)
#(6437074 : 4385056 : 1)
######################################
######################################
#Eva wants to know the flag.
#Can you help Eva?

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
p=14050339
a=1
b=3243167
E = EllipticCurve(GF(p),[a,b])
n = E.order()
G=E(7112688,7410262)
K = E(6562993 , 2753874)  # K = k*G
C1 = E(3095063 , 1465594 ) # C1 = M + k*K
C2 =  E(6437074 ,4385056 ) # C2 = k*G      
factors = factor(n)
print(factors)
result = []
factors = [4 ,3 , 1170811]

!!!重点理解
for f1  in factors:
    t = n // f1
    res = discrete_log(t*K,t*G,operation='+') # operation='+' 默认是乘
    result  += [res]

print(result)
k = crt(result,factors)

M  = C1-k*C2
print(M)
table='abcdefghijklmnopqrstuvwxyz'
a=(12050118 ,14050303)
 
def flag(a):
    flag=""
    x=a[0]
    y=a[1]
    m=str(x)+str(y)
    for i in range(0,16,2):
        flag+=str(table[int(m[i:i+2])-1])
    return flag
print("0xGame{"+flag(a)+"}")

# 注意看下下面的sage代码

# 直接求解离散对数
k = G.discrete_log(K)
如果n是光滑的话，这个G.discrete_log(K)函数会智能用crt解，G是基点、K是公钥

# 解密
M = C1 - k * C2
print("解密得到的点:", M)

矩阵的模板（没用过）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# sage
# 离散对数求解脚本

import tqdm
import hashlib

def babystep_giantstep(g, y, p):
    """Baby-step Giant-step算法求解DLP"""
    m = int((______)**0.5 + 0.5)  # 步长
    table = {}
    gr = ______  # 初始单位元
    
    # Baby-step: 预计算g^0到g^(m-1)
    for r in tqdm.tqdm(range(m)):
        table[str(gr)] = r
        gr = ______  # 计算下一个幂
    
    # Giant-step: 搜索解
    gm = ______  # g^(-m)
    ygqm = ______
    for q in tqdm.tqdm(range(m)):
        if str(ygqm) in table:
            return q * m + table[str(ygqm)]
        ygqm = ______  # 步进
    return None

def pohlig_hellman_DLP(g, y, p):
    """Pohlig-Hellman算法: 集成因子分解+BSGS+CRT"""
    crt_moduli = []
    crt_remain = []
    
    # 对每个素因子求解子群DLP
    for q, _ in factor(______):
        sub_g = ______  # 子群生成元
        sub_y = ______  # 子群目标
        x = babystep_giantstep(sub_g, sub_y, q)
        if x:
            crt_moduli.append(q)
            crt_remain.append(x)
    
    return crt(crt_remain, crt_moduli)  # CRT组合解

# 主程序
p = ______  # 素数
A = ______  # 基础矩阵
enc = ______ # 目标矩阵 A^q

A = matrix(Zmod(p), A)
enc = matrix(Zmod(p), enc)

# 求解离散对数q
partial_q = pohlig_hellman_DLP(A, enc, p)

# 由于解是模数下的，需要找到完整解
lcm_val = ______  # 子群阶LCM
base_val = ______  # 基础解

# 遍历验证完整解
for k in range(10000):
    q_candidate = base_val + k * lcm_val
    if q_candidate < p and A ^ q_candidate == enc:
        flag = 'DASCTF{' + hashlib.md5(str(q_candidate).encode()).hexdigest() + '}'
        print(flag)
        break

# 变量说明:
# p: 素数模数
# A: 生成元矩阵  
# enc: 目标矩阵 A^q
# q: 离散对数(加密指数)
# lcm_val: 子群阶最小公倍数
# base_val: 基础解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# RSA 中p和q都是光滑数

a = 2  # 初始基数值，通常选择小素数
n = 2  # 指数计数器
while True:    
    a = pow(a, n, N)  # 计算 a^n mod N，使用模幂运算提高效率
    res = gmpy2.gcd(a-1, N)  # 计算 gcd(a-1, N)
    
    # 如果找到非平凡因子
    if res != 1 and res != N:        
        q = N // res  # 另一个因子
        p = res       # 找到的因子
        break    
    n += 1  # 增加指数，继续尝试

超奇异椭圆曲线

MOV攻击

攻击的是ECDLP

**Link:**https://zhuanlan.zhihu.com/p/421541257

超奇异椭圆曲线同源密钥交换(SIDH)

Link:Isogeny | 糖醋小鸡块的blog

题目

EC Fun

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Cipher import AES
import random

flag = '******'.encode()
p = 1361137685787644823054950239221481267310111

have = lambda s,t:((1132105824051503958365821105743937899761226*s[0]**3 + 229031861736140864689129133477543367548885*s[0]**2*t[0] + 229031861736140864689129133477543367548885*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3 + 820243406944125048991336110221143271981334*s[0]**2 + 649313030456686003640437242797882952355121*s[0]*s[1] + 527983998322961064385871655992141377230770*s[1]**2 + 1081788557687039548127228258000675990657554*s[0]*t[0] + 711824655330958819414512996423598314954990*s[1]*t[0] + 820243406944125048991336110221143271981334*t[0]**2 + 711824655330958819414512996423598314954990*s[0]*t[1] + 305169689141722694283206927237198512848571*s[1]*t[1] + 649313030456686003640437242797882952355121*t[0]*t[1] + 527983998322961064385871655992141377230770*t[1]**2)*pow(229031861736140864689129133477543367548885*s[0]**2 + 903073962315363093676691972266394532212341*s[0]*t[0] + 229031861736140864689129133477543367548885*t[0]**2,-1,p)%p, (54187766978142688518903451220347809940963*s[0]**4 + 229031861736140864689129133477543367548885*s[0]**3*s[1] + 1252762151831359446017143336780785647428185*s[0]**3*t[0] + 674042100579222228987562838788851164663456*s[0]*s[1]*t[0]**2 + 108375533956285377037806902440695619881926*s[0]*t[0]**3 + 458063723472281729378258266955086735097770*s[1]*t[0]**3 + 1306949918809502134536046788001133457369148*t[0]**4 + 903073962315363093676691972266394532212341*s[0]**3*t[1] + 687095585208422594067387400432630102646655*s[0]**2*t[0]*t[1] + 1132105824051503958365821105743937899761226*t[0]**3*t[1] + 409448300551393558178072250995397507413084*s[0]**3 + 1207230666903911661795540475036106991723031*s[0]**2*s[1] + 62511624874272815774075753625715362599869*s[0]*s[1]**2 + 833153687464683758669078583229339890079341*s[1]**3 + 132792784133464148520733486235288745070859*s[0]**2*t[0] + 307814037767466322518819528370748551174160*s[0]*s[1]*t[0] + 1298626060913372007280874485595765904710242*s[1]**2*t[0] + 1228344901654180674534216752986192522239252*s[0]*t[0]**2 + 1207230666903911661795540475036106991723031*s[1]*t[0]**2 + 951689385236251264876877988226083759897027*t[0]**3 + 153907018883733161259409764185374275587080*s[0]**2*t[1] + 1236114436039099191506798731970050542110373*s[0]*s[1]*t[1] + 222814309181238370102664728754942864382199*s[1]**2*t[1] + 1053323648020178500536130710850732716135951*s[0]*t[0]*t[1] + 125023249748545631548151507251430725199738*s[1]*t[0]*t[1] + 153907018883733161259409764185374275587080*t[0]**2*t[1] + 62511624874272815774075753625715362599869*s[0]*t[1]**2 + 1138323376606406452952285510466538402927912*s[1]*t[1]**2 + 1298626060913372007280874485595765904710242*t[0]*t[1]**2 + 527983998322961064385871655992141377230770*t[1]**3)*pow(229031861736140864689129133477543367548885*s[0]**3 + 674042100579222228987562838788851164663456*s[0]**2*t[0] + 687095585208422594067387400432630102646655*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3,-1,p)%p)
fun = lambda t:((1355411426698193074927107560516481409632646*t[0]**4 + 1178449528330025005130887555984327255695700*t[0]**3 + 431210186226622274082401960566604243166160*t[0]**2*t[1] + 59195913557099283872495176385768072148921*t[0]*t[1]**2 + 251369299603578168918462619253512221092756*t[0]**2 + 879678478093874414429176172962662062922270*t[0]*t[1] + 281103361207015191365820977148971655332738*t[1]**2 + 362519131628697943100337725424101898137457*t[0] + 443705393890279523315779887935020111939334*t[1] + 578364425578037679604436300506704082028031)*pow(956880610267536390357724782030411500415237*t[0]**2 + 1145532592674333686013749258938179145727031*t[0]*t[1] + 650970886115272769591227531417856597580595*t[1]**2 + 233572674711604604519014902334948133513444*t[0] + 535453460641822632058096218419954325337796*t[1] + 725112018286073523450664990921518386913035,-1,p)%p, (1229680448238589741915782165367654357920185*t[0]**6 + 508331960611786860744946345382725399597519*t[0]**5 + 1343958908519289578671422203106481694277716*t[0]**4*t[1] + 177167026616744824850256300247635539724057*t[0]**3*t[1]**2 + 647526478257364195975697407176118287861906*t[0]**4 + 874634578828271234182240863130269063092359*t[0]**3*t[1] + 753721599708341578448324615735431250261044*t[0]**2*t[1]**2 + 59195913557099283872495176385768072148921*t[0]*t[1]**3 + 135184449413711070637582564227488684273926*t[1]**4 + 1184268232038119513987721523209048245879902*t[0]**3 + 588376066139055328517853740807864391561055*t[0]**2*t[1] + 975956920560485006036771022835309336072696*t[0]*t[1]**2 + 1352108846430422970045668681682022723360513*t[1]**3 + 1280832417616997174969599325837067484280181*t[0]**2 + 954546681684014316952546155309712995684234*t[0]*t[1] + 865928094420333438629116336228132264435796*t[1]**2 + 1082085886860697193173121066542089802274658*t[0] + 755869998556204076975668261501936206771336*t[1] + 657902451019006293214253561308197638483112)*pow(956880610267536390357724782030411500415237*t[0]**3 + 1037730046117678117493148768796528084935491*t[0]**2*t[1] + 591774972558173485718732355032088525431674*t[0]*t[1]**2 + 1225953236373933752417367674993992583036185*t[1]**3 + 350359012067406906778522353502422200270166*t[0]**2 + 245222696137823073119338416038381708703277*t[0]*t[1] + 1197892972677768820041026587455773400480227*t[1]**2 + 814198369070575747297044733543073893428994*t[0] + 447093761510564524382892260162823859185717*t[1] + 558976911634572335364921619094958402137856,-1,p)%p)

def have_fun(g2, key):
    res = g1
    while key:
        if key&1:
            res = have(res,g2)
        g2 = fun(g2)
        key >>= 1
    return res

g1 = (1151954709424958906091046463160132564937644,709388597947225692614956015386635942863012)
g2 = (981333628607549915704008747402562350211701,1251610635487471222383956310361676241534200)

key = random.randrange(2,1<<54)
y = have_fun(g2, key)

print('y =',y)
# y = (1233646914495991358880000369082822614720033, 169216170896679696320800078452784590711491)

cipher = AES.new(str(key).encode()[:16], AES.MODE_ECB)
enc = cipher.encrypt(flag)
print('enc =', enc)
# enc = b"t\xf1x\xc2'}q\xe7i.\x0cmj\x0fkNkVJ-\xd5\xbf\xf9H_\xd1\x04hO\xcd\xe1\x95P\xad\xea\xe1\xec\x1c\xben?RCr\x932\x90t"

看了大佬的wp：EC Fun - CTF Writeups by @jiegec

脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from sage.all import *

p = 1361137685787644823054950239221481267310111
F = GF(p)
g1 = (1151954709424958906091046463160132564937644,709388597947225692614956015386635942863012)
g2 = (981333628607549915704008747402562350211701,1251610635487471222383956310361676241534200)

have = lambda s,t:((1132105824051503958365821105743937899761226*s[0]**3 + 229031861736140864689129133477543367548885*s[0]**2*t[0] + 229031861736140864689129133477543367548885*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3 + 820243406944125048991336110221143271981334*s[0]**2 + 649313030456686003640437242797882952355121*s[0]*s[1] + 527983998322961064385871655992141377230770*s[1]**2 + 1081788557687039548127228258000675990657554*s[0]*t[0] + 711824655330958819414512996423598314954990*s[1]*t[0] + 820243406944125048991336110221143271981334*t[0]**2 + 711824655330958819414512996423598314954990*s[0]*t[1] + 305169689141722694283206927237198512848571*s[1]*t[1] + 649313030456686003640437242797882952355121*t[0]*t[1] + 527983998322961064385871655992141377230770*t[1]**2)*pow(229031861736140864689129133477543367548885*s[0]**2 + 903073962315363093676691972266394532212341*s[0]*t[0] + 229031861736140864689129133477543367548885*t[0]**2,-1,p)%p, (54187766978142688518903451220347809940963*s[0]**4 + 229031861736140864689129133477543367548885*s[0]**3*s[1] + 1252762151831359446017143336780785647428185*s[0]**3*t[0] + 674042100579222228987562838788851164663456*s[0]*s[1]*t[0]**2 + 108375533956285377037806902440695619881926*s[0]*t[0]**3 + 458063723472281729378258266955086735097770*s[1]*t[0]**3 + 1306949918809502134536046788001133457369148*t[0]**4 + 903073962315363093676691972266394532212341*s[0]**3*t[1] + 687095585208422594067387400432630102646655*s[0]**2*t[0]*t[1] + 1132105824051503958365821105743937899761226*t[0]**3*t[1] + 409448300551393558178072250995397507413084*s[0]**3 + 1207230666903911661795540475036106991723031*s[0]**2*s[1] + 62511624874272815774075753625715362599869*s[0]*s[1]**2 + 833153687464683758669078583229339890079341*s[1]**3 + 132792784133464148520733486235288745070859*s[0]**2*t[0] + 307814037767466322518819528370748551174160*s[0]*s[1]*t[0] + 1298626060913372007280874485595765904710242*s[1]**2*t[0] + 1228344901654180674534216752986192522239252*s[0]*t[0]**2 + 1207230666903911661795540475036106991723031*s[1]*t[0]**2 + 951689385236251264876877988226083759897027*t[0]**3 + 153907018883733161259409764185374275587080*s[0]**2*t[1] + 1236114436039099191506798731970050542110373*s[0]*s[1]*t[1] + 222814309181238370102664728754942864382199*s[1]**2*t[1] + 1053323648020178500536130710850732716135951*s[0]*t[0]*t[1] + 125023249748545631548151507251430725199738*s[1]*t[0]*t[1] + 153907018883733161259409764185374275587080*t[0]**2*t[1] + 62511624874272815774075753625715362599869*s[0]*t[1]**2 + 1138323376606406452952285510466538402927912*s[1]*t[1]**2 + 1298626060913372007280874485595765904710242*t[0]*t[1]**2 + 527983998322961064385871655992141377230770*t[1]**3)*pow(229031861736140864689129133477543367548885*s[0]**3 + 674042100579222228987562838788851164663456*s[0]**2*t[0] + 687095585208422594067387400432630102646655*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3,-1,p)%p)
fun = lambda t:((1355411426698193074927107560516481409632646*t[0]**4 + 1178449528330025005130887555984327255695700*t[0]**3 + 431210186226622274082401960566604243166160*t[0]**2*t[1] + 59195913557099283872495176385768072148921*t[0]*t[1]**2 + 251369299603578168918462619253512221092756*t[0]**2 + 879678478093874414429176172962662062922270*t[0]*t[1] + 281103361207015191365820977148971655332738*t[1]**2 + 362519131628697943100337725424101898137457*t[0] + 443705393890279523315779887935020111939334*t[1] + 578364425578037679604436300506704082028031)*pow(956880610267536390357724782030411500415237*t[0]**2 + 1145532592674333686013749258938179145727031*t[0]*t[1] + 650970886115272769591227531417856597580595*t[1]**2 + 233572674711604604519014902334948133513444*t[0] + 535453460641822632058096218419954325337796*t[1] + 725112018286073523450664990921518386913035,-1,p)%p, (1229680448238589741915782165367654357920185*t[0]**6 + 508331960611786860744946345382725399597519*t[0]**5 + 1343958908519289578671422203106481694277716*t[0]**4*t[1] + 177167026616744824850256300247635539724057*t[0]**3*t[1]**2 + 647526478257364195975697407176118287861906*t[0]**4 + 874634578828271234182240863130269063092359*t[0]**3*t[1] + 753721599708341578448324615735431250261044*t[0]**2*t[1]**2 + 59195913557099283872495176385768072148921*t[0]*t[1]**3 + 135184449413711070637582564227488684273926*t[1]**4 + 1184268232038119513987721523209048245879902*t[0]**3 + 588376066139055328517853740807864391561055*t[0]**2*t[1] + 975956920560485006036771022835309336072696*t[0]*t[1]**2 + 1352108846430422970045668681682022723360513*t[1]**3 + 1280832417616997174969599325837067484280181*t[0]**2 + 954546681684014316952546155309712995684234*t[0]*t[1] + 865928094420333438629116336228132264435796*t[1]**2 + 1082085886860697193173121066542089802274658*t[0] + 755869998556204076975668261501936206771336*t[1] + 657902451019006293214253561308197638483112)*pow(956880610267536390357724782030411500415237*t[0]**3 + 1037730046117678117493148768796528084935491*t[0]**2*t[1] + 591774972558173485718732355032088525431674*t[0]*t[1]**2 + 1225953236373933752417367674993992583036185*t[1]**3 + 350359012067406906778522353502422200270166*t[0]**2 + 245222696137823073119338416038381708703277*t[0]*t[1] + 1197892972677768820041026587455773400480227*t[1]**2 + 814198369070575747297044733543073893428994*t[0] + 447093761510564524382892260162823859185717*t[1] + 558976911634572335364921619094958402137856,-1,p)%p)

def have_fun(g2, key):
    res = g1
    while key:
        if key&1:
            res = have(res,g2)
        g2 = fun(g2)
        key >>= 1
    return res

points = [have_fun(g2,i) for i in range(10)] + [g1,g2]

M = []
Y = []
for x,y in points:
    M.append([x**2,x,y**2,y,x*y,1])
    Y.append(-(x**3))
    
M = matrix(Zmod(p),M)
Y = vector(Y)
X = M.solve_right(Y)

R = Zmod(p)["x, y"]
(
    x,
    y,
) = R._first_ngens(2)

# print(X)
A, B, C, D, E, F = X
f = x**3 + A * x**2 + B * x + C * y**2 + D * y + E * x * y + F
# print(f)

def mapping(point):
    return (-point[0]*pow(C,-1,p) % p , -point[1]*pow(C,-1,p) % p)

f1 = -x**3 + A*pow(C,-1,p)*x**2 - B * pow(C,-2,p) * x + y ** 2 - D*pow(C,-2,p)*y + E*pow(C,-1,p)*x*y + F*pow(C,-3,p)

C1 = EllipticCurve(f1)
G1 = C1(mapping(g1))
G2 = C1(mapping(g2))

y = (1233646914495991358880000369082822614720033, 169216170896679696320800078452784590711491)
Y = C1(mapping(y))


n = G2.order()
# print(n)
factors = factor(n)
print(factors)
factors = [59 , 139 , 11032831 , 46795057 , 160737905349093178761667]
Y = Y - G1

result = []
for f1 in factors[:-1]:
    t = n // f1
    res = discrete_log(t*Y,t*G2,operation='+') # operation='+' 默认是乘
    result  += [res]

print(result)
k = crt(result,factors[:-1])
assert k == discrete_log(
    Y * factors[-1], G2 * factors[-1], operation="+"
)

print(k)

enc = b"t\xf1x\xc2'}q\xe7i.\x0cmj\x0fkNkVJ-\xd5\xbf\xf9H_\xd1\x04hO\xcd\xe1\x95P\xad\xea\xe1\xec\x1c\xben?RCr\x932\x90t"
from Crypto.Cipher import AES
cipher = AES.new(str(int(k)).encode()[:16], AES.MODE_ECB)
m = cipher.decrypt(enc)
print(m)

# b'flag{Tw1s7ed_5tr4nge_Curve_but_S0_3asy}\xe4\xbd\xa0\xe5\xa5\xbd\xe5\xbc\xb7'
#crypto
椭圆曲线算法_攻击
https://baymax-fools.github.io/2026/03/12/crypto/椭圆曲线算法-攻击/
Author
Baymax
Posted on
March 12, 2026
Updated on
June 17, 2026
Licensed under