1.ez_login

1.1解题思路

在浏览器复制粘贴网址nc1.ctfplus.cn:20520进入,然后输入账号“admin”，密码“admin123”，就可以看到flag。

2.神秘学

2.1题目代码

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

def get_poly(k):
    x,a,b = sympy.symbols('x a b')

    poly = x**3 - a * x**2 + b * x - c-k*n
    deriv1 = sympy.diff(poly, x)

    a1 = random.randint(2**119,2**120)
    b1 = random.randint(2**119,2**120)
    x1 = random.randint(2**510,2**511)

    deriv1_num = deriv1.subs({
        x: x1,
        a: a1,
        b: b1
    })
    return x1,deriv1_num

def RSA():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    k = getPrime(8)
    m = bytes_to_long(flag)
    e = inverse(c,(p-1)*(q-1))
    cipher = pow(m,e,n)
    return n,k,cipher

if __name__ == '__main__':

    n,k,cipher = RSA()
    x1, deriv1_num = get_poly(k)
    print('n =',n)
    print('x1 =',x1)
    print('cipher =',cipher)
    print('deriv1_num =',deriv1_num)

'''
n = 63407394080105297388278430339692150920405158535377818019441803333853224630295862056336407010055412087494487003367799443217769754070745006473326062662322624498633283896600769211094059989665020951007831936771352988585565884180663310304029530702695576386164726400928158921458173971287469220518032325956366276127
x1 = 3481408902400626584294863390184557833125008467348169645656825368985677578418186933223051810792813745190000132321911937970968840332589150965113386330575858
deriv1_num = 36360623837143006554133449776905822223850034204333042340303731846698251185379183585401025894584873826284649058526470710038176516677326058549625930550928515944115160614909195746688504416967586844354012895944251800672195553936202084073217078119494546421088598245791873936703883718926122761577400400368341859847
cipher = 17359360992646515022812225990358117265652240629363564764503325024700251560440679272576574598620940996876220276588413345495658258508097150181947839726337961689195064024953824539654084620226127592330054674517861032601638881355220119605821814412919221685287567648072575917662044603845424779210032794782725398473
'''

2.2解题思路和代码

根据公式poly = x^3 - a x^2 + b x - c-k*n和已知条件deriv1 = sympy.diff(poly, x)，

可以得到$deriv1num=3x1^2-a1x1+b1$

从而能解出a1,b1,代码如下：

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
~~~

```python
#以下代码在sagemath中执行
x1 = 3481408902400626584294863390184557833125008467348169645656825368985677578418186933223051810792813745190000132321911937970968840332589150965113386330575858
deriv1_num = 36360623837143006554133449776905822223850034204333042340303731846698251185379183585401025894584873826284649058526470710038176516677326058549625930550928515944115160614909195746688504416967586844354012895944251800672195553936202084073217078119494546421088598245791873936703883718926122761577400400368341859847

L = 2^119  # 下限
R = 2^120  # 上限

# 提前算好常数
C = deriv1_num - 3*x1^2

print("正在寻找 a1, b1...")

# 因为 a 和 x1 都巨大，不能暴力循环！
# 正确数学解法：a 在 [L, R) 区间，b 也必须落在 [L, R)
# 解不等式：L ≤ C + 2*a*x1 ≤ R

# 解下界
# C + 2*a*x1 >= L
# a >= (L - C) / (2*x1)

# 解上界
# C + 2*a*x1 < R
# a <  (R - C) / (2*x1)

a_min = ceil( (L - C) / (2*x1) )
a_max = floor( (R - C - 1) / (2*x1) )

# 这个区间里只有一个整数，就是答案
for a in range(a_min, a_max+1):
    b = C + 2*a*x1
    if L <= b < R:
        print("a1 =", a)
        print("b1 =", b)
        break
#a1 = 1044146410364763997022740502616607659
#b1 = 1107229666869418904756867438511144199
```

解出a1,b1后，默认代入x1可以让poly为0，那么根据公式$c = x_1³ - a_1 x_1² + b_1 x_1 - k  n$就可以直接解出私钥c(k很小，可以直接爆破)。

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

```python
#python
from Crypto.Util.number import long_to_bytes
n = 63407394080105297388278430339692150920405158535377818019441803333853224630295862056336407010055412087494487003367799443217769754070745006473326062662322624498633283896600769211094059989665020951007831936771352988585565884180663310304029530702695576386164726400928158921458173971287469220518032325956366276127
x1 = 3481408902400626584294863390184557833125008467348169645656825368985677578418186933223051810792813745190000132321911937970968840332589150965113386330575858
cipher = 17359360992646515022812225990358117265652240629363564764503325024700251560440679272576574598620940996876220276588413345495658258508097150181947839726337961689195064024953824539654084620226127592330054674517861032601638881355220119605821814412919221685287567648072575917662044603845424779210032794782725398473
a1 = 1044146410364763997022740502616607659
b1 = 1107229666869418904756867438511144199

# 枚举所有8位素数k
for k in [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251]:
    # 核心公式：c = (x1³ -a1x1² +b1x1) - k*n - t*k
    c= x1**3 - a1*x1**2 + b1*x1-k*n
    try:
        m = pow(cipher, c, n)
        flag = long_to_bytes(m)
        if b'ctf' in flag:
            print(f"flag: {flag}")

    except:
        continue
```

# 3.ECC

## 3.1 题目代码

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

```python
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)
```

## 3.2解题思路和代码

题目已知信息：

- G （基点）

- P = mG （公钥）

要求 m （私钥）。

因为我们发现曲线 可以变为这个形式：$Y^2 = (x-r)^3$

所以对该尖点奇异曲线 $Y^2=(x−r)^3$，$t=(x-r)/Y$ 就是数学家发现的、唯一正确的 “参数化映射”，

它天然满足：①点加法 → 数字加法②倍乘 mG → m⋅t(G)的变换。由此有以下解题代码：

~~~

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
p = 9259018534502783714631247560818133078409930397939705162361230465031580254504264713899169170790687716589100652406132800533397486109926387016562663961524649
a = 0
b = 6235467631650349040636525320446729529985562949423449382969614887116983248527693872546808737512375916974084741892428681798937790855872528526403738040908493
c = 4165903654767429195543540819098180314477702137507994424192636596518008877139978822038616746899053449640020812062736993008962585578921635697413459959685760
d = 1889382340373247565387211782596794283852946561870564309251998196824383297786878212641581641540685106266683503654620956037368416192796434147249748216284648
e = 3015564788819504594313842562882781366361783108618226049128986996153057550014499326419988348165744003693083108924831219996703133056523468396967900376388617

G = (
    1244884551970947614719458919805713649754289814760243366205012699871413235954279930743612403791919112394457579170253990713250052822262255880036254772609156,
    4579639528751113977115209571728128585569082149696598770106934145500742785077382446292613925719404433141749168427443122707253164477493499731016883616496009,
)

P = (
    9039120379228240875764080238389949393433230267005269099421166553853462484353350917730468887801035670710981414900285176863179650428412616144755102163764906,
    6266065680737729548475090556806928225106996606788926050268440244885398464756877886842570309216095272026404453765198968208595242208306240371310555394416694,
)


def inv(x):
    return pow(x, -1, p)


def long_to_bytes(n: int) -> bytes:
    if n == 0:
        return b"\x00"
    return n.to_bytes((n.bit_length() + 7) // 8, "big")


# ===== 题目原始群运算，用来做最终校验 =====
def add(P1, P2):
    if P1 is None:
        return P2

    x1, y1 = P1
    x2, y2 = P2

    lam = (y2 - y1) * inv((x2 - x1) % p) % p
    x3 = (lam * lam + a * lam - b - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1 - a * x3 - c) % p
    return (x3, y3)


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

    x, y = Pt

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


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


# ===== 核心攻击 =====
# 原曲线：
#   y^2 + c*y = x^3 + b*x^2 + d*x + e
#
# 令 Y = y + c/2，则
#   Y^2 = x^3 + b*x^2 + d*x + (e + c^2/4)
#
# 这题右边其实是一个完全立方：
#  Y…… (x - r)^3
# 因而曲线是尖点奇异曲线，不是安全的椭圆曲线。

inv2 = inv(2)
inv3 = inv(3)
inv4 = inv(4)

# 因为x³ + b x² + d x + const= x³ − 3r x² + 3r² x − r³，对应系数相等，由此可算出r
r = (-b * inv3) % p
const_term = (e + c * c * inv4) % p

# 验证确实是 (x - r)^3 = x^3 - 3r x^2 + 3r^2 x - r^3
assert (-3 * r - b) % p == 0
assert (3 * r * r - d) % p == 0
assert ((-pow(r, 3, p)) - const_term) % p == 0

# 对尖点曲线 Y^2 = (x-r)^3，
# 可用参数
#   u = (x-r) / Y
# 把群运算化成 F_p 上的加法：
#   u([m]G) = m * u(G)

def u_map(Pt):
    x, y = Pt
    Y = (y + c * inv2) % p
    return ((x - r) % p) * inv(Y) % p


uG = u_map(G)
uP = u_map(P)

m = uP * inv(uG) % p
flag = long_to_bytes(m)

print("[+] m =", m)
print("[+] flag =", flag)

# 最后用题目的原始 mul 再验一次
assert mul(m, G) == P
print("[+] check passed")

'''
[+] m = 15332171262807319558091438562607183829793153852814538240060075529164504121457743104882975101
[+] flag = b'xmctf{A_s1ngu14r_Curv3_15_n0t_s3cur3!}'
[+] check passed
'''