💭
TBTL CTF 2024 writeup
Fence Building [544 solves]
I've recently got into woodworking and have build a beautiful fence just like this one.
Now I'm working on a flag, but it turns out all garbled for some reason...
T0n40g5BG03cmk0D1hr}T{dFe_3g_3buL_5_n0
fence暗号と言われているので、それを実装する。chatGPTに任せて僕はほかの問題を見ていました。
solve.py
# 正確なスプリット・レール・フェンス暗号の復号処理
def decrypt_split_rail_fence(ciphertext, num_rails):
# 暗号文の長さ
n = len(ciphertext)
# レールごとにインデックスのリストを作成
rails = [[] for _ in range(num_rails)]
# 現在のレールと進行方向
rail, step = 0, 1
# レールパターンを決定
for i in range(n):
rails[rail].append(i)
if rail == 0:
step = 1
elif rail == num_rails - 1:
step = -1
rail += step
# レールパターンに基づいて復号
result = [''] * n
idx = 0
for r in rails:
for i in r:
result[i] = ciphertext[idx]
idx += 1
return ''.join(result)
# 4レールを仮定して復号を試みる
decrypted_text_correct_4_rails_fixed = decrypt_split_rail_fence(cipher_text, 4)
decrypted_text_correct_4_rails_fixed
TBTL{G00d_F3nce5_m4k3_g00D_n31ghb0ur5}
School Essay [101 solves]
I had to write an essay for school describing my favorite classmate. I wonder if my classmates will be able to figure out who I'm describing...
chall.py
from Crypto.Util.number import *
from redacted import FLAG
ESSAY_TEMPLATE = """
My Favorite Classmate
=====================
My favorite person in this class has a beautiful smile,
great sense of humour, and lots of colorful notebooks.
However, their most distinctive feature is the fact that
you can represent their name as an integer value, square
it modulo %d,
and you'll get %d.
Additionally, When you compute the greatest integer not exceeding
the cube root of their squared name, you get %d.
By now, all of you have probably guessed who I'm talking about.
"""
def invpow3(x):
lo, hi = 1, x
while lo < hi:
mid = (lo + hi) // 2 + 1
if (mid**3) <= x:
lo = mid
else:
hi = mid - 1
return lo
N = 59557942237937483757629838075432240015613811860811898821186897952866236010569299041278104165604573
name_int = bytes_to_long(FLAG)
assert 1 < name_int < N
value_1 = (name_int**2) % N
value_2 = invpow3(name_int**2)
print(ESSAY_TEMPLATE % (N, value_1, value_2))
description.txt
My Favorite Classmate
=====================
My favorite person in this class has a beautiful smile,
great sense of humour, and lots of colorful notebooks.
However, their most distinctive feature is the fact that
you can represent their name as an integer value, square
it modulo 59557942237937483757629838075432240015613811860811898821186897952866236010569299041278104165604573,
and you'll get 34994952631013563439857468985559745199379391295940238707110695903159545061311344766055629477728657.
Additionally, When you compute the greatest integer not exceeding
the cube root of their squared name, you get 7906488397402721714607879953738472269409876715324979164781592447.
By now, all of you have probably guessed who I'm talking about.
solve.py
import gmpy2
from Crypto.Util.number import *
N = 59557942237937483757629838075432240015613811860811898821186897952866236010569299041278104165604573
value_1 = 34994952631013563439857468985559745199379391295940238707110695903159545061311344766055629477728657
value_2 = 7906488397402721714607879953738472269409876715324979164781592447
# https://qiita.com/taiyaki8926/items/6720a1c19e9c9afbfd12#%E5%85%A8%E4%BD%93%E3%81%AE%E3%82%BD%E3%83%BC%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%89
def legendre_symbol(n, p):
ls = pow(n, (p - 1) // 2, p)
if ls == 1:
return 1
elif ls == p - 1:
return -1
else:
# in case ls == 0
raise Exception('n:{} = 0 mod p:{}'.format(n, p))
def check_sqrt(x, n, p):
assert(pow(x, 2, p) == n % p)
def modular_sqrt(n:int, p:int) -> list:
if type(n) != int or type(p) != int:
raise TypeError('n and p must be integers')
if p < 3:
raise Exception('p must be equal to or more than 3')
if not isPrime(p):
raise Exception('p must be a prime number. {} is a composite number'.format(p))
if legendre_symbol(n, p) == -1:
raise Exception('n={} is Quadratic Nonresidue modulo p={}'.format(n, p))
if p % 4 == 3:
x = pow(n, (p + 1) // 4, p)
check_sqrt(x, n, p)
return [x, p - x]
# Tonelli-Shanks
q, s = p - 1, 0
while q % 2 == 0:
q //= 2
s += 1
z = 2
while legendre_symbol(z, p) != -1:
z += 1
m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
while t != 1:
pow_t = pow(t, 2, p)
for j in range(1, m):
if pow_t == 1:
m_update = j
break
pow_t = pow(pow_t, 2, p)
b = pow(c, int(pow(2, m - m_update - 1)), p)
m, c, t, r = m_update, pow(b, 2, p), t * pow(b, 2, p) % p, r * b % p
check_sqrt(r, n, p)
return [r, p - r]
name_ints = modular_sqrt(value_1, N)
for name_int in name_ints:
try:
print(long_to_bytes(name_int))
except:
pass
TBTL{J0hn_J4c0b_J1n6leH31mer_Schm1d7_<3}
Wikipedia Signatures [84 solves]
https://en.wikipedia.org/w/index.php?title=Digital_signature&oldid=1113936031
Alice signs a message—"Hello Bob!"—by appending to the original message a version encrypted with her private key. Bob receives both the message and signature. He uses Alice's public key to verify the authenticity of the message, i.e. that the encrypted copy, decrypted using the public key, exactly matches the original message.
server.py
#!/usr/bin/python3
from redacted import FLAG
from Crypto.Util.number import bytes_to_long
from Crypto.Math.Numbers import Integer
from Crypto.PublicKey import RSA
import signal
TARGET = b'I challenge you to sign this message!'
def myprint(s):
print(s, flush=True)
def handler(_signum, _frame):
myprint("Time out!")
exit(0)
def rsa(m, n, x):
if not 0 <= m < n:
raise ValueError("Value too large")
return int(pow(Integer(m), x, n))
# Alice signs a message—"Hello Bob!"—by appending to the original
# message a version encrypted with her private key.
def wikipedia_sign(message, n, d):
return rsa(message, n, d)
# Bob receives both the message and signature. He uses Alice's public key
# to verify the authenticity of the message, i.e. that the encrypted copy,
# decrypted using the public key, exactly matches the original message.
def wikipedia_verify(message, signature, n, e):
return rsa(signature, n, e) == bytes_to_long(message)
def main():
signal.signal(signal.SIGALRM, handler)
signal.alarm(300)
rsa_key = RSA.generate(1024)
public_key = (rsa_key.n, rsa_key.e)
myprint(f"RSA public key: {public_key}")
myprint("Options:")
myprint(f"1 <sig> -- Submit signature for {TARGET} and win")
myprint("2 <msg> -- Sign any other message using wikipedia-RSA")
for _ in range(10):
line = input("> ")
action, data = map(int, line.split())
if action == 1:
if wikipedia_verify(TARGET, data, rsa_key.n, rsa_key.e):
myprint(f"{FLAG}")
exit(0)
else:
myprint(f"Nope. Keep trying!")
elif action == 2:
if data % rsa_key.n == bytes_to_long(TARGET):
myprint(f"Nope. Won't sign that!")
else:
sig = wikipedia_sign(data, rsa_key.n, rsa_key.d)
myprint(sig)
else:
break
if __name__ == "__main__":
main()
任意の復号結果を受け取れてしまうので、
以下のプログラムを使いながらやり取りしました。
solve.py
from Crypto.Util.number import *
N = int(input("N:"))
e = 65537
pow2 = pow(2, e, N)
TARGET = b'I challenge you to sign this message!'
c = bytes_to_long(TARGET)
send = pow2*c % N
print(f'{send=}')
recv = int(input("recv:"))
sig = recv//2 if recv%2 == 0 else (N+recv) // 2
print(f'{sig=}')
TBTL{r3p347_4f73r_m3-d16174l_516n47ur3_15_n07_3ncryp710n}
署名を適当に理解しているせいで、
upsolve したい問題
University Paper [28 solves]
I had to write a scientific paper for one of my university courses describing my scientific role model. I wonder if my professors will be able to figure out who I'm describing...
chall.py
from Crypto.Util.number import *
from redacted import FLAG
ESSAY_TEMPLATE = """
On the Estemeed Scientifc Role Model of Mine
============================================
Within the confines of this academic setting, the individual whom
I hold in highest regard not only boasts an engaging smile but also
possesses a remarkable sense of humor, complemented by an array of
vibrant notebooks.
Yet, it is their distinct quantifiable attribute that stands out
most prominently: their name, when converted into an integer value
and squared modulo %d,
astonishingly results in %d.
Furthermore, the greatest integer that does not surpass the cube root
of the aforementioned squared name equals %d.
This computational detail adds another layer of distinction.
It is likely that by this point, many of you have discerned the identity
of this distinguished role model.
"""
def invpow3(x):
lo, hi = 1, x
while lo < hi:
mid = (lo + hi) // 2 + 1
if (mid**3) <= x:
lo = mid
else:
hi = mid - 1
return lo
N = 13113180816763040887576781992067364636289723584543479342139964290889855987378109190372819034517913477911738026253141916115785049387269347257060732629562571
name_int = bytes_to_long(FLAG)
assert 1 < name_int < N
value_1 = (name_int**2) % N
value_2 = invpow3(name_int**2)
assert (value_2**3) <= (name_int**2)
assert ((value_2 + 2) ** 3) > (name_int**2)
print(ESSAY_TEMPLATE % (N, value_1, value_2))
description.txt
On the Estemeed Scientifc Role Model of Mine
============================================
Within the confines of this academic setting, the individual whom
I hold in highest regard not only boasts an engaging smile but also
possesses a remarkable sense of humor, complemented by an array of
vibrant notebooks.
Yet, it is their distinct quantifiable attribute that stands out
most prominently: their name, when converted into an integer value
and squared modulo 13113180816763040887576781992067364636289723584543479342139964290889855987378109190372819034517913477911738026253141916115785049387269347257060732629562571,
astonishingly results in 11295696938311339473824077083449119515455766620804723271417795055153345707595152245303924808555919718654126902417279389829240793581636850443514989727075129.
Furthermore, the greatest integer that does not surpass the cube root
of the aforementioned squared name equals 25255532621039290870985214051278041571596463385115156541846401100873975663406085683775323107488.
This computational detail adds another layer of distinction.
It is likely that by this point, many of you have discerned the identity
of this distinguished role model.
どうやら
一方で、
TBTL{7h3_0n3_4nd_0nly_--_4ndr3w_W1lL14m
問題は、後半をどうにかして求める過程なのだが、どうもわからない。
Kung Fu Cipher [17 solves]
典型問題っぽいのでサラっと知識を回収したいね。
Discussion