2023强网杯密码部分题解

就摸了4题，勉强算做了一半吧。

题目难度还是挺大的，不过个人感觉难点主要在找论文、处理大量数据和码代码上，好像也并没学到太多东西（

+最近怼论文眼都要瞎了，又调了两天Bug，命都没半条了（x

题目·

SpeedUp·

题目：SpeedUp.zip

直接搜索，找到前人生成的数据，取出第27个然后算一遍sha256即可

import hashlib

# https://oeis.org/A244060
fx = 4495662081
flag = hashlib.sha256(str(fx).encode()).hexdigest()
flag = 'flag{%s}' % flag
print(flag)

# flag{bbdee5c548fddfc76617c562952a3a3b03d423985c095521a8661d248fad3797}

赛后发现其实并不需要什么加速，直接用Sage的factorial计算就行，渣机大概算了20分钟

#!/usr/bin/env sage

#a = gamma(2^27+1)    # 17m47s
a = factorial(2^27)   # 18m1s
d = a.digits()
a = 0
s = sum(d)
d = []
print(s)
# 4495662081

除了用factorial也可以用Gamma函数去算，在Sage中可以直接调gamma。

不过效率其实差不多。

babyrsa·

题目：babyrsa.zip

第一眼是个Wiener，然后p-q的低100位为0，可以缩小未知量，用纯格的方法算了一下刚好界不够，然后用Coppersmit也没出。

然后找到这个论文，用这个也不行，顺着引用文献可以找到这篇

对着论文抄一遍即可

#!/usr/bin/env sage

from Crypto.Util.number import isPrime, inverse, long_to_bytes
from random import getrandbits, randrange
from collections import namedtuple
from gmpy2 import iroot

Complex = namedtuple("Complex", ["re", "im"])

def complex_mult(c1, c2, modulus):
    return Complex(
        (c1.re * c2.re - c1.im * c2.im) % modulus,
        (c1.re * c2.im + c1.im * c2.re) % modulus,
    )

def complex_pow(c, exp, modulus):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = complex_mult(result, c, modulus)
        c = complex_mult(c, c, modulus)
        exp >>= 1
    return result

n = 591143727706634512649148024939759359125332935965941339741301978100443626383764927192405352906265750441870484772597124866948416540051132797882766876525721890148417364187305274504045823909525810653621572555356644898701170387745996604627164605007922178682643820283078770381294378888391241362701866218417
e = 286946467444242125329232917366005482758108555562774407977935741707895065443551620433804352056018479543399936884283530961542517475681912633594516017006078645316684486996756770475826189189863772520489210693019367686071424252294502612171368401536443115059090019686947917579310650427245795515739689571717195342905189116070822202985869406209819001354794867213391783564718632331851210595177019029809911030842175529435093135302899375148321696495849291318040755489943683469106936515633912280068318274552872682582057701665040704440982616977621678524771480018759950866149932684370941131288823828567953532010239
c = Complex(re=466945074314394618048804903430146870407477348092856785114352121347573765297276603523823356061058665588358168906592812014840355312975623615872669350475423336999911145662063168579527228973092663141715593574293676068879530756106740387499946781859474224812941258752096544261250573356872425877525845188509, im=539172679356466036153667427018194773623808764616135073906943348291977037250808294837529529613499717611287613222519742317858999188657402414805409046190891945128148002520616896558562883270550640806765061686359425281201226450591985013283011470643176844774957570392307535783368083398557427779492426758982)

print(n)
print(e)

r = 100
#u0 = Integer(-Zmod(2^r)(n).nth_root(2))
u0s = Zmod(2^r)(n).nth_root(2, all=True)
print(u0s)
for u0 in u0s:
  print(u0)
  u0 = Integer(u0)
  v0 = Integer(( 2 * u0 + (n - u0^2) * u0.inverse_mod(2^(2*r)) ) % 2^(2*r))
  a1 = v0 * (2^(2*r-1)).inverse_mod(e) % e
  a2 = -((n+1)^2 - v0^2) * (2^(4*r)).inverse_mod(e) % e
  a3 = -1 * (2^(4*r)).inverse_mod(e) % e
  X = Integer(2 * n^0.7)
  Y = Integer(3 * n^0.3)

  load('./copper.sage')
  PR.<x, y> = PolynomialRing(ZZ)
  f = x * y^2 + a1 * x * y + a2 * x + a3
  res = lattice_attack(PR, f, e, 4, 3, X, Y)
  if res:
    print(res)
    break

k, v = res[0]

r = 100
ppq = 2^(2*r) * v + v0
pmq = ppq^2 - 4 * n
pmq = iroot(pmq, 2)
assert pmq[1]
pmq = Integer(pmq[0])
p = (ppq + pmq) // 2
q = n // p
assert p * q == n

phi = (p^2-1) * (q^2-1)
d = e.inverse_mod(phi)

m = complex_pow(c, d, n)
print(m)
flag = b''.join([long_to_bytes(mi) for mi in list(m)])
print(flag)


'''
[(149639950165401370800040220223187826523021045890365249443622785517178686078823694521646436258083914747634419055968718717943496892995631611456804659803012934359813236394143368904438436233733641937238021358755752, 957733246901790769061173211294976823448907733389188013192768616756978467669504039559041133)]
Complex(re=2284117282070459085219909197928661795481074017, im=1164185736764860305066816661603110168167004285)
b'flag{081613a301e49a442dfed994daba0c98}'
'''

调的Coppersmith里面的多项式要按照论文的构造

copper.sage我直接改的之前2022 TQLCTF里清华✌的代码，注意把最后的i和j两个循环改小可以减少运行时间，由于LLL规约后只有前几行才是短向量，所以没必要用太大的i和j

参数设置m=4和t=3也可以出得快一点，没必要用论文例子的t=4

# copper.sage

def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            if BB[ii, jj] == 0:
                a += ' '
            else:
                a += 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

def lattice_attack(PR, pol, e, mm, tt, X, Y):
    x, y = PR.gens()
    polys = []
    dd = pol.degree()

    for s in range(mm + 1):
      for i in range(s, mm+1):
        for j in range(2*s, 2*s+1+1):
            poly = x^(i-s) * y^(j-2*s) * pol^s * e^(mm-s)
            polys.append(poly)

    for s in range(mm + 1):
        i = s
        for j in range(2*s+2, 2*s+tt+1):
            poly = x^(i-s) * y^(j-2*s) * pol^s * e^(mm-s)
            polys.append(poly)

    polys = sorted(polys)
    monomials = []
    for poly in polys:
        monomials += poly.monomials()
    monomials = sorted(set(monomials))
    dims1 = len(polys)
    dims2 = len(monomials)
    M = matrix(QQ, dims1, dims2)

    for ii in range(dims1):
        M[ii, 0] = polys[ii](0, 0)
        for jj in range(dims2):
            if monomials[jj] in polys[ii].monomials():
                M[ii, jj] = polys[ii](x * X, y * Y).monomial_coefficient(monomials[jj])
    
    matrix_overview(M)
    print('=' * 128)
    print(len(M.rows()), len(M.columns()))
    #M = M.hermite_form()
    B = M.LLL()
    print('LLL done')

    det = B.det()
    print(det == 0)
    print(f"monomials: {monomials}")
    nn = len(monomials)
    matrix_overview(B)
    H = [(i, 0) for i in range(dims1)]
    H = dict(H)
    for j in range(dims2):
        for i in range(dims1):
            H[i] += (monomials[j] * B[i, j]) / monomials[j](X, Y)
    
    PQ.<q> = PolynomialRing(ZZ)
    H = list(H.values())
    solutions = []
    print(len(H))
    #for i in range(len(H)//2):
    for i in range(5):
        #for j in range(i + 1, len(H)//2):
        for j in range(i + 1, 5):
            pol1 = PR(H[i])
            pol2 = PR(H[j])
            rr = pol1.resultant(pol2, y)
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            sols = rr(q, q).roots()
            for sol in sols:
                solx = sol[0]
                if solx == -1:
                    continue
                try:
                    soly = pol1(solx, q).roots()[0][0]
                    solutions.append((solx, soly))
                    print('=' * 128)
                except:
                    pass
                if len(solutions) > 0:
                    break
            if len(solutions) > 0:
                break
        if len(solutions) > 0:
            break
    return solutions

not only rsa·

题目：not_only_rsa_task1.zip

题目把n写死就可以直接怀疑n有问题，分解一下发现是某个素数p的5次方，分解之

分解后发现$e$和$\varphi$不互素，AMM解之，这里我直接调我之前写的模板

#!/usr/bin/env
n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943
p = 91027438112295439314606669837102361953591324472804851543344131406676387779969
assert n == p^5

phi = p^4 * (p-1)
print(gcd(e, phi))
print(gcd(e, phi//e))

import libnum
# https://tover.xyz/p/n-root-in-F/
load('./nth.sage')
res = nthRSA_p(c, e, p, 5)
for r in res:
  flag = libnum.n2s(int(r))
  if b'flag' in flag:
    print(r)
    print(flag)

# flag{c19c3ec0-d489-4bbb-83fc-bc0419a6822a}

赛后讨论了一下，直接用nth_root设all=True也可以出，就不用这么麻烦

discrete_log·

题目：discrete_log_task1.zip

素数是强素数没啥漏洞，题目给了个flag，直接交不对，然后发现这个flag其实是个脑洞，意思是提示flag里面是一串长度不长的十六进制字符串。。。

直接枚举不出来，怼了个Meet in Middle

首先可以把flag分拆成前中后3段

mh: flag{
mm: unknown
ml: } + padding

然后只有mm是需要爆破的未知数，假设未知的mm有$i$个字符，代进原来的DLP问题就可以得到

$$\begin{aligned} c &\equiv g^m \\ &\equiv g^{ 2^{8 \cdot 128- 8 \cdot 5} \cdot m_h + 2^{8 \cdot 128- 8 \cdot 5 - 8 \cdot i} \cdot m_m + m_l} \\ &\equiv g^{2^{8 \cdot 128- 8 \cdot 5} \cdot m_h + m_l} \cdot g^{2^{8 \cdot 128- 8 \cdot 5 - 8 \cdot i} \cdot m_m} \pmod p \end{aligned}$$

这样看有点复杂，不妨令

$$\begin{aligned} A &= g^{2^{8 \cdot 128- 8 \cdot 5} \cdot m_h + m_l} \\ \beta &= 2^{8 \cdot 128- 8 \cdot 5 - 8 \cdot i} \end{aligned}$$

就可以简化为

$$c \equiv A \cdot g^{\beta \cdot m_m} \pmod p$$

然后这里继续把$m_m$切割成高位半的$m_m^h$（低位补上0）和低位一半的$m_m^l$，就得到

$$\begin{aligned} m_m &= m_m^h + m_m^l \\ c &\equiv A \cdot g^{\beta \cdot (m_m^h + m_m^l)} \pmod p \\ c \cdot A^{-1} &\equiv g^{\beta \cdot (m_m^h + m_m^l)} \pmod p \\ (c \cdot A^{-1})^{\beta^{-1} \pmod {\frac{p-1}{2}}} &\equiv g^{m_m^h + m_m^l} \pmod p \\ \end{aligned}$$

注意这里因为$\text{gcd}(\beta, p-1) = 2$，所以不能直接取$\beta$模$\varphi(p)=p-1$的逆元，由于这里$c \cdot A^{-1}$的阶大概率不是$2$，所以可以大胆地直接用$\frac{p-1}{2}$为阶取逆元

然后令

$$A' \equiv (c \cdot A^{-1})^{\beta^{-1}} \pmod p$$

就是

$$\begin{aligned} A' &\equiv g^{m_m^h + m_m^l} \pmod p \\ A' \cdot g^{-m_m^h} &\equiv g^{m_m^l} \pmod p \end{aligned}$$

到这里就可以用$m_m^h$和$g^{m_m^l}$做Meet in Middle爆破

最后爆出来的长度为i=12，并不是题目给的flag中的14，如果是14的话估计要爆半天。。。

#!/usr/bin/env sage
p = 173383907346370188246634353442514171630882212643019826706575120637048836061602034776136960080336351252616860522273644431927909101923807914940397420063587913080793842100264484222211278105783220210128152062330954876427406484701993115395306434064667136148361558851998019806319799444970703714594938822660931343299
q = 86691953673185094123317176721257085815441106321509913353287560318524418030801017388068480040168175626308430261136822215963954550961903957470198710031793956540396921050132242111105639052891610105064076031165477438213703242350996557697653217032333568074180779425999009903159899722485351857297469411330465671649
assert p == 2 * q + 1

g = 5
c = 105956730578629949992232286714779776923846577007389446302378719229216496867835280661431342821159505656015790792811649783966417989318584221840008436316642333656736724414761508478750342102083967959048112859470526771487533503436337125728018422740023680376681927932966058904269005466550073181194896860353202252854

print(p.nbits())

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from tqdm import tqdm
import itertools
import string


#for i in range(128-6):
i = 14
i = 12
#i = 10
#i = 8
#i = 4
print(i)

fake = 'flag{%s}' % ('a' * i)
print(fake)
ml = Integer(bytes_to_long(pad(fake.encode(), 128)[5+i:]))
mh = Integer(bytes_to_long(b'flag{'))

'''
c = pow(g, bytes_to_long(pad(fake.encode(), 128)), p)
j = Integer(bytes_to_long(b'aa'))
k = Integer(bytes_to_long(b'aa\x00\x00'))
B = 2^(1024-40-8*i) % (p-1)
A = pow(g, mh * 2^(1024-40) + ml, p)
A = Integer(A).inverse_mod(p) * c % p
A = pow(A, B.inverse_mod(q), p)
ginv = g.inverse_mod(p)
print(pow(g, j, p) % p)
print(pow(ginv, k, p) * A % p)
print(j, k)
'''

n = 16^(i//2)
List = set()
Lj = {}
B = 2^(1024-40-8*i) % (p-1)
A = pow(g, mh * 2^(1024-40) + ml, p)
A = Integer(A).inverse_mod(p) * c % p
A = pow(A, (B).inverse_mod(q), p)
for j in tqdm(itertools.product(string.hexdigits[:16], repeat=i//2), total=int(16^(i//2))):
  j = bytes_to_long(''.join(j).encode())
  lj = pow(g, j, p)
  List.add(lj)
  Lj[lj] = j

ginv = g.inverse_mod(p)
for k in tqdm(itertools.product(string.hexdigits[:16], repeat=i//2), total=int(16^(i//2))):
  k = bytes_to_long((''.join(k)+'\x00'*(i//2)).encode())
  lk = pow(ginv, k, p) * A % p
  if lk in List:
    print(k, lk)
    break

j = Lj[lk] 
flag = long_to_bytes(k + j)
flag = 'flag{%s}' % flag.decode()
print(flag)

  
'''
1024
12
flag{aaaaaaaaaaaa}
100%|████████████████| 16777216/16777216 [15:03<00:00, 18563.12it/s]
 38%|██████▌          | 6416198/16777216 [10:32<16:46, 10298.31it/s]16771905891018463815302905856 135529567858850443107510144315754681449995927325397869726845551407254736955982955315931298476445549398904618225678737565918473822963060588935860022359594391409973542725505768767829857404385071260684422207579208358076457034566480966492187698885320727337820205594291169458111117508529532766504392148482781992555
 38%|██████▌          | 6416384/16777216 [10:32<17:00, 10150.39it/s]
flag{61e8007dd65f}
'''

PS：这里其实还能继续做优化，因为这里的pow幂运算里面会有重复的乘法运算，而普通的Meet in Middle会把这种幂运算优化掉，最后只剩下乘法运算，但这里爆破的是字符，在数字上不连续，所以不太好这样操作，留个坑

1515·

题目：1515.zip

首先需要远程拿参数，矩阵的维度m和n直接数即可

q的话，在远程的代码中x * A1515是在Zq上的运算，而A1515可以通过拿到的A0构造，所以可以本地构造一个ZZ上的A1515，然后用ZZ上的x * A1515和Zq上的x * A1515相减，得到的向量中的每个元素就都是q的倍数，gcd一下即可恢复q

v的话，只要构造一个满足x * A1515 == u的x，即可泄露v，这里不妨把x分成$x_0$和$x_1$两半，即得

$$\begin{bmatrix} x_0 & x_1 \end{bmatrix} \begin{bmatrix} I \\ A_0 \end{bmatrix} \equiv x_0 + x_1 A_0 \pmod q$$

所以只要设$x_0 = u$和$x_1 = 0$，即得

$$x_0 + x_1 A_0 \equiv u + 0 \equiv u \pmod q$$

参考代码：

#!/usr/bin/env sage
import re
import hashlib
from pwn import *

def pow(r1, HASH):
  for r0 in range(1, 2**20):
    if hashlib.sha256(str(r0*r1).encode()).hexdigest() == HASH:
      return r0 

#r = remote('47.104.147.171', 1515)
r = remote('120.27.12.173', 1515)
r1, HASH = r.recvline()[:-1].decode().split(' ')
print(r1, HASH)
r1 = int(r1)
r0 = pow(r1, HASH)
print(r0)

r.recvuntil(b'exit(0)')
r.recvuntil(b'Give me r0: ')
r.sendline(str(r0).encode())

m = 0
A0 = []
while True:
  A0i = r.recvline()[:-1].decode()
  if not '[' in A0i:
    break
  A0i = re.findall(r'\d+', A0i)
  A0i = [Integer(ai) for ai in A0i]
  A0 += [A0i]
  assert len(A0i) == 512

u = re.findall(r'\d+', A0i)
u = [Integer(ui) for ui in u]
print(len(A0), len(u))
n = 512
m = 1024

A0z = matrix(ZZ, A0)
A1515z = matrix.block(ZZ, [[identity_matrix(ZZ, n)], [A0]])

'''
x = [1] * m
r.recvuntil(b'Give me a list of numbers: ')
r.sendline(str(x).encode())

xz = vector(ZZ, x)
xA0q = r.recvline()[:-1].decode()
xA0q = re.findall(r'\d+', xA0q)
xA0q = [Integer(xA0qi) for xA0qi in xA0q]
uz = xz * A1515z

print(xA0q)
print(gcd(uz[0] - xA0q[0], uz[1] - xA0q[1]))
print(gcd(uz[1] - xA0q[1], uz[2] - xA0q[2]))
print(gcd(uz[2] - xA0q[2], uz[3] - xA0q[3]))
'''
q = 277
Zq = IntegerModRing(q)

'''
A0q = matrix(Zq, A0)
uq = vector(Zq, u)
x0 = vector(Zq, [0] * n)
x1 = uq * A0q^(-1)
x = list(x0) + list(x1)

r.recvuntil(b'Give me a list of numbers: ')
r.sendline(str(x).encode())
'''
v = 1510

r.interactive()
r.close()

最后泄露出

m = 1024
n = 512
q = 277
v = 1510

接下来就是要找一个短的x，涉及短向量的话可以直接想到格，于是可以构造

$$x_0 + x_1 A_0 \equiv u \pmod q \\ x_0 + x_1 A_0 - k \cdot qI = u \\ k \cdot qI - x_1 A_0 + u = x_0$$

然后就可以构造格基

$$B = \begin{bmatrix} qI & & \\ -A_0 & I & \\ u & 0 & C \end{bmatrix}$$

使得

$$(k, x_1, 1) \cdot B = (x_0, x_1, C)$$

理论上LLL后得到的$(x_0, x_1)$就是我想要的短向量，但是这个格基的维度是$1025$，不大可能用LLL解出

后来发现题目名字的1515其实是ISIS，寻找相关攻击找到这篇文章，情况和题目的完全一样，还给出了攻击代码，其中好像用了一种很先进（？）的降维方法（留坑），要用到G6K，可以参考我的上一篇文章安装

最后改了攻击代码的参数，并把beta_BKZ和beta_sieve调大后，本地出了，但是把x发过去后给我EOF了，就很迷（

PS：上次刚说完G6K不会用这次就来了格G6K的代码了，有空研究研究（逃

guess_game·

题目：guess_game.zip

当时没时间看，后来听说可以非预期嗯猜，0.7和0.5的概率好像也不是相差很多。。。

留坑

recovery·

题目：recovery.zip

还没看，留坑

总结·

菜