SECCON Beginners simple_RSA[crypto] wirteup
Description
SECCON Beginners のcrypto問題一問目のsimple_RSAを解いたので備忘録を書いておきます。
はい、問題文
Writeup
simple_RSA.tar.gzというファイルが与えられるので、linuxで解凍すると
output.txt
problem.py
という二つのファイルが与えられます。
与えられたPythonのソースコードはよくわかりませんでしたが、picoCTFで同じような問題が出ていたのでカンニングしました笑
picoのminiRSAという問題はe=3と小さい場合の復号の問題です。これは、e乗根を使った方法で復号できます。
e乗根についてはこの記事で見つけました。ほかにもいろいろな方法があるみたいです。
cpawの最後に使ったcommon modules attackしか知りませんでした。
eが小さいとき、nのe乗根以下の平文mについては、単純に暗号文cのe乗根を取れば求めることができる。
コード
ソースコードはこんな感じです。まあ、これはminiRSAのwriteupから見つけたものの一部コピペです。
# ctf4b21 simple_RSA import gmpy2 n = # input the module e = 3 cipher_str = # input the cipher str gs = gmpy2.mpz(cipher_str) gm = gmpy2.mpz(n) ge = gmpy2.mpz(e) root, exact = gmpy2.iroot(gs, ge) root = format(root, 'x') # 10進数→16進数 byte_array = bytearray.fromhex(root) # 16進数→バイト配列 print(byte_array.decode()) # バイト配列→ASCII
復習
与えられたソースコードよくわかんなかったけど、kurenaifさんの解説見るとどの関数が何をしているのかわかってああってなりました。(ちゃんとはわかってない)
Crypto.Util.numberみたいなやつはdecodeの作業に使うらしい…