SECCON Beginners Logical_SEESAW[crypto] wirteup

Description

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個の論理和をとってもいいのかな