太坐牢了，照着n1的wp复现一下
yet another MT game
题目：
import os
from sage.all import set_random_seed, random_matrix, Zmod
import signal
FLAG = os.environ.get("FLAG", "RCTF{fake_flag}")
MACHINE_LIMIT = 19937
secret = os.urandom(64)
set_random_seed(int.from_bytes(secret, 'big'))
def random_machine(mod: int, nrow: int, ncol: int) -> bytes:
outs = (random_matrix(Zmod(mod), nrow, ncol).list())
print("🤖 Machine output:", outs)
print("✨ Yet Another Mersenne Twister Game ✨")
print("🤔 Sagemath is just an extension of python, right?")
signal.alarm(60)
mod, nrow, ncol = map(int, input("✨ Enter mod and dimension (space separated): ").split())
if not(mod > 1 and nrow > 0 and ncol > 0):
print("❌ Invalid input!")
exit()
nbits = (mod - 1).bit_length()
leaked = nbits * nrow * ncol
if leaked > MACHINE_LIMIT:
print("💥 The machine has broken down due to too much randomness being extracted!")
exit()
random_machine(mod, nrow, ncol)
guess = bytes.fromhex(input("🤔 secret (hex): ").strip())
if guess == secret:
print(f"🎉 Correct! Here is your flag: {FLAG}")
题目很明显是通过random_matrix来预测随机数并倒退回seed，下面是gpt生成的调用图
random_matrix(Zmod(mod))
|
v
MatrixSpace (检查 mod 大小)
|
+---+-------------------------+
| |
[mod < Limit] [mod > Limit]
| |
Matrix_modn_dense_X Matrix_generic_dense
(包含 template.pxi) (继承 matrix2.pyx)
| |
v v
A.randomize() A.randomize()
| |
v v
randstate.c_random() base_ring.random_element()
| |
v v
GMP_urandomb (C Level) ZZ.random_element (Python/GMP Mixed)
| ^
| |
+----[Seed Dependency]--------+
(Python RNG 的种子来自于 GMP 的输出)
赛中的时候思路跑偏了，一直在尝试右路这条流程，之后发现是不可行的，最后再说为什么不行吧
题目调用random_matrix，来自https://github.com/sagemath/sage/blob/develop/src/sage/matrix/special.py
第214行(摘抄，...代表省略的代码)：
def random_matrix(ring, nrows, ncols=None, algorithm='randomize', implementation=None, *args, **kwds):
...
if ncols is None:
ncols = nrows
sparse = kwds.pop('sparse', False)
# Construct the parent of the desired matrix
parent = matrix_space.MatrixSpace(ring, nrows, ncols, sparse=sparse, implementation=implementation)
if algorithm == 'randomize':
density = kwds.pop('density', None)
# zero matrix is immutable, copy is mutable
A = copy(parent.zero_matrix())
if density is None:
A.randomize(density=float(1), nonzero=False, *args, **kwds)
else:
A.randomize(density=density, nonzero=True, *args, **kwds)
return A
elif algorithm == 'echelon_form':
return random_rref_matrix(parent, *args, **kwds)
elif algorithm == 'echelonizable':
return random_echelonizable_matrix(parent, *args, **kwds)
elif algorithm == 'diagonalizable':
return random_diagonalizable_matrix(parent, *args, **kwds)
elif algorithm == 'subspaces':
return random_subspaces_matrix(parent, *args, **kwds)
elif algorithm == 'unimodular':
return random_unimodular_matrix(parent, *args, **kwds)
elif algorithm == 'unitary':
return random_unitary_matrix(parent, *args, **kwds)
else:
raise ValueError('random matrix algorithm "%s" is not recognized' % algorithm)
代码中运用了matrix_space模块中的MatrixSpace类，并在这基础上使用randomize函数
找到MatrixSpace类的定义，来自https://github.com/sagemath/sage/blob/develop/src/sage/matrix/matrix_space.py
第784行(摘抄，...代表省略的代码)：
class MatrixSpace(UniqueRepresentation, Parent):
...
def __classcall__(cls, base_ring,
nrows_or_row_keys=None, ncols_or_column_keys=None,
sparse=False, implementation=None, *,
nrows=None, ncols=None,
row_keys=None, column_keys=None,
**kwds):
...
matrix_cls = get_matrix_class(base_ring, nrows, ncols, sparse, implementation)
return super().__classcall__(cls, base_ring, nrows,
ncols, sparse, matrix_cls, **kwds)
发现关键的函数get_matrix_class
第92行(摘抄，...代表省略的代码)：
def get_matrix_class(R, nrows, ncols, sparse, implementation):
...
if isinstance(R, sage.rings.abc.IntegerModRing):
try:
from . import matrix_modn_dense_double, matrix_modn_dense_float
except ImportError:
pass
else:
if R.order() < matrix_modn_dense_float.MAX_MODULUS:
return matrix_modn_dense_float.Matrix_modn_dense_float
if R.order() < matrix_modn_dense_double.MAX_MODULUS:
return matrix_modn_dense_double.Matrix_modn_dense_double
在Zmod(2)的情况下生成matrix_modn_dense_float
找到matrix_modn_dense_float
https://github.com/sagemath/sage/blob/develop/src/sage/matrix/matrix_modn_dense_float.pyx
cdef class Matrix_modn_dense_float(Matrix_modn_dense_template):
得知他继承了Matrix_modn_dense_float
https://github.com/sagemath/sage/blob/develop/src/sage/matrix/matrix_modn_dense_template.pxi
找到randomize函数
def randomize(self, density=1, nonzero=False):
...
density = float(density)
if density <= 0:
return
if density > 1:
density = float(1)
self.check_mutability()
self.clear_cache()
cdef randstate rstate = current_randstate()
cdef int nc, p = <int>self.p
cdef long pm1
if not nonzero:
# Original code, before adding the ``nonzero`` option.
if density == 1:
for i from 0 <= i < self._nrows*self._ncols:
self._entries[i] = rstate.c_random() % p
else:
nc = self._ncols
num_per_row = int(density * nc)
sig_on()
for i from 0 <= i < self._nrows:
for j from 0 <= j < num_per_row:
k = rstate.c_random() % nc
self._matrix[i][k] = rstate.c_random() % p
sig_off()
else:
# New code, to implement the ``nonzero`` option.
pm1 = p - 1
if density == 1:
for i from 0 <= i < self._nrows*self._ncols:
self._entries[i] = (rstate.c_random() % pm1) + 1
else:
nc = self._ncols
num_per_row = int(density * nc)
sig_on()
for i from 0 <= i < self._nrows:
for j from 0 <= j < num_per_row:
k = rstate.c_random() % nc
self._matrix[i][k] = (rstate.c_random() % pm1) + 1
sig_off()
注意到nonzero=false，density == 1所以所有元素都是
rstate.c_random() % p
c_random()函数
cpdef int c_random(self) noexcept:
return gmp_urandomb_ui(self.gmp_state, 31)
c_random就是获得gmp-MT19937生成的随机数的低31位
set_random_seed：
if seed:
mpz_init(mpz_seed)
mpz_set_pylong(mpz_seed, seed)
gmp_randseed(self.gmp_state, mpz_seed)
mpz_clear(mpz_seed)
gmp应用了set_random_seed里面的seed
GMP-MT19937的源码，写成python代码：
import gmpy2
WARM_UP = 2000
N = 624
M = 396
MAX_MT_POWER = 2**19937
E = 1074888996
GE = 12 # GCD(E, MAX_MT_POWER - 20023 - 1)
D = pow(E//GE, -1, MAX_MT_POWER - 20023 - 1)
def mangle_seed(seed, e=1074888996):
# GMP's mangle_seed function
# https://github.com/alisw/GMP/blob/2bbd52703e5af82509773264bfbd20ff8464804f/rand/randmts.c#L37
# Calculate (b^e) mod (2^n-k) for e=1074888996, n=19937 and k=20023,
return int(gmpy2.powmod(seed, e, MAX_MT_POWER - 20023))
def randseed_mt_state(seed: int):
seed = seed % (MAX_MT_POWER - 20027) + 2
seed = mangle_seed(seed)
mt_state = [0] * 624
for i in range(1, N):
mt_state[i] = seed & 0xFFFFFFFF
seed >>= 32
mt_state[0] = seed * 0x80000000
# mt_state[N - 1] = seed2
assert seed == 0 or seed == 1, f"Invalid case: {seed = }"
return mt_state
def randseed_gmp_mt(seed: int, warm_up= WARM_UP):
mt_state = randseed_mt_state(seed)
for i in range(warm_up//N):
mt_state = twist(mt_state)
prng = random.Random()
prng.setstate((3, tuple(mt_state + [(warm_up + 1) % N]), None))
return prng
整个过程就是
第一步：
把set_random_seed(int.from_bytes(secret, 'big'))中的secret，简单的取模
secret << 2^{19937} - 20027，所以seed1 = secret + 2
第二步：
然后将19937位放到state[0]的最高位，其余位都是0
其他19936bit从小端序每32bit一组，放入state[1]~state[623]
然后先warm up一下，就是twist3次+指针指到state[128]
使用gf2bv的MT19937，本身就twist1次了所以直接可以写成：
for i in range(2000 - 624):
rng.getrandbits(32)
这就是矩阵输出时的状态，接下来就是使用gf2bv来求解seed2，再恢复seed
exp:
import gmpy2
from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import os
secret_int = bytes_to_long(os.urandom(64))
print(secret_int)
set_random_seed(secret_int)
outs = random_matrix(Zmod(2),19937,1).list()
output = list(map(int,outs))
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = [mt[0] & 0x7FFFFFFF]
for i in range(2000 - 624):
rng.getrandbits(32)
for i in tqdm(range(len(output))):
zeros.append((rng.getrandbits(32) & 1) ^ output[i])
MOD2 = 2**19937 - 20023
d = pow(1074888996 // 12, -1, (MOD2 - 1) // 12)
for sol in lin.solve_all(zeros):
seed2 = 0
if sol[0] == 0x80000000:
seed2 += 1
for word in sol[1:][::-1]:
seed2 <<= 32
seed2 += word
seed = gmpy2.powmod(seed2, d, MOD2)
seed= gmpy2.iroot(seed, 12)
seed = seed[0] - 2
print(seed)
比赛的时候思路就跑偏了，当时发现是Zmod(2^19937)的1*1的矩阵可以直接输出getrandbits(19937)，那就可以直接进行随机数预测了，但是恢复不了seed，因为他的seed的生成代码：
rand.seed(int(ZZ.random_element(1< 128)))
cdef int den = rstate.c_random()-SAGE_RAND_MAX/2 #yet another shuffled MT game会用
mpz_urandomm(value, rstate.gmp_state, n_max.value)
发现pyrand的种子由gmp的MT生成，这里就算算出来pyrand的种子，也没有足够多的数据来恢复seed
yet another shuffled MT game
题目：
import os
from sage.all import set_random_seed, random_matrix, Zmod, ZZ, shuffle
import signal
FLAG = os.environ.get("FLAG", "RCTF{fake_flag}")
secret = os.urandom(64)
set_random_seed(int.from_bytes(secret, 'big'))
N_RUNS = 3
MACHINE_LIMIT = 16400
IS_BROKEN = False
def shuffle_int(num: int, nbits: int):
bits = ZZ(num).digits(base = 2, padto = nbits)
shuffle(bits)
return ZZ(bits, 2)
def random_machine(mod: int, nrow: int, ncol: int) -> bytes:
global IS_BROKEN
nbits = (mod - 1).bit_length()
outs = random_matrix(Zmod(mod), nrow, ncol).list()
if IS_BROKEN:
outs = [shuffle_int(x, nbits) for x in outs]
shuffle(outs)
print("🤖 Machine output:", outs)
print("✨ Yet Another Mersenne Twister Game ✨")
print("🤔 However, the random machine will break down if you extract too much randomness from it.")
leaked = 0
signal.alarm(60)
for i in range(N_RUNS):
mod, nrow, ncol = map(int, input("✨ Enter mod and dimensions (space separated): ").split())
if not(mod > 1 and nrow > 0 and ncol > 0):
break
nbits = (mod - 1).bit_length()
leaked += nbits * nrow * ncol
if leaked > MACHINE_LIMIT and IS_BROKEN == False:
IS_BROKEN = True
print("💥 The machine has broken down due to too much randomness being extracted!")
random_machine(mod, nrow, ncol)
guess = bytes.fromhex(input("🤔 secret (hex): ").strip())
if guess == secret:
print(f"🎉 Correct! Here is your flag: {FLAG}")
跟上一题比多了shuffle，shuffle调用的是pyrand，这道题有三次交互机会，第一次来得到pyrand的种子，第二次输入，并且逆向 shuffle，之后就跟上一题一样了
第一步：恢复pyrand的种子
由于题目只给了16400bit，使用python_random_breaker恢复seed
测试：
from CTF_Library.Cryptography.MersenneTwister import python_random_breaker
import random
def crackme(outputs):
breaker = python_random_breaker()
bit_len = 128
is_exact = 1
indices = [i for i in
breaker.get_required_output_indices_for_integer_seed_recovery(bit_len,
is_exact)]
cur_outputs = [outputs[i] for i in indices]
print(cur_outputs)
return (breaker.recover_all_integer_seeds_from_few_outputs(bit_len,cur_outputs, True))
if __name__ == "__main__":
seed = random.getrandbits(128)
rng = random.Random(seed)
outputs = [rng.getrandbits(32) for i in range(300)]
print(seed)
print(crackme(outputs))
恢复出pyrand的seed后就直接恢复output，之后的做法就跟上一题一样了，但是需要注意生成pyrand的种子调用的gmp的MT
cdef int den = rstate.c_random()-SAGE_RAND_MAX/2 #yet another shuffled MT game会用
mpz_urandomm(value, rstate.gmp_state, n_max.value)
用了第一步32bit+第二步128bit
exp：
import gmpy2
from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import os
from CTF_Library.Cryptography.MersenneTwister import python_random_breaker
import random
def crackme(outputs):
breaker = python_random_breaker()
bit_len = 128
is_exact = 1
indices = [i for i in
breaker.get_required_output_indices_for_integer_seed_recovery(bit_len,
is_exact)]
cur_outputs = [outputs[i] for i in indices]
# print(cur_outputs)
return (breaker.recover_all_integer_seeds_from_few_outputs(bit_len,cur_outputs, True))
def shuffle_int(num: int, nbits: int):
bits = ZZ(num).digits(base = 2, padto = nbits)
shuffle(bits)
return ZZ(bits, 2)
secret_int = bytes_to_long(os.urandom(64))
print(secret_int)
set_random_seed(secret_int)
outs = random_matrix(Zmod(2**32-2),1,300).list()
outs = [int(x) for x in outs]
seed = crackme(outs)[0]
r = random.Random(seed)
for i in range(300):
assert r.getrandbits(32) == outs[i]
print(f"[+] {seed = }")
outs = random_matrix(Zmod(2), 1, 20000).list()
outs1 = [shuffle_int(x, 1) for x in outs]
shuffle(outs1)
output = list(map(int,outs1))
n = 20000
indices = list(range(n))
r.shuffle(indices)
real_output = [None for i in range(n)]
for i in range(n):
real_output[indices[i]] = output[i]
output = real_output
assert output == outs
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = [mt[0] & 0x7FFFFFFF]
for i in range(2000 - 624):
rng.getrandbits(32)
rng.getrandbits(128)
rng.getrandbits(32)
for i in tqdm(range(len(output))):
zeros.append((rng.getrandbits(32) & 1) ^ output[i])
MOD2 = 2**19937 - 20023
d = pow(1074888996 // 12, -1, (MOD2 - 1) // 12)
for sol in lin.solve_all(zeros):
seed2 = 0
if sol[0] == 0x80000000:
seed2 += 1
for word in sol[1:][::-1]:
seed2 <<= 32
seed2 += word
seed = gmpy2.powmod(seed2, d, MOD2)
seed= gmpy2.iroot(seed, 12)
seed = seed[0] - 2
print(seed)
f, l and ag++
题目：
from Crypto.Util.number import getPrime, GCD, bytes_to_long
from secrets import token_bytes
import os
import signal
RCTF_FLAG = os.environ.get("FLAG", "RCTF{fake_flag}")
while True:
p = getPrime(1024)
q = getPrime(1024)
e = 0x101
if GCD((p - 1) * (q - 1), e) == 1:
break
N = p * q
flag = token_bytes(68)
assert len(flag) == 68
f, l, ag = flag[:17], flag[17:34], flag[34:]
f, l, ag, flag = map(bytes_to_long, (f, l, ag, flag))
f_enc = pow(f, e, N)
l_enc = pow(l, e, N)
ag_enc = pow(ag, e, N)
flag_enc = pow(flag, e, N)
print(f"{N = }")
print(f"{e = }")
print(f"{f_enc = }")
print(f"{l_enc = }")
print(f"{ag_enc = }")
print(f"{flag_enc = }")
signal.alarm(10)
guess = bytes.fromhex(input("🤔 flag: ").strip()).decode()
if guess == hex(flag)[2:]:
print(f"🎉 Correct! Here is your RCTF flag: {RCTF_FLAG}")
首先，我们要明白题目里的 flag 是怎么构成的。
这里 是字节的基数。
- : 高 17 字节
- : 中 17 字节
- : 低 34 字节
我们已知 。
消除一个未知数
F.<x> = Zmod(N, is_field=True)[]
l2, ag2, flag2 = [F(z) / f_enc for z in [l_enc, ag_enc, flag_enc]]
原理：
目前的方程里有 三个未知数，太复杂了。
因为 RSA 是乘法同态的（在模 下），我们可以把所有东西都除以 （即 ）。
令新的未知变量：
那么原本的加密值就变成了比值的加密值：
l2ag2flag2
@parallel(ncpus=20)
def get_resultant(i):
# i 是我们猜测的一个中间变量 W
# W = S^17 + l/f
# 方程 B: 来源于 ag^e
# 也就是 (ag/f)^e - ag2 = 0
# 在这里 x 代表 ag/f (即变量 Y)
B = x ^ e - ag2
# 方程 A: 来源于 flag^e
# flag/f = S^34 * (S^17 + l/f) + ag/f
# 令 guess = i (代表 S^17 + l/f)
# 则 (x + S^34 * i)^e - flag2 = 0
# "- B" 是为了消去 x^e 项，降低多项式次数，加速计算
A = (x + 256 ^ 34 * i) ^ e - flag2 - B
# 计算 Resultant(A, B) 的值
# 使用欧几里得辗转相除法
t = 1
while A.degree():
t *= B.lc()
A, B = B, A % B
# 返回采样点
# x坐标: i^e (因为结式多项式是关于 i^e 的函数)
# y坐标: 计算出的结式值 (t^2 是为了消除正负号影响)
return F(i) ^ e, t ^ 2 * A[0] ^ B.degree()
原理：
我们设未知数 。我们想求出一个关于 的多项式 ，使得 。
这个多项式 本质上是消去了 后的约束方程。
直接算 的符号表达式太难了（次数高达 257）。
所以，我们假装 等于
把这些数字代进去，算出对应的 的数值
这些数值就是上面的代码算出来的 return 值。
这一步结束后，我们得到了一堆点坐标：
这里的横坐标都是是因为任何类似于：
都可以写成：
它实际上不仅仅是关于 的多项式，它实际上是关于 的多项式
这些项的系数统统是 0
如果我们用上述 作为横坐标
那么那个稀疏的多项式 就变成了一个紧凑的多项式 ：
这个 的次数非常低（只有 甚至更低
这样我们用这些点做插值就能极大的提升了速度
然后就是插值，把原@Neobeo的脚本做了这么一点修改，使用ProductTree插值，再优化一点
xs = [item[0] for item in arr]
ys = [item[1] for item in arr]
poly = ProductTree([x - xi for xi in xs]).interpolation(ys)
expanded_poly = F([j for i in poly for j in [i] + [0] * (e - 1)])
然后就是gcd
l, f = rational_reconstruction(r - 256 ^ 17, N).as_integer_ratio()
这一步当l和f mod N下是小值时，可以直接得到的分子和分母
这道题相比于Dreamhack Invitational 2024 的 f, l and ag，只多了时间限制，所以我直接用了那道题的数据
exp：
from sage.rings.generic import ProductTree
N = 13598153154833637656818517220292744946788560583202271669901644497177188925057767594849738947760162557359993013941391365772760007445899524368318435830676981817869673331870320737330775671648984463969468621798675109684957542627082360473783145645163195229452107363085083258061770951116708326158577900955824955580368937846998203862237667423531218641802533914520455768252943768258927701410136655514715642813622386907691909497053923779237421603983819718385274631056656164913952692683677249557675196144295524011209128894457571141496385889368393134706462736219400077160407228213790054598648594900234976787858245149588928960833
e = 257
f_enc = 73030397489099035279319855876886070810220785465128177783721084297465432817625336278147155884719651609504955461626696472226952698687233692421868683109668418808721348267656762914374932598845711762635302313777700950638040111032350897518341089453486878658752043973075172018407361437099018715978298553803310145104409716664859214032127299409390714013989919916925043280767966542091117410879060785455668156731917964298043856173226330939889557079289189362452492120327774680559927819819318320757393827478407474666372553788179255657267753672542551199879923864602793613493560797273359691934240752456707850607374109729242957842
l_enc = 6825921200349018807592335703838432756553045344446552588201212894686478236555882317769002755040398386112516580071466306416980142838663872816104291019190292985262727159441917005019446973370290161687441469000543372114223121684652244269880489000376504530684131188689017789471615206507470670355039250137661131451746230811543561823505247817951434369253704777477653801136551022141872820041695930382231777466427220328067948143423045759378273927189539190771224135246712538904597020537140232746518680426526607221858502476407003978155063780019151756163019505238511043244276199463778365406677436273087709538658354614028117605582
ag_enc = 13405734267473132964260648663662344691844124982067327807881447856906250215686955458840289075308599292884212579562070237306595813776114395770150100351698547278532462839559854176530380866034504401927460008482371273242234325195162560776433353563575265714310904078717547709421045819664460331652434824032359065910161206241508170553957699730174000953561319613897164604349886114030816663906511303410418434744417978755078997530231897836134105477564039394202236695430108076055265480289187871498243928056441475859991691886765082969555596956305613394840885959746799424044011106435318927874502200386083084292536310499299783132802
flag_enc = 3056721804126947156716832420271562440267433769620752944594737373742274947913485305137112373038501559035048723290582397238429559201578142286878226849109459842475726175229206479884282120253887765565064942559084499366369714492364454013309271233067776222260569521165957785067838323358689331121321008119215549159710593434825687954850384499195220170098401040423113540443602023460964321711666489448380410860143657566323543041994634505475840126749840054856691763832258809835642024521361484290659719157960232861905750980614338555945530164284419245959143626705465690336586407187101019404335441902329298015796866670034526063722
F.<x> = Zmod(N, is_field=True)[]
l2, ag2, flag2 = [F(z) / f_enc for z in [l_enc, ag_enc, flag_enc]]
print(ag2)
################################################################################ Fast resultant calculation
@parallel(ncpus=20)
def get_resultant(i):
B = x ^ e - ag2
A = (x + 256 ^ 34 * i) ^ e - flag2 - B
t = 1
while A.degree():
t *= B.lc()
A, B = B, A % B
return F(i) ^ e, t ^ 2 * A[0] ^ B.degree()
arr = [a for _, a in get_resultant([0..e])]
print('Finished calculating resultants')
print(arr)
################################################################################ Fast lagrange interpolation
xs = [item[0] for item in arr]
ys = [item[1] for item in arr]
poly = ProductTree([x - xi for xi in xs]).interpolation(ys)
expanded_poly = F([j for i in poly for j in [i] + [0] * (e - 1)])
################################################################################ Calculate everything else to get flag
r = -gcd(expanded_poly, (x - 256 ^ 17) ^ e - l2)[0]
s = -gcd(x ^ e - ag2, (x + 256 ^ 34 * r) ^ e - flag2)[0]
l, f = rational_reconstruction(r - 256 ^ 17, N).as_integer_ratio()
ag = ZZ(f * s)
print(b''.join(int(z).to_bytes(z.nbits() // 8 + 1, 'big') for z in [f, l, ag]))