- Windows 11/WSL2
- Ubuntu 22.04 LTS
記事投稿日: 2024年10月13日(日)
最終更新日: 2024年10月13日(日)
かなり遅れてになりますが、今回はAlpacaHack Round 3の問題に挑戦してみます。 今回は最初の問題の「qrime」を解いてみます。 ジャンルとしては「Crypto」とのことです。 Cryptoは暗号関係の問題ということで私はほとんど暗号の知識を持っていませんが、調べつつ頑張ってみます。
AlpacaHack Round 3のトップページAlpacaHackへのリンクはこちら
AlpacaHackのサイトへのリンク2024年9月8日の記事です。
AlpacaHackで始めるCTF入門4:AlpacaHack Round 2 - Simple Loginに挑戦この問題ではprime.tar.gzというファイルが与えられます。 中身を展開してみるとchall.pyとchall.txtの二つのファイルが入っています。 chall.pyを読んでみると素数を使ってflagを暗号化してそうな感じがしました(全然違かったらすみません)。 chall.txtはchall.pyの実行結果を保存したファイルっぽいです。 この2つのファイルからflagを取得する問題のようです。
実行にはCryptoというライブラリが必要そうなのでインストールしておきます。 おまけで下記の記事のとおりに他のライブラリもインストールしてみます。
pip install pycryptodome gmpy2 pwntools z3
参考記事↓
Zenn - Crypto で便利なツールを紹介するとりあえず下記のコマンドで実行してみますが、処理が終わらず、出力結果が返ってきません。
python3 chall.py
どうやらいい感じの乱数(素数?)が取得できるまでループしているっぽいです。
ということで、おそらくchall.pyを自分の環境で実行する必要はなくて、chall.pyを実行した際にchall.txtが結果として返ってきた場合、 flagはどうなるかということを考えれば良さそうです。
chall.pyの内容を箇条書きしてみます。
何にも分からないけど、逆に計算していけばflagが求まる?
chall.txtにはn,e,c,rの結果が保存されている。
おそらくRSA暗号っぽいのでRSA暗号についてChatGPTに聞いてみました。 どうやらnとeが公開鍵、dが秘密鍵と呼ばれるらしいです。 平文のメッセージmをnとeを使って暗号化したものがcで、そのcをd乗してnで割って余りをとると復号化できるらしいです。
つまり、今回はchall.pyにおけるdが求められるとflagが取得できそうです。 そしてdを求めるためにはphiを求める必要があって、phiを求めるためにはpとqを求める必要があります。 おそらくnとrを使ってgen関数を読み解きながらpとqを求めるのかなと思います。 私にはこれ以上難しそうなので一旦やめておきます。
AlpacaHack Round 3のqrimeに挑戦してみました。 これまでの人生では暗号というものにほとんど触れたことがなかったので、 勉強する良いきっかけになった気がします。 問題を解くにはほど遠いですが、ChatGPTを使いながら少しずつ暗号についても勉強できたら嬉しいです。 あとは他の方のwriteupを読んで参考にしてみます。 それでは、また。
2024年10月14日の記事です。
AlpacaHackで始めるCTF入門6:AlpacaHack Round 4 - Simple Flag Checkerに挑戦各シリーズの記事を下記にまとめてあります。