出了两道题，写个题解
subgroup_dlp
题目：
from Crypto.Util.number import *
flag = b'UniCTF{???}'
m = bytes_to_long(flag)
n = 20416580311348568104958456290409800602076453150746674606637172527592736894552749500299570715851384304673805100612931000268540860237227126141075427447627491168
print(pow(7,m,n))
# c = 8195229101228793312160531614487746122056220479081491148455134171051226604632289610379779462628287749120056961207013231802759766535835599450864667728106141697
分解n:
2**5 * 3**2 * 10711086940911733573 * 188455199626845780197**3 * 988854958862525695246052320176260067587096611000882853771819829938377275059
#找出几个大数，之后crt
k = [(10711086940911733573,1),(188455199626845780197,3),(988854958862525695246052320176260067587096611000882853771819829938377275059,1)]
然后发现光滑的，使用来解，发现位数应该不太够解出flag，再观察到
使用p-adic，发现还是解不出flag，尝试爆破几位
exp：
from Crypto.Util.number import *
from sage.all import *
c = 8195229101228793312160531614487746122056220479081491148455134171051226604632289610379779462628287749120056961207013231802759766535835599450864667728106141697
k = [(10711086940911733573,1),(188455199626845780197,3),(988854958862525695246052320176260067587096611000882853771819829938377275059,1)]
ps = []
ord_p = []
for p,exp in k:
Fp = GF(p)
ord = discrete_log(Fp(c), Fp(7))
g = Fp(7)
order = g.multiplicative_order()
ps.append(order)
ord_p.append(ord)
if exp != 1:
R = Zp(p, prec=exp)
xa1 = (R(c).log() / R(7).log()).lift()
ps.append(p**2)
ord_p.append(xa1)
x = crt(ord_p, ps)
l = 1
for i in ps:
l = lcm(l,i)
for i in range(2**10):
x = x + i * l
flag = long_to_bytes(x)
# print(x.bit_length())
if b'UniCTF{' in flag:
print(x.bit_length())
print(flag)
subgroup_MT19937
题目：
import os
import random
import sys
import signal
def banner():
print(r"""
_ _ _ _____ _____ ______
| | | | (_) / ____|_ _| ____|
| | | |_ __ _ | | | | | |__
| | | | '_ \| | | | | | __|
| |__| | | | | | |____ | | | |
\____/|_| |_|_|\_____| |_| |_|
""")
print("Welcome to the UniCTF Random Challenge!")
print("-" * 50)
if __name__ == "__main__":
banner()
signal.alarm(60)
FLAG = os.environ.get("FLAG", "UniCTF{fake_flag}")
secret = os.urandom(32)
rng = random.Random(int.from_bytes(secret, 'big'))
outputs = [rng.getrandbits(b'\x1e\x40\x20'[i % 3]) for i in range(300)]
print(outputs)
try:
guess_hex = input("secret (hex): ").strip()
guess = bytes.fromhex(guess_hex)
if guess == secret:
print(f"Correct! Here is your flag: {FLAG}")
else:
print("Wrong secret!")
except Exception:
print("Invalid input format.")
发现只需要知道第0~11和227~238的32bit数，就可以计算出256bit的seed
需要把题目的64bit数拆开，再爆破6个30bit数就可以恢复
from CTF_Library.Cryptography.MersenneTwister import python_random_breaker
import random
import itertools
from sage.all import *
outputs = [633719237, 17296393461392712884, 2729402561, 1006435218, 5347906016802498750, 2641289731, 394521109, 16202623786516081725, 2887450454, 673432407, 17415531378123973366, 2906722483, 891362026, 12484157007105072866, 1372488110, 516169017, 12956460107060697145, 1128880427, 872720724, 13912728298091190551, 2141671640, 296444257, 16224793223236281263, 1416730702, 253987892, 15935047531832532695, 616368744, 821800863, 12045004794188751259, 3284660692, 426322313, 8001205610301432203, 4238558347, 568005430, 8143449657523815442, 1527987078, 197119842, 9948489878708074340, 2111615399, 739262478, 4493631307275911140, 1580337225, 255569151, 700930075796908951, 1032827877, 734314292, 2854593844568283873, 1522900360, 1030392917, 9067645866040684255, 2176329521, 1026738863, 6972618127397136068, 3916007126, 410764592, 658826913645191387, 2743545699, 500848189, 10810124185328811093, 1404236960, 40209274, 6416426844776513095, 3078096649, 703459769, 17164536364426758098, 4181897428, 37617524, 10123855627096251347, 3888666691, 472500916, 7893086491803196558, 1011311897, 357000692, 17089727905092255433, 170510248, 281838271, 968170269780363365, 3793259149, 124812063, 18123618883690308513, 3532442270, 455883883, 12366758603478883228, 896195186, 628421822, 17910311011476667596, 2739288845, 441493564, 15255370896906042429, 2472227046, 143801173, 17406315013171843034, 2720395771, 574436257, 10885897595543621623, 4230165172, 486885472, 5964180114425579510, 1815760698, 417262730, 14733347761553835307, 368608880, 1022217081, 13084067580690423234, 443684071, 623864229, 17171633783559226381, 398003671, 960292740, 9838081004631111094, 799045152, 916066798, 6912210281985595727, 1356391431, 974341415, 3429250774430951727, 3757470168, 721550581, 6167668531916928184, 54813224, 684389822, 1673599056568894870, 148586836, 527572276, 6988164039473797066, 2333712799, 697906207, 10997398800107404425, 4051152123, 656498563, 6229920532557186563, 757520223, 126587282, 2130732191724278203, 1099275741, 562325288, 9236801444070492525, 84615396, 25237295, 6450144121009487113, 298083311, 129137157, 4835452009781596645, 350490516, 471782331, 8129018340462939935, 3038916495, 256078018, 10299727196482069401, 3220723483, 781990709, 14424889126162099049, 3734415865, 422665510, 5723106157102173513, 529224802, 740438310, 9728186614110852957, 2210219269, 657182704, 14303734426856382447, 2754582841, 415352084, 6263649792854771423, 1082515466, 175963561, 467790002319747792, 4078990457, 862322342, 2987756291596558235, 1510928128, 957124997, 8534006470781249966, 1161920404, 628354052, 14833009669652972593, 2930459999, 945153110, 635825472977599221, 2520365142, 82359455, 8751900292623772976, 1166627489, 929845396, 5772425661060145018, 2566782242, 276555308, 10852977495743176283, 2879058831, 870031241, 16285896413505086860, 3400676906, 408625992, 3411199607692163971, 1020473011, 267875032, 15005095254613066133, 1316767254, 712603851, 9565433420331412112, 3860276591, 260680761, 11696102672719554931, 3300750690, 280360826, 10336048491927755147, 1185581489, 219336017, 14770059841548187168, 475209665, 202879498, 12014349870830300301, 3073695382, 442055773, 12655431302460212273, 3113638573, 946392948, 15321296423105853716, 3698491480, 111377720, 14989836291198904400, 612296926, 785310491, 647871534906908661, 3237451540, 473225450, 476785664918644069, 3389603082, 678412312, 14785655390887782002, 3159388100, 168687451, 4706495674140600526, 1425078263, 859954141, 1262321884757354438, 4123667128, 261089284, 1211771828572743190, 309762122, 839396734, 2955828442841315678, 4220099220, 190345632, 8222489847472310641, 2099738441, 439856259, 5758107464694755011, 3765680070, 294344404, 11664087582740181286, 1042907723, 320513525, 4173577738810232032, 3756803817, 18991625, 382826592851942064, 2237482919, 1001544296, 13661440468681331232, 2305698394, 1052539865, 11652968721980320061, 1103630788, 773175711, 10965071586645626186, 464245208, 456365285, 14203416326251218575, 2681724777, 22999419, 16485858857930265903, 2210984322, 384628663, 8819416352381864194, 4176644600, 436575568, 6696663884410632999, 173295634, 775039969, 15899413532923623153, 2840547084, 44784865, 5670011457670110268, 2227379515, 366802853, 18368396958485442855, 3412152652, 787023667, 5250335085064884410, 1761564219, 556776833, 4650150264035861883, 251067849, 884930863, 16356307450320543427, 3750682736, 738689267, 3319418910075602867, 598358016]
out = []
k = 0
for i in range(len(outputs)):
if i % 3 == 1:
low_32 = outputs[i] & 0xFFFFFFFF
high_32 = outputs[i] >> 32
out.append(low_32)
out.append(high_32)
else :
out.append(outputs[i])
outs = out[:11]+out[227:238]
processed_data = []
target_indices = []
for i, val in enumerate(outs):
if i < 11:
real_index = i
else:
real_index = i + 216
if real_index % 4 == 0:
bits = 30
target_indices.append(i)
print(len(target_indices))
for bits in itertools.product(range(4), repeat=len(target_indices)):
candidate_out = list(outs)
for idx, bit in zip(target_indices, bits):
candidate_out[idx] = (candidate_out[idx] << 2) + bit
try:
breaker = python_random_breaker()
print(hex(breaker.recover_all_integer_seeds_from_few_outputs(256, candidate_out, True)[0]))
except:
pass