![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ntru_poly.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / ntru|
Return to ntru_poly.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / ntru |
1.1 misho 1: /*
2: * Copyright (C) 2014-2016 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:
20: #include <crypto/xofs/xof_bitspender.h>
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 indices of the non-zero coefficients
62: */
63: size_t num_indices;
64:
65: /**
66: * Number of sparse polynomials
67: */
68: int num_polynomials;
69:
70: /**
71: * Number of nonzero coefficients for up to 3 sparse polynomials
72: */
73: indices_len_t indices_len[3];
74:
75: };
76:
77: METHOD(ntru_poly_t, get_size, size_t,
78: private_ntru_poly_t *this)
79: {
80: return this->num_indices;
81: }
82:
83: METHOD(ntru_poly_t, get_indices, uint16_t*,
84: private_ntru_poly_t *this)
85: {
86: return this->indices;
87: }
88:
89: /**
90: * Multiplication of polynomial a with a sparse polynomial b given by
91: * the indices of its +1 and -1 coefficients results in polynomial c.
92: * This is a convolution operation
93: */
94: static void ring_mult_i(uint16_t *a, indices_len_t len, uint16_t *indices,
95: uint16_t N, uint16_t mod_q_mask, uint16_t *t,
96: uint16_t *c)
97: {
98: int i, j, k;
99:
100: /* initialize temporary array t */
101: for (k = 0; k < N; k++)
102: {
103: t[k] = 0;
104: }
105:
106: /* t[(i+k)%N] = sum i=0 through N-1 of a[i], for b[k] = -1 */
107: for (j = len.p; j < len.p + len.m; j++)
108: {
109: k = indices[j];
110: for (i = 0; k < N; ++i, ++k)
111: {
112: t[k] += a[i];
113: }
114: for (k = 0; i < N; ++i, ++k)
115: {
116: t[k] += a[i];
117: }
118: }
119:
120: /* t[(i+k)%N] = -(sum i=0 through N-1 of a[i] for b[k] = -1) */
121: for (k = 0; k < N; k++)
122: {
123: t[k] = -t[k];
124: }
125:
126: /* t[(i+k)%N] += sum i=0 through N-1 of a[i] for b[k] = +1 */
127: for (j = 0; j < len.p; j++)
128: {
129: k = indices[j];
130: for (i = 0; k < N; ++i, ++k)
131: {
132: t[k] += a[i];
133: }
134: for (k = 0; i < N; ++i, ++k)
135: {
136: t[k] += a[i];
137: }
138: }
139:
140: /* c = (a * b) mod q */
141: for (k = 0; k < N; k++)
142: {
143: c[k] = t[k] & mod_q_mask;
144: }
145: }
146:
147: METHOD(ntru_poly_t, get_array, void,
148: private_ntru_poly_t *this, uint16_t *array)
149: {
150: uint16_t *t, *bi;
151: uint16_t mod_q_mask = this->q - 1;
152: indices_len_t len;
153: int i;
154:
155: /* form polynomial F or F1 */
156: memset(array, 0x00, this->N * sizeof(uint16_t));
157: bi = this->indices;
158: len = this->indices_len[0];
159: for (i = 0; i < len.p + len.m; i++)
160: {
161: array[bi[i]] = (i < len.p) ? 1 : mod_q_mask;
162: }
163:
164: if (this->num_polynomials == 3)
165: {
166: /* allocate temporary array t */
167: t = malloc(this->N * sizeof(uint16_t));
168:
169: /* form F1 * F2 */
170: bi += len.p + len.m;
171: len = this->indices_len[1];
172: ring_mult_i(array, len, bi, this->N, mod_q_mask, t, array);
173:
174: /* form (F1 * F2) + F3 */
175: bi += len.p + len.m;
176: len = this->indices_len[2];
177: for (i = 0; i < len.p + len.m; i++)
178: {
179: if (i < len.p)
180: {
181: array[bi[i]] += 1;
182: }
183: else
184: {
185: array[bi[i]] -= 1;
186: }
187: array[bi[i]] &= mod_q_mask;
188: }
189: free(t);
190: }
191: }
192:
193: METHOD(ntru_poly_t, ring_mult, void,
194: private_ntru_poly_t *this, uint16_t *a, uint16_t *c)
195: {
196: uint16_t *t1, *t2;
197: uint16_t *bi = this->indices;
198: uint16_t mod_q_mask = this->q - 1;
199: int i;
200:
201: /* allocate temporary array t1 */
202: t1 = malloc(this->N * sizeof(uint16_t));
203:
204: if (this->num_polynomials == 1)
205: {
206: ring_mult_i(a, this->indices_len[0], bi, this->N, mod_q_mask, t1, c);
207: }
208: else
209: {
210: /* allocate temporary array t2 */
211: t2 = malloc(this->N * sizeof(uint16_t));
212:
213: /* t1 = a * b1 */
214: ring_mult_i(a, this->indices_len[0], bi, this->N, mod_q_mask, t1, t1);
215:
216: /* t1 = (a * b1) * b2 */
217: bi += this->indices_len[0].p + this->indices_len[0].m;
218: ring_mult_i(t1, this->indices_len[1], bi, this->N, mod_q_mask, t2, t1);
219:
220: /* t2 = a * b3 */
221: bi += this->indices_len[1].p + this->indices_len[1].m;
222: ring_mult_i(a, this->indices_len[2], bi, this->N, mod_q_mask, t2, t2);
223:
224: /* c = (a * b1 * b2) + (a * b3) */
225: for (i = 0; i < this->N; i++)
226: {
227: c[i] = (t1[i] + t2[i]) & mod_q_mask;
228: }
229: free(t2);
230: }
231: free(t1);
232: }
233:
234: METHOD(ntru_poly_t, destroy, void,
235: private_ntru_poly_t *this)
236: {
237: memwipe(this->indices, sizeof(uint16_t) * get_size(this));
238: free(this->indices);
239: free(this);
240: }
241:
242: /**
243: * Creates an empty ntru_poly_t object with space allocated for indices
244: */
245: static private_ntru_poly_t* ntru_poly_create(uint16_t N, uint16_t q,
246: uint32_t indices_len_p,
247: uint32_t indices_len_m,
248: bool is_product_form)
249: {
250: private_ntru_poly_t *this;
251: int n;
252:
253: INIT(this,
254: .public = {
255: .get_size = _get_size,
256: .get_indices = _get_indices,
257: .get_array = _get_array,
258: .ring_mult = _ring_mult,
259: .destroy = _destroy,
260: },
261: .N = N,
262: .q = q,
263: );
264:
265: if (is_product_form)
266: {
267: this->num_polynomials = 3;
268: for (n = 0; n < 3; n++)
269: {
270: this->indices_len[n].p = 0xff & indices_len_p;
271: this->indices_len[n].m = 0xff & indices_len_m;
272: this->num_indices += this->indices_len[n].p +
273: this->indices_len[n].m;
274: indices_len_p >>= 8;
275: indices_len_m >>= 8;
276: }
277: }
278: else
279: {
280: this->num_polynomials = 1;
281: this->indices_len[0].p = indices_len_p;
282: this->indices_len[0].m = indices_len_m;
283: this->num_indices = indices_len_p + indices_len_m;
284: }
285: this->indices = malloc(sizeof(uint16_t) * this->num_indices);
286:
287: return this;
288: }
289:
290: /*
291: * Described in header.
292: */
293: ntru_poly_t *ntru_poly_create_from_seed(ext_out_function_t mgf1_type,
294: chunk_t seed, uint8_t c_bits,
295: uint16_t N, uint16_t q,
296: uint32_t indices_len_p,
297: uint32_t indices_len_m,
298: bool is_product_form)
299: {
300: private_ntru_poly_t *this;
301: int n, num_indices, index_i = 0;
302: uint32_t index, limit;
303: uint8_t *used;
304: xof_bitspender_t *bitspender;
305:
306: bitspender = xof_bitspender_create(mgf1_type, seed, TRUE);
307: if (!bitspender)
308: {
309: return NULL;
310: }
311: this = ntru_poly_create(N, q, indices_len_p, indices_len_m, is_product_form);
312: used = malloc(N);
313: limit = N * ((1 << c_bits) / N);
314:
315: /* generate indices for all polynomials */
316: for (n = 0; n < this->num_polynomials; n++)
317: {
318: memset(used, 0, N);
319: num_indices = this->indices_len[n].p + this->indices_len[n].m;
320:
321: /* generate indices for a single polynomial */
322: while (num_indices)
323: {
324: /* generate a random candidate index with a size of c_bits */
325: do
326: {
327: if (!bitspender->get_bits(bitspender, c_bits, &index))
328: {
329: bitspender->destroy(bitspender);
330: destroy(this);
331: free(used);
332: return NULL;
333: }
334: }
335: while (index >= limit);
336:
337: /* form index and check if unique */
338: index %= N;
339: if (!used[index])
340: {
341: used[index] = 1;
342: this->indices[index_i++] = index;
343: num_indices--;
344: }
345: }
346: }
347:
348: bitspender->destroy(bitspender);
349: free(used);
350:
351: return &this->public;
352: }
353:
354: /*
355: * Described in header.
356: */
357: ntru_poly_t *ntru_poly_create_from_data(uint16_t *data, uint16_t N, uint16_t q,
358: uint32_t indices_len_p,
359: uint32_t indices_len_m,
360: bool is_product_form)
361: {
362: private_ntru_poly_t *this;
363: int i;
364:
365: this = ntru_poly_create(N, q, indices_len_p, indices_len_m, is_product_form);
366:
367: for (i = 0; i < this->num_indices; i++)
368: {
369: this->indices[i] = data[i];
370: }
371:
372: return &this->public;
373: }
374:
375: EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_seed);
376:
377: EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_data);