## 解法

1. RSA公開鍵 pubkey の $n$ : 算数
2. AES秘密鍵 aeskey : LSB leak attack, これを貼る
3. AES IV : mersenne twisterの予測, これを貼る

## 実装

#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
import gmpy2
import mt19937predictor  # https://github.com/kmyk/mersenne-twister-predictor

import argparse
import binascii
import fractions
import functools
import math
import random
import telnetlib

parser = argparse.ArgumentParser()
args = parser.parse_args()
tn = telnetlib.Telnet(args.host, args.port)

def encrypt(plaintext):
tn.write(b'1\n')
tn.write(plaintext + b'\n')
ciphertext = {}
return ciphertext

def decrypt(ciphertext):
tn.write(b'2\n')
tn.write(binascii.hexlify(ciphertext) + b'\n')
return { 'RSA': plaintext }

def print_flag():
tn.write(b'3\n')

def print_key():
tn.write(b'4\n')

def find_n(e):
m1 = 2
m2 = 3
c1 = bytes_to_long(encrypt(long_to_bytes(m1))['RSA'])
c2 = bytes_to_long(encrypt(long_to_bytes(m2))['RSA'])
return fractions.gcd(m1 ** e - c1, m2 ** e - c2)
e = 65537
n = find_n(e)
print('[*] n:', n)

def lsb_leak_attack(e, n, c):
l, r = 0, n  # [l, r)
i = 1
while r - l >= 1:
m = fractions.Fraction(l + r, 2)
print('[*] m:', bin(math.ceil(m)))
if bytes_to_long(decrypt(long_to_bytes(pow(2, i * e, n) * c % n))['RSA']) & 1:
l = m
else:
r = m
i += 1
return math.ceil(l)
aeskey = print_key()
print('[*] encrypted AES key:', repr(aeskey))
aeskey = long_to_bytes(lsb_leak_attack(e, n, bytes_to_long(aeskey)))
print('[*] AES key:', repr(aeskey))

BLOCK_SIZE = 16
def guess_iv():
predictor = mt19937predictor.MT19937Predictor()
for _ in range(624 // 4):
iv = encrypt(b'hoge')['AES'][: BLOCK_SIZE]
print('[*] iv:', repr(iv))
predictor.setrandbits(bytes_to_long(iv), BLOCK_SIZE * 8)
return predictor.getrandbits(BLOCK_SIZE * 8)
iv = long_to_bytes(guess_iv())
print('[*] guessed iv:', repr(iv))
flag = print_flag()
print('[*] encrypted flag:', repr(flag))

# decrypt flag
aes = AES.new(aeskey, AES.MODE_CBC, iv)
flag = aes.decrypt(flag[BLOCK_SIZE :])
print('[*] flag:', repr(flag))