きゅうり。

主にCTF関係のことを書いていく気がします

SECCON2016 Qual Alpha Complex1 writeup

CTF crypto

SECCON2016予選のcrypto 300の問題、Alpha Complex1のwriteupです。

4月からに向けてm1z0r3用のcrypto for beginnersみたいな記事（チーム用なので公開予定なし。たぶん。）を書いてたんですが、執筆にあたって色々調べてたら「これAlpha Complex解けんじゃね？」みたいな感じになったのでやってみたら解けました。 

12月の記憶を呼び戻して書いてるので、問題の説明とか間違ってたらすいません。

 

問題

問題文は省略します。Complex.pyとserver.pyという2つのファイルが渡されます。

実はやっていることは単純(?)で、RSA暗号を複素平面上で定義しています。フラグをx座標、こちらから送った値をy座標として、{\displaystyle C \equiv (x+y*I)^e \pmod{N} }を計算した結果が返ってきます。Nとeはわかっていて、今回のeは0x1337です。

なお、便宜上x座標y座標と呼んでいますが正しいかは謎なのでそこは目を瞑ってください。

 

解法

暗号文Cの式を展開すると、以下のようになります。

{\displaystyle (x^e + a_{e-1}Ix^{e-1} + a_{e-2}(-1)x^{e-2} + ... - C)  mod  N = 0 }

この式には実部と虚部があるのでわけて式を定義してみます。

{\displaystyle g_r(x) = (x^e + a_{e-2}(-1)x^{e-2} + ... - C_x)  mod  N }

{\displaystyle g_y(x) = (a_{e-1}Ix^{e-1} +  ... - C_y)  mod  N }

この2つの式は、xにフラグ(mと定義)が入るとき当然ながら0となります。つまり言い換えると、{\displaystyle g_r(x),g_i(x)=0}はmを根に持ちます。なので以下のように表現できます。

{\displaystyle g_r(x)=(x-m)G_r(x)}、{\displaystyle g_i(x)=(x-m)G_i(x)}

これを見ると、2式の最大公約式をとればx-mが出てきてフラグを得ることができそうです。

 

というわけで実際に試します、が、いきなり本番の値でやると大変なのでまずは自分で用意したフラグと暗号文でやります。なおここではe=5にして暗号化してます。

これを実行してみるとちゃんと平文を得ることができました。なので後は本番用の値でやるだけなのですが、21~26行目を見てわかる通り展開した式をベタ書きしてます。本番のeでこれをやると0x1337乗なのでとんでもないことになります。

苦肉の策として、

  1. expandしたものを一旦テキストとしてファイルに出力
  2. 出力したものを読み込み、文字列として実部虚部に分割（虚部のIは削除）
  3. z_real=`実部` z_imag=`虚部`みたいな形でまたファイルに出力（expとする）
  4. 先ほどのsolverの24行目まで書いたものを用意（solver.sage）
  5. cat exp >> solver.sage; echo 27行目 >> solver.sage; echo 28行目 >> solver.sage

としました。

solver.sageは63MBになりました。

そんなものを貼るつもりは起きないですが、先ほどのsolverのパラメータを書き換えただけでやってる処理は同じです。

というわけでこれを実行することで無事フラグを得ることができました。

SECCON{3907c554839a6462b920f55274c159eea1949086}

 

あとがき

Alpha Complex2のほうはまだ問題すら見てないです...

あとこれ解いてたからcrypto for beginnersも書いてないです。許して。