Swizzer's Sound

Back
14 min read
ctf /
crypto /
rsa /
因数分解 /
流密码 /
xoshiro256**

切题 2025.06

刷题是做题家的必备技能

手痒挑点题做做，顺便为今年的CryptoCTF做点准备。

AlpacaHack Round 3 - Rainbow Sweet Alchemist#

task.py
import os
import random
from math import prod
from Crypto.Util.number import isPrime, bytes_to_long

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

# This is not likely to fail
assert deterministicGetPrime() == 2710959347947821323, "Your Python's random module is not compatible with this challenge."

def getPrime(bit):
  factors = [deterministicGetPrime() for _ in range(bit // 64)]
  while True:
    p = 2 * prod(factors) + 1
    if isPrime(p):
      return p
    factors.remove(random.choice(factors))
    factors.append(deterministicGetPrime())

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 0x10001
c = pow(m, e, n)

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

素数是拿一堆64 bits的deterministicPrime再加上一些随机的prime去生成的。这个素数生成方式一看就会觉得比较像光滑数那套东西，并且p-1的因子是通过deterministicGetPrime()生成的，所以直接拿它的方式生成deterministicPrime然后拿去pollard p-1就好了。

本地生成数据测试一下:

n=160836544037910609005780702840165144068490234071854739366259912370392021076162916908702610103919348574435852754290816429580095072837120435975860749774167077491150887237325177752814819594099069509673116704614282426710640390809184105755337634828025495668016233827749767515861968807361207644166645232738546335987072305559426271004929819939657344282341216361231946634442046776703779492052787601546596196615984327207554025268885162611428039402102968138061378958552034317041644642199476417863048058175952288091064095980612330416790623259640251348133728428585845944609236301175564125437779808581385619776495153
e=65537
c=118707624155875859009358958766331195664386597352681752983738108218395299110736747069989506131216691251322359417233027264547530843040314710981659802130681627977793468801786294244641830546848712365256323684323873286345491561980129378805654203629862398466381689583050212391463467895889393150259213417246822075653572977971738913147466928929696260238201706327097882191399023863349288842190379528694171322417557695844727901469288657315762970276151355204666133947517888145117922624608766623891093435209969564448590959028819595013869821164200043020655201774161682008634247207294514649792778252870547275362679891
txt
exp.py
n=160836544037910609005780702840165144068490234071854739366259912370392021076162916908702610103919348574435852754290816429580095072837120435975860749774167077491150887237325177752814819594099069509673116704614282426710640390809184105755337634828025495668016233827749767515861968807361207644166645232738546335987072305559426271004929819939657344282341216361231946634442046776703779492052787601546596196615984327207554025268885162611428039402102968138061378958552034317041644642199476417863048058175952288091064095980612330416790623259640251348133728428585845944609236301175564125437779808581385619776495153
e=65537
c=118707624155875859009358958766331195664386597352681752983738108218395299110736747069989506131216691251322359417233027264547530843040314710981659802130681627977793468801786294244641830546848712365256323684323873286345491561980129378805654203629862398466381689583050212391463467895889393150259213417246822075653572977971738913147466928929696260238201706327097882191399023863349288842190379528694171322417557695844727901469288657315762970276151355204666133947517888145117922624608766623891093435209969564448590959028819595013869821164200043020655201774161682008634247207294514649792778252870547275362679891
import os
import random
from math import prod
from Crypto.Util.number import isPrime, long_to_bytes, inverse
import gmpy2
r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p
def pollard(n) -> tuple:
    a = 65536
    while True:
        a = gmpy2.powmod(a, deterministicGetPrime(), n)
        p = gmpy2.gcd(a - 1, n)
        if p != 1 and p != n and p * (n // p) == n:
            return p, n//p
p, q = pollard(n)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = gmpy2.powmod(c, d, n)
flag = long_to_bytes(m)
print(flag)
# fakeflag
python

成功🥳

AlpacaHack Round 3 - qrime#

task.py
import os
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger, isPrime

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

def gen():
    while True:
        q = getRandomNBitInteger(256)
        r = getRandomNBitInteger(256)
        p = q * nextPrime(r) + nextPrime(q) * r
        if isPrime(p) and isPrime(q):
            return p, q, r

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q, r = gen()
n = p * q

phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
c = pow(m, e, n)

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

这题的p,q满足

n=pqp=q(r+x1)+(q+x2)rn = pq \\ p = q(r+x_1)+(q+x_2)r

其中 x1x_1 和 x2x_2 都比较小，然后额外给了 rr ，目标就是利用 rr 去分解 nn 。

见到这种关系第一反应就是考虑  mod  r\bmod \ r 下的性质，那么有 p≡qx1(modr)⇒n≡q2x1(modr)p\equiv qx_1 \pmod{r} \Rightarrow n\equiv q^2x_1 \pmod{r}

如果 x1x_1 在 (modr)\pmod{r} 下有逆，也就是 gcd(x1,r)=1gcd(x_1, r)=1 ，那么爆破 x1x_1 后对 nx1−1nx_1^{-1} 开根后就能拿到 qq ；如果 rr 是素数，那么就能让 gcd(x1,r)=1gcd(x_1, r)=1 对于所有小于 rr 的数成立。问题在于，原题是静态的，没办法通过反复重连使得 rr 为素数🤔

当然就算r不是素数我们也能在r的素因子 rkr_k 里去尝试求q，那样求出的q无非是 (modrk)\pmod{r_k} 而已，然后Coppersmith也不是不行，这题的数据范围也刚好可以Copper(rmaxr_{max} 有186bits，q只有256bits)。

exp.py
n = 200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e = 65537
c = 77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r = 30736331670163278077316573297195977299089049174626053101058657011068283335270
from tqdm import trange
from Crypto.Util.number import inverse, long_to_bytes
proof.all(False)
r_max = factor(r)[-1][0]
F = GF(r_max)
for x_cand in trange(1,2000):
    tmp = Zmod(r // gcd(r, x_cand))(n) / x_cand
    if not tmp.is_square():
        continue
    q_r = ZZ(F(tmp).sqrt())
    x = polygen(Zmod(n))
    f = (r_max * x + q_r).monic()
    try:
        res = f.small_roots(X=2**256 // r_max, beta=0.33, epsilon=0.015)[0]
        q = gcd(n, ZZ(f(res)))
        if q != 1 and q != n:
            p = n // q
            assert p * q == n
            break
    except:
        continue
phi = (p-1) * (q-1)
d = inverse(e, phi)
flag = long_to_bytes(pow(c, d, n))
print(flag)
#   9%|███████████▏                                                                                                                 | 178/1999 [00:00<00:08, 216.54it/s]
# b'Alpaca{q_and_r_have_nothing_to_do_with_QR_code}'
python

2024 DASCTF 暑期挑战赛 - 1z_RSA#

task.py
from Crypto.Util.number import *
from sympy import *
import os
from secrets import flag

nbit =130
e = 65537
l = getPrime(505)
m = bytes_to_long(flag + os.urandom(64))

assert len(flag) == 29

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PQ = int(str(p<<120)+str(q))
    QP = int(str(q<<120)+str(p))
    if isPrime(PQ) and isPrime(QP):
        break

n = PQ * QP
PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
M = pow(m,1,l)
c = pow(m,e,N)

print('n =', n)
print('c =', c)
# n = 16445702053284878471661149821929236160827349860248398845138927737656956155376460402218197208193336565070826064696649172229472596804167403573551471681598293095327847455986697781130763893067438016088641806277728646579590680432425469
# c = 887267289769222134322645658185740890076570973814978825206856442917869951183407787099985715495254579291183691081385458063887609704126682101105986126757195338464870470784104063964312361198792751675180153036987799155562165373093688
python

这题的数据中，N由n的因子决定，得想办法分解n=PQ*QP。

PQ和QP的生成方式是这样的:

p, q = getPrime(130), getPrime(130)
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
python

看起来 PQ=212010xp+q,QP=212010yq+pPQ = 2^{120}10^{x}p+q, QP = 2^{120}10^{y}q+p

测一下：

looooooog

那么x和y的取值范围就是39或40。二元Copper走起

copper.py
def small_roots(f, bounds, m, d=None):
    if not d:
        d = f.degree()
 
    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
 
    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
 
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
 
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
 
    B = B.dense_matrix().LLL()
 
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
 
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []
from Crypto.Util.number import *
import itertools
n = 16445702053284878471661149821929236160827349860248398845138927737656956155376460402218197208193336565070826064696649172229472596804167403573551471681598293095327847455986697781130763893067438016088641806277728646579590680432425469
c = 887267289769222134322645658185740890076570973814978825206856442917869951183407787099985715495254579291183691081385458063887609704126682101105986126757195338464870470784104063964312361198792751675180153036987799155562165373093688
PR = PolynomialRing(Zmod(n), "p, q")
p, q = PR.gens()
f = (2**120*10**39*(2*p+1)+(2*q+1))*(2**120*10**40*(2*q+1)+(2*p+1))
bounds = (2**130, 2**130)
print(small_roots(f, bounds, m=2, d=4))
# [(590352663997702178900249614724312559588, 394168522856050219618619947492543239498), (16445702053284878471661149821929236160827349860248398845138927737656956155376460402218197208193336565070826064696649172229472596804167403573551471681598293095327847455986697781130763893067437425735977808575549746329975956119865880, 16445702053284878471661149821929236160827349860248398845138927737656956155376460402218197208193336565070826064696649172229472596804167403573551471681598293095327847455986697781130763893067437621920118950227509027959643187889185970)]
python

几秒钟就能Copper出来。

get_flag.py
from Crypto.Util.number import *
res = [(590352663997702178900249614724312559588, 394168522856050219618619947492543239498), (16445702053284878471661149821929236160827349860248398845138927737656956155376460402218197208193336565070826064696649172229472596804167403573551471681598293095327847455986697781130763893067437425735977808575549746329975956119865880, 16445702053284878471661149821929236160827349860248398845138927737656956155376460402218197208193336565070826064696649172229472596804167403573551471681598293095327847455986697781130763893067437621920118950227509027959643187889185970)]
n = 16445702053284878471661149821929236160827349860248398845138927737656956155376460402218197208193336565070826064696649172229472596804167403573551471681598293095327847455986697781130763893067438016088641806277728646579590680432425469
c = 887267289769222134322645658185740890076570973814978825206856442917869951183407787099985715495254579291183691081385458063887609704126682101105986126757195338464870470784104063964312361198792751675180153036987799155562165373093688
p,q = 2*int(res[0][1])+1,2*int(res[0][0])+1
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
PP = next_prime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = next_prime((QP >> 190) * (PQ & (2 ** 190 - 1)))
phi = (PP-1)*(QQ-1)
d = inverse(65537, phi)
print(long_to_bytes(pow(c,d,PP*QQ)))
# b'flag{dummy_flag_for_testing!}\x8b\x11dl\xfd\xd0Xe\xd0\x99\x8d\xc4?\xc3\xae\x81\x98\xdfa) >\xfd\x00\xdc\xa7?\xed\xb2\xd2\x17\x0c\t\x18\xdf\x80\xf7\xbb\xa1\x90\x00C\x89\xe2-EU\xe6\xf6;\xcf\xca<\x9fG\x0f\xcc\xb9\x0b\x0f\x825\x8f\xcd'
python

imaginaryCTF round45 - Moonjump#

enc.lua
function u(s)
    local r = 0

    for i = #s, 1, -1 do
        r = r * 256
        r = r + string.byte(string.sub(s, i, i))
    end

    return r
end

function sw(t, a, b)
    local x = t[a]
    t[a] = t[b]
    t[b] = x
end

function s(k)
    local r = {}

    for i = 0, 255 do
        r[i] = i
    end

    local j = 0
    local idx = 0

    for i = 0, 255 do
        idx = (i % #k) + 1
        j = (j + r[i] + k:sub(idx, idx):byte()) % 256
        sw(r, i, j)
    end

    return r
end

function e(p, k)
    local i = 0
    local j = 0
    local r = ""

    for l = 1, 3072 do
        i = (i + 1) % 256
        j = (j + k[i]) % 256
        sw(k, i, j)
        t = (k[i] + k[j]) % 256
    end

    for l = 1, #p do
        i = (i + 1) % 256
        j = (j + k[i]) % 256
        sw(k, i, j)
        t = (k[i] + k[j]) % 256
        r = r .. string.char(p:sub(l, l):byte() ~ k[t])
    end

    return r
end

local f = assert(io.open("moon.bmp", "r"))
local d = f:read("*all")
f:close()

local t = os.time()
math.randomseed(t)

local o = u(string.sub(d, 11, 14)) + 1
local p = string.sub(d, o, #d)

for i = 1, 1000000000000000 do
    math.random()
end

local ks = s(tostring(math.random(0, 2^32 - 1)))
local ct = e(p, ks)

f = assert(io.open("chall.bmp", "w"))
f:write(string.sub(d, 0, o - 1) .. ct .. os.date("!%d %h %Y, %H:%M", t))
f:close()
lua

使用随机数生成密钥后对位图的一部分像素做了RC4加密.给出了时间戳,随机数的种子是可以爆破的,无非就60种情况;但是PRNG的中间状态不少于1000000000000000种,直接从头输出的话,耗时是不可接受的.

通过搜索了解到Lua4.2之后内置的随机数发生器为Xoshiro256**,其提供了一个jump操作,执行一次可以跳过 21282^{128} 个状态,不过简单推演就能知道不适用于本题.

不过Xoshiro256**其实是个linear的PRNG,lua中的实现在最后输出时仅仅做了个truncate。是线性的就能算出个矩阵,这样就转化到了对矩阵做幂运算,用上快速幂之后就能在可接受时间内计算出PRNG的输出。

这里计算状态变换矩阵的方法跟鸡块的MT19937板子里的方式几乎一致，取一个只有一个分量为1的vector去乘就能获得矩阵的一行/一列。

solve.sage
# sage
from Crypto.Cipher import ARC4
from datetime import datetime

def rotl(x, n, nbits=64):
    return ((x << n) % (2**nbits)) | (x >> (64 - n))


class LuaXoshiro:
    def __init__(self, seed=0):
        self.seed(seed)

    def seed(self, seed):
        self.state = [seed, 0xff, 0, 0]

    def raw_seed(self, state):
        self.state = [state >> 192, (state >> 128) % (2**64), (state >> 64) % (2**64), state % (2**64)]

    def next(self):
        [s0, s1, s2, s3] = self.state
        s2 ^^= s0
        s3 ^^= s1
        res = rotl((s1 * 5) % (2**64), 7) * 9 % (2**64)
        self.state[0] = s0 ^^ s3
        self.state[1] = s1 ^^ s2
        self.state[2] = s2 ^^ ((s1 << 17) % (2**64))
        self.state[3] = rotl(s3, 45)
        return res

    def raw_state(self):
        [s0, s1, s2, s3] = self.state
        return (s0 << 192) + (s1 << 128) + (s2 << 64) + s3

    def next_state(self):
        self.next()
        return self.raw_state()


def n_to_bit_list(n, nbits=256):
    F = GF(2)
    result = [None for _ in range(nbits)]
    for i in range(nbits):
        result[i] = F((n >> (nbits - i - 1)) % 2)
    return result

def bit_list_to_n(bl):
    result = 0
    for b in bl:
        result *= 2
        result += int(b)
    return result


def transition_matrix(engine, nbits=256):
    state = engine.state
    columns = []
    # calculate the standard matrix
    for i in range(nbits):
        seed = 1 << (nbits - i - 1)
        engine.raw_seed(seed)
        columns.append(n_to_bit_list(engine.next_state()))

    engine.state = state
    return matrix(GF(2), columns).transpose()


def jump(engine, num_steps, mat=None):
    if mat is None:
        mat = transition_matrix(engine)

    state = engine.raw_state()
    v = vector(n_to_bit_list(state))
    v2 = mat^num_steps * v
    newstate = bit_list_to_n(v2)
    engine.raw_seed(newstate)


def lua_nth_random(e, n, mat=None):
    # lua advances the state 16 times after setting the seed in math.randomseed
    jump(e, n + 16, mat)
    return e.next() & (2**32 - 1)


def solve():
    with open('chall.bmp', 'rb') as f:
        data = f.read()
    header = data[:0x8a]
    enc = data[0x8a:]
    dt = datetime.strptime('31 Jan 2020, 20:38 +0000', '%d %b %Y, %H:%M %z')
    e = LuaXoshiro()
    mat = transition_matrix(e)
    for i in range(60):
        seed = int(dt.timestamp() + i)
        e.seed(seed)
        key = str(lua_nth_random(e, 1_000_000_000_000_000)).encode()
        cipher = ARC4.new(key, drop=3072)
        dec = cipher.decrypt(enc)
        with open(f'decrypted/{i:02}.bmp', 'wb') as f:
            f.write(header + dec)


if __name__ == '__main__':
    solve()

# ictf{xoshiro_jumps_in_lua_like_a_pro}
python

MaltaCTF 2025 Quals - grammar nazi#

虽然报名了这个比赛但是当天在逛漫展而没打😖 下来看了看题感觉难度还行

chall.py
from Crypto.Util.number import *

FLAG = 'maltactf{???????????????????????????????}'
assert len(FLAG) == 41

p = getPrime(128)
q = getPrime(128)
N = p * q
e = 65537

m = f'The flag is {FLAG}'
c = pow(bytes_to_long(m.encode()), e, N)

# ERROR: Sentences should end with a period.
m += '.'
c += pow(bytes_to_long(m.encode()), e, N)

# All good now!
print(f'{N = }')
print(f'{c = }')

'''
N = 83839453754784827797201083929300181050320503279359875805303608931874182224243
c = 32104483815246305654072935180480116143927362174667948848821645940823281560338
'''
python

记最初的m为 xx , 那么题目给出的其实就是

c=xe+(256x+46)e(modN)c = x^e+(256x+46)^e \pmod{N}

记 f=xe+(256x+46)e−c(modN)f = x^e+(256x+46)^e-c \pmod{N}。因为p,q都很小，所以N可以分解，那么f就能放到模p和模q下分别求根，然后CRT回去就行。不过因为指数太大了，所以可以仿照CryptoCTF 2024 - Duzly那题的做法，注意到模p下的多项式 g=xp−1−1g = x^{p-1}-1 以 Fp\mathbb{F}_p中任一元素为根，把g和f做个GCD就能降次求根了。

总之先分解N:

ebbebb37a3c0a99529bbc6c80652c679.png

p = 276784813000398431755706235529589161781 q = 302904819256337380397575865141537456903

因为g的指数超出了Sagemath默认能处理的多项式指数上限，所以需要在模f下处理。之前我是通过把g lift到商环上搞定的，这次从maple佬那里学到了可以直接pow()去计算。

最后因为flag长度大于N所以求出来的东西是模N后的，还需要再处理一下，这部分的code就直接用maple的了。

solve.py
from shared.polynomial import fast_polynomial_gcd # https://github.com/jvdsn/crypto-attacks
from sage.all import *
N = 83839453754784827797201083929300181050320503279359875805303608931874182224243
c = 32104483815246305654072935180480116143927362174667948848821645940823281560338
p = 276784813000398431755706235529589161781
q = 302904819256337380397575865141537456903
e = 65537
def cal_roots(p):
	PR = PolynomialRing(GF(p), 'x')
	x = PR.gen()
	f = x**e+(256*x+46)**e - c
	# g = x**(p-1) - 1
	g = pow(x, p-1, f) - 1
	h = fast_polynomial_gcd(f, g)
	print("[+] Starting to calculate roots...")
	roots = [int(res) for res, _ in h.roots()]
	print("[+] Roots calculated.")
	return roots
roots_p = cal_roots(p)
roots_q = cal_roots(q)

# The following codes were copied from https://blog.maple3142.net/2025/06/22/maltactf-2025-quals-writeups/#grammar-nazi
tmpl = int.from_bytes(
    b"The flag is maltactf{???????????????????????????????}".replace(b"?", b"\x00"),
    "big",
)
for rp in roots_p:
    for rq in roots_q:
        r = crt([rp, rq], [p, q])
        f = (r - tmpl) / 256 % N
        flag = int(f).to_bytes(41, "big").strip(b"\x00")
        if flag.isascii():
            print(flag)
python

maple的blog还提到pari.polrootsmod比Sage自带的f.roots()快上不少，过几天试试看。

切题 2025.06
https://blog.swizzer.cc/blog/%E5%88%87%E9%A2%98-202506
Author Swizzer
Published at June 27, 2025
Copyright CC BY-NC-SA 4.0

2025 GoogleCTF

live functional