Use mgf1_bitspender to generate random secret key
authorAndreas Steffen <andreas.steffen@strongswan.org>
Sat, 1 Nov 2014 10:29:03 +0000 (11:29 +0100)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Sat, 29 Nov 2014 13:51:15 +0000 (14:51 +0100)
src/libstrongswan/plugins/bliss/bliss_private_key.c

index 38676d6..2af6f2b 100644 (file)
 #include "bliss_param_set.h"
 #include "bliss_fft.h"
 
+#include <crypto/mgf1/mgf1_bitspender.h>
+
 #define _GNU_SOURCE
 #include <stdlib.h>
 
 typedef struct private_bliss_private_key_t private_bliss_private_key_t;
 
+#define SECRET_KEY_TRIALS_MAX  30
+
 /**
  * Private data of a bliss_private_key_t object.
  */
@@ -155,7 +159,7 @@ static private_bliss_private_key_t *bliss_private_key_create_empty(void)
 /**
  * Compute the scalar product of a vector x with a negative wrapped vector y
  */
-static int16_t wrapped_product(int16_t *x, int16_t *y, int n, int shift)
+static int16_t wrapped_product(int8_t *x, int8_t *y, int n, int shift)
 {
        int16_t product = 0;
        int i;
@@ -188,6 +192,9 @@ static void wrap(int16_t *x, int n, int shift, int16_t *x_wrapped)
        }
 }
 
+/**
+ * int16_t compare function needed for qsort()
+ */
 static int compare(const int16_t *a, const int16_t *b)
 {
        int16_t temp = *a - *b;
@@ -209,7 +216,7 @@ static int compare(const int16_t *a, const int16_t *b)
 /**
  * Compute the Nk(S) norm of S = (s1, s2)
  */
-static uint32_t nks_norm(int16_t *s1, int16_t *s2, int n, uint16_t kappa)
+static uint32_t nks_norm(int8_t *s1, int8_t *s2, int n, uint16_t kappa)
 {
        int16_t t[n], t_wrapped[n], max_kappa[n];
        uint32_t nks = 0;
@@ -272,256 +279,172 @@ static uint32_t invert(uint32_t x, uint16_t q)
 }
 
 /**
+ * Create a vector with sparse and small coefficients from seed
+ */
+static int8_t* create_vector_from_seed(private_bliss_private_key_t *this,
+                                                                          hash_algorithm_t alg, chunk_t seed)
+{
+       mgf1_bitspender_t *bitspender;
+       uint32_t index, sign;
+       int8_t *vector;
+       int non_zero;
+
+       bitspender = mgf1_bitspender_create(alg, seed, FALSE);
+       if (!bitspender)
+       {
+           return NULL;
+       }
+
+       vector = malloc(sizeof(int8_t) * this->set->n);
+       memset(vector, 0x00, this->set->n);
+
+       non_zero = this->set->non_zero1;
+       while (non_zero)
+       {
+               index = bitspender->get_bits(bitspender, this->set->n_bits);
+               if (index == MGF1_BITSPENDER_ERROR)
+               {
+                       free(vector);
+                       return NULL;
+               }
+               if (vector[index] != 0)
+               {
+                       continue;
+               }
+
+               sign = bitspender->get_bits(bitspender, 1);
+               if (sign == MGF1_BITSPENDER_ERROR)
+               {
+                       free(vector);
+                       return NULL;
+               }
+               vector[index] = sign ? 1 : -1;
+               non_zero--;
+       }
+
+       non_zero = this->set->non_zero2;
+       while (non_zero)
+       {
+               index = bitspender->get_bits(bitspender, this->set->n_bits);
+               if (index == MGF1_BITSPENDER_ERROR)
+               {
+                       free(vector);
+                       return NULL;
+               }
+               if (vector[index] != 0)
+               {
+                       continue;
+               }
+
+               sign = bitspender->get_bits(bitspender, 1);
+               if (sign == MGF1_BITSPENDER_ERROR)
+               {
+                       free(vector);
+                       return NULL;
+               }
+               vector[index] = bitspender->get_bits(bitspender, 1) ? 2 : -2;
+               non_zero--;
+       }
+       bitspender->destroy(bitspender);
+
+       return vector;
+}
+
+/**
+ * Generate the secret key S = (s1, s2) fulfilling the Nk(S) norm
+ */
+static bool create_secret(private_bliss_private_key_t *this, rng_t *rng,
+                                                int8_t **s1, int8_t **s2, int *trials)
+{
+       uint8_t seed_buf[32];
+       uint8_t *f, *g;
+       uint32_t l2_norm, nks;
+       int i, n;
+       chunk_t seed;
+       size_t seed_len;
+       hash_algorithm_t alg;
+
+       n = this->set->n;
+       *s1 = NULL;
+       *s2 = NULL;
+
+       /* Set MGF1 hash algorithm and seed length based on security strength */
+       if (this->set->strength > 160)
+       {
+               alg = HASH_SHA256;
+               seed_len = HASH_SIZE_SHA256;
+       }
+       else
+       {
+               alg = HASH_SHA1;
+               seed_len = HASH_SIZE_SHA1;
+       }
+       seed = chunk_create(seed_buf, seed_len);
+
+       while (*trials < SECRET_KEY_TRIALS_MAX)
+       {
+               (*trials)++;
+
+               if (!rng->get_bytes(rng, seed_len, seed_buf))
+               {
+                       return FALSE;
+               }
+               f = create_vector_from_seed(this, alg, seed);
+               if (f == NULL)
+               {
+                       return FALSE;
+               }
+               if (!rng->get_bytes(rng, seed_len, seed_buf))
+               {
+                       free(f);
+                       return FALSE;
+               }
+               g = create_vector_from_seed(this, alg, seed);
+               if (g == NULL)
+               {
+                       free(f);
+                       return FALSE;
+               }
+
+               /* Compute 2g + 1 */
+               for (i = 0; i < n; i++)
+               {
+                       g[i] *= 2;
+               }
+               g[0] += 1;
+
+               l2_norm = wrapped_product(f, f, n, 0) +  wrapped_product(g, g, n, 0);
+               nks = nks_norm(f, g, n, this->set->kappa);
+               DBG2(DBG_LIB, "l2 norm of s1||s2: %d, Nk(S): %u (%u max)",
+                                          l2_norm, nks, this->set->nks_max);
+               if (nks < this->set->nks_max)
+               {
+                       *s1 = f;
+                       *s2 = g;
+                       return TRUE;
+               }
+               free(f);
+               free(g);
+       }
+
+       return FALSE;
+}
+
+/**
  * See header.
  */
 bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args)
 {
        private_bliss_private_key_t *this;
        u_int key_size = 1;
-       int i;
-       uint32_t *a, *A, *F, *G, nks;
-       uint16_t q, n, l2_norm;
+       int i, n, trials = 0;
+       int8_t *s1 = NULL, *s2 = NULL;
+       uint16_t q;
+       uint32_t *a, *A, *S1, *S2;
+       bool success = FALSE;
        bliss_param_set_t *set;
        bliss_fft_t *fft;
-
-       int16_t f_bliss1[] = {
-                0,  0,  0,  0,  1,  1,  0, -1,  0,  1, 
-                0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 
-                0,  0, -1,  0,  0,  0, -1,  1,  0,  0, 
-                1,  1, -1,  0,  1,  1,  0,  0,  0,  0, 
-                0,  0,  0,  0,  1,  0, -1,  0, -1,  0, 
-                0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 
-               -1,  0,  1,  0,  1,  0,  0,  0,  0,  0, 
-                0,  0,  1,  0,  0,  1,  0, -1,  0,  0, 
-                0, -1,  0,  0,  1, -1,  0,  0,  0,  0, 
-                0,  0,  0,  0,  1,  0,  0,  0,  0,  0, 
-
-                0,  0,  0,  0,  0,  1,  0, -1,  0,  1, 
-                1, -1,  0,  1,  0,  1,  0,  0,  1,  0, 
-               -1,  0,  0,  0,  1, -1,  1,  0,  1,  0, 
-                0,  0,  0, -1, -1,  0,  0,  0, -1,  0, 
-               -1,  0,  0,  0,  1,  0,  1,  0,  0,  1, 
-                0, -1,  0,  0,  0, -1,  0, -1,  0,  0, 
-               -1,  0,  0, -1,  1,  1, -1,  0,  0, -1, 
-                0,  0,  1, -1,  0, -1,  0,  0,  1,  0, 
-                0,  1,  1,  0,  0,  0, -1,  0,  0, -1, 
-                0,  0,  0, -1,  1,  0,  0, -1,  0,  1, 
-
-                0,  0,  1, -1, -1,  0,  0,  0,  0,  1, 
-                0,  0,  0,  0,  0,  0,  0,  0, -1,  0, 
-                0,  0,  0,  0,  0,  0,  0,  0,  0,  1, 
-                1,  0, -1,  0,  0,  0,  0,  0,  1,  0, 
-                0,  1,  0,  1,  0,  0,  0,  0,  0,  1, 
-                0,  0,  0,  0,  0,  1,  0,  0, -1,  0, 
-                1, -1,  0,  0,  0,  0,  1,  0, -1,  0, 
-               -1,  0, -1,  1,  0,  0,  1,  1,  0,  0, 
-                0,  0,  0,  0,  0,  1,  0,  0, -1,  0, 
-                0,  1, -1,  0,  1,  0,  0,  0,  1, -1, 
-
-               -1,  0,  0,  0, -1,  0,  1,  0,  0,  0, 
-                0,  0,  1, -1,  1,  0,  0,  0,  0,  0, 
-                0, -1,  0,  1,  0,  0,  0,  0,  0, -1, 
-                0,  0,  0,  0,  0,  0,  0,  1,  0,  1, 
-                0,  0,  0,  0, -1,  1,  0,  0,  0,  0, 
-                0,  0,  0,  0, -1,  0,  0,  0,  0,  1, 
-                0, -1,  0,  0,  0,  1,  0,  1, -1,  1, 
-                0,  0,  0,  0,  1,  1,  0,  1,  0,  0, 
-                0, -1,  1,  0,  1, -1,  0,  0, -1,  0, 
-                0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 
-
-                0,  0,  1,  0,  0,  0,  0,  0, -1,  0, 
-                0, -1,  0,  0,  0,  1,  0,  0,  0,  1, 
-                0,  0,  0,  0,  0,  0,  0, -1,  0,  0, 
-                0,  0, -1,  1,  0,  1,  0,  0, -1,  0, 
-                0, -1,  0,  0,  0,  0,  0,  0,  0,  0, 
-                0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 
-               -1,  0,  0,  1,  0, -1,  1,  0,  1,  0, 
-               -1,  1,  0,  0,  0,  0,  0,  0,  0, -1, 
-                0,  0,  0,  0,  0,  1,  1,  0, -1,  0, 
-               -1,  0,  0,  0, -1, -1,  0,  0,  0,  0, 
-
-                0,  0, -1, -1,  0,  1, -1,  0,  0,  0, 
-                0, -1
-       };
-
-int16_t g_bliss1[] = {
-               -1,  0,  0,  0,  0,  0,  0,  0,  1,  0, 
-                0,  0,  0,  0,  0,  0,  0,  1,  1,  0, 
-                1,  0,  0,  0,  1,  0, -1,  0,  0,  0, 
-                0,  0,  0,  0, -1,  1,  0,  0,  0,  0, 
-                0,  0, -1,  1,  0,  0,  0,  0,  0, -1, 
-               -1,  0, -1,  0,  1, -1,  0,  0,  0,  0, 
-                0,  0,  0,  0,  1, -1,  0,  0,  1,  0, 
-                0,  1,  0, -1,  1,  0,  0,  0,  0,  0, 
-                0,  0,  0,  0, -1,  1,  0, -1,  0,  1, 
-                0,  1,  0,  0,  1,  0, -1,  1,  0,  0, 
-
-                0,  0,  0,  0,  0,  0,  1,  1,  0,  0, 
-                0,  0,  0,  0,  0,  0,  0,  0,  1,  0, 
-                0,  0,  0,  0,  0,  0,  1,  0,  0,  1, 
-                1,  1,  1,  0,  0,  0,  0,  0, -1,  0, 
-                1,  1,  0,  0,  1,  0, -1,  1,  0,  0, 
-               -1,  0,  0, -1,  0,  0,  0,  0,  0,  0, 
-                0,  0,  0, -1,  0, -1,  1,  0,  0, -1, 
-                0,  0, -1,  0,  0,  0,  0,  0,  0, -1, 
-                0,  0,  1,  0,  0,  0,  0, -1,  0,  1, 
-                0,  0, -1,  0,  0,  0,  0,  0,  0,  0, 
-
-                0,  0,  0,  0,  0,  0,  0,  1,  0,  1, 
-                1,  0, -1,  0,  0,  0,  0,  1,  1,  0, 
-                0, -1,  1,  1,  0,  0,  0, -1,  1,  0, 
-                0,  1,  0,  0,  0,  0, -1,  1,  0,  0, 
-               -1,  0,  1,  0,  0,  0, -1, -1,  0,  0, 
-                0, -1,  1,  1,  0,  1,  0,  0,  0,  0, 
-                0,  0,  1,  0,  0,  1,  1,  1,  1,  0, 
-                0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 
-                0,  0,  0,  0,  1,  0,  0,  0,  0,  1, 
-                0, -1, -1,  0, -1,  0, -1, -1,  1, -1, 
-
-               -1,  0,  0,  0, -1,  0,  0,  0,  0,  0, 
-               -1,  1,  0, -1,  0,  0,  0,  0,  0,  0, 
-                1,  0,  0,  0,  0,  0, -1,  0,  0, -1, 
-                1,  0,  0, -1,  0,  0,  0,  0,  0, -1, 
-                0,  0, -1,  0,  0,  0, -1,  0,  0,  0, 
-                0,  0,  0,  1,  1,  0,  0,  0,  0,  0, 
-               -1,  0,  0,  0,  0,  0, -1,  0,  0,  0, 
-                1,  1,  1,  0,  0,  0,  0, -1, -1,  0, 
-               -1,  0,  1,  0,  0,  0,  0,  0, -1,  0, 
-               -1,  0,  0,  0,  0,  1,  0,  0, -1, -1, 
-
-                1,  0,  0,  0,  0,  0,  0,  0, -1,  0, 
-                0,  0,  1, -1,  0,  0,  1,  0,  0,  1, 
-               -1,  0,  1,  0,  1,  1,  0,  0,  0,  0, 
-                0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 
-                0, -1,  0,  0,  0,  0,  1,  1,  0,  0, 
-                1,  0, -1,  0,  0,  1,  1,  0,  0,  0, 
-                0,  0, -1,  0,  0,  0,  0,  0,  1,  0, 
-                0,  0,  1, -1, -1,  0,  0,  0,  0,  1, 
-               -1, -1,  1,  0,  0,  0,  0,  0,  0,  1, 
-                0,  0,  0,  1,  0,  0,  0,  1,  1,  0, 
-
-               -1,  0,  1,  0,  0,  0,  0,  0,  0,  0, 
-                0, -1 
-};
-
-       int16_t f[] = {
-                0, -1, -1,  0,  0,  1, -1, -1,  0,  0, 
-                0,  0,  1,  1,  0,  0,  0,  1, -1,  1, 
-               -2,  1,  0,  0, -1,  0,  0,  0, -1,  0, 
-                0, -1,  0,  1,  1, -1,  0,  1, -2, -1, 
-                1,  0,  0,  0,  0, -1, -1,  0,  1,  2, 
-                0,  0,  1,  0, -1,  0,  1,  1,  1,  0, 
-                2, -1,  0,  0,  1,  0,  0, -1,  0,  0, 
-                0,  0,  1,  0,  0, -1,  0, -1, -1,  0, 
-                0,  0,  0, -1, -2, -1, -1, -1,  1,  0, 
-                0,  1,  0,  1, -1, -1,  0,  0,  0,  1, 
-
-                0, -1,  1,  1,  1,  0, -1,  0,  0, -1, 
-                0,  1, -1,  1, -2,  0,  1,  1, -1,  0, 
-                1, -1, -2,  0,  0, -1,  0,  0,  1,  0, 
-                0,  0,  1, -1,  1, -2,  0,  0, -1,  1, 
-                0,  0, -1, -1,  0, -1,  0,  0,  0,  0, 
-               -1,  0,  1, -1,  1,  0, -1,  1,  0,  1, 
-                1,  0,  0, -1,  0,  1,  1,  0, -1,  1, 
-                1,  1,  2,  0,  0,  1,  0,  1,  0,  0, 
-               -1, -1,  0, -2,  0, -1,  0,  0, -1,  1, 
-               -1, -2,  0,  2,  0, -1,  2,  1,  0,  1, 
-
-                1,  1,  1,  0, -1,  1, -1,  1,  1, -1, 
-                0,  1,  1,  1,  0,  0,  0,  0,  1,  0, 
-               -2,  0,  1,  1,  0, -1, -1,  1,  0,  1, 
-               -2,  1,  1, -1,  1,  0,  0,  1, -1, -1, 
-                1,  0,  1,  1,  1, -1,  0, -1,  0,  0, 
-                0,  0,  1,  0,  0, -1,  0,  0,  0,  0, 
-                1, -1,  2, -1,  1,  0,  0,  1,  0,  0, 
-                0, -1, -1,  2,  1,  1,  0, -1,  0, -1, 
-                0,  0,  0,  0,  0,  0,  0, -1, -1,  0, 
-                0,  0,  0, -1,  0,  1,  1,  1, -1,  0, 
-
-               -1,  1,  0,  1,  0,  0,  0,  1,  0, -1, 
-                0,  0,  1, -2,  0,  0,  0,  0, -1,  1, 
-                0,  1,  0,  0,  0, -1,  0,  1,  0, -1, 
-                0,  1, -1,  0,  0,  1,  0,  0,  0,  0, 
-                1, -1,  0, -2,  0,  0,  2,  0, -1, -1, 
-               -1,  1,  1,  0,  1, -1,  1,  2, -1,  1, 
-               -1,  0,  1, -2,  0,  0, -1,  2, -1,  0, 
-               -1,  0, -1,  0,  1, -2,  0,  2,  0,  0, 
-                1, -1,  1, -1,  1,  0,  1,  1, -1,  0, 
-                0,  0, -1, -1,  0,  0,  0, -1, -2,  0, 
-
-                0,  0,  1, -2,  0,  0,  1,  1,  0, -1, 
-                0,  0,  0,  0,  0,  1,  0,  0,  0,  0, 
-                0,  0, -1,  0,  0,  0,  1,  0,  0,  0, 
-                1,  2,  0, -1,  0,  0,  1,  0,  0,  0, 
-               -1,  0,  0,  1, -1,  0, -1,  0,  0, -1, 
-               -1, -1,  2,  0,  0,  0, -1,  0,  2,  0, 
-               -1,  0, -1,  0, -1,  1,  0,  0,  0,  0, 
-               -1,  2,  0,  1,  0,  0, -1,  0,  0,  0, 
-                1, -1, -1,  0,  0, -1,  0, -1,  1, -1, 
-                1,  0, -1, -1,  1,  1,  0,  0,  0,  0, 
-
-                0,  0,  0,  1, -1,  0,  0,  0,  0,  0, 
-                0,  0 
-       };
-int16_t g[] = {
-                0,  2,  1,  0, -1,  1,  1,  1, -1, -1, 
-                1,  2,  0,  0,  0, -1,  0, -1,  1,  0, 
-                1, -1,  1,  0,  0,  0, -1, -1,  1,  0, 
-               -1,  1,  0,  0,  0,  0,  0,  0,  0,  0, 
-                0,  1, -1, -1, -1, -1,  0,  0,  0,  0, 
-                0, -1,  0, -1, -2,  0,  0,  1,  0, -1, 
-               -1, -1, -1, -1,  2,  1, -1,  0, -1,  0, 
-                0,  1,  1,  0,  1,  0,  0,  0, -1,  1, 
-                0,  1,  0,  0,  0,  1,  0,  0,  0,  0, 
-                0, -1,  0,  0,  0, -1,  0,  0,  0,  0, 
-
-                0,  1, -2,  1,  1, -1,  1,  1,  0,  1, 
-                0,  0,  1,  0,  0,  0, -1,  0,  0,  0, 
-                0,  0,  1,  0,  1, -1,  0,  0,  0,  1, 
-                1,  1,  0,  0,  1,  0,  0,  1,  1,  1, 
-                0,  0,  0, -1,  0, -1, -2,  1,  0,  1, 
-                0, -1, -2,  1,  0,  0, -1,  0,  0,  0, 
-                0,  0,  1,  0,  1, -1,  1,  1, -1,  0, 
-                0,  0,  1, -1,  1,  1, -2, -1,  1,  0, 
-               -2,  0,  0,  0,  1,  1,  2,  0,  2,  1, 
-                1,  0,  1,  0, -1,  1,  0,  0,  0, -1, 
-
-               -1, -1,  0,  0, -1,  1,  0,  1,  0, -1, 
-                0,  0,  2,  1,  0,  0,  1, -2, -1,  0, 
-                1,  0, -1,  1, -1,  0,  1, -1, -1,  1, 
-                0,  0, -1, -1, -1,  0,  0,  1, -2, -1, 
-                0, -1,  1, -1,  1, -1,  0, -1, -1,  1, 
-                0,  1, -1,  0,  2,  1, -1,  0, -2,  0, 
-               -1,  0,  0,  1,  0, -1,  1,  1,  0,  0, 
-                0, -1, -2,  1,  0,  0,  2,  0, -1,  0, 
-                1,  1,  0, -1,  0,  0, -1, -1, -1,  0, 
-                0, -1,  0,  0,  0,  0,  1,  0, -1, -1, 
-
-                1, -1,  0,  0,  1,  0, -1,  1,  0,  1, 
-                0,  1,  1,  1, -1,  0,  0,  1,  0, -1, 
-                0, -1,  0,  0,  0, -1, -1,  0,  0,  0, 
-               -1, -1,  0,  1,  0,  0,  0,  1,  0,  0, 
-                1,  1, -1,  0,  0,  0, -1,  0,  1,  1, 
-                0,  1,  0,  1,  0, -1, -1,  0,  0,  0, 
-                2, -1,  0,  0, -1,  1, -1, -2, -1,  0, 
-                0,  1,  0,  1,  1,  0,  0,  0, -1,  2, 
-                0, -1,  0,  0,  0, -1, -1, -1,  0,  1, 
-               -2,  0,  0,  1, -1,  0,  0,  0,  1,  1, 
-
-                1,  1,  0, -1,  0,  0,  0,  0,  0,  0, 
-                0,  0,  0,  0,  0,  0, -2,  0,  0,  0, 
-                2,  1,  0,  0,  0,  0,  1,  0,  0, -1, 
-                1, -2,  0,  0,  1,  1,  1,  0, -2,  0, 
-               -1,  0,  1,  2,  1,  0,  0, -2,  0, -1, 
-               -1,  0,  1,  0,  1,  0,  1,  0, -1, -1, 
-                2,  0,  1, -1,  0,  1,  0,  0,  0, -1, 
-                1,  0,  1, -1,  0,  0,  0,  0,  0, -1, 
-                0,  0,  1, -1,  0,  0,  1,  1,  0,  0, 
-                0,  1, -1,  0, -1, -2, -1,  0,  0, -2, 
-
-                0, -1,  0,  0,  0, -1,  1,  0,  1,  1, 
-               -1,  0
-       };
+       rng_t *rng;
 
        while (TRUE)
        {
@@ -538,7 +461,7 @@ int16_t g[] = {
                break;
        }
 
-       /* Only BLISS-I and BLISS-IV are supported */
+       /* Only BLISS-I and BLISS-IV are currently supported */
        set = bliss_param_set_get_by_id(key_size);
        if (!set)
        {
@@ -561,58 +484,81 @@ int16_t g[] = {
        /* We derive the public key from the private key using the FFT */
        fft = bliss_fft_create(set->fft_params);
 
-       /* Compute 2g + 1 */
-       for (i = 0; i < n; i++)
-       {
-               g[i] *= 2;
-       }
-       g[0] += 1;
-
-       l2_norm = wrapped_product(f, f, n, 0) + wrapped_product(g, g, n, 0);
-       nks = nks_norm(f, g, n, set->kappa);
-       DBG2(DBG_LIB, "L2 norm of s1||s2: %d, Nk(S): %u (%u max)",
-                l2_norm, nks, set->nks_max);
+       /* Some vectors needed to derive the publi key */
+       S1 = malloc(n * sizeof(uint32_t));
+       S2 = malloc(n * sizeof(uint32_t));
+       A =  malloc(n * sizeof(uint32_t));
+       a =  malloc(n * sizeof(uint32_t));
 
-       F = malloc(n * sizeof(uint32_t));
-       G = malloc(n * sizeof(uint32_t));
-       A = malloc(n * sizeof(uint32_t));
-       a = malloc(n * sizeof(uint32_t));
+       /* Instantiate a true random generator */
+       rng = lib->crypto->create_rng(lib->crypto, RNG_TRUE);
 
-       /* Convert signed arrays to unsigned arrays before FFT */
-       for (i = 0; i < n; i++)
+       /* Loop until we have an invertible polynomial s1 */
+       do
        {
-               F[i] = (f[i] < 0) ? f[i] + q : f[i];
-               G[i] = (g[i] < 0) ? g[i] + q : g[i];
+               if (!create_secret(this, rng, &s1, &s2, &trials))
+               {
+                       break;
+               }
+
+               /* Convert signed arrays to unsigned arrays before FFT */
+               for (i = 0; i < n; i++)
+               {
+                       S1[i] = (s1[i] < 0) ? s1[i] + q : s1[i];
+                       S1[i] = (s2[i] < 0) ? s2[i] + q : s2[i];
+               }
+               fft->transform(fft, S1, S1, FALSE);
+               fft->transform(fft, S2, S2, FALSE);
+
+               success = TRUE;
+               for (i = 0; i < n; i++)
+               {
+                       if (S1[i] == 0)
+                       {
+                               DBG1(DBG_LIB, "S1[%d] is zero - s1 is not invertible", i);
+                               free(s1);
+                               s1 = NULL;
+                               free(s2);
+                               s2 = NULL;
+                               success = FALSE;
+                               break;
+                       }
+                       A[i] = invert(S1[i], q);
+                       A[i] = (S2[i] * A[i]) % q;
+               }
        }
-       fft->transform(fft, F, F, FALSE);
-       fft->transform(fft, G, G, FALSE);
+       while (!success && trials < SECRET_KEY_TRIALS_MAX);
 
-       for (i = 0; i < n; i++)
+       DBG1(DBG_LIB, "secret key generation %s after %d trial%s",
+                success ? "succeeded" : "failed", trials, (trials == 1) ? "" : "s");
+
+       if (success)
        {
-               if (F[i] == 0)
+               fft->transform(fft, A, a, TRUE);
+
+               DBG4(DBG_LIB, "   i   f   g     a     F     G     A");
+               for (i = 0; i < n; i++)
                {
-                       DBG1(DBG_LIB, "F[%d] is zero", i);
+                       DBG4(DBG_LIB, "%4d %3d %3d %5u %5u %5u %5u",
+                                i, s1[i], s2[i], a[i], S1[i], S2[i], A[i]);
                }
-               A[i] = invert(F[i], q);
-               A[i] = (G[i] * A[i]) % q;
        }
-       fft->transform(fft, A, a, TRUE);
-
-       DBG4(DBG_LIB, "   i   f   g     a     F     G     A");
-       for (i = 0; i < n; i++)
+       else
        {
-               DBG4(DBG_LIB, "%4d %3d %3d %5u %5u %5u %5u",
-                        i, f[i], g[i], a[i], F[i], G[i], A[i]);
+               destroy(this);
        }
 
        /* Cleanup */
        fft->destroy(fft);
+       rng->destroy(rng);
+       free(s1);
+       free(s2);
        free(a);
        free(A);
-       free(F);
-       free(G);
+       free(S1);
+       free(S2);
 
-       return &this->public;
+       return success ? &this->public : NULL;
 }
 
 /**