はじめに

おはようございます！
ワンキャリアのセキュリティチームでエンジニアをやっている蟹です。

今回は、先日行われた（といっても2023年9月16日、気づけば結構時間が経ってしまいましたが。。） SECCON CTF 2023 予選にソロ＆初参加してみたので、writeupを書いてみよう！といった所存です。

自分自身が初心者ということもあるので、当記事は「SECCON CTFってどんな感じなんだろう？」と思っている初心者の方の参考になることを目標にしたいと思います。

SECCON CTF 概要

「そもそもCTFって何？」という話については、以前記事を書いているのでこちらをご覧ください。

次に「SECCONって何？」についてですが、Security Contestの略で、日本最大級のCTFの一つです。公式サイトでの説明としては下記のように書かれています。

「SECCON」 ではカンファレンスやワークショップなどのほかに、攻撃・防御両者の視点を含むセキュリティの総合力を試すハッキングコンテスト「CTF (Capture the Flag)」や、あるテーマにあわせてプログラムを作成して披露するプログラミングコンテスト「ハッカソン」などがあります。

つまり、「国内最大級のCTF」だと思っていただければ大きな間違いはないかと思います。

SECCONのサイトへアカウント登録後、ログインすると、以下画像のように問題がずらっと並んでおり、好きなものを選択して順に解いていきます。

plai_n_rsa

その中でも今回は、crypto分野の「plai_n_rsa」について取り上げます。
問題を押下すると、以下のようにモーダルが出現し、問題の概要やファイルへのリンクが設置されています。
「dist.tar.gz」をダウンロードし、問題を解いていきましょう！

問題設定

「dist.tar.gz」をダウンロードして展開すると、「problem.py」と「output.txt」が入っています。
RSA暗号において、$${e , d, \rm{hint} = p+q}$$ と暗号文 $${c}$$ が既知の状態から、平文 $${m}$$ を求めよ。という問題のよう。

problem.py

import os


from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes


flag = os.getenvb(b"FLAG", b"SECCON{THIS_IS_FAKE}")
assert flag.startswith(b"SECCON{")
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
hint = p+q
c = pow(m, e, n)


print(f"e={e}")
print(f"d={d}")
print(f"hint={hint}")
print(f"c={c}")

output.txt

e=65537
d=15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793
hint=275283221549738046345918168846641811313380618998221352140350570432714307281165805636851656302966169945585002477544100664479545771828799856955454062819317543203364336967894150765237798162853443692451109345096413650403488959887587524671632723079836454946011490118632739774018505384238035279207770245283729785148
c=8886475661097818039066941589615421186081120873494216719709365309402150643930242604194319283606485508450705024002429584410440203415990175581398430415621156767275792997271367757163480361466096219943197979148150607711332505026324163525477415452796059295609690271141521528116799770835194738989305897474856228866459232100638048610347607923061496926398910241473920007677045790186229028825033878826280815810993961703594770572708574523213733640930273501406675234173813473008872562157659306181281292203417508382016007143058555525203094236927290804729068748715105735023514403359232769760857994195163746288848235503985114734813

RSA暗号のおさらい

では解く前にまず、簡単に今回のテーマであるRSA暗号について復習しておきます。

鍵の準備
・ $${p, q}$$ として十分大きい素数を取る
・ $${e = 65537 = 2^{2^4} -1}$$ とおく（公開鍵その1）
・ $${n = pq}$$ とおく（公開鍵その2）
・ $${ d = e^{-1} \mod (p-1)(q-1) }$$ とおく（秘密鍵）
平文 $${m}$$ を暗号化
・ $${c = m^e \mod n}$$
暗号文 $${c}$$ の復号
・ $${m = c^d \mod n}$$

以上がRSA暗号の暗号化・復号の仕組みでした。

通常のケースでは、公開鍵 $${e, n = p * q}$$ から秘密鍵 $${d}$$ の推測が困難であることが安全性の担保となっています。
今回は一風変わった設定で、 $${e , d, \rm{hint} = p+q}$$ が既知の状態から暗号文 $${c}$$ を復号することができますか？という問題です。（秘密鍵 $${d}$$ や $${\rm{hint} = p+q}$$ は通常知り得ない情報です。）

解法と解答例

以下ネタバレ？になりますので、自力で考えてみたい方は一度ここでストップしてください！

Step1. 大方針

$${(p-1)(q-1) = pq - (p+q) + 1 = n - \rm{hint} + 1}$$ と、今回のポイントとなりそうな $${n}$$ や $${\rm{hint}}$$ たちが一緒に現れる秘密鍵の式に注目しましょう。

秘密鍵の定義より

$$
\begin{array}{}
d &=& e^{-1} \mod (p-1)(q-1) \\\
de &=& 1 \mod (p-1)(q-1) \\\
de - 1 &=& 0 \mod (p-1)(q-1)
\end{array}
$$

modをバラして（ユークリッドの互助法によりある $${x}$$ が存在し）

$$
\begin{array}{}
de - 1 &=& x(p-1)(q-1) \\\
de - 1 &=& x(pq - (p+q) + 1) \\\
de - 1 &=& x*(n - \rm{hint} + 1) \\\
n &=& (d*e-1)/x + \rm{hint} - 1
\end{array}
$$

これで $${n}$$ の形が絞れたので、
$${ n = (d*e-1)/x + \rm{hint} - 1 }$$
に対し、未知整数 $${x}$$ に関するループを回せば良い。

Step2. xの範囲を絞る

$${x}$$ についてのループを回す範囲を考えると、 $${x}$$ はユークリッドの互除法で取ってきており $${d*e-1}$$ 以下であることは分かります。それでもいいのですがちょっと数字が大きいので少し工夫して候補を減らしましょう。
（$${d=15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793}$$ がとても大きかったことを思い出してください。）

「 $${x}$$の範囲は、$${x \leq e}$$とできる。」
証明：$${d}$$ は $${\mod (p-1)(q-1)}$$ で取っているため $${d < (p-1)(q-1)}$$ なので、 $${x*(p-1)(q-1) = d*e + 1}$$ より $${x < e + 1}$$ である。
「 $${d*e - 1}$$ が $${4x}$$ の倍数である場合のみ調べればよい。」
証明：$${de - 1 = x(p-1)(q-1)}$$ において、$${p, q}$$ が奇数なので右辺は $${4x}$$ の倍数となっている。

Step3. コードを書く

上記Step1、Step2をコードに落とし込みます。
最後に long_to_bytes をお忘れなく！

from Crypto.Util.number import long_to_bytes


e=65537
d=（略）
hint=（略）
c=（略）


for x in range(1,e):
 if (d*e-1) % (4*x) == 0:
   n = (d*e-1)//x + hint - 1
   print(f"m={ long_to_bytes(pow(c, d ,n)) }")

こちらを走らせると

e=65537
d=15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793
hint=275283221549738046345918168846641811313380618998221352140350570432714307281165805636851656302966169945585002477544100664479545771828799856955454062819317543203364336967894150765237798162853443692451109345096413650403488959887587524671632723079836454946011490118632739774018505384238035279207770245283729785148
c=8886475661097818039066941589615421186081120873494216719709365309402150643930242604194319283606485508450705024002429584410440203415990175581398430415621156767275792997271367757163480361466096219943197979148150607711332505026324163525477415452796059295609690271141521528116799770835194738989305897474856228866459232100638048610347607923061496926398910241473920007677045790186229028825033878826280815810993961703594770572708574523213733640930273501406675234173813473008872562157659306181281292203417508382016007143058555525203094236927290804729068748715105735023514403359232769760857994195163746288848235503985114734813

こんな感じでバーっと出力されます。（こちらでの出力は94行となり、 $${e = 65537}$$ 行よりもかなり削減できています）

やってみての学び

今回、当日に解けたのは1問だけだったのですが、取り組んだ問題に後日改めてじっくり再チャレンジしたり、他の方のwriteupを読んで参考にしたり、外から見ているだけの学習よりも浸透度が一段二段高く感じました。

「やったことないし全く歯が立たなそう。。。」「一緒にやる知人もいないし。。。」といった方でも意外と簡単に登録できますし、1問も解けずともきっと得られるものがあると思います。皆さんのチャレンジを応援しています！一緒に一歩ずつやってみましょう！

おわりに

ここまでお読みいただき大変ありがとうございました。

予選が終わってからすぐ書こう書こうと思っているうちに、気づけばSECCON本番も過ぎ、年も明けてしまいました。。。writeupはCTF後すぐに出しましょう。。。（自戒です。）

また、最後になりますが、今回の作問者である kurenaif さんの解説動画もYouTubeにアップロードされておりますので、こちらも是非ご覧ください。難易度「warmup」（最も簡単）のタグがついた問題たちについて、非常に分かりやすく解説されています。

ワンキャリアでは、一緒に働くエンジニアを募集しています。
本記事を読んで少しでもご興味持っていただけた方は、ぜひご連絡ください！

▼ワンキャリアのエンジニア組織のことを知りたい方はまずこちら

▼カジュアル面談を希望の方はこちら

hrmos.co エンジニア／カジュアル面談

株式会社ワンキャリア 東京都渋谷区 ほか0箇所 フルタイム

募集要項をみる

▼エンジニア求人票