本記事について
2021年5月22日と2021年5月23日に開催された「SECCON Beginners CTF 2021」の「crypto」の「simple_RSA」問題について、解きましたので、手順を詳細に記載します。
crypto（simple_RSA）
以下の問題文に記載がありますが、提供されたファイルを解読してRSA暗号化を復号化する問題です。
ファイルを解凍すると、以下の2つのファイルがありました。
from Crypto.Util.number import *
from flag import flag
flag = bytes_to_long(flag.encode("utf-8"))
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 3
assert 2046 < n.bit_length()
assert 375 == flag.bit_length()
print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613RSAでeの値が小さい時（eが3などの時）、「Low Public Exponent Attack」ができるとのことです。
以下のプログラムを実行すると、フラグ（ctf4b{0,1,10,11…It’s_so_annoying.___I’m_done}）が出力されました。
import gmpy2
from Crypto.Util.number import *
# 提供されたoutput.txtの内容
n=17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e=3
c=213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613
# cのe乗根号の整数の値をmに代入
m,result = gmpy2.iroot(c,e)
# 復号化された値を出力
print(m)
print(long_to_bytes(int(m)))プログラムで使用している関数の概要は以下の通りです。
| 関数 | 概要 |
|---|---|
| gmpy2.iroot(c,e) | 一つ目の返り値はcのe乗根号の整数の値（少数点以下は切り捨てる）を返します。 二つ目の返り値はcのe乗根号が整数である場合True、整数でない場合はFalseを返します。 例えば、 (例1) gmpy2.iroot(125,3)の場合125の3乗根（＝5の3乗の値が125）ですので、一つ目の返り値は5、二つ目の返り値はTrueを返します。 (例2) gmpy2.iroot(127,3)の場合127の3乗根は5.0265…ですので、一つ目の返り値は5、二つ目の返り値はFalseを返します。 詳細は「https://gmpy2.readthedocs.io/en/latest/mpz.html」をご確認ください。 |
| long_to_bytes(m) | 整数をバイトの文字列に変換します。 詳細は「https://www.kite.com/python/docs/Crypto.Util.number.long_to_bytes」をご確認ください。 |
参考までに、上記のプログラムの実行はKali Linux上で以下のコマンドを実行しました。
# ソフトウェアのインストール
sudo apt-get update
sudo apt install python3-pip
pip install pycrypto
sudo apt-get install python3-gmpy2
# プログラム実行
python3 resolve.pySECCON Beginners CTF 2021に関する記事
SECCON Beginners CTF 2021についての関連記事は以下の通りです。
必要に応じて、ご確認ください。
| No | タイトル | 記事の概要 |
|---|---|---|
| 1 | SECCON Beginners CTF 2021 writeup | 以下のカテゴリの問題のwriteupを記載します。 【カテゴリ：welcome】 ・welcome 【カテゴリ：crypto】 ・imple_RSA 【カテゴリ：reversing】 ・only_read ・children 【カテゴリ：pwnable】 ・rewriter 【カテゴリ：web】 ・osoba 【カテゴリ：misc】 ・git-leak ・Mail_Address_Validator |
| 2 | SECCON Beginners CTF 2021 writeup （crypto：simple_RSA） | cryptカテゴリのsimple_RSAの問題の writeupを記載します。 |
| 3 | SECCON Beginners CTF 2021 writeup （crypto：Logical_SEESAW） | cryptカテゴリのLogical_SEESAWの問題の writeupを記載します。 |
| 4 | SECCON Beginners CTF 2021 writeup （crypto：GFM） | cryptカテゴリのGFMの問題の writeupを記載します。 |
| 5 | SECCON Beginners CTF 2021 writeup （crypto：Imaginary） | cryptカテゴリのImaginaryの問題の writeupを記載します。 |
| 6 | SECCON Beginners CTF 2021 writeup （web：Werewolf） | webカテゴリのWerewolfの問題の writeupを記載します。 |
| 7 | SECCON Beginners CTF 2021 writeup （web：check_url） | webカテゴリのcheck_urlの問題の writeupを記載します。 |
| 8 | SECCON Beginners CTF 2021 writeup （web：json） | webカテゴリのjsonの問題の writeupを記載します。 |
| 9 | SECCON Beginners CTF 2021 writeup （web：cant_use_db） | webカテゴリのcant_use_dbの問題の writeupを記載します。 |
