👋

2024/07/01に公開

# Determined

"It is my experience that proofs involving matrices can be shortened by 50% if one throws the matrices out."
Emil Artin

gen.py
from SECRET import FLAG, p, q, r
from Crypto.Util.number import bytes_to_long
n = p * q
e = 65535
m = bytes_to_long(FLAG)
c = pow(m, e, n)
# printed to gen.txt
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")


server.py
from Crypto.Util.number import bytes_to_long, long_to_bytes
from itertools import permutations
from SECRET import FLAG, p, q, r

def inputs():
print("[DET] First things first, gimme some numbers:")
M = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
try:
M[0][0] = p
M[0][2] = int(input("[DET] M[0][2] = "))
M[0][4] = int(input("[DET] M[0][4] = "))

M[1][1] = int(input("[DET] M[1][1] = "))
M[1][3] = int(input("[DET] M[1][3] = "))

M[2][0] = int(input("[DET] M[2][0] = "))
M[2][2] = int(input("[DET] M[2][2] = "))
M[2][4] = int(input("[DET] M[2][4] = "))

M[3][1] = q
M[3][3] = r

M[4][0] = int(input("[DET] M[4][0] = "))
M[4][2] = int(input("[DET] M[4][2] = "))
except:
return None
return M

def handler(signum, frame):
raise Exception("[DET] You're trying too hard, try something simpler")

def fun(M):
def sign(sigma):
l = 0
for i in range(5):
for j in range(i + 1, 5):
if sigma[i] > sigma[j]:
l += 1
return (-1)**l

res = 0
for sigma in permutations([0,1,2,3,4]):
curr = 1
for i in range(5):
curr *= M[sigma[i]][i]
res += sign(sigma) * curr
return res

def main():
print("[DET] Welcome")
M = inputs()
if M is None:
print("[DET] You tried something weird...")
return

res = fun(M)
print(f"[DET] Have fun: {res}")

if __name__ == "__main__":
main()


サーバーを介して p, q のヒントを得れる問題。穴あきの正方行列に、自由に値を与えることができ、それの行列式を得られる。

• M_{1,3} のみ 2 でそれ以外を 1
• M_{4,3} のみ 2 でそれ以外を 1

の二つの行列式は、それぞれ pq-pr-2q+2r, pq-2pr-2q+2r となっており、差を取って n を足すと pr を得られる。

n と gcd を取れば p を手に入れることができるので、復元が可能。

from itertools import permutations

zero_table = [
[False, True, False, True, False],
[True, False, True, False, True],
[False, True, False, True, False],
[True, False, True, False, True],
[False, True, False, True, True],
]

num = [
[-1, -1, 1, -1, 1],
[-1, 1, -1, 1, -1],
[1, -1, 1, -1, 1],
[-1, -1, -1, -1, -1],
[1, -1, 2, -1, -1],
]

def M(i, j):
zero = zero_table[i][j]
p = True if i == 0 and j == 0 else False
q = True if i == 3 and j == 1 else False
r = True if i == 3 and j == 3 else False
_mul = num[i][j] if num[i][j] != -1 else 1
return zero, p, q, r, _mul

def sign(sigma):
l = 0
for i in range(5):
for j in range(i + 1, 5):
if sigma[i] > sigma[j]:
l += 1
return (-1)**l

ps, qs, rs = 0, 0, 0
pqs, prs, qrs = 0, 0, 0
pqrs = 0
other = 0
for sigma in permutations([0,1,2,3,4]):
zero, P, Q, R = False, False, False, False
mul = 1
for i in range(5):
_zero, _p, _q, _r, _mul = M(sigma[i], i)
zero |= _zero
P |= _p
Q |= _q
R |= _r
mul *= _mul
if zero:
continue

if P and Q and R:
pqrs += sign(sigma)*mul
elif P and Q:
pqs += sign(sigma)*mul
elif P and R:
prs += sign(sigma)*mul
elif Q and R:
qrs += sign(sigma)*mul
elif P:
ps += sign(sigma)*mul
elif Q:
qs += sign(sigma)*mul
elif R:
rs += sign(sigma)*mul
else:
other += sign(sigma)*mul

print(pqrs, pqs, prs, qrs, ps, qs, rs, other)

solve.py
import math
from Crypto.Util.number import *

n = 158794636700752922781275926476194117856757725604680390949164778150869764326023702391967976086363365534718230514141547968577753309521188288428236024251993839560087229636799779157903650823700424848036276986652311165197569877428810358366358203174595667453056843209344115949077094799081260298678936223331932826351
e = 65535
c = 72186625991702159773441286864850566837138114624570350089877959520356759693054091827950124758916323653021925443200239303328819702117245200182521971965172749321771266746783797202515535351816124885833031875091162736190721470393029924557370228547165074694258453101355875242872797209141366404264775972151904835111

a = 69143703864818353130371867063903344721913499237213762852365448402106351546379534901008421404055139746270928626550203483668654060066917995961156948563756752700538511697695076762773965531010748006659492973112024174525746367374237063293523650725957257590333321191693876781172827116596771133374732236966118301362

b = 138287407729636706260743734127806689443826998474427525704730896804212703092759069802016842808110279492541857253100406967337308120133835991922313897127513516320621205708659704142079963748777128382549701084698364980167762697266410903475395355942138123738857962124700981542288716811468935303034718002058884136696

pr = a-b+n

p = math.gcd(pr, n)
q = n // p

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

print(long_to_bytes(m))


uiuctf{h4rd_w0rk_&&_d3t3rm1n4t10n}

# Naptime

I'm pretty tired. Don't leak my flag while I'm asleep.

enc_dist.sage
from random import randint
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import numpy as np

def get_b(n):
b = []
b.append(randint(2**(n-1), 2**n))
for i in range(n - 1):
lb = sum(b)
found = False
num = randint(max(2**(n + i), lb + 1), 2**(n + i + 1))
if num > lb:
found = True
b.append(num)

return b

def get_MW(b):
lb = sum(b)
M = randint(lb + 1, 2*lb)
W = getPrime(int(1.5*len(b)))

return M, W

def get_a(b, M, W):
a_ = []
for num in b:
a_.append(num * W % M)
pi = np.random.permutation(list(i for i in range(len(b)))).tolist()
a = [a_[pi[i]] for i in range(len(b))]
return a, pi

def enc(flag, a, n):
bitstrings = []
for c in flag:
# c -> int -> 8-bit binary string
bitstrings.append(bin(ord(c))[2:].zfill(8))
ct = []
for bits in bitstrings:
curr = 0
for i, b in enumerate(bits):
if b == "1":
curr += a[i]
ct.append(curr)

return ct

def dec(ct, a, b, pi, M, W, n):
# construct inverse permuation to pi
pii = np.argsort(pi).tolist()
m = ""
U = pow(W, -1, M)
ct = [c * U % M for c in ct]
for c in ct:
# find b_pi(j)
diff = 0
bits = ["0" for _ in range(n)]
for i in reversed(range(n)):
if c - diff > sum(b[:i]):
diff += b[i]
bits[pii[i]] = "1"
# convert bits to character
m += chr(int("".join(bits), base=2))

return m

def main():
flag = 'uiuctf{I_DID_NOT_LEAVE_THE_FLAG_THIS_TIME}'

# generate cryptosystem
n = 8
b = get_b(n)
M, W = get_MW(b)
a, pi = get_a(b, M, W)

# encrypt
ct = enc(flag, a, n)

# public information
print(f"{a =  }")
print(f"{ct = }")

# decrypt
res = dec(ct, a, b, pi, M, W, n)

if __name__ == "__main__":
main()

enc.txt
a =  [66128, 61158, 36912, 65196, 15611, 45292, 84119, 65338]
ct = [273896, 179019, 273896, 247527, 208558, 227481, 328334, 179019, 336714, 292819, 102108, 208558, 336714, 312723, 158973, 208700, 208700, 163266, 244215, 336714, 312723, 102108, 336714, 142107, 336714, 167446, 251565, 227481, 296857, 336714, 208558, 113681, 251565, 336714, 227481, 158973, 147400, 292819, 289507]


ナップザック暗号の一種となっている（っぽい？chatGPTに聞いたらそう返ってきた）。各文字毎に暗号化をしているので、どうにか ct[i] となる集合を求める。集合に関しては、ビットごとにシャッフルされているっぽいので順列を全部試す。

solve.py
a =  [66128, 61158, 36912, 65196, 15611, 45292, 84119, 65338]
ct = [273896, 179019, 273896, 247527, 208558, 227481, 328334, 179019, 336714, 292819, 102108, 208558, 336714, 312723, 158973, 208700, 208700, 163266, 244215, 336714, 312723, 102108, 336714, 142107, 336714, 167446, 251565, 227481, 296857, 336714, 208558, 113681, 251565, 336714, 227481, 158973, 147400, 292819, 289507]

bs = []

for c in ct:
for S in range(256):
sum = 0
for i in range(8):
if S >> i & 1:
sum += a[i]
if sum == c:
bs.append(S)

from itertools import permutations

for iter in permutations(range(8)):
ms = []
for b in bs:
num = 0
for i in range(8):
if b >> i & 1:
num += 1 << iter[i]
ms.append(num)
if ms[0] == ord('u'):
print(''.join(chr(x) for x in ms))



uiuctf{i_g0t_sleepy_s0_I_13f7_th3_fl4g}

# Groups

My friend told me that cryptography is unbreakable if moduli are Carmichael numbers instead of primes. I decided to use this CTF to test out this theory.

(6k+1)(12k+1)(18k+1)3 項すべてが素数の場合、これはカーマイケル数になるのだが、これだと中国剰余定理に落とし込むことが難しそう（同じ素因数が 3 回程度現れるため）