糖醋小鸡块的blog
0%

2024-NSSCTF-3rd-wp-crypto

发表于 分类于 Valine：

这次出了两个MT和3rdRSA，不过这一篇wp也包含yolbby的LFSRs。

3rdRSA

题目描述：

1
3rd’s Crypto checkin

题目：

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 random import *
from secret import flag
from os import urandom
from random import *

def pad(c,l):
    return c + urandom(l-len(c))

def getPrime3(bits):
    while(1):
        p = int("333"*33)*getrandbits(bits-333) + 1
        if(isPrime(p)):
            return p

p1th = getPrime(3*3*3*3*3*3)
p2nd = getPrime(3*3*3*3*3*3)
p3rd = getPrime3(3*3*3*3*3*3)
nss = p1th*p2nd*p3rd
m = bytes_to_long(pad(flag,3*3*3*3 + 33 + 3*3*3 + 3*3))

print("nss =", nss)
print("c1th =", pow(m,3,nss))
print("c2nd =", pow(3,m,nss))
print("p3rd =", p3rd)


'''
nss = 129063444400395931140552937306125851382394430986439278160593873744789936793795518045323178995007062628298309773582176239691459885773526624534690277511861861603281624682554253545227928169748182762012056234854538541309647111293806528166653033498149834445725530659660926127593831428768095049111056550293489376446453196283413940748453177975852069148305909986767912740830549027892132105563377310203897753966350743874679104628321785862987706430998848051299468409157327409929019736966482807332241638171032488791288702638854996896008055380420273360334533680833179185524820732104480666659321861366843400175400593725077960919448688150587388484016394469887799115548829
c1th = 34434392180151160913417544852616971692121904677314473399957347521083237373034994312975350004829141725822217771937654823384811574065863494723195053499396034949290411943322317170325058243501037304118017625559902628138026099775011556912632571666551501574674149399754491989755975771939193289559108779735832803131353873359793188227274679870124905519577462789862633176435874379040514994389592895575023493569300837110208625710266981571291166908408795186263690648761483931536077993683195891166866749702144363195471519064199405194909234060054947618318112220998235092847932193233297870660035092387998034397222343161862784190790234800655328367322488558923652724216788
c2nd = 2607182269911588640317443768516313475146031043011942375047416295563239497652683572392929453795834334601092180070778075446956225213228673291202712614851722328808263442169879046516657696381344172034458368689995793563352685120784745264814592735479698208625232292101406540095075755385738751964408524935105574210332493169531158694712409957008980603987021669723807161080311585592233184680564859608827956836072947637991546257832547921898039818720396103470292159465748053549459040177976994334908062142249458811885621719209965027537964222416346303361195322236614316663222188005352271974634346800843280024794327865267659775840158740927725776164466534809032826708671
p3rd = 34625024969762267128651307772809623649843622265032692142413571471210174269061639087466847081494470128344958794692961988682025560523709683489711068300641190919761862123159064271694245866486251838863170363349568878104217
'''

把组成n的三个素数分别记作p、q、r，题目给出了以下信息：

  • p、q、r均为729bit左右的素数
  • r-1有一些光滑的小素因子，将他们的乘积记为t，t大约有100bit
  • m大约在1200bit左右
  • $m^3$和$3^m$的值
  • n和r的值

由于给出了r，所以可以先求出m模r的值，同时由$3^m$可以在模r下求光滑部分的dlp，也就得到了m模t的值，之后crt起来就可以拿到m模rt的值，记为ml，此时就可以把m写为：

代入$m^3$中就可以得到：

所以就有：

所以接下来copper就可以了，而由于x的系数有r所以在模n下无法monic，所以转到模pq下去copper就行。

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

nss = 129063444400395931140552937306125851382394430986439278160593873744789936793795518045323178995007062628298309773582176239691459885773526624534690277511861861603281624682554253545227928169748182762012056234854538541309647111293806528166653033498149834445725530659660926127593831428768095049111056550293489376446453196283413940748453177975852069148305909986767912740830549027892132105563377310203897753966350743874679104628321785862987706430998848051299468409157327409929019736966482807332241638171032488791288702638854996896008055380420273360334533680833179185524820732104480666659321861366843400175400593725077960919448688150587388484016394469887799115548829
c1th = 34434392180151160913417544852616971692121904677314473399957347521083237373034994312975350004829141725822217771937654823384811574065863494723195053499396034949290411943322317170325058243501037304118017625559902628138026099775011556912632571666551501574674149399754491989755975771939193289559108779735832803131353873359793188227274679870124905519577462789862633176435874379040514994389592895575023493569300837110208625710266981571291166908408795186263690648761483931536077993683195891166866749702144363195471519064199405194909234060054947618318112220998235092847932193233297870660035092387998034397222343161862784190790234800655328367322488558923652724216788
c2nd = 2607182269911588640317443768516313475146031043011942375047416295563239497652683572392929453795834334601092180070778075446956225213228673291202712614851722328808263442169879046516657696381344172034458368689995793563352685120784745264814592735479698208625232292101406540095075755385738751964408524935105574210332493169531158694712409957008980603987021669723807161080311585592233184680564859608827956836072947637991546257832547921898039818720396103470292159465748053549459040177976994334908062142249458811885621719209965027537964222416346303361195322236614316663222188005352271974634346800843280024794327865267659775840158740927725776164466534809032826708671
p3rd = 34625024969762267128651307772809623649843622265032692142413571471210174269061639087466847081494470128344958794692961988682025560523709683489711068300641190919761862123159064271694245866486251838863170363349568878104217

r = p3rd
r_1 = r-1
t = int("333"*33) // 362853724342990469324766235474268869786311886053883 // 1344628210313298373
cofactor = r_1 // t

m_t = discrete_log(Mod(pow(c2nd,cofactor,p3rd),p3rd), Mod(pow(3,cofactor,p3rd),p3rd), ord = t)

PR.<x> = PolynomialRing(Zmod(r))
f = x^3 - c1th
m_rs = f.roots()
for i in m_rs:
    m_r = int(i[0])
    m_rt = crt([m_t,m_r], [t,r])
    ll = len(bin(m_rt)[2:])

    PR1.<m> = PolynomialRing(Zmod(nss // r))
    f1 = (m*r*t + m_rt)^3 - c1th
    f1 = f1.monic()
    res = f1.small_roots(X=2^((3*3*3*3 + 33 + 3*3*3 + 3*3 + 3) * 8 - ll), beta=1, epsilon=0.05)
    if(res != []):
        print(long_to_bytes(int(res[0])*r*t + m_rt))
        break


#NSSCTF{Rea1lY_EZ_Ch3ck1n_4nd_H4ve_FUN!}



MT-N

题目描述：

1
A brand-new MT challenge

题目：

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

def N(k):
    return getrandbits(1) & 0 if k == 0 else getrandbits(k)

gift = []
for i in range(100000):
    gift.append(N(N(N(1))))

key = getrandbits(500)
c = bytes_to_long(flag)^key

with open("output.txt", "w") as f:
    f.write(f"gift = {gift}\n")
    f.write(f"c = {long_to_bytes(c)}")

题目先定义了一个函数N，其基本上就是一个getrandbits函数，特殊性在于参数k=0时，依然会进行1bit的getrandbits。在此基础上，题目给出了100000次如下式子的结果：

并且以之后的500bit作为key与flag异或，也就是说要利用这给出的结果向后预测随机数，才能得到flag。

由以前MT的题型可以知道，如果我们知道了19968位getrandbits的结果以及这些比特位的位置，那么就可以构造矩阵来解线性方程得到初始state，然后就可以向后预测随机数了。

而问题在于，题目的MT进行了三层嵌套，相当于每次实际上都是三个bit的结果复合而成的，没办法直接获得每个bit。但是可以发现，如果gift中结果为1，那么其对应的三层一定都是1，就相当于获得了3bit的已知结果，因此搜集到足够19968bit就可以建矩阵了。

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
from Crypto.Util.number import *
from output import gift,c
from random import *
from tqdm import *

if(0): #test
    RNG1 = Random()
    print(RNG1.getstate())
    def N(k):
        return RNG1.getrandbits(1) & 0 if k == 0 else RNG1.getrandbits(k)
    gift = []
    for i in range(100000):
        gift.append(N(N(N(1))))


############################################################ part1 get state
RNG = Random()
length = 19968

def construct_a_row(RNG):
    ind = 0
    row = []
    while(1):
        if(gift[ind] == 0):
            RNG.getrandbits(1)
            RNG.getrandbits(1)
            RNG.getrandbits(1)
        elif(gift[ind] == 1):
            row.append(RNG.getrandbits(1))
            if(len(row) == length):
                return row
            row.append(RNG.getrandbits(1))
            if(len(row) == length):
                return row
            row.append(RNG.getrandbits(1))
            if(len(row) == length):
                return row
        ind += 1


L = []
for i in trange(length):
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(length-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG))

L = Matrix(GF(2),L)
'''
#test (ttt is init state)
sss = ""
for i in ttt:
    sss += bin(i)[2:].zfill(32)
sss = list(map(int,sss))
sss = vector(GF(2),sss)
print(sss*L)
'''

s = L.solve_left(vector(GF(2),[1]*length))
init = "".join(list(map(str,s)))
state = []
for i in range(624):
    state.append(int(init[32*i:32*i+32],2))


############################################################ part2 get flag
RNG1 = Random()
RNG1.setstate((3,tuple(state+[624]),None))
def N(k):
    return RNG1.getrandbits(1) & 0 if k == 0 else RNG1.getrandbits(k)
for i in range(100000):
    N(N(N(1)))

print(long_to_bytes(RNG1.getrandbits(500)^^bytes_to_long(c)))


#NSSCTF{1st_year_2nd_year_And_now_is_3rd_not_4th_Do_U_know_why?}



MT-SS

题目描述：

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

def SS(k):
    return getrandbits(1) & 0 if k == 0 else getrandbits(k)

gift = []
for i in range(50000):
    gift.append(SS(SS(5)))

key = getrandbits(500)
c = bytes_to_long(flag)^key

with open("output.txt", "w") as f:
    f.write(f"gift = {gift}\n")
    f.write(f"c = {long_to_bytes(c)}")

题目的SS函数其实完全就是上一题的N函数，只是为了起题目标题所以用了另一个名字XD，这一题的区别在于是给了50000次的如下结果：

但其实上一题明白道理的话，这个题目完全就是一样的，挑选gift中满31bit的数字，就说明内层的SS(5)结果是31，外层的SS(31)结果是gift中的值，这就获得了36bit的结果，凑够19968bit就行了。

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
from Crypto.Util.number import *
from output import gift,c
from random import *
from tqdm import *

if(0): #test
    RNG1 = Random()
    print(RNG1.getstate())
    def SS(k):
        return RNG1.getrandbits(1) & 0 if k == 0 else RNG1.getrandbits(k)
    gift = []
    for i in range(50000):
        gift.append(SS(SS(5)))


############################################################ part1 get state
RNG = Random()
length = 19968

def construct_a_row(RNG):
    ind = 0
    row = []
    while(1):
        if(len(bin(gift[ind])[2:]) == 31):
            t1 = bin(RNG.getrandbits(5))[2:].zfill(5)
            for tt in t1:
                row.append(int(tt))
            t2 = bin(RNG.getrandbits(31))[2:].zfill(31)
            for tt in t2:
                row.append(int(tt))
        else:
            RNG.getrandbits(32)
            RNG.getrandbits(32)
        if(len(row) >= length):
            return row
        ind += 1


L = []
for i in trange(length):
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(length-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG))

L = Matrix(GF(2),L)

known = []
for i in gift:
    if(len(bin(i)[2:]) == 31):
        known += [1,1,1,1,1]
        known += list(map(int,bin(i)[2:]))
        if(len(known) >= length):
            break
s = L.solve_left(vector(GF(2),known))
init = "".join(list(map(str,s)))
for i in range(624):
    state.append(int(init[32*i:32*i+32],2))


############################################################ part2 get flag
RNG2 = Random()
RNG2.setstate((3,tuple(state+[624]),None))
def SS(k):
    return RNG2.getrandbits(1) & 0 if k == 0 else RNG2.getrandbits(k)
for i in range(50000):
    SS(SS(5))

print(long_to_bytes(RNG2.getrandbits(500)^^bytes_to_long(c)))


#NSSCTF{Bec4us3_0f_LinearXD!!}



LFSRs

题目描述：

1
LFSR Family

题目：

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
import secrets, os
from random import randint
from Crypto.Util.number import *
from secret import flag

n = 256
MASK = 0x41140551440400010011541111545550144504145551145505114110154050d8
flag = flag.lstrip(b'NSSCTF{').rstrip(b'}')

class LFSR:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = key & ((1 << n) - 1)
        self.mask = mask

    def __call__(self):
        v = self.state & 1
        self.state = (self.state >> 1) | (
            (int(self.state & self.mask).bit_count() & 1) << (self.n - 1)
        )
        return v

def int_to_base(n, b):
    digits = []
    while n:
        digits.append(n % b)
        n //= b
    return digits

K = [randint(2^255,2^256) for i in range(16)]
lfsr = [LFSR(randint(200,256),K[i],MASK) for i in range(16)]

output = []
for i in range(20000):
    output.append(sum(lfsr[j]() for j in range(16)))
    
print(K)
print(output)

output = []
for i in range(5000):
    output.append(sum(lfsr[j]() for j in range(16)))

h = sha256(str(output).encode()).digest()
h = bytes_to_long(h)
print(h^^bytes_to_long(flag))

题目随机生成了16个LFSR，每个LFSR的mask和key都已知，唯一未知的是200-256的随机数n，n代表了LFSR中究竟用了多少位mask进行递推。

之后题目给出了20000组16个LFSR递推结果的和，需要继续预测5000组LFSR递推结果的和从而得到flag。

由于给出的数据是十六个LFSR的和，所以当和为0、16、1、15之类的特殊值时，对当前16个LFSR的bit就都有制约，所以只需要对16个LFSR逐一爆破n，并把不满足概率分布的筛掉，就可以得到全部的n了。

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

n = 256
MASK = 0x41140551440400010011541111545550144504145551145505114110154050d8
nums = 20000

class LFSR:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = key & ((1 << n) - 1)
        self.mask = mask

    def __call__(self):
        v = self.state & 1
        self.state = (self.state >> 1) | (
            (bin(int(self.state & self.mask))[2:].count("1") & 1) << (self.n - 1)
        )
        return v

if(0): #test
    from random import randint
    ns = [randint(200,256) for i in range(16)]
    lfsr = [LFSR(ns[i],K[i],MASK) for i in range(16)]
    output = []
    for i in range(nums):
        output.append(sum(lfsr[j]() for j in range(16)))
    print(ns)


##################################################### part1 find useful data in out
useful_index = []
for i in range(len(output)):
    if(output[i] == 0):
        useful_index.append(["1",0])
    elif(output[i] == 16):
        useful_index.append(["0",0])
    elif(output[i] == 1):
        useful_index.append(["1",1/16])
    elif(output[i] == 15):
        useful_index.append(["0",1/16])
    elif(output[i] == 2):
        useful_index.append(["1",2/16])
    elif(output[i] == 14):
        useful_index.append(["0",2/16])
    else:
        useful_index.append(["01",1])

##################################################### part2 remove some n
possible = [[] for i in range(16)]
for i in trange(16):
    for n in range(200,256+1):
        lfsri = LFSR(n,K[i],MASK)
        rate = 1
        for t in range(nums):
            temp = str(lfsri())
            if(temp in useful_index[t][0]):
                rate *= useful_index[t][1]
        if(rate >= 1/100000000000000000000):
            possible[i].append(n)
assert [] not in possible


from random import choice

for t in range(10):
    ns = []
    for i in range(16):
        ns.append(choice(possible[i]))
    lfsr = [LFSR(ns[i],K[i],MASK) for i in range(16)]
    output = []
    for i in range(nums):
        output.append(sum(lfsr[j]() for j in range(16)))
    output = []
    for i in range(5000):
        output.append(sum(lfsr[j]() for j in range(16)))

    h = sha256(str(output).encode()).digest()
    h = bytes_to_long(h)
    print(long_to_bytes(h^c))


#NSSCTF{Ann1v3rs4ry!LSFRs_R4150_r3united}