## solution

ちょっと変形するとLSB oracleが得られるのでやるだけ。 過去に書いたやつをコピペ: https://kimiyuki.net/blog/2017/06/24/lsb-leak-attack/

## implementation

#!/usr/bin/env python3
import argparse
import concurrent.futures
import fractions
import math
import socket

from Crypto.Util.number import long_to_bytes, bytes_to_long
import Crypto.PublicKey.RSA as RSA

parser = argparse.ArgumentParser()
args = parser.parse_args()

with open(args.flag, 'rb') as fh:
print('[*] size =', len(ciphertext))

with open(args.pubkey) as fh:
print('[*] n =', public_key.n)
print('[*] e =', public_key.e)
print('[*] size =', public_key.size())

def challenge(m0, m1, ciphertext):
assert m0 in [ 0, 1 ]
assert m1 in [ 0, 1 ]
assert len(ciphertext) == (public_key.size() + 1) // 8
print('[+] connect', args.host, args.port)
with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as sock:
sock.connect((args.host, args.port))
sock.send(bytes([ m0 ]))
sock.send(bytes([ m1 ]))
sock.send(ciphertext)
for _ in range(100):
yield ord(sock.recv(1))

def lsb_oracle(c):
cnt = 0
for p in challenge(0, 1, long_to_bytes(c, 128)):
cnt += p
return int(cnt >= 50)

n = public_key.n
e = public_key.e
c = bytes_to_long(ciphertext)

def attack(e, n, c, oracle, max_workers=16):
futures = {}
for i in range(1, n.bit_length() + 10):
futures[i] = executor.submit(oracle, pow(2, i * e, n) * c % n)
l, r = 0, n  # [l, r)
i = 1
while r - l >= 1:
m = fractions.Fraction(l + r, 2)
if futures[i].result():
l = m
else:
r = m
i += 1
print('[*] l =', long_to_bytes(math.floor(l)))
print('[*] r =', long_to_bytes(math.ceil(r)))
return math.ceil(l)

m = attack(e, n, c, lsb_oracle)
assert pow(m, e, n) == c
print('[*] plaintext = ', long_to_bytes(m))