2023ACTF

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 2.2k 阅读时长 ≈ 8 分钟

赛题很难，呜呜呜

MDH

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 = (sk_alice[0].T * pk_bob * sk_alice[1]).trace()

即$shared = (a_1^T \times b_1\times b_2^T \times a_2).trace()$

我们已知Pk_alice = $a_1\times a_2^T$和Pk_bob = $b_1\times b_2^T$

根据矩阵迹的性质$Tr(A) = Tr(A^T)$，$Tr(AB) = Tr(BA)$，参考：矩阵的迹(Trace)及相关性质证明_矩阵迹的性质及证明-CSDN博客

于是我们可以把shared改写成

$shared = (a_1^T\times a_2 \times b_1\times b_2^T).trace()$

即shared = (Pk_alice.T * Pk_bob).trace()

exp:

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

p = 308955606868885551120230861462612873078105583047156930179459717798715109629
Fq = GF(p)

f = open("output.txt",'r')
data = f.readlines()

ct = eval(data[0])
pk_alice = eval(data[1])
pk_bob = eval(data[2])

pk_alice = Matrix(Fp,pk_alice)
pk_bob = Matrix(Fq,pk_bob)

shared = (pk_alice.T * pk_bob).trace()

m = int(sha256(str(int(shared)).encode()).hexdigest(), 16) ^^ ct
flag = bytes.fromhex(hex(m)[2:])
print(flag)
# ACTF{do_you_know_f0rm2l1n_1s_4w3s0m3!}

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
116
117
118
119
120
#!/usr/bin/env python3
from Crypto.Util.number import (
    bytes_to_long, long_to_bytes
)
from hashlib import md5
import os, 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)
        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")

import hashlib
import os

def generate_proof_of_work(size,difficulty):
    target = os.urandom(size).hex()
    hash_value = hashlib.sha1(target.encode()).hexdigest()
    return target[difficulty:],hash_value

def check_proof_of_work(prefix,suffix,expected):
    return hashlib.sha1(f'{prefix}{suffix}'.encode()).hexdigest()==expected

def proof():
    POW_SIZE=32
    POW_DIFFICULTY=6
    suff,hs=generate_proof_of_work(POW_SIZE,POW_DIFFICULTY)
    print(f'sha1(prefix+"{suff}")=={hs}')
    pref=input("prefix = ?\n")
    if not check_proof_of_work(pref,suff,hs):
        print("PoW error")
        exit(1)

def main():
    signal.alarm(600)
    proof()
    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()

比赛中途加了个proof验证

首先是抓到娃娃，我们其实位置是(0,0)，根据它的位置，输入W和D就可以了

这题关键是让我们的得分达到2220

关键在于下面两段代码

1
2
3
4
5
6
7
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)
    if c=='0': return True
    else: return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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")

总之是要在$p,q$在一个范围内取值，然后让delta = r*q - p*2^128尽可能含有更多的0

于是想到固定$q = 2^{63}$，这样r*q就意味着把$r$左移动63位，于是低63位全都是0了

右边p*2^128意味着把$p$左移128位

我们可以令p等于r的第2位到第63位，这样保证delta的第一位是1

这样子delta中0的数目占了80%以上，我们得分的概率就有了80%

0

本地测试的时候把chaos默认为128bit的情况，但实际上chaos还有很多情况

对于chaos大小的测试（尽可能模拟了当时的情况）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import random
from Crypto.Util.number import *
import os, signal
from hashlib import md5

BITS = 128
seed = bytes_to_long(os.urandom(BITS//8))

def get_chaos(seed,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((seed + vs) % pow(2,BITS))).digest())
    seed = (seed + chaos + 1) % pow(2,BITS)
    return chaos
    

for _ in range(10):
    inp = "W" * random.randint(1,16) + "D" * random.randint(1,16)
    r = get_chaos(seed,inp)
    print(r.bit_length())

最后对chaos的不同大小， 对p进行不同处理，最后都要保证delta中的0尽可能多

处理方式是p = (r >> (65)) & ((1 << (r.bit_length() - 63 - 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
import random
from Crypto.Util.number import *
import os, signal
from hashlib import md5

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

BITS = 128
seed = bytes_to_long(os.urandom(BITS//8))

def get_chaos(seed,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((seed + vs) % pow(2,BITS))).digest())
    seed = (seed + chaos + 1) % pow(2,BITS)
    return chaos
    
    
for _ in range(100):
    scores = 0
    for i in range(256):
        inp = "W" * random.randint(1,16) + "D" * random.randint(1,16)
        r = get_chaos(seed,inp)
        q = 2 ** 63
        p = (r >> (65)) & ((1 << (r.bit_length() - 63 - 3)) - 1)
        delta = (r * q) - (p*(2**128))
        c = destiny_claw(delta)
        if c == True:
            scores += 10
    if scores >= 2220:
        print(scores)
        print("跑了"+str(_+1)+"次")
        break

比较难受的是，连靶机一直跑不到2220分，我的猜测是疏忽了未得分的时候，bless += 16

EasyRSA

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
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("p1 =", p1)
            break

    while True:
        d = getRandomNBitInteger(dbits)
        p2 = b * c * d + 1
        if isPrime(p2):
            # 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

参考论文：IJCSI-9-2-1-311-314.pdf

从上述代码可以提取到的信息是
$$
ed = k_1\phi(n_1) + 1
$$

$$
ed = k_2\phi(n_2) + 1
$$

$$
ed = k_3\phi(n_3) + 1
$$

把$\phi(n_i)$用$n_i-s_i$代替

则有
$$
ed - k_1n_1 = 1-k_1s_1
$$

$$
ed - k_2n_2 = 1-k_2s_2
$$

$$
ed - k_3n_3 = 1-k_3s_3
$$

构造格

$M = \sqrt{n_{max}}$，其实M取$\frac{nbits}{2}$即可

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

c = 
e = 
n1 = 
n2 = 
n3 = 


n = [n1,n2,n3]
M = isqrt(max(n))

Ge = [[M,e,e,e],
    [0,-n1,0,0],
    [0,0,-n2,0],
    [0,0,0,-n3]]

Ge = Matrix(ZZ,Ge)

dM = Ge.LLL()[0][0]
d = abs(dM) // M
m = pow(c,d,n1)
print(long_to_bytes(int(m)))
# ACTF{5FFC427B-F14F-DCA0-C425-675B149890C2}

MidRSA

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
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("p1 =", p1)
            break

    while True:
        d = getRandomNBitInteger(dbits)
        p2 = b * c * d + 1
        if isPrime(p2):
            # 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 = 0x240

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 = 598823083137858565473505718525815255620672892612784824187302545127574115000325539999824374357957135208478070797113625659118825530731575573239221853507638809719397849963861367352055486212696958923800593172417262351719477530809870735637329898331854130533160020420263724619225174940214193740379571953951059401685115164634005411478583529751890781498407518739069969017597521632392997743956791839564573371955246955738575593780508817401390102856295102225132502636316844
# e = 334726528702628887205076146544909357751287869200972341824248480332256143541098971600873722567713812425364296038771650383962046800505086167635487091757206238206029361844181642521606953049529231154613145553220809927001722518303114599682529196697410089598230645579658906203453435640824934159645602447676974027474924465177723434855318446073578465621382859962701578350462059764095163424218813852195709023435581237538699769359084386399099644884006684995755938605201771
# n1 = 621786427956510577894657745225233425730501124908354697121702414978035232119311662357181409283130180887720760732555757426221953950475736078765267856308595870951635246720750862259255389006679454647170476427262240270915881126875224574474706572728931213060252787326765271752969318854360970801540289807965575654629288558728966771231501959974533484678236051025940684114262451777094234017210230731492336480895879764397821363102224085859281971513276968559080593778873231
# n2 = 335133378611627373902246132362791381335635839627660359611198202073307340179794138179041524058800936207811546752188713855950891460382258433727589232119735602364790267515558352318957355100518427499530387075144776790492766973547088838586041648900788325902589777445641895775357091753360428198189998860317775077739054298868885308909495601041757108114540069950359802851809227248145281594107487276003206931533768902437356652676341735882783415106786497390475670647453821
# n3 = 220290953009399899705676642623181513318918775662713704923101352853965768389363281894663344270979715555659079125651553079702318700200824118622766698792556506368153467944348604006011828780474050012010677204862020009069971864222175380878120025727369117819196954091417740367068284457817961773989542151049465711430065838517386380261817772422927774945414543880659243592749932727798690742051285364898081188510009069286094647222933710799481899960520270189522155672272451

与上题不同之处在于，增大了$d$的大小，$d$从528bit增大到了576bit

$$
\begin{pmatrix}
d_{1h} & d_{2h} & d_{3h} & k_1 & k_2 & k_3 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 0 & 0 & e_12^{t} & 0 & 0 & 0\
0 & 1 & 0 & 0 & e_22^{t} & 0 & 0\
0 & 0 & 1 & 0 & 0 & e_32^t & 0\
0 & 0 & 0 & -n & 0 & 0 & 0\
0 & 0 & 0 & 0 & -n & 0 & 0\
0 & 0 & 0 & 0 & 0 & -n & 0\
0 & 0 & 0 & e_{1}d_{1l} & e_2d_{2l} & e_3d_{3l} & 1
\end{pmatrix}

\begin{pmatrix}
d_{1h} & d_{2h} & d_{3h} & 1+k_1s & 1+k_2s & 1+k_3 & 1
\end{pmatrix}
$$

-------------已经到底啦！-------------