Misay's blog

羊城杯2024

发表于 分类于
羊城杯2024初赛Crypto复现

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)

题目给出如下运算式子

自定义了一个曲线上的计算

然后我们知道

这里我们的曲线方程实际是 我们可以由解出来这里的

我们做一个换元 可得 参照鸡块师傅的博客

2023-CryptoCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz) Barak中，sage的EllipticCurve_from_cubic方法可以从一个三元多项式方程来衍生出一条标准维尔斯特拉斯椭圆曲线

我们可以由这个多项式衍生出一条标准的维尔斯特拉斯椭圆曲线，并且获得它和原曲线的映射关系，之后就是在这条标准曲线上做ECDLP即可

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

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

# Q = G * m
xg, yg = G
xq, yq = Q
d = (2*xg^3 + yg^3 + 1) * pow(xg*yg,-1,p) % p
# dd = (2*xq^3 + yq^3 + 1) * pow(xq*yq,-1,p) % p == d
A = [0,1,-1]
R.<x,y,z> = Zmod(p)[]
cubic = 2*x^3+y^3+z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic, A,morphism=True) # 由多项式方程生成一个曲线
Ee = EllipticCurve_from_cubic(cubic, A,morphism=False)

# E包含映射关系
G = E(G)
Q = E(Q)
order = Ee.order()
print(order)
m = G.discrete_log(Q)
print(m)
flag = b"DASCTF{" + long_to_bytes(m) + b"}"
print(flag)
# DASCTF{e@sy_cuRvL_c0o!}

这里我们获得的E是包含映射关系的曲线，而Ee就是正常的维尔斯特拉斯曲线，所以用E进行坐标转化，用Ee来算阶即可，如果这里我们DLP出来的不满足范围的话再考虑加减几个曲线的阶爆破即可

Baby_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
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
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'}

给出了曲线上点加的计算方式

不是常规的椭圆曲线 先不管往下看

我们先给出第一组曲线参数，以及点然后计算 然后再用建立一条标准椭圆曲线，要你解ECDLP 那么我们就考虑爆破求出然后直接解AES即可

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
75
76
import os
import hashlib
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from tqdm import tqdm

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

a = 46
d = 20
p1 = 826100030683243954408990060837
K1 = (a, d, p1)
G1 = (560766116033078013304693968735, 756416322956623525864568772142)
P1 = (528578510004630596855654721810, 639541632629313772609548040620)
Q1 = (819520958411405887240280598475, 76906957256966244725924513645)

# -------------------------------------find b c------------------------------------------

for i in tqdm(range(-100, 100)):
    P2 = mul_curve(i, G1, K1)
    if P2 == P1:
        c = i
        break

for i in tqdm(range(-100, 100)):
    Q2 = mul_curve(i, G1, K1)
    if Q2 == Q1:
        b = i
        break

print(f"b = {b}, c = {c}")
# b = 98, c = 35
# --------------------------------------ECDLP--------------------------------------------

p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-c, b])
G = (584273268656071313022845392380 , 105970580903682721429154563816)
P = (401055814681171318348566474726 , 293186309252428491012795616690)
G = E(G)
P = E(P)
k = G.discrete_log(P)

print(f"found key = {k}")
# found key = 2951856998192356
# ------------------------------------- AES Decrypt ------------------------------------------


iv = bytes.fromhex('bae1b42f174443d009c8d3a1576f07d6')
ciphertext = bytes.fromhex('ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4')
key = hashlib.sha256(str(k).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ciphertext)

print(flag)
# DASCTF{THe_C0rv!_1s_Aw3s0me@!!}\x01

RSA_Loss

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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'

给出了RSA解密的一个小，但不是我们的预期解 猜测原因是导致的,简单爆破不可行

我们仍有 这里尝试利用我们的flag的组成规律 即

m = b'DASCTF{' + ?????? + b'}'

中间的??????字符串大致20~60字节 且是可打印字符 可以考虑来爆破，我们知道flag最小的情况是

m0 = b'DASCTF{' + b'\x00' * i + b'}'

最大是

m1 = b'DASCTF{' + b'\xff' * i + b'}'

我们就很自然的能想尝试去进行个爆破

设m的长度是i+8，可以计算出上下界m0~m1，我们又知道必有,然后去找这个解即可

运气很好 能直接爆出来，需要大概15分钟

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
from Crypto.Util.number import *
from tqdm import tqdm
import string

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

# --------------------brute_crack--------------------------------------
for i in tqdm(range(20, 60)):
    flag0 = b"DASCTF{" + b"\x00" * i + b"}"
    flag1 = b"DASCTF{" + b"\xff" * i + b"}"
    m0 = bytes_to_long(flag0)
    m1 = bytes_to_long(flag1)
    k0 = (m0 - m) // n
    k1 = (m1 - m) // n
    
    k = k0
    while k <= k1:                
        pm = k * n + m
        pmes = long_to_bytes(pm)
        if (pmes.startswith(b"DASCTF{") and pmes.endswith(b"}") and all(32 <= byte <= 126 for byte in pmes)): 
            print(f"Found potential flag (i={i}, k={k}): {pmes}")
            break
        if pm % 256 == ord('}'):
            k += 256  
        else:
            k += 1    

# Found potential flag (i=28, k=181321970727117606593880360): b'DASCTF{o0p5_m3ssaGe_to0_b1g_nv93nd0}'

但是这个解法不够优雅 我们还能再进行一个优化

前面提到 我们有 根据bytes_to_long函数的特性 我们已知，对于字符串 它的转换长整数结果会是 这里我们的前缀是DASCTF{ 后缀是}，我们都是知道的 也就是说 我们能得到中间的?????的byts_to_long结果 就转化为求它了,设这里是flag

我们可以得到 flag又可以拆成

这不就是个背包格问题吗？

我们要求的的值是ASCII码 满足 我们直接令 就得到了一个很小小量的的方程 这里满足 带入上面已有的方程就是 简单移项 那就是 做换元

造格子 这里格的大小是 取次根，这里的是200比特左右 需要我们的配大一点点 取先试试

调不出来 参考N0wayBack师傅的题解 造这样的格子效果更好

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
from Crypto.Util.number import *
from tqdm import tqdm
import string

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

prefix = b"DASCTF{"
suffix = b"}"
t = n
centerMark = 79

# 遍历flag的长度
for i in tqdm(range(20, 40)):
    length = i
    k = length - len(prefix) - len(suffix)
    pc = c
    # 剥离前后缀的影响
    pc = (pc - bytes_to_long(prefix) * pow(256, k + len(suffix), n) - bytes_to_long(suffix)) % n

    # 获得明文的对应长整数
    cc = pc * inverse_mod(256, n) % n
    sumConstant = sum(256^j for j in range(k))
    C = (cc - centerMark * sumConstant) % n

    # 造格子 规约
    M = matrix(ZZ, k + 2, k + 2)
    for index in range(k):
        M[index, index] = 1
        M[index, k+1] = t * 256^index
    M[k, k] = 1
    M[k, k + 1] = -t * C
    M[k + 1, k + 1] = t * n
    L = M.BKZ()
    # print(L)

    # 筛选可能的答案
    for row in L:
        tag = 1
        for num in row[:-2]:
            if num < 33 - centerMark or num > 126 - centerMark:
                tag = 0
                break
                
        if tag:
            flag = ""
            for num in row[:-2][::-1]:
                flag += chr(num + centerMark)
            if chr(centerMark) * 4  not in flag:
                pflag = b"DASCTF{" + flag.encode() + b"}"    
                print(f"length {i} , flag {pflag}")
    
'''
100%|██████████| 20/20 [00:00<00:00, 323.41it/s]
length 36 , flag b'DASCTF{o0p5_m3ssaGe_to0_b1g_nv93nd0}'
length 37 , flag b'DASCTF{+[ML"sIDDTCQ[,)Av6|LU.?-+rcB|}'
length 38 , flag b'DASCTF{O=V-MT"B=oe2&T@3i}oXKE2:"DfV>n}'
length 39 , flag b'DASCTF{@NmMm^1Pk@J3QXIA5D<OPXFF(HA{cVQ}'
length 39 , flag b'DASCTF{cU5AW:?Gg!cR8Y*CK@kQAaMxAIH]l<Q}'
length 39 , flag b'DASCTF{n^[ERBLa$Xe}^YhWP7nTLa0*@^%fToN}'
length 39 , flag b'DASCTF{CBEL|Qs>g@qC9IMcWenU$j\\TZ)2$%T5}'
length 39 , flag b"DASCTF{eA671MFQzT'C7:[7vX]J^G]OH^C>-ms}"
'''

后面也换了一下centerMark有点玄学的 建议是75~100之间多选点 师傅的88和我的79都能规约出来，这道题的参数配平倒是没那么重要

Theorem_Plus

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

RSA问题 由函数decode_e给出，然后就是解一个相邻素数的RSA

先分析decode_e函数

首先计算e-1的阶乘mul

随后的判断式子e - mul % e - 1 == 0 用到了Wilson’s Theorem 本质是判断是否为素数

即式子 当且仅当是素数时成立

如果是素数，那么就有 由Wilson’s Theorem 这里的是

如果是合数，假设存在分解 那么在计算阶乘的时候，必有 也就必定有 此时的就是0

但是存在几个例外 如果为

那么

综上对于式子decode_e(p)我们只需要计算小于等于的素数个数 对于所有的素数 自减1，对于除开之外的合数 不变 尝试写个脚本跑一下？但是时间复杂度太高 有什么办法简化吗，考虑对这种大范围使用素数筛法即Sieve of Eratosthenes

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
from Crypto.Util.number import *
from tqdm import tqdm
import numpy as np
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
goal = 703440151

res = 0
def count_primes_with_sieve(p):
    if p < 2:
        return 0
    is_prime = np.ones(p + 1, dtype=bool)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(p**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = False
    return np.sum(is_prime) 
num =  count_primes_with_sieve(goal) 
e = abs(num * -1 + 2)
pp = floor(sqrt(n))
for i in range(-10000, 10000):
    p = pp + i
    if n % p == 0:
        q = n // p
        phi = (p-1) * (q-1)
        assert gcd(e,phi) == 1
        d = inverse_mod(e, phi)
        print(long_to_bytes(pow(c,d,n)))

# b'DASCTF{Ot2N63D_n8L6kJt_f40V61m_zS1O8L7}'