👋
UIUCTF 2024 Writeup
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()
サーバーを介して
行列式に適当に値を入れてみたときに、
- M_{1,3} のみ
2 1 - M_{4,3} のみ
2 1
の二つの行列式は、それぞれ
行列式の係数の寄与を求めたプログラム
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
while not found:
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}
upsolveしたい問題
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.
都合の良いカーマイケル数を見つけることができたら、Pohlig–Hellman algorithm で求めることができそう。ただ、都合の良いカーマイケル数を見つけることができなかった。
Discussion