はじめに
久々にWriteupを書きます。あまり時間が取れなかったのと、まだまだ実力不足のせいであまり貢献できなかったのが悔しい限りです。
例によってGitHubに問題を掲載しておきます。
Lithp
My friend gave me this program but I couldn't understand what he was saying - what was he trying to tell me?
名前から分かる通り、Lispで書かれたコードが表示されます。
自分はLispなんて1秒も勉強したことないのでその都度ググる必要があるわけなのですが…
逆にいうと、(C言語なりPythonなり)少しでもプログラミングをやっていれば、1時間ほどで書かれているLispの内容を理解するレベルまでは到達できます。
与えられたLispコードをPythonに直したものを掲載します。Lispと比較してみてください。
この問題に関しては検索力と意地があればなんとかなります。
encrypt = [8930,15006,8930,10302,11772,13806,13340,11556,12432,13340,10712,10100,11556,12432,9312,10712,10100,10100,8930,10920,8930,5256,9312,9702,8930,10712,15500,9312]
reorder = [19,4,14,3,10,17,24,22,8,2,5,11,7,26,0,25,18,6,21,23,9,13,16,1,12,15,27,20]
def enc(plain):
# setfはC言語の変数宣言みたいなもの
uwuth = multh(plain)
uwuth = owo(uwuth)
out = []
# dotimes (ind (length plain) out)は
# indを0から増やしていき, ind == len(plain)になったらoutを出力
for ind in range(len(plain)):
# / (nth ind uwuth) -1について,
# "/ 3 4"は3÷4の意味
# "nth i list"はlist[i]の意味
out.append(-uwuth[ind])
return out
def multh(plain):
# condはif文, 2行下の"t"はelseの意味
if plain == []:
return []
else:
# "cons a b"で2つのリストa, bの結合
# carはリストの先頭を抽出, cdrはリストの先頭以外を抽出
return [whats_this(1-plain[0], plain[0])] + multh(plain[1:])
def owo(inpth):
out = []
redth = reorder
# "do a b c"について
# aは変数の初期値と行う操作(C言語でいうfor(i=0; i<100; i++)の1,3項目)
# bはwhile文を抜ける条件(C言語でいうfor(i=0; i<100; i++)の2項目)と返り値
# cはwhile文内で行う処理
# a : (redth *reorder* (cdr redth))は初期値redth = reorder, 変数に行う操作はcdr
# b : ((null redth) out)はredth == nullになればoutを返す
# c : outにnth (car redth) inpthをappendする
while redth != []:
out.append(inpth[redth[0]])
redth = redth[1:]
return out
def whats_this(x, y):
if y == 0:
return 0
else:
return whats_this(x, y-1) + x
最低限の注釈を書きましたが、正直限界があるので必要に応じて調べてください。
あとはwhat_thisがただの乗算であること、multhが各要素に対して
$x \rightarrow x(1-x)$
を施していること、owoが入力に対して
「入力の19番目, 入力の4番目, …, 入力の20番目」
と、reorderに沿って並び替えているだけであることに気付ければ簡単です。あとはGitHubに上げているdecrypt.pyを参照してください1。
Half and half
Mm, coffee. Best served with half and half!
仕組みはそんなに難しくありません。
flagを前半(milk)と後半(cream)に分けて、各要素に対して XORをとっているだけです。
例えば
flag = 'IamCTFsolver'
なら
milk = 'IamCTF'
cream = 'solver'
for i in range(6):
print(ord(milk[i]) ^ ord(cream[i]))
みたいな感じです。
さて、XORをとった結果が12文字なので当然milkもcreamも12文字で、今回のCTFのflagの形式を考えると
milk = 'actf{???????'
cream = '???????????}'
encrypt = '\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"'
と考えられます。XORの性質上
・milk XOR encrypt = cream
・cream XOR encrypt = milk
なので、creamの最初の5文字、milkの最後の文字はすぐに判明します。
milk = 'actf{??????_'
cream = 'taste??????}'
encrypt = '\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"'
そして、ここからは残念ながら閃き力で全てが決まります。今回の問題設定上、"コーヒーのBest served"がキーになると考えると、
milk = 'actf{coffee_'
cream = 'taste??????}'
と考えるのが自然でしょう(cが大文字の可能性もお忘れなく)。
こう予想してcreamを求めると
milk = 'actf{coffee_'
cream = 'tastes_good}'
と、意味の通じる文章が導き出せます。actf{coffee_tastes_good}入力すると無事正解。
Runes
The year is 20XX. ångstromCTF only has pwn challenges, and the winner is solely determined by who can establish a socket connection first. In the data remnants of an ancient hard disk, we've recovered a string of letters and digits. The only clue is the etching on the disk's surface: Paillier.
$e$ではなく$g$が与えられているのでRSAではないようです(もし$e$だとしても流石に大きすぎます)。
$n$は素因数分解できるとして、そこから先は進まないのでとりあえず"Paillier"でググってみるしかなさそうです。
…Paillier暗号なるものがヒット。$g$も使われているので、Wilipediaに掲載されている通りに復号すれば良さそうです。
まずは$n$を素因数分解しておきましょう。
$p$ = 310013024566643256138761337388255591613
$q$ = 319848228152346890121384041219876391791
さて、復号コードを書いていきます。
import math
import codecs
n = 99157116611790833573985267443453374677300242114595736901854871276546481648883
g = 99157116611790833573985267443453374677300242114595736901854871276546481648884
c = 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869
p = 310013024566643256138761337388255591613
q = 319848228152346890121384041219876391791
_lambda = (p-1) * (q-1) // math.gcd(p-1, q-1)
def L(u):
return (u-1) // n
m = (L(pow(c, _lambda, n**2)) // L(pow(g, _lambda, n**2))) % n
codecs.decode(('%x'%m), 'hex_codec')
ここまではすんなり2いけました。ただ、このコード動かないのです…。
問題は、m = 1であること。もっというと、$L(c^\lambda\ {\rm mod}\ n^2)$が$L(g^\lambda\ {\rm mod}\ n^2)$で割り切れません。
色々検索した結果、Wikipediaに載っている
$$\frac{L(c^\lambda\ {\rm mod}\ n^2)}{L(g^\lambda\ {\rm mod}\ n^2)}\ {\rm mod} \ n$$
は、所謂分数としての計算ではなく、
$$L(c^\lambda\ {\rm mod}\ n^2) \cdot \left(L(g^\lambda\ {\rm mod}\ n^2)\right)^{-1}\ {\rm mod} \ n$$
と、$n$を法とするモジュラ逆数$\left(L(g^\lambda\ {\rm mod}\ n^2)\right)^{-1}$をかける操作であることが判明しました。
このモジュラ逆数は拡張Euclid互除法で求められるので、以上をまとめて正しいコードは以下のようになります。
import math
import codecs
n = 99157116611790833573985267443453374677300242114595736901854871276546481648883
g = 99157116611790833573985267443453374677300242114595736901854871276546481648884
c = 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869
p = 310013024566643256138761337388255591613
q = 319848228152346890121384041219876391791
_lambda = (p-1) * (q-1) // math.gcd(p-1, q-1)
def L(u):
return (u-1) // n
# 拡張Euclid互除法
def egcd(e, n):
x, y, u, v = 0, 1, 1, 0
while e != 0:
q, r = n // e, n % e
m, n = x - u * q, y - v * q
n, e, x, y, u, v = e, r, u, v, m, n
return x
m = L(pow(c, _lambda, n**2)) * egcd(L(pow(g, _lambda, n**2)), n) % n
codecs.decode(('%x'%m), 'hex_codec')
actf{crypto_lives}が導けました。
Paint
This amazing new paint protocol lets artists share secret paintings with each other! Good thing U.S. Patent 4200770 is expired.
今回の1番の収穫かもしれません。
キーワードとして"U.S. Patent 4200770"がありますが、残念ながら特に有用な情報は得られません。
ソースコード自体は難しいものではありません。簡略のため
$g$ = base
$x$ = secret(未知)
$h$ = my_mix
$G$ = palette
と表記すると、
$$g^x = h\ ({\rm mod}\ G)$$
なる$x$を求めろ、との問題です。一般にこれは離散対数問題3と呼ばれ、解くのが非常に難しいのですが、今回は
$$g^n = 1 \ ({\rm mod}\ G)$$
なる最小の$n$(これを$g$の位数と言います)が
$$n = 2^{2045}$$
のように簡単な素因数を持つ場合のみPohlig-Hellmanのアルゴリズムを用いることができます。
対応するアルファベットは上のリンク先と一致させてありますので、今回は$p = 2, e = 2045$となります。
from Crypto.Util.number import inverse
# base
g = 13489305024865487703110255658234329747698118206959778644688156332043783846078839120693894255527894489531905012244713117142764166452312133019772171674466933769775907460046497284522592167536594047800489828714315435570429416637425443402332599055774982796405757075108551322778712959943658831605397635195107786224617525627358659165255604556424206194207190437525742567525338826878962081515333896433312311548844614323540250054093970082337500580573165008440265840792908334486258260848163001490152587781983042546491301026074736907693887630347258892882871059741621049169714319440564952700454580681894452760215968494428411686329
# palette
G = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656
# my_mix
h = 6870295205307030503255600311283969014496436297715066273709495591567561187646528069669895230912327862244474990612611625088862250315706633708998214109152824455738719595737772769297517386968692628228327225922261219083693899105983726637012353264168761696183327692619506267951701511870035935612090359086376808592001973358166067468618577312983514388332736591060901174314042634365304017788649960016991442596975922402288221898367955532116456798868804571091463566329706023967280838744359633963847966790121312196824818606244189274966061324393424041211903396020720341163472399763951106703068172772579049891895580785347369093113
p = 2
e = 2045
# Pohlig-Hellmanのアルゴリズム
x = [0]
gamma = pow(g, p ** (e-1), G)
for k in range(e):
h_k = (pow(inverse(g, G), x[k], G) * h) % G
h_k = pow(h_k, p ** (e-1-k), G)
if h_k == gamma:
d_k = 1
else:
d_k = 0
x.append(x[k] + (p ** k) * d_k)
# secret
x[-1]
本当はここからshared_mixやimageを求めたりと、もう少し処理をしなければいけないのですが、ここからは簡単なので割愛します。