最近の解いたCTFまとめ

Harekaze mini CTF 2021

・ first exam
・ sage training
・ mulmulmulti-prime rsa
・ lost key

hxp CTF 2021

・ gipfel

Harekaze mini CTF 2021

###first exam
$ct = flag \otimes key$なので，$ct\otimes key = flag \otimes key\otimes key$で求まりますね.base64に注意して戻すと
HarekazeCTF{OK_you_can_join_wizardry_school}
これで無事に魔法学校に入学できました!
###sage training
$F_p$の行列を$e$乗したもの暗号文としています

{\begin{pmatrix}
p^e & 0 \\
0 & flag^e\\
\end{pmatrix}}
={\begin{pmatrix}
p & 0 \\
0 & flag\\
\end{pmatrix}}^e

より$n=pq$を考えると$gcd(n,p^e)=p$となるので$p,q$が求まります.
後はRSAぽく $ed\equiv 1\ mod (\varphi(n))$として
$pt \equiv flag^d \ mod(n)$ で求まります!

HarekazeCTF{which_do_you_like_mage_or_sage?}
個人的にはmageの方が好きですね!

###mulmulmulti-prime rsa

通常のRSAの素数と$flag$の十進の数以下の素数をかけ合わせたものをNとしています.
ここで，慣れている人だと素数多い→CRTかな?となりそうですけど，謎に

problem.py

from sympy.ntheory.modular import crt

となればCRTかぁってなりますね

solve.py

list1=[]
list2=[]
while num< 1000:
    if N%num==0:
        N =N// num
        list1.append(num)
        d = gmpy2.invert(e,num-1)
        list2.append(pow(c,d,num))
        print(num)
    num += 1

print(list2,list1)

print(long_to_bytes(crt(list2,list1)))

これでおしまい!

HarekazeCTF{Small_prime_numbers_give_a_large_amount_of_information}

###lost key

さぁラストです!
$flag$の文字列を一文字ずつUTF-8に変換しそれを基準にして$e$乗しています．

f(x) =  \left\{
\begin{array}{ll}
m[0]^e \equiv ct[0]& mod(n) \\
m[1]^e \equiv ct[1]& mod(n)
\end{array}
\right.\\
= \left\{
\begin{array}{l}
m[0]^e - ct[0] = k_0n \\
m[1]^e - ct[1] = k_1n
\end{array}
\right.\\

よって，$gcd(m[0]^e - ct[0],m[1]^e - ct[1])=n $ ( $ k_0,k_1 $ が互いに素なため)
$n$が求まります．ここで，mは0x20から0x7fまでの値が取れるのですべて$e$乗して合致するか調べていくと答えが出ます．
HarekazeCTF{Can_you_Recover_with0ut_the_public_4nd_pr1vate_keys!?}

###感想
タイムアタック的な感覚で面白かったです．解き方はわかるけどコードが書けない人からすると3つ目で少し事故りました...要精進...

##hxp CTF 2021
ついでなんで書いちゃいます

###gipfel

\begin{align}
password &= random\\
g &= H(password)\\
privA &\equiv random\\
pubA &\equiv g^{privA} \ mod(q)\\
shared &\equiv pubB^{privA} \  mod(q)\\
verA &\equiv g^{shared^3} \ mod(q)\\
verB &\equiv g^{shared^5}\ mod(q)\\
\end{align}

出現する変数をまとめてみました．ここで行うことは$varB, password, shared$の導出です．
私たちが行えることは$pubB$の値の設定，$pubA,varA$の値の確認です．
ここで，$pubB$の値を決めることで$shared$→$verA$→$verB$と順に値が決まっていきます．
強引に$n$乗根を求めてもいいのかもしれませんが，$pubB=q-1$とすることで$shared=-1 \ or \ 1$となり，更に進めて$verA=verB=g^{-1}\ or \ g$となるため簡単に$varB, shared$を導出でき残りの$password$は$[0,10^6]$の間にあるためブルートフォースでも短時間で求めることができます．
後は$key$をハッシュ関数から求めAESを解くとflagが得られます．
hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345}