## solution

$m$ がすべて Your OTP for transaction #731337 in ABCXYZ Bank is ?????????. の形をしていることをgeussingすればあとはCoppersmithの定理やるだけ。気付けない場合は平文が似通ってることを信じてCoppersmith’s Short Pad Attack。

## note

sageの起動が遅い問題はserverとして建てれば解決することに気付いた

## implementation

### main.py

#!/usr/bin/env python3
import argparse
import ast
import sys
import telnetlib
import Crypto.PublicKey.RSA
import Crypto.Util.number

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

def solve(sage_tn):
sage_tn.write((' '.join(map(str, [ n, e, c1, c2 ])) + '\n').encode())
if result:
m1, m2 = result
return m1

with telnetlib.Telnet(args.host, args.port) as tn:

def test_the_otp():
tn.write(b'1\n')
return otp, encrypted_dat, decrypted_dat

def get_the_public_key():
tn.write(b'2\n')
BEGIN = b'-----BEGIN PUBLIC KEY-----'
END = b'-----END PUBLIC KEY-----'
return Crypto.PublicKey.RSA.importKey(key)

def get_flag(callback):
tn.write(b'3\n')
tn.read_until(b'send me otp to get flag >>> ')
otp = callback(encrypted_dat)
tn.write(str(otp).encode() + b'\n')

pubkey = get_the_public_key()
e = pubkey.e
n = pubkey.n
print('[*] e =', e)
print('[*] n =', hex(n))
assert e == 3

for _ in range(0):
otp, encrypted_dat, decrypted_dat = test_the_otp()
c = int(encrypted_dat, 16)
m = Crypto.Util.number.bytes_to_long(decrypted_dat)
print('[*] otp =', hex(otp))
print('[*] c =', hex(c))
print('[*] m =', hex(m))
assert pow(m, e, n) == c

def solve_otp(encrypted_dat, cs=[]):
c1 = int(encrypted_dat, 16)
print('[*] c =', hex(c1))
for c2 in cs:
m1 = coppersmiths_short_pad_attack(n, e, c1, c2)
if m1:
msg = Crypto.Util.number.long_to_bytes(m1).decode()
otp = int(msg.split()[-1].rstrip('.'))
print('[*] otp =', otp)
return otp
else:
cs += [ c1 ]
return 0

while True:
try:
result = get_flag(solve_otp)
except EOFError:
break
print('[+]', result)
if not result.startswith('Sorry, '):
return result

with telnetlib.Telnet(args.sage_host, args.sage_port) as tn:
while True:
flag = solve(sage_tn=tn)
if flag:
print('[+]', flag)
break


#!/usr/bin/env sage
# http://inaz2.hatenablog.com/entry/2016/01/20/022936

import sys

PRxy.<x,y> = PolynomialRing(Zmod(n))
PRx.<xn> = PolynomialRing(Zmod(n))
PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

g1 = x^e - c1
g2 = (x+y)^e - c2

q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)

h = q2.resultant(q1)
h = h.univariate_polynomial()
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()

kbits = n.nbits()//(2*e*e)
diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

return diff

def related_message_attack(c1, c2, diff, e, n):
PRx.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+diff)^e - c2

def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()

return -gcd(g1, g2)[0]

def main():
n, e, c1, c2 = map(ZZ, raw_input().split())
nbits = n.nbits()
kbits = nbits//(2*e*e)

try:
diff = short_pad_attack(c1, c2, e, n)
m1 = related_message_attack(c1, c2, diff, e, n)
m2 = m1 + diff

assert pow(m1, e, n) == c1
assert pow(m2, e, n) == c2
print [ m1, m2 ]
except:
print []
sys.stdout.flush()

if __name__ == '__main__':
while True:
main()