NTRU.sage

RRR = RealField(40);
P.<x> = PolynomialRing(ZZ);


#Generates a random polynomial of degree and norm bounded by N and no
def Rand_Pol_Fixed_Norm(N,no):
    v = vector(ZZ,N);
    for i in range(N):
        v[i] = randint(-1000*no,1000*no);
    norm = v*v;
    for i in range(N):
        v[i] = (v[i]*no)//isqrt(norm);
    f = sum(v[i]*x^i for i in range(N));
    return f;


#For fixed f,g,N,q, generates the NTRU polynomials F,G associated by f,g
def Derivation_FG(f,g,N,q):
    phi = x^N+1;
    (R_f, rho_f, iphi) = xgcd(f,phi);
    (R_g, rho_g, iphi) = xgcd(g,phi);
    assert(R_f.degree() == 0);
    assert(R_g.degree() == 0);
    (pgcd,alpha,beta) = xgcd(R_f[0],R_g[0]);
    if (pgcd != 1):
        print "pgcd =", pgcd;
        print "The GCD of R_f and R_g is different of 1.";
    assert(pgcd == 1);
    F = -q*beta*rho_g;
    G = q*alpha*rho_f;
    k = Compute_k(f,g,F,G,N);
    iter = 0;
    while (k!= 0):
        F = (F - k*f).quo_rem(phi)[1];
        G = (G - k*g).quo_rem(phi)[1];
        k = Compute_k(f,g,F,G,N);
    return(F,G);


#Tests if f,g can generate a NTRU lattice
def Test(f,g,N,q):
    phi = x^N+1;
    (R_f, rho_f, iphi) = xgcd(f,phi);
    (R_g, rho_g, iphi) = xgcd(g,phi);
    assert(R_f.degree() == 0);
    assert(R_g.degree() == 0);
    (pgcd,alpha,beta) = xgcd(R_f[0],R_g[0]);
    if (pgcd != 1):
        return False;
    return True;


#Returns f(1/x) mod (x^N+1)
def Reverse(f,N):
    g = sum( f[i]*(x^(N-i)) for i in [1..N-1] );
    return f[0] - g;


#Compute the polynomial k used to reduce F,G
#(See the end of Appendix A in "NTRUSign: Digital Signatures using the NTRU Lattice")
def Compute_k(f,g,F,G,N):
    RRR=RealField(350);
    phi = (x^N+1);
    FB = Reverse(F,N);
    GB = Reverse(G,N);
    fb = Reverse(f,N);
    gb = Reverse(g,N);
    num = (fb*F+gb*G).quo_rem(phi)[1];
    den = (f*fb+g*gb).quo_rem(phi)[1];
    (a,iden,iphi) = xgcd(den,x^N+1);
    k0 = (num*iden).quo_rem(phi)[1];
    k = sum( (k0[i]//a[0])*x^i for i in [0..N-1]  );
    k = k.change_ring(ZZ);
    return k;


def Rotate(v,k):
    w = list(v);
    for i in range(k):
        w.insert(0,-w.pop());
    return vector(w);


#Returns the Anticirculant matrix A_N(f) generated by, f, x^k.f, ..., x^((N-1)k).f
def AC(f,N,k):
    u = f.coeffs();
    while(len(u)<N):
        u.append(0);
    A = matrix(ZZ,N);
    z = vector(u);
    for i in range(N):
        A[i] = z;
        z = Rotate(z,k);
    return A;


#Tests if f is invertible mod X^N+1 mod q
def Is_Invertible(f,N,q):
    (pgcd,u,v) = xgcd(f,x^N+1);
    rep = gcd(pgcd,q);
    return (rep==1);


#Computes the inverse of f mod X^N+1 mod q
def Inverse(f,N,q):
    (pgcd,u,v) = xgcd(f,x^N+1);
    p_1 = inverse_mod(pgcd[0],q);
    u = p_1*u;
    u = u.quo_rem(q)[1];
    return u;


#Computes h = g/f mod X^N+1 mod q
def h_from_fg(f,g,N,q):
    phi = x^N+1;
    f_1 = Inverse(f,N,q);
    h = ((f_1*g).quo_rem(phi)[1]).quo_rem(q)[1];
    return h;


#Returns the NTRU secret basis generated by f,g
def NTRU_Secret_Basis(f,g,N,q):
    (F,G) = Derivation_FG(f,g,N,q);
    A = AC(f,N,1);
    B = AC(g,N,1);
    C = AC(F,N,1);
    D = AC(G,N,1);
    E = block_matrix([[A,B],[C,D]]);
    return E;


#Returns the NTRU public basis generated by f,g
def NTRU_Public_Basis(f,g,N,q):
    phi = x^N+1;
    h = h_from_fg(f,g,N,q);
    A = identity_matrix(ZZ,N);
    B = AC(h,N,1);
    C = zero_matrix(ZZ,N);
    D = q*identity_matrix(ZZ,N);
    E = block_matrix([[A,B],[C,D]]);
    return E;


#Push-button procedure for generating the public and private bases for a NTRU lattice
#The expected norms of f,g is hardcoded ('norm') but you can change it
def Keygen(N,q):
    norm = isqrt(q)//2;
    Rep = False;
    while(Rep==False):
        f = Rand_Pol_Fixed_Norm(N,norm);
        g = Rand_Pol_Fixed_Norm(N,norm);
        Rep = Test(f,g,N,q);
        if(Rep==True):
            Rep = Is_Invertible(f,N,q);
    Sk = NTRU_Secret_Basis(f,g,N,q);
    Pk = NTRU_Public_Basis(f,g,N,q);
    return (Sk,Pk);