Added get_array() method to ntru_poly_t class
[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 /**
92 * Multiplication of polynomial a with a sparse polynomial b given by
93 * the indices of its +1 and -1 coefficients results in polynomial c.
94 * This is a convolution operation
95 */
96 static void ring_mult_i(uint16_t *a, indices_len_t len, uint16_t *indices,
97 uint16_t N, uint16_t mod_q_mask, uint16_t *t,
98 uint16_t *c)
99 {
100 int i, j, k;
101
102 /* initialize temporary array t */
103 for (k = 0; k < N; k++)
104 {
105 t[k] = 0;
106 }
107
108 /* t[(i+k)%N] = sum i=0 through N-1 of a[i], for b[k] = -1 */
109 for (j = len.p; j < len.p + len.m; j++)
110 {
111 k = indices[j];
112 for (i = 0; k < N; ++i, ++k)
113 {
114 t[k] += a[i];
115 }
116 for (k = 0; i < N; ++i, ++k)
117 {
118 t[k] += a[i];
119 }
120 }
121
122 /* t[(i+k)%N] = -(sum i=0 through N-1 of a[i] for b[k] = -1) */
123 for (k = 0; k < N; k++)
124 {
125 t[k] = -t[k];
126 }
127
128 /* t[(i+k)%N] += sum i=0 through N-1 of a[i] for b[k] = +1 */
129 for (j = 0; j < len.p; j++)
130 {
131 k = indices[j];
132 for (i = 0; k < N; ++i, ++k)
133 {
134 t[k] += a[i];
135 }
136 for (k = 0; i < N; ++i, ++k)
137 {
138 t[k] += a[i];
139 }
140 }
141
142 /* c = (a * b) mod q */
143 for (k = 0; k < N; k++)
144 {
145 c[k] = t[k] & mod_q_mask;
146 }
147 }
148
149 METHOD(ntru_poly_t, get_array, void,
150 private_ntru_poly_t *this, uint16_t *array)
151 {
152 uint16_t *t, *bi;
153 uint16_t mod_q_mask = this->q - 1;
154 indices_len_t len;
155 int i;
156
157 /* form polynomial F or F1 */
158 memset(array, 0x00, this->N * sizeof(uint16_t));
159 bi = this->indices;
160 len = this->indices_len[0];
161 for (i = 0; i < len.p + len.m; i++)
162 {
163 array[bi[i]] = (i < len.p) ? 1 : mod_q_mask;
164 }
165
166 if (this->num_polynomials == 3)
167 {
168 /* allocate temporary array t */
169 t = malloc(this->N * sizeof(uint16_t));
170
171 /* form F1 * F2 */
172 bi += len.p + len.m;
173 len = this->indices_len[1];
174 ring_mult_i(array, len, bi, this->N, mod_q_mask, t, array);
175
176 /* form (F1 * F2) + F3 */
177 bi += len.p + len.m;
178 len = this->indices_len[2];
179 for (i = 0; i < len.p + len.m; i++)
180 {
181 if (i < len.p)
182 {
183 array[bi[i]] += 1;
184 }
185 else
186 {
187 array[bi[i]] -= 1;
188 }
189 array[bi[i]] &= mod_q_mask;
190 }
191 free(t);
192 }
193 }
194
195 METHOD(ntru_poly_t, ring_mult, void,
196 private_ntru_poly_t *this, uint16_t *a, uint16_t *c)
197 {
198 uint16_t *t1, *t2;
199 uint16_t *bi = this->indices;
200 uint16_t mod_q_mask = this->q - 1;
201 int i;
202
203 /* allocate temporary array t1 */
204 t1 = malloc(this->N * sizeof(uint16_t));
205
206 if (this->num_polynomials == 1)
207 {
208 ring_mult_i(a, this->indices_len[0], bi, this->N, mod_q_mask, t1, c);
209 }
210 else
211 {
212 /* allocate temporary array t2 */
213 t2 = malloc(this->N * sizeof(uint16_t));
214
215 /* t1 = a * b1 */
216 ring_mult_i(a, this->indices_len[0], bi, this->N, mod_q_mask, t1, t1);
217
218 /* t1 = (a * b1) * b2 */
219 bi += this->indices_len[0].p + this->indices_len[0].m;
220 ring_mult_i(t1, this->indices_len[1], bi, this->N, mod_q_mask, t2, t1);
221
222 /* t2 = a * b3 */
223 bi += this->indices_len[1].p + this->indices_len[1].m;
224 ring_mult_i(a, this->indices_len[2], bi, this->N, mod_q_mask, t2, t2);
225
226 /* c = (a * b1 * b2) + (a * b3) */
227 for (i = 0; i < this->N; i++)
228 {
229 c[i] = (t1[i] + t2[i]) & mod_q_mask;
230 }
231 free(t2);
232 }
233 free(t1);
234 }
235
236 METHOD(ntru_poly_t, destroy, void,
237 private_ntru_poly_t *this)
238 {
239 memwipe(this->indices, sizeof(uint16_t) * get_size(this));
240 free(this->indices);
241 free(this);
242 }
243
244 /*
245 * Described in header.
246 */
247 ntru_poly_t *ntru_poly_create_from_seed(hash_algorithm_t alg, chunk_t seed,
248 uint8_t c_bits, uint16_t N, uint16_t q,
249 uint32_t indices_len_p,
250 uint32_t indices_len_m,
251 bool is_product_form)
252 {
253 private_ntru_poly_t *this;
254 size_t hash_len, octet_count = 0, i;
255 uint8_t octets[HASH_SIZE_SHA512], *used, num_left = 0, num_needed;
256 uint16_t index, limit, left = 0;
257 int n, num_indices, index_i = 0;
258 ntru_mgf1_t *mgf1;
259
260 DBG2(DBG_LIB, "MGF1 is seeded with %u bytes", seed.len);
261 mgf1 = ntru_mgf1_create(alg, seed, TRUE);
262 if (!mgf1)
263 {
264 return NULL;
265 }
266 i = hash_len = mgf1->get_hash_size(mgf1);
267
268 INIT(this,
269 .public = {
270 .get_size = _get_size,
271 .get_indices = _get_indices,
272 .get_array = _get_array,
273 .ring_mult = _ring_mult,
274 .destroy = _destroy,
275 },
276 .N = N,
277 .q = q,
278 );
279
280 if (is_product_form)
281 {
282 this->num_polynomials = 3;
283 for (n = 0; n < 3; n++)
284 {
285 this->indices_len[n].p = 0xff & indices_len_p;
286 this->indices_len[n].m = 0xff & indices_len_m;
287 indices_len_p >>= 8;
288 indices_len_m >>= 8;
289 }
290 }
291 else
292 {
293 this->num_polynomials = 1;
294 this->indices_len[0].p = indices_len_p;
295 this->indices_len[0].m = indices_len_m;
296 }
297 this->indices = malloc(sizeof(uint16_t) * get_size(this)),
298
299 used = malloc(N);
300 limit = N * ((1 << c_bits) / N);
301
302 /* generate indices for all polynomials */
303 for (n = 0; n < this->num_polynomials; n++)
304 {
305 memset(used, 0, N);
306 num_indices = this->indices_len[n].p + this->indices_len[n].m;
307
308 /* generate indices for a single polynomial */
309 while (num_indices)
310 {
311 /* generate a random candidate index with a size of c_bits */
312 do
313 {
314 /* use any leftover bits first */
315 index = num_left ? left << (c_bits - num_left) : 0;
316
317 /* get the rest of the bits needed from new octets */
318 num_needed = c_bits - num_left;
319
320 while (num_needed)
321 {
322 if (i == hash_len)
323 {
324 /* get another block from MGF1 */
325 if (!mgf1->get_mask(mgf1, hash_len, octets))
326 {
327 mgf1->destroy(mgf1);
328 destroy(this);
329 free(used);
330 return NULL;
331 }
332 octet_count += hash_len;
333 i = 0;
334 }
335 left = octets[i++];
336
337 if (num_needed <= 8)
338 {
339 /* all bits needed to fill the index are in this octet */
340 index |= left >> (8 - num_needed);
341 num_left = 8 - num_needed;
342 num_needed = 0;
343 left &= 0xff >> (8 - num_left);
344 }
345 else
346 {
347 /* more than one octet will be needed */
348 index |= left << (num_needed - 8);
349 num_needed -= 8;
350 }
351 }
352 }
353 while (index >= limit);
354
355 /* form index and check if unique */
356 index %= N;
357 if (!used[index])
358 {
359 used[index] = 1;
360 this->indices[index_i++] = index;
361 num_indices--;
362 }
363 }
364 }
365
366 DBG2(DBG_LIB, "MGF1 generates %u octets to derive %u indices",
367 octet_count, get_size(this));
368 mgf1->destroy(mgf1);
369 free(used);
370
371 return &this->public;
372 }
373
374 /*
375 * Described in header.
376 */
377 ntru_poly_t *ntru_poly_create_from_data(uint16_t *data, uint16_t N, uint16_t q,
378 uint32_t indices_len_p,
379 uint32_t indices_len_m,
380 bool is_product_form)
381 {
382 private_ntru_poly_t *this;
383 int n, i, num_indices;
384
385 INIT(this,
386 .public = {
387 .get_size = _get_size,
388 .get_indices = _get_indices,
389 .get_array = _get_array,
390 .ring_mult = _ring_mult,
391 .destroy = _destroy,
392 },
393 .N = N,
394 .q = q,
395 );
396
397 if (is_product_form)
398 {
399 this->num_polynomials = 3;
400 for (n = 0; n < 3; n++)
401 {
402 this->indices_len[n].p = 0xff & indices_len_p;
403 this->indices_len[n].m = 0xff & indices_len_m;
404 indices_len_p >>= 8;
405 indices_len_m >>= 8;
406 }
407 }
408 else
409 {
410 this->num_polynomials = 1;
411 this->indices_len[0].p = indices_len_p;
412 this->indices_len[0].m = indices_len_m;
413 }
414 num_indices = get_size(this);
415
416 this->indices = malloc(sizeof(uint16_t) * num_indices);
417 for (i = 0; i < num_indices; i++)
418 {
419 this->indices[i] = data[i];
420 }
421
422 return &this->public;
423 }
424
425 EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_seed);
426
427 EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_data);