2024 CryptoCTF Writeup（绝赞更新中...）

和1997的队友打了今年的Crypto CTF

最近都忙着搞论文，明显手生了，主要表现在，虽然能做出题，但是做题速度奇慢，包括复现的速度…

而且毕业季也各种事情，最后就变成玩具车了

最后结果是，差两题AK，拿了第五，对比上年还是进步了一名

被队友带飞了

以下给出我的题目复现WP

Warm-up·

CV：CCTF{Harn3sS_Y0ur_CrYptO9rAphy_Pr0wEs5_💪_⚡_💥_🔥!}

Easy·

Alibos·

审题得$c \equiv pk + d^2 m \pmod {10^d}$，$pk$、$d$和$c$已知，所以直接

$$m \equiv (c - pk) d^{-2} \pmod {10^d}$$

就好了，最后解出来的$m$记得做unpad

参考代码：

#!/usr/bin/env sage
pkey = 8582435512564229286688465405009040056856016872134514945016805951785759509953023638490767572236748566493023965794194297026085882082781147026501124183913218900918532638964014591302221504335115379744625749001902791287122243760312557423006862735120339132655680911213722073949690947638446354528576541717311700749946777
enc  = 6314597738211377086770535291073179315279171595861180001679392971498929017818237394074266448467963648845725270238638741470530326527225591470945568628357663345362977083408459035746665948779559824189070193446347235731566688204757001867451307179564783577100125355658166518394135392082890798973020986161756145194380336
d = len(str(pkey))

n = 10^d
m = (enc - pkey) * pow(d, -2, n) % n
assert (pkey + d ** 2 * m) % (10 ** d) == enc

m = str(m).split('1111111111')[0]
m = Integer(m)
flag = bytes.fromhex(hex(m)[2:])
print(flag)

# b'CCTF{h0M3_m4De_cRyp70_5ySTeM_1N_CryptoCTF!!!}'

Beheaded·

PPM格式·

magick的安装参考这里

wget https://imagemagick.org/archive/ImageMagick.tar.gz
tar -xzvf ImageMagick.tar.gz
cd ImageMagick-7.1.1-33
./configure
make -j8
./utilities/magick

懒得安装了，于是

alias magick='/path_to/ImageMagick-7.1.1-33/utilities/magick'

然后生成一个看看格式

magick -background white -fill blue -pointsize 72 -size "10"x"10" -gravity North caption:"1997" flag.ppm

得到的大概是

P6
10 10
65535
+ binary...

执行tail后就是只保留后面的二进制数据

于是找下P6格式的说明，找到这个

那么翻译一下，对于我自己生成的数据，大概意思是：

• P6表示文件是Pixmap Binary格式
• 10 10表示图像长宽各10个像素
• 65535表示RGB每个值最大65535，即占2个字节，所以一个像素占6字节

解法·

回到题目，题目的all_flags.enc文件是用类似的magick命令生成的，只是隐去了文件头信息，那么可以推测也是P6格式，且每个像素占用6个字节，但是长宽信息不清楚，于是先统计一下all_flags.enc文件的字节数

✎ $ wc --bytes ./all_flags.enc 
100691360 ./all_flags.enc

再看看题目脚本，发现有个坑，脚本生成的all_flags.enc是多个图片密文的拼接，所以在解之前需要先把图片分离，那么就要先确定一共有多少张图片

观察一下all_flags.enc文件里的密文，发现里面有大量的

b'\xdbN\x86\xffv\xe9\x18?\x97\xa9]w \xdc\x1d1'

结合脚本中的-background white和ECB加密的特性，基本可以确定这是一块纯白背景的密文（注，AES-256的Block size是16字节）

再看最后一块密文是

b'\x8b\x88\xb4\x08.h\xd5J\x0b\n\x9a\xb2\xe1\x9e\xbd\x05'

在这里，为了确定图片的数量，可以先斗胆做个假设，即假设每章图片的最后一块也是纯白的背景，之所以和其他纯白的密文不一样，是因为最后一块做了padding

那么根据这样的假设，就可以通过数最后一块密文的数量确定图片的数量，怼个脚本实验一下：

with open('./all_flags.enc', 'rb') as f:
  data = f.read()
tail = data[-16:]
print(tail)
print(data.count(tail))
# 124

那么理论上就是有124张图片，但是进一步验证发现其实并不是，因为在用最后一块密文进行分割时，发现每一张图片的密文数量并不一致，而题目脚本生成的每张图片应该是大小一样的：

data = data.split(tail)[:-1]
data = [d+tail for d in data]
test = [len(d) for d in data]
print(test)
# [915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 414352, 501024, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 416656, 498720, 292144, 623232, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 416848, 480, 498048, 915376, 915376, 915376, 915376, 915376, 417040, 498336, 417760, 497616, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 414976, 500400, 915376, 915376, 915376, 416560, 498816, 915376, 413248, 502128, 915376, 915376, 418048, 497328, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 416368, 499008, 915376, 525856, 389520, 915376, 434848, 480528, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376, 915376]

通过输出可以知道一张图片的密文大小应该是出现最多的915376，而其他零散的数字通过相加后其实也可以拼凑出915376，于是最终得到应该有110张图片

esize = max(test, key=test.count)
assert n % esize == 0
npic = n // esize
print(npic, esize)
# 110 915376

接下来就要推算每张图片的大小，即脚本中的X和Y

目前已经知道每张图片的密文数为psize = 915376，根据P6格式的解释，图片的像素是psize除以6，但这里的psize显然不能整除6，原因是明文在加密时做了padding

由于Block size是16字节，所以原来明文的大小（或者说padding的数量）只可能是2种情况：

psizes = []
for i in range(16):
  if (esize-i) % 6 == 0:
    psizes += [(esize-i) // 6]
print(psizes)
# [152562, 152561]

然后每张图片的长宽就是这两个数之一的因子，只需要遍历所有因子观察图片中是否有flag即可，为了减轻工作量，可以不妨先对第一张图片进行遍历：

d = data[0]
out_path = './out/'
epsilon = 72
for psize in psizes:
  for X in psize.divisors():
    Y = psize // X
    if X < Y or X < epsilon or Y < epsilon:
      continue
    print(X, Y)
    fname = '%s%d_%d_%d' % (out_path, psize, X, Y)
    with open(fname+'.ppm', 'wb') as f:
      f.write(b'P6\n%d %d\n65535\n' % (X, Y) + d[:psize*6])
    img = cv2.imread(fname+'.ppm')
    cv2.imwrite(fname+'.png', img)

注：因为最后结果需要人工筛选，所以我做了下剪枝，首先因为-pointsize 72，所以可以假设长宽一定大于72，然后因为图片是一串flag，所以可以假设图片的宽一定比高大，最后引文PPM文件有点难打开，所以参考了春哥的方法，用opencv把图片转成PNG，最后爆出来一张有明显文字的，得到尺寸为：

psize = 152562
X = 1623
Y = 94

明显第一张是个Fake，而且加了盐，所以只能（肉眼）遍历所有图片来找到真正的Flag了，现在有了图片尺寸，所以事情就容易了很多：

with open('./all_flags.enc', 'rb') as f:
  data = f.read()
data = [data[esize*i: esize*(i+1)] for i in range(npic)]
psize = 152562
X = 1623
Y = 94
for i in range(len(data)):
  fname = '%s%d_%d_%d-%d' % (out_path, psize, X, Y, i)
  print(fname)
  with open(fname+'.ppm', 'wb') as f:
    f.write(b'P6\n%d %d\n65535\n' % (X, Y) + data[i][:psize*6])
  img = cv2.imread(fname+'.ppm')
  cv2.imwrite(fname+'.png', img)

遍历到i=40的时候找到真的图片

理论上已经出Flag了，但还可以多做一步让图片更好看，在上面已经知道了纯白的密文，所以可以把对应的密文换成白色，其他密文块换成黑色，于是：

real = b''
w = data[0][:16]
for i in range(len(data[40])//16):
  di = data[40][16*i: 16*(i+1)]
  if di == w:
    real += b'\xff' * 16
  else:
    real += b'\x00' * 16

with open('flag.ppm', 'wb') as f:
  f.write(b'P6\n%d %d\n65535\n' % (X, Y) + real[:psize*6])
img = cv2.imread('flag.ppm')
cv2.imwrite('flag.png', img)

最后附上完整参考脚本：

#!/usr/bin/env sage
import cv2

with open('./all_flags.enc', 'rb') as f:
  data = f.read()
n = len(data)
tail = data[-16:]

data = data.split(tail)[:-1]
data = [d+tail for d in data]
test = [len(d) for d in data]

esize = max(test, key=test.count)
assert n % esize == 0
npic = n // esize
print(npic, esize)

psizes = []
for i in range(16):
  if (esize-i) % 6 == 0:
    psizes += [(esize-i) // 6]
print(psizes)

# get Size
d = data[0]
out_path = './out/'
epsilon = 72
for psize in psizes:
  for X in psize.divisors():
    Y = psize // X
    if X < Y or X < epsilon or Y < epsilon:
      continue
    print(X, Y)
    fname = '%s%d_%d_%d' % (out_path, psize, X, Y)
    with open(fname+'.ppm', 'wb') as f:
      f.write(b'P6\n%d %d\n65535\n' % (X, Y) + d[:psize*6])
    img = cv2.imread(fname+'.ppm')
    cv2.imwrite(fname+'.png', img)
    
# rm fake
with open('./all_flags.enc', 'rb') as f:
  data = f.read()
data = [data[esize*i: esize*(i+1)] for i in range(npic)]
psize = 152562
X = 1623
Y = 94
for i in range(len(data)):
  fname = '%s%d_%d_%d-%d' % (out_path, psize, X, Y, i)
  print(fname)
  with open(fname+'.ppm', 'wb') as f:
    f.write(b'P6\n%d %d\n65535\n' % (X, Y) + data[i][:psize*6])
  img = cv2.imread(fname+'.ppm')
  cv2.imwrite(fname+'.png', img)
  
# prettify
real = b''
w = data[0][:16]
for i in range(len(data[40])//16):
  di = data[40][16*i: 16*(i+1)]
  if di == w:
    real += b'\xff' * 16
  else:
    real += b'\x00' * 16

with open('flag.ppm', 'wb') as f:
  f.write(b'P6\n%d %d\n65535\n' % (X, Y) + real[:psize*6])
img = cv2.imread('flag.ppm')
cv2.imwrite('flag.png', img)

Mashy·

要求给出8组不同的(d1, d2)，满足

$$\begin{aligned} MD5(d_1 \oplus d_2) &\ne ae09d7510659ca40eda3e45ca70e9606 \\ MD5(d_1) \oplus MD5(d_2) \oplus Salt &= a483b30944cbf762d4a3afc154aad825 \end{aligned}$$

两个哈希，第一个没查到，第二个要收钱，摆了

后来看了春乎，原来就是找8组256字节的MD5碰撞，这…

用HashClash怼一遍，首先安装

sudo apt-get install autoconf automake libtool
sudo apt-get install zlib1g-dev libbz2-dev
git clone https://github.com/cr-marcstevens/hashclash.git
cd hashclash
./build.sh

注：如果./build.sh运行的时候卡住了，有可能是网络问题，自行挂代理即可

然后

mkdir cpc_workdir
cd cpc_workdir
echo -n "1997" > prefix.txt

../scripts/generic_ipc.sh prefix.txt
mv ./collision1.bin ./collision1.bin.0
mv ./collision2.bin ./collision2.bin.0

... ...

运行8次generic_ipc.sh后就得到8组的MD5碰撞，每次运行完后把结果改下名，方便后面写交互脚本

最后的参考交互脚本如下：

from pwn import remote, context
context.log_level = 'debug'

r = remote('00.cr.yp.toc.tf', 13771)
for i in range(8):
  print(i)
  r.recvuntil(b'first input:')
  with open('./hashclash/cpc_workdir/collision1.bin.%d' % i, 'rb') as f:
    r.sendline(f.read().hex())
  r.recvuntil(b'second input:')
  with open('./hashclash/cpc_workdir/collision2.bin.%d' % i, 'rb') as f:
    r.sendline(f.read().hex())

r.interactive()
r.close()

# ┃ Congrats! the flag: b'CCTF{mD5_h4Sh_cOlL!Si0N_CrYp7o_ch41lEnGe!!!}'

Medium·

Ahoo·

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Welcome to Ahoo task! Given integer n, find the smallest positive   ┃
┃ integer c such that n * c has the minimum number of 1 bits in its   ┃
┃ binary representation. Completing all steps will reveal the flag :) ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

直接站在春哥的肩膀上找到A143069和aut-msw-1-10000.txt，然后写交互脚本即可

参考代码：

from pwn import remote, context
context.log_level = 'debug'

# https://raw.githubusercontent.com/FinnLidbetter/sturdy-numbers/master/timing/aut-msw-1-10000.txt
with open('./aut-msw-1-10000.txt', 'r') as f:
    data = f.read().split('\n')[:-1]
data = [0] + [int(_) for _ in data]

r = remote('00.cr.yp.toc.tf', 17371)
for _ in range(20):
    r.recvuntil(b'n = ')
    n = int(r.recvuntil(b',')[:-1])

    res = b'%d, %d' % (bin(data[n] * n).count('1'), data[n])
    r.sendline(res)

r.interactive()
r.close()

# ┃ Congrats, you got the flag: b'CCTF{iZ_It_5h0rT_c0mpUt3r_C4lcuLaT!oN!???}'

Alilbols·

题目解法和NTRU的解法类似

首先由$h \equiv f^{-1} g \pmod q$，得$fh - kq = g$，于是构造格使得：

$$(-k, f) \begin{bmatrix} q & \\ h & 1 \end{bmatrix} = (g, f)$$

粗略计算：

$$\|w\| \approx \sqrt{2} \cdot 10^d < 2 \cdot 10^d \approx \sigma$$

于是对格进行规约后可以拿到$f$和$g$​

PS：其实这一步可能会出现多解，不过其实只要解满足$h \equiv f^{-1} g \pmod q$即可

然后需要对$c$进行解密，解密方法和NTRU的类似，首先计算

$$fc \equiv r (f+g) + fm \pmod q$$

然后算一下界可以发现$r (f+g) + fm$有极大概率小于$q$，所以可以算得

$$a = fc \pmod q = r (f+g) + fm$$

最后计算

$$m \equiv f^{-1} a \pmod {f + g}$$

即可解密

在最后一步中可能会出现$gcd(f, f+g) \ne 1$的情况，就无法求逆，如果出现这种情况的话就需要做AMM，但我实际解的时候没有，就不管了

理论如此，实际做的时候还需要知道$d$，这个只需要在$h$或$c$的十进制规模附近遍历即可

参考代码：

with open('./ouput.txt', 'r') as f:
  exec(f.read())

for i in range(1):
  d = (len(str(c))) // 2
  q = 4 * 100 ** d

  B = matrix(ZZ, [
    [q, 0],
    [h, 1]
  ])
  g, f = B.LLL()[0]
  f, g = abs(f), abs(g)
  print(f, g)
  print(gcd(f, f+g))

  a = f * c % q
  n = (f + g) // gcd(f, f+g)
  #n = n // gcd(f, n)
  print(gcd(f, n))
  m = a * f.inverse_mod(n) % n
  try:
    flag = bytes.fromhex(hex(m)[2:])
    print(flag)
  except:
    pass

'''
113064947692702103799231199468072510903839498374716047303085853453113283728818247305758215677954588763931471946182908063714777335122912930256571619331664053621631174370186578849231886568333948343534395353919774419633731806963043911274007420241089284010144207714339617510789422811656735331222466776153901647025851637829858405953050072469297992493334984730777005154182274995099150706806282346277695670937656012866815920565404878131472860889178457719003956941536200135614026090372738773201706091708638664496577612244017928430272852213629449803865503473673985014191137 121225735948962805927435238039810819215887992413542216149877302158471567001614227054453188896976336350561801244215667264722788859622407059935854582497557238535977706646667824468703286568029648346697105178986470102548390104380856939377786046149771635771656620472465696255524883500461088148118520891769358583188198505080807288139862744022281798728618135336019815478870827242841306653937757979436969147775800185012065008310407495836925318623318860872984004964969550906585353801421678977298537476134466756779438293960694910065864999873778057675968654079621038359759233

b'CCTF{4_c0N9rU3n7!aL_Pu81iC_k3Y_cRyp70_5ySTeM_1N_CCTF!!}'
'''

Ally·

苏氨酸找到了一篇这样的文章（用方程作为关键字搜一下其实就能搜到），读到第二页基本就出解了

首先看这段，说Stroeker的1980年的文章中有这样一个关系

虽然网上并没找到Stroeker的文章，但可以先把这个关系即下来，即存在$u$、$v$和$l$，满足（注意文章中的$N$就是题目中的$p$）

$$\begin{aligned} 2x &= v - u + l + 1 \\ 2y &= v - u - l + 1 \\ uv &= pl \end{aligned}$$

接着往下翻发现（可能是Stroeker的文章说的）

即（可能）存在一组解为

$$\begin{cases} v = p \\ u = \frac{p+3}{4} \\ l = p \end{cases}$$

这里因为这篇文章是想说存在没有解的$N$，所以文章中的$N$是个偶数，就会导致$\frac{N+3}{4}$非整数，即方程无解

但是在题目中，$p$肯定是奇数，所以只要找到满足$p + 3 \equiv 0 \pmod 4$的$p$就好了

那么接下来验证一下这个解对不对，首先把解代回求$x$和$y$得

$$\begin{cases} x = \frac{v-u+l+1}{2} = \frac{p+1}{2} \\ y = \frac{v-u-l+1}{2} = \frac{p-1}{4} \end{cases}$$

由于$p + 3 \equiv 0 \pmod 4$，所以满足$x$和$y$都是整数

然后验证是否满足方程，这就直接用代码了：

var('p')
x = (p+1)/2
y = (p-1)/4
f = p * (x-y)^3 - (x^2+y) * (x+y^2)
assert bool(f==0) == True

于是最后编写交互脚本即可

参考代码：

#!/usr/bin/env sage
from pwn import remote, context
context.log_level = 'debug'

r = remote('00.cr.yp.toc.tf', 13777)

for _ in range(20):
  r.recvuntil(b'your ')
  nbit = Integer(r.recvuntil(b'-')[:-1].decode())
  while True:
    p = random_prime(2^nbit, lbound=2^(nbit-1))
    if (p + 3) % 4 == 0:
      break
  r.sendline(str(p).encode())

  r.recvuntil(b'(x + y**2)')
  x = (p+1) // 2
  y = (p-1) // 4
  r.sendline(b'%d, %d' % (x, y))

r.interactive()
r.close()

# ┃ Congratz! You got the flag: b'CCTF{Di0phaNtinE_eQuaT1on_iZ_4n_equ4tion_wiTh_int3ger_solu7Ions_0nly!}'

Bada·

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Hey! It's time to solve the equation of a function f: N x N -> Z.    ┃
┃ Function f has given certain conditions. In each step, solve the     ┃
┃ equation f(x, y) = z with the given value of z. We know f(a+1, b) =  ┃
┃ f(a, b) + a, and f(a, b+1) = f(a, b) - b, for every `a' and `b'.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

先推关系式，根据题目有

$$f(x, y) = f(1, 1) + \sum_{i=1}^{x-1} i - \sum_{i=1}^{y-1}i$$

根据$x$和$y$的大小分为两种情况，消去重叠的部分的

$$\begin{cases} f(x, y) = f(1, 1) + \sum_{i=y}^{x-1} i ,\ x > y \\ f(x, y) = f(1, 1) - \sum_{i=x}^{y-1} i ,\ x \le y \end{cases}$$

问题给出了$f(x, y)$和$f(1, 1)$，于是两种情况可根据差值$\Delta = f(x, y)- f(1, 1)$的正负确定，问题就转化为（不妨假设$x > y$）根据$\sum_{i=y}^{x-1} i$求$x$和$y$

根据求和数列，展开$\sum_{i=y}^{x-1} i$可以得到

$$\Delta = \frac{(x-y) (x+y-1)}{2}$$

一个方程，两个未知数，似乎无解

但在生成多组数据后发现，$\Delta$总为正，而且是个素数，这就有意思了

因为$2$也是素数，所以这样分解后就可以得到

$$\begin{cases} x - y = 2 \\ x + y - 1 = \Delta \end{cases}$$

这样就有了两组方程，也即得

$$\begin{cases} y = \frac{\Delta - 1}{2} \\ x = y + 2 \end{cases}$$

理论上是这样，但提交的时候发现错了，才发现有另一种可能的解为

$$\begin{cases} x - y = 1 \\ x + y - 1 = 2\Delta \end{cases}$$

解出来是简单粗暴的

$$\begin{cases} y = \Delta \\ x = \Delta + 1 \end{cases}$$

这组交上去就对了，好家伙

如果我没推错的话应该两组解都是对的，估计出题人的Oracle里面就没有实现这个$f$，或者是我推得有问题

最后参考代码：

#!/usr/bin/env sage
from pwn import remote, context
context.log_level = 'debug'

r = remote('00.cr.yp.toc.tf', 17113)

for _ in range(20):
  r.recvuntil(b'f(1, 1) = ')
  f11 = Integer(r.recvuntil(b' ')[:-1].decode())
  print('f11 = %d' % f11)
  r.recvuntil(b'f(x, y) = ')
  fxy = Integer(r.recvline()[:-1].decode())
  print('fxy = %d' % fxy)

  delta = fxy - f11
  assert is_pseudoprime(delta)

  ''' emmmm
  y = (delta - 1) // 2
  x = y + 2
  '''
  y = delta
  x = y + 1
  assert sum(range(y, x)) == delta
  res = b'%d,%d' % (x, y)
  print('res = %s' % res.decode())
  r.sendline(res)

r.interactive()
r.close()

'''
┃ Congratulation! You got the flag!
┃ flag = b'CCTF{BADA_iZ_4_K0r3An_5!ngeR!!}'
┃ Exiting...
'''

Duzly·

全场唯一一道0解居然是Medium…

赛后发现已经被Sarkoxed给做出来了，附上WP

原来比赛时想着消去$x^{2^{24}}$以上的项，赛后才发现$2^{24}$其实也还是可以枚举，所以应该还是像怎么遍历方程的所有解

等其他题都复现完再回来怼这题

Forghan·

首先$n = (p^2-1)(q^2 - 1) = (p-1)(q-1)(p+1)(q+1)$，其中$p$和$q$可以自己指定，于是就大大降低了题目难度

这里我选择偷下鸡，首先构造$p$和$q$都是强素数（即$p = 2p'-1$、$q = 2q'-1$，其中$p'$和$q'$都是素数），然后计算$n' = \frac{(p-1) (q-1)}{4} = p'q'$，显然此时$\varphi = (p-1)(q-1)$

由于题目的flag没有做padding，所以这里我可以大胆地假设flag在512比特以下，即小于$n'$，而由于$n'$可以整除$n$，所以可以把题目迁移到$\mathbb{Z}_{n'}$中去解，于是问题就转变为经典的RSA问题，理论上直接做解密即可

但是实际操作中会遇到加密指数和$\varphi$不互素的情况，就是典型的AMM，虽然可以通过多次碰运气拿到互素的y，但这里我选择直接上科技

最终参考代码：

#!/usr/bin/env sage
from pwn import remote
import string
nbit = 256

'''
while True:
  p = random_prime(2^nbit, lbound=2^(nbit-1))
  if is_pseudoprime((p-1)//2):  # and is_pseudoprime((p+1)//2):
    break
print('p = %d' % p)

while True:
  q = random_prime(2^nbit, lbound=2^(nbit-1))
  if is_pseudoprime((q-1)//2):  # and is_pseudoprime((q+1)//2):
    break
print('q = %d' % q)
'''
p = 92359933018593186462337679162334725394160369981894321367332184324690845592087
q = 102283889061290799573026525305840487663463568046501552623800355768317899298779
n = (p-1) * (q-1) // 4
phi = ((p-1)//2 - 1) * ((q-1)//2 - 1)
# https://tover.xyz/p/n-root-in-F/
load('./nth.sage')

def gao():
  r = remote('00.cr.yp.toc.tf', 13337)

  r.recvuntil(b'[Q]uit')
  r.sendline(b's')
  r.recvuntil(b'comma:')
  r.sendline(b'%d, %d' % (p, q))

  r.recvuntil(b'menu!')
  r.sendline(b'g')
  r.recvuntil(b'cp = ')
  cp = Integer(r.recvline()[:-1].decode())
  print('cp = %d' % cp)
  r.recvuntil(b'cq = ')
  cq = Integer(r.recvline()[:-1].decode())
  print('cq = %d' % cq)

  r.recvuntil(b'[Q]uit')
  r.sendline(b'p')
  r.recvuntil(b'gp = ')
  gp = Integer(r.recvline()[:-1].decode())
  print('gp = %d' % gp)
  r.recvuntil(b'gq = ')
  gq = Integer(r.recvline()[:-1].decode())
  print('gq = %d' % gq)
  r.recvuntil(b'yp = ')
  yp = Integer(r.recvline()[:-1].decode())
  print('yp = %d' % yp)
  r.recvuntil(b'yq = ')
  yq = Integer(r.recvline()[:-1].decode())
  print('yq = %d' % yq)

  r.recvuntil(b'[Q]uit')
  r.sendline(b'q')

  r.close()

  print(gcd(yp, phi))
  print(gcd(yq, phi))

  checker = genStrChecker(string.printable)
  ps = [(p-1)//2, (q-1)//2]
  resp = nthRSA_n(cp, yp, ps, checker=checker)
  for r in resp:
    flag = bytes.fromhex(hex(r)[2:])
    print(flag)
  resq = nthRSA_n(cq, yq, ps, checker=checker)
  for r in resq:
    flag = bytes.fromhex(hex(r)[2:])
    print(flag)

  

if __name__ == '__main__':
  gao()

'''
cp = 51037070783731607792547265664812531042214827725561670059107692922124910573738184335739124819964679396899318639399590288618476108416545674456109476211992070396721602462492938426353395283735164228867013135713295965603317658373640648065544328771805586033284843982719229248593474013498887586738121554237231018945
cq = 17583131733004414626211459866069811946002721706199587887773336420363302777773726571740335926933521908872272558840736255334971053925220669053269241521007136933740053260328854022883859701478709545614557088191126416683911030483800041671595698069571649021459294095642040125668549463595536590804543343591332212992
gp = 79705551004622712935130852699971716363581172692336825374735565625045837538825
gq = 93047693534514864175763736584542296204942878898616074436543824803936037756198
yp = 10171904860560631060258657995115056301271679947354495710836846000010032359222
yq = 56539370829697159254885996797528819931130657377200722518380358827750225547405

b'...::::: CCTF{f!nD1N9_7wIn_'
b'5m0OtH_1nT3GErS!!!} :::::...'
'''

另：实测即使不取特殊的$p$和$q$，用Yafu也能分解，然后求得$\varphi$，不过写代码会有点麻烦，而且AMM的复杂度会变大

Honey·

直接看加密，得

$$C_i \equiv Q_i m + R_i r_i + S_i s_i \pmod p$$

大概就是一道类似HNP的题目，于是照搬HNP的解法

PS：可以参考我以前的一些学习笔记（看理论部分即可），不过这笔记还是太老了，估计以后再更新一下，挖坑

首先消去$m$，把$Q_im$放到一边，然后拿两组式子组合

$$C_0 - R_0 r_0 - S_0 s_0 \equiv Q_0 m \pmod p \\ C_i - R_i r_i - S_i s_i \equiv Q_i m \pmod p$$

把上式乘$Q_i$，下式乘$Q_0$，然后联立即消去$m$，得

$$Q_i C_0 - Q_i R_0 r_0 - Q_i S_0 s_0 \equiv Q_0 C_i - Q_0 R_i r_i - Q_0 S_i s_i \pmod p \\ (Q_0 C_i - Q_i C_0) - Q_0 R_i r_i - Q_0 S_i s_i + Q_i R_0 r_0 + Q_i S_0 s_0 \equiv 0 \pmod p$$

然后还要展开模数，代入一个$k_i$

$$(Q_0 C_i - Q_i C_0) - Q_0 R_i r_i - Q_0 S_i s_i - k_i p + Q_i R_0 r_0 + Q_i S_0 s_0 = 0$$

然后构造格基（其中$D = 2^{32}$，$i = 1, \cdots, d-1$）

$$B = \begin{bmatrix} \begin{array}{lll|l|lll|lll} 1 & & - Q_0 R_i \\ & 1 & - Q_0 S_i \\ & & - p \\ \hline &&& \ddots \\ \hline &&&& 1 & & - Q_0 R_{d-1} \\ &&&& & 1 & - Q_0 S_{d-1} \\ &&&& & & - p \\ \hline && Q_i R_0 &&&& Q_{d-1} R_0 & 1 & & \\ && Q_i S_0 &&&& Q_{d-1} S_0 & & 1 & \\ && Q_0 C_i - Q_i C_0 &&&& Q_0 C_{d-1} - Q_{d-1} C_0 & & & D \\ \end{array} \end{bmatrix}_{(3d \times 3d)}$$

可得

$$(r_1, s_1, k_1\ |\ \cdots\ |\ r_{d-1}, s_{d-1}, k_{d-1}\ |\ r_0, s_0, 1) \cdot B \\ = (r_1, s_1, 0\ |\ \cdots\ |\ r_{d-1}, s_{d-1}, 0\ |\ r_0, s_0, D)$$

$p$是512 bits，$d$是32 bits，所以不用算也可以知道能规约成功了，有兴趣的可以自己算一下界

规约后可以得到$r_i$和$s_i$，然后代回去求$m$即可

实际写代码时可以把$i=0$当作数组的最后一个，$i=1$当作第一个，就好操作一点

参考代码：

#!/usr/bin/env sage
with open('./params_enc.txt', 'r') as f:
  exec(f.read())
d = len(Q)

B = matrix(ZZ, 3*d)
for i in range(d-1):
  B[3*i, 3*i] = 1  
  B[3*i, 3*i+2] = -Q[-1] * R[i]
  B[3*i+1, 3*i+1] = 1  
  B[3*i+1, 3*i+2] = -Q[-1] * S[i]
  B[3*i+2, 3*i+2] = -p
  B[-3, 3*i+2] = Q[i] * R[-1]
  B[-2, 3*i+2] = Q[i] * S[-1]
  B[-1, 3*i+2] = C[i] * Q[-1] - C[-1] * Q[i]
B[-3, -3] = 1
B[-2, -2] = 1
B[-1, -1] = 2^32

L = B.LLL()
print(L[0])

r0 = L[0][0]
s0 = L[0][1]
m = (C[0] - r0 * R[0] - s0 * S[0]) * pow(Q[0], -1, p) % p
flag = bytes.fromhex(hex(m)[2:])
print(flag)


r0 = L[0][3]
s0 = L[0][4]
m = (C[1] - r0 * R[1] - s0 * S[1]) * pow(Q[1], -1, p) % p
flag = bytes.fromhex(hex(m)[2:])
print(flag)

# CCTF{3X7eNdED_H!dD3n_nNm8eR_pR0Bl3m_iN_CCTF!!}

Joe-19·

理论上出题人也肯定没有这个GPT，所以只需要遍历$e$即可

可以自己生成一个$e$​进行遍历，但我在网上找到一个现成的，就直接拿来用了

最后解密即可

参考代码：

#!/usr/bin/env sage
import re
from tqdm import tqdm

with open('./output.txt', 'r') as f:
  exec(f.read())

# https://apod.nasa.gov/htmltest/gifcity/e.2mil
with open('./e.2mil') as f:
  data = f.read() 

data = re.findall(r'\d+', data)
data = ''.join(data)

ps = []
for l in (154, 155):
  a = data[:l]
  b = data[l:]

  for _ in tqdm(range(len(b))):
    if n % int(a) == 0:
      print(a)
      ps += [Integer(a)]
    a = a[1:] + b[0]
    b = b[1:]

e = 0x10001
phi = product([x-1 for x in ps])
d = e.inverse_mod(phi)
m = pow(c, d, n)
flag = bytes.fromhex(hex(m)[2:])
print(flag)

'''
  1%|▎                               | 17134/1999914 [00:03<05:33, 5949.13it/s]7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781
 42%|█████████████                  | 844774/1999914 [02:00<01:57, 9854.41it/s]9688632098638681429535439991332657144752666147923336383829750592576742104399942931057096761773496510622226977570278994077236841491368959008277469453600569
100%|█████████████████████████████| 1999914/1999914 [03:08<00:00, 10617.18it/s]
 41%|████████████▌                  | 813253/1999913 [01:55<02:17, 8633.62it/s]10019005372961705640183251650710051163228093250949727357306333102512304273058618645339800283588040423877666492199352609508401454089083503146788384653241593
 48%|██████████████▎               | 955277/1999913 [02:09<01:41, 10328.27it/s]10795109107229646654467923653403055635071360620150038008453082390943756377071343139771120080956310498862485323957447467376538994662280143050510681877597429
100%|█████████████████████████████| 1999913/1999913 [03:04<00:00

Melek·

题目大概意思就是，知道$t$组的$(a, f(a))$，其中

$$f(a) = \sum_{i=0}^{t-1} C_i a^i$$

其中$C_0 \equiv m^e \pmod p$

由于$p$是素数，所以解密是简单的，重点在于求$C_0$

首先我们都知道上面的求和可以写成向量的点乘

$$\begin{bmatrix} c_0 & c_1 & \cdots & c_{t-1} \end{bmatrix} \begin{bmatrix} a^0 \\ a^1 \\ \vdots \\ a^{t-1} \end{bmatrix} \equiv f(a) \pmod p$$

然后现在有$t$组的$(a, f(a))$，所以就可以组成一组可解的线性方程

不妨令

$$A = \begin{bmatrix} a_0^0 & a_1^0 & \cdots & a_{t-1}^0 \\ a_0^1 & a_1^1 & \cdots & a_{t-1}^1 \\ \vdots & \vdots & \ddots & \vdots \\ a_0^{t-1} & a_1^{t-1} & \cdots & a_{t-1}^{t-1} \end{bmatrix} \\ v_c = (C_0, C_1, \cdots, C_{t-1}) \\ v_f = (f(a_0), f(a_1), \cdots, f(a_{t-1}))$$

可得

$$v_f = v_c A$$

求逆即

$$v^c = v_f A^{-1}$$

于是可得$C_0$，然后解密即可

解密发现$e$和$p-1$不互素，nth解之

参考代码：

#!/usr/bin/env sage
from gmpy2 import powmod

with open('./output.txt', 'r') as f:
  exec(f.read())

e, p, PT = enc
t = len(PT)
a = []
fa = []
for i in range(len(PT)):
  a += [PT[i][0]]
  fa += [PT[i][1]]

A = matrix(GF(p), t, t)
for i in range(t):
  for j in range(t):
    A[i, j] = powmod(a[j], i, p)
Ainv = A^(-1)

vf = vector(GF(p), fa)
vc = vf * Ainv
c = Integer(vc[0])
print('c = %d' % c)

assert gcd(e, p-1) != 1
# https://tover.xyz/p/n-root-in-F/
load('nth.sage')
checker = genStrChecker(string.printable)
res = nthRSA_n(c, Integer(e), [Integer(p)], checker=checker)
for r in res:
  flag = bytes.fromhex(hex(r)[2:])
  print(flag)

'''
c = 7578451683223886721897751965012512970186814199061886859082385728532294810974986601048390882041773215459258245487361965408708218417206386123135513829067466
b'CCTF{SSS_iZ_4n_3fF!ciEn7_5ecr3T_ShArIn9_alGorItHm!}'
'''

Nabat·

题目要求构造符合以下4个条件的多项式$f$（其中$d$为$f$的最高次数，$g = x^2 + 2 + 2$）：

1. 多项式系数是$-1$、$0$或$1$

2. $d+1 \ge 2 \cdot ln(l)$

3. 多项式系数中$0$的数量大于等于$\lfloor \frac{d}{3}\rfloor - 3$（PS：题目修改之前为$\lfloor \frac{d}{3}\rfloor$​）

4. $f \equiv l \pmod g$

首先条件2和3好像有点难构造，于是可以先考虑构造条件1和4，然后再判断是否符合条件2和3

从条件4中可得到$2 \equiv -x^2 - x \pmod g$，便可用这个关系减小多项式的系数（的绝对值），从而达到条件1

那么Trivial的做法是，对于输入$l$，先把$2$提取出来，举个例子，比如$l=5$，那么就可以得到

$$\begin{aligned} 5 &\equiv 2 \cdot 2 + 1 \\ &\equiv 2 (-x^2 - x) + 1 \\ &\equiv -2 x^2 - 2 x + 1 \pmod g \end{aligned}$$

这样做就可以把常数项的系数降为$1$

但新生成的一次和二次项系数都是$-1$，不满足条件1，于是可以使用迭代的方法进行操作，即

$$\begin{aligned} -2 x^2 - 2 x + 1 &\equiv -(-x^2 - x) x^2 - (-x^2 - x) x + 1 \\ &\equiv x^4 + x^3 + x^3 + x^2 + 1 \\ &\equiv x^4 + 2x^3 + x^2 + 1 \pmod g \end{aligned}$$

接着最后再对$2 x^3$​迭代操作即可

这个迭代操作可以写成下面的flatten函数：

def flatten(f):
  coefs = f.list()
  while not all(abs(_) <= 1 for _ in coefs):
    for i in range(len(coefs)):
      while abs(coefs[i]) >= 2:
        if i+3 > len(coefs):
          coefs += [0]*2
        s = coefs[i].sign()
        coefs[i] -= 2 * s
        coefs[i+1] -= s
        coefs[i+2] -= s
  return R(coefs)

这个Trivial的做法对于$l$很大的情况会迭代得非常慢，所以我还参考了二进制数的计算方法进行了优化

具体是，先计算$1$、$2$、$2^2$…$2^{s_{tep}}$对应的多项式$f_i$：

bits = [R(1)]
for i in range(1, step+1):
  bits += [flatten(bits[-1] * 2)]
  assert bits[-1] % g == 2^i

然后对于输入$l$，转化为二进制表示后把对应的$f_i$相加，然后展平即可

def getf(l):
  f = R(0)
  lb = l.bits()
  for i in range(len(lb)):
    if lb[i]:
      f += bits[i]
  f = flatten(f)
  return f

虽然运算加快了，但是对于大部分的输入发现会不满足条件3（而条件2其实是容易达到的），于是需要进行优化

我的优化方式是选用一些特殊的关系对多项式的某些项进行替换，我选用的关系是$x+1 \equiv -x^2-1$和$x-1 \equiv -x^3+1$

def upgrade(f):
  coefs = f.list() + [0] * 2
  # x+1 = -x^2-1
  for i in range(1, len(coefs)-1):
    if coefs[i-1] == coefs[i] and abs(coefs[i]) == 1:
      coefs[i-1] = - coefs[i-1]
      s = coefs[i].sign()
      coefs[i] -= s
      coefs[i+1] -= s

  # x-1 = -x^3+1
  for i in range(1, len(coefs)-1):
    if coefs[i-1] == -coefs[i] and abs(coefs[i]) == 1:
      coefs[i-1] = - coefs[i-1]
      s = coefs[i].sign()
      coefs[i] -= s
      coefs[i+2] -= s
  return flatten(R(coefs))

'''
count = 0
for l in range(1, 2^13):
  f = getf(Integer(l))
  for _ in range(10):
    f = upgrade(f)
  if check(f, l) != 0:
    count += 1 
print(count)
# 12
'''

对于step = 12的所有数进行测试，发现优化后只有12个数不通过条件3，所以就点到为止了

PS：如果按更新前的题目，估计还要找更好用的关系进行优化，但因为这需要手工去找，所以我还是摆了，

最后写交互脚本即可，总的参考代码：

#!/usr/bin/env sage
from pwn import remote, context
context.log_level = 'debug'
step = 12

R = PolynomialRing(ZZ, 'x')
g = R(x^2 + x + 2)

def check(f, l):
  f = R(f)
  coefs = f.list()
  if not all(abs(_) <= 1 for _ in coefs):
    return 1
  if not f.degree() + 1 - 2 * n(log(l)) >= 0:
    return 2
  if not coefs.count(0) >= 2 * f.degree() // 3 - 3:
    return 3
  if not (f - l) % g == 0:
    return 4
  return 0

def flatten(f):
  coefs = f.list()
  while not all(abs(_) <= 1 for _ in coefs):
    for i in range(len(coefs)):
      while abs(coefs[i]) >= 2:
        if i+3 > len(coefs):
          coefs += [0]*2
        s = coefs[i].sign()
        coefs[i] -= 2 * s
        coefs[i+1] -= s
        coefs[i+2] -= s
  return R(coefs)
        
bits = [R(1)]
for i in range(1, step+1):
  bits += [flatten(bits[-1] * 2)]
  assert bits[-1] % g == 2^i
  assert check(bits[-1], bits[-1] % g) == 0

def getf(l):
  f = R(0)
  lb = l.bits()
  for i in range(len(lb)):
    if lb[i]:
      f += bits[i]
  f = flatten(f)
  return f

def upgrade(f):
  coefs = f.list() + [0] * 2
  # x+1 = -x^2-1
  for i in range(1, len(coefs)-1):
    if coefs[i-1] == coefs[i] and abs(coefs[i]) == 1:
      coefs[i-1] = - coefs[i-1]
      s = coefs[i].sign()
      coefs[i] -= s
      coefs[i+1] -= s

  # x-1 = -x^3+1
  for i in range(1, len(coefs)-1):
    if coefs[i-1] == -coefs[i] and abs(coefs[i]) == 1:
      coefs[i-1] = - coefs[i-1]
      s = coefs[i].sign()
      coefs[i] -= s
      coefs[i+2] -= s
  return flatten(R(coefs))

'''
count = 0
for l in range(1, 2^13):
  f = getf(Integer(l))
  for _ in range(10):
    f = upgrade(f)
  if check(f, l) != 0:
    count += 1 
print(count)
# 12
'''

r = remote('00.cr.yp.toc.tf', 37771)

for s in range(1, step):
  r.recvuntil(b'step %d and n = ' % s)
  l = Integer(r.recvuntil(',')[:-1].decode())
  print(s, l)
  
  f = getf(l)
  for _ in range(16):
    f = upgrade(f)
  r.sendline(str(f).encode())

r.interactive()
r.close()

# ┃ Congrats, you got the flag: b'CCTF{0p71M!5TiC_rEpR3SenT4t!0n_Of_n_8Y_Frobenius!}'

外传·

在刚看到这道题时，我的第一个想法是用背包格去做的

首先对于所有的$x^i \pmod g$，都可以转化为

$$x^i \equiv a_i + b_i x \pmod g$$

的形式

那么令$f = \sum_{i} c_i x^i \equiv l \pmod g$的话，就可以推出

$$\sum_{i} a_i c_i = l \\ \sum_{i} b_i c_i = 0$$

由此可以构造格基

$$B = \begin{bmatrix} -l & \\ a_1 & b_1 \\ a_2 & b_2 & 1 \\ \vdots & \vdots & & \ddots \\ a_d & b_d & & & 1 \end{bmatrix}_{(d+1) \times (d+1)}$$

注意：因为$b_0 = 0$​，所以格基中不能放入0次项，不然会和第一行线性相关

然后可以得到关系

$$(1, c_1, c_2, \cdots, c_d) \cdot B = (0, 0, c_2, \cdots, c_d)$$

因为$c_i$都是$-1$、$0$或$1$​，所以最后的结果是个短向量，于是规约后就可以得到对应的多项式系数

但实际测试中发现效果一般，主要是LLL还是太玄学了

附参考代码：

#!/usr/bin/env sage
step = 12

R = PolynomialRing(ZZ, 'x')
g = R(x^2 + x + 2)

def check(f, l):
  f = R(f)
  coefs = f.list()
  if not all(abs(_) <= 1 for _ in coefs):
    return 1
  if not f.degree() + 1 - 2 * n(log(l)) >= 0:
    return 2
  if not coefs.count(0) >= 2 * f.degree() // 3 - 3:
    return 3
  if not (f - l) % g == 0:
    return 4
  return 0


results = {}
''' non-singular ...
a = [1]
b = [0]
'''
a = []
b = []
size = 32
for i in range(1, size):
  tmp = list(R(x^i) % g)
  a += [tmp[0]]
  b += [tmp[1]]

B = identity_matrix(ZZ, size)
for i in range(size-1):
  B[i+1, 0] = a[i] 
  B[i+1, 1] = b[i] 

for l in range(1, 2^(step+1)):
  B[0, 0] = -l
  L = B.LLL()
  Binv = B^(-1)

  for w in L:
    v = w * Binv
    if abs(v[0]) == 1:
      v = [0] + [Integer(vi) for vi in (v[0]*v)[1:]]
    else:
      continue
    
    f = R(v)
    try:
      i = Integer(f % g)
    except:
      continue

    if check(f, i) == 0:
      try:
        results[i] += [f]
      except:
        results[i] = [f]
      print('Found: %d -> %s' % (i, f))

print(results)

Nazdone·

首先关注sol函数的素数生成，转化一下即

$$p = \sum_{i=1}^{a-1} x_i m^i + 1 + (m (a - 1) \pmod 2),\ x_i \in (0, 1)$$

转化一下，令$b = (m (a - 1) \pmod 2) \in (0, 1)$，即

$$p = m \cdot \sum_{i=0}^{a-2} x_i m^i + 1 + b$$

也就是取决于$b=0$还是$b=1$，有$p-1 \equiv 0 \pmod m$或$p-2 \equiv 0 \pmod m$

把这两个关系转化到$n$中，可以得到

$$\begin{cases} n - 1^3 \equiv 0 \pmod m,\ b=0 \\ n - 2^3 \equiv 0 \pmod m,\ b=1 \end{cases}$$

具体参考：

sage: var('x, y, z')                                                         
(x, y, z)
sage: ((x+1) * (y+1) * (z+1)).expand()                                       
x*y*z + x*y + x*z + y*z + x + y + z + 1
sage: ((x+2) * (y+2) * (z+2)).expand()                                       
x*y*z + 2*x*y + 2*x*z + 2*y*z + 4*x + 4*y + 4*z + 8

于是把$n-1$和$n-8$分解，得到$n-8$中有个特殊的因子$19^7$，于是大概可以确定

$$b = 1 \\ m = 19$$

注：观察回$p = m \cdot \sum_{i=0}^{a-2} x_i m^i + 2$这个式子，其实有很大的概率会有$x_0 = 0$，这样的话就有$p-1 \equiv 0 \pmod {m^2}$，类似的还有$x_i = 0$，于是其实有很大的概率会有$n-8 \equiv \pmod {m^k}$，即$m$的某次是$n-8$的因子，所以看到$19^7$时基本就可以确定了，不过这是人工的做法- -

接下来就要分解$n$，看这个大小似乎无法分解，但现在已经知道$p$、$q$和$r$都是关于$m=19$的多项式，所以可以使用分解多项式的方法进行分解（因为次数不高，所以多项式的分解会更有效）

首先把$n$也转化为关于$m=19$的多项式，粗略怼个代码：

m = 19

R = PolynomialRing(ZZ, 'x')
x = R.gen()
f = R(0)
nn = n
i = 0
while nn != 0:
  f += Integer(nn % 19) * x^i
  nn //= 19
  i += 1

然后对多项式f分解即可，理论上可以分解为3个多项式的乘积，最后把$x=m=19$代进每一条多项式就可以得到$p$、$q$和$r$

pqr = list(factor(f))
assert len(pqr) == 3
p, q, r = [_[0](x=m) for _ in pqr]
assert p * q * r == n

最后就是解密，解密需要知道$z$，就目前已知的信息并不能精确地求得$z$，但是知道$z$一定比多项式的最高次小，所以遍历即可

最终的参考代码：

#!/usr/bin/env sage
with open('./output.txt', 'r') as f:
  exec(f.read())
m = 19

R = PolynomialRing(ZZ, 'x')
x = R.gen()
f = R(0)
nn = n
i = 0
while nn != 0:
  f += Integer(nn % 19) * x^i
  nn //= 19
  i += 1
pqr = list(factor(f))
assert len(pqr) == 3

p, q, r = [_[0](x=m) for _ in pqr]
assert p * q * r == n
print('p = %d' % p)
print('q = %d' % q)
print('r = %d' % r)


phi = (p-1) * (q-1) * (r-1)
zl = max([list(pqr[i][0]-2).count(1) for i in range(3)])
zu = max([pqr[i][0].degree() for i in range(3)])

for z in range(zl, zu):
  e = m^3 + z - 2
  # if gcd != 1 -> https://tover.xyz/p/n-root-in-F/
  if gcd(e, phi) != 1:
    continue
  
  d = Integer(e).inverse_mod(phi)
  try:
    flag = bytes.fromhex(Integer(pow(c, d, n)).hex())
    print('z = %d' % z)
    print(flag)
  except:
    pass


'''
p = 3530869780887683268140728773245395170410635845517928489976021534009516369358447511411853596093628646212566313257712207746790503704123439
q = 67086525836865982094673880600810256005961617151283317566078153226175705789594094624822652838168627925461219084263915001883644637391279141
r = 1274643990900453659882765495755380673132370043776742526720540623203930562265302201405804416214498793910236254519606076438989349099317154363
z = 14
b'CCTF{nUmb3r5_1N_D!fFerEn7_8As35_4r3_n!cE!?}'
'''

RM2·

和Forghan类似，可以指定$p$和$q$，只不过这里的nbit变成1024，但是m1和m2都是256 bits

于是我的做法是，首先构造$n_1 = \frac{p-1}{2}$和$n_2 = 2q+1$都是素数，然后把问题转换到

$$c_1 \equiv m_1 ^ e \pmod {n_1} \\ c_2 \equiv m_2 ^ e \pmod {n_2}$$

显然$m_i < n_i$，而$\varphi(n_i) = n_i-1$，所以接下来就是普通的RSA解密

参考代码：

#!/usr/bin/env sage
from pwn import remote
nbit = 1024
e = 65537

nbit = 1024
u = 2^nbit
l = 2^(nbit-1)

while True:
  p = random_prime(u, proof=False, lbound=l)
  if is_pseudoprime((p-1) // 2):
    break
print('p = %d' % p)

while True:
  q = random_prime(u, proof=False, lbound=l)
  if is_pseudoprime(2*q + 1):
    break
print('q = %d' % q)

r = remote('00.cr.yp.toc.tf', 13371)
r.recvuntil(b'numbers p, q:')
r.sendline(b'%d, %d' % (p, q))
r.recvuntil(b'c1 = ')
c1 = Integer(r.recvline()[:-1].decode())
print('c1 = %d' % c1)
r.recvuntil(b'c2 = ')
c2 = Integer(r.recvline()[:-1].decode())
print('c2 = %d' % c2)

r.recvuntil(b'get the flag:')
n1 = (p-1) // 2
n2 = 2*q + 1
d1 = e.inverse_mod(n1-1)
d2 = e.inverse_mod(n2-1)
m1 = Integer(pow(c1, d1, n1))
m2 = Integer(pow(c2, d2, n2))
m = bytes.fromhex(hex(m1)[2:]) + bytes.fromhex(hex(m2)[2:])
print(m)
r.sendline(m)

r.interactive()
r.close()

'''
p = 170419411044243649575968568803119326480062498303185788757071683273958787501743289158767039780358010332500195646057645005603590293451945001588177653208249251401019010667035815261810566080788928697123451536081716869901257854819010875458997170623472465566246148371246774656922716246196644404529783720097279174943
q = 121389429224881811999842712420895892425740113903137501530787005343385394926001080709658313369142519153140009435127621843306477837497056646141722688050506424312270814711879431587802438068190431318799563221153768753250146454542011878594872033023525321627672861037474813080296293841821790394857701843118231428379

c1 = 16851109719674747515928162790979103019121652069351377283379480448414701835722334551663300991482001099269835613375074853214302856817000930895730076912290596861378085399506620701658500264716618864092040522915429553883521065911904101203127015799080857315580215146805413199212844765588556378611989193651949698282520103198862698636200367661108241526563903850975173038763877640383311130133991451517233765715051522347999611293800019711410468042216877341258348264514991734670604499204300485082305427627676235514370697704034130719642571551678298929097015712514262273244419736689188158296231848134665921617592574063920283684300
c2 = 11388759558547894146779330952019236740837002218897449957026077029951318715765049464891259134512701437892209542200251851372417057656668181424841199699005825316073094792043493689603551180610164632243899965524360006851205640109225367899576814217366714662729507780375710594933434891752958309210951833796677191487794028456740265322188994453821863137132611991231095575388866223168333734421585130656326335795251214823194429125162337364029662033796076227066646295836292688007752587369451481088391725076886219116499352583969396611525407786280609852756419439839918482004730801189223247350212092815673576195530685321127526064370
b'gz@[i8r\\_E6?sI3Y!RSX7.="3,"[9q@0]&Y<E=qhq&Wurmp,EOswG^)odXuK:?l:'

┃ Congrats, you got the flag: b'CCTF{i_l0v3_5UpeR_S4fE_Pr1m3s!!}'
'''

Soufia·

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ .::   Soufia is a random oracle, your mission is to break it   ::. ┃
┃ We know that f: Z → Z and for all integers `x' and `y' we have:    ┃
┃     f(t * x) + t * f(x) = f(f(x + y)) for constant integer `t'.    ┃
┃ Also, f(0) = 171179160041154255998170822544254161925,              ┃
┃ and   f(9) = 2918265810101910926377464647051822947123              ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┃ Please send the f(10):

不是，这递推式左边怎么没有$y$啊，盲猜应该是（后来也从春哥的WP里石锤了）

$$f(t x) + t f(y) = f(f(x + y))$$

于是就先推出一个好看一点的递推式

首先消去等号右边的奇奇怪怪的形式，理论上只要所给的$x$和$y$的和值相同，等号右边那一块就相同，于是就可以使用这个方法构造新的等式

而我要推的是递推式，所以便代入$y = i$和$y = i-1$（之所以不代入$x$是因为$f(t x)$里面有个$t$会影响我构造），对应的$x$中要代入$x = 0$和$x = 1$，就得到

$$\begin{aligned} f(0) + t f(i) &= f(f(i)) \\ f(t) + t f(i-1) &= f(f(i)) \end{aligned}$$

联立，得

$$f(0) + t f(i) = f(t) + t f(i-1)$$

然后整理可得

$$f(i) - f(i-1) = \frac{f(t) - f(0)}{t}$$

由于$t$是个常数，所以不管等号右边的多复杂，都是个常数，不妨令$c = \frac{f(t) - f(0)}{t}$，即

$$f(i) = f(i-1) + c$$

题目给了$f(0)$和$f(9)$，于是应该用

$$f(x) = f(0) + cx$$

代入$f(9)$求得$c$后算$f(10)$即可（上面输出为例，实测每次给的不一样，不过会给$f(0)$）

参考代码：

#!/usr/bin/env sage
from pwn import remote, context
context.log_level = 'debug'

r = remote('00.cr.yp.toc.tf', 13377)
r.recvuntil(b'f(0) = ')
f0 = Integer(r.recvuntil(b',')[:-1].decode())

r.recvuntil(b'and   f(')
x = Integer(r.recvuntil(b')')[:-1].decode())
r.recvuntil(b' = ')
fx = Integer(r.recvuntil(b' ')[:-1].decode())
c = (fx - f0) // x

for _ in range(20):
  r.recvuntil(b'the f(')
  y = Integer(r.recvuntil(b')')[:-1].decode())
  fy = f0 + c * y
  r.sendline(str(fy).encode())

r.interactive()
r.close()

# ┃ Congratz! You got the flag: b'CCTF{A_funCti0nal_3qu4tiOn_iZ_4_7yPe_oF_EquAtioN_tHaT_inv0lVe5_an_unKnOwn_funCt!on_r4tH3r_thAn_juS7_vArIabl3s!!}'

Vantuk·

代入方程可得3个关系

$$\begin{aligned} A &= a + \frac{5a - 4a}{a^2 + (4a)^2} \\ U &= m_1 + \frac{a m_1 - m_2}{m_1^2 + m_2^2} \\ V &= m_2 - \frac{m_1 + am_2}{m_1^2 + m_2^2} \end{aligned}$$

首先用$A$解$a$，化简$A$可得

$$A = a + \frac{5a - 4a}{a^2 + (4a)^2} = a + \frac{a}{17 a^2} = a + \frac{1}{17 a} = \frac{17a^2+1}{17a}$$

假设分子分母的公约数为$1$，那么从输出的$A$的分子分母中即可得到$17a^2+1$和$17a$，于是解得$a$

An = A.numerator()
Ad = A.denominator()
a = Ad // 17
assert Ad % 17 == 0
assert 17 * a^2 + 1 == An
print('a = %d' % a)

接着就要用$U$、$V$和$a$去解$m_1$和$m_2$，首先化简$U$和$V$，不妨令$b = m_1^2 + m_2^2$，则

$$\begin{aligned} U &= m_1 + \frac{a m_1 - m_2}{b} = \frac{(a+b) m_1 - m_2}{b} \\ V &= m_2 - \frac{m_1 + am_2}{b} = \frac{-m_1 + (b-a) m_2}{b} \end{aligned}$$

那么用类似的方法，从$U$和$V$的分母中可以拿到$b$，而从分子中可以拿到

$$\begin{aligned} U_n &= (a+b) m_1 - m_2 \\ V_n &= -m_1 + (b-a) m_2 \end{aligned}$$

两个方程两个未知数，可解，于是构造线性方程

$$(m_1, m_2) = (U_n, V_n) \begin{bmatrix} a+b & -1 \\ -1 & b-a \end{bmatrix}^{-1}$$

可解得$m_1$和$m_2$，于是

Un = U.numerator()
Ud = U.denominator()
Vn = V.numerator()
Vd = V.denominator()
assert Ud == Vd
b = Ud
print('b = %d' % b)

M = matrix(ZZ, [
    [a+b, -1],
    [-1, b-a]
])
w = vector(ZZ, (Un, Vn))
v = w * M^(-1)
m1, m2 = v

很不幸解出来的$m_1$和$m_2$都不是整数，但理论上是对的

再check了一下，发现有可能是$U$和$V$的分子分母都约了一个公约数（注意题目数据中的$U$和$V$的分母是一样的）

于是遍历一下小因子，发现果然约了个因子$5$

最终的参考代码：

#!/usr/bin/env sage
A = 6080057478320734754578252336954411086329731226445881868123716230995225973869803901199434606333357820515656618869146654158788168766842914410452961599054518002813068771365518772891986864276289860125347726759503163130747954047189098354503529975642910040243893426023284760560550058749486622149336255123273699589/10166660077500992696786674322778747305573988490459101951030888617339232488971703619809763229396514541455656973227690713112602531083990085142454453827397614
U = 3225614773582213369706292127090052479554140270383744354251548034114969532022146352828696162628127070196943244336606099417210627640399143341122777407316956319347428454301338989662689983156270502206905873768685192940264891098471650041034871787036353839986435/9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609
V = 1971582892158351181843851788527088806814104010680626247728311504906886858748378948163011806974145871263749452213375101951129675358232283650086419295655854343862361076089682606804214329522917382524296561295274823374483828323983651110722084223144007926678084087/9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609

An = A.numerator()
Ad = A.denominator()
a = Ad // 17
assert Ad % 17 == 0
assert 17 * a^2 + 1 == An
print('a = %d' % a)

Un = U.numerator()
Ud = U.denominator()
Vn = V.numerator()
Vd = V.denominator()
assert Ud == Vd
b = Ud
print('b = %d' % b)

for g in range(1, 1997):
  M = matrix(ZZ, [
    [a+g*b, -1],
    [-1, g*b-a]
  ])
  w = vector(ZZ, (g*Un, g*Vn))
  v = w * M^(-1)
  m1, m2 = v
  try:
    flag = bytes.fromhex(hex(m1)[2:]) + bytes.fromhex(hex(m2)[2:])
    print('g = %d' % g)
    print(flag)
  except:
    pass

'''
a = 598038828088293688046274960163455723857293440615241291237111095137601911115982565871162542905677325967979821954570041947800148887293534420144379636905742
b = 9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609
g = 5
b'.:: CCTF{d!D_y0U_5oLv3_7HiS_eQu4T!On_wItH_uSing_c0mPlEx_Num8erS!!?} ::.'
'''

Hard·

绝赞更新中…

Tough·

绝赞更新中…