这里也记录一下,各种比赛零零散散的题目(觉得比较有意思的)

KalmarCTF2025 - basic sums

py
with open("flag.txt", "rb") as f:
flag = f.read()

# I found this super cool function on stack overflow \o/ https://stackoverflow.com/questions/2267362/how-to-convert-an-integer-to-a-string-in-any-base
def numberToBase(n, b):
if n == 0:
return [0]
digits = []
while n:
digits.append(int(n % b))
n //= b
return digits[::-1]

assert len(flag) <= 45

flag = int.from_bytes(flag, 'big')

base = int(input("Give me a base! "))

if base < 2:
print("Base is too small")
quit()
if base > 256:
print("Base is too big")
quit()

print(f'Here you go! {sum(numberToBase(flag, base))}')

题目代码非常简单,我们会得到flag转换为n进制之后的数字之和,可以写成下面的形式

flag=anbn+an1bn1+an2bn2+...+a0b0flag=a_{n}b^{n}+a_{n-1}b^{n-1}+a_{n-2}b^{n-2}+...+a_{0}b^{0}
同时,不难看出有同时,不难看出有
flagsumsan+an1+an2+...+a1+a1(mod b1)flag\equiv sums\equiv a_{n}+a_{n-1}+a_{n-2}+...+a_{1}+a_{1}(mod\ b-1)

上面是我们选择的进制之间的最小公倍数,下面是flag的近似大小(肯定要比这个大)

所以,当模数足够大的时候,flag模它才能得到本身,同时我们也有

flagsums mod (b1)flag\equiv sums\ mod\ (b-1)

flagm mod lcm(n,b1)flag\equiv m\ mod\ lcm(n,b-1)

在b不断增大的情况下,对m不断地进行crt结果的合并,当最小公倍数增大到模数大于flag的值时,我们才能获取到flag的唯一解

flag=crt([m,sums],[lcm(n,b1),b1])flag=crt([m,sums],[lcm(n,b-1),b-1])

py
# sage
from pwn import *
from tqdm import trange

context(os='linux', arch='amd64', log_level='debug')
m = 0
n = 1
for i in trange(2,256):
p = remote('basic-sums.chal-kalmarc.tf', 2256)
p.sendlineafter(b'Give me a base! ',str(i).encode())
p.recvuntil(b'go! ')
m0 = int(p.recvline())
n0 = i-1
m = crt([m,m0],[n,n0])
n = lcm(n,n0)
p.close()
print(long_to_bytes(int(m)))
# b'kalmar{At_least_it_wasnt_lattices_right???!?}'


这图片起到了一定的迷惑作用,我还以为要构造格才做的出来,我寻思着我这格构造的好像也不怎么行啊,而且这么多组数据,要怎么整呢,然后就看到春哥做出来了,牛批!!!

所以上面其实是我看了春哥写的文档之后,思考了一番(过程应该没问题),觉得挺有意思的记录一下OvO

TPCTF2025 - randomized random

py
# FROM python:3
import random
with open("flag.txt","rb") as f:
flag=f.read()
for i in range(2**64):
print(random.getrandbits(32)+flag[random.getrandbits(32)%len(flag)])
input()

看到getrandbits,可以立马想到MT19937,这里的话因为两个随机数“加”起来了,我们不好处理,但是可以看做是我们可以得到不连续的随机数中的高24位,但看了师傅们的wp都说了实际测试发现影响到了低20位,所以取得是高12位

然后就是不连续的MT19937

待我有空再钻研钻研

2024第四届长城杯 - RandomRSA

题目描述:A特工从敌方服务器获取到了一份带有hint的机密文件,请协助破解加密。

py
import gmpy2
import random
from secret import flag
from Crypto.Util.number import *


class LCG:
def __init__(self, p, a, b):
self.p = p
self.a = a
self.b = b
self.x = random.randint(0, p-1)
print(self.p, self.a, self.b)

def next(self):
self.x = (self.a*self.x+self.b) % self.p
return self.x


def getPrimes(bits, k):
p = getPrime(bits)
a = random.randint(0, p-1)
b = random.randint(0, p-1)
l = LCG(p, a, b)
return [gmpy2.next_prime(l.next()) for _ in range(k)]


p, q = getPrimes(1024, 2)
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(n, c)
'''
p = 170302223332374952785269454020752010235000449292324018706323228421794605831609342383813680059406887437726391567716617403068082252456126724116360291722050578106527815908837796377811535800753042840119867579793401648981916062128752925574017615120362457848369672169913701701169754804744410516724429370808383640129
a = 95647398016998994323232737206171888899957187357027939982909965407086383339418183844601496450055752805846840966207033179756334909869395071918100649183599056695688702272113280126999439574017728476367307673524762493771576155949866442317616306832252931038932232342396406623324967479959770751756551238647385191314
b = 122891504335833588148026640678812283515533067572514249355105863367413556242876686249628488512479399795117688641973272470884323873621143234628351006002398994272892177228185516130875243250912554684234982558913267007466946601210297176541861279902930860851219732696973412096603548467720104727887907369470758901838
n = 5593134172275186875590245131682192688778392004699750710462210806902340747682378400226605648011816039948262008066066650657006955703136928662067931212033472838067050429624395919771757949640517085036958623280188133965150285410609475158882527926240531113060812228408346482328419754802280082212250908375099979058307437751229421708615341486221424596128137575042934928922615832987202762651904056934292682021963290271144473446994958975487980146329697970484311863524622696562094720833240915154181032649358743041246023013296745195478603299127094103448698060367648192905729866897074234681844252549934531893172709301411995941527
c = 2185680728108057860427602387168654320024588536620246138642042133525937248576850574716324994222027251548743663286125769988360677327713281974075574656905916643746842819251899233266706138267250441832133068661277187507427787343897863339824140927640373352305007520681800240743854093190786046280731148485148774188448658663250731076739737801267702682463265663725900621375689684459894544169879873344003810307496162858318574830487480360419897453892053456993436452783099460908947258094434884954726862549670168954554640433833484822078996925040310316609425805351183165668893199137911145057639657709936762866208635582348932189646
'''

xax+b%px\equiv ax+b\%p
p(x+k1)%pp'\equiv(x+k1)\%p
q(ax+b+k2)%pq'\equiv(ax+b+k2)\%p
pqnax2+(b+k2+ak1)x+bk1+k1k2n0%pp'*q'-n\equiv ax^{2}+(b+k2+ak1)x+bk1+k1k2-n\equiv0\%p
abpn已知,k1k2是小数可爆破,那就解x的一元二次方程即可

这里得开多线程搞一手……

reference

https://tover.xyz/p/2024-ccb-RandomRSA/
http://www.andynoel.xyz/?p=904
https://blog.csdn.net/Jayjay___/article/details/142059111