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·

Chochol·

这题和Solmaz有点类似

首先两个曲线形如

$$E_p : y^2 \equiv x^3 + a x \pmod p \\ E_q : y^2 \equiv x^3 + a x \pmod q \\$$

第一步需要恢复曲线的参数$a$、$p$和$q$

先拿$E_q$做例子，题目给了$E_q$上的两个点，不妨令

PS：之所以先搞$E_q$，是因为实际操作的时候发现$E_q$的数据好操作一点

$$G_q = (x_{q1}, y_{q1}) \\ H_q = (x_{q2}, y_{q2})$$

那么就有

$$y_{q1}^2 \equiv x_{q1}^3 + a x_{q1} \pmod q \\ y_{q2}^2 \equiv x_{q2}^3 + a x_{q2} \pmod q \\$$

联立两个方程消去多余的$a$，对上式乘$x_{q2}$，对下式乘$x_{q1}$，然后相减得到

$$(y_{q1}^2-x_{q1}^3) * x_{q2} \equiv (y_{q2}^2-x_{q2}^3) * x_{q1} \pmod q$$

于是存在一个k使得

$$k q = (y_{q1}^2-x_{q1}^3) * x_{q2} - (y_{q2}^2-x_{q2}^3) * x_{q1}$$

在这个题目中，$q$是128 bits，那么$kq$大概是256 bits，是一个不大的数，所以可以考虑暴力分解

当时做的时候队友说Yafu不太行，所以我的做法是直接上Cado

PS：把$kq$的小因子去掉后再跑Cado的话会快很多

然后分解得到

$$q = 278451262698064898668334196027031252819$$

有了$q$后，就可以算出

$$a \equiv (y_{qi}^2 - x_{qi}^3) x_{qi}^{-1} \pmod q$$

接着再看$E_p$，不妨令

$$G_p = (x_{p1}, y_{p1}) \\ H_p = (x_{p2}, y_{p2})$$

就有

$$y_{p1}^2 \equiv x_{p1}^3 + a x_{p1} \pmod p \\ y_{p2}^2 \equiv x_{p2}^3 + a x_{p2} \pmod p \\$$

由于$E_p$和$E_q$用的相同的$a$，所以就不用再分解一次了

由两式可知道存在$k_1$和$k_2$，使得

$$k_1 p = y_{p1}^2 - x_{p1}^3 - a x_{p1} \\ k_2 p = y_{p2}^2 - x_{p2}^3 - a x_{p2} \\$$

最后计算

$$p = gcd(k_1 p, k_2 p)$$

即可

恢复参数的参考代码：

#!/usr/bin/env sage
Gp = (2024, 77522466419731346352388161327659294096)
Hp = (187001239996895215821259450553198409012, 158495938026527642884038157170741730943)
Gq = (2024, 92609909821520263487623088269239797003)
Hq = (191534442430060308634251661645421139195, 102273233384427938890774177710170123915)
c  = 15084463560924811262750235394027264639346464192638172940901706702947534963652

xp1, yp1 = Gp
xp2, yp2 = Hp
xq1, yq1 = Gq
xq2, yq2 = Hq

kp = (yp1^2-xp1^3) * xp2 - (yp2^2-xp2^3) * xp1
kq = (yq1^2-xq1^3) * xq2 - (yq2^2-xq2^3) * xq1
assert kp % (2^3 * 5^2 * 47) == 0
assert kq % (5^2 * 11 * 23 * 521 * 1271953 * 3018047 * 25079843 * 5681358923) == 0
kp //= (2^3 * 5^2 * 47)
kq //= (5^2 * 11 * 23 * 521 * 1271953 * 3018047 * 25079843 * 5681358923)
# by cado
assert kq == 28338689773015872412188935645719088445835579 * 278451262698064898668334196027031252819

q = 278451262698064898668334196027031252819
assert q.nbits() == 128
print('q = %d' % q)

a = Integer((yq1^2 - xq1^3) * pow(xq1, -1, q) % q)
print('a = %d' % a)

kp1 = abs(yp1^2 - xp1^3 - a * xp1)
kp2 = abs(yp2^2 - xp2^3 - a * xp2)
p = gcd(kp1, kp2)
assert p.nbits() == 128
print('p = %d' % p)

'''
q = 278451262698064898668334196027031252819
a = 127671661251150651301269745259748083900
p = 243678574849421895808521345944938402807
'''

恢复参数后发现$E_p$的阶是平滑的，Pohlig-Hellman解之即可

另外，观察发现$E_p$的阶是$p+1$，所以也可以用MOV算法，更快

解出来后会发现解出来的$s$满足

$$s G_p = H_p$$

但不满足

$$s Gq = Hq$$

原因是真正的$s$比$H_p$（或$G_p$）的阶更大，遍历一下加上$H_p$的阶的倍数即可

最后就是RSA解密，这里因为$gcd(s, \varphi) \ne 1$，所以不能普通的解，直接调之前写好的模板即可

后半部分的参考代码

#!/usr/bin/env sage
import string

q = 278451262698064898668334196027031252819
a = 127671661251150651301269745259748083900
p = 243678574849421895808521345944938402807

c  = 15084463560924811262750235394027264639346464192638172940901706702947534963652
Gp = (2024, 77522466419731346352388161327659294096)
Hp = (187001239996895215821259450553198409012, 158495938026527642884038157170741730943)
Gq = (2024, 92609909821520263487623088269239797003)
Hq = (191534442430060308634251661645421139195, 102273233384427938890774177710170123915)

Ep, Eq = EllipticCurve(GF(p), [a, 0]), EllipticCurve(GF(q), [a, 0])
Gp = Ep(Gp)
Hp = Ep(Hp)
Gq = Eq(Gq)
Hq = Eq(Hq)

assert Ep.order() == p + 1
assert Eq.order() == q + 1

'''
# Not good :(
s = discrete_log(Hp, Gp, operation='+')
assert s * Gp == Hp
'''

# better (:
# https://zhuanlan.zhihu.com/p/421541257
def MOV(E, G, H):
        k = 2
        p = Integer(E.base()(-1)) + 1
        F1 = GF(p)
        F2 = GF(p^k)
        phi = Hom(F1, F2)(F1.gen().minpoly().roots(F2)[0][0])
        E1 = E
        E2 = E.change_ring(F2)

        n = E1.order()
        G1 = E1(G)
        H1 = E1(H)

        G2 = E2(phi(G1.xy()[0]), phi(G1.xy()[1]))
        H2 = E2(phi(H1.xy()[0]), phi(H1.xy()[1]))

        cn1 = p + 1
        coeff = ZZ(cn1 / n)

        Q = coeff * E2.random_point()
        alpha = G2.weil_pairing(Q, n)
        beta = H2.weil_pairing(Q, n)
        s = beta.log(alpha)
        return Integer(s)

s = MOV(Ep, Gp, Hp)

print(s)

for _ in range(1000):
        if s * Gq == Hq:
          break
        s += Hp.order()
print(s, gcd(s, (p-1)*(q-1)))

load('./nth.sage')
checker = genStrChecker(string.printable)
res = nthRSA_n(c, s, [p, q], [1, 1], checker=checker)
print(res)
for r in res:
  flag = libnum.n2s(int(r))
  print(flag)


'''
50295274560999838770579032062844522666
172134561985710786674839705035313724070 6
[Log] Complexity = 36: [6, 6]
  0%|                                                                                                          | 0/36 [00:00<?, ?it/s]m1X!n9__3cC__&_R54_!
100%|██████████████████████████████████████████████████████████████████████████████████████████████| 36/36 [00:00<00:00, 75838.75it/s]
[623380407791519586796790884342787036947739336481]
b'm1X!n9__3cC__&_R54_!'
'''

Imen·

复现的时候环境已经下架了，等NSS的环境修好了再回来补（逃

Latifa·

加密其实就是一个求和公式

$$\sum_{i=0}^{m} \frac{b g}{g^{2i/m} + g}$$

把公式扔进Wolfram Alpha中

结果有点复杂…

但总所周知，求和的结果其实接近于求积分，所以不妨用积分近似一下

化简并近似一下就是

$$\begin{aligned} c &=\frac{b m (2 log(g) + log(g + 1) - log(g (g + 1)))}{2 log(g)} \\ &= b m \frac{2 log(g) + log(g + 1) - log(g (g + 1)}{2 log(g)} \\ &= b m (1 + \frac{log(g + 1)}{2 log(g)} - \frac{log(g (g + 1)}{2 log(g)}) \\ &\approx b m (1 + \frac{log(g)}{2 log(g)} - \frac{log(g^2)}{2 log(g)}) \\ &= b m (1 + \frac{1}{2} - 1) \\ &= \frac{bm}{2} \end{aligned}$$

大胆假设，小心求证，我用了几个例子试过，发现结果都接近$\frac{bm}{2}$，接近的程度取决于$g$的大小

而且观察题目的输出可以发现，加密的结果后面都是0，这只有在$g$很小的情况下才会发生（比如显然的$g=1$，我试过$g=2$有点机会，$g=3$就不行了）

原因是题目中的

n(pow(g, Rational(2*i/m)), prec = b)

在$g$增大时，会大概率出现无限的小数

所以假设$g=1$的话，就是

$$c = \frac{bm}{2}$$

接下来求证一下，要先求出$b$

首先从输出的精度上可以得到

c = ... ...
print(c.prec())
# 39717

所以知道$b$是一个接近且大于$39717$的数

然后从$(2 * c)$的因子中找符合条件的数，可以得到

$$b = 39719$$

接下来计算

$$m = \frac{2c}{b}$$

实现解密

参考代码

c = ... ...
b = 39719
g = 1
m = Integer(c * 2) // b
print(bytes.fromhex(hex(m)[2:]))
# b'h4Lf_7UrN_5ym3Try!'

PS：实际上我做的时候是遍历$(2*c)$的因子来求$b$的，即

c2 = Integer(c * 2)
for b in c2.divisors():
  try:
    print('%s, %s' % (b, bytes.fromhex(hex(c2 // b)[2:])))
  except:
    pass
# 39719, b'h4Lf_7UrN_5ym3Try!'

PPS：做这题的时候有一个坑点是，如果用

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

去读数据的话，读出来的类型是float，就出现精度损失，导致后面会解错

O7R·

第一步要把数据读进来，我的方法是对每个变量都截个图，然后用OpenCV读，主打一个有多人工就有多智能

首先需要定位每个数字的位置，比如我选择先定位每个数字的左上角，观察一下pdf的渲染发现，只需要判断上一行是全白的且下一行不是全白的位置，就可以得到每一行数字的顶端的位置，同理对列做同样的操作即可得到每一列数字的最左侧的位置

然后还需要得到每个数字占用的长宽，类似的操作，判断上一行不是全白且下一行是全白即可得到每一行数字的底部位置，底部位置减去顶端位置即使每个数字的长度，同理对列进行操作可得到宽度

注意实际操作会发现每列数字的宽度其实不都是一样的，这里算是一个坑

import cv2

def format(a):
  return int(a > 128)

def T(data):
  h = len(data)
  w = len(data[0])
  return [[data[hi][wi] for hi in range(h)] for wi in range(w)]

def getPos(data):
  h = len(data)
  w = len(data[0])

  # get position
  posH = []
  hi = 0
  while hi < h:
    tmp = []
    for hj in range(hi, h):
      if len(set(data[hj])) == 1:
        continue
      tmp += [hj]
      break

    if not tmp:
      break

    for hj in range(tmp[0], h):
      if len(set(data[hj])) == 1:
        tmp += [hj]
        break

    posH += [tmp]
    hi = hj

  data2 = T(data)
  posW = []
  wi = 0
  while wi < w:
    tmp = []
    for wj in range(wi, w):
      if len(set(data2[wj])) == 1:
        continue
      tmp += [wj]
      break

    if not tmp:
      break

    for wj in range(tmp[0], w):
      if len(set(data2[wj])) == 1:
        tmp += [wj]
        break

    posW += [tmp]
    wi = wj

  return (posH, posW)

有了每个数字的位置和长宽后，就可以通过采样，得到每个数字的七段数码管的值，采样的方式可以按个人爱好来，附个我使用的采样代码

def getDataN(data):
  posH, posW = getPos(data)
  res = []
  for ph in posH:
    for pw in posW:
      deltaH = ph[1] - ph[0]
      deltaW = pw[1] - pw[0]
      r = []
      r += [int(data[ph[0]+2][pw[0]+deltaW//2] == 0)]             #  -
      r += [int(data[ph[0]+deltaH//3][pw[0]+2] == 0)]             # |
      r += [int(data[ph[0]+deltaH//3][pw[1]-3] == 0)]             #   |
      r += [int(data[ph[0]+deltaH//2][pw[0]+deltaW//2] == 0)]     #  -
      r += [int(data[ph[0]+deltaH*2//3][pw[0]+2] == 0)]           # |
      r += [int(data[ph[0]+deltaH*2//3][pw[1]-3] == 0)]           #   |
      r += [int(data[ph[1]-3][pw[0]+deltaW//2] == 0)]             #  -
      if r == [0] * 7:
        return res
      res += [r]
  return res

最后就是把七段数码管解码成数字，由于题目给的数据有缺失，所以现在还不能解出准确的数字，我的做法是选择先把每个数字可能性存起来

根据pdf的摘要，每个数字只可能是完整的，或者缺了一段，所以先怼个对比函数cmp，判断两个数字间缺失/增加了多少段

def cmp(a, b):
  assert len(a) == len(b)
  ad = 0
  mi = 0
  for i in range(len(a)):
    if a[i] != b[i]:
      if a[i] == 1:
        ad += 1
      else:
        mi += 1
  return (ad, mi)

然后对每个数字只记录完整或缺了一段的数字即可

def getNum(data, corrupted=True):
  dn = getDataN(data)
  dic = [
      [1, 1, 1, 0, 1, 1, 1],
      [0, 0, 1, 0, 0, 1, 0],
      [1, 0, 1, 1, 1, 0, 1],
      [1, 0, 1, 1, 0, 1, 1],
      [0, 1, 1, 1, 0, 1, 0],
      [1, 1, 0, 1, 0, 1, 1],
      [1, 1, 0, 1, 1, 1, 1],
      [1, 0, 1, 0, 0, 1, 0],
      [1, 1, 1, 1, 1, 1, 1],
      [1, 1, 1, 1, 0, 1, 1]
  ]

  res = []
  for dni in dn:
    tmp = set()
    for j in range(len(dic)):
      c = cmp(dni, dic[j])
      if corrupted and (c == (0, 0) or c == (0, 1)):
        tmp.add(j)
      elif (not corrupted) and c == (0, 0):
        tmp.add(j)
    res += [list(tmp)]
  return res

到这里已经完成了数据的读取，接下来就是要根据所读取的数据恢复p和q

首先恢复n，方法也不难，就是根据关系

$$n^2 \equiv n_2 \pmod {10^i}$$

遍历每一位，进行剪枝，如无意外剪完就只剩下一个结果，参考代码

# n^2 \equiv n2 \pmod {10^i}
def gaoN(a, i):
  if i >= len(dn):
    return [a]

  res = []
  for ni in dn[-i-1]:
    b = ni * 10**i + a
    #print(b)
    if digit(b**2, i) in dn2[-i-1]:
      res += gaoN(b, i+1)
  return res

ns = gaoN(0, 0)

恢复p和q也是类似的操作，根据关系

$$p q \equiv n \pmod {10^i}$$

遍历每一位进行剪枝

# p * q \equiv n \pmod {10^i}
def gaoP(a, b, i):
  if i >= len(dp):
    return [(a, b)]

  res = []
  mod = 10**(i+1)
  ni = n % mod
  for pi in dp[-i-1]:
    aa = pi * 10**i + a
    for qi in dq[-i-1]:
      bb = qi * 10**i + b
      #print(aa, bb)
      if aa * bb % mod == ni:
        res += gaoP(aa, bb, i+1)
  return res

pq = gaoP(0, 0, 0)

最后解密即可

最终的参考代码（附我使用的截图数据：data.zip）：

import cv2

def format(a):
  return int(a > 128)

def T(data):
  h = len(data)
  w = len(data[0])
  return [[data[hi][wi] for hi in range(h)] for wi in range(w)]

def getPos(data):
  h = len(data)
  w = len(data[0])

  # get position
  posH = []
  hi = 0
  while hi < h:
    tmp = []
    for hj in range(hi, h):
      if len(set(data[hj])) == 1:
        continue
      tmp += [hj]
      break

    if not tmp:
      break

    for hj in range(tmp[0], h):
      if len(set(data[hj])) == 1:
        tmp += [hj]
        break

    posH += [tmp]
    hi = hj

  data2 = T(data)
  posW = []
  wi = 0
  while wi < w:
    tmp = []
    for wj in range(wi, w):
      if len(set(data2[wj])) == 1:
        continue
      tmp += [wj]
      break

    if not tmp:
      break

    for wj in range(tmp[0], w):
      if len(set(data2[wj])) == 1:
        tmp += [wj]
        break

    posW += [tmp]
    wi = wj

  return (posH, posW)

def getDataN(data):
  posH, posW = getPos(data)
  res = []
  for ph in posH:
    for pw in posW:
      deltaH = ph[1] - ph[0]
      deltaW = pw[1] - pw[0]
      r = []
      r += [int(data[ph[0]+2][pw[0]+deltaW//2] == 0)]             #  -
      r += [int(data[ph[0]+deltaH//3][pw[0]+2] == 0)]             # |
      r += [int(data[ph[0]+deltaH//3][pw[1]-3] == 0)]             #   |
      r += [int(data[ph[0]+deltaH//2][pw[0]+deltaW//2] == 0)]     #  -
      r += [int(data[ph[0]+deltaH*2//3][pw[0]+2] == 0)]           # |
      r += [int(data[ph[0]+deltaH*2//3][pw[1]-3] == 0)]           #   |
      r += [int(data[ph[1]-3][pw[0]+deltaW//2] == 0)]             #  -
      if r == [0] * 7:
        return res
      res += [r]
  return res

def cmp(a, b):
  assert len(a) == len(b)
  ad = 0
  mi = 0
  for i in range(len(a)):
    if a[i] != b[i]:
      if a[i] == 1:
        ad += 1
      else:
        mi += 1
  return (ad, mi)

def getNum(data, corrupted=True):
  dn = getDataN(data)
  dic = [
      [1, 1, 1, 0, 1, 1, 1],
      [0, 0, 1, 0, 0, 1, 0],
      [1, 0, 1, 1, 1, 0, 1],
      [1, 0, 1, 1, 0, 1, 1],
      [0, 1, 1, 1, 0, 1, 0],
      [1, 1, 0, 1, 0, 1, 1],
      [1, 1, 0, 1, 1, 1, 1],
      [1, 0, 1, 0, 0, 1, 0],
      [1, 1, 1, 1, 1, 1, 1],
      [1, 1, 1, 1, 0, 1, 1]
  ]

  res = []
  for dni in dn:
    tmp = set()
    for j in range(len(dic)):
      c = cmp(dni, dic[j])
      if corrupted and (c == (0, 0) or c == (0, 1)):
        tmp.add(j)
      elif (not corrupted) and c == (0, 0):
        tmp.add(j)
    res += [list(tmp)]
  return res

def gao(fn, corrupted=True):
  img = cv2.imread(fn, cv2.IMREAD_GRAYSCALE)
  h, w = img.shape
  data = [[format(img[hi, wi]) for wi in range(w)] for hi in range(h)]
  num = getNum(data, corrupted)
  if not corrupted:
    num = int(''.join([str(ni[0]) for ni in num]))
  return num

dn = gao('./data/n.png')
dn2 = gao('./data/n21.png') + gao('./data/n22.png')

def digit(a, i):
  return (a // (10**i)) % 10

# n^2 \equiv n2 \pmod {10^i}
def gaoN(a, i):
  if i >= len(dn):
    return [a]

  res = []
  for ni in dn[-i-1]:
    b = ni * 10**i + a
    #print(b)
    if digit(b**2, i) in dn2[-i-1]:
      res += gaoN(b, i+1)
  return res

ns = gaoN(0, 0)
assert len(ns) == 1
n = ns[0]
print(n)
#n = 51840653766135257556705784110586546118676089708004013435602970220926295283816878821050426175442651800294714598543387936802967395783256810099645552253441747581358771859540018337692473506717451852649939157063176604854122365788654002888134740888490552508260965571678016738291345759316361219424782467740769731273

dp = gao('./data/p.png')
dq = gao('./data/q.png')

# p * q \equiv n \pmod {10^i}
def gaoP(a, b, i):
  if i >= len(dp):
    return [(a, b)]

  res = []
  mod = 10**(i+1)
  ni = n % mod
  for pi in dp[-i-1]:
    aa = pi * 10**i + a
    for qi in dq[-i-1]:
      bb = qi * 10**i + b
      #print(aa, bb)
      if aa * bb % mod == ni:
        res += gaoP(aa, bb, i+1)
  return res

pq = gaoP(0, 0, 0)
assert len(pq) == 1
p, q = pq[0]
print(p, q)
# p = 7326673976775677403615902952775786009780696864351810113969520603559523530618382637866632341958388570488543071638027072634087397361132795284727648994814597
# q = 7075605374343310393660736847187727587911784641033429799366923429044581810690842608691612098700666156539827395662425799607464237168537039463467940973806709

c = gao('./data/c.png', False)
print(c)
#c = 3562663791006368034141977288433903435480729754256243271724528203580472770993094486280368310543613382256743525891807443983661459665243901555404810179525594817342115941001759547407703653781422057871347356603203075709275979343680289210665741824992476238299997444201948575831891922291318008008982215564064059476

import libnum
e = 65537
phi = (p-1) * (q-1)
d = libnum.invmod(e, phi)
m = pow(c, d, n)
flag = libnum.n2s(m)
print(flag)
# b'CCTF{5eVEn_S39Men7_RSA_w!Th_k3Y_rEc0v3Ry!!!}'

Solmaz·

这题和Chochol有点类似

首先需要恢复素数$p$，看素数$p$的结构

$$p = 4 \cdot \sum_{i=1}^{4} t_i^2 + 1$$

其中$t_i$是$32$比特，这么看的话$p-1$就是个平滑数，但这个结论暂时还没啥用

继续往下看，题目只公开了点$P$和$Q$的信息，不妨令

$$P = (x_1, y_1) \\ Q = (x_2, y_2)$$

那么就有

$$y_1^2 \equiv x_1^3 + c x_1 \pmod p \\ y_2^2 \equiv x_2^3 + c x_2 \pmod p \\$$

联立两个方程消去多余的$c$，对上式乘$x_2$，对下式乘$x_1$，得

$$x_2 y_1^2 \equiv x_2 x_1^3 + c x_2 x_1 \pmod p \\ x_1 y_2^2 \equiv x_1 x_2^3 + c x_1 x_2 \pmod p \\$$

然后相减

$$x_2 y_1^2 - x_1 y_2^2 \equiv x_2 x_1^3 - x_2 x_1^3 \pmod p \\$$

于是就有

$$(x_2 y_1^2 - x_1 y_2^2) - (x_2 x_1^3 - x_2 x_1^3) = k p$$

P = (1338, 9218578132576071095213927906233283616907115389852794510465118810355739314264)
Q = (3454561753909947353764378180794889923919743476068813953002808647958908878895, 17267599534808803050751150297274989016063324917454246976792837120400888025519)
x1, y1 = P
x2, y2 = Q

kp = (x2 * y1^2 - x1 * y2^2) - (x2 * x1^3 - x1 * x2^3)
print(kp)
# 55454940004513276799611588380059302189664933020838413515384708243928267219228512844352832003082349090934777517286737687281070260517892560156083453894086877367076953177914949876201881341274104406095268673060476748059522884381040212

到这里再回看一下，$p-1$是个平滑数，所以可以用Pollard’s p-1算法分解$kp$得到$p$

先回顾一下Pollard’s p-1算法，令

$$L = \prod_{j=1}^{某个上界} j$$

如果$p-1$整除$L$的话，就可以找到一个生成元$a$，使得

$$a^L \equiv 1 \pmod p$$

于是通过计算

$$p = gcd(a^L - 1, kp)$$

就可以分解

PS：当然前提是$k-1$不整除$L$，显然这个是大概率可以保证的

如果直接用上述的Pollard’s p-1算法解的话，会发现并不能分解，原因是这个题目中的$p$的结构是

$$p = 4 \cdot \sum_{i=1}^{4} t_i^2 + 1$$

而对于$L = \prod_{j=1} j$这种形式其实只使用于没有平方的$p = 4 \cdot \sum_{i=1}^{4} t_i + 1$这种结构

于是就需要稍微修改一下算法，使用

$$L = \prod_{j=1}^{2^{32}} j^2$$

进行爆破，为了省事我就直接用之前强网杯数学赛的代码改

import _thread
from gmpy2 import gcd, powmod, next_prime
import time

DONE = None
def check(n, a, pi, lfn):
  global DONE
  d = gcd(a-1, n)
  log = '[Debug - %s] pi = %d\ta = %d\t d = %d' % (time.asctime(time.localtime(time.time())), pi, a, d)
  if d == n:
    print('Bias so large!')
    DONE = False
    return
  if d > 1 and d < n:
    print('Done:')
    DONE = d   # assert BIAS is large enough, so omit lock
    log += '\n[Done] d = %d' % d
  print(log)
  if lfn != None:
    with open(lfn, 'a') as lf:
      lf.write(log + '\n')
  return

def pollard(n, a=1997, pi=2, B=4294967296, lfn=None, BIAS=100000):
  global DONE
  counter = 0
  while pi < B:
    counter += 1
    a = powmod(a, pi**2, n)
    if counter == BIAS:
      #if DONE != None:
      #  break
      counter = 0
      _thread.start_new_thread(check, (n, a, pi, lfn, ) )
    pi = next_prime(pi)
  print(a)
  return DONE

n = 55454940004513276799611588380059302189664933020838413515384708243928267219228512844352832003082349090934777517286737687281070260517892560156083453894086877367076953177914949876201881341274104406095268673060476748059522884381040212
print(pollard(n, lfn='2.log', BIAS=1000000))

'''
[Debug - Sun Jun  9 12:33:08 2024] pi = 4288745689      a = 41796247117548419842067502887605859178728492422481636548744332802536552090555044041852177722341635878380287586624149488684405428698014974559269656456979765616334263342731950862444943868887167328019636800628738987823732429850433301       d = 1566581522863345508373538061687634135881069744445964147271311412129513267140484
[Done] d = 1566581522863345508373538061687634135881069744445964147271311412129513267140484
23632405699744684254857279227122949585597970532057770285914309757078720472714878357874858662881309542928360162136993847765326890804157599045393522175874544969750365847185152917221589844874068096188042339732844999687445319803827613
1566581522863345508373538061687634135881069744445964147271311412129513267140484
'''

PS：最近换了新电脑，发现其实这个代码并不慢，爆出来还不用一小时，只是之前的旧电脑慢而已，之前强网数学赛吃了不少亏啊。。。

爆出来是

1566581522863345508373538061687634135881069744445964147271311412129513267140484

扔进factorDB再分解一下得到

p = 30126567747372029007183424263223733382328264316268541293679065617875255137317

有了$p$后就可以算出$c$，然后恢复曲线后发现阶也是平滑的，直接上discrete_log即可

#!/usr/bin/env sage

p = 30126567747372029007183424263223733382328264316268541293679065617875255137317
P = (1338, 9218578132576071095213927906233283616907115389852794510465118810355739314264)
Q = (3454561753909947353764378180794889923919743476068813953002808647958908878895, 17267599534808803050751150297274989016063324917454246976792837120400888025519)
x, y = P

c = Integer((y^2 - x^3) * pow(x, -1, p) % p)
E = EllipticCurve(GF(p), [c, 0])
P = E(P)
Q = E(Q)

m = discrete_log(Q, P, operation='+')
print(m)
flag = bytes.fromhex(hex(m)[2:])
print(flag)

'''
68306031653152687384080876677059655513
b'3cC_d1ViSibil!7Y'
'''

Tesvir·

前面一堆花里胡哨的，翻到encrypt其实就是一个背包密码，只不过多了一层encode

首先看encrypt，对于每一个m，就是

$$s \equiv \sum_{i=0}^{p-1} m_i \cdot PK_i \pmod {p^h-1}$$

其中$m_i$就是$m$的第$i$个比特

整理一下就是存在一个$k$使得

$$\sum_{i=0}^{p-1} m_i \cdot PK_i - k \cdot (p^h-1) - s = 0$$

于是可以构造格基

$$B = \begin{bmatrix} 1 & & & & & & PK_0 \\ & 1 & & & & & PK_1 \\ & & 1 & & & & PK_2 \\ & & & \ddots & & & \\ & & & & 1 & & PK_{p-1} \\ & & & & & -1 & s \\ & & & & & & p^h-1 \\ \end{bmatrix}_{(p+2) \times (p+2)}$$

根据关系

$$\begin{aligned} v =& (m_0, \cdots, m_{p-1}, -1, k) \\ w =& (m_0, \cdots, m_{p-1}, 1, 0) \\ v \cdot B =& w \end{aligned}$$

进行LLL，然后恢复$w$

但这样不太稳，因为这个格太大了，规模是$p+2 = 225$，实测也是没弄出来，所以要进行一波降维

先看一下encode是怎么做的，大概意思就是encode后的$m$可以分为三段

$$m = msg_{(h)}\ |\ 0_{(p-2h)} \ |\ pad_{(h)}$$

令$\ell$为$msg$的二进制中$1$的个数，那么$pad$就是低$\ell$位为$1$，其余为$0$，数学上即

$$pad = 2^\ell - 1$$

观察$m$的三个部分，首先$msg$是肯定不能动的，然后$0$的部分可以无视，最后$pad$只有$24$种可能，可以通过枚举去除

于是降维后的表达式就是

$$(s - \sum_{i=p-h}^{p-1} m_i \cdot PK_i) \equiv \sum_{i=0}^{h-1} m_i \cdot PK_i \pmod {p^h-1}$$

展开

$$\sum_{i=0}^{h-1} m_i \cdot PK_i - k \cdot (p^h-1) - (s - \sum_{i=p-h}^{p-1} m_i \cdot PK_i) = 0$$

然后格基就变成

$$B = \begin{bmatrix} 1 & & & & & & PK_0 \\ & 1 & & & & & PK_1 \\ & & 1 & & & & PK_2 \\ & & & \ddots & & & \\ & & & & 1 & & PK_{h-1} \\ & & & & & -1 & s \\ & & & & & & p^h-1 \\ \end{bmatrix}_{(h+2) \times (h+2)}$$

最终枚举$pad$，用这个格基进行LLL即可

参考代码

#!/usr/bin/env sage
with open('./output_updated.txt', 'r') as f:
  exec(f.read())
p, h = 223, 24

print(len(enc))
print(len(pubkey))


ms = []
for c in enc:
  for k in range(1, h):    # assume k 1s
    B = matrix(ZZ, h+2)
    for i in range(h):
      B[i, i] = 1
      B[i, -1] = pubkey[i]
    B[-2, -2] = -1
    B[-2, -1] = (c - sum(pubkey[-k:])) % (p^h-1)
    B[-1, -1] = p^h-1

    L = B.LLL()
    if not (abs(L[0]) < 6 and L[0][-1] == 0):
      continue

    s = sum(L[0][:h])
    m = list(L[0][:h])
    if s < 0:
      m = list((-L[0])[:h])

    if abs(s) != m.count(1):
      continue

    print(m)
    ms += m
    break
      
m = ''.join([str(_) for _ in ms])
m = int(m, 2)
flag = bytes.fromhex(hex(m)[2:])
print(flag)
    
# b'CCTF{9j_h0W_dO_yUo_5oLvE_tH!s_m1X3D_5eMi_H4rD_T4Sk!!!?' 

PS：做的时候我也试过不去除$pad$，然后用$(2h+2)$的格基做，但没搞出来

Tough·

绝赞更新中…