Defined ntru_poly_create_from_seed() and ntru_poly_create_from_data() constructors...
[strongswan.git] / src / libstrongswan / plugins / ntru / ntru_poly.c
1 /*
2 * Copyright (C) 2014 Andreas Steffen
3 * HSR Hochschule fuer Technik Rapperswil
4 *
5 * Copyright (C) 2009-2013 Security Innovation
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2 of the License, or (at your
10 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * for more details.
16 */
17
18 #include "ntru_poly.h"
19 #include "ntru_mgf1.h"
20
21 #include <utils/debug.h>
22 #include <utils/test.h>
23
24 typedef struct private_ntru_poly_t private_ntru_poly_t;
25 typedef struct indices_len_t indices_len_t;
26
27 /**
28 * Stores number of +1 and -1 coefficients
29 */
30 struct indices_len_t {
31 int p;
32 int m;
33 };
34
35 /**
36 * Private data of an ntru_poly_t object.
37 */
38 struct private_ntru_poly_t {
39
40 /**
41 * Public ntru_poly_t interface.
42 */
43 ntru_poly_t public;
44
45 /**
46 * Ring dimension equal to the number of polynomial coefficients
47 */
48 uint16_t N;
49
50 /**
51 * Large modulus
52 */
53 uint16_t q;
54
55 /**
56 * Array containing the indices of the non-zero coefficients
57 */
58 uint16_t *indices;
59
60 /**
61 * Number of sparse polynomials
62 */
63 int num_polynomials;
64
65 /**
66 * Number of nonzero coefficients for up to 3 sparse polynomials
67 */
68 indices_len_t indices_len[3];
69
70 };
71
72 METHOD(ntru_poly_t, get_size, size_t,
73 private_ntru_poly_t *this)
74 {
75 int n;
76 size_t size = 0;
77
78 for (n = 0; n < this->num_polynomials; n++)
79 {
80 size += this->indices_len[n].p + this->indices_len[n].m;
81 }
82 return size;
83 }
84
85 METHOD(ntru_poly_t, get_indices, uint16_t*,
86 private_ntru_poly_t *this)
87 {
88 return this->indices;
89 }
90 /**
91 * Multiplication of polynomial a with a sparse polynomial b given by
92 * the indices of its +1 and -1 coefficients results in polynomial c.
93 * This is a convolution operation
94 */
95 static void ring_mult_i(uint16_t *a, indices_len_t len, uint16_t *indices,
96 uint16_t N, uint16_t mod_q_mask, uint16_t *t,
97 uint16_t *c)
98 {
99 int i, j, k;
100
101 /* initialize temporary array t */
102 for (k = 0; k < N; k++)
103 {
104 t[k] = 0;
105 }
106
107 /* t[(i+k)%N] = sum i=0 through N-1 of a[i], for b[k] = -1 */
108 for (j = len.p; j < len.p + len.m; j++)
109 {
110 k = indices[j];
111 for (i = 0; k < N; ++i, ++k)
112 {
113 t[k] += a[i];
114 }
115 for (k = 0; i < N; ++i, ++k)
116 {
117 t[k] += a[i];
118 }
119 }
120
121 /* t[(i+k)%N] = -(sum i=0 through N-1 of a[i] for b[k] = -1) */
122 for (k = 0; k < N; k++)
123 {
124 t[k] = -t[k];
125 }
126
127 /* t[(i+k)%N] += sum i=0 through N-1 of a[i] for b[k] = +1 */
128 for (j = 0; j < len.p; j++)
129 {
130 k = indices[j];
131 for (i = 0; k < N; ++i, ++k)
132 {
133 t[k] += a[i];
134 }
135 for (k = 0; i < N; ++i, ++k)
136 {
137 t[k] += a[i];
138 }
139 }
140
141 /* c = (a * b) mod q */
142 for (k = 0; k < N; k++)
143 {
144 c[k] = t[k] & mod_q_mask;
145 }
146 }
147
148 METHOD(ntru_poly_t, ring_mult, void,
149 private_ntru_poly_t *this, uint16_t *a, uint16_t *c)
150 {
151 uint16_t *t1, *t2;
152 uint16_t *bi = this->indices;
153 uint16_t mod_q_mask = this->q - 1;
154 int i;
155
156 /* allocate temporary array t1 */
157 t1 = malloc(this->N * sizeof(uint16_t));
158
159 if (this->num_polynomials == 1)
160 {
161 ring_mult_i(a, this->indices_len[0], bi, this->N, mod_q_mask, t1, c);
162 }
163 else
164 {
165 /* allocate temporary array t2 */
166 t2 = malloc(this->N * sizeof(uint16_t));
167
168 /* t1 = a * b1 */
169 ring_mult_i(a, this->indices_len[0], bi, this->N, mod_q_mask, t1, t1);
170
171 /* t1 = (a * b1) * b2 */
172 bi += this->indices_len[0].p + this->indices_len[0].m;
173 ring_mult_i(t1, this->indices_len[1], bi, this->N, mod_q_mask, t2, t1);
174
175 /* t2 = a * b3 */
176 bi += this->indices_len[1].p + this->indices_len[1].m;
177 ring_mult_i(a, this->indices_len[2], bi, this->N, mod_q_mask, t2, t2);
178
179 /* c = (a * b1 * b2) + (a * b3) */
180 for (i = 0; i < this->N; i++)
181 {
182 c[i] = (t1[i] + t2[i]) & mod_q_mask;
183 }
184 free(t2);
185 }
186 free(t1);
187 }
188
189 METHOD(ntru_poly_t, destroy, void,
190 private_ntru_poly_t *this)
191 {
192 memwipe(this->indices, sizeof(uint16_t) * get_size(this));
193 free(this->indices);
194 free(this);
195 }
196
197 /*
198 * Described in header.
199 */
200 ntru_poly_t *ntru_poly_create_from_seed(hash_algorithm_t alg, chunk_t seed,
201 uint8_t c_bits, uint16_t N, uint16_t q,
202 uint32_t indices_len_p,
203 uint32_t indices_len_m,
204 bool is_product_form)
205 {
206 private_ntru_poly_t *this;
207 size_t hash_len, octet_count = 0, i;
208 uint8_t octets[HASH_SIZE_SHA512], *used, num_left = 0, num_needed;
209 uint16_t index, limit, left = 0;
210 int n, num_indices, index_i = 0;
211 ntru_mgf1_t *mgf1;
212
213 DBG2(DBG_LIB, "MGF1 is seeded with %u bytes", seed.len);
214 mgf1 = ntru_mgf1_create(alg, seed, TRUE);
215 if (!mgf1)
216 {
217 return NULL;
218 }
219 i = hash_len = mgf1->get_hash_size(mgf1);
220
221 INIT(this,
222 .public = {
223 .get_size = _get_size,
224 .get_indices = _get_indices,
225 .ring_mult = _ring_mult,
226 .destroy = _destroy,
227 },
228 .N = N,
229 .q = q,
230 );
231
232 if (is_product_form)
233 {
234 this->num_polynomials = 3;
235 for (n = 0; n < 3; n++)
236 {
237 this->indices_len[n].p = 0xff & indices_len_p;
238 this->indices_len[n].m = 0xff & indices_len_m;
239 indices_len_p >>= 8;
240 indices_len_m >>= 8;
241 }
242 }
243 else
244 {
245 this->num_polynomials = 1;
246 this->indices_len[0].p = indices_len_p;
247 this->indices_len[0].m = indices_len_m;
248 }
249 this->indices = malloc(sizeof(uint16_t) * get_size(this)),
250
251 used = malloc(N);
252 limit = N * ((1 << c_bits) / N);
253
254 /* generate indices for all polynomials */
255 for (n = 0; n < this->num_polynomials; n++)
256 {
257 memset(used, 0, N);
258 num_indices = this->indices_len[n].p + this->indices_len[n].m;
259
260 /* generate indices for a single polynomial */
261 while (num_indices)
262 {
263 /* generate a random candidate index with a size of c_bits */
264 do
265 {
266 /* use any leftover bits first */
267 index = num_left ? left << (c_bits - num_left) : 0;
268
269 /* get the rest of the bits needed from new octets */
270 num_needed = c_bits - num_left;
271
272 while (num_needed)
273 {
274 if (i == hash_len)
275 {
276 /* get another block from MGF1 */
277 if (!mgf1->get_mask(mgf1, hash_len, octets))
278 {
279 mgf1->destroy(mgf1);
280 destroy(this);
281 free(used);
282 return NULL;
283 }
284 octet_count += hash_len;
285 i = 0;
286 }
287 left = octets[i++];
288
289 if (num_needed <= 8)
290 {
291 /* all bits needed to fill the index are in this octet */
292 index |= left >> (8 - num_needed);
293 num_left = 8 - num_needed;
294 num_needed = 0;
295 left &= 0xff >> (8 - num_left);
296 }
297 else
298 {
299 /* more than one octet will be needed */
300 index |= left << (num_needed - 8);
301 num_needed -= 8;
302 }
303 }
304 }
305 while (index >= limit);
306
307 /* form index and check if unique */
308 index %= N;
309 if (!used[index])
310 {
311 used[index] = 1;
312 this->indices[index_i++] = index;
313 num_indices--;
314 }
315 }
316 }
317
318 DBG2(DBG_LIB, "MGF1 generates %u octets to derive %u indices",
319 octet_count, get_size(this));
320 mgf1->destroy(mgf1);
321 free(used);
322
323 return &this->public;
324 }
325
326 /*
327 * Described in header.
328 */
329 ntru_poly_t *ntru_poly_create_from_data(uint16_t *data, uint16_t N, uint16_t q,
330 uint32_t indices_len_p,
331 uint32_t indices_len_m,
332 bool is_product_form)
333 {
334 private_ntru_poly_t *this;
335 int n, i, num_indices;
336
337 INIT(this,
338 .public = {
339 .get_size = _get_size,
340 .get_indices = _get_indices,
341 .ring_mult = _ring_mult,
342 .destroy = _destroy,
343 },
344 .N = N,
345 .q = q,
346 );
347
348 if (is_product_form)
349 {
350 this->num_polynomials = 3;
351 for (n = 0; n < 3; n++)
352 {
353 this->indices_len[n].p = 0xff & indices_len_p;
354 this->indices_len[n].m = 0xff & indices_len_m;
355 indices_len_p >>= 8;
356 indices_len_m >>= 8;
357 }
358 }
359 else
360 {
361 this->num_polynomials = 1;
362 this->indices_len[0].p = indices_len_p;
363 this->indices_len[0].m = indices_len_m;
364 }
365 num_indices = get_size(this);
366
367 this->indices = malloc(sizeof(uint16_t) * num_indices);
368 for (i = 0; i < num_indices; i++)
369 {
370 this->indices[i] = data[i];
371 }
372
373 return &this->public;
374 }
375
376 EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_seed);
377
378 EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_data);