d = data[0] out_path = './out/' epsilon = 72 for psize in psizes: for X in psize.divisors(): Y = psize // X if X < Y or X < epsilon or Y < epsilon: continue print(X, Y) fname = '%s%d_%d_%d' % (out_path, psize, X, Y) withopen(fname+'.ppm', 'wb') as f: f.write(b'P6\n%d %d\n65535\n' % (X, Y) + d[:psize*6]) img = cv2.imread(fname+'.ppm') cv2.imwrite(fname+'.png', img)
withopen('./all_flags.enc', 'rb') as f: data = f.read() data = [data[esize*i: esize*(i+1)] for i inrange(npic)] psize = 152562 X = 1623 Y = 94 for i inrange(len(data)): fname = '%s%d_%d_%d-%d' % (out_path, psize, X, Y, i) print(fname) withopen(fname+'.ppm', 'wb') as f: f.write(b'P6\n%d %d\n65535\n' % (X, Y) + data[i][:psize*6]) img = cv2.imread(fname+'.ppm') cv2.imwrite(fname+'.png', img)
real = b'' w = data[0][:16] for i inrange(len(data[40])//16): di = data[40][16*i: 16*(i+1)] if di == w: real += b'\xff' * 16 else: real += b'\x00' * 16
withopen('./all_flags.enc', 'rb') as f: data = f.read() n = len(data) tail = data[-16:]
data = data.split(tail)[:-1] data = [d+tail for d in data] test = [len(d) for d in data]
esize = max(test, key=test.count) assert n % esize == 0 npic = n // esize print(npic, esize)
psizes = [] for i inrange(16): if (esize-i) % 6 == 0: psizes += [(esize-i) // 6] print(psizes)
# get Size d = data[0] out_path = './out/' epsilon = 72 for psize in psizes: for X in psize.divisors(): Y = psize // X if X < Y or X < epsilon or Y < epsilon: continue print(X, Y) fname = '%s%d_%d_%d' % (out_path, psize, X, Y) withopen(fname+'.ppm', 'wb') as f: f.write(b'P6\n%d %d\n65535\n' % (X, Y) + d[:psize*6]) img = cv2.imread(fname+'.ppm') cv2.imwrite(fname+'.png', img) # rm fake withopen('./all_flags.enc', 'rb') as f: data = f.read() data = [data[esize*i: esize*(i+1)] for i inrange(npic)] psize = 152562 X = 1623 Y = 94 for i inrange(len(data)): fname = '%s%d_%d_%d-%d' % (out_path, psize, X, Y, i) print(fname) withopen(fname+'.ppm', 'wb') as f: f.write(b'P6\n%d %d\n65535\n' % (X, Y) + data[i][:psize*6]) img = cv2.imread(fname+'.ppm') cv2.imwrite(fname+'.png', img) # prettify real = b'' w = data[0][:16] for i inrange(len(data[40])//16): di = data[40][16*i: 16*(i+1)] if di == w: real += b'\xff' * 16 else: real += b'\x00' * 16
from pwn import remote, context context.log_level = 'debug'
r = remote('00.cr.yp.toc.tf', 13771) for i inrange(8): print(i) r.recvuntil(b'first input:') withopen('./hashclash/cpc_workdir/collision1.bin.%d' % i, 'rb') as f: r.sendline(f.read().hex()) r.recvuntil(b'second input:') withopen('./hashclash/cpc_workdir/collision2.bin.%d' % i, 'rb') as f: r.sendline(f.read().hex())
r.interactive() r.close()
# ┃ Congrats! the flag: b'CCTF{mD5_h4Sh_cOlL!Si0N_CrYp7o_ch41lEnGe!!!}'
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Welcome to Ahoo task! Given integer n, find the smallest positive ┃ ┃ integer c such that n * c has the minimum number of 1 bits in its ┃ ┃ binary representation. Completing all steps will reveal the flag :) ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
from pwn import remote, context context.log_level = 'debug'
# https://raw.githubusercontent.com/FinnLidbetter/sturdy-numbers/master/timing/aut-msw-1-10000.txt withopen('./aut-msw-1-10000.txt', 'r') as f: data = f.read().split('\n')[:-1] data = [0] + [int(_) for _ in data]
r = remote('00.cr.yp.toc.tf', 17371) for _ inrange(20): r.recvuntil(b'n = ') n = int(r.recvuntil(b',')[:-1])
res = b'%d, %d' % (bin(data[n] * n).count('1'), data[n]) r.sendline(res)
r.interactive() r.close()
# ┃ Congrats, you got the flag: b'CCTF{iZ_It_5h0rT_c0mpUt3r_C4lcuLaT!oN!???}'
for i inrange(1): d = (len(str(c))) // 2 q = 4 * 100 ** d
B = matrix(ZZ, [ [q, 0], [h, 1] ]) g, f = B.LLL()[0] f, g = abs(f), abs(g) print(f, g) print(gcd(f, f+g))
a = f * c % q n = (f + g) // gcd(f, f+g) #n = n // gcd(f, n) print(gcd(f, n)) m = a * f.inverse_mod(n) % n try: flag = bytes.fromhex(hex(m)[2:]) print(flag) except: pass
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Hey! It's time to solve the equation of a function f: N x N -> Z. ┃ ┃ Function f has given certain conditions. In each step, solve the ┃ ┃ equation f(x, y) = z with the given value of z. We know f(a+1, b) = ┃ ┃ f(a, b) + a, and f(a, b+1) = f(a, b) - b, for every `a' and `b'. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
checker = genStrChecker(string.printable) ps = [(p-1)//2, (q-1)//2] resp = nthRSA_n(cp, yp, ps, checker=checker) for r in resp: flag = bytes.fromhex(hex(r)[2:]) print(flag) resq = nthRSA_n(cq, yq, ps, checker=checker) for r in resq: flag = bytes.fromhex(hex(r)[2:]) print(flag)
withopen('./output.txt', 'r') as f: exec(f.read())
e, p, PT = enc t = len(PT) a = [] fa = [] for i inrange(len(PT)): a += [PT[i][0]] fa += [PT[i][1]]
A = matrix(GF(p), t, t) for i inrange(t): for j inrange(t): A[i, j] = powmod(a[j], i, p) Ainv = A^(-1)
vf = vector(GF(p), fa) vc = vf * Ainv c = Integer(vc[0]) print('c = %d' % c)
assert gcd(e, p-1) != 1 # https://tover.xyz/p/n-root-in-F/ load('nth.sage') checker = genStrChecker(string.printable) res = nthRSA_n(c, Integer(e), [Integer(p)], checker=checker) for r in res: flag = bytes.fromhex(hex(r)[2:]) print(flag)
''' c = 7578451683223886721897751965012512970186814199061886859082385728532294810974986601048390882041773215459258245487361965408708218417206386123135513829067466 b'CCTF{SSS_iZ_4n_3fF!ciEn7_5ecr3T_ShArIn9_alGorItHm!}' '''
defflatten(f): coefs = f.list() whilenotall(abs(_) <= 1for _ in coefs): for i inrange(len(coefs)): whileabs(coefs[i]) >= 2: if i+3 > len(coefs): coefs += [0]*2 s = coefs[i].sign() coefs[i] -= 2 * s coefs[i+1] -= s coefs[i+2] -= s return R(coefs)
这个Trivial的做法对于l很大的情况会迭代得非常慢,所以我还参考了二进制数的计算方法进行了优化
具体是,先计算1、2、22…2step对应的多项式fi:
1 2 3 4
bits = [R(1)] for i inrange(1, step+1): bits += [flatten(bits[-1] * 2)] assert bits[-1] % g == 2^i
然后对于输入l,转化为二进制表示后把对应的fi相加,然后展平即可
1 2 3 4 5 6 7 8
defgetf(l): f = R(0) lb = l.bits() for i inrange(len(lb)): if lb[i]: f += bits[i] f = flatten(f) return f
defupgrade(f): coefs = f.list() + [0] * 2 # x+1 = -x^2-1 for i inrange(1, len(coefs)-1): if coefs[i-1] == coefs[i] andabs(coefs[i]) == 1: coefs[i-1] = - coefs[i-1] s = coefs[i].sign() coefs[i] -= s coefs[i+1] -= s
# x-1 = -x^3+1 for i inrange(1, len(coefs)-1): if coefs[i-1] == -coefs[i] andabs(coefs[i]) == 1: coefs[i-1] = - coefs[i-1] s = coefs[i].sign() coefs[i] -= s coefs[i+2] -= s return flatten(R(coefs))
''' count = 0 for l in range(1, 2^13): f = getf(Integer(l)) for _ in range(10): f = upgrade(f) if check(f, l) != 0: count += 1 print(count) # 12 '''
defflatten(f): coefs = f.list() whilenotall(abs(_) <= 1for _ in coefs): for i inrange(len(coefs)): whileabs(coefs[i]) >= 2: if i+3 > len(coefs): coefs += [0]*2 s = coefs[i].sign() coefs[i] -= 2 * s coefs[i+1] -= s coefs[i+2] -= s return R(coefs) bits = [R(1)] for i inrange(1, step+1): bits += [flatten(bits[-1] * 2)] assert bits[-1] % g == 2^i assert check(bits[-1], bits[-1] % g) == 0
defgetf(l): f = R(0) lb = l.bits() for i inrange(len(lb)): if lb[i]: f += bits[i] f = flatten(f) return f
defupgrade(f): coefs = f.list() + [0] * 2 # x+1 = -x^2-1 for i inrange(1, len(coefs)-1): if coefs[i-1] == coefs[i] andabs(coefs[i]) == 1: coefs[i-1] = - coefs[i-1] s = coefs[i].sign() coefs[i] -= s coefs[i+1] -= s
# x-1 = -x^3+1 for i inrange(1, len(coefs)-1): if coefs[i-1] == -coefs[i] andabs(coefs[i]) == 1: coefs[i-1] = - coefs[i-1] s = coefs[i].sign() coefs[i] -= s coefs[i+2] -= s return flatten(R(coefs))
''' count = 0 for l in range(1, 2^13): f = getf(Integer(l)) for _ in range(10): f = upgrade(f) if check(f, l) != 0: count += 1 print(count) # 12 '''
r = remote('00.cr.yp.toc.tf', 37771)
for s inrange(1, step): r.recvuntil(b'step %d and n = ' % s) l = Integer(r.recvuntil(',')[:-1].decode()) print(s, l) f = getf(l) for _ inrange(16): f = upgrade(f) r.sendline(str(f).encode())
r.interactive() r.close()
# ┃ Congrats, you got the flag: b'CCTF{0p71M!5TiC_rEpR3SenT4t!0n_Of_n_8Y_Frobenius!}'
results = {} ''' non-singular ... a = [1] b = [0] ''' a = [] b = [] size = 32 for i inrange(1, size): tmp = list(R(x^i) % g) a += [tmp[0]] b += [tmp[1]]
B = identity_matrix(ZZ, size) for i inrange(size-1): B[i+1, 0] = a[i] B[i+1, 1] = b[i]
for l inrange(1, 2^(step+1)): B[0, 0] = -l L = B.LLL() Binv = B^(-1)
for w in L: v = w * Binv ifabs(v[0]) == 1: v = [0] + [Integer(vi) for vi in (v[0]*v)[1:]] else: continue f = R(v) try: i = Integer(f % g) except: continue
#!/usr/bin/env sage withopen('./output.txt', 'r') as f: exec(f.read()) m = 19
R = PolynomialRing(ZZ, 'x') x = R.gen() f = R(0) nn = n i = 0 while nn != 0: f += Integer(nn % 19) * x^i nn //= 19 i += 1 pqr = list(factor(f)) assertlen(pqr) == 3
p, q, r = [_[0](x=m) for _ in pqr] assert p * q * r == n print('p = %d' % p) print('q = %d' % q) print('r = %d' % r)
phi = (p-1) * (q-1) * (r-1) zl = max([list(pqr[i][0]-2).count(1) for i inrange(3)]) zu = max([pqr[i][0].degree() for i inrange(3)])
for z inrange(zl, zu): e = m^3 + z - 2 # if gcd != 1 -> https://tover.xyz/p/n-root-in-F/ if gcd(e, phi) != 1: continue d = Integer(e).inverse_mod(phi) try: flag = bytes.fromhex(Integer(pow(c, d, n)).hex()) print('z = %d' % z) print(flag) except: pass
''' p = 3530869780887683268140728773245395170410635845517928489976021534009516369358447511411853596093628646212566313257712207746790503704123439 q = 67086525836865982094673880600810256005961617151283317566078153226175705789594094624822652838168627925461219084263915001883644637391279141 r = 1274643990900453659882765495755380673132370043776742526720540623203930562265302201405804416214498793910236254519606076438989349099317154363 z = 14 b'CCTF{nUmb3r5_1N_D!fFerEn7_8As35_4r3_n!cE!?}' '''
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ .:: Soufia is a random oracle, your mission is to break it ::. ┃ ┃ We know that f: Z → Z and for all integers `x' and `y' we have: ┃ ┃ f(t * x) + t * f(x) = f(f(x + y)) for constant integer `t'. ┃ ┃ Also, f(0) = 171179160041154255998170822544254161925, ┃ ┃ and f(9) = 2918265810101910926377464647051822947123 ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃ Please send the f(10):
#!/usr/bin/env sage from pwn import remote, context context.log_level = 'debug'
r = remote('00.cr.yp.toc.tf', 13377) r.recvuntil(b'f(0) = ') f0 = Integer(r.recvuntil(b',')[:-1].decode())
r.recvuntil(b'and f(') x = Integer(r.recvuntil(b')')[:-1].decode()) r.recvuntil(b' = ') fx = Integer(r.recvuntil(b' ')[:-1].decode()) c = (fx - f0) // x
for _ inrange(20): r.recvuntil(b'the f(') y = Integer(r.recvuntil(b')')[:-1].decode()) fy = f0 + c * y r.sendline(str(fy).encode())
r.interactive() r.close()
# ┃ Congratz! You got the flag: b'CCTF{A_funCti0nal_3qu4tiOn_iZ_4_7yPe_oF_EquAtioN_tHaT_inv0lVe5_an_unKnOwn_funCt!on_r4tH3r_thAn_juS7_vArIabl3s!!}'
#!/usr/bin/env sage A = 6080057478320734754578252336954411086329731226445881868123716230995225973869803901199434606333357820515656618869146654158788168766842914410452961599054518002813068771365518772891986864276289860125347726759503163130747954047189098354503529975642910040243893426023284760560550058749486622149336255123273699589/10166660077500992696786674322778747305573988490459101951030888617339232488971703619809763229396514541455656973227690713112602531083990085142454453827397614 U = 3225614773582213369706292127090052479554140270383744354251548034114969532022146352828696162628127070196943244336606099417210627640399143341122777407316956319347428454301338989662689983156270502206905873768685192940264891098471650041034871787036353839986435/9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609 V = 1971582892158351181843851788527088806814104010680626247728311504906886858748378948163011806974145871263749452213375101951129675358232283650086419295655854343862361076089682606804214329522917382524296561295274823374483828323983651110722084223144007926678084087/9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609
An = A.numerator() Ad = A.denominator() a = Ad // 17 assert Ad % 17 == 0 assert17 * a^2 + 1 == An print('a = %d' % a)
Un = U.numerator() Ud = U.denominator() Vn = V.numerator() Vd = V.denominator() assert Ud == Vd b = Ud print('b = %d' % b)
for g inrange(1, 1997): M = matrix(ZZ, [ [a+g*b, -1], [-1, g*b-a] ]) w = vector(ZZ, (g*Un, g*Vn)) v = w * M^(-1) m1, m2 = v try: flag = bytes.fromhex(hex(m1)[2:]) + bytes.fromhex(hex(m2)[2:]) print('g = %d' % g) print(flag) except: pass
''' a = 598038828088293688046274960163455723857293440615241291237111095137601911115982565871162542905677325967979821954570041947800148887293534420144379636905742 b = 9195042623204647899565271327907071916397082689301388805795886223781949921278129819112624089473306486581983153439866384171645444456400131619437018878598534536108398238424609 g = 5 b'.:: CCTF{d!D_y0U_5oLv3_7HiS_eQu4T!On_wItH_uSing_c0mPlEx_Num8erS!!?} ::.' '''