Created ntru_poly class for sparse trinary polynomials
authorAndreas Steffen <andreas.steffen@strongswan.org>
Tue, 18 Feb 2014 15:17:18 +0000 (16:17 +0100)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Tue, 18 Feb 2014 15:17:38 +0000 (16:17 +0100)
src/libstrongswan/plugins/ntru/Makefile.am
src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_encrypt.c
src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_encrypt_param_sets.c
src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_encrypt_param_sets.h
src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_poly.c
src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_poly.h
src/libstrongswan/plugins/ntru/ntru_poly.c [new file with mode: 0644]
src/libstrongswan/plugins/ntru/ntru_poly.h [new file with mode: 0644]
src/libstrongswan/tests/suites/test_ntru.c

index 26dca72..b33cbc8 100644 (file)
@@ -15,6 +15,7 @@ libstrongswan_ntru_la_SOURCES = \
        ntru_drbg.h ntru_drbg.c \
        ntru_ke.h ntru_ke.c \
        ntru_mgf1.h ntru_mgf1.c \
+       ntru_poly.h ntru_poly.c \
        ntru_trits.h ntru_trits.c \
        ntru_crypto/ntru_crypto.h \
        ntru_crypto/ntru_crypto_ntru_convert.h \
index 0654609..56236b5 100644 (file)
@@ -42,6 +42,7 @@
 #include "ntru_crypto_ntru_poly.h"
 #
 #include "ntru_trits.h"
+#include "ntru_poly.h"
 
 /* ntru_crypto_ntru_encrypt
  *
@@ -99,7 +100,6 @@ ntru_crypto_ntru_encrypt(
     int16_t                 m1 = 0;
     uint16_t               *scratch_buf = NULL;
     uint16_t               *ringel_buf = NULL;
-    uint16_t               *r_buf = NULL;
     uint8_t                *b_buf = NULL;
     uint8_t                *tmp_buf = NULL;
     bool                    msg_rep_good = FALSE;
@@ -110,6 +110,8 @@ ntru_crypto_ntru_encrypt(
        ntru_trits_t           *mask;
        uint8_t                *mask_trits;
        chunk_t                 seed;
+       ntru_poly_t                             *r_poly;
+       uint16_t                                *r_indices;
 
     /* check for bad parameters */
 
@@ -186,8 +188,7 @@ ntru_crypto_ntru_encrypt(
                return NTRU_OUT_OF_MEMORY;
     }
     ringel_buf = scratch_buf + ring_mult_tmp_len;
-    r_buf = ringel_buf + params->N;
-    b_buf = (uint8_t *)(r_buf + (dr << 1));
+    b_buf = (uint8_t *)(ringel_buf + params->N);
     tmp_buf = (uint8_t *)scratch_buf;
 
        /* set hash algorithm based on security strength */
@@ -225,39 +226,46 @@ ntru_crypto_ntru_encrypt(
             memcpy(ptr, pubkey_packed, params->sec_strength_len);
             ptr += params->sec_strength_len;
 
+                       DBG2(DBG_LIB, "generate polynomial r");
 
-            /* generate r */
-            result = ntru_gen_poly(hash_algid,
-                                   params->min_IGF_hash_calls,
-                                   (uint16_t)(ptr - tmp_buf),
-                                   tmp_buf, tmp_buf,
-                                   params->N, params->c_bits,
-                                   params->no_bias_limit,
-                                   params->is_product_form,
-                                   params->dF_r << 1, r_buf);
+                       seed = chunk_create(tmp_buf, ptr - tmp_buf);
+                       r_poly = ntru_poly_create(hash_algid, seed,
+                                                                         params->c_bits, params->no_bias_limit,
+                                                                         params->N, 2 * params->dF_r,
+                                                                         params->is_product_form);
+                       if (!r_poly)
+                       {
+                          result = NTRU_MGF1_FAIL;
+                       }
         }
 
                if (result == NTRU_OK)
                {
-            uint16_t pubkey_packed_len;
+                       uint16_t pubkey_packed_len;
 
-            /* unpack the public key */
-            assert(pubkey_pack_type == NTRU_ENCRYPT_KEY_PACKED_COEFFICIENTS);
-            pubkey_packed_len = (params->N * params->q_bits + 7) >> 3;
-            ntru_octets_2_elements(pubkey_packed_len, pubkey_packed,
-                                   params->q_bits, ringel_buf);
+                       /* unpack the public key */
+                       assert(pubkey_pack_type == NTRU_ENCRYPT_KEY_PACKED_COEFFICIENTS);
+                       pubkey_packed_len = (params->N * params->q_bits + 7) >> 3;
+                       ntru_octets_2_elements(pubkey_packed_len, pubkey_packed,
+                                                                  params->q_bits, ringel_buf);
 
-            /* form R = h * r */
+                       /* form R = h * r */
+                       r_indices = r_poly->get_indices(r_poly);
 
-            if (params->is_product_form)
-                ntru_ring_mult_product_indices(ringel_buf, (uint16_t)dr1,
-                                               (uint16_t)dr2, (uint16_t)dr3,
-                                               r_buf, params->N, params->q,
-                                               scratch_buf, ringel_buf);
-            else
-                ntru_ring_mult_indices(ringel_buf, (uint16_t)dr, (uint16_t)dr,
-                                       r_buf, params->N, params->q,
-                                       scratch_buf, ringel_buf);
+                       if (params->is_product_form)
+                       {
+                               ntru_ring_mult_product_indices(ringel_buf, (uint16_t)dr1,
+                                                                                          (uint16_t)dr2, (uint16_t)dr3,
+                                                                                          r_indices, params->N, params->q,
+                                                                                          scratch_buf, ringel_buf);
+                       }
+                       else
+                       {
+                               ntru_ring_mult_indices(ringel_buf, (uint16_t)dr, (uint16_t)dr,
+                                                                          r_indices, params->N, params->q,
+                                                                          scratch_buf, ringel_buf);
+                       }
+                       r_poly->destroy(r_poly);
 
                        /* form R mod 4 */
                        ntru_coeffs_mod4_2_octets(params->N, ringel_buf, tmp_buf);
@@ -451,6 +459,8 @@ ntru_crypto_ntru_decrypt(
        ntru_trits_t           *mask;
        uint8_t                *mask_trits;
        chunk_t                 seed;
+       ntru_poly_t                        *i_poly;
+       uint16_t                           *i_indices;
 
        /* check for bad parameters */
        if (!privkey_blob || !ct || !pt_len)
@@ -699,69 +709,74 @@ ntru_crypto_ntru_decrypt(
         ptr += params->sec_strength_len;
 
         /* generate cr */
-
-        result = ntru_gen_poly(hash_algid,
-                               params->min_IGF_hash_calls,
-                               (uint16_t)(ptr - tmp_buf),
-                               tmp_buf, tmp_buf,
-                               params->N, params->c_bits,
-                               params->no_bias_limit,
-                               params->is_product_form,
-                               params->dF_r << 1, i_buf);
+               DBG2(DBG_LIB, "generate polynomial i");
+
+               seed = chunk_create(tmp_buf, ptr - tmp_buf);
+               i_poly = ntru_poly_create(hash_algid, seed,
+                                                                 params->c_bits, params->no_bias_limit,
+                                                                 params->N, 2 * params->dF_r,
+                                                                 params->is_product_form);
+               if (!i_poly)
+               {
+                  result = NTRU_MGF1_FAIL;
+               }
     }
 
        if (result == NTRU_OK)
        {
-
-        /* unpack the public key */
-
-        {
+               /* unpack the public key */
+               {
             uint16_t pubkey_packed_len;
 
-            assert(pubkey_pack_type == NTRU_ENCRYPT_KEY_PACKED_COEFFICIENTS);
-            pubkey_packed_len = (params->N * params->q_bits + 7) >> 3;
-            ntru_octets_2_elements(pubkey_packed_len, pubkey_packed,
-                                   params->q_bits, ringel_buf1);
-        }
+                       assert(pubkey_pack_type == NTRU_ENCRYPT_KEY_PACKED_COEFFICIENTS);
+                       pubkey_packed_len = (params->N * params->q_bits + 7) >> 3;
+                       ntru_octets_2_elements(pubkey_packed_len, pubkey_packed,
+                                                                  params->q_bits, ringel_buf1);
+               }
 
-        /* form cR' = h * cr */
+               /* form cR' = h * cr */
+               i_indices = i_poly->get_indices(i_poly);
+               if (params->is_product_form)
+               {
+                       ntru_ring_mult_product_indices(ringel_buf1, (uint16_t)dF_r1,
+                                                                                  (uint16_t)dF_r2, (uint16_t)dF_r3,
+                                                                                  i_indices, params->N, params->q,
+                                                                                  scratch_buf, ringel_buf1);
+               }
+               else
+               {
+                       ntru_ring_mult_indices(ringel_buf1, (uint16_t)dF_r, (uint16_t)dF_r,
+                                                                  i_indices, params->N, params->q,
+                                                                  scratch_buf, ringel_buf1);
+               }
+               i_poly->destroy(i_poly);
 
-        if (params->is_product_form)
-            ntru_ring_mult_product_indices(ringel_buf1, (uint16_t)dF_r1,
-                                           (uint16_t)dF_r2, (uint16_t)dF_r3,
-                                           i_buf, params->N, params->q,
-                                           scratch_buf, ringel_buf1);
-        else
-            ntru_ring_mult_indices(ringel_buf1, (uint16_t)dF_r, (uint16_t)dF_r,
-                                   i_buf, params->N, params->q,
-                                   scratch_buf, ringel_buf1);
-
-        /* compare cR' to cR */
-
-        for (i = 0; i < params->N; i++) {
-            if (ringel_buf1[i] != ringel_buf2[i])
+               /* compare cR' to cR */
+               for (i = 0; i < params->N; i++)
+               {
+                       if (ringel_buf1[i] != ringel_buf2[i])
+                       {
                 decryption_ok = FALSE;
-        }
+                       }
+               }
 
         /* output plaintext and plaintext length */
-
-        if (decryption_ok)
+               if (decryption_ok)
                {
-            if (*pt_len < cm_len)
+                       if (*pt_len < cm_len)
                        {
                                return NTRU_BUFFER_TOO_SMALL;
                        }
-            memcpy(pt, m_buf, cm_len);
-            *pt_len = cm_len;
+                       memcpy(pt, m_buf, cm_len);
+                       *pt_len = cm_len;
         }
     }
 
-    /* cleanup */
-
-    memset(scratch_buf, 0, scratch_buf_len);
-    free(scratch_buf);
+       /* cleanup */
+       memset(scratch_buf, 0, scratch_buf_len);
+       free(scratch_buf);
     
-    if (!decryption_ok)
+       if (!decryption_ok)
        {
                return NTRU_FAIL;
        }
@@ -836,13 +851,15 @@ ntru_crypto_ntru_encrypt_keygen(
     uint16_t               *scratch_buf = NULL;
     uint16_t               *ringel_buf1 = NULL;
     uint16_t               *ringel_buf2 = NULL;
-    uint16_t               *F_buf = NULL;
     uint8_t                *tmp_buf = NULL;
     uint16_t                mod_q_mask;
     hash_algorithm_t        hash_algid;
-    uint8_t                 md_len;
     uint16_t                seed_len;
+       chunk_t                                 seed;
     uint32_t                result = NTRU_OK;
+       ntru_poly_t                        *F_poly = NULL;
+       ntru_poly_t            *g_poly = NULL;
+       uint16_t                           *F_indices, *g_indices;
 
     /* get a pointer to the parameter-set parameters */
 
@@ -907,19 +924,16 @@ ntru_crypto_ntru_encrypt_keygen(
     }
     ringel_buf1 = scratch_buf + (params->N << 1);
     ringel_buf2 = ringel_buf1 + params->N;
-    F_buf = ringel_buf2 + params->N;
     tmp_buf = (uint8_t *)scratch_buf;
 
        /* set hash algorithm and seed length based on security strength */
     if (params->sec_strength_len <= 20)
        {
                hash_algid = HASH_SHA1;
-               md_len = 20;
        }
        else
        {
                hash_algid = HASH_SHA256;
-               md_len = 32;
        }
        seed_len = params->sec_strength_len + 8;
 
@@ -943,81 +957,92 @@ ntru_crypto_ntru_encrypt_keygen(
 
        if (result == NTRU_OK)
        {
-
-        /* generate F */
-        result = ntru_gen_poly(hash_algid,
-                               params->min_IGF_hash_calls,
-                               seed_len, tmp_buf, tmp_buf,
-                               params->N, params->c_bits,
-                               params->no_bias_limit,
-                               params->is_product_form,
-                               params->dF_r << 1, F_buf);
+               DBG2(DBG_LIB, "generate polynomial F");
+
+               seed = chunk_create(tmp_buf, seed_len);
+               F_poly = ntru_poly_create(hash_algid, seed,
+                                                                 params->c_bits, params->no_bias_limit,
+                                                                 params->N, 2 * params->dF_r,
+                                                                 params->is_product_form);
+               if (!F_poly)
+               {
+                  result = NTRU_MGF1_FAIL;
+               }
     }
 
        if (result == NTRU_OK)
        {
         uint32_t i;
 
-        memset(ringel_buf1, 0, params->N * sizeof(uint16_t));
-
-        /* form F as a ring element */
-
-        if (params->is_product_form) {
-            uint32_t dF3_offset = (dF1 + dF2) << 1;
-
-            /* form F1 as a ring element */
-
-            for (i = 0; i < dF1; i++)
-                ringel_buf1[F_buf[i]] = 1;
-            for (; i < (dF1 << 1); i++)
-                ringel_buf1[F_buf[i]] = mod_q_mask;
+               memset(ringel_buf1, 0, params->N * sizeof(uint16_t));
+               F_indices = F_poly->get_indices(F_poly);
 
-            /* form F1 * F2 */
-
-            ntru_ring_mult_indices(ringel_buf1, (uint16_t)dF2, (uint16_t)dF2,
-                                   F_buf + (dF1 << 1), params->N, params->q,
-                                   scratch_buf, ringel_buf1);
-
-            /* form (F1 * F2) + F3 */
-
-            for (i = 0; i < dF3; i++) {
-                uint16_t index = F_buf[dF3_offset + i];
-                ringel_buf1[index] = (ringel_buf1[index] + 1) & mod_q_mask;
-            }
-            for (; i < (dF3 << 1); i++) {
-                uint16_t index = F_buf[dF3_offset + i];
-                ringel_buf1[index] = (ringel_buf1[index] - 1) & mod_q_mask;
-            }
+               /* form F as a ring element */
+               if (params->is_product_form)
+               {
+                       uint32_t dF3_offset = (dF1 + dF2) << 1;
 
-        } else {
+                       /* form F1 as a ring element */
+                       for (i = 0; i < dF1; i++)
+                       {
+                               ringel_buf1[F_indices[i]] = 1;
+                       }
+                       for (; i < (dF1 << 1); i++)
+                       {
+                               ringel_buf1[F_indices[i]] = mod_q_mask;
+                       }
 
-            /* form F as a ring element */
+                       /* form F1 * F2 */
+                       ntru_ring_mult_indices(ringel_buf1, (uint16_t)dF2, (uint16_t)dF2,
+                                                                  F_indices + (dF1 << 1), params->N, params->q,
+                                                                  scratch_buf, ringel_buf1);
 
-            for (i = 0; i < dF; i++)
-                ringel_buf1[F_buf[i]] = 1;
-            for (; i < (dF << 1); i++)
-                ringel_buf1[F_buf[i]] = mod_q_mask;
-        }
+                       /* form (F1 * F2) + F3 */
+                       for (i = 0; i < dF3; i++)
+                       {
+                               uint16_t index = F_indices[dF3_offset + i];
 
-        /* form f = 1 + pF */
+                               ringel_buf1[index] = (ringel_buf1[index] + 1) & mod_q_mask;
+                       }
+                       for (; i < (dF3 << 1); i++)
+                       {
+                               uint16_t index = F_indices[dF3_offset + i];
 
-        for (i = 0; i < params->N; i++)
-            ringel_buf1[i] = (ringel_buf1[i] * 3) & mod_q_mask;
-        ringel_buf1[0] = (ringel_buf1[0] + 1) & mod_q_mask;
+                               ringel_buf1[index] = (ringel_buf1[index] - 1) & mod_q_mask;
+                       }
+               }
+               else
+               {
+                       /* form F as a ring element */
+                       for (i = 0; i < dF; i++)
+                       {
+                               ringel_buf1[F_indices[i]] = 1;
+                       }
+                       for (; i < (dF << 1); i++)
+                       {
+                               ringel_buf1[F_indices[i]] = mod_q_mask;
+                       }
+               }
 
-        /* find f^-1 in (Z/qZ)[X]/(X^N - 1) */
+               /* form f = 1 + pF */
+               for (i = 0; i < params->N; i++)
+               {
+                       ringel_buf1[i] = (ringel_buf1[i] * 3) & mod_q_mask;
+               }
+               ringel_buf1[0] = (ringel_buf1[0] + 1) & mod_q_mask;
 
-        if (!ntru_ring_inv(ringel_buf1, params->N, params->q,
-                           scratch_buf, ringel_buf2))
+               /* find f^-1 in (Z/qZ)[X]/(X^N - 1) */
+               if (!ntru_ring_inv(ringel_buf1, params->N, params->q,
+                                                  scratch_buf, ringel_buf2))
                {
                        result = NTRU_FAIL;
                }
-    }
+       }
 
        if (result == NTRU_OK)
        {
 
-        /* get random bytes for seed for generating trinary g
+        /* get random bytes for seed for generating trinary polynomial g
          * as a list of indices
          */
         if (!drbg->generate(drbg, params->sec_strength_len * BITS_PER_BYTE,
@@ -1029,53 +1054,52 @@ ntru_crypto_ntru_encrypt_keygen(
 
        if (result == NTRU_OK)
        {
-        uint16_t min_IGF_hash_calls =
-            ((((params->dg << 2) + 2) * params->N_bits) + (md_len << 3) - 1) /
-            (md_len << 3);
-
-        /* generate g */
-
-        result = ntru_gen_poly(hash_algid,
-                               (uint8_t)min_IGF_hash_calls,
-                               seed_len, tmp_buf, tmp_buf,
-                               params->N, params->c_bits,
-                               params->no_bias_limit, FALSE,
-                               (params->dg << 1) + 1, ringel_buf1);
-    }
+               DBG2(DBG_LIB, "generate polynomial g");
+
+               seed = chunk_create(tmp_buf, seed_len);
+               g_poly = ntru_poly_create(hash_algid, seed,
+                                                                 params->c_bits, params->no_bias_limit,
+                                                                 params->N, 2*params->dg + 1, FALSE);
+               if (!g_poly)
+               {
+                  result = NTRU_MGF1_FAIL;
+               }
+   }
 
        if (result == NTRU_OK)
        {
-        uint16_t i;
-
-        /* compute h = p * (f^-1 * g) mod q */
-
-        ntru_ring_mult_indices(ringel_buf2, params->dg + 1, params->dg,
-                               ringel_buf1, params->N, params->q, scratch_buf,
-                               ringel_buf2);
+               uint16_t i;
 
-        for (i = 0; i < params->N; i++)
-            ringel_buf2[i] = (ringel_buf2[i] * 3) & mod_q_mask;
+               /* compute h = p * (f^-1 * g) mod q */
+               g_indices = g_poly->get_indices(g_poly);
+               ntru_ring_mult_indices(ringel_buf2, params->dg + 1, params->dg,
+                                                          g_indices, params->N, params->q, scratch_buf,
+                                                          ringel_buf2);
+               g_poly->destroy(g_poly);
 
-        /* create public key blob */
-
-        ntru_crypto_ntru_encrypt_key_create_pubkey_blob(params, ringel_buf2,
-                                                        pubkey_pack_type,
-                                                        pubkey_blob);
-        *pubkey_blob_len = public_key_blob_len;
-
-        /* create private key blob */
+               for (i = 0; i < params->N; i++)
+               {
+                       ringel_buf2[i] = (ringel_buf2[i] * 3) & mod_q_mask;
+               }
 
-        ntru_crypto_ntru_encrypt_key_create_privkey_blob(params, ringel_buf2,
-                                                         F_buf,
-                                                         privkey_pack_type,
-                                                         tmp_buf, privkey_blob);
-        *privkey_blob_len = private_key_blob_len;
+               /* create public key blob */
+               ntru_crypto_ntru_encrypt_key_create_pubkey_blob(params, ringel_buf2,
+                                                                                                           pubkey_pack_type,
+                                                                                                               pubkey_blob);
+               *pubkey_blob_len = public_key_blob_len;
+
+               /* create private key blob */
+               ntru_crypto_ntru_encrypt_key_create_privkey_blob(params, ringel_buf2,
+                                                                                                                F_indices,
+                                                                                                                privkey_pack_type,
+                                                                                                                tmp_buf, privkey_blob);
+               *privkey_blob_len = private_key_blob_len;
     }
 
-    /* cleanup */
-
-    memset(scratch_buf, 0, scratch_buf_len);
-    free(scratch_buf);
-    
-    return result;
+       /* cleanup */
+       DESTROY_IF(F_poly);
+       memset(scratch_buf, 0, scratch_buf_len);
+       free(scratch_buf);
+  
+       return result;
 }
index cf3c862..05ee538 100644 (file)
@@ -56,7 +56,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         2005,                        /* 2^c - (2^c mod N) */
         11,                          /* c */
         1,                           /* lLen */
-        32,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -76,7 +75,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         449,                         /* 2^c - (2^c mod N) */
         9,                           /* c */
         1,                           /* lLen */
-        31,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -96,7 +94,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         2031,                        /* 2^c - (2^c mod N) */
         11,                          /* c */
         1,                           /* lLen */
-        27,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -116,7 +113,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         7609,                        /* 2^c - (2^c mod N) */
         13,                          /* c */
         1,                           /* lLen */
-        25,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -136,7 +132,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         3787,                        /* 2^c - (2^c mod N) */
         12,                          /* c */
         1,                           /* lLen */
-        15,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -156,7 +151,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         1839,                        /* 2^c - (2^c mod N) */
         11,                          /* c */
         1,                           /* lLen */
-        16,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -176,7 +170,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         887,                         /* 2^c - (2^c mod N) */
         10,                          /* c */
         1,                           /* lLen */
-        13,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -196,7 +189,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         3513,                        /* 2^c - (2^c mod N) */
         12,                          /* c */
         1,                           /* lLen */
-        20,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -216,7 +208,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         1977,                        /* 2^c - (2^c mod N) */
         11,                          /* c */
         1,                           /* lLen */
-        11,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -236,7 +227,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         3805,                        /* 2^c - (2^c mod N) */
         12,                          /* c */
         1,                           /* lLen */
-        13,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -256,7 +246,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         7609,                        /* 2^c - (2^c mod N) */
         13,                          /* c */
         1,                           /* lLen */
-        13,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -276,7 +265,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         7495,                        /* 2^c - (2^c mod N) */
         13,                          /* c */
         1,                           /* lLen */
-        17,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -296,8 +284,7 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         2005,                        /* 2^c - (2^c mod N) */
         11,                          /* c */
         1,                           /* lLen */
-        10,                          /* min. no. of hash calls for IGF-2 */
-    },
+   },
 
     {
         NTRU_EES439EP1,              /* parameter-set id */
@@ -316,7 +303,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         439,                         /* 2^c - (2^c mod N) */
         9,                           /* c */
         1,                           /* lLen */
-        15,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -336,7 +322,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         1779,                        /* 2^c - (2^c mod N) */
         11,                          /* c */
         1,                           /* lLen */
-        12,                          /* min. no. of hash calls for IGF-2 */
     },
 
     {
@@ -356,7 +341,6 @@ static NTRU_ENCRYPT_PARAM_SET ntruParamSets[] = {
         8173,                        /* 2^c - (2^c mod N) */
         13,                          /* c */
         1,                           /* lLen */
-        12,                          /* min. no. of hash calls for IGF-2 */
     },
 
 };
index 08c87be..731bd36 100644 (file)
@@ -66,8 +66,6 @@ typedef struct _NTRU_ENCRYPT_PARAM_SET {
                                                      IGF-2 */
     uint8_t                   m_len_len;          /* no. of octets to hold
                                                      mLenOctets */
-    uint8_t                   min_IGF_hash_calls; /* min. no. of hash calls for
-                                                     IGF-2 */
 } NTRU_ENCRYPT_PARAM_SET;
 
 
index 6969baa..cfd78e2 100644 (file)
  *
  *****************************************************************************/
  
-/******************************************************************************
- *
- * File: ntru_crypto_ntru_poly.c
- *
- * Contents: Routines for generating and operating on polynomials in the
- *           NTRU algorithm.
- *
- *****************************************************************************/
-
-
 #include <stdlib.h>
 #include <string.h>
 #include "ntru_crypto_ntru_poly.h"
 
-#include "ntru_mgf1.h"
-
-#include <utils/debug.h>
-
-/* ntru_gen_poly
- *
- * Generates polynomials by creating for each polynomial, a list of the
- * indices of the +1 coefficients followed by a list of the indices of
- * the -1 coefficients.
- *
- * If a single polynomial is generated (non-product form), indices_counts
- * contains a single value of the total number of indices (for +1 and -1
- * comefficients combined).
- *
- * If multiple polynomials are generated (for product form), their lists of
- * indices are sequentially stored in the indices buffer.  Each byte of
- * indices_counts contains the total number of indices (for +1 and -1
- * coefficients combined) for a single polynomial, beginning with the
- * low-order byte for the first polynomial.  The high-order byte is unused.
- *
- * Returns NTRU_OK if successful.
- * Returns HASH_BAD_ALG if the algorithm is not supported.
- *
- */
-
-uint32_t
-ntru_gen_poly(
-    hash_algorithm_t        hash_algid,      /*  in - hash algorithm ID for
-                                                      IGF-2 */
-    uint8_t                 min_calls,       /*  in - minimum no. of hash
-                                                      calls */
-    uint16_t                seed_len,        /*  in - no. of octets in seed */
-    uint8_t                *seed,            /*  in - pointer to seed */
-    uint8_t                *buf,             /*  in - pointer to working
-                                                      buffer */
-    uint16_t                N,               /*  in - max index + 1 */
-    uint8_t                 c_bits,          /*  in - no. bits for candidate */
-    uint16_t                limit,           /*  in - conversion to index
-                                                      limit */
-    bool                    is_product_form, /*  in - if generating multiple
-                                                      polys */
-    uint32_t                indices_counts,  /*  in - nos. of indices needed */
-    uint16_t               *indices)         /* out - address for indices */
-{
-       uint8_t   md_len;
-    uint8_t  *octets;
-    uint8_t  *used;
-    uint8_t   num_polys;
-    uint16_t  num_indices;
-    uint16_t  octets_available;
-    uint16_t  index_cnt = 0;
-    uint8_t   left = 0;
-    uint8_t   num_left = 0;
-       ntru_mgf1_t *mgf1;
-
-    /* generate minimum MGF1 output */
-       DBG2(DBG_LIB, "MGF1 is seeded with %u bytes", seed_len);
-       mgf1 = ntru_mgf1_create(hash_algid, chunk_create(seed, seed_len), TRUE);
-       if (!mgf1)
-       {
-               return NTRU_MGF1_FAIL;
-       }
-       md_len = mgf1->get_hash_size(mgf1);
-    octets = buf;
-    octets_available = min_calls * md_len;
-
-    /* init indices counts for number of polynomials being generated */
-    if (is_product_form) {
-
-        /* number of indices for poly1 is in low byte of indices_counts,
-         * number of indices for poly2 and poly3 are in next higher bytes
-         */
-
-        num_polys = 3;
-        num_indices = (uint16_t)(indices_counts & 0xff);
-        indices_counts >>= 8;
-
-    } else {
-
-        /* number of bytes for poly is in low 16 bits of indices_counts */
-
-        num_polys = 1;
-        num_indices = (uint16_t)indices_counts;
-    }
-
-    /* init used-index array */
-
-    used = buf + octets_available;
-    memset(used, 0, N);
-
-    /* generate indices (IGF-2) for all polynomials */
-       DBG2(DBG_LIB, "MGF1 generates %u octets for %u indices",
-                                  octets_available, num_indices);
-       if (!mgf1->get_mask(mgf1, octets_available, octets))
-       {
-               mgf1->destroy(mgf1);
-               return NTRU_MGF1_FAIL;
-       }
-
-    while (num_polys > 0) {
-
-        /* generate indices for a single polynomial */
-
-        while (index_cnt < num_indices) {
-            uint16_t index;
-            uint8_t  num_needed;
-
-            /* form next index to convert to an index */
-
-            do {
-                /* use any leftover bits first */
-
-                if (num_left != 0) {
-                    index = left << (c_bits - num_left);
-                } else {
-                    index = 0;
-                }
-
-                /* get the rest of the bits needed from new octets */
-
-                num_needed = c_bits - num_left;
-                while (num_needed != 0)
-                               {
-
-                    /* get another octet */
-                    if (octets_available == 0)
-                                       {
-                        octets = buf;
-                        octets_available = md_len;
-
-                                               DBG2(DBG_LIB, "MGF1 generates another %u octets for the "
-                                                                         "remaining %u indices", octets_available,
-                                                                          num_indices - index_cnt);
-                                               if (!mgf1->get_mask(mgf1, octets_available, octets))
-                                               {
-                                                       mgf1->destroy(mgf1);
-                                                       return NTRU_MGF1_FAIL;
-                                               }
-                    }
-                    left = *octets++;
-                    --octets_available;
-
-                                       if (num_needed <= 8)
-                                       {
-
-                        /* all bits needed to fill the index are in this octet */
-
-                        index |= ((uint16_t)(left)) >> (8 - num_needed);
-                        num_left = 8 - num_needed;
-                        num_needed = 0;
-                        left &= 0xff >> (8 - num_left);
-
-                    } else {
-
-                        /* another octet will be needed after using this
-                         * whole octet
-                         */
-
-                        index |= ((uint16_t)left) << (num_needed - 8);
-                        num_needed -= 8;
-                    }
-                }
-            } while (index >= limit);
-
-            /* form index and check if unique */
-
-            index %= N;
-                       if (!used[index])
-                       {
-                used[index] = 1;
-                indices[index_cnt] = index;
-                ++index_cnt;
-            }
-        }
-        --num_polys;
-
-        /* init for next polynomial if another polynomial to be generated */
-
-               if (num_polys > 0)
-               {
-            memset(used, 0, N);
-            num_indices = num_indices +
-                          (uint16_t)(indices_counts & 0xff);
-            indices_counts >>= 8;
-        }
-    }
-       mgf1->destroy(mgf1);
-
-       return NTRU_OK;
-}
-
-
 /* ntru_poly_check_min_weight
  *
  * Checks that the number of 0, +1, and -1 trinary ring elements meet or exceed
index 9d0406b..e2bd35b 100644 (file)
 
 /* function declarations */
 
-/* ntru_gen_poly
- *
- * Generates polynomials by creating for each polynomial, a list of the
- * indices of the +1 coefficients followed by a list of the indices of
- * the -1 coefficients.
- *
- * If a single polynomial is generated (non-product form), indices_counts
- * contains a single value of the total number of indices (for +1 and -1
- * comefficients combined).
- *
- * If multiple polynomials are generated (for product form), their lists of
- * indices are sequentially stored in the indices buffer.  Each byte of
- * indices_counts contains the total number of indices (for +1 and -1
- * coefficients combined) for a single polynomial, beginning with the
- * low-order byte for the first polynomial.  The high-order byte is unused.
- *
- * Returns NTRU_OK if successful.
- * Returns HASH_BAD_ALG if the algorithm is not supported.
- *
- */
-
-extern uint32_t
-ntru_gen_poly(
-    hash_algorithm_t       hash_algid,      /*  in - hash algorithm ID for
-                                                      IGF-2 */
-    uint8_t                 min_calls,       /*  in - minimum no. of hash
-                                                      calls */
-    uint16_t                seed_len,        /*  in - no. of octets in seed */
-    uint8_t                *seed,            /*  in - pointer to seed */
-    uint8_t                *buf,             /*  in - pointer to working
-                                                      buffer */
-    uint16_t                N,               /*  in - max index + 1 */
-    uint8_t                 c_bits,          /*  in - no. bits for candidate */
-    uint16_t                limit,           /*  in - conversion to index
-                                                      limit */
-    bool                    is_product_form, /*  in - if generating multiple
-                                                      polys */
-    uint32_t                indices_counts,  /*  in - nos. of indices needed */
-    uint16_t               *indices);        /* out - address for indices */
-
-
 /* ntru_poly_check_min_weight
  *
  * Checks that the number of 0, +1, and -1 trinary ring elements meet or exceed
diff --git a/src/libstrongswan/plugins/ntru/ntru_poly.c b/src/libstrongswan/plugins/ntru/ntru_poly.c
new file mode 100644 (file)
index 0000000..a021ace
--- /dev/null
@@ -0,0 +1,189 @@
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * Copyright (C) 2009-2013  Security Innovation
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+#include "ntru_poly.h"
+#include "ntru_mgf1.h"
+
+#include <utils/debug.h>
+#include <utils/test.h>
+
+typedef struct private_ntru_poly_t private_ntru_poly_t;
+
+/**
+ * Private data of an ntru_poly_t object.
+ */
+struct private_ntru_poly_t {
+
+       /**
+        * Public ntru_poly_t interface.
+        */
+       ntru_poly_t public;
+
+       /**
+        * Array containing the indices of the non-zero coefficients
+        */
+       uint16_t *indices;
+
+       /**
+        * Number of non-zero coefficients
+        */
+       uint32_t indices_len;
+
+};
+
+METHOD(ntru_poly_t, get_size, size_t,
+       private_ntru_poly_t *this)
+{
+       return this->indices_len;
+}
+
+METHOD(ntru_poly_t, get_indices, uint16_t*,
+       private_ntru_poly_t *this)
+{
+       return this->indices;
+}
+
+METHOD(ntru_poly_t, destroy, void,
+       private_ntru_poly_t *this)
+{
+       memwipe(this->indices, this->indices_len);
+       free(this->indices);
+       free(this);
+}
+
+/*
+ * Described in header.
+ */
+ntru_poly_t *ntru_poly_create(hash_algorithm_t alg, chunk_t seed,
+                                                         uint8_t c_bits, uint16_t limit, 
+                                                 uint16_t poly_len, uint32_t indices_count,
+                                                         bool is_product_form)
+{
+       private_ntru_poly_t *this;
+       size_t hash_len, octet_count = 0, i, num_polys, num_indices[3], indices_len;
+       uint8_t octets[HASH_SIZE_SHA512], *used, num_left = 0, num_needed;
+       uint16_t index, left = 0;
+       int poly_i = 0, index_i = 0;
+       ntru_mgf1_t *mgf1;
+
+       DBG2(DBG_LIB, "MGF1 is seeded with %u bytes", seed.len);
+       mgf1 = ntru_mgf1_create(alg, seed, TRUE);
+       if (!mgf1)
+       {
+           return NULL;
+       }
+       i = hash_len = mgf1->get_hash_size(mgf1);
+
+       if (is_product_form)
+       {
+               num_polys = 3;
+               num_indices[0] = 0xff &  indices_count;
+               num_indices[1] = 0xff & (indices_count >> 8);
+               num_indices[2] = 0xff & (indices_count >> 16);
+               indices_len = num_indices[0] + num_indices[1] + num_indices[2];
+       }
+       else
+       {
+               num_polys = 1;
+               num_indices[0] = indices_count;
+               indices_len = indices_count;
+       }
+       used = malloc(poly_len);
+
+       INIT(this,
+               .public = {
+                       .get_size = _get_size,
+                       .get_indices = _get_indices,
+                       .destroy = _destroy,
+               },
+               .indices_len = indices_len,
+               .indices = malloc(indices_len * sizeof(uint16_t)),
+       );
+
+       /* generate indices for all polynomials */
+       while (poly_i < num_polys)
+       {
+               memset(used, 0, poly_len);
+
+               /* generate indices for a single polynomial */
+               while (num_indices[poly_i])
+               {
+                       /* generate a random candidate index with a size of c_bits */           
+                       do
+                       {
+                               /* use any leftover bits first */
+                               index = num_left ? left << (c_bits - num_left) : 0;
+
+                               /* get the rest of the bits needed from new octets */
+                               num_needed = c_bits - num_left;
+
+                               while (num_needed)
+                               {
+                                       if (i == hash_len)
+                                       {
+                                               /* get another block from MGF1 */
+                                               if (!mgf1->get_mask(mgf1, hash_len, octets))
+                                               {
+                                                       mgf1->destroy(mgf1);
+                                                       destroy(this);
+                                                       free(used);
+                                                       return NULL;
+                                               }
+                                               octet_count += hash_len;
+                                               i = 0;
+                                       }
+                                       left = octets[i++];
+
+                                       if (num_needed <= 8)
+                                       {
+                                               /* all bits needed to fill the index are in this octet */
+                                               index |= left >> (8 - num_needed);
+                                               num_left = 8 - num_needed;
+                                               num_needed = 0;
+                                               left &= 0xff >> (8 - num_left);
+                                       }
+                                       else
+                                       {
+                                               /* more than one octet will be needed */
+                                               index |= left << (num_needed - 8);
+                                               num_needed -= 8;
+                                       }
+                               }
+                       }
+                       while (index >= limit);
+
+                       /* form index and check if unique */
+                       index %= poly_len;
+                       if (!used[index])
+                       {
+                               used[index] = 1;
+                               this->indices[index_i++] = index;
+                               num_indices[poly_i]--;
+                       }
+               }
+               poly_i++;
+       }
+
+       DBG2(DBG_LIB, "MGF1 generates %u octets to derive %u indices",
+                                  octet_count, this->indices_len);
+       mgf1->destroy(mgf1);
+       free(used);
+
+       return &this->public;
+}
+
+EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create);
diff --git a/src/libstrongswan/plugins/ntru/ntru_poly.h b/src/libstrongswan/plugins/ntru/ntru_poly.h
new file mode 100644 (file)
index 0000000..85bc341
--- /dev/null
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup ntru_poly ntru_poly
+ * @{ @ingroup ntru_p
+ */
+
+#ifndef NTRU_POLY_H_
+#define NTRU_POLY_H_
+
+typedef struct ntru_poly_t ntru_poly_t;
+
+#include <library.h>
+
+/**
+ * Implements a trinary polynomial storing the indices of non-zero coefficients 
+ */
+struct ntru_poly_t {
+
+       /**
+        * Get the size of the indices array
+        *
+        * @return                      number of indices
+        */
+       size_t (*get_size)(ntru_poly_t *this);
+
+       /**
+        * @return              array containing the indices of the non-zero coefficients
+        */
+       uint16_t* (*get_indices)(ntru_poly_t *this);
+
+       /**
+        * Destroy ntru_poly_t object
+        */
+       void (*destroy)(ntru_poly_t *this);
+};
+
+/**
+ * Create a trits polynomial from a seed using MGF1 with a base hash function
+ *
+ * @param alg                          hash algorithm to be used by MGF1
+ * @param seed                         seed used by MGF1 to generate trits from
+ * @param poly_len                     size of the trits polynomial
+ * @param c_bits                       number of bits for candidate index
+ * @param limit                                conversion to index limit
+ * @param indices_count                number of non-zero indices
+ * @param is_product_form      generate multiple polynomials
+ */
+ntru_poly_t *ntru_poly_create(hash_algorithm_t alg, chunk_t seed,
+                                                         uint8_t c_bits, uint16_t limit, 
+                                                 uint16_t poly_len, uint32_t indices_count,
+                                                         bool is_product_form);
+
+#endif /** NTRU_POLY_H_ @}*/
+
index 75cf81e..23ce695 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013 Andreas Steffen
+ * Copyright (C) 2013-2014 Andreas Steffen
  * HSR Hochschule fuer Technik Rapperswil
  *
  * This program is free software; you can redistribute it and/or modify it
@@ -19,6 +19,7 @@
 #include <plugins/ntru/ntru_drbg.h>
 #include <plugins/ntru/ntru_mgf1.h>
 #include <plugins/ntru/ntru_trits.h>
+#include <plugins/ntru/ntru_poly.h>
 #include <utils/test.h>
 
 IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_drbg_create, ntru_drbg_t*,
@@ -30,6 +31,11 @@ IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_mgf1_create, ntru_mgf1_t*,
 IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_trits_create, ntru_trits_t*,
                                                  size_t len, hash_algorithm_t alg, chunk_t seed)
 
+IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create, ntru_poly_t*,
+                                                 hash_algorithm_t alg, chunk_t seed, uint8_t c_bits,
+                                                 uint16_t limit, uint16_t poly_len,
+                                                 uint32_t indices_count, bool is_product_form)
+
 /**
  * NTRU parameter sets to test
  */
@@ -295,20 +301,74 @@ START_TEST(test_ntru_drbg_reseed)
 END_TEST
 
 typedef struct {
+       uint8_t c_bits;
+       uint16_t limit;
+       uint16_t poly_len;
+       bool is_product_form;
+       uint32_t indices_count;
+       uint32_t indices_len;
+       uint16_t *indices;
+} poly_test_t;
+
+typedef struct {
        hash_algorithm_t alg;
        size_t hash_size;
-       size_t ml1, ml2, ml3;
+       size_t ml1, ml2, ml3, seed_len;
        chunk_t seed;
        chunk_t hashed_seed;
        chunk_t mask;
        chunk_t trits;
+       poly_test_t poly_test[2];
 } mgf1_test_t;
 
+uint16_t indices_ees439ep1[] = {
+       367, 413,  16, 214, 114, 128,  42, 268, 346, 329, 119, 303, 208, 287, 150,
+         3,  45, 321, 110, 109, 272, 430,  80, 305,  51, 381, 322, 140, 207, 315,
+       206, 186,  56,   5, 273, 177,  44, 100, 205, 210,  98, 191,   8, 336
+};
+
+uint16_t indices_ees613ep1[] = {
+       245, 391, 251, 428, 301,   2, 176, 296, 461, 224, 590, 215, 250,  91, 395,
+       363,  58, 537, 278, 291, 247,  33, 140, 447, 172, 514, 424, 412,  95,  94,
+       281, 159, 196, 302, 277,  63, 404, 150, 608, 315, 195, 334, 207, 376, 398,
+         0, 309, 486, 516,  86, 267, 139, 130,  38, 141, 258,  21, 341, 526, 388,
+       194, 116, 138, 524, 547, 383, 542, 406, 270, 438, 240, 445, 527, 168, 320,
+       186, 327, 212, 543,  82, 606, 131, 294, 392, 477, 430, 583, 142, 253, 434,
+       134, 458, 559, 414, 162, 407, 580, 577, 191, 109, 554, 523,  32,  62, 297,
+       283, 268,  54, 539,   5
+};
+
+uint16_t indices_ees743ep1[] = {
+       285,  62, 136, 655, 460,  35, 450, 208, 340, 212,  61, 234, 454,  52, 520,
+       399, 315, 616, 496,  88, 280, 543, 508, 237, 553,  39, 214, 253, 720, 291,
+       586, 615, 635, 596,  62, 499, 301, 176, 271, 659, 372, 185, 621, 350, 683,
+       180, 717, 509, 641, 738, 666, 171, 639, 606, 353, 706, 237, 358, 410, 423,
+       197, 501, 261, 654, 658, 701, 377, 182, 548, 287, 700, 403, 248, 137
+};
+
+uint16_t indices_ees1171ep1[] = {
+       514, 702, 760, 505, 262, 486, 695, 783, 533,  74, 403, 847, 170,1019, 568,
+       676,1057, 277,1021, 238, 203, 884, 124,  87,  65,  93, 131, 881,1102, 133,
+       459, 462,  92,  40,   5,1152,1158, 297, 599, 299,   7, 458, 347, 343, 173,
+   1044, 264, 871, 819, 679, 328, 438, 990, 982, 308,1135, 423, 470, 254, 295,
+   1029, 892, 759, 789, 123, 939, 749, 353,1062, 145, 562, 337, 550, 102, 549,
+       821,1098, 823,  96, 365, 135,1110, 334, 391, 638, 963, 962,1002,1069, 993,
+       983, 649,1056, 399, 385, 715, 582, 799, 161, 512, 629, 979, 250,  37, 213,
+       929, 413, 566, 336, 727, 160, 616,1170, 748, 282,1115, 325, 994, 189, 500,
+       913, 332,1118, 753, 946, 775,  59, 809, 782, 612, 909,1090, 223, 777, 940,
+       866,1032, 471, 298, 969, 192, 411, 721, 476, 910,1045,1027, 812, 352, 487,
+       215, 625, 808, 230, 602, 457, 900, 416, 985, 850, 908, 155, 670, 669,1054,
+       400,1126, 733, 647, 786, 195, 148, 362,1094, 389,1086,1166, 231, 436, 210,
+       333, 824, 785, 826, 658, 472, 639,1046,1028, 519, 422,  80, 924,1089, 547,
+   1157, 579,   2, 508,1040, 998, 902,1058, 600, 220, 805, 945, 140,1117, 179,
+       536, 191
+};
+
 /**
  * MGF1 Mask Generation Function Test Vectors
  */
 mgf1_test_t mgf1_tests[] = {
-       {       HASH_SHA1, 20, 60, 20, 15,
+       {       HASH_SHA1, 20, 60, 20, 15, 24,
                chunk_from_chars( 
                                                0xED, 0xA5, 0xC3, 0xBC, 0xAF, 0xB3, 0x20, 0x7D,
                                                0x14, 0xA1, 0x54, 0xF7, 0x8B, 0x37, 0xF2, 0x8D,
@@ -366,9 +426,17 @@ mgf1_test_t mgf1_tests[] = {
                                2, 1, 2, 1, 2,  2, 1, 2, 1, 1,  0, 1, 1, 1, 1,  2, 0, 2, 2, 1,
                                0, 1, 1, 2, 1,  2, 0, 2, 1, 0,  1, 0, 1, 0, 1,  2, 0, 1, 1, 0,
                                0, 1, 1, 2, 0,  2, 2, 0, 0, 0,  1, 1, 0, 1, 0,  1, 1, 0, 1, 1,
-                               0, 1, 2, 0, 1,  1, 0, 1, 2, 0,  0, 1, 2, 2, 0,  0, 2, 1, 2)
+                               0, 1, 2, 0, 1,  1, 0, 1, 2, 0,  0, 1, 2, 2, 0,  0, 2, 1, 2),
+               {
+                       {       9, 439, 439, TRUE, 2*(9 + (8 << 8) + (5 << 16)),
+                               countof(indices_ees439ep1), indices_ees439ep1
+                       },
+                       {       11, 1839, 613, FALSE, 2*55,
+                               countof(indices_ees613ep1), indices_ees613ep1
+                       }
+               }
        },
-       {       HASH_SHA256, 32, 64, 32, 33,
+       {       HASH_SHA256, 32, 64, 32, 33, 40,
                chunk_from_chars(
                                                0x52, 0xC5, 0xDD, 0x1E, 0xEF, 0x76, 0x1B, 0x53,
                                                0x08, 0xE4, 0x86, 0x3F, 0x91, 0x12, 0x98, 0x69,
@@ -445,7 +513,15 @@ mgf1_test_t mgf1_tests[] = {
                                0, 0, 0, 1, 1,  0, 0, 2, 2, 2,  2, 2, 0, 1, 2,  0, 1, 2, 0, 1,
                                1, 0, 1, 1, 2,  2, 0, 1, 1, 0,  2, 2, 1, 1, 1,  2, 1, 2, 2, 1,
                                1, 0, 1, 0, 2,  2, 1, 0, 2, 2,  2, 2, 2, 1, 0,  2, 2, 2, 1, 2,
-                               0, 2, 0, 0, 0,  0, 0, 1, 2, 0,  1, 0, 1)
+                               0, 2, 0, 0, 0,  0, 0, 1, 2, 0,  1, 0, 1),
+               {
+                       {       13, 8173, 743, TRUE, 2*(11 + (11 << 8) + (15 << 16)),
+                               countof(indices_ees743ep1), indices_ees743ep1
+                       },
+                       {       12, 3513, 1171, FALSE, 2*106,
+                               countof(indices_ees1171ep1), indices_ees1171ep1
+                       }
+               }
        }
 };
 
@@ -545,6 +621,40 @@ START_TEST(test_ntru_trits)
 }
 END_TEST
 
+START_TEST(test_ntru_poly)
+{
+       ntru_poly_t *poly;
+       uint16_t *indices;
+       chunk_t seed;
+       poly_test_t *p;
+       int j, n;
+
+       seed = mgf1_tests[_i].seed;
+       seed.len = mgf1_tests[_i].seed_len;
+
+       p = &mgf1_tests[_i].poly_test[0];
+       poly = ntru_poly_create(HASH_UNKNOWN, seed, p->c_bits, p->limit,
+                                                       p->poly_len, p->indices_count, p->is_product_form);
+       ck_assert(poly == NULL);
+
+       for (n = 0; n < 2; n++)
+       {
+               p = &mgf1_tests[_i].poly_test[n];
+               poly = ntru_poly_create(mgf1_tests[_i].alg, seed, p->c_bits, p->limit,
+                                                               p->poly_len, p->indices_count,
+                                                               p->is_product_form);
+               ck_assert(poly != NULL && poly->get_size(poly) == p->indices_len);
+
+               indices = poly->get_indices(poly);
+               for (j = 0; j < p->indices_len; j++)
+               {
+                       ck_assert(indices[j] == p->indices[j]);
+               }
+               poly->destroy(poly);
+       }
+}
+END_TEST
+
 START_TEST(test_ntru_ke)
 {
        chunk_t pub_key, cipher_text, i_shared_secret, r_shared_secret;
@@ -755,6 +865,10 @@ Suite *ntru_suite_create()
        tcase_add_loop_test(tc, test_ntru_trits, 0, countof(mgf1_tests));
        suite_add_tcase(s, tc);
 
+       tc = tcase_create("poly");
+       tcase_add_loop_test(tc, test_ntru_poly, 0, countof(mgf1_tests));
+       suite_add_tcase(s, tc);
+
        tc = tcase_create("ke");
        tcase_add_loop_test(tc, test_ntru_ke, 0, countof(params));
        suite_add_tcase(s, tc);