Added get_array() method to ntru_poly_t class
authorAndreas Steffen <andreas.steffen@strongswan.org>
Thu, 27 Feb 2014 21:08:22 +0000 (22:08 +0100)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Thu, 27 Feb 2014 21:08:22 +0000 (22:08 +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 4644494..dba8191 100644 (file)
@@ -951,57 +951,9 @@ ntru_crypto_ntru_encrypt_keygen(
 
        if (result == NTRU_OK)
        {
-        uint32_t i;
+               int i;
 
-               memset(ringel_buf1, 0, params->N * sizeof(uint16_t));
-               F_indices = F_poly->get_indices(F_poly);
-
-               /* 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_indices[i]] = 1;
-                       }
-                       for (; i < (dF1 << 1); i++)
-                       {
-                               ringel_buf1[F_indices[i]] = mod_q_mask;
-                       }
-
-                       /* 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);
-
-                       /* form (F1 * F2) + F3 */
-                       for (i = 0; i < dF3; i++)
-                       {
-                               uint16_t index = F_indices[dF3_offset + i];
-
-                               ringel_buf1[index] = (ringel_buf1[index] + 1) & mod_q_mask;
-                       }
-                       for (; i < (dF3 << 1); i++)
-                       {
-                               uint16_t index = F_indices[dF3_offset + i];
-
-                               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;
-                       }
-               }
+               F_poly->get_array(F_poly, ringel_buf1);
 
                /* form f = 1 + pF */
                for (i = 0; i < params->N; i++)
@@ -1065,6 +1017,7 @@ ntru_crypto_ntru_encrypt_keygen(
                *pubkey_blob_len = public_key_blob_len;
 
                /* create private key blob */
+               F_indices = F_poly->get_indices(F_poly);
                ntru_crypto_ntru_encrypt_key_create_privkey_blob(params, ringel_buf2,
                                                                                                                 F_indices,
                                                                                                                 privkey_pack_type,
index 0bb3404..8e4eede 100644 (file)
@@ -51,77 +51,6 @@ ntru_poly_check_min_weight(
     return TRUE;
 }
 
-
-/* ntru_ring_mult_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 a sparse trinary polynomial with coefficients -1, 0,
- * and 1.  It is specified by a list, bi, of its nonzero indices containing
- * indices for the bi_P1_len +1 coefficients followed by the indices for the
- * bi_M1_len -1 coefficients.
- * The indices are in the range [0,N).
- *
- * The result array "c" may share the same memory space as input array "a",
- * input array "b", or temp array "t".
- *
- * 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_indices(
-    uint16_t const *a,          /*  in - pointer to ring element a */
-    uint16_t        bi_P1_len,  /*  in - no. of +1 coefficients in b */
-    uint16_t        bi_M1_len,  /*  in - no. of -1 coefficients in b */
-    uint16_t const *bi,         /*  in - pointer to the list of nonzero
-                                         indices of ring element b,
-                                         containing indices for the +1
-                                         coefficients followed by the
-                                         indices for -1 coefficients */
-    uint16_t        N,          /*  in - no. of coefficients in a, b, c */
-    uint16_t        q,          /*  in - large modulus */
-    uint16_t       *t,          /*  in - temp buffer of N elements */
-    uint16_t       *c)          /* out - address for polynomial c */
-{
-    uint16_t mod_q_mask = q - 1;
-    uint16_t i, j, k;
-
-    /* t[(i+k)%N] = sum i=0 through N-1 of a[i], for b[k] = -1 */
-
-    for (k = 0; k < N; k++)
-        t[k] = 0;
-    for (j = bi_P1_len; j < bi_P1_len + bi_M1_len; j++) {
-        k = bi[j];
-        for (i = 0; k < N; ++i, ++k)
-            t[k] = t[k] + a[i];
-        for (k = 0; i < N; ++i, ++k)
-            t[k] = t[k] + a[i];
-    }
-
-    /* t[(i+k)%N] = -(sum i=0 through N-1 of a[i] for b[k] = -1) */
-
-    for (k = 0; k < N; k++)
-        t[k] = -t[k];
-
-    /* t[(i+k)%N] += sum i=0 through N-1 of a[i] for b[k] = +1 */
-
-    for (j = 0; j < bi_P1_len; j++) {
-        k = bi[j];
-        for (i = 0; k < N; ++i, ++k)
-            t[k] = t[k] + a[i];
-        for (k = 0; i < N; ++i, ++k)
-            t[k] = t[k] + a[i];
-    }
-
-    /* c = (a * b) mod q */
-
-    for (k = 0; k < N; k++)
-        c[k] = t[k] & mod_q_mask;
-}
-
 /* ntru_ring_mult_coefficients
  *
  * Multiplies ring element (polynomial) "a" by ring element (polynomial) "b"
index 35b022e..1e9d467 100644 (file)
@@ -55,41 +55,6 @@ ntru_poly_check_min_weight(
     uint8_t  *ringels,              /*  in - pointer to trinary ring elements */
     uint16_t  min_wt);              /*  in - minimum weight */
 
-
-/* ntru_ring_mult_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 a sparse trinary polynomial with coefficients -1, 0,
- * and 1.  It is specified by a list, bi, of its nonzero indices containing
- * indices for the bi_P1_len +1 coefficients followed by the indices for the
- * bi_M1_len -1 coefficients.
- * 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_indices(
-    uint16_t const *a,          /*  in - pointer to ring element a */
-    uint16_t        bi_P1_len,  /*  in - no. of +1 coefficients in b */
-    uint16_t        bi_M1_len,  /*  in - no. of -1 coefficients in b */
-    uint16_t const *bi,         /*  in - pointer to the list of nonzero
-                                         indices of ring element b,
-                                         containing indices for the +1
-                                         coefficients followed by the
-                                         indices for -1 coefficients */
-    uint16_t        N,          /*  in - no. of coefficients in a, b, c */
-    uint16_t        q,          /*  in - large modulus */
-    uint16_t       *t,          /*  in - temp buffer of N elements */
-    uint16_t       *c);         /* out - address for polynomial c */
-
 /* ntru_ring_mult_coefficients
  *
  * Multiplies ring element (polynomial) "a" by ring element (polynomial) "b"
index 115fd35..9cc537f 100644 (file)
@@ -87,6 +87,7 @@ METHOD(ntru_poly_t, get_indices, uint16_t*,
 {
        return this->indices;
 }
+
 /**
   * Multiplication of polynomial a with a sparse polynomial b given by
   * the indices of its +1 and -1 coefficients results in polynomial c.
@@ -145,6 +146,52 @@ static void ring_mult_i(uint16_t *a, indices_len_t len, uint16_t *indices,
        }
 }
 
+METHOD(ntru_poly_t, get_array, void,
+       private_ntru_poly_t *this, uint16_t *array)
+{
+       uint16_t *t, *bi;
+       uint16_t mod_q_mask = this->q - 1;
+       indices_len_t len;
+       int i;
+
+       /* form polynomial F or F1 */
+       memset(array, 0x00, this->N * sizeof(uint16_t));
+       bi = this->indices;
+       len = this->indices_len[0];
+       for (i = 0; i < len.p + len.m; i++)
+       {
+               array[bi[i]] = (i < len.p) ? 1 : mod_q_mask;
+       }
+
+       if (this->num_polynomials == 3)
+       {
+               /* allocate temporary array t */
+               t = malloc(this->N * sizeof(uint16_t));
+
+               /* form F1 * F2 */
+               bi += len.p + len.m;
+               len = this->indices_len[1];
+               ring_mult_i(array, len, bi, this->N, mod_q_mask, t, array);
+
+               /* form (F1 * F2) + F3 */
+               bi += len.p + len.m;
+               len = this->indices_len[2];
+               for (i = 0; i < len.p + len.m; i++)
+               {
+                       if (i < len.p)
+                       {
+                               array[bi[i]] += 1;
+                       }
+                       else
+                       {
+                               array[bi[i]] -= 1;
+                       }
+                       array[bi[i]] &= mod_q_mask;
+               }
+               free(t);
+       }
+}
+
 METHOD(ntru_poly_t, ring_mult, void,
        private_ntru_poly_t *this, uint16_t *a, uint16_t *c)
 {
@@ -222,6 +269,7 @@ ntru_poly_t *ntru_poly_create_from_seed(hash_algorithm_t alg, chunk_t seed,
                .public = {
                        .get_size = _get_size,
                        .get_indices = _get_indices,
+                       .get_array = _get_array,
                        .ring_mult = _ring_mult,
                        .destroy = _destroy,
                },
@@ -338,6 +386,7 @@ ntru_poly_t *ntru_poly_create_from_data(uint16_t *data, uint16_t N, uint16_t q,
                .public = {
                        .get_size = _get_size,
                        .get_indices = _get_indices,
+                       .get_array = _get_array,
                        .ring_mult = _ring_mult,
                        .destroy = _destroy,
                },
index 55133c5..87c7710 100644 (file)
@@ -43,6 +43,11 @@ struct ntru_poly_t {
        uint16_t* (*get_indices)(ntru_poly_t *this);
 
        /**
+        * @param array         array containing all N coefficients of the polynomial
+        */
+       void (*get_array)(ntru_poly_t *this, uint16_t *array);
+
+       /**
         * Multiply polynomial a with ntru_poly_t object b having sparse coeffients
         * to form result polynomial c = a * b
         *
index 8e5a036..a46f574 100644 (file)
@@ -752,7 +752,7 @@ START_TEST(test_ntru_ring_mult)
                                                                          t->indices_len_m, t->is_product_form);
        ck_assert(poly != NULL);
 
-       c = malloc(sizeof(uint16_t) * t->N);
+       c = malloc(t->N * sizeof(uint16_t));
        poly->ring_mult(poly, t->a, c);
 
        for (i = 0; i < t->N; i++)
@@ -765,6 +765,34 @@ START_TEST(test_ntru_ring_mult)
 }
 END_TEST
 
+int array_tests[] = { 0, 11, 12, 16 };
+
+START_TEST(test_ntru_array)
+{
+       ntru_poly_t *poly;
+       ring_mult_test_t *t;
+       uint16_t *c;
+       int i;
+
+       t = &ring_mult_tests[array_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(t->N * sizeof(uint16_t));
+       poly->get_array(poly, 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;
@@ -983,6 +1011,10 @@ Suite *ntru_suite_create()
        tcase_add_loop_test(tc, test_ntru_ring_mult, 0, countof(ring_mult_tests));
        suite_add_tcase(s, tc);
 
+       tc = tcase_create("array");
+       tcase_add_loop_test(tc, test_ntru_array, 0, countof(array_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);