Attack on NTRU Cryptosystem with weak parameters.

ntru_attack.sage

# Script is from https://latticehacks.cr.yp.to/ntru.html

import math
import numpy as np
from sympy.abc import x
from sympy import ZZ, Poly
from Crypto.Util.number import long_to_bytes

n = 71
d = 3
q = 512

def convolution(f,g):
  return (f * g) % (x^n-1)

def balancedmod(f,q):
  g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
  return Zx(g)

def invertmodprime(f,p):
  T = Zx.change_ring(Integers(p)).quotient(x^n-1)
  return Zx(lift(1 / T(f)))
  
def decrypt(ciphertext,secretkey):
  f,f3 = secretkey
  a = balancedmod(convolution(ciphertext,f),q)
  return balancedmod(convolution(a,f3),3)

def attack(publickey):
  recip3 = lift(1/Integers(q)(3))
  publickeyover3 = balancedmod(recip3 * publickey,q)
  M = matrix(2 * n)
  for i in range(n):
    M[i,i] = q
  for i in range(n):
    M[i+n,i+n] = 1
    c = convolution(x^i,publickeyover3)
    for j in range(n):
      M[i+n,j] = c[j]
  M = M.LLL()
  for j in range(2 * n):
    try:
      f = Zx(list(M[j][n:]))
      f3 = invertmodprime(f,3)
      return (f,f3)
    except:
      pass
  return (0,0)


Zx.<x> = ZZ[]

hs = [-116, 70, -19, -226, -195, -116, -45, 71, 179, 237, 39, 153, -247, 29, -145, 145, -25, -92, -189, -44, -35, 250, 42, -173, -223, -220, 212, 148, 175, -91, 166, -118, 63, 94, -29, 79, 16, 84, 140, -37, 245, -78, -38, -54, -234, -91, 162, -33, -130, 25, -203, 154, -28, 80, 87, -247, 229, -203, -67, 136, -41, -253, 39, -182, -163, 103, -177, -39, -111, 204, -123]
ct1 = [-28, 42, 55, -242, 44, -234, 76, -90, 104, -106, 107, 108, -224, -159, -83, -198, 210, 148, -136, 143, 165, -163, -236, -10, 77, 212, 119, -6, -22, 29, 59, -146, 26, 41, 250, 160, -96, -119, -95, 143, -193, -243, -118, -253, -134, -19, 196, -247, 94, -118, 53, -136, 44, -98, -163, 12, 105, 130, 106, -40, -151, 153, -129, -180, 149, 78, -84, -248, -222, 218, 5][::-1]

publickey = Zx(hs)
cipher = Zx(ct1)
donald = attack(publickey)
print(donald)
print(decrypt(cipher,donald))