糖醋小鸡块的blog
0%

2023-ACTF-wp-crypto

发表于 更新于 分类于 Valine：

*代表赛中未解出的题目，最后一道待复现。

EasyRSA

题目描述：

1
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

题目给了三组n，其关系如下：

其中，各参数的数量级约为：

并且有如下关系式：

其中d’是指解密所用的私钥，数量级也为538比特，注意与前一个d区分。

然后，题目将flag用e与n1加密，给出密文，要求我们还原明文。而很容易知道，如果我们能够拥有n1的分解，或者直接求出解密密钥d’，都可以求出flag。

看到这些参数应该自然会想到连分数，比如有：

因此期望是从n2/n3的连分数展开后得到a、d，然后用二元copper解出n的分解。

但是实际验证之后会发现，d/a并不是n2/n3的收敛子，这一点也可以用勒让德定理验证得到。那么就得换思路。由题目知道以下式子：

可以发现这其实也是一种共私钥攻击，我们采取以下推导，最终构造出格。

首先由于没有phi，只有n，因此先展开式子：

由这几个关系式出发，我们可以构造如下格：

这个格具有如下关系式：

其中，K是为了使规约出的向量中每个值数量级相当而配的系数，其实也就约为nbits/2。如此一来对该格进行规约就能得到私钥d’，从而解密密文。其实这也就是共私钥攻击的规约过程。

exp：

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 *

nbits = 0x600
dbits = 0x210
c = 63442255298812942222810837512019302954917822996915527697525497640413662503768308023517128481053593562877494934841788054865410798751447333551319775025362132176942795107214528962480350398519459474033659025815248579631003928932688495682277210240277909527931445899728273182691941548330126199931886748296031014210795428593631253184315074234352536885430181103986084755140024577780815130067722355861473639612699372152970688687877075365330095265612016350599320999156644
e = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227
n1 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201
n2 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181
n3 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421

K = 2^(nbits//2)
L = matrix(ZZ,4,4)
L[0]=[K,e,e,e]
L[1]=[0,-n1,0,0]
L[2]=[0,0,-n2,0]
L[3]=[0,0,0,-n3]

res=L.LLL()[0]
d = abs(res[0])//K

print(long_to_bytes(int(pow(c,d,n1))))

#ACTF{5FFC427B-F14F-DCA0-C425-675B149890C2}



MDH

题目描述：

1
Malin’s Diffile-Hellman Key Exchange.

题目：

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

复习一下矩阵trace的性质就好了。

exp：

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

p = 308955606868885551120230861462612873078105583047156930179459717798715109629
c = 8308943029741424587523612386337754255889681699670071706719724435165094611096603769021839263
A = 
B = 

A = matrix(GF(p),A)
B = matrix(GF(p),B)
A = A.transpose()

shared = (A*B).trace()
m = c ^^ int(sha256(str(int(shared)).encode()).hexdigest(), 16)
print(long_to_bytes(m))

#ACTF{do_you_know_f0rm2l1n_1s_4w3s0m3!}



*claw crane

题目描述：

1
抓娃娃咯 / Grabbing Dolls

题目：

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()

简单说一下题目任务：

  • 连接上靶机后，计时600s开始。先通过proof，然后初始化一个随机数种子seed
  • 有256次交互机会，交互成功得10分，否则不得分
  • 交互成功次数大于等于222次，得到flag

然后交互成功在本题中的含义为：

  • 首先，每次随机生成一个娃娃的坐标，需要先输入一段move序列使其移动到对应地方
  • 然后用该段move序列与seed做一定计算后得到一个值chaos并返回，同时更新seed。由于chaos的计算是md5得到，因此可以看作是一个完全随机的数
  • 输入q、p，要求q、p的范围在(1,2^64)之间，然后计算：
  • 对于计算得到的delta，服务器先判断其是否小于128比特，如果小于，则填充0至满128比特；否则不填充
  • 从delta对应的二进制串中随机抽取，抽到0则交互成功，得到10分；抽到1则不得分

接下来讲我的几个尝试：

尝试一

首先能看出，要尽量得到更多的分数，就需要使delta中0的数量尽可能多，而由于靶机会对其进行0的填充，因此第一个想法很自然：使delta尽可能小，就可以填充更多的0。

那么自然就会想到LLL来规约出短向量，我们构造如下的格：

很显然这个格具有如下线性关系：

而这样规约出的q、p可以说刚好落在题目要求区间内，而delta大概为64比特的数量级，因此可以认为平均会填充64比特0，而把delta的前64比特近似看作是均匀的分布的话，那么靶机端抽取0的概率大约是四分之三左右。

而其实我们可以把256次的完整交互过程抽象为一个二项分布，那么我们可以计算一下这个二项分布实验中，成功222次及以上的概率。有个现成的计算器可以使用：

二项分布在线计算,在线计算,在线计算器,计算器在线计算 (osgeo.cn)

可以计算出成功率约为十万分之一，而由生日攻击的理论可以知道，我们如果能完整的交互十万次，就有大于50%的概率至少成功一次。

然而，由于有格的计算，加上本身一次交互就需要一定时间，一分钟其实最多就交互个两三次，因此交互十万次基本是不可能的。并且赛中为了防止生日攻击，还特意加上了proof_of_work，所以我们需要想一想办法，压缩交互时间，并且提高delta中0的概率。

尝试二

其实细想一下就会发现，思路一有一个很明显的不等价关系：

delta中0的个数占比尽量多，不等价于delta尽量小

而如果开始就想到了格，基本很难从这个思路中跳出去了。那么又能怎么样让delta中0的个数多一点呢？其实也比较容易就可以想到这样的q、p：

而为什么这样0的数量也不少呢？因为其实乘2的k次方等价于移位操作，也就是说，现在的delta：

那么显然delta低位也全是0，不过这样delta会超过128比特，仍然近似的看的话，这样抽中0的概率其实只有三分之二，反而是降低了，不过由于没有格的规约过程，速度肯定变快了，但是仍然几乎不可能成功222次以上。

尝试三

但是想到尝试二，基本离成功不远了。

先看看尝试二的缺点，他仅仅利用了q使r移位，却没有利用上p，而p显然是可以有作用的。比如，我们取p为r的高位部分(从第二位开始取，这样能保证delta的数量级依然是190比特左右)，那么这个时候的delta：

因此可以把r的高位部分也对应消掉，这样就只剩中间一部分还有1了，而此时我们每一次的成功概率就达到了六分之五，用二项分布计算出每一次成功概率就有0.057019，而由生日攻击知道，我们只需要完整交互不到20次，就有大概率得到结果了。

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


#context.log_level = 'debug'

def proof_of_work():
    table = "0123456789abcdef"
    temp = sh.recvuntil(b"sha1(prefix+")
    temp = sh.recvline().strip().decode()
    suffix = temp[1:59]
    hex1 = temp[-40:]
    for i in tqdm(table):
        for j in table:
            for k in table:
                for m in table:
                    for o in table:
                        for p in table:
                            temp1 = i+j+k+m+o+p
                            if(sha1((temp1+suffix).encode()).hexdigest() == hex1):
                                sh.sendline(temp1.encode())
                                return
					
average = 0
count = 0
while(1):
    count += 1
    K = 2**128
    #sh = remote("120.46.65.156",19991)
    sh = remote("152.136.172.227",22222)
    proof_of_work()

    for i in trange(256):
        sh.recvuntil(b" am at ")
        pos = eval(sh.recvline().strip().decode().split("]")[0][1:])
        move = b"W" * 15 + b"S" * 15 + b"W" * pos[1] + b"D" * pos[0]
        sh.sendline(move)
        sh.recvuntil(b"choas: ")
        r = int(sh.recvline().strip().decode())
        q = 2**63
        shift = len(bin(r)[2:]) - 65 - 1
        p = (r >> 65) &((1<<shift)-1)
        sh.recvuntil(b"(e.g.: 1,1):")
        sh.sendline(str(p).encode() + b"," + str(q).encode())
        sh.recvline()
    temp = sh.recvline().strip().decode()
    average += int(temp[-4:])
    print(temp,"average =",average // count)
    if("22" in temp):
        print(sh.recvline().strip().decode())
        break
    sh.close()

#ACTF{C0Nt1nu3d_Fract1on&Mor3_zer0s&Replay_it}

一些补充

赛后经过师傅提醒，其实仔细一点看代码的话，可以发现每次随机生成娃娃机的坐标后，我们是先输入一段move序列，做完娃娃机移动，然后才取move的前64个去进行chaos的运算。也就是说，前64个move输入是我们可以随意控制的。我们也就能够通过控制move的前64个，来保持chaos不变，从而先刷出一组delta0含量最高的，再进行完整256次交互，就可以更大概率得到高分了(不太理解如何控制chaos不变的师傅可以问我)。



*MidRSA

题目描述：

1
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

相比EasyRSA一题，这一题唯一的改变就是d的比特数增加了48，而也正如想象的一样，这样增加过后，我们刚才的格无法直接规约出来了。

而之所以无法规约出来，直观的感觉就是规约后的最短向量由于d的比特变大而变长了，而我们构造的格却并没有什么变化。更进一步的讲，我们构造的格和目标向量的关系不再满足高斯启发式。

有关高斯启发式可以参考这篇：

【精选】高斯启发式Gaussian Heuristic 格理论相关知识-CSDN博客

这里我们提出最核心的部分：

image-20231101224740836

也就是说，对于一个构造好的格，我们可以计算他的高斯启发式的近似，来大概知道其最短向量应该小于什么数量级。比如说，我们对于第一题的格，按如下方式计算其高斯启发式的近似值：

1
2
3
4
5
6
def guass_Heuristic(L):
    n = L.nrows()
    efficient = (n/(2*math.pi*math.e))**(0.5)
    return int(efficient*iroot(abs(L.det()),n)[0])

print(guass_Heuristic(L).bit_length())

可以得到约为1342比特。

而我们已知第一题的目标向量中的四个值数量级均为(nbits//2 + dbits)，约为1296左右，所以自然可以规约出这个短向量。

而第二题中，我们用同样的方法，计算其高斯启发式，计算出约为1341比特。这也很容易想清楚，因为构造的这个行列式的数量级只与n的比特有关，所以基本不变。然而，由于d的比特增大了，我们的目标向量的数量级经计算达到了1344比特，可以看出，我们的界被卡了。也就是说，我们的数量级不再满足高斯启发式近似，所以继续使用这个格而不进行改变的话，我们没有办法规约出目标向量。

那么怎么修改格呢？由于我们的目标向量基本不会有大变化，因此我们要从增大格的高斯启发式近似入手，所以我们可以考虑爆破d的一部分比特，如下：

仍然由关系式：

展开得：

把待爆破的低位dl单独写出，就能造出以下格：

其中t为dbits + (nbits/2)，仍然是为了使规约出的格数量级相当，这个格具有如下关系式：

ti的具体含义参考EasyRSA。

而经过计算与测试，爆破14比特的话，我们的高斯启发式能达到1345比特，就超过了我们目标向量的长度，因此我们就能规约出dh了，对应相加dl就有完整的d用于解密。当然，这些计算都是基于数量级的近似，实际上我们需要的是一个数值，所以爆破更多位，理论上来说高斯启发式会更大，也就会更容易规约出目标向量。但是耗时也会越久。

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

nbits = 0x600
dbits = 0x240

c = 598823083137858565473505718525815255620672892612784824187302545127574115000325539999824374357957135208478070797113625659118825530731575573239221853507638809719397849963861367352055486212696958923800593172417262351719477530809870735637329898331854130533160020420263724619225174940214193740379571953951059401685115164634005411478583529751890781498407518739069969017597521632392997743956791839564573371955246955738575593780508817401390102856295102225132502636316844
e = 334726528702628887205076146544909357751287869200972341824248480332256143541098971600873722567713812425364296038771650383962046800505086167635487091757206238206029361844181642521606953049529231154613145553220809927001722518303114599682529196697410089598230645579658906203453435640824934159645602447676974027474924465177723434855318446073578465621382859962701578350462059764095163424218813852195709023435581237538699769359084386399099644884006684995755938605201771
n1 = 621786427956510577894657745225233425730501124908354697121702414978035232119311662357181409283130180887720760732555757426221953950475736078765267856308595870951635246720750862259255389006679454647170476427262240270915881126875224574474706572728931213060252787326765271752969318854360970801540289807965575654629288558728966771231501959974533484678236051025940684114262451777094234017210230731492336480895879764397821363102224085859281971513276968559080593778873231
n2 = 335133378611627373902246132362791381335635839627660359611198202073307340179794138179041524058800936207811546752188713855950891460382258433727589232119735602364790267515558352318957355100518427499530387075144776790492766973547088838586041648900788325902589777445641895775357091753360428198189998860317775077739054298868885308909495601041757108114540069950359802851809227248145281594107487276003206931533768902437356652676341735882783415106786497390475670647453821
n3 = 220290953009399899705676642623181513318918775662713704923101352853965768389363281894663344270979715555659079125651553079702318700200824118622766698792556506368153467944348604006011828780474050012010677204862020009069971864222175380878120025727369117819196954091417740367068284457817961773989542151049465711430065838517386380261817772422927774945414543880659243592749932727798690742051285364898081188510009069286094647222933710799481899960520270189522155672272451

K = 2^(nbits//2)
L = matrix(ZZ,5,5)
shift = 2^16
for dl in trange(shift):
    L[0]=[K*shift,shift*e,shift*e,shift*e,0          ]
    L[1]=[0      ,-n1    ,0      ,0      ,0          ]
    L[2]=[0      ,0      ,-n2    ,0      ,0          ]
    L[3]=[0      ,0      ,0      ,-n3    ,0          ]
    L[4]=[0      ,e*dl   ,e*dl   ,e*dl   ,K*(2^dbits)]

    res=L.LLL()[0]
    if(res[0] > 0):
        d = abs(res[0])//K + dl
    else:
        d = abs(res[0])//K - dl

    flag = long_to_bytes(int(pow(c,d,n1)))
    if(b"ACTF" in flag):
        print(flag)

#ACTF{D16C46D9-77A2-2D96-CA51-4538EFB6AFF7}



*CRCRC

题目描述：

1
No desCRCiption

题目：

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

def crc128(data, poly = 0x883ddfe55bba9af41f47bd6e0b0d8f8f):
    crc = (1 << 128) - 1
    for b in data:
        crc ^= b
        for _ in range(8):
            crc = (crc >> 1) ^ (poly & -(crc & 1))
    return crc ^ ((1 << 128) - 1)

with open('./flag.txt','r') as f:
    flag = f.readline()

YourInput = input().encode()
YourDecode = b64decode(YourInput, validate=True)

print(len(YourDecode))

assert len(YourDecode) <= 127 and YourDecode.startswith(b'Dear guest, welcome to CRCRC Magic House, If you input ') and YourDecode.endswith(b", you will get 0x9c6a11fbc0e97b1fff5844fa88b1ee2d")

YourCRC = crc128(YourInput)
print(hex(YourCRC))

if(YourCRC) == 0x9c6a11fbc0e97b1fff5844fa88b1ee2d:
    print(flag)

在查找了很多资料，以及认识的师傅的大力帮助下，总算是把这题搞明白了大概。接下来我就用我的语言阐述一下我对这道题目的理解，可能会有不是很严谨的地方，如果有错误欢迎各位师傅指出。

主要参考：

ACTF2023 Cypto-CSDN博客

HackerGame 2022 出题记 | tl2cents blog

那么首先弄清楚题目任务，其实描述也很简单，其实就是输入一串base64，使其满足以下要求：

  • base64解密后，长度小于等于127，且前缀与后缀要是给定的一段文本
  • 该base64进行CRC128加密后的值需要是0x9c6a11fbc0e97b1fff5844fa88b1ee2d

如果我们输入的base64串能满足这两个要求，就能得到flag。那么精简一下，问题其实就是：

如何寻找一个字符均在base64码表中的CRC值原像？

我在接下来会把这个问题拆分为两个问题分别解释：如何由CRC值求解明文？如何求解限定范围内的明文？

由CRC值反解明文

从不可加密的异世界的wp中，可以知道CRC128的一个很重要的特殊性质：如果明文的差分固定，那么CRC加密得到的密文的差分也是固定的。在这里，我们将差分定义为两个值的异或值，比如a和b的差分为：

那么刚才所说的差分固定的意思，用表达式写出就是：

也就是说，对于任意的a、b，只要a与b的差分相同，那么两者分别CRC加密后，得到的密文差分也相同。那么这一点对我们反解CRC有什么帮助呢？

我们假设a的比特长度为l，那么不妨将上式的b取为，也就是与a长度相同的全0比特串，代入刚才的式子就有：

那么朴素的想法是：如果我们能建立所有长度为l的比特串a的差分对照表，我们就能很轻松的解出a。举个简单的例子，如果l=2，我们就可以分别计算00,01,10,11与00的差分与CRC值，从而建立一个差分对照表：

有了完整的差分对照表后，如果我们获得一个CRC(a)值，想要获取a，就很简单。我们只需要计算CRC(a)与CRC(0^l)的差分delta’，然后查表找到对应明文差分delta，其实也就是a了。

但是同时也可以想到，这只能在l较小时实现。而假如我们输入的a是128比特，那我们想要建立完整的差分对照表，就需要计算2^128种情况，显然是不可能的，这时候就需要想别的办法。

而注意到CRC128其实都是线性操作，那么我们只要用l组基向量的组合，就可以表示出所有的长度为l的向量。

也就是说，假设我们需要输入的a是l比特，我们就可以用如下的l组标准正交基向量，来张成所有a：

而我们把这每组基向量也视为明文，求出他们的差分delta’：

那么我们也能得到l组计算差分后的基向量，可以想到，这个差分后的基向量也能张成一个空间，而这两个空间其实就形成了我们需要的差分对照表，只是现在变成矩阵表示如下：

其中，M就是我们计算得到的所有差分基向量组成的矩阵，a是我们需要求解的长度为l的明文，，右侧是我们已知的向量。所以我们求解矩阵方程，就能求出给定CRC值的一个解向量a。

这一部分内容的具体实现如下，是不可加密的异世界的wp中的代码：

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
def crc128(data, poly=0x883ddfe55bba9af41f47bd6e0b0d8f8f):
    crc = (1 << 128) - 1
    for b in data:
        crc ^^= b
        for _ in range(8):
            crc = (crc >> 1) ^^ (poly & -(crc & 1))
    return crc ^^ ((1 << 128) - 1)

def equivalent_affine_crc(crc = crc128, crc_bits = 128, target_bytes = 16):
    zero_crc = crc(target_bytes*b"\x00")
    target_bits = 8 * target_bytes
    v2n = lambda v: int(''.join(map(str, v)), 2)
    n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(crc_bits))
    # n2v_t = lambda n: vector(GF(2), bin(n)[2:].zfill(target_bits))
    Affine_Matrix = []
    for i in range(target_bits):
        v = vector(GF(2), (j == i for j in range(target_bits)))
        value = crc(long_to_bytes(v2n(v),target_bytes)) ^^ zero_crc
        Affine_Matrix.append(n2v(value))
    # crc affine function: crc_128(x) = M*x+ C
    return matrix(GF(2),Affine_Matrix).transpose(), n2v(zero_crc)

def crc_128_reverse(crc_value):
    M , C = equivalent_affine_crc()
    # crc affine function: crc_128(x) = M*x+ C
    v2n = lambda v: int(''.join(map(str, v)), 2)
    n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(128))
    res = M.solve_right(n2v(crc_value)+C)
    return long_to_bytes(v2n(res),16)

而看wp也能知道，这部分其实被集成在了一个python包里，只需要一个没有限制的解的话，直接调用即可：

crcsolver · PyPI

限制明文在指定范围内

而题目要求我们解出的明文均为base64码表内的字符，相当于加了一个限制条件。而无论是直接掉包，还是用刚才的代码解矩阵，都只能得到一个特解。

因此，我们需要限制解空间，并用矩阵的右核M去与特解做组合，从而找到符合要求的解。具体来说，既然我们需要解出的明文是base64字符，而大小写字母都在base64字符表内，且ASCII码的二进制开头均为01，那么我们就可以根据这个限制解空间。接下来就继续详细说下怎么限制。

首先，我们要尽可能让我们的解空间大一点，才能找到符合要求的解。而由于解码后长度要小于等于127，并且前后缀已经有55+49=104的长度，我们能在中间填充的base64其实计算出来最多也只能有30个字符。因此，先假定我们就取30个字符，也就是240比特，对应来说就是240个GF(2)上的变量。把这240个变量组成的向量称为x，然后首先由关系式：

我们把右边的向量记作是C向量，其长度为128，也就是：

而由于我们想要限制30个字节的前2比特，因此我们给M加上30*2行，每行在对应比特处置1，其余置0。相应的，C也就要加上60行，分别是01、01、……

如此一来矩阵就变化成了：

我们用如下函数求出一组特解：

1
x = M.solve_right(C)

用如下函数求出M的右核空间(也就是使得Mv=0的所有向量v的集合，可以想到v+x也都是矩阵方程的解)：

1
basis = M.right_kernel()

然后与通解分别组合，并用正则表达式判断是否有符合要求的解出现：

1
re.fullmatch(b'[A-Za-z0-9+/]*', s)

由此就可以求出一组符合要求的解了。

最终求解

但是，虽然解决了主要问题，但是仍然有一个地方还不太清楚，那就是：我们得到的CRC值是完整的base64串的CRC，而不是我们填充部分单独的CRC，因此我们其实还没有需要求解的方程的C以及M，那么怎么办呢？

这个部分我仍然是是参考了这篇：ACTF2023 Cypto-CSDN博客，具体一点讲，观察crc128的函数本身：

1
2
3
4
5
6
7
def crc128(data, poly = 0x883ddfe55bba9af41f47bd6e0b0d8f8f):
    crc = (1 << 128) - 1
    for b in data:
        crc ^= b
        for _ in range(8):
            crc = (crc >> 1) ^ (poly & -(crc & 1))
    return crc ^ ((1 << 128) - 1)

可以看到，他是逐字节的线性操作，并且有了明文的话，整个过程其实可逆。而观察完整的base64串的形式：

image-20231031200220840

我们期望获得1、2处的CRC对应值，从而我们可以将1处的值作为填充部分加密的起点，将2处的值作为填充部分加密后得到的CRC值。如此一来我们就能建立M矩阵、得到C向量，从而求解符合要求的x。而得到这两部分的值是容易的：要得到1处的值，只需要对base64前缀进行CRC加密；要得到2处的值，只需要将给定的最终CRC值与base64做一遍CRC逆操作就行。如此我们就可以矩阵方程得到需要的满足要求的填充了。

同时，在求解过程中会注意到，如果我们真的取30个字节，虽然解空间变大了，但是M的右核空间也变得很大，这样较难组合出一组解。而考虑到base64的解密过程，我们要想减少填充字节数，就要4字节4字节的减少，因此我们将待求的x定为26个字节，这样就能很快组合出一组符合要求的解了。

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

def crc128(data, poly = 0x883ddfe55bba9af41f47bd6e0b0d8f8f):
    crc = (1 << 128) - 1
    for b in data:
        crc ^^= b
        for _ in range(8):
            crc = (crc >> 1) ^^ (poly & -(crc & 1))
    return crc

def re_crc128(data, crc, poly = 0x883ddfe55bba9af41f47bd6e0b0d8f8f):
    crc = crc ^^ ((1 << 128) - 1)
    for b in data[::-1]:
        for _ in range(8):
            if len(bin(crc)[2:]) < 128:
                crc = crc << 1
            else :
                crc = ((crc ^^ poly) << 1) + 1
        crc ^^= b
    return crc

def crc128_(data, poly=0x883ddfe55bba9af41f47bd6e0b0d8f8f):
    crc = crc128(c1)
    for b in data:
        crc ^^= b
        for _ in range(8):
            crc = (crc >> 1) ^^ (poly & -(crc & 1))
    return crc ^^ ((1 << 128) - 1)

def equivalent_affine_crc(crc_func, crc_bits, bytes_num):
    zero_crc = crc_func(bytes_num*b"\x00")
    target_bits = 8 * bytes_num
    v2n = lambda v: int(''.join(map(str, v)), 2)
    n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(crc_bits))

    #Basic Matrix
    Affine_Matrix = []
    for i in range(target_bits):
        v = vector(GF(2), (j == i for j in range(target_bits)))
        value = crc_func(long_to_bytes(v2n(v),bytes_num)) ^^ zero_crc
        Affine_Matrix.append(n2v(value))
    Affine_Matrix=matrix(GF(2),Affine_Matrix).transpose()

    #Add constraints
    for i in range(bytes_num):
        v,w = [0]*target_bits,[0]*target_bits
        v[i*8],w[i*8+1]=1,1
        v = vector(GF(2), v)
        w = vector(GF(2), w)
        Affine_Matrix = Affine_Matrix.stack(v)
        Affine_Matrix = Affine_Matrix.stack(w)
    return Affine_Matrix, n2v(zero_crc)

def crc_128_reverse(crc_value,bytes_num):
    M , C = equivalent_affine_crc(crc128_,128,bytes_num)
    v2n = lambda v: int(''.join(map(str, v)), 2)
    n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(128))
    x = list(n2v(crc_value) + C) + [0,1]*bytes_num
    x = vector(GF(2),x)
    res = M.solve_right(x)
    bas = M.right_kernel()

    #Find solution
    for i in trange(len(bas)):
        tr = res+bas[i]
        s = long_to_bytes(v2n(tr))
        if re.fullmatch(b'[A-Za-z0-9+/]*', s):
            if(check(s)):
                print(c1 + s + c2)

def check(c):
    return (crc128(c1 + c + c2) ^^ ((1 << 128) - 1)) == target

prefix = b'Dear guest, welcome to CRCRC Magic House, If you input '
suffix = b", you will get 0x9c6a11fbc0e97b1fff5844fa88b1ee2d"
c1 = b64encode(prefix)[:-2]
c2 = b64encode(suffix)
target = 0x9c6a11fbc0e97b1fff5844fa88b1ee2d
target2 = re_crc128(c2,target)

bytes_num = 26
crc_128_reverse(target2 ^^ ((1 << 128) - 1),bytes_num)

通过这题收获了很多。



*mt_speedrun

待复现