Lexington Informatics Tournament CTF 2021 writeup
久しぶりにwriteupを書きます。サボっていたわけではなく、一問も解けないCTFが続いたんです…。
Result
Writeup
7 More Caesar Salads
Here’s an easy Crypto problem, try to decipher mshn{Dlsjvtl_Av_Jyfwavnyhwof}
問題名からCaesar暗号のようですね。以下のサイトで試してみたらROT19で上手くいきました。
flag{Welcome_To_Cryptography}
Zzz
Oh no, somebody shuffled the alphabet, can you help us restore the message? Note that the flag is not wrapped with flag{}, so you will have to do that yourself.
ファイル：zzz.txt
アルファベットをシャッフルしたと問題文にあるので、換字式暗号です。quipquipの出番です。
ここに、zzz.txtの内容を入れてsolveをクリックすると最初の文章がflagになります。flag{}で囲ってsubmitします。
flag{HOW_DO_YOU_KNOW_YOU_ARE_NOT_SLEEPING}
RSA Improved
The standard RSA only uses 2 prime factors, way too insecure. Let’s improve it by using more factors! More is better, ...right?
ファイル：rsa_improved.py, output.txt
問題文から、multiple primes RSAであることが予測できます。トーシェント関数φ(n)は(nを構成する素数-1)の積になります。nをfactorDBなどに投げると簡単に素因数分解できました。予想通り、素数が3個以上でした。問題ファイルからも分かりますね。
from Crypto.Util.number import * n = (省略) e = 65537 ct = (省略) N = [2151055861, 2319991937, 2341310833, 2391906757, 2448497717, 2493514393, 2586983803, 2758321513, 2784469417, 2816940109, 2865965429, 3092165243, 3218701459, 3438516511, 3526137361, 3663803701, 3673658161, 3789550043, 3866428117, 3919632263, 4147385899] phi = 1 for nn in N: phi *= (nn-1) d = inverse(e,phi) m = pow(ct,d,n) print(long_to_bytes(m))
flag{rsa_1s_4_pr3tty_imp0rt4nt_crypt0_4lg0r1thm}
Geometry is Fun!
We all love GEOMETRY, let's reminisce of all the times our teacher told us to find how large a certain figure is! Remember, Geometry teachers are bad at encrypting messages so the encryption method is not hard :D
(Note that the graphs may not be precise - only use angles/lengths notated in the diagrams)
ファイル：GeoIsFun.png
何だこの問題は。
問題文を読むと、とりあえず面積を求めよとのこと。やってみましょう。
左上から右に、上から下に(A) ~ (H)と名付けます。
(A)
基本問題ですね。
3 × 6 ÷ 2 = 9
(B)
正三角形で一辺の長さが分かっています。その長さが2重根号になっています。
正三角形の高さは、(辺の長さ) × (√3/2) です。
√(16√3) × { (√(16√3) ) × (√3/2) } ÷ 2
= { √(16√3) × √(16√3) } × (√3/2) ÷ 2
= 16√3 × (√3/2) ÷ 2
= 16 × 3 ÷ 2 ÷ 2
= 12
なんと整数になりました。他の問題もそうなるのかなと予想。
(C)
(B)と考え方は同じですね。
√(10√3) × { (√(10√3) ) × √3 } ÷ 2
= { √(10√3) × √(10√3) } × √3 ÷ 2
= 10√3 × √3 ÷ 2
= 10 × 3 ÷ 2
= 15
(D)
(A) と同じですね。
22/3 × 6 ÷ 2 = 22
(E)
これもまた簡単ですね。
1 × 10 ÷ 2 = 5
(F)
三辺の長さだけが分かっている二等辺三角形ですね。
ヘロンの公式を使います。
ヘロンの公式 面積S = √(s×(s-a)×(s-b)×(s-c) ) ただし、s = (a+b+c)/2, a,b,c は辺の長さ
これを適用します。
s = ( 5√2 + 5√2 + 2)/2 = 5√2 + 1 S = √(s×(s-a)×(s-b)×(s-c) ) = √( (5√2 + 1) × (5√2 + 1 - 5√2) × (5√2 + 1 - 5√2) × (5√2 + 1 - 2) ) = √( (5√2 + 1) × (5√2 - 1) ) = √( (5√2)×(5√2) - 1×1 ) = √(50 - 1) = 7
(G)
三角形の面積を求めるのに、三角関数を使った方法あったなと思いググる。
1/2 × 4 × 5 × sin30 = 5
(H)
直角二等辺三角形で、斜辺の長さだけ分かっています。
(一辺の長さ) = 2√15 × √2/2 = √30 (面積) = √30 × √30 ÷ 2 = 30/2 = 15
復号
以下の値が出揃いました。
9, 12, 15, 22, 5, 7, 5, 15
幾何学の先生だから暗号化方式はそんなに難しくないよ、と問題文にあります。
最大値が22であるので、1~26がa~zに対応しているのでは？とエスパー。復号してみると意味のある文になったビンゴ。
flag{ilovegeo}
Scottish Flag
Was is it Scottish or British? Oh who remembers these days
ファイル：scottish_flag.py, output.txt
scottish_flag.pyを読み、何が出力されているか見ると以下の式が成り立ちます。
t0, t1, t2 : 出力 ct1, ct2 : 求めたいflag a0, a1 : プログラム内の値。a1は未知。 ct1^2 + (ct2-a0)^2 = t0 ・・・ (a) (ct1-a1)^2 + ct2^2 = t1 ・・・ (b) (ct1-a1)^2 + (ct2-a0)^2 = t2 ・・・ (c)
未知数がct1, ct2, a1の3つに対し3式あるので、これは式同士を足し引きすれば求められますね。
ct2を求める
(b) - (c) ct2^2 - (ct2-a0)^2 = t1 - t2 2×a0×ct2 - a0^2 = t1 - t2 ct2 = (t1-t2+a0^2) / 2×a0
ct2が求められました。これをlong_to_bytes()すると、
b'mak35_g00d_pro6I3m}'
となり、方向性は間違っていないようです。
ct1を求める
(a) ct1^2 + (ct2-a0)^2 = t0 ct1 = √(t0 - (ct2-a0)^2 )
右辺のルート内を計算し、平方数であることを確認。二乗根を取ってlong_to_bytes()するとflagの前半が出ました。
b'flag{6r1t15h_cr0s5_'
from Crypto.Util.number import * import gmpy2 t0 = 11167218166350596634324970518743041384610511755703179147618262518561344714067317278672955466 t1 = 11167218166350596634324970522379402989880404344356627706412007661522873314144716029510966061 t2 = 11167218166350596634324970517500867796567936885101366588743135261789294824144716029510966061 a0 = 1000000000000000000 c2 = (t1-t2+a0*a0) // (2*a0) print(long_to_bytes(c2)) cc1 = (t0-pow(c2-a0,2)) print(cc1) c1, ch = gmpy2.iroot(cc1,2) assert ch print(long_to_bytes(int(c1))) flag = long_to_bytes(int(c1)) flag += long_to_bytes(c2) print(flag)
flag{6r1t15h_cr0s5_mak35_g00d_pro6I3m}
Leftovers
Leftovers are bad, but I guess at least they help the environment by not wasting food.
ファイル：Leftovers.py, output.txt
Leftovers.pyが少し複雑ですが、読み解いて行きましょう。
変数gはPRNGクラスのインスタンスで、そのフィールドの一つであるseedにはflagを数値にしたものが入ります。
配列resには、1~4e10内で乱数を生成させ、その値未満の素数でseedを割った余りがどんどんappendされ、長さは12です。これはoutput.txtにあります。
はい、flagを特定するには中国剰余定理を用います。
生成する乱数ですが、最初にシードを1337として初期化しているので同じものを生成できます。中国剰余定理はsympyにあるので、それを使えば楽勝です。
from sympy.ntheory.modular import crt import random from Crypto.Util.number import * import sympy import math val = [16751036754, 7441743891, 13537409447, 12455208971, 16901669565, 15060041617, 15538665605, 192375025, 2176355740, 21877084789, 3184436468, 13214581420] random.seed(1337) mod = [] for i in range(len(val)): mod.append(sympy.prevprime(random.randint(1,4e10))) flag, MOD = crt(mod,val) flag = int(flag) print(long_to_bytes(flag))
なんとこれでは意味ある文字列になりませんでした…。思い違いがあるのかと思ったけど、それではなさそう。
Leftovers.pyに怪しげなassert文がありました。
assert(math.log10(ct) <= 128)
上のプログラムで求めているのは、mod[i]で割ると余りがval[i]になる最小値を求めています。何も最小値が答えとは限りません。求めた最小値に、Π mod[i] (= mod[0]×mod[1]×...×mod[n-1]) をどんどん足していって、long_to_bytes()してb"flag"が含まれていたらそれを出力してプログラムを終わらせます。
from sympy.ntheory.modular import crt import random from Crypto.Util.number import * import sympy import math val = [16751036754, 7441743891, 13537409447, 12455208971, 16901669565, 15060041617, 15538665605, 192375025, 2176355740, 21877084789, 3184436468, 13214581420] random.seed(1337) mod = [] for i in range(len(val)): mod.append(sympy.prevprime(random.randint(1,4e10))) flag, MOD = crt(mod,val) flag = int(flag) while math.log10(flag) <= 128: FLAG = long_to_bytes(flag) flag += MOD if b"flag" in FLAG: print(FLAG) break
flag{ch1nese_f00d_l3ft0v3r_th30r3m_1s_v3ry_d3l1c10u5}
Problems&Solver
おわりに
最近研究の方も忙しくなり、CTFに参加しても最初の一問がすぐ解けないとそっとPCを閉じていました。CTFとの両立頑張りますが、期待はしないでください(笑)
久しぶりにwriteup書いたので、いつもの形式が違うとかあったらすみません
