ECC（奇异曲线）

标签（空格分隔）： 离散对数

奇异曲线的基本解法

什么是奇异曲线呢？奇异曲线就是一个椭圆曲线上有一个点没有导数

首先得知道ECC的一个定理$ \phi(G)^n=\phi(nG)$
这里的$\phi(y,x)= {y+ax \over y-ax}$
注意此时的方程必须满足$y^2=x^3+ax^2$
所以我们可以很简单的得到n。但是原方程不是这样的啊。我们便可以将那个没有导数的点移动到原点，然后再进行套用解出n

例题

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

p = 9259018534502783714631247560818133078409930397939705162361230465031580254504264713899169170790687716589100652406132800533397486109926387016562663961524649
a = 0
b = 6235467631650349040636525320446729529985562949423449382969614887116983248527693872546808737512375916974084741892428681798937790855872528526403738040908493
c = 4165903654767429195543540819098180314477702137507994424192636596518008877139978822038616746899053449640020812062736993008962585578921635697413459959685760
d = 1889382340373247565387211782596794283852946561870564309251998196824383297786878212641581641540685106266683503654620956037368416192796434147249748216284648
e = 3015564788819504594313842562882781366361783108618226049128986996153057550014499326419988348165744003693083108924831219996703133056523468396967900376388617


def add(P1, P2):
    if P1 is None:
        return P2

    x1, y1 = P1
    x2, y2 = P2

    l = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (l**2 + a * l - b - x1 - x2) % p
    y3 = (l * (x1 - x3) - y1 - a * x3 - c) % p
    return (x3, y3)


def double(P):
    if P is None:
        return None

    x, y = P

    denom = (2 * y + a * x + c) % p
    num = (3 * x**2 + 2 * b * x + d - a * y) % p
    l = (num * pow(denom, -1, p)) % p
    x3 = (l**2 + a * l - b - 2 * x) % p
    y3 = (l * (x - x3) - y - a * x3 - c) % p
    return (x3, y3)


def mul(k, P):
    Q = None
    while k:
        if k & 1:
            Q = add(Q, P)
        P = double(P)
        k >>= 1
    return Q


m = bytes_to_long(flag)
G = (1244884551970947614719458919805713649754289814760243366205012699871413235954279930743612403791919112394457579170253990713250052822262255880036254772609156, 4579639528751113977115209571728128585569082149696598770106934145500742785077382446292613925719404433141749168427443122707253164477493499731016883616496009)
P = mul(m, G)
print(P)

# (9039120379228240875764080238389949393433230267005269099421166553853462484353350917730468887801035670710981414900285176863179650428412616144755102163764906, 6266065680737729548475090556806928225106996606788926050268440244885398464756877886842570309216095272026404453765198968208595242208306240371310555394416694)

EXP

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
from Crypto.Util.number import long_to_bytes

# 1. 题目参数
p = 9259018534502783714631247560818133078409930397939705162361230465031580254504264713899169170790687716589100652406132800533397486109926387016562663961524649
a = 0
b = 6235467631650349040636525320446729529985562949423449382969614887116983248527693872546808737512375916974084741892428681798937790855872528526403738040908493
c = 4165903654767429195543540819098180314477702137507994424192636596518008877139978822038616746899053449640020812062736993008962585578921635697413459959685760
d = 1889382340373247565387211782596794283852946561870564309251998196824383297786878212641581641540685106266683503654620956037368416192796434147249748216284648
e = 3015564788819504594313842562882781366361783108618226049128986996153057550014499326419988348165744003693083108924831219996703133056523468396967900376388617

G_x = 1244884551970947614719458919805713649754289814760243366205012699871413235954279930743612403791919112394457579170253990713250052822262255880036254772609156
G_y = 4579639528751113977115209571728128585569082149696598770106934145500742785077382446292613925719404433141749168427443122707253164477493499731016883616496009
P_x = 9039120379228240875764080238389949393433230267005269099421166553853462484353350917730468887801035670710981414900285176863179650428412616144755102163764906
P_y = 6266065680737729548475090556806928225106996606788926050268440244885398464756877886842570309216095272026404453765198968208595242208306240371310555394416694

F = GF(p)

# 2. 寻找奇异点 (xs, ys)
# 偏导数方程: 
# f(x,y) = x^3 + b*x^2 + d*x + e - y^2 - c*y = 0
# df/dy = -2y - c = 0 => ys = -c/2
ys = F(-c) / F(2)

# df/dx = 3x^2 + 2bx + d = 0
R.<x> = PolynomialRing(F)
df_dx = 3*x^2 + 2*b*x + d
roots = df_dx.roots()

xs = None
for r, _ in roots:
    # 验证该根是否在曲线上
    if r^3 + b*r^2 + d*r + e - ys^2 - c*ys == 0:
        xs = F(r)
        break

print(f"Singular point found: ({xs}, {ys})")

# 3. 平移点 G 和 P 使奇异点落在 (0,0)
Gx_sh, Gy_sh = F(G_x) - xs, F(G_y) - ys
Px_sh, Py_sh = F(P_x) - xs, F(P_y) - ys

# 4. 判断奇异曲线的类型 (Cusp 或 Node)
# 平移后的方程为: y^2 = x^3 + A * x^2, 其中 A = 3*xs + b
A = 3*xs + F(b)

if A == 0:
    print("Curve type: Cusp (Additive Group)")
    # 对于 Cusp，同构映射为: phi(x,y) = x / y
    phi_G = Gx_sh / Gy_sh
    phi_P = Px_sh / Py_sh
    m = phi_P / phi_G
else:
    print("Curve type: Node (Multiplicative Group)")
    # 对于 Node，同构映射为: phi(x,y) = (y + alpha * x) / (y - alpha * x)
    # 其中 alpha = sqrt(A)
    # 检查 A 是否是模 p 的二次剩余
    if A.is_square():
        alpha = A.sqrt()
        phi_G = (Gy_sh + alpha * Gx_sh) / (Gy_sh - alpha * Gx_sh)
        phi_P = (Py_sh + alpha * Px_sh) / (Py_sh - alpha * Px_sh)
        m = discrete_log(phi_P, phi_G)
    else:
        # 如果不是二次剩余，需在二次扩域 Fp2 中求解
        F2.<u> = F.extension(x^2 - A)
        alpha = u
        phi_G = (Gy_sh + alpha * Gx_sh) / (Gy_sh - alpha * Gx_sh)
        phi_P = (Py_sh + alpha * Px_sh) / (Py_sh - alpha * Px_sh)
        m = discrete_log(phi_P, phi_G)

print("m =", m)
try:
    print("Flag:", long_to_bytes(int(m)).decode())
except:
    print("Hex string:", hex(int(m)))