NSSCTFRound19

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

密码个人赛部分题解

bestkasscn的超级简单密码

task.py

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 *
import gmpy2
from functools import reduce
from secret import flag

p = getPrime(1024)
i = 0
while True:
    r = p * 5 + i
    if isPrime(r):
        i = 0
        break
    else:
        i += 1
while True:
    q = p * 10 + i
    if isPrime(q):
        break
    else:
        i += 1

n = p * q * r
e = 65537
c = pow(bytes_to_long(flag.encode()), e, n)
print('c=' + str(c))
print('p3=' + str(pow(p, 3, n)))
print('q3=' + str(pow(q, 3, n)))
print('r3=' + str(pow(r, 3, n)))
# n = 44571911854174527304485400947383944661319242813524818888269963870884859557542264803774212076803157466539443358890313286282067621989609252352994203884813364011659788234277369629312571477760818634118449563652776213438461157699447304292906151410018017960605868035069246651843561595572415595568705784173761441087845248621463389786351743200696279604003824362262237505386409700329605140703782099240992158439201646344692107831931849079888757310523663310273856448713786678014221779214444879454790399990056124051739535141631564534546955444505648933134838799753362350266884682987713823886338789502396879543498267617432600351655901149380496067582237899323865338094444822339890783781705936546257971766978222763417870606459677496796373799679580683317833001077683871698246143179166277232084089913202832193540581401453311842960318036078745448783370048914350299341586452159634173821890439194014264891549345881324015485910286021846721593668473
# c = 11212699652154912414419576042130573737460880175860430868241856564678915039929479534373946033032215673944727767507831028500814261134142245577246925294110977629353584372842303558820509861245550773062016272543030477733653059813274587939179134498599049035104941393508776333632172797303569396612594631646093552388772109708942113683783815011735472088985078464550997064595366458370527490791625688389950370254858619018250060982532954113416688720602160768503752410505420577683484807166966007396618297253478916176712265476128018816694458551219452105277131141962052020824990732525958682439071443399050470856132519918853636638476540689226313542250551212688215822543717035669764276377536087788514506366740244284790716170847347643593400673746020474777085815046098314460862593936684624708574116108322520985637474375038848494466480630236867228454838428542365166285156741433845949358227546683144341695680712263215773807461091898003011630162481
# p3 = 891438237083490546089708018947678893226384856270496377765399277417697191150845296075484241536063149330788867177806265725641352439792185047059884077696267280233195764685547392586251429555216372682368991273055524268769223153988946085858123028200360359212117360701384933036871231911448311911374115683475228820531478240539549424647154342506853356292956506486091063660095505979187297020928573605860329881982122478494944846700224611808246427660214535971723459345029873385956677292979041143593821672034573140001092625650099257402018634684516092489263998517027205660003413512870074652126328536906790020794659204007921147300771594986038917179253827432120018857213350120695302091483756021206199805521083496979628811676116525321724267588515105188480380865374667274442027086789352802613365511142499668793725505110436809024171752137883546327359935102833441492430652019931999144063825010678766130335038975376834579129516127516820037383067
# q3 = 44571911854174527304485400947383944661319242813524818888269963870884859557542264803774212076803157466539443358890313286282067621989609252352994203884813364011659788234277369629312571477760818634118449563652776213438461157699447304292906151410018017960605868035069246651843561595572415595568705784173761440671033435053531971051698504592848580356684103015611323747688216493729331061402058160819388999663041629882482138465124920580049057123360829897432472221079140360215664537272316836767039948368780837985855835419681893347839311156887660438769948501100287062738217966360434291369179859862550767272985972263442512061098317471708987686120577904202391381040801620069987103931326500146536990700234262413595295698193570184681785854277656410199477649697026112650581343325348837547631237627207304757407395388155701341044939408589591213693329516396531103489233367665983149963665364824119870832353269655933102900004362236232825539480774
# r3 = 22285955927087263652242700473691972330659621406762409444134981935442429778771132401887106038401578733269721679445156643141033810994804626176497101942406682005829894117138684814656285738880409317059224781826388106719230578849723652146453075705009008980302934017534623325921780797786207797784352892086880720749202442492937918619992591614713131681306874944356693778359565004415437554407990089293135634916859631279984463829118336826115430997439527110961309956466956650522900331263720500751112297418506140413317489683875995326726992533904683800042127871963320754241310699432792081707870167598822650064976439270556418985242630368723264289700246406905189810458354474959276748887369363592834205660349184660073395182450526542246354364903399132116153732074081050985584216815493617906868615192465631416955706457835185743023758573279838341229835613609332206338401219168119635681832981552328638132500079074010106995297184587143613134093145

很容易判断出$p^3 < n$

直接把p3开根号即可得到p，然后用题目的代码生成q,r

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

n = 44571911854174527304485400947383944661319242813524818888269963870884859557542264803774212076803157466539443358890313286282067621989609252352994203884813364011659788234277369629312571477760818634118449563652776213438461157699447304292906151410018017960605868035069246651843561595572415595568705784173761441087845248621463389786351743200696279604003824362262237505386409700329605140703782099240992158439201646344692107831931849079888757310523663310273856448713786678014221779214444879454790399990056124051739535141631564534546955444505648933134838799753362350266884682987713823886338789502396879543498267617432600351655901149380496067582237899323865338094444822339890783781705936546257971766978222763417870606459677496796373799679580683317833001077683871698246143179166277232084089913202832193540581401453311842960318036078745448783370048914350299341586452159634173821890439194014264891549345881324015485910286021846721593668473
c = 11212699652154912414419576042130573737460880175860430868241856564678915039929479534373946033032215673944727767507831028500814261134142245577246925294110977629353584372842303558820509861245550773062016272543030477733653059813274587939179134498599049035104941393508776333632172797303569396612594631646093552388772109708942113683783815011735472088985078464550997064595366458370527490791625688389950370254858619018250060982532954113416688720602160768503752410505420577683484807166966007396618297253478916176712265476128018816694458551219452105277131141962052020824990732525958682439071443399050470856132519918853636638476540689226313542250551212688215822543717035669764276377536087788514506366740244284790716170847347643593400673746020474777085815046098314460862593936684624708574116108322520985637474375038848494466480630236867228454838428542365166285156741433845949358227546683144341695680712263215773807461091898003011630162481
p3 = 891438237083490546089708018947678893226384856270496377765399277417697191150845296075484241536063149330788867177806265725641352439792185047059884077696267280233195764685547392586251429555216372682368991273055524268769223153988946085858123028200360359212117360701384933036871231911448311911374115683475228820531478240539549424647154342506853356292956506486091063660095505979187297020928573605860329881982122478494944846700224611808246427660214535971723459345029873385956677292979041143593821672034573140001092625650099257402018634684516092489263998517027205660003413512870074652126328536906790020794659204007921147300771594986038917179253827432120018857213350120695302091483756021206199805521083496979628811676116525321724267588515105188480380865374667274442027086789352802613365511142499668793725505110436809024171752137883546327359935102833441492430652019931999144063825010678766130335038975376834579129516127516820037383067
q3 = 44571911854174527304485400947383944661319242813524818888269963870884859557542264803774212076803157466539443358890313286282067621989609252352994203884813364011659788234277369629312571477760818634118449563652776213438461157699447304292906151410018017960605868035069246651843561595572415595568705784173761440671033435053531971051698504592848580356684103015611323747688216493729331061402058160819388999663041629882482138465124920580049057123360829897432472221079140360215664537272316836767039948368780837985855835419681893347839311156887660438769948501100287062738217966360434291369179859862550767272985972263442512061098317471708987686120577904202391381040801620069987103931326500146536990700234262413595295698193570184681785854277656410199477649697026112650581343325348837547631237627207304757407395388155701341044939408589591213693329516396531103489233367665983149963665364824119870832353269655933102900004362236232825539480774
r3 = 22285955927087263652242700473691972330659621406762409444134981935442429778771132401887106038401578733269721679445156643141033810994804626176497101942406682005829894117138684814656285738880409317059224781826388106719230578849723652146453075705009008980302934017534623325921780797786207797784352892086880720749202442492937918619992591614713131681306874944356693778359565004415437554407990089293135634916859631279984463829118336826115430997439527110961309956466956650522900331263720500751112297418506140413317489683875995326726992533904683800042127871963320754241310699432792081707870167598822650064976439270556418985242630368723264289700246406905189810458354474959276748887369363592834205660349184660073395182450526542246354364903399132116153732074081050985584216815493617906868615192465631416955706457835185743023758573279838341229835613609332206338401219168119635681832981552328638132500079074010106995297184587143613134093145


p = gmpy2.iroot(p3,3)[0]
i = 0
while True:
    r = p * 5 + i
    if isPrime(r):
        i = 0
        break
    else:
        i += 1
while True:
    q = p * 10 + i
    if isPrime(q):
        break
    else:
        i += 1

phi = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(65537,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# NSSCTF{cc10786a-cc59-a07d-5c9f-df1c55b18cd4}

bestkasscn的简单密码

task.py

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
from random import randint
from secret import flag, enc_key

dir = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}"
assert len(flag) == 64
assert len(enc_key) == 64


def getGraph(row, column):
    graph = [['' for _ in range(row)] for _ in range(column)]
    for i in range(column):
        for j in range(row):
            graph[i][j] = dir[randint(0, 63)]
    return graph


def bestkasscnEncryption(str):
    binary = ''
    res = ''
    for c in str:
        binary += '0' + bin(ord(c))[2:] + ''
    while len(binary) % 6 != 0:
        binary += '0'
    for i in range(len(binary) // 6):
        res += dir[int(binary[i * 6:6 + i * 6], 2)]
    while len(res) % 3 != 0:
        res += '}'
    return res


encrypt = bestkasscnEncryption(enc_key)

graph1 = getGraph(len(encrypt), len(encrypt))
graph2 = getGraph(len(encrypt), len(encrypt))
for i in range(len(flag)):
    graph1[dir.index(encrypt[i])][i] = enc_key[i]
    graph2[i][dir.index(encrypt[i])] = flag[i]

for i in range(0, len(flag), 2):
    graph2[i][dir.index(encrypt[i])] = enc_key[i]
    graph1[dir.index(encrypt[i])][i] = flag[i]

with open('graph1.txt', 'w') as file:
    file.write("graph1:\n")
    for i in graph1:
        file.write(str(i))
        file.write(',')
        file.write('\n')
file.close()
with open('graph2.txt', 'w') as file:
    file.write("graph2:\n")
    for j in graph2:
        file.write(str(j))
        file.write(',')
        file.write('\n')
file.close()

with open('encrypt.txt', 'w') as file:
    file.write(encrypt)
file.close()

注意到

1
2
3
4
5
6
7
for i in range(len(flag)):
    graph1[dir.index(encrypt[i])][i] = enc_key[i]
    graph2[i][dir.index(encrypt[i])] = flag[i]

for i in range(0, len(flag), 2):
    graph2[i][dir.index(encrypt[i])] = enc_key[i]
    graph1[dir.index(encrypt[i])][i] = flag[i]

key(压缩包的密码)的一部分可以通过graph1和encrypt求出

flag的一半也在graph1里

key的另外一半我用比较粗糙的手段(爆破)求出的，key = One_who_has_seen_the_ocean_thinks_nothing_of_mere_rivers_so_do_I

求出key之后打开graph2，再根据flag的位置输出即可

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from random import randint

dir = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}"
encrypt = "t25Lx3DOB19OyxnFC2vLBL90AgvFB2nLyw5FDgHPBMTZx25VDgHPBMDFB2zFBwvYzv9YAxzLCNnFC29Fzg9Fsq}"

graph1 = [[...]]
graph2 = [[...]]

for i in range(64):
    if i % 2 == 0:
        m = graph1[dir.index(encrypt[i])][i]
        flag += m
    else:
        m = graph2[i][dir.index(encrypt[i])]
        flag += m
        
print(flag)
# One_who_has_seen_the_ocean_thinks_nothing_of_mere_rivers_so_do_I
# NSSCTF{What_I_miss_is_saying_nothing_nothing_better_than_hotpot}

以下赛题均为复现，参考2024-NSSCTF-Round19-Basic-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

*3DES?

task.py

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 *
from Crypto.Cipher import DES
from Crypto.Util.Padding import pad
from secret import flag
from random import *

class DEStream():
    def __init__(self):
        self.table = '0123456789'
        self.key = ("".join([choice(self.table) for i in range(8)])).encode()
        self.seed = b"!NSSCTF!"
        self.des = DES.new(self.key,mode=DES.MODE_ECB)

    def next(self):
        self.seed = (self.des).encrypt(self.seed)
        return bytes_to_long(self.seed) & 1
    
    def enc(self,m):
        return (self.des).encrypt(m)

def combine(x1,x2,x3):
    return (x1&x2)^(x2&x3)^x3

des1 =  DEStream()
des2 =  DEStream()
des3 =  DEStream()

output = ""
for i in range(2000):
    output += str(combine(des1.next(),des2.next(),des3.next()))

cipher = des1.enc(pad(flag,8))
cipher = des2.enc(cipher)
cipher = des3.enc(cipher)

print("output =",output)
print("cipher =",cipher)


'''
output = 10110101110110001000111000110101000110111100110110011010000010001110010010101111000101101100101011110101111011000000001110011001011001110010010000001010111101011110011011000111011101010000111011011110010001101001110010111100101111110001000110000110111010100010111010000110000001011010111100100011011010001101001001100000000001100101111110110011000101101100110101010000010101100001010010000010010011001011110000010101111000001110010100110110111011001010111111100010100111000110110010101101000001011000101110101100000110110000101101010100101010000100110011011110100110111101101100011100011100101000000100000000101001100101001010101001000110011110110000111111001111101110110110100001010000100110010100010101000001010001111100000010100000101101111010010011010100011000100111001101100001011111001100111101100011001001000001000100011011010000001101110000001111011000111000011001010011100110110111111101010110101110110110000101110110000000101110000011110101001100010000101001010010000011110111100001101011001110100011101111011001010110111000010000111000010010111111111000111100110000100100100011111100101111011001000000011000001100110100011100110010100010001110011001011100101001101001100110001010000011001001101010010101001111110100010111000000101011000100100000010011111011001011010001101101101001100111010110101001001111000111000001000001010000001100101110110010111111001001011111111000100110011100011000111011010100001011010000011110101001110101010011111000100010011010000101011100110110101000100010010001011101010010100100001011010101000010000110001100100010000010111110011111000011000100011001110001100100111111101000001001101110000100101011010010011001100100100100010000101100111001100110000110010001001010011011011101011010100110001100001000111010000100100100010110111100000100111010101100000111010111011000100011010111110010010000110111111001101000011111000111100110111110011110101001100110111000111111011010011100011000010010011010100000100110010011111011110111011111011011110010110000110011110000
cipher = b'\xe3\t\x13\xe2\x8b\xd1\xdeql\x94F\xb5}\xb8d\xfa~\x06&~\x8f\xcb-&\xf3q/j\xd3\xbe\x1f\xef\x18\x84hn\x1c[t\x03\x10\xb8\x8e?\x89\x8b\x00\xc5\xb9`5E\xeaC\xe9,'
'''

拿到题目发现flag进行了三次加密，很明显我们需要求出3个key

注意到key是由0123456789组成的，长度为8

题目只给出长度2000的二进制序列，所以只能通过这2000个值求3个key

先分析这个combine函数，自己遍历8个组合就可以知道这个combine的结果有75%的概率和$x_1$一样，有50%的概率和$x_2$的概率一样，有75%的概率和$x_3$一样

1
2
3
4
5
6
7
8
x1 = 0,x2 = 0,x3 = 0,combine = 0
x1 = 0,x2 = 0,x3 = 1,combine = 1
x1 = 0,x2 = 1,x3 = 0,combine = 0
x1 = 0,x2 = 1,x3 = 1,combine = 0
x1 = 1,x2 = 0,x3 = 0,combine = 0
x1 = 1,x2 = 0,x3 = 1,combine = 1
x1 = 1,x2 = 1,x3 = 0,combine = 1
x1 = 1,x2 = 1,x3 = 1,combine = 1

而$x_1,x_3$分别是$key_1,key_3$对初始seed加密使用的密钥，这说明我们可以通过爆破的手段求得$key_1,key_3$，判断方式是观察其输出是否与2000位(用不上比较这么多位，鸡块的wp是用200位，加快速度)给定的序列有75%的相似度。还有需要注意的点是，DES加密过程并没有用上密钥的所有数据，密钥每个字节的第8bit(最低那位)是不参与加密的，可以自己跑代码实现试试，这又可以减少很多爆破时间。求key2的时候，只需要判断50位左右，因为在密钥错误的情况下，连续50位和题目给的序列一样的概率非常小。

test.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Cipher import DES

key = b"testtest"

testkey = b""
for i in key:
    temp = (i // 2) << 1
    temp += 1               #加0也没区别
    testkey += bytes.fromhex(hex(temp)[2:])

m = b"A"*8
des = DES.new(key,DES.MODE_ECB)
c = des.encrypt(m)

testdes = DES.new(testkey,DES.MODE_ECB)
testc = testdes.encrypt(m)

print(c)
print(testc)

exp.py

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

output = "10110101110110001000111000110101000110111100110110011010000010001110010010101111000101101100101011110101111011000000001110011001011001110010010000001010111101011110011011000111011101010000111011011110010001101001110010111100101111110001000110000110111010100010111010000110000001011010111100100011011010001101001001100000000001100101111110110011000101101100110101010000010101100001010010000010010011001011110000010101111000001110010100110110111011001010111111100010100111000110110010101101000001011000101110101100000110110000101101010100101010000100110011011110100110111101101100011100011100101000000100000000101001100101001010101001000110011110110000111111001111101110110110100001010000100110010100010101000001010001111100000010100000101101111010010011010100011000100111001101100001011111001100111101100011001001000001000100011011010000001101110000001111011000111000011001010011100110110111111101010110101110110110000101110110000000101110000011110101001100010000101001010010000011110111100001101011001110100011101111011001010110111000010000111000010010111111111000111100110000100100100011111100101111011001000000011000001100110100011100110010100010001110011001011100101001101001100110001010000011001001101010010101001111110100010111000000101011000100100000010011111011001011010001101101101001100111010110101001001111000111000001000001010000001100101110110010111111001001011111111000100110011100011000111011010100001011010000011110101001110101010011111000100010011010000101011100110110101000100010010001011101010010100100001011010101000010000110001100100010000010111110011111000011000100011001110001100100111111101000001001101110000100101011010010011001100100100100010000101100111001100110000110010001001010011011011101011010100110001100001000111010000100100100010110111100000100111010101100000111010111011000100011010111110010010000110111111001101000011111000111100110111110011110101001100110111000111111011010011100011000010010011010100000100110010011111011110111011111011011110010110000110011110000"
cipher = b'\xe3\t\x13\xe2\x8b\xd1\xdeql\x94F\xb5}\xb8d\xfa~\x06&~\x8f\xcb-&\xf3q/j\xd3\xbe\x1f\xef\x18\x84hn\x1c[t\x03\x10\xb8\x8e?\x89\x8b\x00\xc5\xb9`5E\xeaC\xe9,'

def combine(x1,x2,x3):
    return (x1&x2)^(x2&x3)^x3

def compare(str1,str2):               #计算相似度
    assert len(str1) == len(str2)
    num = 0
    for i in range(len(str1)):
        if str1[i] == str2[i]:
            num += 1
    if (num / len(str1)) > 0.75:
        return True
    else:
        return False
    
table = "0123456789"
prefix = []
for i in table:
    temp = bin(ord(i) // 2)[2:].zfill(7)
    if temp not in prefix:
        prefix.append(temp)
# 把这些字符2进制形式的高7位存入

key_may = []
for i in tqdm(product(prefix,repeat = 8)):      #爆破key1和key3,长度为八个字节
    temp = "".join(j + "0" for j in list(i))
    key = long_to_bytes(int(temp,2))
    # 开始爆
    des1 = DES.new(key,DES.MODE_ECB)
    seed = b"!NSSCTF!"
    output1 = ""
    for j in range(200):
        seed = des1.encrypt(seed)
        out = str(bytes_to_long(seed) & 1)
        output1 += out
    if compare(output1,output[:200]):
        key_may.append(key)

# 大概12分钟
# print(key_may)
# key_may = [b'06660408', b'84822042']
# 可能的密钥只有2个，只需要来回试一下key1,key3即可
key1 = key_may[1]                   
key3 = key_may[0]
des1 = DES.new(key1,DES.MODE_ECB)
des3 = DES.new(key3,DES.MODE_ECB)

# 接下来爆key2
# 大概1分20秒
for i in tqdm(product(prefix,repeat = 8)):
    temp = "".join(j + "0" for j in list(i))
    key = long_to_bytes(int(temp,2))
    
    des2 = DES.new(key,DES.MODE_ECB)
    
    seed1 = seed2 = seed3 = b"!NSSCTF!"
    judge = True
    for j in range(50):
        seed1 = des1.encrypt(seed1)
        seed2 = des2.encrypt(seed2)
        seed3 = des3.encrypt(seed3)
        out1 = bytes_to_long(seed1) & 1
        out2 = bytes_to_long(seed2) & 1
        out3 = bytes_to_long(seed3) & 1
        temp = combine(out1,out2,out3)
        if str(temp) != output[j]:
            judge = False
            break
    
    if judge:
        flag = des3.decrypt(cipher)
        flag = des2.decrypt(flag)
        flag = des1.decrypt(flag)
        print(flag)
        # NSSCTF{Y0U_C411_Th15_3DES???_;D_J4st_U53_CorreL@tion!}
        print(f"key2 = {key}")
        # 26206626
        break

$$
output = x_1x_2 \oplus x_2x_3 \oplus x_3
$$
看了wp才知道这个叫Gefee生成器

*Decision

task.py

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

class MRG:
    def __init__(self,para_len,p):
        self.init(para_len,p)

    def next(self):
        self.s = self.s[1: ] + [(sum([i * j for (i, j) in zip(self.a, self.s)]) + self.b) % self.p]
        return self.s[-1]

    def init(self,para_len,p):
        self.p = p
        self.b = randint(1, self.p)
        self.a = [randint(1, self.p) for i in range(para_len)]
        self.s = [ord(choice(string.printable)) for i in range(para_len)]
    
    def get_params(self):
        return [self.a,self.b,self.s[0]]


flag = bytes_to_long(flag)
flag_bin = bin(flag)[2:]

Round = 2024
A_len = 10
p = getPrime(256)

output = []
for i in flag_bin:
    if(i == "0"):
        temp = MRG(A_len,p)
        for j in range(Round):
            temp.next()
        output.append(temp.get_params())
    else:
        a = [randint(1,p) for i in range(A_len)]
        b = randint(1,p)
        s = randint(1,p)
        output.append([a,b,s])

with open("output.txt","w") as f:
    f.write(str(p))
    f.write(str(output))

解题思路是通过flag当前位不同产生的s大小不一样来恢复

当flag当前位是0的时候，会用类MRG来初始化一个s，这个s是由可见字符的ASCII码值组成的，对比flag当前位为1的时候，s为1~p中的一个数，很容易发现当flag当前位为0的时候，s初始状态很小。

也就是说，我们要想办法求出s的初始状态

首先s每次迭代有
$$
s_{10} \equiv a_0s_0+a_1s_1 + … +a_9s_9 + b\mod p
$$
写成矩阵形式有

而题目迭代了2024次，写成矩阵形式就为

难点在于题目只给了$s_{0+2024},a_0,…,a_9,b$，如何利用这些数据来恢复$s_0-s_9$

记

上面表达式可写为$S_{2024} = L\times S_0$

进行转置,得$S_{2024}^T = S_0^T\times L^T$

就是

由于我们只有$s_{0+2024}$,所以我们只取$L^T$的第一列作为线性关系

就有

然后构造出格

其中$L_{1,i}^T$表示$L_1^T$中第i个元素

需要配上系数保证最后一列规约出0

所以最后构造的格为

赛时疑惑只有一个线性关系如何用格处理

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

p = 
output = 

m = ""
for j in trange(len(output)):
    temp = output[j]
    a = temp[0]
    a.append(1)
    b = temp[1]
    s2024 = temp[2]
    Ge = Matrix(Zmod(p),11,11)                   #很值得注意，这个矩阵的定义域是mod p
    for i in range(9):
        Ge[i,i+1] = 1
        Ge[-2,i] = a[i]
    Ge[-2,-2] = a[-2]
    Ge[-2,-1] = b
    Ge[-1,-1] = 1
    L = Ge^2024
    L1 = vector(ZZ,L.transpose()[:,0].list())                #提取转置矩阵的第一列，注意定义域
    M = Matrix(ZZ,13,13)
    for i in range(11):
        M[i,i] = 1
        M[i,-1] = L1[i] * 2^1000
    M[-2,-2] = 1
    M[-2,-1] = -s2024 * 2^1000
    M[-1,-1] = p * 2^1000
    s0 = M.LLL()[0][0]
    if abs(s0) < 128:
        m += "0"
    else:
        m += "1"
        
flag = bytes.fromhex(hex(int(m,2))[2:])
print(flag)
# NSSCTF{D3c1s1on_MRG_I5n'7_diFFiCulT_R1GHT?}

配系数建议乘上对角矩阵，因为手动乘的话，需要注意前面向量，矩阵的一些定义域问题

例如这题就需要先把向量L1从模p的定义域转到整数域

乘对角矩阵的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
from tqdm import *

p = 
output = 

m = ""
for j in trange(len(output)):
    temp = output[j]
    a = temp[0]
    a.append(1)
    b = temp[1]
    s2024 = temp[2]
    Ge = Matrix(Zmod(p),11,11)                   #很值得注意，这个矩阵的定义域是mod p
    for i in range(9):
        Ge[i,i+1] = 1
        Ge[-2,i] = a[i]
    Ge[-2,-2] = a[-2]
    Ge[-2,-1] = b
    Ge[-1,-1] = 1
    L = Ge^2024
    L1 = vector(ZZ,L.transpose()[:,0].list())                #提取转置矩阵的第一列
    M = Matrix(ZZ,13,13)
    for i in range(11):
        M[i,i] = 1
        M[i,-1] = L1[i]
    M[-2,-2] = 1
    M[-2,-1] = -s2024
    M[-1,-1] = p
    Q = diagonal_matrix([1]*12 + [2^1000])
    MM = M * Q
    MM = MM.LLL()
    MM = MM / Q
    MM = M.LLL()
    s0 = MM[0][0]
    if abs(s0) < 128:
        m += "0"
    else:
        m += "1"
        
flag = bytes.fromhex(hex(int(m,2))[2:])
print(flag)
# NSSCTF{D3c1s1on_MRG_I5n'7_diFFiCulT_R1GHT?}

这道题复现的卡顿点还蛮多的，首先在矩阵规模卡顿了一会，然后就是代码实现，因为和鸡块使用的函数不一样，几乎每一处矩阵都不断打印出来核对，最后对于手动配上系数和通过乘对角矩阵配系数也琢磨了挺久，最后花了接近4小时完成复现。

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