2025.5.1miniLCTF

2025.5.1miniLCTF

是 2025.5.1miniLCTF 哒！

勉勉强强做了3道题，稍微记录一下

rsasign

听说你很会RSA？ （flag以miniL开头）

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
from Crypto.Util.number import bytes_to_long, getPrime, inverse
from secret import flag


def genKeys(nbits):
    e = 0x10001
    p = getPrime(nbits // 2)
    q = getPrime(nbits // 2)
    n = p * q
    phi = n - (p + q) + 1
    d = inverse(e, phi)
    pubkey = (n, e)
    prikey = (d, p, q)
    
    return pubkey, prikey


def encrypt(msg, pubkey):
    m = bytes_to_long(msg)
    n, e = pubkey
    c = pow(m, e, n)
    return c


def get_gift(prikey):
    a = bytes_to_long(b'miniL')
    b = bytes_to_long(b'mini7')
    p, q = prikey[1:]
    phi = (p - 1)*(q - 1)
    giftp = p + a
    giftq = q + b
    gift = pow((giftp + giftq + a*b), 2, phi)
    return gift >> 740


if __name__ == "__main__":
    nbits = 1024
    pubkey, prikey = genKeys(nbits)
    c = encrypt(flag, pubkey)
    gift = get_gift(prikey)
    with open('output.txt', 'a') as f:
        f.write('pubkey = ' + str(pubkey) + '\n')
        f.write('c = ' + str(c) + '\n')
        f.write('gift = ' + str(gift) + '\n')

题目给出了$gift=(p+q+a+b+a * b)^2 \ (mod\ phi)$抹去了低740位后的结果，实际测试可以得出，在抹去了低740位后，gift和$(p^2+q^2)%phi>>740$的结果是一样的。
而$n=p * q$，phi和n在题目中抹去了低740位的情况下可以认为是一样的，同时测试得出$(p^2+q^2)//phi=2$，也就是说$gift<<740+2 * n$是$p^2+q^2$的近似值，那么我们可以解出$p+q$的近似值

1
2
import gmpy2
pq=int(gmpy2.iroot((gift<<740)+4*n,2)[0])

然后我们可以用这个近似值以及$n=p*q$来解出p和q的近似值

1
2
3
4
5
6
7
8
pq=20722134693508777238800877111571850901132625448654013903223307395782671739442468572117525995252542531260267404142594227817402250654503919887124996488743970

n=103894244981844985537754880154957043605938484102562158690722531081787219519424572416881754672377601851964416424759136080204870893054485062449999897173374210892603308440838199225926262799093152616430249061743215665167990978654674200171059005559869946978592535720766431524243942662028069102576083861914106412399

R.<x>=PolynomialRing(RealField(1000))
f=x*(pq-x)-n
root=f.roots()
print(int(root[0][0]),int(root[1][0]))

然后二元copper即可求出p，q
ps:这里之前做的时候表达式写错了，然后好久求不出来…
二元copper:

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
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    if isinstance(f, Polynomial):
        x, = polygens(f.base_ring(), f.variable_name(), 1)
        f = f(x)

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

解p,q:

1
2
3
4
5
6
7
8
9
10
n=103894244981844985537754880154957043605938484102562158690722531081787219519424572416881754672377601851964416424759136080204870893054485062449999897173374210892603308440838199225926262799093152616430249061743215665167990978654674200171059005559869946978592535720766431524243942662028069102576083861914106412399

p1=8501639590121977595053523738818375259679414794730106020578368658056270529108719142843616239876180609592408042971719162819965092838486348749800524648844783
q1=12220495103386799643747353372753475641453210653923907882644938737726401210333749429273909755376361921667859361170875064997437157816017571137324471839899186

P.<x,y> = PolynomialRing(Zmod(n))
f=(p1-x)*(q1+y)-n
bounds = (2^230,2^230)
res = small_roots(f,bounds,m = 4 ,d = 7)
print(res)

然后正常解个RSA即可

1
miniL{D0_Y@U_Li)e_T&@_RRRSA??}

babaisiginsigin

Cryptoers(?) sign in here \(≥v≤)/

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
import random
import socket
import threading
import os

def calculate_level1(m, x, y):
    return (m | x) + (m | y)

def calculate_level2(m, x, y):
    return (m | x) + (m ^ y)

def level(conn, calculate, x, y, guess, description, test_times):
    for _ in range(test_times):
        conn.sendall(b"Enter your number: ")
        
        # 设置 5 秒超时
        conn.settimeout(5)
        
        try:
            data = conn.recv(1024)
            if not data:
                return False
            try:
                test = int(data.strip())
            except:
                conn.sendall(b"Invalid input. Bye.\n")
                return False
            result = calculate(test, x, y)
            conn.sendall(f"Calculation result: {result}\n".encode())
        except socket.timeout:
            conn.sendall(b"Time out! Respond in 5 seconds.\n")
            return False

    conn.sendall(f"\nNow, guess the result of {description} for m = {guess}:\n".encode())
    
    # 设置 5 秒超时
    conn.settimeout(5)
    
    try:
        data = conn.recv(1024)
        if not data:
            return False
        try:
            user_guess = int(data.strip())
        except:
            conn.sendall(b"Invalid input. Bye.\n")
            return False

        correct_result = calculate(guess, x, y)
        if user_guess == correct_result:
            conn.sendall(b"Correct! Proceeding to next level...\n\n")
            return True
        else:
            conn.sendall(b"Wrong guess! Exiting...\n")
            return False
    except socket.timeout:
        conn.sendall(b"Time out! You took too long to respond.\n")
        return False

def handle_client(conn, addr, flag):
    conn.sendall(b"Welcome to Puzzle!\n\n")
    try:
        # Level 1
        x = random.getrandbits(30)
        y = random.getrandbits(30)
        guess = random.getrandbits(30)
        conn.sendall(b"Level 1:\n")
        if not level(conn, calculate_level1, x, y, guess, "(m | x) + (m | y)", test_times=2):
            conn.close()
            return

        # Level 2
        x = random.getrandbits(30)
        y = random.getrandbits(30)
        guess = random.getrandbits(30)
        conn.sendall(b"Level 2:\n")
        if not level(conn, calculate_level2, x, y, guess, "(m | x) + (m ^ y)", test_times=2):
            conn.close()
            return

        # 通关，发flag
        conn.sendall(f"Congratulations! You've passed all levels!\nHere is your flag: {flag}\n".encode())
    except Exception as e:
        conn.sendall(b"An error occurred. Bye.\n")
    finally:
        conn.close()

def main():
    host = "0.0.0.0"
    port = 2227

    flag = os.getenv('FLAG', 'flag{testflag}')

    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.bind((host, port))
    s.listen(5)
    print(f"[+] Listening on {host}:{port}")

    while True:
        conn, addr = s.accept()
        threading.Thread(target=handle_client, args=(conn, addr, flag)).start()

if __name__ == "__main__":
    main()

题目要求我们完成2个挑战，每个挑战会先让我们发送2个m，靶机会返回特定计算后的结果，然后让我们计算靶机给出的m的计算后的结果。
这里我们并不需要计算出准确的x和y，只需要得到一个等效的x,y，使得我们的计算结果和靶机上的基本都是一样的就好了。
我的想法是，对于一个二进制的数m，比如10101，靶机会计算$(m|x)+(m|y)$，对于第i位比特位,假如$m_i$是0，那么返回的结果中的第i位就会是$x_i+y_i$，而如果$m_i$是1,那么返回的结果中的第i位就会是$1+1$，就一定是0，同时往前进一位。
那么对于一个01交替的二进制数m来说，这里假设还是10101，对于它的计算结果r，如果$m_0$(最低位)是0，同时$r_0$是0，那么$x_0$和$y_0$就可能都是0，或者都是1，那么我们再看$r_{1}$，如果也是0，那么就证明在$r_0$的计算中没有进位，那么$x_0$和$y_0$就只可能都是0，反之则都是1。
如果$r_0$是1，那么就证明$x_0$和$y_0$中有一个1，而我们可以任意让其中一个是1即可，因为不管哪个是1，这不影响计算结果。
然后我们会注意到如果$m_i$为1的时候会向前进一位，但这也只是让我们上面的结果稍稍改变了一下，并不会使得$x_{i+1}$和$y_{i+1}$变的不确定。
在这种构造下，我们就可以得到x和y一半的比特位了(这里的x，y指等效的x，y)，然后我们对m按位取反即可得到另一半比特位。
这个过程可以交给z3来完成。
然后对于第二部分z3仍然可以求解，我做的时候没有仔细的去思考过，只是想试试z3还能不能做，然后准确率竟然比第一部分还高，很神奇。
z3可能出错的原因我不清楚，它是有可能解出连约束都过不了的解的，但概率还是比较小的，多交换几次即可。
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
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
from z3 import *
import random
from websocket import create_connection

def calculate_level1(m, x, y):
    return (m | x) + (m | y)

def calculate_level2(m, x, y):
    return (m | x) + (m ^ y)

def pred(m1,res1,m2,res2,guess,cal):
    x=BitVec('x',30)
    y=BitVec('y',30)
    solver=Solver()
    solver.add(res1==cal(m1,x,y))
    solver.add(res2==cal(m2,x,y))
    if solver.check()==sat:
        root=solver.model()
        a=root[x].as_long()
        b=root[y].as_long()
        #print('===========',res1==cal(m1,a,b),res2==cal(m2,a,b))
        return cal(guess,a,b)
    else:
        return False
def test(cal):
    x = random.getrandbits(30)
    y = random.getrandbits(30)
    guess = random.getrandbits(30)

    m1 = int('01' * 15, 2)
    m2 = m1 ^ ((1 << 30) - 1)
    res1=cal(m1, x, y)
    res2=cal(m2, x, y)

    predict=pred(m1,res1,m2,res2,guess,cal)
    real=cal(guess,x,y)
    print(predict==real)
"""
for i in range(50):
    test(calculate_level1)
"""

url = "wss://ctf.xidian.edu.cn/api/traffic/D9UHsvaTW4RfhMxCyB5JX?port=2227"
r = create_connection(url)

m1 = int('01' * 15, 2)
m2 = m1 ^ ((1 << 30) - 1)

data=r.recv().decode()
print(data)

r.send(str(m1).encode())

data=r.recv().decode()
print(data)

i=data.find(': ')
j=data.find('\nE')
res1=int(data[i+2:j])

r.send(str(m2).encode())

data=r.recv().decode()
print(data)

i=data.find(': ')
j=data.find('\n\n')
res2=int(data[i+2:j])

i=data.find(' = ')
j=data.find(':\n')

guess=int(data[i+3:j])

predict=pred(m1,res1,m2,res2,guess,calculate_level1)

r.send(str(predict).encode())

data=r.recv().decode()
print(data)


#cal2
r.send(str(m1).encode())

data=r.recv().decode()
print(data)

i=data.find(': ')
j=data.find('\nE')
res1=int(data[i+2:j])

r.send(str(m2).encode())

data=r.recv().decode()
print(data)

i=data.find('t: ')
j=data.find('\n\n')
res2=int(data[i+3:j])

i=data.find(' = ')
j=data.find(':\n')

guess=int(data[i+3:j])

predict=pred(m1,res1,m2,res2,guess,calculate_level2)

r.send(str(predict).encode())

data=r.recv().decode()
print(data)

flag:

1
miniLCTF{646AI-51G1n-CRYpto_Z-l5-Y0u_flag-is_WiN561}

ezhash？！

这次你还能碰撞的出来吗？ （注：flag以miniL开头）

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

def shash(value,key):
    assert type(value) == str
    assert type(key) == int
    length = len(value)

    if length == 0:
        return 0
    mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    x = (ord(value[0]) << 7) & mask
    for c in value:
        x = (key * x) & mask ^ ord(c)

    x ^= length & mask

    return x

def get_test(key):

    testvalue = []
    testhash = []

    for i in range(64):
        a = ''.join(random.choices(string.ascii_letters + string.digits, k=32)) 
        testvalue.append(a)
        testhash.append(shash(a,key))

    return testvalue,testhash

if __name__ == "__main__":
    assert len(flag) == 32
    assert type(flag) == str
    key = getRandomInteger(128)
    testvalue,testhash = get_test(key)
    shash = shash(flag,key)
    with open('output.txt', 'a') as f:
        f.write('testvalue = ' + str(testvalue) + '\n')
        f.write('testhash = ' + str(testhash) + '\n')
        f.write('shash = ' + str(shash) + '\n')

题目给了64组测试数据，然后一个flag的哈希值。
那么我们通过测试数据来解出所用的key，然后解这个哈希即可。
题目中提到key是128位的，但我实际上仅通过一组数据解出来一个更小的key，同时这个key对于后面63组数据来说是符合的，也就是说我们可以解出一个等效的key来解题，而不需要去解128位的key。
这个还是用z3即可

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 z3 import *

f=open('output.txt','r+')
fl=f.readlines()
for i in fl:
    i=i.strip()
    exec(i)

thash=shash
def shash(value,key):
    #assert type(value) == str
    #assert type(key) == int
    length = len(value)

    if length == 0:
        return 0
    mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    x = (ord(value[0]) << 7) & mask
    for c in value:
        x = (key * x) & mask ^ ord(c)

    x ^= length & mask

    return x

key=BitVec('key',20)
solver=Solver()

for i in range(1):
    solver.add(shash(testvalue[i],key)==testhash[i])
if solver.check()==sat:
    res=solver.model()
    print(res[key].as_long())

解出来key是1000001。
接下来可以参考这篇博客
hash——复现
构造相同的格，稍微调一下参数就可以了。

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
from Crypto.Util.number import *
th=463802484547898091835999726502006552543022358314700124374789687370275467670717610329
key=1000001

th=(th^^32)%2**280
#th=((th^^125)%2**280)*inverse(key,2**280)%2**280

len1=32
k1=2^50
k2=2^15
data=[]
data=[128*key^len1+key^(len1-1)]
data+=[key^i for i in range(len1-1)][::-1]
for i in range(len1):
    data[i]=data[i]%2**280
B=[[0]*(len1+2) for i in range(len1+2)]

for i in range(len1):
    B[i][i]=1
    B[i][-1]=data[i]
B[-2][-2]=k1
B[-2][-1]=-th
B[-1][-1]=2**280
B=Matrix(ZZ,B)
B[:,-1:] *= k2
B_=B.LLL()
#print(B_)
print(guass_Heuristic(B).bit_length(),int(iroot(2**256*len1+1,2)[0]).bit_length())
for j in B_:
    if j[-2]==k:
        print(j)
    if j[-2]==k and j[-1]==0:
        tmp=j[:-2]
        plain=b''
        c=th
        for i in range(len(tmp)):
            tmpc = (c - tmp[-i-1]) % 2^280
            s = (tmpc ^^ c)
            plain+=long_to_bytes(s)
            c = (c ^^ s) * inverse(key,2^280) % 2^280
        print(plain[::-1])

经过测试,k2在$2^{10}$ 到 $2^{15}$这个范围内更容易出。

1
miniL{W@!!_Y()o_get_T()@_SEcr@t}

Noisy

Damn, there’s just too much noise! Can we still get the flag back?

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
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from random import getrandbits, randint
from hashlib import md5


class Noisy_cipher:
    def __init__(self, params):
        self.nbits = params["nbits"]
        self.pbits = params["nbits"]//2
        self.Mbits = params["Mbits"]
        self.k0bits = params["k0bits"]
        self.k1bits = params["k1bits"]
        self.samples = params["samples"]
        self.p = getPrime(self.pbits)
        self.q = getPrime(self.nbits)
        self.n = self.p * self.q
        self.s = randint(0, self.n)
        self.M = getrandbits(self.Mbits)
        self.pubKey = [self.n]
        self.priKey = [self.s, self.p, self.M]
    
    
    def encrypt(self,msg):
        res = []
        for i in range(self.samples):
            k0 = getrandbits(self.k0bits)
            k1 = getrandbits(self.k1bits)
            ci = self.s * (msg[i] + k0*self.M)*(1 + k1*self.p) % self.n
            res.append(ci)
        
        return res


if __name__ == '__main__':
    params = {
        "nbits":1024,
        "Mbits":30,
        "k0bits":30,
        "k1bits":512,
        "samples":20,
    }
    mbits = 24
    Noise = Noisy_cipher(params)
    n = Noise.n
    msg = [getrandbits(mbits) for _ in range(params["samples"])]
    cipher = Noise.encrypt(msg)
    with open('secret.txt', 'r') as file:
        flag = file.readlines()[0].encode()
    file.close()
    key = md5(str(msg).encode()).digest()
    aes = AES.new(key, AES.MODE_ECB)
    encrypted_flag = aes.encrypt(pad(flag, 16)).hex()
    with open('output.txt', 'a') as file:
        file.write('n = ' + str(n) + '\n')
        file.write('c = ' + str(cipher) + '\n')
        file.write('encrypted_flag = "' + encrypted_flag + '"\n')
    file.close()

题目要求我们从$ci = self.s * (msg[i] + k0 * self.M) * (1 + k1 * self.p) % self.n$中恢复$msg[i]$。

复现ing…

2025.5.1miniLCTF
https://bddye.github.io/2025/06/01/2025-5-1miniLCTF/
作者
蹦跶的鱼儿
发布于
2025年6月1日
许可协议