发表于 更新于

基础知识:

https://www.hyperelliptic.org/EFD/g1p/auto-twistedhessian.html
https://yunru-volknet.github.io/posts/2024羊城杯/
2024羊城杯的一道题

题目:

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
from Crypto.Util.number import *
from secret import flag


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


def mul_THcurve(n, P):
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_THcurve(R, P)
        P = add_THcurve(P, P)
        n = n // 2
    return R


p = 10297529403524403127640670200603184608844065065952536889
a = 2
G = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)

FLAG = flag.lstrip(b'DASCTF{').rstrip(b'}')
assert len(FLAG) == 15
m = bytes_to_long(FLAG)
assert m < p
Q = mul_THcurve(m, G)
print("Q =", Q)
# Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)

exp:

结合一下名字 Twisted Hessian curves 搜一下就知道满足啥条件了.
a∗x3+y3+1=d∗x∗ya*x^3+y^3+1=d*x*y
化简出d来
d=a⋅Q[0]3+Q[1]3+1Q[0]⋅Q[1]mod  pd = \frac{a \cdot Q[0]^3 + Q[1]^3 + 1}{Q[0] \cdot Q[1]} \mod p
别忘了mod p，这里m[0]就是x,m[1]就是y。
换元
X=x/ZX=x/Z
Y=y/ZY=y/Z
齐次化，归一化
a∗X3+Y3+1=d∗X∗Y∗Za*X^3+Y^3+1=d*X*Y*Z
参数 morphism=True 表示生成椭圆曲线时会自动生成一个从原始曲线到椭圆曲线的同态映射
用上week_txt3的part2解这个椭圆曲线方程

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
from Crypto.Util.number import *
p = 10297529403524403127640670200603184608844065065952536889
a = 2
P = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)
d=(a * Q[0] ** 3 + Q[1] ** 3 + 1) * inverse(Q[0] * Q[1], p) % p
R.<x,y,z>=Zmod(p)[]
cubic = 2*x^3+y^3+z^3-d*x*y*z
E=EllipticCurve_from_cubic(cubic,morphism=True)
Q=E(Q)
P=E(P)
n=P.order()
def f(n,P,Q):
    factors, exponents = zip(*factor(n))
    primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
    print (primes)
    dlogs = []
    for fac in primes:
        t = int(int(P.order()) // int(fac))
        dlog = discrete_log(t*Q,t*P,operation="+")
        dlogs += [dlog]
        print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
    num2=crt(dlogs,primes)
    return num2
num2=f(n,P,Q)
print(long_to_bytes(num2))

factor: 9, Discrete Log: 3
factor: 49, Discrete Log: 0
factor: 11, Discrete Log: 0
factor: 19, Discrete Log: 7
factor: 29, Discrete Log: 8
factor: 1361, Discrete Log: 225
factor: 6421, Discrete Log: 3560
factor: 3376343, Discrete Log: 837823
factor: 1815576031, Discrete Log: 1495286767
factor: 295369272787, Discrete Log: 292393302300
b’e@sy_cuRvL_c0o!’