2023ACTF

周末打了一下 ACTF，题目质量很高。总共 6 道题目做了 3 道，有一道卡着等后续复现。最近太累了，周末比赛，周内复现。。。🐭🐭 我啊，打 CTF 打的！

MDH

手快抢了个三血 hh

看到这道题第一反应是死去的线代开始攻击我，好在还有点印象，对于矩阵的迹来说，就是对角线元素的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from hashlib import sha256
from secret import flag

r = 128
c = 96
p = 308955606868885551120230861462612873078105583047156930179459717798715109629
Fp = GF(p)

def gen():
    a1 = random_matrix(Fp, r, c)
    a2 = random_matrix(Fp, r, c)
    A = a1 * a2.T
    return (a1, a2), A

sk_alice, pk_alice = gen()
sk_bob, pk_bob = gen()
shared = (sk_alice[0].T * pk_bob * sk_alice[1]).trace()
ct = int(sha256(str(int(shared)).encode()).hexdigest(), 16) ^^ int.from_bytes(flag, 'big')

with open('output.txt', 'wb') as f:
    f.write(str(ct).encode() + b'\n')
    f.write(str(list(pk_alice)).encode() + b'\n')
    f.write(str(list(pk_bob)).encode() + b'\n')

将shared的矩阵表示为\(a_1^T\cdot b_1\cdot b_2^T \cdot a_2\)

而题目已知\(PKA=a_1\cdot a_2^T,PKB=b_1\cdot b_2^T\)

对于迹的一个性质来说，若干向量相乘所得的方阵，改变其相乘顺序，矩阵的迹都应一致。

因此只需计算\(PKA^T\cdot PKB\)的迹即可。

1
2
3
4
5
6
7
8
9
10
11
12
from hashlib import sha256
from Crypto.Util.number import *
p = 308955606868885551120230861462612873078105583047156930179459717798715109629
Fp = GF(p)
pk_alice=matrix(Fp,pk_alice)
pk_bob=matrix(Fp,pk_bob)
tmp2=pk_alice*pk_bob.T
print(tmp2.trace())
shared = 229215835499100713048005195047655740191791862411327976508820034350300131774
ct = 8308943029741424587523612386337754255889681699670071706719724435165094611096603769021839263
flag = int(sha256(str(int(shared)).encode()).hexdigest(), 16) ^ ct
print(long_to_bytes(flag))

claw crane

题如其名，真牛魔抓娃娃

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
#!/usr/bin/env python3
from Crypto.Util.number import (
    bytes_to_long, long_to_bytes
)
from hashlib import md5
import os
import signal
import sys
import random

BITS = 128


class ClawCrane(object):
    def __init__(self) -> None:
        self.seed = bytes_to_long(os.urandom(BITS//8))
        self.bless = 0
        self.score = 0

    def get_input(self, prompt="> "):
        print(prompt, end="")
        sys.stdout.flush()
        return input()

    def check_pos(self, pos, moves):
        col, row = 0, 0
        for move in moves:
            if move == "W":
                if row < 15:
                    row += 1
            elif move == "S":
                if row > 0:
                    row -= 1
            elif move == "A":
                if col > 0:
                    col -= 1
            elif move == "D":
                if col < 15:
                    col += 1
            else:
                return -1
        print(col, row)
        return pos == [col, row]

    def gen_chaos(self, inp):
        def mapping(x):
            if x == 'W':
                return "0"
            if x == 'S':
                return "1"
            if x == 'A':
                return "2"
            if x == 'D':
                return "3"
        vs = int("".join(map(mapping, inp)), 4)
        chaos = bytes_to_long(md5(
            long_to_bytes((self.seed + vs) % pow(2, BITS))
        ).digest())
        self.seed = (self.seed + chaos + 1) % pow(2, BITS)
        return chaos

    def destiny_claw(self, delta):
        bits = bin(delta)[2:]
        if len(bits) < 128+self.bless:
            bits += "0"*(128+self.bless - len(bits))
        c = random.choice(bits)
        print(bits)
        if c == '0':
            return True
        else:
            return False

    def run(self):
        pos = [random.randrange(1, 16), random.randrange(1, 16)]
        moves = self.get_input(f"i am at {pos}, claw me.\nYour moves: ")
        if len(moves) > 100:
            print("too many steps")
            return
        if not self.check_pos(pos, moves):
            print("sorry, clawed nothing")
            return
        r = self.gen_chaos(moves[:64])
        print(f"choas: {r}")
        p, q = map(int, self.get_input(
            f"give me your claw using p,q and p,q in [0, 18446744073709551615] (e.g.: 1,1): ").split(","))
        if not (p > 0 and p < pow(2, BITS//2) and q > 0 and q < pow(2, BITS//2)):
            print("not in range")
            return
        delta = abs(r*q - p*pow(2, BITS))
        if self.destiny_claw(delta):
            self.score += 10
            self.bless = 0
            print("you clawed it")
        else:
            self.bless += 16
            print("sorry, clawed nothing")


def main():
    signal.alarm(600)
    cc = ClawCrane()
    for _ in range(256):
        try:
            cc.run()
            print(f"your score: {cc.score}")
        except:
            print(f"abort")
            break
    if cc.score >= 2220:
        print(f"flag: {open('/flag.txt').read()}")


if __name__ == "__main__":
    main()

总之就是要在你构造出的 128 位数当中随机选择选到 0 才会加分，256 次中需要正确 220 次，因此就想方设法让数字的 2 进制 0 多一些，delta = abs(r * q - p * pow(2, 128))，r 已知，需要我们传入 p、q，由于\(p\cdot 2^{128}\)相当于左移 128 位，因此我们也要让 rq 的低位尽可能也为 0，q 不能超过 2^64 次方，因此 q 的取值可以为\(2^{63},2^{63}+2^{62},2^{62}......\) 对于给定的 r 和 q 计算一个 p 值，在多组当中进行 delta 中 0 个数的计算，选择 0 个数最高的一组 p、q 发送，分数可以稳定在 2000 以上，运气好一会就出了。

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
from pwn import *

# context.log_level = 'debug'
round1=0
score=0

def check(delta):
    nums=0
    bits = str(bin(delta)[2:])
    for i in range(len(bits)):
        if bits[i]=='0':
            nums+=1
    return nums

while 1:
    round1+=1
    io = remote('120.46.65.156', 19991)
    count=0
    print(round1)
    print(score)
    while 1:
        try:
            tmp=io.recvuntil(b'],')
            # print(tmp)
            pos=eval(tmp[8:-1])
            # print(pos)
            io.recvuntil(b'moves: ')
            pay=pos[0]*'D'+pos[1]*'W'
            io.sendline(pay.encode())
            # print(io.recv())
            io.recvline()
            r=int(io.recvline()[7:-1].decode())
            # print(r)
            io.recvuntil(b'1,1): ')
            # 初始化变量
            max_re = -1
            best_p = -1
            best_q = -1

            # 循环生成 q 和 p 的组合，计算 delta 和 re
            for i in range(1,512):
                q = 0
                if i & 1:
                    q += 2 ** 55
                if i & 2:
                    q += 2 ** 56
                if i & 4:
                    q += 2 ** 57
                if i & 8:
                    q += 2 ** 58
                if i & 16:
                    q += 2 ** 59
                if i & 32:
                    q += 2 ** 60
                if i & 64:
                    q += 2 ** 61
                if i & 128:
                    q += 2 ** 62
                if i & 256:
                    q += 2 ** 63


                p = (r * q) // (2 ** 128)
                delta = abs(r * q - p * pow(2, 128))
                re0 = check(delta)

                if re0 > max_re:
                    max_re = re0
                    best_p = p
                    best_q = q

            io.sendline((str(best_p)+','+str(best_q)).encode())
            io.recvline()
            tmp=io.recvline()
            score=int(tmp[12:-1])
            count+=1
        except:
            break
    if count>=256:
        print(io.recv())
        break

Easy RSA

题目

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

def genKey(nbits, dbits):
    bbits = (nbits // 2 - dbits) // 2

    while True:
        a = getRandomNBitInteger(dbits)
        b = getRandomNBitInteger(bbits)
        c = getRandomNBitInteger(bbits)
        p1 = a * b * c + 1
        if isPrime(p1):
            print(a)
            print("p1 =", p1)
            break

    while True:
        d = getRandomNBitInteger(dbits)
        p2 = b * c * d + 1
        if isPrime(p2):
            print(d)
            print("p2 =", p2)
            break

    while True:
        e = getRandomNBitInteger(bbits)
        f = getRandomNBitInteger(bbits)
        q1 = e * d * f + 1
        p3 = a * e * f + 1
        if isPrime(q1) and isPrime(p3):
            print("p3 =", p3)
            print("q1 =", q1)
            break

    while True:
        d_ = getRandomNBitInteger(dbits)
        if GCD(a * b * c * d * e * f, d_) != 1:
            continue
        e_ = inverse(d_, a * b * c * d * e * f)
        k1 = (e_ * d_ - 1) // (a * b * c * d * e * f)
        assert e_ * d_ == (a * b * c * d * e * f) * k1 + 1
        q2 = k1 * e * f + 1
        q3 = k1 * b * c + 1
        if isPrime(q2) and isPrime(q3):
            print("q2 =", q2)
            print("q3 =", q3)
            print("e =", e_)
            print("d =", d_)
            break

    n1 = p1 * q1
    n2 = p2 * q2
    n3 = p3 * q3

    assert pow(pow(0xdeadbeef, e_, n1), d_, n1) == 0xdeadbeef
    assert pow(pow(0xdeadbeef, e_, n2), d_, n2) == 0xdeadbeef
    assert pow(pow(0xdeadbeef, e_, n3), d_, n3) == 0xdeadbeef

    return (e_, n1, n2, n3)


nbits = 0x600
dbits = 0x210

m = bytes_to_long(flag)
e, n1, n2, n3 = genKey(nbits, dbits)
c = pow(m, e, n1)

print("c =", c)
print("e =", e)
print("n1 =", n1)
print("n2 =", n2)
print("n3 =", n3)

# c = 63442255298812942222810837512019302954917822996915527697525497640413662503768308023517128481053593562877494934841788054865410798751447333551319775025362132176942795107214528962480350398519459474033659025815248579631003928932688495682277210240277909527931445899728273182691941548330126199931886748296031014210795428593631253184315074234352536885430181103986084755140024577780815130067722355861473639612699372152970688687877075365330095265612016350599320999156644
# e = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227
# n1 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201
# n2 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181
# n3 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421

关键信息

1
2
3
assert pow(pow(0xdeadbeef, e_, n1), d_, n1) == 0xdeadbeef
assert pow(pow(0xdeadbeef, e_, n2), d_, n2) == 0xdeadbeef
assert pow(pow(0xdeadbeef, e_, n3), d_, n3) == 0xdeadbeef

说明了这一组e_,d_满足三个模数 n，相当于已知三组 n、e，对于题目所限制的 d 的位数，刚好满足造格的情况

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

c =
e =
n1 =
n2 =
n3 =
t = 3
N = [n1, n2, n3]
e = [e, e, e]
B = Matrix(ZZ, t+1, t+1)
M = gmpy2.iroot(int(N[t-1]), int(2))[0]
B[0, 0] = M
for i in range(1, t+1):
    B[i, i] = -N[i-1]
    B[0, i] = e[i-1]
Blll = B.LLL()
d = int(abs(Blll[0][0]//M))
print(long_to_bytes(pow(c, d, n1)))

Review

此部分在阅读其余队伍 wp 后的复盘，对于上题，格的具体构造思路描述如下：

\[ \begin{aligned} ED -k_1N_1 &= 1+k_1x_1 \\ ED -aN_2 &= 1+ax_2 \\ ED -dN_3 &= 1+dx_3 \end{aligned} \]

构造格:

\[ \begin{bmatrix} 2^{767} & E &E&E\\ 0 & -N_1 &0&0\\ 0 & 0 &-N_2&0\\ 0 & 0 &0&-N_3\\ \end{bmatrix} \]

Mid RSA(赛后复现)

与 Easy 不同的地方在于将 d 位数提高，原本的格无法规约出来，当时调格子调吐了，但是真没想到本地生成一组数和上一题对比一下，上题的格子拿过来只是差了几位低位。。。

1
2
nbits = 0x600
dbits = 0x240

对于

\[ \begin{aligned} e(d_h\times2^{16}+d_l) -1 &= k_1\phi(N_1) \\ e(d_h\times2^{16}+d_l) -1 &= k_2\phi(N_2) \\ e(d_h\times2^{16}+d_l) -1 &= k_3\phi(N_3) \end{aligned} \]

有

\[ \begin{aligned} e2^{16}d_h+ed_l -k_1N_1 &= 1+k_1s_1 \\ e2^{16}d_h+ed_l -k_2N_2 &= 1+k_2s_2 \\ e2^{16}d_h+ed_l -k_3N_3 &= 1+k_3s_3 \end{aligned} \]

构造格:

\[ \begin{bmatrix} 1 & e2^{16} &e2^{16}&e2^{16}&0\\ 0 & -N_1 &0&0&0\\ 0 & 0 &-N_2&0&0\\ 0 & 0 &0&-N_3&0\\ 0 & ed_l&ed_l&ed_l&1\\ \end{bmatrix} \]

构造方法参考星盟 0HB 师傅，至于为何是低位 16 位，师傅给出的解释是，本地测了一组数据，发现用上一题的格子跑出来相差了 16 位，但具体相差多少还需要具体研究，由于 16 位已足够爆破，因此公式中写为了 16 次方。

经本人测试，对于本题的 d 缺失了 7 位。

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
from tqdm import tqdm
from Crypto.Util.number import *
c = 598823083137858565473505718525815255620672892612784824187302545127574115000325539999824374357957135208478070797113625659118825530731575573239221853507638809719397849963861367352055486212696958923800593172417262351719477530809870735637329898331854130533160020420263724619225174940214193740379571953951059401685115164634005411478583529751890781498407518739069969017597521632392997743956791839564573371955246955738575593780508817401390102856295102225132502636316844
e = 334726528702628887205076146544909357751287869200972341824248480332256143541098971600873722567713812425364296038771650383962046800505086167635487091757206238206029361844181642521606953049529231154613145553220809927001722518303114599682529196697410089598230645579658906203453435640824934159645602447676974027474924465177723434855318446073578465621382859962701578350462059764095163424218813852195709023435581237538699769359084386399099644884006684995755938605201771
n1 = 621786427956510577894657745225233425730501124908354697121702414978035232119311662357181409283130180887720760732555757426221953950475736078765267856308595870951635246720750862259255389006679454647170476427262240270915881126875224574474706572728931213060252787326765271752969318854360970801540289807965575654629288558728966771231501959974533484678236051025940684114262451777094234017210230731492336480895879764397821363102224085859281971513276968559080593778873231
n2 = 335133378611627373902246132362791381335635839627660359611198202073307340179794138179041524058800936207811546752188713855950891460382258433727589232119735602364790267515558352318957355100518427499530387075144776790492766973547088838586041648900788325902589777445641895775357091753360428198189998860317775077739054298868885308909495601041757108114540069950359802851809227248145281594107487276003206931533768902437356652676341735882783415106786497390475670647453821
n3 = 220290953009399899705676642623181513318918775662713704923101352853965768389363281894663344270979715555659079125651553079702318700200824118622766698792556506368153467944348604006011828780474050012010677204862020009069971864222175380878120025727369117819196954091417740367068284457817961773989542151049465711430065838517386380261817772422927774945414543880659243592749932727798690742051285364898081188510009069286094647222933710799481899960520270189522155672272451
N = [n1, n2, n3]
e = [e, e, e]
t = 4
lowbits = 7

for dl in tqdm(range(2 ^ lowbits)):
    B = Matrix(ZZ, t+1, t+1)
    B[0, 0] = 2 ^ (767+lowbits)
    B[t, t] = 2 ^ (767+576)
    for i in range(1, t):
        B[i, i] = N[i-1]
        B[0, i] = e[i-1]*2 ^ lowbits
        B[t, i] = e[i-1]*dl

    Mat_LLL = B.LLL()

    for line in Mat_LLL:
        dh = abs(line[0])//2 ^ (lowbits+767)
        d = int((dh << lowbits)+dl)

        m = int(pow(c, d, n1))
        flag1 = long_to_bytes(m)
        if b'ACTF{' in flag1:
            print(flag1)
            break

CTF
2023ACTF
https://sch01ar.github.io/2023/10/30/2023ACTF/
作者
Roo1e
发布于
2023年10月30日
许可协议