CTFZone 2019 qual NTRU writeup

remote.py

from cryptosystem import PKCS
from polynomials import Polynomial as P


from cryptosystem_edit import PKCS as PKCS_edit
from flag_params import flag_encrypted_password as encpass

cs = PKCS.importPublicKey(open('public.key').read())


from socket import *
sock = socket(AF_INET, SOCK_STREAM)
sock.connect(("crypto-mitm.ctfz.one",5555))

def getunt(c):
	assert type(c) is bytes
	res = b""
	while res==b'' or res[-len(c):]!=c:
		#print(res[-len(c):])
		res += sock.recv(1)
		#print(res)
	#print(res)
	return res

#getunt(b'>')


def remote(x,y):
  bx = x.encode('ascii')
  by = y.encode('ascii')
  print('send',bx,by)
  sock.send(b'check\n')
  getunt(b'plaintext: ')
  sock.send(bx + b'\n')
  getunt(b'ciphertext: ')
  sock.send(by + b'\n')
  res = getunt(b'>')
  print('recv',res)
  return res

def wraps(x):
  _,mx = x.divide_modulo_base_pol(cs.N, cs.p)
  
  sx = cs.encodeCiphertextData(x)
  
  """
  sc = cs.decrypt(sx)
  c = cs.decodePlaintextData(sc)
  _,mc = c.divide_modulo_base_pol(cs.N, cs.p)
  _,emx = cs.decodePlaintextData(cs.encodePlaintextData(mx)).divide_modulo_base_pol(cs.N, cs.p)  
  return mc != emx
  """
  
  #emx = cs.encodePlaintextData(mx)
  #return sc != emx
  
  
  # 向こうでscが帰ってきたあと、さらにemxになって、こっちにエンコードされてとんでくる。(比較される)
  # emx と mc が等しいか、を向こうで検証してほしい
  # sc と比較するものを与えられる。
  
  emx = cs.encodePlaintextData(mx)
  return b'Incorrect' in remote(bytes.hex(emx),bytes.hex(sx))
 
  """
  cc = cs.decryptPolynomial(x)
  
  #print(x,cs.decodeCiphertextData(cs.encodeCiphertextData(x)))
  _,ccx = cs.decodeCiphertextData(cs.encodeCiphertextData(x)).divide_modulo_base_pol(cs.N, cs.q)
  assert x == ccx
  
  _,ccm = cs.decodePlaintextData(cs.encodePlaintextData(cc)).divide_modulo_base_pol(cs.N, cs.p)
  print(cc,cs.encodePlaintextData(cc),ccm,mc)
  assert cc == ccm
  こっちはずれるので、mxをさらにencode->decodeする
  """
  
  """
  print('mx',mx)
  print('cc',cc)
  print('mc',mc)
  assert cc == mc
  """
  
  #print(mc,mx)




f = [1] + [0 for _ in range(cs.N)]
e = [0 for _ in range(cs.N+1)]
w = 1
for i in range(cs.N-1):
  if w < cs.q // 2:
    e[i] = -f[i]
    e[i+1] = -(cs.q//2-w)
  else:
    e[i] = 0
    e[i+1] = -1
  
  
  #print(pe,c)
  #break
  if wraps(P(e)):
    f[i+1] = 1
    w += 1
  else:
    e[i+1] = -e[i+1]
    if wraps(P(e)):
      f[i+1] = -1
      w += 1
    else:
      f[i+1] = 0

print('f',cs.f.coefficients)
print('decoded f',f)

print(cs.df,f.count(1),f.count(-1),'|',cs.f.coefficients.count(1),cs.f.coefficients.count(-1))
#df = P(f[::-1][136:] + f[::-1][1:136])
df = P([0] + f[::-1][156:] + f[::-1][1:156])
print(df.coefficients)
print(cs.f-df)

trydec.py

from polynomials import Polynomial as P
from cryptosystem_edit import PKCS as PKCS_edit

cs = PKCS_edit.importPublicKey(open('public.key').read())

correct_f_base = [1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 0, 0, 0, 0, 0, -1, 0, 0, -1, 1, 1, 0, 0, 1, 1, -1, 1, 0, 1, -1, 1, 1, -1, 0, -1, -1, -1, 1, -1, -1, -1, 1, -1, 0, -1, -1, 0, 0, -1, 1, 1, 0, 0, -1, 0, 1, -1, 1, -1, -1, 1, 0, 0, 1, 0, -1, 1, 0, -1, 1, 0, -1, 0, 1, -1, -1, -1, -1, 0, 0, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 0, -1, -1, 1, -1, 1, 1, 1, -1, 0, 0, 1, 0, 0, 1, -1, 0, -1, -1, -1, 1, -1, -1, 1, -1, 0, -1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 0, 0, -1, 0, -1, 0, 1, 0, 1, -1, 0, 1, 1, 0, 0, 1, 1, 1, -1, 0, 1, -1, 1, 0, -1, 0]

for i in range(cs.N * 3):
  pi = i // 3
  ci = (i % 3) - 1
  tesf = P([ci] + correct_f_base[::-1][pi:] + correct_f_base[::-1][1:pi])
  tcs = PKCS_edit.importPublicKey(open('public.key').read())
  try:
    tcs.generateKey(tesf)
  except AssertionError:
    continue
  d = tcs.decrypt(bytes.fromhex(encpass))
  print('dec',d)
  break