25Jan3

huangx607087 1月的切题 3

0.Introduction

一回家就G了，然后休息了几天，两场CTF比赛都没好好看

1.[DASCTF2304] babyhash_revenge

1x01 题目大意

先瞄一眼题目，这个Hash，和前几天SUCTF那个HASH相似度真高：

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
import socketserver
import signal
from Crypto.Util.number import *
from random import randint
from gmpy2 import next_prime

banner = br'''
 _____     ______     ______     ______     ______   ______  
/\  __-.  /\  __ \   /\  ___\   /\  ___\   /\__  _\ /\  ___\ 
\ \ \/\ \ \ \  __ \  \ \___  \  \ \ \____  \/_/\ \/ \ \  __\ 
 \ \____-  \ \_\ \_\  \/\_____\  \ \_____\    \ \_\  \ \_\   
  \/____/   \/_/\/_/   \/_____/   \/_____/     \/_/   \/_/   
'''

flag = b'xxx'
n0 = 30798082519452208630254982405300548841337042015746308462162479889627080155514391987610153873334549377764946092629701
g = 91289086035117540959154051117940771730039965839291520308840839624996039016929

class LCG():
    def __init__(self) -> None:
        self.n = next_prime(2**240)
        self.a = getRandomNBitInteger(85)
        self.seed = randint(1, self.n-1)

    def next(self):
        self.seed = (self.seed ** 3 * self.a + randint(-2**230, 2**230) + randint(1,100)) % self.n
        return self.seed

def gift():
    lcg = LCG()
    outputs = []
    for i in range(30):
        outputs.append(int(lcg.next()))
    return outputs, lcg.a

gift, a = gift()

def check(str1,str2):
    key = bin(a)[2:]
    test = []
    for i in range(len(key)):
        if key[i] == '0':
            test.append(str1[i] == str2[i])
    return all(test)

def hash(msg):
    key = bin(a)[2:]
    n = n0
    msg = list(map(ord,msg))
    for i in range(len(msg)):
        if key[i] == '1':
            n = g * (2 * n + msg[i])
        else:
            continue
        n = n & ((1 << 383) - 1)
    return (n - 0xdeedbeef114514) % (1 << 100)

MENU = br'''
<OPTION>
'''

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'SERVER <INPUT>: '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        rounds = 1000
        pseudo_prime = int(self.recv(prompt=b'[+] Plz Tell Me your number: '))
        if isPrime(pseudo_prime):
            self.send(b"\nNo! it's a prime, go away!")
            self.request.close()
        for i in range(rounds):
            if pow(randint(2, pseudo_prime), pseudo_prime - 1, pseudo_prime) != 1:
                self.send(b"\nYou failed in round " + str(i + 1).encode() + b', bye~~')
                self.request.close()
        self.send(b"\nCongratulations, you have passed the proof_of_work!\n")
        return True

    def handle(self):
        signal.alarm(300)
        step1 = self.proof_of_work()
        if not step1:
            self.request.close()
        self.send(banner)
        self.send(b"\nNew challenge now! Please give me 2 diff strings whose hashes are the same~~")
        self.send(b'Here is my gift for you: \n' + str(gift).encode())
        string1 = self.recv().decode()
        string2 = self.recv().decode()
        if len(string1) < 70 or len(string2) < 70:
            self.send(b"\nNo! Too short!")
            self.request.close()
        if not check(string1,string2):
            self.send(b"\nNo! I do not like!")
            self.request.close()
        if string1 == string2:
            self.send(b"\nNo! They are the same one!")
            self.request.close()
        if hash(string1) == hash(string2):
            self.send(b'\nGood job~ Here you are!')
            self.send(flag)
        self.send(b"\nConnection has been closed.")
        self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 9999
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

1x02 解题过程

首先先过proof_of_work，发现是一个伪素数的测试，要求给一个合数 $n$，但要求随机 $a$ 均满足 $a^{n-1}\equiv 1\pmod n$。很明显的卡米歇尔数。但这边 $a$ 是随机取的，因此这个卡米歇尔数的素因子要比较大，才能保证 $a$ 和 $n$ 互素。

构造方法很简单：若 $6k+1,12k+1,18k+1$ 均为素数，那么 $n=(6k+1)(12k+1)(18k+1)$ 为卡米歇尔数，这个其实也在SUCTF那个mathgame中到了，不过那个mathgame第三问不能算个题，因此就没有写在blog中了。因此，当 $k$ 达到 $100$ 位后，$n$ 和 $a$ 不互素的概率是可以忽略不计的。

1
2
3
4
5
6
7
8
9
10
11
from random import getrandbits
from Crypto.Util.number import *
def findfakePrime():
    while(1):
        a=getrandbits(100)
        p,q,r=6*a+1,12*a+1,18*a+1
        if(isPrime(p)&isPrime(q)&isPrime(r)):
            return p*q*r
findfakePrime()
# 10s--25s
# 148809159554409110476163772315329170997830985215359063220293349706160369860802335922266079601

然后看他的Hash函数：很明显，这里有 $a$ 是不知道的，那就需要先把 $a$ 求出来。这边 LCG 的参数为：$y=ax^3+b_i$，其中 $b_i$ 为 $230$ 位的随机数，模数为 $240$ 位，给了 $30$ 组数据，求 $a$，这里 $a$ 是 $85$ 位，因此这边相当于一个LCG已知高位，求整个LCG的题。

那么尝试求 $a$ （肯定是三十组数据全用的，这边以三组为例，看个构造过程）

1

对中间矩阵进行LLL，测个界，最终最短向量大概率是 $a$。

有了 $a$ 之后，就可以按照前面那个题的方法，找出一组碰撞，攻击题目中的Hash了。但这边他的要求比较奇怪：如果 $a$ 的对应比特为 $1$，才放入Hash中计算，但又要求 $a$ 对应比特为 $0$ 的位要保持一致，并且要求给出的字符为可见字符。

回顾一下那个题的构造方法：

2

那么直接把SUHash那个找碰撞的函数拿过来用，但注意这边构造的位数为 $a$ 的 $1$ 比特数（大概 $40$ 多），并且找到一组就OK了。

我这边最终构造的结果为：

1
2
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
RPPPPTQSPONPPPPPPPPPKPOPOPPOOONPYPNKLNPPOPPPPPQQSQLPPNPPPPPPPQOQOPPPPPPPRRPPSRPPPPPPP

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
from pwn import *
from sage.all import *
context.log_level = 'debug' 
sh=remote('node5.buuoj.cn',26391)
sh.recvuntil(b':')
sh.sendline(b'148809159554409110476163772315329170997830985215359063220293349706160369860802335922266079601')
sh.recvuntil(b'[')
arr=eval(b'['+sh.recvline(keepends=False))
p=next_prime(1<<240)
A=[arr[i]**3%p for i in range(29)]
B=[arr[1+i] for i in range(29)]
M=[[p*(i==j) for j in range(31)]for i in range(31)]
M[0][0],M[1][1]=2**(230-85),2**230
for i in range(29):
    M[0][2+i]=A[i]
    M[1][2+i]=B[i]
M=matrix(ZZ,M)
M3L=M.LLL()
vec=M3L[0]
a=abs(vec[0])
assert a%(2**(230-85))==0
a=(vec[0])>>(230-85)
print(a)
difflen=bin(a).count('1')
print(difflen)
n0 = 30798082519452208630254982405300548841337042015746308462162479889627080155514391987610153873334549377764946092629701
g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
def H(msg):
    key = bin(a)[2:]
    n = n0
    msg = list(map(ord,msg))
    for i in range(len(msg)):
        #print(i)
        if key[i] == '1':
            n = g * (2 * n + msg[i])
        else:
            continue
        n = n & ((1 << 383) - 1)
    return (n - 0xdeedbeef114514) % (1 << 100)
def getcollision(n):
    M=[[i==j for j in range(n+1)]for i in range(n+1)]
    M[-1][-1]=2**128
    for i in range(n):
        M[i][-1]=2**(n-i)*Integer(pow(g,n-i,2**128))%(2**128)
    M=matrix(ZZ,M)
    M3L=M.LLL()
    vec=[]
    for v in M3L:
        if(v[-1]==0):
            vec.append(v)
    return vec
detla=getcollision(difflen)[0]
s=bytes([80]*85)
t=[80]*85
cur=0
table=bin(a)[2:]
for i in range(85):
    if(table[i]=='1'):
        t[i]+=detla[cur]
        cur+=1
t=bytes(t)
print(s)
print(t)
sh.recvuntil(b':')
sh.sendline(s)
sh.recvuntil(b':')
sh.sendline(t)
print(sh.recvall(timeout=500))
#DASCTF{S0rry_But_this_1s_My_revenge}

2.[DASCTF2410]easy_xor–7solves

2x01 题目大意

先看眼题目：

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
#Sage
import os
from Crypto.Util.number import *
from hashlib import *

def encrypt(msg):
    p = getPrime(256)
    n = 2^512
    x = msg[0] << 7
    for i in msg:
        x = int(x*p % n)
        x ^^= i
    return x ^^ len(msg) ,p


def prime_to_matrix(p , n):
    
    binary_rep = bin(p)[2:].zfill(n^2)
    matrix = Matrix(GF(2), n, n, [int(b) for b in binary_rep])
    
    return matrix

def matrix_to_prime(matrix, n):

    binary_rep = ''.join(str(matrix[i, j]) for i in range(n) for j in range(n))
    p = int(binary_rep, 2)
    
    return p

key = os.urandom(16)
key_list = [i for i in key]
c,p = encrypt(key_list)

P = prime_to_matrix(p,16)

q = getPrime(256) 
Q = prime_to_matrix(q,16)

R = P*Q
r = matrix_to_prime(R,16)

s = p^^r
S = prime_to_matrix(s,16)

array_q = []
t = q
while t > 0:
    array_q.append(t%256)
    t = t//256

m = len(array_q)
A = matrix(ZZ,m,m)
for i in  range(m):
    for j in range(m):
        A[i,j] = randint(65537//2,65537)

x = matrix(ZZ,[array_q])
x = x.T
e = matrix(ZZ,m,1)
for i in range(m):
    e[i,0] = randint(1,256)
b = A*x + e  

with open("out.txt","w") as f:
    f.write(f"c = {c}\n")
    f.write(f"S = {S}\n")
    f.write(f"A = {A}\n")
    f.write(f"b = {b}\n")
    
flag = "CBCTF{"+sha256(key).hexdigest()+"}"

题目要求 $key$，为一个长度为 $16$ 的字符串，给出了 c=enc(key,p)，其中 $p$ 为 $256$ 位素数，并生成了另一个 $256$ 位的素数 $q$。

随后将 $p,q$ 逐比特转化为 $P,Q$ 两个 $16\times16$ 的 $\mathbb F_2$ 上矩阵，并计算 $R=PQ$，又将 $R$ 逐比特转化为 $256$ 位的数值 $r$，并计算 $s=p\oplus r$，最终转化成了矩阵 $S$。

而对于 $q$，又将 $q$ 转化为了 $256$ 进制的形式，得到了 $\vec x$，并最终计算了 $\vec b=A\vec x+\vec e$。

2x02 题目分析

拿到第一步就发现， $\vec b=A\vec x+\vec e$ 这一步没有带模数，可以尝试直接解并获得 $q$。

1
2
3
4
5
6
7
8
RF600=RealField(600)
A=matrix(RF600,A)
b=vector(RF600,[b[i][0] for i in range(len(b))])
x=A.solve_right(b)
xreg=[x[i].round() for i in range(len(x))]
q=sum([xreg[i]*256**i for i in range(len(xreg))])
print(q)
#82562676145944350609535127612846198515707028561842371207246482755300888479199

拿到 $q$ 之后，那下面就是求 $p$。可以发现，从 $R$ 到 $r$ 再计算 $s=p\oplus r$ 这一步骤意义不大，相当于 $\mathbb F_2$ 矩阵计算 $S=PQ+P$，也就是 $S=P(Q+E)$，那么 $P=S(Q+E)^{-1}$ 就能够得到 $p$ 了。

1
2
3
4
5
6
7
Q=prime_to_matrix(q,16)
E=identity_matrix(GF(2),16)
S=Matrix(GF(2),S)
P=S*(Q+E)**-1
p=matrix_to_prime(P,16)
print(p)
#67257864135528287293221481195193537429491893060495096187717252518567940812773

拿到 $p$ 之后，由于已知 key 的长度为 $16$，因此先给 $c$ 异或上 $16$，并且继续将 $\oplus m_i$ 看作 $+\delta_i$ 去推式子（仍然以三位为例）
$$
c=p^2(128p+1)\delta_0+p\delta_1+\delta_2
$$
由此类推可以得到 $15$ 位的情况，这边就不多说了。

1
2
3
4
5
6
7
8
9
10
11
c=3235165504936419327001182958857604252407894106191511594689199770239529482330201776634335054024549532136197669522057846845936856432300465191006002492337710
c=c^^16
y=[pow(p,i,1<<512) for i in range(15)]
y=[(-c)%(1<<512)]+y+[p**15*(128*p+1)%(1<<512)]
y=matrix(ZZ,y[::-1]).T
M=block_matrix(ZZ,[
    [identity_matrix(17),y],
    [zero_matrix(1,17),1<<512]
])
M3L=M.LLL()
print(M3L)

但是LLL之后，观察 M3L 的前两行，我们期待的是 $(\delta_0,\delta_1,…,\delta_{15},1,0)$，但却得到了这样两个向量，第二个向量的倒数第三个分量为 $-11$，最后一个分量为 $12$。因此需要将第二个向量的最后一个分量清零，也就是实际的答案为 $\vec v_2-12\vec v_1$。好在幸运的是，这个线性关系还是很显然的，不然如果看出一个不显然的线性关系，又要继续推式子了。

1
2
[   0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    1    0    1]
[ 254  -26  151  -81   47 -159 -145  -30 -167  -61 -137 -183  -85  -30   61  -11    1   12]

那么最后就可以得到最终结果了。（xs，为啥这个题只有 7 解，因为太套娃了吗？然后10月考过这个题，12月CISCN又考？）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vec=M3L[1]-12*M3L[0]
s=[vec[0]]+[-1]*15
mask=(1<<512)-1
x=int(vec[0]<<7)
x = int(x*p&mask)
x ^^= vec[0]
for i in range(1,16):
    x=int((x*p)&mask)
    xbar=x+vec[i]
    chi=xbar^^x
    x=xbar
    s[i]=chi
print(s)
print(x==c)
from hashlib import *
flag = "CBCTF{"+sha256(bytes(s)).hexdigest()+"}"
print(flag)
#[254, 42, 175, 177, 83, 227, 179, 34, 255, 67, 137, 185, 245, 230, 197, 107]
#True
#CBCTF{0d3f156b0c831817e366a437fc80c0e2c14a5e36ebd5c27f9ad835dd9d6a3855}

3.[DASCTF 2408] ezShamir

题目比较简单，还是先看一下

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 os
from random import getrandbits
from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag

class Shamir:
    def __init__(self, pbits, noise_bit, n, m):
        self.pbits = pbits
        self.noise_bit = noise_bit
        self.n = n
        self.m = m
        self.p = getPrime(pbits)
        P.<x> = PolynomialRing(Zmod(self.p))
        self.poly = P([bytes_to_long(sha256(os.urandom(32)).digest()) for i in range(self.n)])

    def sample(self):
        t = getrandbits(self.pbits)
        y = int(self.poly(t))
        noise = getrandbits(noise_bit)
        return (t, y | noise)

    def get_msg(self):
        res = []
        for i in range(self.m):
            res.append(self.sample())
        return res

pbits = 400
noise_bit = 32
n = 100
m = 75

shamir = Shamir(pbits, noise_bit, n, m)
coefficient = shamir.poly()
key = "".join([str(i) for i in list(coefficient)[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
ct = aes.encrypt(pad(flag, 16))

with open("data.txt", "w") as f:
    f.write(str(shamir.p)+'\n')
    f.write(str(shamir.get_msg())+'\n')
    f.write(str(bytes_to_long(ct))+'\n')

题目给出了 $p$ 和 $75$ 组 $(x,y)$，但 $y=f(x)$ 的结果由于或上了一个 $32$ 比特的随机数，因此是带有误差的，要求求 $f(x)$ 的系数。

还是将 $f(x) \mathrm{bitor}\space \delta$ 看作 $f(x)+\delta$，那么我们有 $y=f(x)+\delta$，也就是 $-\delta =f(x)-y$。

那么可以有这样的关系表达式：

3

其中 $V$ 的表示如下（以 $4\times 4$ 为例）：

4

不过注意到，由于 $a$ 是 $256$ 比特， $\delta$ 是 $32$ 比特，因此需要乘一个平衡系数矩阵 $B=\mathrm{diag}(\vec 1_{n},2^{256},2^{224}\times \vec {1} _m)$，对 $MB$ 进行LLL，然后LLL之后，再给 $B$ 除掉，找中间值为 $1$ 的那一行就OK。

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
p=1914861180127910915217161496032452354459288330404267938814385633318816795789745430689392291853522228462459760259540145551
D= #75组(x,y=f(x)+delta)
c=14058554635665083618818231958810639805770645952778992611953881143316377164307777281092527452513347998950720853358361
n,m=100,75
V=[]
Y=[]
for x,y in D:
    V.append([pow(x,i,p) for i in range(n)])
    Y.append(y)
V=Matrix(ZZ,V)
Y=Matrix(ZZ,Y)
M=block_matrix(ZZ,[
    [identity_matrix(n),zero_matrix(n,1),V.T],
    [zero_matrix(1,n),1,-Y],
    [zero_matrix(m,n),zero_matrix(m,1),p*identity_matrix(m)]
])
B=diagonal_matrix([1]*n+[1<<256]+[1<<224]*m)
M=M*B

f=open('out122.txt','w')
from datetime import *
f.write(str(datetime.now())+"\n")
#2025-01-21 22:26:49.809221

M3L=M.LLL()
f.write(str(datetime.now())+"\n")
#2025-01-21 23:57:37.928773

M3L=M3L*B**-1
for vec in M3L:
    if(abs(vec[n])==1):
        f.write(str(vec)+"\n")
        break
coef=vec[:n]*vec[n]
from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES
key = "".join([str(i) for i in coef[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
f.write(str(aes.decrypt(long_to_bytes(c))))
f.close()
#DASCTF{3617af36-7869-6939-3a09-bb8038aea171}\x04\x04\x04\x04

挂在服务器上跑的，真没想到 $176\times 176$ 的矩阵要跑 $91$ 分钟（听说flatter只要八分钟）。

4.[DASCTF 2203]meet me in the middle

题目看着很长，其实也就是一个DSA，每次签名给出 $r,s$ 外，还给出了随机数 $k$ 中间的比特，高 $30$ 比特和低 $30$ 比特被忽略了。

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
from Crypto.Util.number import *
from hashlib import sha256
import socketserver
import signal
import string
from Crypto.Random import random
from Crypto.PublicKey import DSA

table = string.ascii_letters + string.digits
BANNER = br'''
'''

class DigitalSignatureAlgorithm:
    def __init__(self, key):
        self.p = key.p
        self.q = key.q
        self.g = key.g
        self.y = key.y
        self.x = key.x
        self.k = []

    def sign(self, m):
        k = random.StrongRandom().randint(1, self.q - 1)
        self.k.append(k)
        h = bytes_to_long(sha256(m).digest())
        r = pow(self.g, k, self.p) % self.q
        s = inverse(k, self.q) * (h + self.x * r) % self.q
        return r, s

    def verify(self, m, signature):
        r, s = signature
        if (not (1 <= r <= self.q - 1)) or (not (1 <= s <= self.q - 1)):
            return False
        z = bytes_to_long(sha256(m).digest())
        w = inverse(s, self.q)
        u1 = (z * w) % self.q
        u2 = (r * w) % self.q
        v = (pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p % self.q
        return r == v


myDSA = DigitalSignatureAlgorithm(DSA.generate(1024))
MENU = br'''
[1] Sign.
[2] Verify.
[3] Get_public_key.
[4] Get_sth_in_the_middle
[5] Exit.
'''


class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        proof = (''.join([random.choice(table) for _ in range(12)])).encode()
        sha = sha256(proof).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha)
        XXXX = self.recv(prompt=b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True

    def sign(self):
        m1 = b'What you want to know'
        m2 = b'My dear lone warrior'
        signature1 = myDSA.sign(m1)
        signature2 = myDSA.sign(m2)
        self.send(b'Your signature1 is:' + str(signature1).encode())
        self.send(b'Your signature2 is:' + str(signature2).encode())

    def verify(self):
        m = self.recv(b'message:')
        r = int(self.recv(b'r:'))
        s = int(self.recv(b's:'))
        signature = (r, s)
        if m == b"I'm Admin.I want flag.":
            if myDSA.verify(m, signature):
                self.send(b'Hello there.This is what you want.')
                flag = open('flag').read()
                self.send(flag.encode())
            else:
                self.send(b'Who are U?Get out!')
                return False
        else:
            self.send(b'Who are U?Get out!')

    def get_public_key(self):
        self.send(b'p = ' + str(myDSA.p).encode())
        self.send(b'q = ' + str(myDSA.q).encode())
        self.send(b'g = ' + str(myDSA.g).encode())
        self.send(b'y = ' + str(myDSA.y).encode())

    def sth_in_the_middle(self):
        if len(myDSA.k) == 2:
            middle_k0 = int(bin(myDSA.k[0])[2:][30:-30], 2) << 30
            middle_k1 = int(bin(myDSA.k[1])[2:][30:-30], 2) << 30
            self.send(b'middle_k0' + str(middle_k0).encode())
            self.send(b'middle_k1' + str(middle_k1).encode())
        else:
            self.send(b"The time has not come.")

    def handle(self):
        signal.alarm(60)
        self.send(BANNER)
        if not self.proof_of_work():
            self.send(b'Oops,you are wrong. Bye~')
            self.request.close()
        while 1:
            self.send(MENU)
            option = int(self.recv(prompt=b'Give me your option:'))
            if option == 1:
                self.sign()
            elif option == 2:
                self.verify()
                break
            elif option == 3:
                self.get_public_key()
            elif option == 4:
                self.sth_in_the_middle()
            else:
                break
        self.request.close()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 5000

    print("HOST:POST " + HOST + ":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

那么看着很显然，就要从 $k$ 泄露的比特入手，我们可以得到线性关系式：
$$
ks\equiv h+xr\pmod q
$$
由于是两条消息，那就是 $k_1s_1-xr_1-h_1-u_1q=0$ 和 $k_2s_2-xr_2-h_2-u_2q=0$

对上面的式子，区分 $z=k_H,y=k_L$ 和 $k=k_M$，也就是：
$$
2^az+k+y-xr-h-uq=0
$$
注意到 $k$ 在被去掉低 $30$ 位之后，又重新乘上了 $2^{30}$，所以不需要系数。尝试构造线性关系：

5

确定一下平衡系数：$z,y$ 都是 $30$ 位，$x$ 是 $160$ 位，那么 $B=\mathrm{diag}(2^{130},2^{130},2^{130},2^{130},1,2^{800},2^{800},2^{160})$ 。两个 $2^{800}$ 是因为对应的位置为 $0$，因此乘上一个大数可以大力出奇迹（bushi），对 上面的矩阵乘上 $B$，LLL 后再除以 $B$ ，然后找最后三个数字为 $0,0,1$ 的向量就是目标向量。

这么做了一下，看着推导的式子没有问题，LLL后除以 $B$ 没有出现分数，说明数量级是对的，但规约出来的向量的前 4 个分量都是 $33\sim35$ 位，和 $30$ 位有所距离。因此，问题应该是出自 $x$ 这里，考虑消掉 $x$。

消 $x$ 可以得到：
$$
2^{a_1}s_1r_2z_1-2^{a_2}s_2r_1z_2+s_1r_2y_1-s_2r_1y_2+C-uq=0
$$
其中 $C=k_1s_1r_2-h_1r_2-k_2s_2r_1+h_2r_1$。因此，我们的式子就简化，并且 $(z_1,z_2,y_1,y_2)$ 均为 $30$ 位，因此平衡系数也可以小一点：

6

这样只需要给第五列乘 $2^{30}$，最后一列乘 $2^{800}$ 即可，我们就可以得到最终的 $z_1,z_2,y_1,y_2$，恢复 $k$ 的所有比特，然后求出私钥 $x$ 并得到最终的签名就OK了。

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
from pwn import *
from hashlib import sha256
from sage.all import *
from Crypto.Util.number import *
context.log_level = 'sdebug' 
sh=remote('node5.buuoj.cn',25739)
sh.recvuntil(b'sha256(XXXX+')
s16=sh.recvuntil(b')')[:-1]
sh.recvuntil(b'==')
s64=sh.recvline(keepends=False).strip()
def getyzm(s16,s64):
	table='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
	for i in table:
		for j in table:
			for k in table:
				for l in table:
					if(sha256((i+j+k+l+s16).encode()).hexdigest()==s64):
						return i+j+k+l
print(s16)
print(s64)
yzm=getyzm(s16.decode(),s64.decode())
sh.sendline(yzm.encode())
sh.recvuntil(b':')
sh.sendline(b'1')
sh.recvuntil(b's:')
r1,s1=eval(sh.recvline(keepends=False))
sh.recvuntil(b's:')
r2,s2=eval(sh.recvline(keepends=False))
print(r1,s1)
print(r2,s2)

sh.recvuntil(b':')
sh.sendline(b'3')
arr=[]
for i in range(4):
	sh.recvuntil(b'=')
	arr.append(eval(sh.recvline(keepends=False)))
p,q,g,y=arr
print(p,q,g,y)

sh.recvuntil(b':')
sh.sendline(b'4')
sh.recvuntil(b'middle_k0')
k1m=eval(sh.recvline(keepends=False))
sh.recvuntil(b'middle_k1')
k2m=eval(sh.recvline(keepends=False))
print('{:040x}'.format(k1m),'{:040x}'.format(k2m))
a1,a2=k1m.bit_length(),k2m.bit_length()
m1 = b'What you want to know'
m2 = b'My dear lone warrior'
h1=bytes_to_long(sha256(m1).digest())
h2=bytes_to_long(sha256(m2).digest())



Ax1=2**a1*s1*r2%q
Ax2=(-2**a2*s2*r1)%q
Ay1=s1*r2%q
Ay2=(-s2*r1)%q
C=(k1m*s1*r2-h1*r2-k2m*s2*r1+h2*r1)%q
K=2**500
M=matrix([
	[1,0,0,0,0,Ax1],
	[0,1,0,0,0,Ax2],
	[0,0,1,0,0,Ay1],
	[0,0,0,1,0,Ay2],
	[0,0,0,0,1,-C],
	[0,0,0,0,0,q],
])
B=diagonal_matrix([1,1,1,1,2**30,2**500])
M3L=(M*B).LLL()*(B**-1)
for vec in M3L:
	if(vec[-1]==0 and abs(vec[-2])==1):
		break
z1,z2,y1,y2=(abs(i) for i in vec[:4])
k1=z1*2**a1+k1m+y1
k2=z2*2**a2+k2m+y2

x=(k1*s1-h1)*inverse(r1,q)%q
xchk=(k2*s2-h2)*inverse(r2,q)%q
print(x,xchk)
assert x==xchk
assert pow(g,x,p)==y


msg=long_to_bytes(0x49276d2041646d696e2e492077616e7420666c61672e)

h3=bytes_to_long(sha256(msg).digest())
sh.recvuntil(b':')
sh.sendline(b'2')
sh.recvuntil(b'e:')
sh.send(msg)
#k=1
sh.recvuntil(b'r:')
g1=g%p%q
sh.sendline(str(g1).encode())
sh.recvuntil(b's:')
sh.sendline(str((h3+x*g1)%q).encode())
print(sh.recvall(timeout=600))

突然发现，几个DSA翻来覆去就那一个线性关系式，感觉好像开始套路化了，基本都是用这个固定的线性关系式LLL的。。。

5.[VNCTF2022] Are You Admin 1

又是一个DSA：

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
from Crypto.Util.number import *
from hashlib import *
from secret import secretkey,flag,ezmath_flag
import socketserver
import os
import signal
import string
assert len(bin(secretkey)) == 169

table = string.ascii_letters+string.digits

class PseudoRandomNumbersGenerators:
    def __init__(self,seed1,seed2):
        self.state_a = seed1
        self.state_b = seed2
        self.a = getRandomNBitInteger(160)
        self.b = getRandomNBitInteger(160)
        self.c = getRandomNBitInteger(160)
        self.M = 1 << 512

    def GetNext(self):
        ret = (self.state_a * self.a + self.state_b * self.b + self.c) % self.M
        self.state_a = self.state_b
        self.state_b = ret
        return ret

    def GetSomethingUseful(self,admin):
        if admin == True:
            return self.a,self.b,self.c
        else:
            return "You can't get anything here!Get out!"
    
    def choice(self,input):
        length = len(input)
        tmp = self.GetNext() % length
        return input[tmp]

class DigitalSignatureAlgorithm:
    def __init__(self,RANDOM):
        self.p = 8945295668911819059540208265461979177678201229057426412681001447446107919117765962027889488459965388254641301806100385155760254966914075104367813869235667
        self.q = 4472647834455909529770104132730989588839100614528713206340500723723053959558882981013944744229982694127320650903050192577880127483457037552183906934617833
        self.g = 3
        self.Random = RANDOM

    def verify(self, m, y, sig):
        r, s = sig
        if (not (1 <= r <= self.q - 1)) or (not (1 <= s <= self.q - 1)): 
            return False
        z = bytes_to_long(sha256(m).digest())
        w = inverse(s, self.q)
        u1 = (z * w) % self.q
        u2 = (r * w) % self.q
        v = (pow(self.g, u1, self.p) * pow(y, u2, self.p)) % self.p % self.q
        return r == v

    def sign(self, m , x):
        z = bytes_to_long(sha256(m).digest())
        while 1:
            k = self.Random.GetNext() % self.q 
            r = pow(self.g , k, self.p) % self.q
            s = (inverse(k, self.q) * (z + x * r)) % self.q
            if (s != 0) and (r != 0) :
                return (r, s)

RANDOM = PseudoRandomNumbersGenerators(getPrime(120),getPrime(120))
DSA = DigitalSignatureAlgorithm(RANDOM)
x = secretkey
y = pow(DSA.g,x,DSA.p)

MENU = br'''
[S]ign.
[V]erify(or get flag).
[I]dentify.
[E]xit.
'''

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b''):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        proof = (''.join([RANDOM.choice(table)for _ in range(20)])).encode()
        sha = sha256(proof).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
        XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True

    def sign(self):
        m0 = b'dawn'
        m1 = b'whisper'
        m2 = b'want flag'
        sign0 = DSA.sign(m0,x)
        sign1 = DSA.sign(m1,x)
        sign2 = DSA.sign(m2,x)

        self.send(b'sign of (dawn) is: '      + str(sign0).encode())
        self.send(b'sign of (whisper) is: '   + str(sign1).encode())
        self.send(b'sign of (want flag) is: ' + str(sign2).encode())

    def identify(self):
        rec_key = self.recv(b'flag of ezmath is :')
        ret = RANDOM.GetSomethingUseful(rec_key == ezmath_flag)
        self.send(str(ret).encode())

    def verify(self):
        msg = self.recv(b'msg:')
        r = int(self.recv(b'r:'))
        s = int(self.recv(b's:'))
        sig = (r,s)
        if msg == b"I'm Admin.Plz give me flag!":
            if DSA.verify(msg,y,sig):
                self.send(b'Yes Sir!Thank you Sir!')
                return flag
            else:
                self.send(b'Who are U?Get out!')
                return False
        else:
            if DSA.verify(msg,y,sig):
                self.send(b'Yeah!You sign successfully!')
                return os.urandom(32)

    def handle(self):
        proof = self.proof_of_work()
        if not proof:
            self.request.close()
        signal.alarm(60)
        chance = 0
        while 1:
            self.send(MENU)
            option = self.recv(b'\n==plz give me your option==\n[IN]:')
            if option == b'S':
                if chance == 0:
                    self.sign()
                    chance += 1
                else:
                    self.send(b'ERROR! You only have one time!')
            elif option == b'V':
                ret = self.verify()
                if ret :
                    self.send(b'Your Flag is :' + ret)
                break
            elif option == b'I':
                self.identify()
            else:
                break
        self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10004
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

从题目中可以得到的信息为：私钥 $x$ 为 $167$ 比特，随机数 $k$ 为 LCG 生成，其表达式为 $x_2=ax_0+bx_1+c$，题目会给出 $3$ 条内容的签名结果。

不过需要注意的是，LCG 的模数为 $2^{512}$，而 $q$ 为 $511$ 位素数。 $x_0,x_1$ 两个种子值为 $120$ 位，$a,b,c$ 系数为 $160$ 位，那么我们可以分析出：$k_0,k_1$ 的数量级分别为 $2^{281},2^{441}$ ，而 $k_2$ 经过了取模，并且使用时还经历了两次取模，先模 $2^{512}$ 再模 $q$。不过好在，由于 $q$ 是 $511$ 位素数，这就意味着对 $2^{512}$ 取模后，最多只会减去 $2$ 个 $q$。

题目中的 $a,b,c$ 其实是给出的，那个验证的flag题目给出了，可以忽略这一部分。

那么做了这么多DSA了，里面线性关系式，还是很明显的：我们有三组 $k_is_i-xr_i-u_iq=h_i$，其中 $i=0,1,2$ 。和一组 $ak_0+bk_1+c-2^{512}u_3-u_4q=0$ 。其中 $u_4$ 取值为 $0,1,2$。那么可以构造一个 $9\times9$ 的线性关系矩阵，乘上平衡系数，就OK了。

然后LLL没得到任何结果，调了 $k_{0,1,2}$ 的数量级也没啥用。但线性关系肯定是没问题的，一个很普通的DSA，你还能有别的线性关系吗？

卡了3h，然后看到了这个：VNCTF2022 Crypto WriteUp | tl2cents blog (tanglee.top)，发现这个题要用CVP解。因为线性关系就那么一个，解不出来说明目标向量并非短向量，但如果能够抓住目标向量的显著特征，那么可以考虑CVP，其构造的矩阵是这样的（LLL前需要转置一下，因为Sage是行向量）

7

可以发现他这边的平衡系数很有意思：我们刚才分析了，他这个 $n_5$ 相当于我上面的 $u_5$，其取值只有 $0,1,2$，数量级为 $2$，而$x,k_0,k_1,k_2$ 的数量级分别为 $2^{169},q,q,q$，（P.S. $x$ 的数量级为 $2^{167}$），因此这样平衡之后，其他的数值就基本为 $1$ 了。

此外，LLL之后，向量之间有不错的正交性，因此CVP可以通过简单的舍入法去调整，我们只需要求出格中距离 $(h_0,h_1,h_2,-c,1,1,1,1,1)$ 最近的向量就OK了，得到的向量中可能有私钥 $x$。

本地测了一波，测试使用的私钥为：
$$
x=174847216550444586801265996907385021425341123437671
$$
这是一个素数。如果LLL能够直接得到私钥，那么根据素数的性质和Sage中基本都用分数表示的特点，我们可以在LLL后，在矩阵中直接得到私钥 $x$，但测试后发现，LLL的结果找不到私钥 $x$。

8

而求CVP的函数也很简单，就是再来一次施密特正交化，对于目标向量 $\vec w$ 和格中向量 $\vec g$，每次对 $\vec w$ 减去 $\left\lfloor\dfrac{\vec w\cdot \vec g}{\vec g^2}\right\rceil \vec g$ 即可。

1
2
3
4
5
6
7
8
def BabaisClosestPlaneAlgorithm(L, w):
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round((w*G[i]) / G[i].norm() ** 2) * L[i]
        i -= 1
    return t - w

在得到这个之后，那么最后解题也就不难了，感觉这个题难点就是CVP：

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
from pwn import *
from hashlib import sha256
from sage.all import *
from Crypto.Util.number import *
sh=remote('node5.buuoj.cn',25626)
sh.recvuntil(b'sha256(XXXX+')
s16=sh.recvuntil(b')')[:-1]
sh.recvuntil(b'==')
s64=sh.recvline(keepends=False).strip()
def getyzm(s16,s64):
	table='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
	for i in table:
		for j in table:
			for k in table:
				for l in table:
					if(sha256((i+j+k+l+s16).encode()).hexdigest()==s64):
						return i+j+k+l
print(s16)
print(s64)
yzm=getyzm(s16.decode(),s64.decode())
sh.sendline(yzm.encode())
sh.recvuntil(b'[IN]:')
sh.sendline(b'I')
sh.recvuntil(b':')
sh.sendline(b'vnctf{m4th_5tr#c7Ur3_c4n_b3_e@s&!}')
a,b,c=eval(sh.recvline())
sh.recvuntil(b'[IN]:')
sh.sendline(b'S')
sh.recvuntil(b'is:')
r1,s1=eval(sh.recvline(keepends=False).strip())
sh.recvuntil(b'is:')
r2,s2=eval(sh.recvline(keepends=False).strip())
sh.recvuntil(b'is:')
r3,s3=eval(sh.recvline(keepends=False).strip())
q=4472647834455909529770104132730989588839100614528713206340500723723053959558882981013944744229982694127320650903050192577880127483457037552183906934617833
m1 = b'dawn'
m2 = b'whisper'
m3 = b'want flag'
h1,h2,h3=[bytes_to_long(sha256(i).digest()) for i in [m1,m2,m3]]
print(h1,h2,h3)
M = matrix(
    [
        [-r1, s1,  0,  0,  q, 0, 0, 0,0],
        [-r2,  0, s2,  0,  0, q, 0, 0,0],
        [-r3,  0,  0,  s3,  0, 0, q, 0,0],
        [0,  a,  b,  -1,  0, 0, 0, 2**512,q],
        [Rational(f'2/{2**169}'),  0,  0,   0,  0, 0, 0, 0,0],
        [0, Rational(f'2/{q}'),  0,   0,  0, 0, 0, 0,0],
        [0,  0, Rational(f'2/{q}'),   0,  0, 0, 0, 0,0],
        [0,  0,  0, Rational(f'2/{q}'),  0, 0, 0, 0,0],
        [0,  0,  0, 0,  0, 0, 0, 0,1]
    ]).T


M=matrix(M)
M3L=M.LLL()

def BabaisClosestPlaneAlgorithm(L, w):
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round((w*G[i]) / G[i].norm() ** 2) * L[i]
        i -= 1
    return t - w


C = vector([h1, h2, h3, -c, 1, 1, 1, 1,1])  # target vector
A = BabaisClosestPlaneAlgorithm(M3L, C)
print(A)
x = A[4] / Rational(f'2/{2**169}')

print(x)
g=3
k=1
r=g
msg=b"I'm Admin.Plz give me flag!"
h=bytes_to_long(sha256(msg).digest())
s=((h + x * r))% q
sh.recvuntil(b'[IN]:')
sh.sendline(b'V')
sh.recvuntil(b'msg:')
sh.sendline(msg)
sh.recvuntil(b'r:')
sh.sendline(str(r).encode())
sh.recvuntil(b's:')
sh.sendline(str(s).encode())
print(sh.recvall(timeout=500))
#print(s)
#print(M3L)
#sh.interactive()

6.[VNCTF2022] crypto_sign_in_4

先看一眼题目：

题目给出了素数 $p$，其中 $2$ 在 $\mathbb F_p$ 的阶为素数，然后题目允许你选择一个 $m$，然后回给你返回 $c_1=2^x$ 和 $c_2=2^{mx}$，其中 $x$ 未知。 

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
from Crypto.Util.number import *
from random import getrandbits
from uuid import *
welcome="Welcome to VNCTF 2023!Hope you can enjoy this challenge!"
description='''These days DengFeng want to provide a surprise for Deebato.\n
So he come up with an idea...\n
That is...\n
Designing a DLP!\n
Namely Deebato Love Problem!'''
begin='''So let's go!\n
In 1997, I learned to drive a car...\n'''

def hello():
    print(welcome)
    print(description)
    print(begin)


def gen():
    a=2
    while True:
        p=getPrime(90)
        order=GF(p)(a).multiplicative_order()
        if isPrime(int(order)):
            return a,p,order
            

def get_msg(m,a,p,order):
    secret=getrandbits(85)
    c1=pow(a,secret,p)
    c2=pow(a,pow(secret,m,order),p)
    return secret,c1,c2


def main():
    alarm(300)
    hello()
    a,p,order=gen()
    print("OOOOOOh!I will give you something useful!")
    print(f"a = {a}")
    print(f"p = {p}")
    m=int(input("Please give me your choice:"))
    secret,c1,c2=get_msg(m,a,p,order)
    print("OK,here is my gift.")
    print(f"c1 = {c1}")
    print(f"c2 = {c2}")
    ticket=int(input("Please give me the secret:"))
    if ticket==secret:
        print("OKOK,it seems that you know Deebato Love Problem well.Here is my flag")
        print('flag{'+str(uuid4())+'}')
    else:
        print("Sorry!You don't understand Deebato Love Problem not at all!I can't give you flag!")


try:
    main()
except Exception as e:
    print(f"Error : {e}")

题目还给出了提示：

Hint1: cheon discrete log attack

根据关键词 Google 了一圈，发现 eprint 上编号为 2008-300 的论文给出了算法：

11

不过需要注意的是：这里 $P$ 是椭圆曲线上的点，而我们这边是乘法群上的运算，因此 $\alpha P$ 应该写为 $2^\alpha$，然后 $p$ 在算法中表示的是 $P$ 的阶数，但题目中 $p$ 是模数，$2$ 在 $\mathbb F_p$ 上的阶为素数，在这里我们设 $2$ 在 $\mathbb F_p$ 上的阶为 $q$。

那么在实际编程的时候， 上面所有的 $p$ 都要换成 $q$，$P$ 换成 $2$，$P_1,P_2$ 对应 $c_1,c_2$。因此，我们需要在 $\mathbb F_q$ 上找到原根 $g$，且将 $q-1$ 尽可能地分解成两个近似相等的数值（不一定是素数），其中一个作为 $d$，用于BSGS。 $p$ 是 $90$ 位，$q$ 可能略低于 $90$ 位，那么这样算下来，复杂度大概就在 $2^{22}$ 左右了，题目的限时为 5 分钟，基本可以接受。

并且，$q$ 长度不超过 $90$ 意味着我们可以高效对 $q -1$ 分解来获取 $d$，以及寻找 $q$ 的原根。

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
def findd(x):
    L=[]
    fcp=list(factor(x-1))
    for u,v in fcp:
        L=L+v*[u]
    xbits=x.nbits()
    bound=xbits>>1
    d=Integer(1)
    for i in L:
        dbits=d.nbits()
        dibits=(d*i).nbits()
        if(abs(dbits-bound)<abs(dibits-bound)):
            print(f'factor 1: of {dbits}/{xbits} bits:{d}')
            print(f'factor 2: of {((x-1)//d).nbits()}/{xbits} bits:{(x-1)//d}')
            return d,(x-1)//d,dbits,((x-1)//d).nbits()
        else:
            d=d*i
def findgen(prime):
    assert isPrime(prime)
    g=1
    fcp=list(factor(prime-1))
    while(1):
        g=g+1
        res=True
        for x,_ in fcp:
            if(pow(g,(prime-1)//x,prime)==1):
                res=False
                break
        if(res==True):
            return g
sh.recvuntil(b'a =')
a=eval(sh.recvline())
sh.recvuntil(b'p =')
p=eval(sh.recvline())
print(a,p)
q=GF(p)(a).multiplicative_order()
d,_,bits1,bits2=findd(q)
if(max(bits1,bits2)>47):
    sh.close()
    raise ValueError(f"Find bits {max(bits1,bits2)} that exceed 47!")
g0=findgen(q)

然后就是两个 BSGS 了，注意 BSGS 存入字典的方式，别存倒了就OK！

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
#BSGS1
from tqdm import *
D=dict()
ginv=pow(g,q-2,q)
for i in tqdm(range(d1)):
    u=i
    v=pow(c2,pow(ginv,i,q),p)
    D[v]=u
u1,v1=None,None
for i in tqdm(range(d1)):
    v=pow(2,pow(g,d1*i,q),p)
    if(D.get(v,None)):
        u1,v1=D.get(v,None),i
        print(u1,v1)
        break
#BSGS2
k0=d1*v1+u1
d2=int(1+sqrt(d).n())
D=dict()
g0inv=pow(g0,q-2,q)
p1divd=(p-1)//d
for i in tqdm(range(d2)):
    u=i
    v=pow(c1,pow(g0inv,u*p1divd,q),p)
    D[v]=u
u2,v2=None,None
for i in tqdm(range(d2)):
    v=pow(2,pow(g0,k0+d2*i*p1divd,q),p)
    if(D.get(v,None)):
        u2,v2=D.get(v,None),i
        print(u2,v2)
        break
ans=pow(g0,k0+(d2*v2+u2)*p1divd,q)

由于远程环境G了，那么就本地测一下，这里可以多次尝试，确保 $q-1$ 被均匀分解，如果做不到可以重连换一组数据。

当然，也可以多次自动重连，直到成功再结束程序，平均下来，大概尝试 20 次能有一次成功（不知为啥，发现有的时候在最后一步也不一定成功）

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
from pwn import *
from sage.all import *
from Crypto.Util.number import *
from tqdm import *
#context.log_level = 'debug' 

def findd(x):
    L=[]
    fcp=list(factor(x-1))
    for u,v in fcp:
        L=L+v*[u]
    xbits=x.nbits()
    bound=xbits>>1
    d=Integer(1)
    for i in L:
        dbits=d.nbits()
        dibits=(d*i).nbits()
        if(abs(dbits-bound)<abs(dibits-bound)):
            print(f'factor 1: of {dbits}/{xbits} bits:{d}')
            print(f'factor 2: of {((x-1)//d).nbits()}/{xbits} bits:{(x-1)//d}')
            return d,(x-1)//d,dbits,((x-1)//d).nbits()
        else:
            d=d*i
def findgen(prime):
    assert isPrime(prime)
    g=1
    fcp=list(factor(prime-1))
    while(1):
        g=g+1
        res=True
        for x,_ in fcp:
            if(pow(g,(prime-1)//x,prime)==1):
                res=False
                break
        if(res==True):
            return g
def run(sh):
    
    sh.recvuntil(b'a =')
    a=eval(sh.recvline())
    sh.recvuntil(b'p =')
    p=eval(sh.recvline())
    print(a,p)
    q=GF(p)(a).multiplicative_order()
    
            
    d,_,bits1,bits2=findd(q)
    if(max(bits1,bits2)>=47):
        sh.close()
        raise ValueError(f"Find bits {max(bits1,bits2)} that exceed 47!")
    sh.recvuntil(b'ce:')
    sh.sendline(str(d).encode())
    sh.recvuntil(b'=')
    c1=eval(sh.recvline(keepends=False))
    sh.recvuntil(b'=')
    c2=eval(sh.recvline(keepends=False))
    print(c1,c2)
    g0=findgen(q)
    g=pow(g0,d,q)
    d1=(sqrt((q-1)/d))
    d1=int(d1.n()+0.5)
    #---------BSGS1---------
    D=dict()
    ginv=pow(g,q-2,q)
    for i in tqdm(range(d1)):
        u=i
        v=pow(c2,pow(ginv,i,q),p)
        D[v]=u
    u1,v1=None,None
    for i in tqdm(range(d1)):
        v=pow(2,pow(g,d1*i,q),p)
        if(D.get(v,None)):
            u1,v1=D.get(v,None),i
            print(u1,v1)
            break
    k0=d1*v1+u1
    d2=int(1+sqrt(d).n())
    D=dict()
    g0inv=pow(g0,q-2,q)
    p1divd=(p-1)//d
    #---------BSGS2---------
    for i in tqdm(range(d2)):
        u=i
        v=pow(c1,pow(g0inv,u*p1divd,q),p)
        D[v]=u
    u2,v2=None,None
    for i in tqdm(range(d2)):
        v=pow(2,pow(g0,k0+d2*i*p1divd,q),p)
        if(D.get(v,None)):
            u2,v2=D.get(v,None),i
            print(u2,v2)
            break
    ans=pow(g0,k0+(d2*v2+u2)*p1divd,q)
    
    sh.sendline(str(ans).encode())
    print(sh.recvall(timeout=600))
def run2():
    sh=None
    try:
        sh=process(['sage','task9.sage'])
        run(sh)
        return 1
    except:
        sh.close()
        return 0
Tim=0
while(1):
    Tim+=1
    print(f'Running on {Tim}th time')
    if(run2()):
        break

10

这种论文题，感觉主要还是论文实现。

9.总结

BUU继续上分ing，当年自己最高好像是Crypto区第 6 来着？然后两年没打，跌到了 35，寒假才重新回来继续打，上到了 15 名！

xs，这时间跨度，也没谁了

13

还有，Explore MT19937 经过 3 年半，更新了一些内容，补充了任意 19937 个比特的情况，具体请访问那篇博文内容。

14

CTFSeason4
#ExpLog
25Jan3
http://example.com/2025/01/26/25Jan3/
作者
huangx607087
发布于
2025年1月26日
许可协议