nahamcon ctf Raspberry Homecooked Write up
皆さん、こんにちは！ Ken.Sです！
今回もCTFのWrite upを書いていこうと思います。
Raspberry
与えられたprompt.txtはこうなってます。(前回の記事にはこういうの載せ忘れてました)
n = 7735208939848985079680614633581782274371148157293352904905313315409418467322726702848189532721490121708517697848255948254656192793679424796954743649810878292688507385952920229483776389922650388739975072587660866986603080986980359219525111589659191172937047869008331982383695605801970189336227832715706317
e = 65537
c = 5300731709583714451062905238531972160518525080858095184581839366680022995297863013911612079520115435945472004626222058696229239285358638047675780769773922795279074074633888720787195549544835291528116093909456225670152733191556650639553906195856979794273349598903501654956482056938935258794217285615471681
とりあえずRSAでないかとnを素因数分解してみます。どうせだめでしょうけど…。
と思ったら出来たんですこれが。けど素数2つの積ではなく、素数32個の積でした。こういう時はMulti-Prime RSAですね。Multi-Prime RSAは通常のRSAと何が違うかというとほとんど変わりません。秘密鍵dを手に入れるために必要なφ(n)をどう求めるか、くらいです。
そもそもオイラー関数とは、φ(n) = 1~nまでの整数の内, nと互いに素である整数の個数 です。nが素数である場合、1~n-1の全ての整数と互いに素であるのでφ(n)=n-1です。また、このオイラー関数は乗法的であるので、φ(nm) = φ(n) * φ(m)とできます。なので、通常のRSAの場合、n=pqなのでφ(n) = φ(p) * φ(q) = (p-1) * (q-1)となるのです。詳しくはWikiで。
では、nが3個以上の素数の積である場合はその(素数-1)の積を求めればいいのです。
n = Πp_i とすると、φ(n) = Π(p_i-1)です。
φ(n)が求まれば、あとはいつも通りです。
flag{there_are_a_few_extra_berries_in_this_one}
RSAのP(rime)がvery(berry)存在しているよ…？という意味なのでしょうか。
Homecooked
この問題は、自分の解法よりも同じ研究室のメンバーの解法がキレイでびっくりしました。
与えられたdecrypt.pyはこうなっています。関数a,bについてみると…
関数a : 素数判定
関数b : 回文判定
関数aが素数判定なのでsympy.isprimeに置き換えたり、i*i>nでbreakすれば簡単に解けます。
が、きれいな解法は関数a,bを判定しているif文の順番を変えるだけでした。
時間的計算量で考えると
関数a : O(N)
関数b : O(logN) 底:10
であるので関数bが通った整数だけ関数aに投げる方が早く終わります。
flag{pR1m3s_4re_co0ler_Wh3n_pal1nDr0miC}
今回はこの2問を紹介しました！
それでは！
See you next time!
