AlpacaHackで始めるCTF入門5：AlpacaHack Round 3 - qrimeに挑戦

記事投稿日: 2024年10月13日（日）

最終更新日: 2024年10月13日（日）

はじめに

概要

かなり遅れてになりますが、今回はAlpacaHack Round 3の問題に挑戦してみます。今回は最初の問題の「qrime」を解いてみます。ジャンルとしては「Crypto」とのことです。 Cryptoは暗号関係の問題ということで私はほとんど暗号の知識を持っていませんが、調べつつ頑張ってみます。

AlpacaHack Round 3のトップページ

AlpacaHack

AlpacaHackへのリンクはこちら

AlpacaHackのサイトへのリンク

私のCTF環境

Windows 11/WSL2
Ubuntu 22.04 LTS

前回の記事

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を取得する問題のようです。

chall.pyを実行してみる

実行にはCryptoというライブラリが必要そうなのでインストールしておきます。おまけで下記の記事のとおりに他のライブラリもインストールしてみます。

pip install pycryptodome gmpy2 pwntools z3

参考記事↓

Zenn - Crypto で便利なツールを紹介する

とりあえず下記のコマンドで実行してみますが、処理が終わらず、出力結果が返ってきません。

python3 chall.py

どうやらいい感じの乱数（素数？）が取得できるまでループしているっぽいです。

flagの取得方法を考えてみる

ということで、おそらくchall.pyを自分の環境で実行する必要はなくて、chall.pyを実行した際にchall.txtが結果として返ってきた場合、 flagはどうなるかということを考えれば良さそうです。

chall.pyを読み解いてみる

chall.pyの内容を箇条書きしてみます。

nextPrime関数：入力n以上の素数を返しそう
gen関数：変数p,q,rを生成しそう
r：ランダム整数
q：ランダム素数
p：rとqから生成した素数っぽい（本当に？）
flag：文字列をバイト列に変換したもの？
m：flagを整数に変換したもの？（long intかな？）
n：p*q
phi：(p-1)*(q-1)、dを求めるのに使ってるけど、ヒント的なもの？
e：65537
d：pow(e,-1,phi)、使ってなさそうだけど、ヒント的なもの？
c：pow(m,e,n)、これがflagを暗号化したもの？、flagを65537乗してからnで割った余りをとっているらしい

何にも分からないけど、逆に計算していけばflagが求まる？

chall.txtにはn,e,c,rの結果が保存されている。

n=200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e=65537
c=77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r=30736331670163278077316573297195977299089049174626053101058657011068283335270

考えたこと

私はmが知りたい。cを求める計算において、cとeとnは与えられているから、そのcとeとnを使ってmを求めるのか。それともchall.pyには何かしら暗号化のミスがあってそこをいい感じにつくとflagが取得できるのか。ミスの場合はnextPrime()とgen()が怪しそう。
rも与えられているが何に使うんだろう。nは素数pと素数qの掛け算でできているので、めちゃくちゃコンピュータが頑張ったらpとqは求められそう。rとpとqが分かったところでそれが何に繋がるのか分からない。

ChatGPTに聞いてみる

おそらく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を読んで参考にしてみます。それでは、また。