W'Blog

Wbuildings的自勉小屋

0%

2024羊城杯

发表于 分类于 Valine：
本文字数： 14k 阅读时长 ≈ 13 分钟

本科组挺离谱的，睡醒被第二十名拉开一大截

1.TH_Curve

题目

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)

对照点加的公式，是Twisted Hessian Curves

有一道 Hessian Curves 的例题

https://blog.maple3142.net/2023/07/09/cryptoctf-2023-writeups/#barak

多了个 a

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
import gmpy2
from Crypto.Util.number import *
# a*x^3+y^3+1 = d*x*y

G = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
p = 10297529403524403127640670200603184608844065065952536889
c = 1
a = 2
x = G[0]
y = G[1]
inv_xy = gmpy2.invert(x*y,p)
d = (a*x^3+y^3+1)*inv_xy % p

x, y, z = QQ["x,y,z"].gens()
eq = a * x ^ 3 + y ^ 3 + c * z ^ 3 - d * x * y * z	# 乘a
phi = EllipticCurve_from_cubic(eq)
E = phi.codomain().change_ring(GF(p))
P = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)

fx, fy, fz = map(lambda f: f.change_ring(F), phi.defining_polynomials())
phiP = lambda x, y, z=1: E(fx(x, y, z) / fz(x, y, z), fy(x, y, z) / fz(x, y, z))
EP = phiP(*P)
EQ = phiP(*Q)
x = discrete_log(EQ, EP, operation="+")
print(x)
od = EP.order()
print(
    [
        flag
        for i in range(E.order() // od)
        if (flag := long_to_bytes(int(x + od * i))).isascii()
    ]
)

# e@sy_cuRvL_c0o!

记

曲线本身是个多项式

1
2
3
4
5
6
7
8
p = 10297529403524403127640670200603184608844065065952536889
a = 2
G = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
gx,gy=G[0],G[1]
PR.<d>=PolynomialRing(Zmod(p))
f=a*gx^3+gy^3+1-d*gx*gy
ret=f.roots()
print(ret)

EllipticCurve_from_cubic需要三个变量才能构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
d=8817708809404273675545317762394593437543647288341187200
Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)
from Crypto.Util.number import *
import gmpy2
p = 10297529403524403127640670200603184608844065065952536889
a = 2
P=(8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)

R.<x,y,z> = Zmod(p)[]
cubic = a*x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
P = E(P)
Q = E(Q)
m = P.discrete_log(Q)
m=525729205728344257526560548008783649
print(long_to_bytes(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
from Crypto.Util.number import *

p = 10297529403524403127640670200603184608844065065952536889
a = 2
G = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
d = 8817708809404273675545317762394593437543647288341187200
Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)

def THessian_to_Weierstrass(P):  
    x, y = P  
    A = (d ** 3 - 27 * a) * pow(3 + 3 * y + d * x, -1, p)  
    u = (x * A) * pow(3, -1, p) - (d ** 2) * pow(4, -1, p)  
    v = A * (1 - y) * pow(2, -1, p)  
    return (u, v)

a4 = -(d ** 4 + 216 * d * a) * pow(48, -1, p)  
a6 = (d ** 6 - 540 * d ** 3 * a - 5832 * a ** 2) * pow(864, -1, p)

E = EllipticCurve(GF(p), [a4,a6])
print(E)

G = E(THessian_to_Weierstrass(G))
Q = E(THessian_to_Weierstrass(Q))
m = Q.log(G)
print(long_to_bytes(m))

# b'e@sy_cuRvL_c0o!'

点在曲线中的转换：

1
2
3
E = EllipticCurve(GF(p), [a4,a6])

G = E(THessian_to_Weierstrass(G))

2.BabyCurve

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
#!/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'}

差点舍本逐末，因为a，b很小，直接在源码的基础上爆破c，d 就很方便，然后是ECC中的离散对数问题

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
#!/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 = (528578510004630596855654721810, 639541632629313772609548040620)
Q1 = (819520958411405887240280598475, 76906957256966244725924513645)

for i in range(1000):
    PP = mul_curve(i, G1, K1)
    if PP == P1:
        c = i
    QQ = mul_curve(i, G1, K1)
    if QQ == Q1:
        b = i

p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-c, b])
G = E.gens()[0]

P = E(401055814681171318348566474726,293186309252428491012795616690)
G = E(584273268656071313022845392380 , 105970580903682721429154563816)
key = P.log(G)

def AES_encrypt(k):
    key = hashlib.sha256(str(k).encode()).digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    cipher = cipher.decrypt(c)
    
    return cipher

iv = 'bae1b42f174443d009c8d3a1576f07d6'
c = 'ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4'
iv = bytes.fromhex(iv)
c= bytes.fromhex(c)
print(AES_encrypt(key))

# DASCTF{THe_C0rv!_1s_Aw3s0me@!!}

求解以base为底，a的对数；ord为base的阶，可以缺省，operation可以是'+'与 '*'，默认为'*'；bounds是一个区间(ld,ud)，需要保证所计算的对数在此区间内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#通用的求离散对数的方法
x=discrete_log(a,base,ord,operation)

#求离散对数的Pollard-Rho算法
x=discrete_log_rho(a,base,ord,operation)

#求离散对数的Pollard-kangaroo算法(也称为lambda算法)
x=discrete_log_lambda(a,base,bounds,operation)

#小步大步法
x=bsgs(base,a,bounds,operation)

k = P.log(G)

3.RSA_loss

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from gmpy2 import *
p = getPrime(100)
q = getPrime(100)
n = p * q
e = 65537
message = b""
m = bytes_to_long(message)
c = pow(m, e, n)
print(f'c = {c}')
print(f'p = {p}')
print(f'q = {q}')
d = invert(e,(p-1)*(q-1))
newm = pow(c, d, n)
print(long_to_bytes(newm))
#c = 356435791209686635044593929546092486613929446770721636839137
#p = 898278915648707936019913202333
#q = 814090608763917394723955024893
#b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15'

试了一下直接正常爆破 k*n 不可行

bcactf-4.0/rsa-is-broken/rsa-broken-sol.py at main · BCACTF/bcactf-4.0 (github.com)

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
import libnum
from gmpy2 import *
import math
import re

p = 898278915648707936019913202333
q = 814090608763917394723955024893
c = 356435791209686635044593929546092486613929446770721636839137
e = 65537
n = p * q

d = invert(e,(p-1)*(q-1))
newm = pow(c, d, n)

# 调整明文直到其最后一个字节为 '}'
while newm % 256 != 125:    # ord('}') = 125
    newm += n

# 构建目标前缀和flag模板
tmp = b'DASCTF{' + b'0' * math.floor(math.log(newm, 256) - 7)
flag = libnum.n2s(int(newm))

# # 持续调整解密后的消息直到符合目标格式
while re.fullmatch(b'[0-9a-zA-Z_{}]+', flag) is None:
    if flag[:7] == b'DASCTF{':
        newm += n * 256
    else:
        newm += n * 256 * int(math.ceil((libnum.s2n(tmp) - newm) / (n * 256)))
        tmp += b'0'
    flag = libnum.n2s(int(newm))

print(flag)

# DASCTF{o0p5_m3ssaGe_to0_b1g_nv93nd0}

已知 头DASCTF{，尾 }，中间未知，需要未知的位数小于 n 才能做，所以我们还需要将未知部分拆分成两份，一部分爆破，一部分用于求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from itertools import *
import string

e = 65537
c = 356435791209686635044593929546092486613929446770721636839137
p = 898278915648707936019913202333
q = 814090608763917394723955024893
n = p * q
cc = b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15'
cc = bytes_to_long(cc)

table = string.digits + string.ascii_letters + "_"
nums = 3
for j in product(table,repeat = nums):
    fix = bytes_to_long(b"DASCTF{" + "".join(j).encode() + b"\x00"*25 + b"}")
    try:
        flag = "".join(j) + long_to_bytes((cc - fix)*inverse(256,n) % n).decode()
        if(all(i in table for i in flag)):
            print("DASCTF{" + flag + "}")
            break
    except:
        pass

4.TheoremPlus

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

def decode_e(e):
    if e > 1:
        mul = 1
        for i in range(1, e):
            mul *= i
        if e - mul % e - 1 == 0:
            mulmod = mul % e - e
        else:
            mulmod = mul % e
        return mulmod + decode_e(e - 1)
    else:
        return 0


q = getPrime(1024)
p = next_prime(q)
n = p * q
phi = (p - 1) * (q - 1)
e = abs(decode_e(703440151))
c = pow(bytes_to_long(flag), e, n)
print('n = {}\n'
      'c = {}'.format(n, c))

'''
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
'''

测试发现这就是算素数个数的，但要-2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def decode_e(e):
    if e > 1:
        mul = 1
        for i in range(1, e):
            mul *= i
        if e - mul % e - 1 == 0:
            mulmod = mul % e - e
        else:
            mulmod = mul % e
        return mulmod + decode_e(e - 1)
    else:
        return 0

print(abs(decode_e(200)))

# 44

for e in range(200):
    if isPrime(e):
        num=num+1
print(num)

# 46

找到——Python 埃拉托色尼筛法 – 寻找质数

Python 埃拉托色尼筛法 – 寻找质数|极客教程 (geek-docs.com)

然后费马小定理分解 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
55
56
57
58
59
60
61
62
63
64
65
def sieve_of_eratosthenes(n):
    if n < 2:
        return []

    primes = [True] * ((n+1)//2)
    primes[0] = False

    p = 3
    while p * p <= n:
        if primes[p // 2]:
            for i in range(p * p, n+1, 2 * p):
                primes[i // 2] = False
        p += 2

    return len([2] + [2 * i + 1 for i, is_prime in enumerate(primes) if is_prime])

n = 703440151
prime_numbers = sieve_of_eratosthenes(n)
print(prime_numbers)
# 36421875

n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566

import libnum

def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, verbose=True):
    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(n)
    count = 0
    while b*b != b2:
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q

    print('p=',p)
    print('q=',q)

    return p, q

pq=fermat(n)

p=pq[0]
q=pq[1]
phi=(p-1)*(q-1)

e = 36421873
d=libnum.invmod(e,phi)
m = libnum.n2s(int(pow(c,d,n)))
print(m)

# DASCTF{Ot2N63D_n8L6kJt_f40V61m_zS1O8L7}

除了 埃拉托色尼筛法 找素数之外

sage中可以用 prime_pi(703440151) 函数来输出703440151中有多少个素数

-------------　　　　本文结束　　感谢阅读　　　　-------------