Mobile wallpaper 1Mobile wallpaper 2Mobile wallpaper 3Mobile wallpaper 4Mobile wallpaper 5Mobile wallpaper 6
Profile Image of the Author
Q1uJu
Announcement
Hope my blog can help you.
Site Statistics
Posts
5
Categories
2
Tags
2
Total Words
13,640
Running Time
0 days
Last Activity
0 days ago
3941 words
20 minutes
鹏城杯 2025 WriteUp
2025-12-17
WriteUp
2025

题目后面带(*)的是指赛后出了复现的~

Crypto#

true_of_false#

题目：

import json, random, hashlib
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes


A=1103515245
B=12345
MOD=2**31


def lcg(s):
    while True:
        s=(A*s+B)%MOD
        yield s&0xFF


def mix(b,s):
    g=lcg(s)
    o=bytearray()
    for i in range(0,len(b),8):
        t=b[i:i+8][::-1]
        for x in t:
            o.append(x^next(g))
    return bytes(o)


BITS=512
e=65537
p=getPrime(BITS)
q=getPrime(BITS)
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)


FLAG=b"flag{de5b8aec-6294-42dd-8038-18e0854e3d22}"
m=bytes_to_long(hashlib.sha256(FLAG).digest())
flag_enc=bytes_to_long(FLAG)^m


sig_ok=pow(m,d,n)


d_p=d%(p-1)
d_q=d%(q-1)
s_p=pow(m,d_p,p)
s_q=random.randrange(q)
inv= inverse(q,p)
sig_fault=(s_q+q*((s_p-s_q)*inv%p))%n


seed=random.randrange(1,2**31)
cj={
    "n":hex(n),
    "e":e,
    "sig_ok_mixed":mix(long_to_bytes(sig_ok),seed).hex(),
    "sig_fault_mixed":mix(long_to_bytes(sig_fault),seed+123456).hex(),
    "flag_enc":hex(flag_enc),
    "seed_hint":seed%97
}


json.dump(cj,open("challenge.json","w"),indent=0)

送flag的题一，难评。仔细看看考点（）好像还是挺新奇的，起码我是第一次见。

加密流程

整体分为RSA加密层和LCG混淆层。

RSA加密层的加密方式类似 One-Time Pad：flag_enc = flag ^ m。要想拿到flag，就必须先算出m。

而m给出了两个签名，一是正常签名sig_ok，由RSA私钥d进行签名：

s=md(modn)s=m^d\pmod{n}

二是故障签名sig_fault，这里使用了CRT加速签名的变体，但是再计算q分量时引入了错误（s_q = random）。

正确：

sp≡md(modp)s_p\equiv m^{d}\pmod{p}

使得组合出的sig_fault在模p下正确，在模q下错误：

sigfault=（sq+q∗((sp−sq)∗q−1(modp))(modn)sig_{fault}=（s_q+q*((s_p-s_q)*q^{-1}\pmod{p})\pmod{n}

接着LCG混淆层生成了一个随机种子seed，给出了一个已知a，b，mod的LCG生成器，mix函数中将输入的数据按 8 字节分组，反转后和LCG生成的随机字节进行异或。

题目给出了

解密思路

利用Bellcore Attack作为验证标准爆破出seed，从而恢复真实签名，再恢复m和flag。

首先只能爆破出LCG种子，种子的范围上给出了seed_hint = seed % 97，范围的话暂时只能定在p以下。然后验证标准就要使用Bellcore Attack也就是故障攻击的原理：

gcd(∣S−S′∣,n)=pgcd(|S-S'|, n)=p

所以在爆破时同时解混淆得到两个签名，计算差值与n的最大公约数，如果位数为 512 位说明seed正确且成功分解n。

拿到seed后拿正确签名恢复m即可。

exp.py：

import json
from math import gcd
from tqdm import trange
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse


A = 1103515245
B = 12345
MOD = 2 ** 31


def lcg(s):
    while True:
        s = (A * s + B) % MOD
        yield s & 0xFF


def unmix(mixed_hex, seed):
    data = bytes.fromhex(mixed_hex)
    g = lcg(seed)
    o = bytearray()
    for i in range(0, len(data), 8):
        chunk = data[i:i + 8]
        xor_chunk = bytearray()
        for x in chunk:
            xor_chunk.append(x ^ next(g))
        o.extend(xor_chunk[::-1])
    return bytes(o)


data = json.load(open("challenge.json", "r"))
n = int(data["n"], 16)
e = data["e"]
sig_ok_hex = data["sig_ok_mixed"]
sig_fault_hex = data["sig_fault_mixed"]
flag_enc = int(data["flag_enc"], 16)
seed_hint = data["seed_hint"]
start_seed = seed_hint if seed_hint != 0 else 97
if start_seed < 1: start_seed += 97
found_p = None
real_seed = None
real_sig_ok = None
for s in trange(start_seed, 2 ** 31, 97):
    bytes_ok = unmix(sig_ok_hex, s)
    val_ok = bytes_to_long(bytes_ok)
    if val_ok >= n:
        continue
    bytes_fault = unmix(sig_fault_hex, s + 123456)
    val_fault = bytes_to_long(bytes_fault)
    if val_fault >= n:
        continue
    diff = abs(val_ok - val_fault)
    if diff == 0:
        continue
    p = gcd(diff, n)
    if 1 < p < n:
        found_p = p
        real_seed = s
        real_sig_ok = val_ok
        print(f"[+] Found Seed: {s}")
        break
if found_p:
    m = pow(real_sig_ok, e, n)
    flag = flag_enc ^ m
    print(long_to_bytes(flag).decode())
#   0%|          | 131/22139007 [00:00<24:06, 15304.69it/s]
# [+] Found Seed: 12720
# flag{de5b8aec-6294-42dd-8038-18e0854e3d22}

weak_leak#

题目：

from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
import os, base64, random
from math import gcd


e = 65537
LCG_A, LCG_B, LCG_MOD = 1103515245, 12345, 10007
SECRET_VALUE = 1234


password = f"{random.randint(0,999999):06d}"
salt = os.urandom(8).hex()
hash_val = sha256((salt + password).encode()).hexdigest()


def gen_seq(seed,a,b,m,length):
    seq=[seed % m]
    for _ in range(length-1):
        nxt=(a*seq[-1]+b) % m
        nxt ^= (seq[-1] & 0xff)
        seq.append(nxt)
    return seq


lcg_seed = (int(password) ^ SECRET_VALUE) % LCG_MOD
seq = gen_seq(lcg_seed, LCG_A, LCG_B, LCG_MOD, 15)
seq_prefix = seq[:7]
seq9 = seq[9]


BITS = 256
p = getPrime(BITS)
q = getPrime(BITS)
n = p * q
n1 = p * (q + 1)
n2 = (p + 1) * q + seq9


aes_key = os.urandom(16)
mask_bytes = sha256(str(seq9).encode()).digest()[:16]
masked_key_int = bytes_to_long(aes_key) ^ bytes_to_long(mask_bytes)


cipher_rsa = pow(masked_key_int, e, n)


FLAG = b"flag{7980dd68-c028-439d-8f33-3b4e4cfeeb55}"
iv = os.urandom(16)
cipher = AES.new(aes_key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(FLAG,16))




print("salt:", salt)
print("hash:", hash_val)
print("n1:", n1)
print("n2:", n2)
print("seq_prefix:", ",".join(str(x) for x in seq_prefix))
print("cipher_rsa:", cipher_rsa)
print("iv:", base64.b64encode(iv).decode())
print("ciphertext:", base64.b64encode(ct).decode())
'''
salt: ...
hash: ...
n1: ...
n2: ...
seq_prefix: ...
cipher_rsa: ...
iv: ...
ciphertext: ...
'''

送flag的题二。先是一个hash爆破，解出的password用于LCG的种子，然后由变种LCG算法生成序列，求得seq9用于后续加密，然后是一个简单的RSA，给出了n1和n2两个hint，联立求解方程就行。最后按流程恢复aes_key，求解密文。

exp.py：

from Crypto.Util.number import long_to_bytes, inverse
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from base64 import b64decode
from sympy import symbols, Eq, solve
from hashlib import sha256
from tqdm import trange


salt = "..."
target_hash = "..."
n1 = ...
n2 = ...
cipher_rsa = ...
iv_b64 = "..."
ct_b64 = "..."
LCG_A, LCG_B, LCG_MOD = 1103515245, 12345, 10007
SECRET_VALUE = 1234
e = 65537
for i in trange(1000000):
    candidate = f"{i:06d}"
    h = sha256((salt + candidate).encode()).hexdigest()
    if h == target_hash:
        password_str = candidate
        print(f"[+] Found password: {password_str}")
        break


def gen_seq(seed, a, b, m, length):
    seq = [seed % m]
    for _ in range(length - 1):
        nxt = (a * seq[-1] + b) % m
        nxt ^= (seq[-1] & 0xff)
        seq.append(nxt)
    return seq
lcg_seed = (int(password_str) ^ SECRET_VALUE) % LCG_MOD
seq = gen_seq(lcg_seed, LCG_A, LCG_B, LCG_MOD, 15)
seq9 = seq[9]
print(f"[+] Recovered seq9: {seq9}")


val_b = n2 - seq9  # val_b = pq + q
delta = n1 - val_b # delta = (pq + p) - (pq + q) = p - q
p, q = symbols("p q")
eq1 = Eq(p * (q + 1), n1)
eq2 = Eq((p + 1) * q + seq9, n2)
p, q = solve([eq1, eq2], p, q)[1]
p, q = int(p), int(q)
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
masked_key_int = pow(cipher_rsa, d, n)


mask_bytes = sha256(str(seq9).encode()).digest()[:16]
mask_int = int.from_bytes(mask_bytes, 'big')
aes_key_int = masked_key_int ^ mask_int
aes_key = long_to_bytes(aes_key_int)
print(f"[+] Recovered AES Key: {aes_key.hex()}")


iv, ct = b64decode(iv_b64), b64decode(ct_b64)
cipher = AES.new(aes_key, AES.MODE_CBC, iv)
plaintext = unpad(cipher.decrypt(ct), 16)
print(plaintext.decode())
#  38%|███▊      | 384457/1000000 [00:00<00:00, 1186476.50it/s]
# [+] Found password: 384457
# [+] Recovered seq9: 2191
# [+] Recovered AES Key: ab2553cc5412343bdbd1607770492fcf
# flag{7980dd68-c028-439d-8f33-3b4e4cfeeb55}

babyrsa#

题目：

from Crypto.Util.number import *
import decimal
m=long_to_bytes("?????")
p=getPrime(1024)
while True:
    q=getPrime(1024)
    if p>q:
        break
n=p*q
e="?????"
d=inverse(e,(p-1)*(q-1))
c=pow(m,e,n)
decimal.getcontext().prec = 1024
P=decimal.Decimal(p)
Q=decimal.Decimal(q)
leak=decimal.Decimal((3*P*P-1)/(3*P*Q))
print("c =",c)
print("leak =",leak)
print("d =",d)
#leak = ...
#d = ...
#c= ...

BaseCTF 2024 Week 3 - wiener?

基本和原题一样，直接给个链接。

exp.py：

# SageMath 10.7
from Crypto.Util.number import *


leak = ...
d = ...
c = ...
cf = continued_fraction(leak)
convers = cf.convergents()
for pkd in convers:
    pp, pq = pkd.as_integer_ratio()
    pp = int(pp)
    if pp.bit_length() == 1024 and isPrime(pp):
        flag = long_to_bytes(int(pow(c, d, pp)))
        if b'flag' in flag:
            print(flag.decode())
            break
# flag{th1s_1s_4_ture_fl4g}

PECO#

题目：

from Crypto.Util.number import *
from secret import FLAG,x,y


f0= bytes_to_long(FLAG[:len(FLAG)//2].encode())
f1= bytes_to_long(FLAG[len(FLAG)//2:].encode())


n= int(...)
c= int(...)
gift1= int(...)
gift2= int(...)




m=getPrime(1876)
p=getPrime(1024)
q=getPrime(1024)
print(p,q)
n=p*q
e=65537
c=pow(m,e,n)
print('n=',n)
print('c=',c)
print('gift1=',1293023064232431070902426583269468463*x**2-105279230912868770223946474836383391725923*y**2)
print('gift2=',(p**7+q**13)&(2**777-1))


assert (x*f0+y*f1)%m <2**99

求解思路整体大概就是四步：求解 Pell 方程，Hensel Lifting 恢复p_low，CopperSmith 打出p，格攻击恢复f0和f1。

求解 Pell 方程

题目给出了gift1的关系式如下：

gift1=A⋅x2−B⋅y2gift_1=A\cdot x^2-B\cdot y^2

而仔细观察会发现，A = gift1，此方程就可以转化为标准的佩尔方程：

x2−BAy2=1x^2-\frac{B}{A}y^2=1

我们可以计算 B/A\sqrt{B/A} 的连分数展开，通过连分数找到满足方程的最小解(x, y)。

Hensel Lifting 恢复 p_low & CopperSmith 打出 p

题目给出了gift2的关系式如下：

gift2=(p7+q13)&(2777−1)⇒p7+q13≡gift2(mod2777)⇒p7+(n⋅p−1)13≡gift2(mod2777)⇒p7+n13⋅p−13−gift2≡0(mod2777)⇒p20−gift2⋅p13+n13≡0(mod2777)\begin{align} gift_2=(p^7+q^{13})\&(2^{777}-1)\\ \Rightarrow p^7+q^{13}\equiv gift_2\pmod{2^{777}}\\ \Rightarrow p^7+(n\cdot p^{-1})^{13}\equiv gift_2\pmod{2^{777}}\\ \Rightarrow p^7+n^{13}\cdot p^{-13}-gift_2\equiv 0\pmod{2^{777}}\\ \Rightarrow p^{20}-gift_2\cdot p^{13}+n^{13}\equiv 0\pmod{2^{777}} \end{align}

直接用 SageMath 的roots()方法可以求出p的低 777 位，剩余的约 247 位直接 CopperSmith 打就行，打出p了就可以求出m了。

格

最后给了一个约束条件：

(x⋅f0+y⋅f1)(modm)<299(x\cdot f_0+y\cdot f_1)\pmod{m}<2^{99}

即存在小整数k和小整数diff(0 <= diff < 2 ** 99)使得：

x⋅f0+y⋅f1−k⋅m=diffx\cdot f_0+y\cdot f_1-k\cdot m=diff

直接构格打（m很大，直接打就行不用配平）：

M=[10x01y00m]M=\begin{bmatrix} 1 & 0 & x\\ 0 & 1 & y\\ 0 & 0 & m \end{bmatrix}(f0,f1,−k)M=(f0,f1,diff)(f_0,f_1,-k)M=(f_0,f_1,diff)

exp.py：

# SageMath 10.7
from Crypto.Util.number import long_to_bytes


n = ...
c = ...
gift1 = ...
coeff_x = ...
coeff_y = ...
gift2 = ...
e = 65537
# Pell
D = QQ(coeff_y) / QQ(coeff_x)
sqrt_D = sqrt(D)
cf = continued_fraction(sqrt_D)
x_pell, y_pell = 0, 0
for convers in cf.convergents():
    num = convers.numerator()
    den = convers.denominator()
    if coeff_x * num ** 2 - coeff_y * den ** 2 == gift1:
        x_pell = int(num)
        y_pell = int(den)
        break
# Hensel Lifting
mod_poly = 2 ** 777
PR.<x> = PolynomialRing(Zmod(mod_poly))
f = x ** 20 - gift2 * x ** 13 + n ** 13
plow = int(f.roots(multiplicities=False)[0])
# CopperSmith
PR.<x> = PolynomialRing(Zmod(n))
f = x * 2 ** 777 + plow
phigh = int(f.monic().small_roots(X=2**247, beta=0.4, epsilon=0.01)[0])
p = int(phigh * 2 ** 777 + plow)
q = n // p
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = int(pow(c, d, n))
# Lattice
M = Matrix(ZZ, [[1, 0, x_pell],
                [0, 1, y_pell],
                [0, 0, m]])
f = M.LLL()[0]
print(long_to_bytes(abs(int(f[0]))).decode() + long_to_bytes(abs(int(f[1]))).decode())
# flag{p4ssword_b1g_snake!!}

budo的pem(*)#

public.pem：

1b0a79b5f7bdf1088a4f77a10b13ad8a3671dbff92
0013137fc5e2975a581cd87bcc8515d873bfaec4334cb1c31b16206316f92cbe449fae811574113e5eb2ed0153d1fccb80a0210e8076e1c5fbf6afabbea73ad1805c0a1b20c70cf2c13bfe03


028201    # e
00705509ec283dc94e3bbe85ca1e36858586721f3d1a8d67813451e160728cc87e73a5f16a3c4ed3efb553ede15d5401de32c265cc4902a6666a3b7d8e9844b9cb2a1ffc4479df0d0f1ee992718493ad47cb289df206337a063a0fb0d75f66a0998120a0227b4ac01000eee0e8e60012aa6ab613fb92b373922ee3285b6cbd429a3bf8a63172090e146b19cf190af15abe6573e99abbfd01695f800c2cf47063ef7fec9e6960f91968243b6732ae431a3ef408ea027e3e7cd446e33d430f18edbad8c65f754b064a83cc0ff81d794726c5c1f7d39ff91a79cd3a7e18fe26f3cfa23de3349fcb44d7084a05e79aed9890adeae932d3e7789d020832432362b1e125

private.pem：

3082046d  # Begin Sequence: len=0x046d
0201    # Version: (len=0x01)
00


02820101  # n
00d81db195024c9bd03dd856656ad119fa19a0a77120bf10d9c402f4eb3dc798b611fdd9c209c17d87939fa92fb0e8c1147323227dd2edd81b40f682a54de1035f0af03a660ec1b34db68884d038e2e1afaab79546d47250fd30d2a70a7ffd83f1138f353ec94f58bf2b3448f8c4d332419e3e1a32cf731dcedb66ec1fc40afdfe3a05ad2d1cf4f766a642cb64690b45e2b646563afb6dfdf599df84838b711f
1b0a79b5f7bdf1088a4f77a10b13ad8a3671dbff92

蛮抽象的，大e和n，比赛实在没想到，要把n结合公私钥拼起来hhhh，Boneh直接打就行，m设 6 就够。

exp.py：

from __future__ import print_function
import time


############################################
# Config
##########################################


"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True


"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False


"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension


############################################
# Functions
##########################################


# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1


    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")


# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)


# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB


    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj


            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB


            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB


"""
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May


    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """


    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()


    UU = XX*YY + 1


    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()


    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()


    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution


    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)


    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)


    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0,0


    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^mm)


    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print("We do not have det < bound. Solutions might not be found.")
        print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")


    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)


    # LLL
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")


    BB = BB.LLL()


    if debug:
        print("LLL is done!")


    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False


    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)


            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)


            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break


    if not found_polynomials:
        print("no independant vectors could be found. This should very rarely happen...")
        return 0, 0


    rr = rr(q, q)


    # solutions
    soly = rr.roots()


    if len(soly) == 0:
        print("Your prediction (delta) is too small")
        return 0, 0


    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]


    #
    return solx, soly


def example():
    ############################################
    # How To Use This Script
    ##########################################


    #
    # The problem to solve (edit the following values)
    #


    # the modulus
    N = ...
    # the public exponent
    e = ...


    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .26 # this means that d < N^delta


    #
    # Lattice (tweak those values)
    #


    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 6 # size of the lattice (bigger the better/slower)


    # you need to be a lattice master to tweak these
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(N^delta)  # this _might_ be too much
    Y = floor(N^(1/2))    # correct if p, q are ~ same size


    #
    # Don't touch anything below
    #


    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)


    #
    # Find the solutions!
    #


    # Checking bounds
    if debug:
        print("=== checking values ===")
        print("* delta:", delta)
        print("* delta < 0.292", delta < 0.292)
        print("* size of e:", int(log(e)/log(2)))
        print("* size of N:", int(log(N)/log(2)))
        print("* m:", m, ", t:", t)


    # boneh_durfee
    if debug:
        print("=== running algorithm ===")
        start_time = time.time()


    solx, soly = boneh_durfee(pol, e, m, t, X, Y)


    # found a solution?
    if solx > 0:
        print("=== solution found ===")
        if False:
            print("x:", solx)
            print("y:", soly)


        d = int(pol(solx, soly) / e)
        print("private key found:", d)
        from Crypto.Util.number import bytes_to_long, long_to_bytes
        c = bytes_to_long(open("enc", "rb").read())
        m = int(pow(c, d, N))
        print(long_to_bytes(m).decode())
    else:
        print("=== no solution was found ===")


    if debug:
        print(("=== %s seconds ===" % (time.time() - start_time)))


if __name__ == "__main__":
    example()
# flag{RSA_key_rebuild_success}

RandomAudit(*)#

呃，我真的会无语…

题目描述

某内部审计系统号称“全部采用自研高强度密码模块”，为了节省日志空间，他们把敏感日志 AES 加密后上传，又用 RSA 对关键密钥做了“备份加密”，最后还用“秘密分享”来保护真正的 FLAG。不幸的是，开发同学对“随机数”和“密码学”理解似乎有点……偏差。你从审计服务器上拿到了以下文件你的任务是：从这些文件中还原出最终的 flag。

看zsm师傅和chenxing师傅的博客试着复现复现hhhh，比赛反正我下午看的时候只有 1 解，不知道是哪位师傅的。

给了四个文件aes_ct.txt，rsa_pub.txt，session_ids.txt，shares.enc，我这就不整理思路了，相当于在两位师傅的思路基础上直接说解题过程了。

session_ids.txt里的五个随机数是LCG的五个状态，所以我们可以根据这五个状态恢复求解器，然后往下生成四个状态，第三四两个随机数拼接在一起就是已知的iv，所以猜测第一二两个随机数拼接在一起是key，然后使用 AES-CTR 模式解密aes_ct.txt得到rsa_seed。这个seed是生成p和q的Random对象的种子。由此可以得到p和q，结合rsa_pub.txt解出shares.enc的三个数值，是等差数列，他们的固定diff转十六进制加上-构成的uuid就是flag。

exp.py：

# LCG
state = [18180927788752802137, 17282895955721322606, 6099480220253429739, 6300661433352782096, 16375414315099041565]
# all 64 bit
p = 2 ** 64
a = (state[2] - state[1]) * pow(state[1] - state[0], -1, p) % p
b = (state[1] - a * state[0]) % p
print(f"{a = }")
print(f"{b = }")
print(f"{p = }")
# a = 2985016781437487305
# b = 7999203871274490253
# p = 18446744073709551616
a = 2985016781437487305
b = 7999203871274490253
p = 18446744073709551616
new_state = []
state = 16375414315099041565
for i in range(4):
    state = (a * state + b) % p
    new_state.append(state)
for i in new_state:
    print(f"state {new_state.index(i)}: {hex(i)[2:]}")
# state 0: e18e0b036273ff52
# state 1: 1ae1729d164360ef
# state 2: 42c92a1cdbb02d34 iv[:16]
# state 3: 7b4b12b9609cf761 iv[16:]


# AES CTR
from Crypto.Cipher import AES
from Crypto.Util import Counter


key = bytes.fromhex("e18e0b036273ff521ae1729d164360ef")
iv = bytes.fromhex("42c92a1cdbb02d347b4b12b9609cf761")
ciphertext = bytes.fromhex("1268d5a5513b091aa91bd263479e066b07fadc2fbbe45bef3c551f5743df6290efac6008efec815a92d781f56d46a70c")
counter = Counter.new(128, initial_value=int(iv.hex(), 16))
cipher = AES.new(key=key, mode=AES.MODE_CTR, counter=counter)
pt = cipher.decrypt(ciphertext).decode()
print(pt)
# rsa_seed=106141198856029082317733263764736461207


# RSA
import random
from Crypto.Util.number import long_to_bytes, inverse


rsa_seed = 106141198856029082317733263764736461207
n = 14448446619901911082459007889685721725680439060725350743569322155645458011734556057675947993220704371020476516568646586885283913148938740926737898805445614714032672445417590527807998210095698512153249389800494251979617943578391716055258550807448612914300134993287344474991004931078983886017648843976928491853922545681367649020611719416129281298024839864263193236272253977406788185152922537075953161349835965958367362419140954183280033874927397931106816815848243331537133623628059136650221110030928439294443459932885523261901634369102152105618433841943766668404214910274232926198895411937001894534370492568479216945821
print(n.bit_length())
# 2047
e = 65537
enc = [10490446977619103069001003040486311071978258142421336052507257522875474797470114964826023919192727268692922256856652858277992495171032562230040420656266197389810578603393339709249435149905947489583447642314971169203129701324545382296605329968093805623085091037041383918898863606006040657610555353505097417933879241971194430768615532922845973883691987688479825332766028800851528002249541074495918035787961557869335382147521674475402254162082487461333820079507872678735070636201634641388295625530938494923015901907636472951311020506187207731872422229080880406432931064027509903450627233085289319384639770111853961194173,
       743543530169071239116476194995130287577397444839878381190323439278920253193070703147739971809232103531663814326885396949461522610039497489729382962956546531947712520339554515115672653928505197575781138133407250554871658829577958508307679587210232844184449562790093797350878222669855209441010484097564691896453015601662453896822719270868321247424008816580067245157535459310278265418077691933129567685517708559976634296731742166139336765265993523200086705895447733895631261834250507718941102582843992200156414235064121973675311925953582587558104979368104990418797298789916260850166852409948945330444433345847549654807,
       2029042383383543423822480961040444011316223475888350349028507603033900194528521850810498682278559241519416272300206175404920960777005556199927430201052663390710468284846655098680434563893510099837791622819154273540446883979349265553248678057937124051615313506877155912975894736822847688340682915149135134624117775360734190231872747665460355709192535066382845245616076861873767871845621325187272538154068026983469680440318851689871048209435452483669288691299287219165436861956437625332354783255272742721764184259145427360294854601680425317982867911864451490378130715517007586443259629430886305855145096221339953320736]
random.seed(rsa_seed)
for i in range(1000):
    p = random.getrandbits(1024)
    if n % p == 0:
        print(f"{i = }")
        print(f"{p = }")
        break
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
for c in enc:
    m = pow(c, d, n)
    print(f"m{enc.index(c)} = {m}")
# i = 731
# p = 90609714628980382832928314067735122109537000815405703652905812504340171456915234535659504024209916610947095995757554416998229460671634350728278188486124871962281306292021145245327286154856863282195166928593488382708996274001548097657625671236135154197435672004124259946571008184688393674125715687022036411833
# m0 = 123456789012345678901234567890123456775
# m1 = 246913578024691357802469135780246913564
# m2 = 370370367037037036703703703670370370353
m0 = 123456789012345678901234567890123456775
m1 = 246913578024691357802469135780246913564
m2 = 370370367037037036703703703670370370353
assert m2 - m1 == m1 - m0
flag = hex(m2 - m1)[2:]
print("flag{" + flag[:8] + "-" + flag[8:12] + "-" + flag[12:16] + "-" + flag[16:20] + "-" + flag[20:] + "}")
# flag{5ce0e9a5-6015-fec5-aadf-a328ae398115}

PS#

笑的，送两道题，一道对脑电波的场景题，难评。

鹏城杯 2025 WriteUp
https://q1uju.cc/posts/5-pcb2025/
Author
Q1uJu
Published at
2025-12-17
License
CC BY-NC-SA 4.0

Some information may be outdated

PolarCTF网络安全2025冬季个人挑战赛 WriteUp
© 2025 Q1uJu. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 7.6