#!/usr/bin/env python

import sys
from pwn import *

def calcAx(x):
    global cache
    global nreq
    global r

    if x in cache:
        return cache[x]

    assert nreq
    nreq -= 1

    r.sendline('A')
    r.recvuntil('input: ')

    h = hex(x)[2:].strip('L')
    r.sendline('0'*(len(h)%2) + h)

    res = r.recvline(keepends=False)
    assert 'no' not in res
    r.recvuntil('cmd: ')

    cache[x] = int(res, 16)

    return int(res, 16)

def calcBx(x):
    global nreq
    global r

    assert nreq
    nreq -= 1

    r.sendline('B')
    r.recvuntil('input: ')

    h = hex(x)[2:].strip('L')
    r.sendline('0'*(len(h)%2) + h)

    res = r.recvline(keepends=False)
    assert 'no' not in res
    r.recvuntil('cmd: ')

    return int(res, 16)

def findN(bts):
    global r

    with context.local(log_level='warning'):
        if 'remote' in sys.argv[1:]:
            r = remote('13.112.92.9', 21701)
        else:
            r = process('./crypto-33dee9470e5b5639777f7c50e4c650e3.py')

    r.recvuntil('flag!\n')
    hexflag = r.recvline(keepends=False)
    r.recvuntil('cmd: ')

    # log.info('hexflag: %s', hexflag)

    roba = calcAx(0)
    acc = 0

    for i in xrange(1023, bts-1, -1):
        x = (1 << i) + acc

        encx = calcAx(x)
        dec  = calcBx(encx * roba)

        progressN.status('{:b}'.format(x))

        if dec & 0xff == x & 0xff: # n > x
            acc = x

    # x = 0xff + acc
    # encx = calcAx(x)
    # dec  = calcBx(encx * roba)
    # acc += 0xff - (dec & 0xff)

    # progressN.status('{:b}'.format(acc))

    return int(hexflag, 16), acc

# context.log_level='debug'

r = None
cache = None

# findbits = 32 # ignore this number of final bits from N

#flagbit = 1023
# flagbit = 32 * 8 # nth bit of flag to start with
# flagbit = 1024
# flagbit = 73 * 8
# flag = 0
# flag = int(('hitcon{' + '\x00' * (72-7)).encode('hex'), 16)
# flagbit = (72 - 7) * 8
flag = int(('hitcon{binary__search__and_least_significant_BYTE_oracle_in_paillier' + '\x00' * (4)).encode('hex'), 16)
flagbit = 4 * 8

while flagbit > 0:
    progressN = log.progress('N')
    progressBit = log.progress('flagbit')
    progress = log.progress('flag')

    progressBit.status('%d', flagbit)
    h = hex(flag)[2:].rstrip('L')
    progress.status(repr(('0'*(len(h)%2) + h).decode('hex')) + ' ' + bin(flag))

    nreq = 2048
    cache = {}
    encflag, n = findN(flagbit // 2 - 2)

    while nreq >= 3 and flagbit > 0:
        x = n - (1 << flagbit) - flag

        progressBit.status('%d', flagbit)

        if x < 0:
            flagbit -= 1
            continue

        encx = calcAx(x)
        dec  = calcBx(encx * encflag)

        first = False

        h = hex(flag)[2:].rstrip('L')
        progress.status(repr(('0'*(len(h)%2) + h).decode('hex')) + ' ' + bin(flag))

        if dec & 0xff != ((x + 0x0a) & 0xff): # flag > x
            flag += 1 << flagbit

        flagbit -= 1
    print flagbit, bin(flag), repr(('0'*(len(h)%2) + h).decode('hex'))

    with context.local(log_level='warning'):
        r.close()

h = hex(flag)[2:].rstrip('L')
progress.success(repr(('0'*(len(h)%2) + h).decode('hex')) + ' ' + bin(flag))
