CNSS-Summer2025-Crypto-WriteUp

Crypto

原来是这样，招新赛的题放到了summer，那新生就惨喽

task1(😴 苦昼短)

见cnss-recruit-2024😴 苦昼短

O…OFB ?(🐬 詩超絆)

见cnss-recruit-2024🐬 詩超絆

线…线性规划？(😭 声声慢)

from Crypto.Util.number import *

nbits = 640
n = getRandomNBitInteger(nbits)
s = 0
a = []
x = []
for i in range(4):
    ai = getRandomNBitInteger(nbits)
    xi = getRandomNBitInteger(64 + 32 * i)
    a.append(ai)
    x.append(xi)
    s += ai * xi

k = s//n
s %= n
print(f"{n = }")
print(f"{s = }")
print(f"{a = }")
flag = 'cnss{'+"".join([str(i) for i in x])+'}'
print(flag)
'''
n = 3904064643893390361433617712655100029912556632089667501554029429639468928393101622043906144668453264281530453865022580589294831765389441377916901119131234356458963290551834945708721353433505601
s = 3604875074795055000123916123224108624958126368977597327049275476975598192797160984462664525867166641119496011661706120902314295453633878065433943707394662052729528152546793152201914658255139867
a = [2730885493586765190463536251928549081027650544135162075248013764093382819365134392595553863394291517552006396494131206919459935145536152218329288354821904074559120766005594153544756912098945832, 2682794543299249423965520585343408877939482776908813108080125635950617712534116358263875473393216488846715164240099514620137387390122653676168840502450478268278599148289754303414710910342195076, 3056310241622299025529837725147575615329254835813066425883457571781120647010672396603486688297231719653298145480220955878347533091003144227093892753771160874705140077267221046644815086744932854, 4118287861218613731723595777607376442710273799564235506091542746021449841390393039734820750495517116647742753148077759431161482333337542591059373997816043305851015242515503798301490457740269149]
flag = cnss{***}
'''

说实话，这题的格很好构造，一目了然

$$\left [ \begin{matrix} k&x_{0}&x_{1}&x_{2}&x_{3}\\ \end{matrix} \right ] * \left [ \begin{matrix} -n&0&0&0&0\\ a_{0}&1&0&0&0\\ a_{1}&0&1&0&0\\ a_{2}&0&0&1&0\\ a_{3}&0&0&0&1\\ \end{matrix} \right ] \ = \left [ \begin{matrix} s&x_{0}&x_{1}&x_{2}&x_{3} \end{matrix} \right ]$$

这里我还没未配平，然而就算配平(目标向量平衡在160bits)之后，LLL规约出来的目标向量第一个居然是n？？？wtf

不理解，然后拷打GPT一番，发现它更是一坨，感觉根本不懂什么是配平，当然代码依旧一坨

随之转战Gemini 2.5Pro，这一次它构造的格和我们稍微不一样(最下面一行，它把0给规约出来了)，虽然我前面也想到了，拷打了两次，第二次调教一下配平(与k平衡)，比GPT好用多了

大常数C最重要(最好是2**160起步，但实际手测最小为2^137)，可能我之前也是缺这么个东西，导致规约出来的向量不理想(?)
其实之前也从别人wp看到过类似的情况，但自己还没有碰到过，算是长眼了

问AI补了一下知识：LLL算法找的是格L中的向量v，它的欧几里得范数要尽可能小
如果解(v=c·L)正确(c=x0,x1,x2,x3,-k,1)，范数平方(最小)为$(x_{0}W_{0})^{2}+(x_{1}W_{1})^{2}+(x_{2}W_{2})^{2}+(x_{3}W_{3})^{2}+(kW_{4})^{2}+0$
大概会在$(x_{0}W_{0})^{2}$这个数量级(常数)附近位置(再大一点)，但如果解不正确，这时候我们假设C，范数平方会大于(C·Z)^2，且至少为C^2
这是最坏的一种情况，但如果我们让 $C^{2}>(x_{0}W_{0})^{2}$，我们就确保了下界，可以找到最小的欧几里得范数(正解)，从而找到目标向量v

感觉还是有点小瑕疵，反正差不多就这个意思

$$\left [ \begin{matrix} x_{0}&x_{1}&x_{2}&x_{3}&-k&1\\ \end{matrix} \right ] * \left [ \begin{matrix} W_{0}&0&0&0&0&C*a_{0}\\ 0&W_{1}&0&0&0&C*a_{1}\\ 0&0&W_{2}&0&0&C*a_{2}\\ 0&0&0&W_{3}&0&C*a_{3}\\ 0&0&0&0&W_{4}&C*n\\ 0&0&0&0&0&C*(-s)\\ \end{matrix} \right ] \ = \left [ \begin{matrix} W_{0}x_{0}&W_{1}x_{1}&W_{2}x_{2}&W_{3}x_{3}&W_{4}(-k)&0 \end{matrix} \right ]$$

$其实这题是flag2，因为flag1的x1位数固定，直接考flag2即可跳过flag1$

# sage
n = 3904064643893390361433617712655100029912556632089667501554029429639468928393101622043906144668453264281530453865022580589294831765389441377916901119131234356458963290551834945708721353433505601
s = 3604875074795055000123916123224108624958126368977597327049275476975598192797160984462664525867166641119496011661706120902314295453633878065433943707394662052729528152546793152201914658255139867
a = [2730885493586765190463536251928549081027650544135162075248013764093382819365134392595553863394291517552006396494131206919459935145536152218329288354821904074559120766005594153544756912098945832, 2682794543299249423965520585343408877939482776908813108080125635950617712534116358263875473393216488846715164240099514620137387390122653676168840502450478268278599148289754303414710910342195076, 3056310241622299025529837725147575615329254835813066425883457571781120647010672396603486688297231719653298145480220955878347533091003144227093892753771160874705140077267221046644815086744932854, 4118287861218613731723595777607376442710273799564235506091542746021449841390393039734820750495517116647742753148077759431161482333337542591059373997816043305851015242515503798301490457740269149]

W = [
    2**(162 - 64),
    2**(162 - 96),
    2**(162 - 128),
    2**(162 - 160),
    1
]
C = n
M = Matrix(ZZ, [
    [W[0], 0,    0,    0,    0,    C * a[0]],
    [0,    W[1], 0,    0,    0,    C * a[1]],
    [0,    0,    W[2], 0,    0,    C * a[2]],
    [0,    0,    0,    W[3], 0,    C * a[3]],
    [0,    0,    0,    0,    W[4], C * n],
    [0,    0,    0,    0,    0,    C * (-s)]
])
res = M.LLL()
if res[0][5] == 0:
    x = []
    for i in range(4):
        x.append(Integer(round(res[0][i] / W[i])))
    X = [abs(val) for val in x]
    flag = 'cnss{' + "".join([str(val) for val in X]) + '}'
    print(f"Found x values: {x}")
    print(f"FLAG: {flag}")
else:
    print("Not found")

三…三角函数？(🚗 narcissu)

from Crypto.Util.number import *
from functools import reduce
from secret import flag

P = 4
while not isPrime(P):
    lis = [getPrime(48) for i in range(6)]
    P = 1 + 4 * reduce(lambda x, y: x * y, lis)
x1 = getRandomInteger(6 * 48)


def inv(x: int) -> int:
    return pow(x, -1, P)


def add(x1: int, x2: int) -> int:
    return (x1 + x2) * inv(1 - x1 * x2) % P


def mul(a: int, y: int) -> int:
    ans = 0
    tmp = a
    while y:
        if y & 1:
            ans = add(ans, tmp)
        tmp = add(tmp, tmp)
        y >>= 1
    return ans


x2 = mul(x1, bytes_to_long(flag))
print(f"{P = }")
print(f"{x1 = }")
print(f"{x2 = }")

"""
P = 472958314625001949286760892821211871536814324967123614257153023707299229675608813176509
x1 = 238328866712703378513058278097596198883342987522679076735041467171358733524094199996347
x2 = 142236542616006661645511771838641346094908915542395871010964119785370551657030998834210
"""

$这题的加法很眼熟，加上题目提示的三角函数，得到tan(\alpha+\beta)=\frac{tan(\alpha)+tan(\beta)}{1+tan(\alpha)tan(\beta)}的形式$
$而乘法是通过加法实现的，称之为标量乘法，令x=tan(\theta)$
x2 = mul(x1, bytes_to_long(flag))可以理解为$tan(\theta_{2})=tan(\theta_{1}·m)$
$我们利用复数和欧拉公式做这样的一个映射$
$\phi(x)=\frac{1+i·x}{1-i·x}，i^{2}\equiv -1\ mod\ P，其中P=4k+1，表明平方根i存在(二次剩余QR)$
$根据欧拉公式，e^{i\theta}=cos(\theta)+isin(\theta)$
$有\phi(tan(\theta))=\frac{1+i\frac{sin(\theta)}{cos(\theta)}}{1-i\frac{sin(\theta)}{cos(\theta)}}=\frac{cos(\theta)+isin(\theta)}{cos(\theta)-isin(\theta)}=\frac{e^{i\theta}}{e^{-i\theta}}=e^{2i\theta}$
$\phi(add(x_{1},x_{2}))=\phi(tan(\theta_{1}+\theta_{2}))=e^{2i(\theta_{1}+\theta_{2})}=\phi(x_{1})·\phi(x_{2})$
$\phi(x_{2})=\phi(mul(x_{1},m))=\phi(x_{1})^{m}，因为乘法是通过倍加实现的$
$到了这一步就成了我们熟悉的离散对数DLP，只需要在模P的整数域中找到-1的模平方根即可$

$下面就是Sagemath魅力时刻！感谢Gemini\ 2.5Pro的大力支持$

# sage
import time
from Crypto.Util.number import *
P = 472958314625001949286760892821211871536814324967123614257153023707299229675608813176509
x1 = 238328866712703378513058278097596198883342987522679076735041467171358733524094199996347
x2 = 142236542616006661645511771838641346094908915542395871010964119785370551657030998834210

start = time.time()
Fp = Zmod(P)
i_p = Fp(-1).sqrt()

x1_fp = Fp(x1)
x2_fp = Fp(x2)
g_plus = (1 + i_p * x1_fp) / (1 - i_p * x1_fp)
h_plus = (1 + i_p * x2_fp) / (1 - i_p * x2_fp)

order = P - 1
# 在 Fp 上求解
m = discrete_log(h_plus, g_plus, ord=order)
flag = long_to_bytes(int(m))
print(f"🚩 Flag: {flag.decode()}")
end = time.time()
print(f"[*] time: {end - start}")

🚩 Flag: cnss{y0u_4re_m4s7er_d1scr3te_l0g}
[*] time: 180.23613619804382

椭…椭圆曲线？1(🦄 迷星叫)

# sage
import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag, key

while True:
    p=4 * prod(random.sample([*primes(3, 256)], k = 32)) - 1
    if isPrime(p):
        break
F = GF(p)
ells = list(prime_divisors((p + 1) // 4))

def encrypt(A, P, ekey):
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    for (e, ell) in zip(ekey, ells):
        for _ in range(e):
            while not (Q := (p + 1) // ell * E.random_element()):
                pass
            phi = E.isogeny(Q)
            P = phi(P)
            E = phi.codomain()
    phi = E.isomorphism_to(E.montgomery_model())
    return phi(P)

m = 4
data = []
for _ in range(4):
    ekey = [random.randrange(0, m) for _ in ells]
    E = EllipticCurve(F, [0, 0, 0, 1, 0])
    P = E.random_element()
    Q = key * P
    data.append((encrypt(0, P, ekey).xy(), encrypt(0, Q, ekey).xy()))

cipher = AES.new(key = long_to_bytes(key), mode = AES.MODE_ECB)
enc = cipher.encrypt(pad(flag, 16))

print(f"p = {p}")
print(f"data = {data}")
print(f"enc = {enc}")

'''
p = 256164319887327000989059029935823287458865939529442604969219
data = [((133322079708888134755019133444750161850879838598642433684887, 141662416810310244901219160105878753684218815280213343782668), (229143019021594526687304781835968753291812313242978239625102, 197368860501718054721602204458353352625750671877991598154057)), ((187134450081607478089479488801524874232630053794005900575216, 108690106297722459738228043998568418620629744138148194690181), (158737296444873957747216583327576148521622006828733278132244, 21759841797267370899319253789108512363816846645505810398443)), ((18592521600279966910815352919263447903089956838725738504356, 217007987923415358882996311453118946045551003198364830822737), (72802893837043345748680021219614457864560584498084819044335, 222972538476200390779435449736524404899986548610269476763396)), ((214951010493336432708756958146170664734100491612877932290657, 206792141318815098607404794799281385860758537898905322132398), (33011808565377048731911863657787101878775783475990031474694, 241862920640278847851897950044938935131848397480764375514952))]
enc = b'|\xb3\x18/9YN\x11\xd4a\xc1\x11\x1648\xbaK\x8dt\xd5\x02\xa9\x94\xac\x95*[f\x07-+\xd1\xb2\x1a\\\xe8\x84\x8c\x85*N\x02f\x94\x1d\x91f%'
'''

$曲线的阶N=P+1，光滑$
$此处的encrypt函数将曲线y^{2}=x^{3}+Ax^{2}+x\pmod P做同源映射，到蒙哥马利模型上，得到蒙哥马利曲线，并返回点在新模型下的坐标$

$data的生成：曲线y^{2}=x^{3}+x\pmod P$
$ECDLP: Q=key\cdot P，同时PQ每次都被同样的秘钥加密，然后做映射塞入到data中$

$通过点坐标可以恢复蒙哥马利曲线E'$
$因为是同源映射，Q'=key\cdot P'$
$但是用discrete_log求解方程的时候，求的其实是k$
$k\equiv key\pmod {order(P')}$
$Q'=k\cdot P'$
$我们可以找到四个k，以及四次P'在E'上的阶，通过中国剩余定理恢复出key$

# sage
from Crypto.Util.number import *
from Crypto.Cipher import AES

p = 256164319887327000989059029935823287458865939529442604969219
data = [((133322079708888134755019133444750161850879838598642433684887, 141662416810310244901219160105878753684218815280213343782668), (229143019021594526687304781835968753291812313242978239625102, 197368860501718054721602204458353352625750671877991598154057)), ((187134450081607478089479488801524874232630053794005900575216, 108690106297722459738228043998568418620629744138148194690181), (158737296444873957747216583327576148521622006828733278132244, 21759841797267370899319253789108512363816846645505810398443)), ((18592521600279966910815352919263447903089956838725738504356, 217007987923415358882996311453118946045551003198364830822737), (72802893837043345748680021219614457864560584498084819044335, 222972538476200390779435449736524404899986548610269476763396)), ((214951010493336432708756958146170664734100491612877932290657, 206792141318815098607404794799281385860758537898905322132398), (33011808565377048731911863657787101878775783475990031474694, 241862920640278847851897950044938935131848397480764375514952))]
enc = b'|\xb3\x18/9YN\x11\xd4a\xc1\x11\x1648\xbaK\x8dt\xd5\x02\xa9\x94\xac\x95*[f\x07-+\xd1\xb2\x1a\\\xe8\x84\x8c\x85*N\x02f\x94\x1d\x91f%'

F = GF(p)
remainders = []
moduli = []
for i, ((xp, yp), (xq, yq)) in enumerate(data):
    xp, yp, xq, yq = F(xp), F(yp), F(xq), F(yq)
    xp_sq_inv = (xp^2)^-1
    A_prime = (yp^2 - xp^3 - xp) * xp_sq_inv
    E_prime = EllipticCurve(F, [0, A_prime, 0, 1, 0])
    P_prime = E_prime(xp, yp)
    Q_prime = E_prime(xq, yq)
    order = P_prime.order()
    moduli.append(order)
    k = P_prime.discrete_log(Q_prime)
    remainders.append(k)
key = crt(remainders, moduli)
key = long_to_bytes(int(key), 16)
cipher = AES.new(key=key, mode=AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(f"\n[+] Flag: {flag.decode()}")

格…格基规约？(❄️ White Album 2)

from sage.all import *
import os
import random
from Crypto.Util.number import *
from secret import flag

p = getPrime(150)
m = int(pow(p, 1 / 3))

def pad(msg):
    L = 512
    lenL = random.randrange(0, L - len(msg) + 1)
    lenR = L - len(msg) - lenL
    return os.urandom(lenL) + msg + os.urandom(lenR)

def encrypt(msg):
    s = [bytes_to_long(msg[i : i + 16]) for i in range(0, len(msg), 16)]
    ls = len(s)
    Fp = GF(p)
    A = random_matrix(Fp, ls * ls, ls)
    s = vector(Fp, s)
    e = vector(Fp, [random.randrange(-m, m + 1) for _ in range(ls * ls)])
    b = A * s + e
    return A, b

A, b = encrypt(pad(flag))

with open("data.txt","w") as f:
    f.write(f"p = {p}\n")
    f.write(f"A = {list(A)}\n")
    f.write(f"b = {list(b)}\n")

$flag被前后pad为512字节，分成了32段的s，A是1024*32的随机矩阵，错误向量e_{i}\in [-2^{50},2^{50}]，还是很大的数$

$A的维度太大了，并且flag是被前后填充的，实际就可能中间的三四块，可以优化的地方是这两个$

但是不管了，先把糖醋小鸡块师傅的LWE-primal attack(优化版本)拿过来跑了

# sage
from sage.all import *
from Crypto.Util.number import long_to_bytes
import ast
from time import time
import re

m,n,esz = 512, 32, 2**50
start = time()
with open("data.txt", "r") as f:
    p_str = f.readline().strip()
    A_str = f.readline().strip()
    b_str = f.readline().strip()
    p = ast.literal_eval(p_str.split('=')[1].strip())
    A_list = ast.literal_eval(A_str.split('=')[1].strip())
    b_list = ast.literal_eval(b_str.split('=')[1].strip())

A = Matrix(ZZ, A_list[:m])
b = vector(ZZ, b_list[:m])
def primal_attack2(A,b,m,n,p,esz):
    L = block_matrix(
        [
            [matrix(Zmod(p), A).T.echelon_form().change_ring(ZZ), 0],
            [matrix.zero(m - n, n).augment(matrix.identity(m - n) * p), 0],
            [matrix(ZZ, b), 1],
        ]
    )
    #print(L.dimensions())
    Q = diagonal_matrix([1]*m + [esz])
    L *= Q
    L = L.LLL()
    L /= Q
    res = L[0]
    if(res[-1] == 1):
        e = vector(GF(p), res[:m])
    elif(res[-1] == -1):
        e = -vector(GF(p), res[:m])
    s = matrix(Zmod(p), A).solve_right((vector(Zmod(p), b)-e))
    return s

s=primal_attack2(A,b,m,n,p,esz)

if s:
    print("[+] 攻击成功, 正在尝试恢复 Flag...")
    try:
        padded_flag_bytes = b""
        for val in s:
            integer_val = int(val.lift())
            padded_flag_bytes += long_to_bytes(integer_val, 16)  
        print(f"[*] 已恢复512字节的填充后消息。")
        match = re.search(b'cnss\{[^\}]+\}', padded_flag_bytes)
        if match:
            flag = match.group(0).decode()
            print("\n" + "="*50)
            print("🎉🎉🎉 Flag 提取成功! 🎉🎉🎉")
            print(f"[*] Flag: {flag}")
            print("="*50)
        else:
            print("\n[-] 未能在恢复的数据中找到 'cnss{...}' 格式的 Flag。")
            print("[*] 恢复的原始数据（可能包含乱码）如下:")
            print(padded_flag_bytes)
    except Exception as e:
        print(f"\n[!] 在 Flag 重建过程中发生错误: {e}")
else:
    print("\n[-] 攻击失败, 未能恢复向量 s。")

end = time()
print(f"[*] 总计用时 {end - start:.2f}s")

[+] 攻击成功, 正在尝试恢复 Flag...
[*] 已恢复512字节的填充后消息。

==================================================
🎉🎉🎉 Flag 提取成功! 🎉🎉🎉
[*] Flag: cnss{9dbee80aaef3bfca2fb576a7e11d986f}
==================================================
[*] 总计用时 9202.24s

$不负众望，我的电脑两个半小时拿下！$

椭…椭圆曲线？2*(🌂 壹雫空)

from collections import namedtuple
from Crypto.Util.number import *
from secret import flag

inf = -1
Point = namedtuple('Point', ['x', 'y'])
Pubkey = namedtuple('Pubkey', ['n', 'e', 'r'])
Privkey = namedtuple('Privkey', ['p', 'q', 'd'])

class Curve:
    def genkey(self, nbits, dbits):
        while True:
            p = getPrime(nbits // 2)
            if(p % 3 == 1):
                break
        while True:
            q = getPrime(nbits // 2)
            if(q % 3 == 1):
                break
        n = p * q
        while True:
            r = getRandomRange(1,n)
            if((pow(r, (p-1)//3, p) != 1) and (pow(r, (q-1)//3, q) != 1)):
                break
        d = getPrime(dbits)
        e = inverse(d, (p * p + p + 1) * (q * q + q + 1))
        return Pubkey(n, e, r), Privkey(p, q, d)
    
    def __init__(self, nbits, dbits):
        self.Pubkey, self.Privkey = self.genkey(nbits, dbits)
    
    def product(self, a, b):
        n, _, r = self.Pubkey
        if(a == Point(inf, inf)):
            return b
        if(b == Point(inf, inf)):
            return a
        if(a.y == inf):
            a, b = b, a
        u, v = a
        p, q = b
        if(q == inf):
            if(v == inf):
                return Point((u * p) % n, (u + p) % n)
            elif((v + p) % n):
                iv = inverse(v + p, n)
                return Point((u * p + r) * iv % n, (u + v * p) * iv % n)
            elif((u - v * v) % n):
                iv = inverse(u - v * v, n) 
                return Point((u * p + r) * iv % n, inf)
            else:
                return Point(inf, inf)
        else:
            if((u + p + v * q) % n):
                iv = inverse(u + p + v * q, n)
                return Point((u * p + (v + q) * r) * iv % n, (v * p + u * q + r) * iv % n)
            elif((v * p + u * q + r) % n):
                iv = inverse(v * p + u * q + r, n)
                return Point((u * p + (v + q) * r) * iv % n, inf)
            else:
                return Point(inf, inf)

    def encrypt(self, a):
        k = self.Pubkey.e
        res = Point(inf, inf)
        while k:
            if(k & 1):
                res = self.product(res, a)
            a = self.product(a, a)
            k >>= 1
        return res
    
    def decrypt(self, a):
        k = self.Privkey.d
        res = Point(inf, inf)
        while k:
            if(k & 1):
                res = self.product(res, a)
            a = self.product(a, a)
            k >>= 1
        return res

SYS = Curve(512, 256)
msg = Point(bytes_to_long(flag[:len(flag)//2]),bytes_to_long(flag[len(flag)//2:]))
enc = SYS.encrypt(msg)

print(f"pubkey = {SYS.Pubkey}")
print(f"enc = {enc}")

'''
pubkey = Pubkey(n=4873189510606632670051462507037860421077551672164701436608907002436560192840356016750494285565924106988544952397402675547921930867836902302893011890256779, e=13378485234962864327763969254924381829836619219064695812825856516258702951436596931331119028308233868359134774242758549790397497067433124687542530097719178781601238604579006713726763589993220493028013459103929256891706082648574000763659034977028816094438365563682368664776491208827662655323646975736791610283, r=12276290027089634179666721556762461660058574159904682072699747683370547320796053531346228587347389593630764829928291692127976550810879034430985232250912)
enc = Point(x=2091733356436558288163136748650604712672684547651742349852169921359344595959145998331036292720052611932763413100160720842985758067666744134352011068441384, y=3606887286200111465466487525784448417643735862168228528263397534620187006806130329379762200338558634931139253300267143260393005244954232632353514520202318)
'''

自定义公钥系统，不一样的KMOV？
p % 3 == 1，见过余2的，还没见过余1的
椭圆曲线上的RSA

这题的方向应该是基于大整数很难被分解，关键是要找到r怎么去利用？
暂时就这么些思考了……