SECCON Beginners Logical_SEESAW[crypto] wirteup
Description
このこれを解凍すると、problem.pyとoutput.txtがもらえるのでproblem.pyを読みます。以下problem.py
from Crypto.Util.number import * from random import random, getrandbits from flag import flag flag = bytes_to_long(flag.encode("utf-8")) length = flag.bit_length() key = getrandbits(length) while not length == key.bit_length(): key = getrandbits(length) flag = list(bin(flag)[2:]) key = list(bin(key)[2:]) cipher_L = [] for _ in range(16): # 16 times cipher = flag[:] m = 0.5 for i in range(length): n = random() # 50%で if n > m: cipher[i] = str(eval(cipher[i] + "&" + key[i])) # 論理積をとる cipher_L.append("".join(cipher)) print("cipher =", cipher_L)
Writeup
これを読むと、flagの一文字一文字が50％の確率で論理積を取られたものが暗号文として出力されていることがわかる。cipherのリストはたぶん16個の暗号文が書かれているのだと思われる。
元文(flag)の桁に1があるならcipherのうちのどれか一つはその桁が1になっているはずなので、以下のようなコードで答えが得られるはず！
一応、元の文が1でもcipherの16個の暗号文にある論理積の結果が全部1ではない確率は1/2^16で1/10^5とかなので多分大丈夫だと信じて実行します！
from Crypto.Util.number import long_to_bytes cipher = [] # 長いので省きました… a = ['0'] * len(cipher[0]) n = len(cipher[0]) for c in cipher: for i in range(n): if c[i] == '1': a[i] = '1' a = ''.join(a) print(long_to_bytes(eval('0b' + a)))
GET！！！
後記
暗号文16個の論理和をとってもいいのかな
No module named 'Crypto' のエラーを解決した！！
はじめに
SECCON Begginersの解説放送などを見て、Crypto問を解いていて、
ModuleNotFoundError: No module named 'Crypto'
に悩まされた方は私だけではないと思ったので投稿しました。
解決方法
だらだらと説明されるのは嫌だと思うので簡潔に。
多分みなさん
$ pip install Crypto
とかやってると思うので、やってない人はこれしてください。
本題
エクスプローラーで
C:\Users\*name*\AppData\Local\Programs\Python\Python38-32\Lib\site-packages
の位置に"crypto"という名前のファイルがあると思うので、このファイルの先頭を大文字にして"Crypto"にしてください！それだけです。
SECCON Beginners simple_RSA[crypto] wirteup
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の作業に使うらしい…
