24Nov2

huangx607087 11月的切题2

0.Introduction

自博客创立以来，ExpLog并不多：分别是21Jan1,21Jan2,21Jan3,21Jan4,21Feb1,21Feb2,21May1和24Nov1。（好家伙，这跨度）。21年那个时候自己确实切了很多题，也是当时进步最快的时候，不过后期因为保研要卷G.所以CTF就没怎么打了。（当然如果本科保研和CTF二选一让我再选一次的话，当然还是得选保研），因为这样才能在研一导师放养的时候，继续搞技术。

怎么除了第一题全是鹏城杯？算了，混个第一题进去，名字不变了吧，还叫24Nov2，不改成鹏城杯wp了

1.[2024强网拟态]CFBChall

首先来先看一下题目代码（本地复现时，对题目代码有所修改）

from Crypto.Cipher import AES
import os
from string import printable
key = os.urandom(16)
iv  = os.urandom(16)
register_open = True
login_attempts = 500
def encrypt(data, key):
    cipher = AES.new(key, AES.MODE_CFB, iv=iv)
    ct_bytes = cipher.encrypt(data.encode('utf-8'))
    return ct_bytes.hex()

def decrypt(ct, key):
    ct_bytes = bytes.fromhex(ct)
    cipher = AES.new(key, AES.MODE_CFB, iv=iv)
    data = cipher.decrypt(ct_bytes[:])
    return data
print('debug:(key,iv)=',key.hex(),iv.hex()) #这个是我本地复现加的，真实情况没有这个。
def InitialGlobals():
    global key,iv,register_open,login_attempts
    key = os.urandom(16)
    iv  = os.urandom(16)
    register_open = True
    login_attempts = 500
def Register(username,password):
    global key,iv,register_open,login_attempts
    if not register_open:
        return None
    else:
        if len(password)<8:
            return None
        elif not set(password+username)<=set(printable):
            return None
        elif 'admin' in username:
            return None
        else:
            token = encrypt(f"{username}\x00{password}\x01\x02\x03", key)
            register_open = False
            return token
def Login(username,password,token): #函数和原题有所差别。
    global key,iv,register_open,login_attempts
    if login_attempts <= 0:
        return None
    else:
        try:
            decrypted = decrypt(token, key)
            token_username, *_, token_password = decrypted.split(b'\x00')
            assert(token_password[-3:]==b"\x01\x02\x03")
            token_password=token_password[:-3]
            if username == token_username and password == token_password:
                if username == b'admin':
                    if password == b'123456':
                        return ('flag{This is a flag}')
                    else:
                        return 'failed'
                else:
                    return 'failed'
            else:
                return 'failed'
        except:
            return 'failed'
        finally:
            login_attempts -= 1

在原始题目中，你有一次注册的机会，输入用户名和密码，然后他会给你一个加密的token，token的格式是username||\x00||password||\x01\x02\x03，用AES-CFB加密。登陆时需要以admin 的身份和 123456 的密码登录就可以获得flag。题目中没有限制交互次数，但登陆尝试最多为 500 次，整个过程也可以重置参数进行重试。

在BlockCipher3中，我们回顾了CFB的模式，CFB模式将分组密码当流密码使用。在Crypto.Util.Cipher中的实现为逐字节加密：投入初始向量 $(u_0,u_1,…,u_{15})$ ，对初始向量用密钥加密后，将一个字节（目前尚不清楚是首个还是最后一个）和 一字节明文异或得到密文 $u_{16}$，也就是消息首个字节 $m_0$ 的密文为 $u_{16}$。然后下一轮，对 $(u_1,u_2,…,u_{16})$ 用相同的密钥加密， 然后将明文第二字节$m_1$和得出的加密结果的一字节异或得到 $u_{17}$，以此类推。

如果使用密钥和IV相同，那么对于两个消息 $M_1=A||B,M_2=A||C$，那么这两个消息加密后，其前缀 $A$ 会被加密成相同内容

因为AES的分组长度为 16 字节，因此当出现1字节错误时，后面 16 字节会出现错误，16字节之后会恢复正常。之所以CFB、OFB、CTR模式可以在分组密码中使用，是因为分组密码良好的扩散性和混淆性，两个相似的明文，经过加密后，会得到样貌相差很大的密文。

了解了CFB的工作原理，下面我们就需要考虑构建payload了：

由于其AES良好的扩散性和混淆性，因此，对于两个明文：00 00 00 00 和 00 00 01 00，假设前者经过加密变成了 f0 e0 d0 c0，那么后者经过相同加密，前三字节一定是 f0 e0 d1，但第四字节就无法预知了。因此，为了能够构造admin开头的内容，我们可以根据这个特性，用户名输入admio （o 和n 的异或值为1）。密码的话，由于要求强制八位以上，加上前面一位o 会影响后续 16 位，因此放16个填充字符，然后加上123456，这样最后刚好可以在最后以 \x01\x02\x03 的padding结尾。

然后就是拼运气了，因为第6位字符开始受到影响，因此第六位对应的密文，我们可以进行爆破，然后赌这中间存在 \x00 进行隔断。

T=0
found=0
while not found:
    InitialGlobals()
    mytoken=Register('admio','A'*16+'123456')
    mytoken=mytoken[:8]+'{:02x}'.format(int(mytoken[8:10],16)^1)+'XX'+mytoken[12:]
    for i in range(256):
        ftoken=mytoken.replace('XX','{:02x}'.format(i))
        chk=Login(b'admin',b'123456',ftoken)
        T+=1
        if(chk[:4]=='flag'):
            print(f'success with {T} queries')
            found=1
            break
print(decrypt(ftoken,key))
print('debug:(key,iv)=',key.hex(),iv.hex()) #本地复现，可以输出调试用。

一个可能的输出结果，30000多次可以拿到flag，不过本地测试时交互时间不定，运气好2000多次出结果，运气差要10万次。

success with 35192 queries
b'admin\x00\x0e-\xb0[.\xd3\xd4\xb9\xd5\x1f`\xd2\xe9)\x9e\x00123456\x01\x02\x03'
debug:(key,iv)= fe419d0b1dcd16b75247181d1e7fa0f5 8b49ad0c5018eb41d083058881323f84

2.[2024鹏城杯] babyenc

题目一共分两问，分别来看

2o01 Part1

第一问的加密代码：

def enc1(m, e, shift):
    n = next_prime(m << shift) #shift=310
    tmp = getPrime(256)
    cc = []
    for i in range(len(e)):
        cc.append(int(pow(tmp, e[i], n)))
    return cc
"""
output:e = [43, 37, 53, 61, 59]
c1 = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]

"""

在这一问中，给出了五组 $t^{e} \bmod n$ 的值，其中 $n$ 是 $2^{310}m$ 的下一个素数，而 $e$ 的值很小。但这边 $n,t$ 都不知道。

设 $A,B,C,D,E$ 分别为 $5$ 个 $c$ 值，那么有 $(t^{43},t^{37},t^{53},t^{61},t^{59})\equiv (A,B,C,D,E) \pmod n$。

因此，可以得到等式：
$$
\frac{A}{B}\equiv\frac{E}{C}\equiv\frac{D^3}{E^3}\equiv t^{6} \pmod n
$$
也就是
$$
AC-BE \equiv AE^3-BD^3\equiv E^4-CD^3\equiv 0\pmod n
$$
随便取两组数据，比如计算 $|AC-BE|$ 和 $|AE^3-BD^3|$（不取模），然后求最大公约数就可以得到 $n$ 了。当然也可以选第三组数据 $|E^4-CD^3|$。

$n$ 得到后直接右移 $310$ 位，得到flag前半部分。

from Crypto.Util.number import *
e = [43, 37, 53, 61, 59]
c1 = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]

aa,bb,cc,dd=c1[1],c1[0],c1[2],c1[4]
#Ax^6=B (mod u)
#Cx^6=D (mod u)
#B/A=D/C
#BC=AD (mod u)
F=bb*cc-aa*dd
aaa,bbb,ccc,ddd=c1[1],c1[0],c1[4],c1[3]
#Ax^6=B
#Cx^2=D
#C^3x^6=D^3
#B/A=D/C
G=abs(bbb*(ccc**3)-aaa*(ddd**3))

u=gcd(F,G)
print(u,isPrime(int(u)))
u3=u>>310
long_to_bytes(u3)
# print(u,isPrime(int(u))) 输出结果
#312246073793634738336797238973383686069608357320504281244915809376146746877615304143136570336999218383069369602336776078145547720220248077500917 True
#Out[29]:
#b'flag{3e99c26b-efdd-4c'

2o02 Part 2

然后是第二问：第二问给了 $g=m^p \pmod n,h=m^q\pmod n$。这一问由于 $n=pq$，因此如果把 $g,h$写成中国剩余定理的形式，就是：

根据费马小定理 $m^p\equiv m\pmod p$，可以有

此，去掉同余，我们可以写成： $g=up+m,h=vq+m$。

也就是 $(g-m)(h-m)\equiv gh-m(g+h)+m^2\equiv (up)(vq) \equiv uvpq\equiv 0\pmod n$

注意到 $m$ 是 $21\times8=168$ 位，而 $n$是2048位，m相对于n特别小。

上面式子去同余，有 $(g-m)(h-m)=gh-m(g+h)+m^2-wn=0$。

因此可以构造矩阵，LLL格基归约搞出$m$（这个$K=2^{1600}$是为了扩大最短向量的长度，否则最短向量就是矩阵第三行的$(0,0,0,1,-1)$）

事后补充： 这边因为 $m$ 只有 $168$ 位，所以随便乱搞就出来了，但其实从闵可夫斯基定理来看，你右边整体乘一行， $\det M$ 只增加了 $K$ 倍。正确做法还要考虑三个 $1$ 过小带来的影响。因为 $m$ 是 $168$ 位，那么 $m^2$ 就是 $376$ 位。因此构造的矩阵前 $3$ 列最好乘一个 $(2^{376},2^{168},1)$ 的系数，来保证两边平衡。最终结果为 $(2^{376},2^{168}m,m^2)$。

最后就可以得到 $m$了，可以看到结果与预期相符，差个符号取正就行了。

# In [1]:
n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c2 = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364, 13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]
g,h=c2
K=2**1600
M=Matrix(ZZ,[[1,0,0,g*h*K],[0,1,0,-(g+h)*K],[0,0,1,1*K],[0,0,0,K*n]])
print(M.LLL()[0])

# Out [1]:
#(-1, -146436625375651639081292195233290471195543268962429, -21443685251408941546679213362069702254265669437874360093122983595763055555796655464630848682213580041, 0)
#对应(1,m,m^2,w,0)，差个了符号，无所谓

# In [2]:
from Crypto.Util.number import *
long_to_bytes(146436625375651639081292195233290471195543268962429)#直接复制上面第二个分量即可。
# Out [2]:
#b'd2-bbe5-1420eaaa3b30}'
#最终flag:flag{3e99c26b-efdd-4cd2-bbe5-1420eaaa3b30}

3.[2024鹏城杯] tarscr

这个题目 $d_q$ 很小，$p$ 和 $q$ 的大小也不平衡。也就是 $p<n^{\beta},d_q<n^{\delta}$。这里 $\beta=0.3,\delta=0.1$。

一开始根据 这篇文献中的方法做的，因为 $\beta<0.382$，但这篇文献还有一个要求就是 $3\beta-\beta^2+2\delta<1$，因此不满足条件。

因此根据 这篇文献的方法去做，参考了lazzaro的博客，改一下里面的参数即可。

貌似是2022NCTF的原题？那个时候我CTF已经退役了（不过话说回来，再给我一次选择，CTF和保研之间我当然还是选择保研啦，保研深造3年，去认识认识更多的大佬，对我而言还是比直接工作好。当然，以前CTF队友本科毕业直接工作，还去了很不错的单位，毕竟他们不需要读研就可以找到一个非常好的工作，也是挺令人羡慕的）。

#reference: https://lazzzaro.github.io/2020/05/06/crypto-RSA/index.html
from copy import deepcopy
# https://www.iacr.org/archive/pkc2006/39580001/39580001.pdf
# Author: ZM__________J, To1in
N = 61857467041120006957454494977971762866359211220721592255304580940306873708357617802596067329984189345493420858543581027612648626678588277060222860337783377316655375278359169520243355170247177279595812282793212550819124960549824278287538977769728573023023364686725321548391592858202718446127851076431000427033
e = 22696852369762746127523066296087974245933137295782964284054040654103039210164173227291367914580709029582944005335464668969366909190396194570924426653294883884186299265660358589254391341147028477295482787041170991166896788171334992065199814524969470117229229967188623636764051681654720429531708441920158042161
alpha = log(e, N)
beta = 0.3
delta = 0.1
P.<x,y,z>=PolynomialRing(ZZ)
 
X = ceil(2 * N^(alpha + beta + delta - 1))
Y = ceil(2 * N^beta)
Z = ceil(2 * N^(1 - beta))
 
def f(x,y):
    return x*(N-y)+N
def trans(f):
    my_tuples = f.exponents(as_ETuples=False)
    g = 0
    for my_tuple in my_tuples:
        exponent = list(my_tuple)
        mon = x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
        tmp = f.monomial_coefficient(mon)
        
        my_minus = min(exponent[1], exponent[2])
        exponent[1] -= my_minus
        exponent[2] -= my_minus
        tmp *= N^my_minus
        tmp *= x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
        
        g += tmp
    return g
  
m = 5 # need to be adjusted according to different situations
tau = ((1 - beta)^2 - delta) / (2 * beta * (1 - beta))
sigma = (1 - beta - delta) / (2 * (1 - beta))
 
print(sigma * m)
print(tau * m)
 
s = ceil(sigma * m)
t = ceil(tau * m)
my_polynomials = []
for i in range(m+1):
    for j in range(m-i+1):
        g_ij = trans(e^(m-i) * x^j * z^s * f(x, y)^i)
        my_polynomials.append(g_ij)
 
for i in range(m+1):
    for j in range(1, t+1):
        h_ij = trans(e^(m-i) * y^j * z^s * f(x, y)^i)
        my_polynomials.append(h_ij)
        
known_set = set()
new_polynomials = []
my_monomials = []
 
# construct partial order
while len(my_polynomials) > 0:
    for i in range(len(my_polynomials)):
        f = my_polynomials[i]
        current_monomial_set = set(x^tx * y^ty * z^tz for tx, ty, tz in f.exponents(as_ETuples=False))
        delta_set = current_monomial_set - known_set
        if len(delta_set) == 1:
            new_monomial = list(delta_set)[0]
            my_monomials.append(new_monomial)
            known_set |= current_monomial_set
            new_polynomials.append(f)            
            my_polynomials.pop(i)
            break
    else:
        raise Exception('GG')
        
my_polynomials = deepcopy(new_polynomials)
 
nrows = len(my_polynomials)
ncols = len(my_monomials)
L = [[0 for j in range(ncols)] for i in range(nrows)]
 
for i in range(nrows):
    g_scale = my_polynomials[i](X * x, Y * y, Z * z)
    for j in range(ncols):
        L[i][j] = g_scale.monomial_coefficient(my_monomials[j])
        
# remove N^j
for i in range(nrows):
    Lii = L[i][i]
    N_Power = 1
    while (Lii % N == 0):
        N_Power *= N
        Lii //= N
    L[i][i] = Lii
    for j in range(ncols):
        if (j != i):
            L[i][j] = (L[i][j] * inverse_mod(N_Power, e^m))

L = Matrix(ZZ, L)
nrows = L.nrows()
 
L = L.LLL()
# Recover poly
reduced_polynomials = []
for i in range(nrows):
    g_l = 0
    for j in range(ncols):
        g_l += L[i][j] // my_monomials[j](X, Y, Z) * my_monomials[j]
    reduced_polynomials.append(g_l)
 
my_ideal_list= [y * z - N] + reduced_polynomials
 
# Variety
my_ideal_list = [Hi.change_ring(QQ) for Hi in my_ideal_list]
for i in range(len(my_ideal_list),3,-1):
    print(i)
    V = Ideal(my_ideal_list[:i]).variety(ring=ZZ)
    print(V)
"""
OUTPUT:
2.14285714285714
4.64285714285714
52
[]
51
[]
50
[]
49
[]
48
[]
47
[]
46
[]
45
[]
44
[]
43
[]
42
[]
41
[{z: 426614979768518060635433317149972303610396098751783498586225631589479798053751568080185868568717967344782297587209012869059719479952019313461850777653567018452929932659204669967695196434044149034271037885062392902287, y: 144996003362760405215910388196517232449311004246441924325936847006315296003811348342536838359, x: 66838488369949543369599279980954380920457752396291961341704448955532596917094831390389571041281062121515985150418852560085}]
40
[{z: 426614979768518060635433317149972303610396098751783498586225631589479798053751568080185868568717967344782297587209012869059719479952019313461850777653567018452929932659204669967695196434044149034271037885062392902287, y: 144996003362760405215910388196517232449311004246441924325936847006315296003811348342536838359, x: 66838488369949543369599279980954380920457752396291961341704448955532596917094831390389571041281062121515985150418852560085}]
"""

上面式子中, $y$ 和 $z$ 分别对应 $p$ 和 $q$，$x$ 对应 $d_q$，复制到下一个框内直接解即可。

N=61857467041120006957454494977971762866359211220721592255304580940306873708357617802596067329984189345493420858543581027612648626678588277060222860337783377316655375278359169520243355170247177279595812282793212550819124960549824278287538977769728573023023364686725321548391592858202718446127851076431000427033
p=426614979768518060635433317149972303610396098751783498586225631589479798053751568080185868568717967344782297587209012869059719479952019313461850777653567018452929932659204669967695196434044149034271037885062392902287
q=144996003362760405215910388196517232449311004246441924325936847006315296003811348342536838359
e=22696852369762746127523066296087974245933137295782964284054040654103039210164173227291367914580709029582944005335464668969366909190396194570924426653294883884186299265660358589254391341147028477295482787041170991166896788171334992065199814524969470117229229967188623636764051681654720429531708441920158042161
from Crypto.Util.number import *
c = 41862679760722981662840433621129671566139143933210627878095169470855743742734397276638345217059912784871301273620533442249011607182329472311453700434692358352210197988000738272869600692181834281813995048665466937302183039555350612260646428575598237960405962714063137455677605629008760761743568236135324015278
d=inverse(e,(p-1)*(q-1))
long_to_bytes(int(pow(c,d,N)))
#output:b'flag{tlp17_1s_4w3s0m3}'

4.[2024鹏城杯] PolyPrime

4o01 Problem

先看看题目：

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from secret import flag
import random


k = getPrime(333 * 5)
e = 65537
m = bytes_to_long(flag)

def temp_calc(x): 
    return (x * random.randint(2, 5)) ^ random.randint(100, 500)

def some_calc(size, depth):
    def sums_calc(base, degree): 
        result = 0
        for i in range(degree): 
            temp = temp_calc(base ** i)
            result += base ** i + temp // temp_calc(base**(i + 1))
        return result

    while True:
        prime_number = getPrime(size)

        temp_number = temp_calc(prime_number)
        poly_primes = sums_calc(prime_number, depth)  
        if temp_number % 3 == 0: 
            temp_number = temp_calc(poly_primes)
            continue
        
        if isPrime(poly_primes):
            return prime_number, poly_primes


p, q = some_calc(333, 5)

n = p * q * k
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

OUTPUT：

n = 659401821142664131364043958430747314465977448744532421905138184036743766362324320051729418680079590835903781525157600055608268591994754328563246418114269690475272262915661210669701969695314157602927462228079044905276064391615467601628466982949165371933147600418057089432876120807721483665788557812323607370950442342057254926375842684430119320789097029996211564275310819486004520088130146630452262340185192110066151930586956190499953220051855668474863659201165952231016814569364299000130323859609047687714260776467149437031397019411599103716200258382231589757031469168245396061619327867355414287059363691024984066070128364157490336808211223714816668548049472199794493895870662970541167490686648385211854469386812214775829776376273299648505880034651930322294605482489225723014758138525637864689594748771025870209444029669477294995691067669374491852721622469656239730320092112222948718027850386898461208936333788173263904607181823233002355650353116486156927403178510412091666951574340730799316032588099237
c = 455042981325030540026829365098432813829591020497037525707600104817313008442900331256387443469027825344761381076471749826547710666806180999603254398722965179851898391700090501419875562919365894255855734276825027850795202733875071307773598881254863911398285400038957998385685292965812925607278232164067624548120378758414574370042945538632864154772437639053907149514588502689277630450575630168099810584842881257614115970132960679023265157277718654731105815060916800751033956715430930381384344469220951638102432198422350425390757155267143393385221465041749156153517556389417033187856017198907366720281408810250981776112815100319814215140919133440637395953567624057248002125277569474190364142291136361144552953540727462623677375371327473687508344483184466522697912317252462246054471196345909304668083637177166153036111122244170846815657389873986264187766636830907458940128844256504176917204131708083105093700023335939233711693409336968008112511482237441198116493965744903995545941700742865846469036763734618
e = 0x10001

题目给出了 $n=pqk$，其中 $k$ 是 $333\times5$ 的素数， $p,q$ 生成方式很奇怪。

审计一下 temp_calc 函数，给人一种RLWE的感觉。但在 some_calc 中的 sums_calc 中，考虑到 size 是 $333$，那么关注这一部分：

for i in range(degree): 
	temp = temp_calc(base ** i)
	result += base ** i + temp // temp_calc(base**(i + 1))

temp的数量级是 $333\times i$，而 temp_calc(base**(i+1)) 的数量级是 $333\times(i+1)$，是temp的 $2^{333}$ 倍。而temp_calc 返回 $[2x-512,5x+512]$ 的值，对于 $2^{233}$ 完全可以忽略，因此这一部分的值计算结果总为 $0$ 。本地测试了一下也确实如此。

那么，可以得到：$q=p^4+p^3+p^2+p+1$，那么 $n=kp(p^4+p^3+p^2+p+1)$。

对于$$q=p+p^2+p^3$$的情形在[ImaginaryCTF 2023](https://github.com/maple3142/My-CTF-Challenges/tree/master/ImaginaryCTF 2023)中有过类似的题目，因此可以直接参考那个题目的WP link，简单修改参数即可。

from Crypto.Util.number import *
n = 
c = 
e = 
k = 5

R = Zmod(n)["x"]
while True:
    Q = R.quo(R.random_element(k))
    pp = gcd(ZZ(list(Q.random_element() ^ n)[1]), n)
    if pp != 1:
        qq = sum([pp**i for i in range(k)])
        rr = n // (pp * qq)
        assert n == pp * qq * rr
        break
phi = (pp - 1) * (qq - 1) * (rr - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))
#b'flag{som3thing_1nter3sting_1n_su5}'

4o02 Proof

当然直接把原题搬过来肯定是不太好的，看看怎么证明的？

Pick a random polynomial $f(x)=x^3+ax^2+bx+c$, and pick a random element a in $R=\mathbb Z_n[x]/f(x)$ . If $f(x)$ is irreducible in $\mathbb F_p[x]$ then the filed $\mathbb K=\mathbb F_p[x]= \mathbb F_p[x]/f(x)=\mathbb F_{p^3}$ will be a field with order $p^3−1=(p−1)(p^2+p+1)$.

We raise a to the power of $n=pqr=p(p^2+p+1)r$ then an would probably be of order $p−1$, which implies it will be in the form of $u+0x+0x^2$ in $\mathbb K$. This means we can take the degree $1$ or $2$ coefficient of an in $R$ and gcd it with $n$ to get $p$, then we can fully factor $n$ to decrypt the flag.

This is basically the same idea as Pollard’s $p-1$ or Williams’ $p+1$ factorization algorithm, but we are doing it in a field with higher degree.

第一段给出了模 $p$ 意义下 $n$ 阶有限域的 $\mathbb F_{p^n}$ 的构造过程，这个在信安数基中讲过，不细说了。

然后简单提一下，为啥 $x^4+x^3+x^2+x+1$ 不可约，打个表看一下，可以发现，如果 $n$ 是素数，那么 $\sum_{i=0}^{n-1}$ 不可约。

其实这也很简单，因为这就是一个等比数列求和公式。
$$
\sum_{i=0}^{n-1} x^i=\frac{x^{n}-1}{x-1}
$$
然后就是考虑 $x^n-1$ 的问题，据说与分圆域和分圆多项式有关。

因为令 $x^n-1=0$，在 $\mathbb C$ 中可以解得 $x=\omega(i,n)=\cos \frac{2k\pi}{n}+\mathrm i\sin \frac{2k\pi}{n}$，其中 $k=1,2,…,n$，$x_n=\omega(n,n)=1$。如果 $n$ 是素数，假设 $i=1,2,…,n-1$，那么 $\omega(i,n)$ 的阶一定是 $n$，因为 $\gcd(i,n)$ 一定为 $1$ 。如果 $n$ 不是素数，那么 $\omega(i,n)$ 的阶不为 $n$。比如当 $n=4$ 时，$\omega(1,4)=\mathrm i$，$\omega(2,4)=-1$，$-1$ 的阶数是 $2$ 而不是 $4$。

这个 $\omega$ 也比较有趣，比如大数乘法可以使用FFT/NTT实现，最常用模数就是 $998244353$，因为 $998244353-1=2^{23}\times7\times17$，其原根为 $3$，在NTT中，最长可以计算到 $2^{23}$ 次单位根不损失精度（具体NTT可以自行了解，RLWE中常用的模数 $12289$ 和 $786433$ 也有这个性质）。其具有一个重要性质就是 $\omega(a,n)^b=\omega(ab,n)$ 和 $\omega(a,n)\omega(b,n)=\omega(a+b,n)$

当然，如果读者觉得不理解，可以尝试在原点画一个单位圆，从 $x^+$ 轴开始划分这个圆为 $n$ 等份，每一份对应圆上点的坐标就是 $(\cos \frac{2k\pi}{n},\sin\frac{2k\pi}{n})$，然后设 $\theta_k$ 为对应角，自己从 $(1,0)$ 开始，每次旋转 $\theta_k$，看看最快回到 $(1,0)$ 需要几步。这其实就对应了旋转变换。

读者如果有兴趣的话可以看看分圆多项式怎么求的，我大概看出来了几个性质（以后再补充）

1. 若 $n$ 为素数，$n$ 次分圆多项式为 $f_n(x)=\sum_{i=1}^{n-1}x^i$，比如 $f_3(x)=x^2+x+1$
2. $2n$ 次分圆多项式为 $f_n(-x)$，比如 $f_6(x)=x^2-x+1$。
3. 若 $n$ 为素数，则 $n^a$ 次分圆多项式为 $f_n(x^{n^{a-1}})$，比如 $f_9(x)=f_3(x^3)=x^6+x^3+1$，$f_{27}(x)=f_3(x^9)=x^{18}+x^9+1$。
4. $n$ 次分圆多项式次数为 $\varphi(n)$。

貌似扯远了（尴尬），反正先知道 $x^4+x^3+x^2+x+1$ 不可约。这边阶数是 $5$，那么 $\mathbb F_{p^5}$ 上，除了 $0$ 之外，都有 $a^{p^5-1}=1$ 。然后 $p^5-1=(p^4+p^3+p^2+p+1)(p-1)$。同时，对于一个群而言，若 $a^{k}=1$，则满足条件的 $a$ 有 $k$ 个，$k$ 整除群的阶数。因此，$k=p-1$ 时，满足 $a^{p-1}=1$ 的元素很明显有 $p-1$ 个，就是 $1,2,…,p-1$。带 $x$ 的阶数一定不是 $p-1$。

因此，对 $x$ 做 $n$ 次方，那么 $x^{n}=x^{kp(p^4+p^3+p^2+p+1)}$，可以看到 $x$ 的指数上有 $p^4+p^3+p^2+p+1$ 整除 $p^5-1$，因此 $x^n$ 的阶一定为 $p-1$，且 $x^n=1$ 的概率是可忽略的。因此 $x^n$ 在域中的结果，带 $x$ 的项的系数一定是 $p$ 的倍数，做公约数就可以分解 $n$ 了。

5.[2024鹏城杯]rickroll(赛后补题)

鹏城杯一共6个密码题，做了5个，有一个qwb那个apbq的第三问，还有一个题目过于trivial，就不放了。当时做完已经18:15了，看了一下这个题，就忙别的了。这里补一下题。

先看一眼题目：

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from pwn import xor
import os
from hashlib import *
from random import *


HINT = ?
FLAG = "flag{xxxxxxxx}"
EFFECTIVE_ROW = 6


def rickroll_loader():
    with open("rickroll", "r") as file:
        lines = [line.strip().encode() for line in file if line.strip()]
    return lines


def find_ezprime(size):
    while True:
        prime = getPrime(size)
        if isPrime(prime // 2):
            return prime


def secure_encrypt(message_parts, hint_value):
    modulus = find_ezprime(260)

    key_material = os.urandom(32)
    multipliers = [getrandbits(256) for _ in range(EFFECTIVE_ROW)]

    encrypted_parts = [
        int((multiplier * hint_value + bytes_to_long(xor(pad(chunk, 32)
            [::-1], key_material))) % (modulus - 1))
        for multiplier, chunk in zip(multipliers, message_parts)
    ]

    return encrypted_parts, multipliers, modulus


if __name__ == "__main__":
    rickroll = rickroll_loader()
    m = bytes_to_long(HINT)

    encrypted_lyrics, multipliers, modulus = secure_encrypt(
        rickroll[:EFFECTIVE_ROW], m)

    print("S =", encrypted_lyrics)
    print("V =", multipliers)
    print("n =", modulus)


'''
S = [624073892368439332713131144655355187273652775732037030273908973687487472640419, 1129513550732743550887354593625951854836036688324123410864182971141396110133306, 1117643028354341949186759218964558582164677605237787761003042032239935547551873, 151619055620013230556169740951169935393567570823439146992800622058967940011364, 596106506159944398847755500086869373163910176213091804211992440336880292610397, 685472210701608040945173323626153641749419080165879222271110177606156013942182]
V = [100024809269721744282017864103544473542698741247649693420201028956644193231147, 85493218764912449360009112267171851264674952927507787108286827385372626006804, 75451455656190167222034904545925816909383290106210237096763781707294423744719, 1864420400658866895837249178680154965580281261003086054650703872439476331244, 111069754111223622246512532174936637994215526100226395068812327641951277359169, 88031405587803201423744918486788030404029698214504194443110805396831023823738]
n = 1497114501625523578039715607844306226528709444454126120151416887663514076507099
'''

rickroll.txt

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you
--A mysterious singer who does not want to be named.

题目给出了 $S,V,n$ 和明文结果。

看一眼这个加密函数：这个加密方式比较奇怪：设 $q$ 为素数， $n=2q+1$ 也是素数，密钥 $k$ 是32字节固定内容。设 $x=\mathrm{hintvalue}$，则每次生成一个随即数 $A$ 作为乘数，然后乘 $x$。然后再加上 $m_i \oplus k$ 的结果。其中 $m_i$ 进行了填充。也就是
$$
C_i\equiv A_ix+m_i\oplus k \pmod {n-1}
$$

def secure_encrypt(message_parts, hint_value):
    modulus = find_ezprime(260)

    key_material = os.urandom(32)
    multipliers = [getrandbits(256) for _ in range(EFFECTIVE_ROW)]

    encrypted_parts = [
        int((multiplier * hint_value + bytes_to_long(xor(pad(chunk, 32)
            [::-1], key_material))) % (modulus - 1))
        for multiplier, chunk in zip(multipliers, message_parts)
    ]

当时感觉像是一个HNP问题，但这个题没有HNP那种明显的标志（，然后那天事情有点多，就暂时放弃了。。

不过赛后在striving✌的提示下，我又回看了一下这个题目。

受限，我们可以注意到：每一句话都是以 Never\x20gonna\x20 开头的（长度为12），并且 len(Msg[0])==len(Msg[4]),len(Msg[1])==len(Msg[3])。长度相同，就意味着填充内容也相同，那么异或同一个 $k$ 之后，得到的内容也相同。

那么上面的加密就可以写成这种形式。因为 $n=2q+1$，所以 $n-1=2q$，因此可以考虑模 $q$ 意义下的值。
$$
C_i\equiv A_ix+B_{Hi}+B_{Mi}+B_{Li} \pmod q
$$
计算 $C_{04}=C_0-C_4,C_{13}=C_1-C_3$，有
$$
\Delta C_{04}\equiv\Delta A_{04}x+\Delta B_{04}\pmod q \tag{F}
$$
和
$$
\Delta C_{13}=\Delta A_{13}x+\Delta B_{13}\pmod q\tag{G}
$$
这个位数大概在 $2^{96}$ 开始的，$x$ 长度未知，因为做差后，$B$ 相同的部分被减掉了。所以 $2^{96}\Delta B_{M04}=\Delta B_{04}$，$2^{96}\Delta B_{M13}=\Delta B_{13}$。$\Delta B_{M04}$ 约为 $88$ 位，$\Delta B_{M13}$ 约为 $96$ 位。

这边两个方程，三个未知量 $\Delta B_{M13},\Delta B_{M04},x$。因为 $x$ 的系数已知，因此可以计算 $A_{13}\text{(F)}-A_{04}\text{(G)}$ 消去 $x$，就变成了：
$$
2^{96}\Delta A_{13}\Delta B_{M04}-2^{96}\Delta A_{04}\Delta B_{M13}+\Delta C_{04}\Delta A_{13}-\Delta A_{04}\Delta C_{13}\equiv 0\pmod q
$$
去同余，有
$$
2^{96}\Delta A_{13}\Delta B_{M04}-2^{96}\Delta A_{04}\Delta B_{M13}+\Delta C_{04}\Delta A_{13}-\Delta A_{04}\Delta C_{13}-kq=0
$$
构造矩阵：

不过这样貌似是求不出来的，因此还需要一个平衡系数：因为$\Delta B_{M04}$ 约为 $88$ 位，$\Delta B_{M13}$ 约为 $96$ 位，因此前三列的平衡系数分别为 $(2^8,1,2^{96})$，然后为了扩大行列式，最后一列也给乘个 $2^{96}$。

至于这个平衡系数，可以看到我们构造的矩阵是一个上三角矩阵，因此其行列式值就是对角线四个数的乘积。我们想要的数字在 $2^{96}$ 规模，因此我们就需要将行列式提升到至少 $2^{384}$。初步构造中，因为 $\Delta B_{M04},\Delta B_{M13}$ 是我们想要的，我们在对应格放了个 $1$，第三列的 $1$ 目的是和已知的常数相乘。但三个 $1$ 放在对角线上实在是太小了，因此我们需要平衡一下前三列。估计其值与 $2^{96}$ 的差距。分别差了 $2^{8},1,2^{96}$，因此乘上平衡系数之后可以保持每一列数量级相等。而最后一列再乘一个很大的数字，是为了扩大矩阵中每一行向量的长度，并且最后一列计算得到结果为$0$。

这样操作后，不仅扩大了行列式，还没有破坏原有关系，进一步确保我们的目标向量为短向量

因此，对矩阵LLL之后，可以得到最短向量为 $(2^{8}\Delta B_{M04},B_{M13},2^{96},0)$。因此我们找第三个分量为 $2^{96}$ 的向量 $\vec v$，那么其第二个分量就是 $\Delta B_{M13}$。

EXP：

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
import os
from hashlib import *
from random import *
def bytexor(b1,b2):
    if(len(b1)<len(b2)):
        b1,b2=b2,b1
    lenb1,lenb2=len(b1),len(b2)
    bs=[0]*lenb1
    for i in range(lenb1):
        bs[i]=b1[i]^^b2[i%lenb2]
    return bytes(bs)
Msg=[
b'Never gonna give you up',
b'Never gonna let you down',
b'Never gonna run around and desert you',
b'Never gonna make you cry',
b'Never gonna say goodbye',
b'Never gonna tell a lie and hurt you']
S = [624073892368439332713131144655355187273652775732037030273908973687487472640419, 1129513550732743550887354593625951854836036688324123410864182971141396110133306, 1117643028354341949186759218964558582164677605237787761003042032239935547551873, 151619055620013230556169740951169935393567570823439146992800622058967940011364, 596106506159944398847755500086869373163910176213091804211992440336880292610397, 685472210701608040945173323626153641749419080165879222271110177606156013942182]
V = [100024809269721744282017864103544473542698741247649693420201028956644193231147, 85493218764912449360009112267171851264674952927507787108286827385372626006804, 75451455656190167222034904545925816909383290106210237096763781707294423744719, 1864420400658866895837249178680154965580281261003086054650703872439476331244, 111069754111223622246512532174936637994215526100226395068812327641951277359169, 88031405587803201423744918486788030404029698214504194443110805396831023823738]
n = 1497114501625523578039715607844306226528709444454126120151416887663514076507099
q=n//2
detAx04=(V[0]-V[4])%q
detBx04=(S[0]-S[4])%q
detAx13=(V[1]-V[3])%q
detBx13=(S[1]-S[3])%q
M=[
    [1,0,0,(2**96*detAx13)%q],
    [0,1,0,(-2**96*detAx04%q)],
    [0,0,1,(detBx04*detAx13-detAx04*detBx13)%q],
    [0,0,0,q]
]
M=Matrix(ZZ,M)
M=M*diagonal_matrix(ZZ,[2**8,1,2**96,2**96])
MLLL=M.LLL()
for v in MLLL:
    if(v[2]==2**96):
        break

print(v)
long_to_bytes((detBx13+v[1]*2**96)*inverse(detAx13,q)%q)

运行结果：

(-6513984789217167717123492864, 2791429855208147482625244161, 79228162514264337593543950336, 0)
b"Md5 of 'r1ckr01l' in the flag"

因此，我们得到了hint：Md5 of 'r1ckr01l' in the flag，因此最终答案为 flag{a0fd873d6622f7552f8141baeb0f7ee8}。