Defined ntru_poly_create_from_seed() and ntru_poly_create_from_data() constructors...
authorAndreas Steffen <andreas.steffen@strongswan.org>
Thu, 27 Feb 2014 19:36:17 +0000 (20:36 +0100)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Thu, 27 Feb 2014 19:36:17 +0000 (20:36 +0100)
src/libstrongswan/plugins/ntru/ntru_crypto/ntru_crypto_ntru_encrypt.c
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
src/libstrongswan/plugins/ntru/ntru_poly.h
src/libstrongswan/tests/suites/test_ntru.c

index af218d6..4644494 100644 (file)
@@ -228,9 +228,10 @@ ntru_crypto_ntru_encrypt(
                        DBG2(DBG_LIB, "generate polynomial r");
 
                        seed = chunk_create(tmp_buf, ptr - tmp_buf);
-                       r_poly = ntru_poly_create(hash_algid, seed, params->c_bits,
-                                                                         params->N, params->q, params->dF_r,
-                                                                         params->dF_r, params->is_product_form);
+                       r_poly = ntru_poly_create_from_seed(hash_algid, seed, params->c_bits,
+                                                                                               params->N, params->q,
+                                                                                               params->dF_r, params->dF_r,
+                                                                                               params->is_product_form);
                        if (!r_poly)
                        {
                           result = NTRU_MGF1_FAIL;
@@ -443,7 +444,7 @@ ntru_crypto_ntru_decrypt(
        ntru_trits_t           *mask;
        uint8_t                *mask_trits;
        chunk_t                 seed;
-       ntru_poly_t                        *r_poly;
+       ntru_poly_t                        *F_poly, *r_poly;
 
        /* check for bad parameters */
        if (!privkey_blob || !ct || !pt_len)
@@ -557,16 +558,16 @@ ntru_crypto_ntru_decrypt(
      *  a = A in the range [-q/2, q/2)
      *  cm' = a mod p
      */
+       F_poly = ntru_poly_create_from_data(i_buf, params->N, params->q,
+                                                                               params->dF_r, params->dF_r,
+                                                                           params->is_product_form);
+       F_poly->ring_mult(F_poly, ringel_buf2, ringel_buf1);
+       F_poly->destroy(F_poly);
 
     cmprime_len = params->N;
     if (params->is_product_form)
        {
          --cmprime_len;
-        ntru_ring_mult_product_indices(ringel_buf2, (uint16_t)dF_r1,
-                                       (uint16_t)dF_r2, (uint16_t)dF_r3,
-                                       i_buf, params->N, params->q,
-                                       scratch_buf, ringel_buf1);
-
                for (i = 0; i < cmprime_len; i++)
                {
                        ringel_buf1[i] = (ringel_buf2[i] + 3 * ringel_buf1[i]) & mod_q_mask;
@@ -587,10 +588,6 @@ ntru_crypto_ntru_decrypt(
        }
        else
        {
-        ntru_ring_mult_indices(ringel_buf2, (uint16_t)dF_r, (uint16_t)dF_r,
-                               i_buf, params->N, params->q,
-                               scratch_buf, ringel_buf1);
-
                for (i = 0; i < cmprime_len; i++)
                {
                        ringel_buf1[i] = (ringel_buf2[i] + 3 * ringel_buf1[i]) & mod_q_mask;
@@ -600,7 +597,7 @@ ntru_crypto_ntru_decrypt(
                        }
                        Mtrin_buf[i] = (uint8_t)(ringel_buf1[i] % 3);
                }
-}
+       }
 
     /* check that the candidate message representative meets minimum weight
      * requirements
@@ -707,9 +704,10 @@ ntru_crypto_ntru_decrypt(
                DBG2(DBG_LIB, "generate polynomial r");
 
                seed = chunk_create(tmp_buf, ptr - tmp_buf);
-               r_poly = ntru_poly_create(hash_algid, seed, params->c_bits,
-                                                                 params->N, params->q, params->dF_r,
-                                                                 params->dF_r, params->is_product_form);
+               r_poly = ntru_poly_create_from_seed(hash_algid, seed, params->c_bits,
+                                                                                       params->N, params->q,
+                                                                                       params->dF_r, params->dF_r,
+                                                                                       params->is_product_form);
                if (!r_poly)
                {
                   result = NTRU_MGF1_FAIL;
@@ -941,9 +939,10 @@ ntru_crypto_ntru_encrypt_keygen(
                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->N, params->q, params->dF_r,
-                                                                 params->dF_r, params->is_product_form);
+               F_poly = ntru_poly_create_from_seed(hash_algid, seed, params->c_bits,
+                                                                                       params->N, params->q,
+                                                                                       params->dF_r, params->dF_r,
+                                                                                       params->is_product_form);
                if (!F_poly)
                {
                   result = NTRU_MGF1_FAIL;
@@ -1037,9 +1036,9 @@ ntru_crypto_ntru_encrypt_keygen(
                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->N, params->q, params->dg + 1,
-                                                                 params->dg, FALSE);
+               g_poly = ntru_poly_create_from_seed(hash_algid, seed, params->c_bits,
+                                                                                       params->N, params->q,
+                                                                                       params->dg + 1, params->dg, FALSE);
                if (!g_poly)
                {
                   result = NTRU_MGF1_FAIL;
index cfd78e2..0bb3404 100644 (file)
@@ -122,66 +122,6 @@ ntru_ring_mult_indices(
         c[k] = t[k] & mod_q_mask;
 }
 
-
-/* ntru_ring_mult_product_indices
- *
- * Multiplies ring element (polynomial) "a" by ring element (polynomial) "b"
- * to produce ring element (polynomial) "c" in (Z/qZ)[X]/(X^N - 1).
- * This is a convolution operation.
- *
- * Ring element "b" is represented by the product form b1 * b2 + b3, where
- * b1, b2, and b3 are each a sparse trinary polynomial with coefficients -1,
- * 0, and 1.  It is specified by a list, bi, of the nonzero indices of b1, b2,
- * and b3, containing the indices for the +1 coefficients followed by the
- * indices for the -1 coefficients for each polynomial in that order.
- * The indices are in the range [0,N).
- *
- * The result array "c" may share the same memory space as input array "a",
- * or input array "b".
- *
- * This assumes q is 2^r where 8 < r < 16, so that overflow of the sum
- * beyond 16 bits does not matter.
- */
-
-void
-ntru_ring_mult_product_indices(
-    uint16_t       *a,          /*  in - pointer to ring element a */
-    uint16_t        b1i_len,    /*  in - no. of +1 or -1 coefficients in b1 */
-    uint16_t        b2i_len,    /*  in - no. of +1 or -1 coefficients in b2 */
-    uint16_t        b3i_len,    /*  in - no. of +1 or -1 coefficients in b3 */
-    uint16_t const *bi,         /*  in - pointer to the list of nonzero
-                                         indices of polynomials b1, b2, b3,
-                                         containing indices for the +1
-                                         coefficients followed by the
-                                         indices for -1 coefficients for
-                                         each polynomial */
-    uint16_t        N,          /*  in - no. of coefficients in a, b, c */
-    uint16_t        q,          /*  in - large modulus */
-    uint16_t       *t,          /*  in - temp buffer of 2N elements */
-    uint16_t       *c)          /* out - address for polynomial c */
-{
-    uint16_t *t2 = t + N;
-    uint16_t  mod_q_mask = q - 1;
-    uint16_t  i;
-
-
-    /* t2 = a * b1 */
-    ntru_ring_mult_indices(a, b1i_len, b1i_len, bi, N, q, t, t2);
-
-    /* t2 = (a * b1) * b2 */
-    ntru_ring_mult_indices(t2, b2i_len, b2i_len, bi + (b1i_len << 1), N, q,
-                           t, t2);
-
-    /* t = a * b3 */
-    ntru_ring_mult_indices(a, b3i_len, b3i_len,
-                           bi + ((b1i_len + b2i_len) << 1), N, q, t, t);
-
-    /* c = (a * b1 * b2) + (a * b3) */
-    for (i = 0; i < N; i++)
-        c[i] = (t2[i] + t[i]) & mod_q_mask;
-}
-
-
 /* ntru_ring_mult_coefficients
  *
  * Multiplies ring element (polynomial) "a" by ring element (polynomial) "b"
index e2bd35b..35b022e 100644 (file)
@@ -90,45 +90,6 @@ ntru_ring_mult_indices(
     uint16_t       *t,          /*  in - temp buffer of N elements */
     uint16_t       *c);         /* out - address for polynomial c */
 
-
-/* ntru_ring_mult_product_indices
- *
- * Multiplies ring element (polynomial) "a" by ring element (polynomial) "b"
- * to produce ring element (polynomial) "c" in (Z/qZ)[X]/(X^N - 1).
- * This is a convolution operation.
- *
- * Ring element "b" is represented by the product form b1 * b2 + b3, where
- * b1, b2, and b3 are each a sparse trinary polynomial with coefficients -1,
- * 0, and 1.  It is specified by a list, bi, of the nonzero indices of b1, b2,
- * and b3, containing the indices for the +1 coefficients followed by the
- * indices for the -1 coefficients for each polynomial in that order.
- * The indices are in the range [0,N).
- *
- * The result array "c" may share the same memory space as input array "a",
- * or input array "b".
- *
- * This assumes q is 2^r where 8 < r < 16, so that overflow of the sum
- * beyond 16 bits does not matter.
- */
-
-extern void
-ntru_ring_mult_product_indices(
-    uint16_t       *a,          /*  in - pointer to ring element a */
-    uint16_t        b1i_len,    /*  in - no. of +1 or -1 coefficients in b1 */
-    uint16_t        b2i_len,    /*  in - no. of +1 or -1 coefficients in b2 */
-    uint16_t        b3i_len,    /*  in - no. of +1 or -1 coefficients in b3 */
-    uint16_t const *bi,         /*  in - pointer to the list of nonzero
-                                         indices of polynomials b1, b2, b3,
-                                         containing indices for the +1
-                                         coefficients followed by the
-                                         indices for -1 coefficients for
-                                         each polynomial */
-    uint16_t        N,          /*  in - no. of coefficients in a, b, c */
-    uint16_t        q,          /*  in - large modulus */
-    uint16_t       *t,          /*  in - temp buffer of 2N elements */
-    uint16_t       *c);         /* out - address for polynomial c */
-
-
 /* ntru_ring_mult_coefficients
  *
  * Multiplies ring element (polynomial) "a" by ring element (polynomial) "b"
index a4cc871..115fd35 100644 (file)
@@ -197,10 +197,11 @@ METHOD(ntru_poly_t, destroy, void,
 /*
  * Described in header.
  */
-ntru_poly_t *ntru_poly_create(hash_algorithm_t alg, chunk_t seed,
-                                                         uint8_t c_bits, uint16_t N, uint16_t q,
-                                                         uint32_t indices_len_p, uint32_t indices_len_m,
-                                                         bool is_product_form)
+ntru_poly_t *ntru_poly_create_from_seed(hash_algorithm_t alg, chunk_t seed,
+                                                                               uint8_t c_bits, uint16_t N, uint16_t q,
+                                                                               uint32_t indices_len_p,
+                                                                               uint32_t indices_len_m,
+                                                                               bool is_product_form)
 {
        private_ntru_poly_t *this;
        size_t hash_len, octet_count = 0, i;
@@ -322,4 +323,56 @@ ntru_poly_t *ntru_poly_create(hash_algorithm_t alg, chunk_t seed,
        return &this->public;
 }
 
-EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create);
+/*
+ * Described in header.
+ */
+ntru_poly_t *ntru_poly_create_from_data(uint16_t *data, uint16_t N, uint16_t q,
+                                                                               uint32_t indices_len_p,
+                                                                               uint32_t indices_len_m,
+                                                                               bool is_product_form)
+{
+       private_ntru_poly_t *this;
+       int n, i, num_indices;
+
+       INIT(this,
+               .public = {
+                       .get_size = _get_size,
+                       .get_indices = _get_indices,
+                       .ring_mult = _ring_mult,
+                       .destroy = _destroy,
+               },
+               .N = N,
+               .q = q,
+       );
+
+       if (is_product_form)
+       {
+               this->num_polynomials = 3;
+               for (n = 0; n < 3; n++)
+               {
+                       this->indices_len[n].p = 0xff & indices_len_p;
+                       this->indices_len[n].m = 0xff & indices_len_m;
+                       indices_len_p >>= 8;
+                       indices_len_m >>= 8;
+               }
+       }
+       else
+       {
+               this->num_polynomials = 1;
+               this->indices_len[0].p = indices_len_p;
+               this->indices_len[0].m = indices_len_m;
+       }
+       num_indices = get_size(this);
+
+       this->indices = malloc(sizeof(uint16_t) * num_indices);
+       for (i = 0; i < num_indices; i++)
+       {
+               this->indices[i] = data[i];
+       }
+
+       return &this->public;
+}
+
+EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_seed);
+
+EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_data);
index d698f81..55133c5 100644 (file)
@@ -69,10 +69,26 @@ struct ntru_poly_t {
  * @param indices_len_m                number of indices for -1 coefficients
  * @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 N, uint16_t q,
-                                                         uint32_t indices_len_p, uint32_t indices_len_m,
-                                                         bool is_product_form);
+ntru_poly_t *ntru_poly_create_from_seed(hash_algorithm_t alg, chunk_t seed,
+                                                                               uint8_t c_bits, uint16_t N, uint16_t q,
+                                                                               uint32_t indices_len_p,
+                                                                               uint32_t indices_len_m,
+                                                                               bool is_product_form);
+
+/**
+ * Create a trits polynomial from an array of indices of non-zero coefficients
+ *
+ * @param data                         array of indices of non-zero coefficients
+ * @param N                                    ring dimension, number of polynomial coefficients
+ * @param q                                    large modulus
+ * @param indices_len_p                number of indices for +1 coefficients
+ * @param indices_len_m                number of indices for -1 coefficients
+ * @param is_product_form      generate multiple polynomials
+ */
+ntru_poly_t *ntru_poly_create_from_data(uint16_t *data, uint16_t N, uint16_t q,
+                                                                               uint32_t indices_len_p,
+                                                                               uint32_t indices_len_m,
+                                                                               bool is_product_form);
 
 #endif /** NTRU_POLY_H_ @}*/
 
index 3bb7851..8e5a036 100644 (file)
@@ -31,11 +31,16 @@ 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*,
+IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_seed, ntru_poly_t*,
                                                  hash_algorithm_t alg, chunk_t seed, uint8_t c_bits,
                                                  uint16_t N, uint16_t q, uint32_t indices_len_p,
                                                  uint32_t indices_len_m, bool is_product_form)
 
+IMPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_data, ntru_poly_t*,
+                                                 u_int16_t *data, uint16_t N, uint16_t q,
+                                                 uint32_t indices_len_p, uint32_t indices_len_m,
+                                                 bool is_product_form)
+
 /**
  * NTRU parameter sets to test
  */
@@ -633,17 +638,17 @@ START_TEST(test_ntru_poly)
        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->N, p->q,
-                                                       p->indices_len, p->indices_len,
-                                                       p->is_product_form);
+       poly = ntru_poly_create_from_seed(HASH_UNKNOWN, seed, p->c_bits, p->N, p->q,
+                                                                         p->indices_len, p->indices_len,
+                                                                         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->N, p->q,
-                                                               p->indices_len, p->indices_len,
-                                                               p->is_product_form);
+               poly = ntru_poly_create_from_seed(mgf1_tests[_i].alg, seed, p->c_bits,
+                                                                                 p->N, p->q, p->indices_len,
+                                                                                 p->indices_len, p->is_product_form);
                ck_assert(poly != NULL && poly->get_size(poly) == p->indices_size);
 
                indices = poly->get_indices(poly);
@@ -656,6 +661,110 @@ START_TEST(test_ntru_poly)
 }
 END_TEST
 
+typedef struct {
+       uint16_t N;
+       uint16_t q;
+       bool is_product_form;
+       uint32_t indices_len_p;
+       uint32_t indices_len_m;
+       uint16_t *indices;
+       uint16_t *a;
+       uint16_t *c;
+} ring_mult_test_t;
+
+uint16_t t1_indices[] = { 1, 6, 5, 3 };
+
+uint16_t t1_a[] = { 1, 0, 0, 0, 0, 0, 0 };
+uint16_t t1_c[] = { 0, 1, 0, 7, 0, 7, 1 };
+
+uint16_t t2_a[] = { 5, 0, 0, 0, 0, 0, 0 };
+uint16_t t2_c[] = { 0, 5, 0, 3, 0, 3, 5 };
+
+uint16_t t3_a[]  = { 4, 0, 0, 0, 0, 0, 0 };
+uint16_t t3_c[]  = { 0, 4, 0, 4, 0, 4, 4 };
+
+uint16_t t4_a[]  = { 0, 6, 0, 0, 0, 0, 0 };
+uint16_t t4_c[]  = { 6, 0, 6, 0, 2, 0, 2 };
+
+uint16_t t5_a[]  = { 4, 6, 0, 0, 0, 0, 0 };
+uint16_t t5_c[]  = { 6, 4, 6, 4, 2, 4, 6 };
+
+uint16_t t6_a[]  = { 0, 0, 3, 0, 0, 0, 0 };
+uint16_t t6_c[]  = { 5, 3, 0, 3, 0, 5, 0 };
+
+uint16_t t7_a[]  = { 4, 6, 3, 0, 0, 0, 0 };
+uint16_t t7_c[]  = { 3, 7, 6, 7, 2, 1, 6 };
+
+uint16_t t8_a[]  = { 0, 0, 0, 7, 0, 0, 0 };
+uint16_t t8_c[]  = { 0, 1, 7, 0, 7, 0, 1 };
+
+uint16_t t9_a[]  = { 4, 6, 3, 7, 0, 0, 0 };
+uint16_t t9_c[]  = { 3, 0, 5, 7, 1, 1, 7 };
+
+uint16_t t10_a[] = { 0, 0, 0, 0, 0, 1, 0 };
+uint16_t t10_c[] = { 0, 7, 0, 7, 1, 0, 1 };
+
+uint16_t t11_a[] = { 4, 6, 3, 7, 0, 1, 0 };
+uint16_t t11_c[] = { 3, 7, 5, 6, 2, 1, 0 };
+
+uint16_t t2_indices[] = { 1, 6, 5, 2, 3 };
+
+uint16_t t12_c[] = { 0, 1, 7, 7, 0, 1, 1 };
+uint16_t t13_c[] = { 0, 1, 7, 7, 0, 7, 1 };
+uint16_t t14_c[] = { 0, 1, 0, 31, 0, 31, 1 };
+uint16_t t15_c[] = { 0, 5, 0, 2043, 0, 2043, 5 };
+uint16_t t16_c[] = { 0, 5, 0, 32763, 0, 32763, 5 };
+
+uint16_t t3_indices[] = { 7, 2, 3, 5, 0, 2, 3, 10, 7, 0, 8, 2 };
+
+uint16_t t17_a[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+uint16_t t17_c[] = { 7, 1, 0, 1, 1, 7, 0, 7, 7, 7, 2 };
+
+ring_mult_test_t ring_mult_tests[] = {
+       {  7,     8, FALSE, 2, 2, t1_indices, t1_a,  t1_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t2_a,  t2_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t3_a,  t3_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t4_a,  t4_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t5_a,  t5_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t6_a,  t6_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t7_a,  t7_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t8_a,  t8_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t9_a,  t9_c  },
+       {  7,     8, FALSE, 2, 2, t1_indices, t10_a, t10_c },
+       {  7,     8, FALSE, 2, 2, t1_indices, t11_a, t11_c },
+       {  7,     8, FALSE, 3, 2, t2_indices, t1_a,  t12_c },
+       {  7,     8, FALSE, 2, 3, t2_indices, t1_a,  t13_c },
+       {  7,    32, FALSE, 2, 2, t1_indices, t1_a,  t14_c },
+       {  7,  2048, FALSE, 2, 2, t1_indices, t2_a,  t15_c },
+       {  7, 32768, FALSE, 2, 2, t1_indices, t2_a,  t16_c },
+       { 11,     8, TRUE, 197121, 197121, t3_indices, t17_a,  t17_c },
+};
+
+START_TEST(test_ntru_ring_mult)
+{
+       ntru_poly_t *poly;
+       ring_mult_test_t *t;
+       uint16_t *c;
+       int i;
+
+       t = &ring_mult_tests[_i];
+       poly = ntru_poly_create_from_data(t->indices, t->N, t->q, t->indices_len_p,
+                                                                         t->indices_len_m, t->is_product_form);
+       ck_assert(poly != NULL);
+
+       c = malloc(sizeof(uint16_t) * t->N);
+       poly->ring_mult(poly, t->a, c);
+
+       for (i = 0; i < t->N; i++)
+       {
+               ck_assert(c[i] == t->c[i]);
+       }
+
+       free(c);
+       poly->destroy(poly);
+}
+END_TEST
+
 START_TEST(test_ntru_ke)
 {
        chunk_t pub_key, cipher_text, i_shared_secret, r_shared_secret;
@@ -870,6 +979,10 @@ Suite *ntru_suite_create()
        tcase_add_loop_test(tc, test_ntru_poly, 0, countof(mgf1_tests));
        suite_add_tcase(s, tc);
 
+       tc = tcase_create("ring_mult");
+       tcase_add_loop_test(tc, test_ntru_ring_mult, 0, countof(ring_mult_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);