MoeCTF2026 wp

MoeCTF2026 wp

Crypto

moeSign1n

阅读代码,题目逻辑其实很简单:

设m = b'MoeCTF 2026'

菜单1:加密除了m的任意内容并返回密文

菜单2:提交一个密文,解密后是m给你flag

所以题目就是要在不直接加密m的原文的情况下加密m

这里利用rsa的乘法同态性就能做到

我们把m 拆成m1*m2,分别加密m1,m2,再$E(m_1) \cdot E(m_2) $

就在不直接加密m的情况下得到m的密文


from Crypto.Util.number import *
from gmpy2 import *
from pwn import *

m = b'MoeCTF 2026'

io = remote('127.0.0.1', 57842)
m1 = bytes_to_long(m) // 2
m1 = long_to_bytes(m1).hex()
m2 = long_to_bytes(2).hex()
io.recv()
io.sendline(str(1))
io.recv()
io.sendline(str(m1).encode())
c1 = int(io.recvline().strip().decode())
print(c1)
io.recv()
io.sendline(str(1))
io.recv()
io.sendline(str(m2).encode())
c2 = int(io.recvline().strip().decode())
print(c2)
c = c1 * c2
io.recv()
io.sendline(str(2))
io.recv()
io.sendline(str(c).encode())
flag = io.recv()

print(flag)

wsl_Sign1n

sage是个好东西,大家可以多多研究一下,密码手必备神器

justXOR

读题发现是xor加密,题目给了密钥key的生成逻辑,我们尝试还原key就能解密

key生成逻辑

因为初始状态和生成方法都已知,所有看完代码的第一反应就是再把gen_key()函数再跑一次就能拿到key

但是马上就会发现问题:n数字过大,跑完n轮循环几乎不可能,所以另寻他法求解key

我们仔细分析代码:发现这个生成key的式子就是一个数列的递推式,我们求出这个数列的通项公式就能不要跑完range(n-1)就能拿到key

from Crypto.Util.number import long_to_bytes

# just a normal big prime
M = 2039129633208009090414901212304234091626233923923301042398416489123719065081065776033127561876033127924471

n = 10**25
key = 2*pow(3,n-1,M) - 1

enc = b'it\x0bM\xfa-\xe3T{\xaa\x0f@\xa2\xf1@\xbd\x86e\x85\x9e\xfcp_o\x8f\xccd\x13\xceW\x13\x14\x11\x055b\xcbk\xa0'
flag = bytes([x ^ y for x, y in zip(enc, long_to_bytes(key))])
print(flag)

ez_f3mr4t

这个题出发点肯定在q = next_prime(p ^ ((1<<512)-1))

设 m = 1<<512,t = p^m 不难发现t其实就是p的按位取反,进一步我们可以发现:p + t = M

由此我们可以分析出p,q大致范围

题目中:

q=next_prime(M−p)q

所以存在一个很小的 gap,使得:

q=M−p+gap

于是:

p+q=M+gap

令:

S=M+gap

那么 p,q 是方程:

x2−Sx+n=0

的两个根,判别式为:

Δ=S2−4n

当 gap 正确时,\Delta 是完全平方数。

枚举很小的奇数 gap 即可分解 n,然后解 RSA。

from Crypto.Util.number import *
from gmpy2 import *

e = 65537
n = 0x308244e7a7de386723c92ba62e35bc22c3ec1b93023e1551408344a4ba31c6203da849aedee0cadf26a3442f9fd652f7d97c053a3f2c298eab6c0f0c2d0b4642a81765ddb00b690425eb212d5520327ac2d53a22922448399fecb54fbc04dbb68fa33fee7666cb9e05278b5f5f1330b3918d3a7def580fcc00f6f596f16eba3b
c = 0x13a77e34f09b8a2291cdb397ea0e5cb9e86f691c6565b35c76e6bb6248b67db24315e22fe1dc5321a8820320cdd9b51e3d431459aac2213948f4fbf01c4ce974428d1ed745b2c06f8aa92b22dfede3b7ceb59aa4eb22467129f55b60037a1a2de9b37f25fda3fe40323fccc7c8bbdd4446096b37cef4138337ee9a04c2e3d5fd
M = (1 << 512) - 1
# p = getStrongPrime(512)
# q = nextprime(M - p)
for k in range(1,100000):
delt = pow(M + k,2) - 4*n
if iroot(delt,2)[1]:
p = (M + k + iroot(delt,2)[0]) // 2
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

ez_fermat

给了一个hint,从hint入手

因为 a*p + b ≡ b (mod p),所以:

plain

Text
hint ≡ (a*p + b)^q ≡ b^q (mod p)

第二步:关键变形 —— 把未知的 q 换成已知的 n

由费马小定理,模 p 时指数可以对 p-1 取模。注意 n = pq,而 p ≡ 1 (mod p-1),所以:

Text
n = p*q ≡ 1*q = q (mod p-1)

于是:

Text
b^n ≡ b^q ≡ hint (mod p)

也就是说 p 整除 (b^n − hint),而 b、n、hint 全是已知量

第三步:gcd 出 p,由此分解n

p = gcd(n, pow(b, n, n) - hint)
from Crypto.Util.number import *
from gmpy2 import *

n = 15962603324053600624662899467930954606237037554051572101066176482327650464579501876010780067612122315010349894395035821617153081982429716234378979239633769779503395609504372912298014522344609346937078959678893005192469085672940628091531228571447786013091492389216237976408692434723698967667324605921896928717731731591488800520224411239128106892402734198486634978989319563704879076976307439748456769245703782902660583833942684475506024284563786886608632662629581206716450648212025254862836883526055933841863348546872473877054469843468332542834452213365868510001991952142536759384940216228753729399187149594010090304067
c = 4281919068424886012214413435957379635517466043647380176350221253614623990599452495938689758001256045320061491376355750164051326734927905972267385611552894838140009898450267453653097466286838460889968896032216593811984942511165228143089457988630435810304672454147149556110542203084341901598519587611096893432307236558970264536719689039318023572680185246871600989317992399536729717958072642243834689061928667913495884682029212015071613730401843271641197254089900489231738518876415262001687002012972665662364940457678043829768126263211295258465202419686281997749861180041439407866197636369525192971926660559217573713931
hint = 8894364790280693556124457666776501614023509475927164016497858629229215409128965020674642063592770935057209719989294548263833927477972267267951214184209046168773196349537926982123382473522039515862138755400978350128128233701795758152143272668945626119949376162344749760499165210224412751964322150037199401111258869439672762883792051818112500032192131948644557686621759867629440824691768395882797936616839572906841251000681054283164497419314938363871139253289134458466501698235039234455154975165111296198209091586550990873209534256929400689017034618807232508747449076486852786199340704419120538526208691066898035362296

a, b = 0x2025, 0x2026
e = 65537
p = gcd(pow(b,n,n) - hint,n)
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

the_KEY_of_DES

看代码知道题目要求我们输入两个des的key,而且使用这两个key加密同一随机明文,要求输出同一密文。

既然让我们构造特定的密钥,那我们就从密钥下手

我们知道,真正参与加密运算的不是初始key,而是初始key扩展出来的16个子密钥

那么思路就是找key1,key2,使其扩展后的子密钥完全相同就行

梳理一下子密钥的生成的过程,第一步pc-1置换就能初见端倪:64位的密钥每八位就会有一个奇偶校验位,校验位的值在生成子密钥的过程中会被扔掉,与最终的16个子密钥无关

那么就诞生了一个想法:随便弄一个64位密钥key1,改动第8位(奇偶校验位之一)形成key2

这两个key生成的子密钥完全相同,加密同一密文的结果也会相同**
**

key1 = 0x123456789abcdef

key1 = [0x01,0x23,0x45,0x67,0x89,0xAB,0xCD,0xEF]
bits64 = []
for b in key1:
for i in range(7, -1, -1):
bits64.append((b >> i) & 1)

print(bits64)
#[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1]

把第八位的1改成0再变回16进制

bits64 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1]
out = bytearray()
for i in range(0,64,8):
val = 0
for j in range(8):
val = (val << 1) | bits64[i+j]
out.append(val)

key2 = "0x" + out.hex()
print(key2)
**#0x0023456789abcdef**

把两个key发回服务器就能拿flag

moePoly1

题目给了一个多项式。其中多项式的系数就是flag,恢复系数就能恢复flag

题目多项式:

f(x)=∑k=0n−1ck⋅xk,ck=ord(flag[k])⋅2248(modp)f(x) = \sum_{k=0}^{n-1} c_k \cdot x^k,\quad c_k = \mathrm{ord}(flag[k]) \cdot 2^{248} \pmod{p}

把ord(flag[k])记作aka_k

简化一下:

f(x)=2248∑k=0n−1ak⋅xkf(x) = 2^{248} \sum_{k=0}^{n-1} a_k \cdot x^k

我们需要恢复aka_k

用拉格朗日插值直接秒,没什么好说的

sage有封装好的函数

from Crypto.Util.number import *
import uuid
from pwn import *
from gmpy2 import *

io = remote("127.0.0.1", 55450)
io.recvuntil(b'p = ')
p = io.recvline()
p = int(p.strip().decode())
print(p)
points = []

inv = inverse(2**248,p)

for i in range(1,45):
io.recvuntil(b'choice: ')
io.sendline(b'1')
io.recvuntil(b'input x: ')
io.sendline(str(i).encode())
data = int(io.recvline().strip()) * inv
point = (i, data)
points.append(point)


R.<x> = PolynomialRing(GF(p))
f = R.lagrange_polynomial(points)
print(f)
cs = f.list()
flag = ''.join(chr(x) for x in cs)

print(flag)

XOR_revenge

惹前面那个一样的思路,求通项拿key就行

from Crypto.Util.number import *

M = 2**521 - 1
n = 10**25

COEFF = [3, 5, 7, 11, 13, 17, 36]
INIT = [1, 2, 3, 4, 5, 6, 7]

def mat_mul(a, b, mod):
rows = len(a)
inner = len(b)
cols = len(b[0])

return [
[
sum(a[i][k] * b[k][j] for k in range(inner)) % mod
for j in range(cols)
]
for i in range(rows)
]

def mat_pow(base, exp, mod):
size = len(base)
result = [[int(i == j) for j in range(size)] for i in range(size)]

while exp:
if exp & 1:
result = mat_mul(result, base, mod)
base = mat_mul(base, base, mod)
exp >>= 1

return result

def gen_key_fast(n):
if n < 7:
return INIT[n]

# 状态: [F(k), F(k-1), ..., F(k-6)]
transition = [
COEFF[:], # 计算下一项
[1, 0, 0, 0, 0, 0, 0], # F(k) 下移
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 0],
]

power = mat_pow(transition, n - 6, M)
initial_state = [[INIT[6 - i]] for i in range(7)]

return mat_mul(power, initial_state, M)[0][0]
key = gen_key_fast(n)
print(key)
enc = b'lz\xb0T\xeb\x18\xec\xcfQ\x8bv#\x17t\xf0\xc7\xdaM\x87\xf5sr\xef\xd0\xfc3.\xdc%\xaaf\xf4\xd1\xc8\xb7\xef'

flag = bytes([x ^ y for x, y in zip(enc, long_to_bytes(key))])
print(flag)

ez_lattice

分析

题目给出的信息太简单了:ci=μai+eic_i=\mu a_i+e_i

已知cic_i求解明文aia_i

未知量太多了,我们先尝试消元

μ\mu在本题中很明显成为一个孤儿变量,我们尝试消去:

ci−ei=μaic_i - e_i=\mu a_i

我们两两相比,消去μ\mu:

{a1(c0−e0)=a0(c1−e1)a3(c2−e2)=a2(c3−e3)a5(c4−e4)=a4(c5−e5)\begin{cases} a_1(c_0-e_0)=a_0(c_1-e_1)\\ a_3(c_2-e_2)=a_2(c_3-e_3)\\ a_5(c_4-e_4)=a_4(c_5-e_5) \end{cases}

求和再整理:

$\boldsymbol{
a_1 c_0 - a_0 c_1 + a_3 c_2 - a_2 c_3 + a_5 c_4 - a_4 c_5

a_1 e_0 - a_0 e_1 + a_3 e_2 - a_2 e_3 + a_5 e_4 - a_4 e_5
}$

由此想到造格:

$\begin{pmatrix}
a_0 , a_1 , a_2 , a_3 , a_4 , a_5
\end{pmatrix}
\begin{pmatrix}
s & 0 & 0 & 0 & 0 & 0 & c_0 \
0 & s & 0 & 0 & 0 & 0 & c_1 \
0 & 0 & s & 0 & 0 & 0 & c_2 \
0 & 0 & 0 & s & 0 & 0 & c_3 \
0 & 0 & 0 & 0 & s & 0 & c_4 \
0 & 0 & 0 & 0 & 0 & s & c_5
\end{pmatrix}

\Big(, sa_0,, sa_1,, sa_2,, sa_3,, sa_4,, sa_5,, \sum_{i=0}^{5} a_i c_i ,\Big)$

我们对B=(s00000c00s0000c100s000c2000s00c30000s0c400000sc5)B = \begin{pmatrix} s & 0 & 0 & 0 & 0 & 0 & c_0 \\ 0 & s & 0 & 0 & 0 & 0 & c_1 \\ 0 & 0 & s & 0 & 0 & 0 & c_2 \\ 0 & 0 & 0 & s & 0 & 0 & c_3 \\ 0 & 0 & 0 & 0 & s & 0 & c_4 \\ 0 & 0 & 0 & 0 & 0 & s & c_5 \end{pmatrix}做lll,理想下是得到( sa0, sa1, sa2, sa3, sa4, sa5, ∑i=05aici )(\, sa_0,\, sa_1,\, sa_2,\, sa_3,\, sa_4,\, sa_5,\, \sum_{i=0}^{5} a_i c_i \,)

但是现实不尽人意,目标向量太大了,lll输出无法对应上,所以我们继续优化:
目标向量要尽可能短:所以我们先把我们期待的a化换成更严谨的x:

LLL之后得到:

$\begin{pmatrix}
x_0 , x_1 , x_2 , x_3 , x_4 , x_5
\end{pmatrix}
\begin{pmatrix}
s & 0 & 0 & 0 & 0 & 0 & c_0 \
0 & s & 0 & 0 & 0 & 0 & c_1 \
0 & 0 & s & 0 & 0 & 0 & c_2 \
0 & 0 & 0 & s & 0 & 0 & c_3 \
0 & 0 & 0 & 0 & s & 0 & c_4 \
0 & 0 & 0 & 0 & 0 & s & c_5
\end{pmatrix}

\Big(, sx_0,, sx_1,, sx_2,, sx_3,, sx_4,, sx_5,, \sum_{i=0}^{5} x_i c_i ,\Big)$

我们尝试直接把第六项去优化,使其特别小,接近格的真正输出:

∑ixici=∑ixi(Mai+ei) =M∑ixiai+∑ixiei \begin{aligned} \sum_i x_ic_i &=\sum_i x_i(Ma_i+e_i)\ &=M\sum_i x_ia_i+\sum_i x_ie_i\ &\end{aligned}

如果∑ixiai=0\sum_i x_ia_i = 0那么因为 eie_i 很小,所以最后一维也很小

于是:

(sx0,…,sx5,∑ixici)(s x_0,\ldots,s x_5,\sum_i x_i c_i)

就成了短向量。

我们除以s拿到多组真正x后

X=(x(1)x(2)⋮x(5))X= \begin{pmatrix} x^{(1)}\\ x^{(2)}\\ \vdots\\ x^{(5)} \end{pmatrix}

然后求:

Xa=0X a=0

最后利用整数归一化和明文范围确定 aa。

m1x3d_d1p

恢复 salt(二项式定理)

题目中生成密文 cc 的方式为:

c≡(n−1)msg(modn3)c \equiv (n - 1)^{msg} \pmod{n^3}

其中 msg=bytes_to_int(salt)msg = \text{bytes\_to\_int}(salt)。由二项式定理展开:

(n−1)msg=∑k=0msg(msgk)nk(−1)msg−k(n - 1)^{msg} = \sum_{k=0}^{msg} \binom{msg}{k} n^k (-1)^{msg - k}

模 n3n^3 下,只需保留 k<3k < 3 的前三项:

(n−1)msg≡(−1)msg⋅(1−msg⋅n+msg(msg−1)2n2)(modn3)(n - 1)^{msg} \equiv (-1)^{msg} \cdot \left(1 - msg \cdot n + \frac{msg(msg - 1)}{2} n^2\right) \pmod{n^3}

因为 saltsalt 是 16 字节随机数,其最高位字节不固定,但 msg≪nmsg \ll n:

  • 考察模 n2n^2:

  • c≡(−1)msg(1−msg⋅n)(modn2)c \equiv (-1)^{msg} (1 - msg \cdot n) \pmod{n^2}

  • 如果 msgmsg 为偶数:c≡1−msg⋅n(modn2)  ⟹  msg⋅n≡1−c(modn2)c \equiv 1 - msg \cdot n \pmod{n^2} \implies msg \cdot n \equiv 1 - c \pmod{n^2};

  • 如果 msgmsg 为奇数:c≡−1+msg⋅n(modn2)  ⟹  msg⋅n≡c+1(modn2)c \equiv -1 + msg \cdot n \pmod{n^2} \implies msg \cdot n \equiv c + 1 \pmod{n^2}。

由于 msg<nmsg < n,直接计算:

msg=(1−c) mod n2n或msg=(c+1) mod n2nmsg = \frac{(1 - c) \bmod n^2}{n} \quad \text{或} \quad msg = \frac{(c + 1) \bmod n^2}{n}

通过检查结果是否刚好为 16 字节(长度 ≤128\le 128 位)即可直接还原出 salt。

求解私钥 x(Pohlig-Hellman 离散对数)

在椭圆曲线部分:

  • 曲线阶为 N=2521N = 2^{521},这是一个纯粹的 2 的幂次平滑阶(22-smooth)。

  • Q=h⋅GQ = h \cdot G 在椭圆曲线上,已知 GG 与 QQ。

  • 根据 Pohlig-Hellman 算法(或 SageMath 自带的 discrete_log),可以在多项式时间内直接求出 h(modN)h \pmod{N}(因为 h<p1<Nh < p_1 < N,hh 即为其真实整数值)。

  • 得到 hh 后,已知 h≡4x(modp1)h \equiv 4^x \pmod{p_1}。

  • 虽然 p1p_1 是 256 位安全素数(p1=2q+1p_1 = 2q + 1),普通的离散对数很难解,但题中限定了:

  • x=LOWER+Δx=(2⊕72)+Δxx = \text{LOWER} + \Delta x = (2 \oplus 72) + \Delta x

  • 注意:原 Python 代码中写的是 LOWER = 2^72 和 WIDTH = 2^50。在 Python 中 ^ 是**异或(XOR)**运算符,不是幂运算!

    • LOWER = 2 ^ 72 = 74

    • WIDTH = 2 ^ 50 = 48

  • 因此 xx 的范围仅在 [74,74+48][74, 74 + 48] 之间,甚至小于 150,也可以直接暴力循环验证 4x≡h(modp1)4^x \equiv h \pmod{p_1},或者直接比对 hh。

1391超时

分析

  1. tar 长度为 13 字节,由 AES-ECB 加密后截断前 13 字节构成。由于密钥 key 未知,我们无法直接计算 tar。

  2. 验证函数 ****verify(target, tag):

Text
for i in range(l):
tmp1, tmp2 = target[i], tag[i]
tmp3 = super_sha256(bytes([tmp1]))
tmp4 = super_sha256(bytes([tmp2]))
if tmp3 != tmp4:
return False
  • 校验是逐字节独立对比的:第 ii 位的验证只取决于 target[i] 和 tag[i] 的 super_sha256 结果是否相同。

  • 单字节的取值范围仅有 256 种可能(0 到 255)。

  • super_sha256(x) 是一个确定的哈希函数,单字节输入只有 256 种输出。

因为单字节映射只有 256 种可能,你可以直接预计算单字节的查找表(Rainbow Table):

Python

from hashlib import sha256

def super_sha256(x):
result = x
for _ in range(1391):
result = sha256(result).digest()[:13]
return result

# 预计算 0~255 的 super_sha256 映射
table = {}
for b in range(256):
val = super_sha256(bytes([b]))
table[val] = b