Implement ring multiplication method
[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_indices(uint16_t *a, indices_len_t len, uint16_t *indices,
96 uint16_t N, uint16_t mod_q_mask, uint16_t *c)
97 {
98 uint16_t *t;
99 int i, j, k;
100
101 /* allocate and initialize temporary array t */
102 t = malloc(N * sizeof(uint16_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 /* cleanup */
149 free(t);
150 }
151
152 METHOD(ntru_poly_t, ring_mult, void,
153 private_ntru_poly_t *this, uint16_t *a, uint16_t *c)
154 {
155 uint16_t *bi = this->indices, mod_q_mask = this->q - 1;
156
157 if (this->num_polynomials == 1)
158 {
159 ring_mult_indices(a, this->indices_len[0], bi, this->N, mod_q_mask, c);
160 }
161 else
162 {
163 uint16_t *t1, *t2;
164 int i;
165
166 /* allocate temporary arrays */
167 t1 = malloc(this->N * sizeof(uint16_t));
168 t2 = malloc(this->N * sizeof(uint16_t));
169
170 /* t1 = a * b1 */
171 ring_mult_indices(a, this->indices_len[0], bi, this->N, mod_q_mask, t1);
172
173 /* t1 = (a * b1) * b2 */
174 bi += this->indices_len[0].p + this->indices_len[0].m;
175 ring_mult_indices(t1, this->indices_len[1], bi, this->N, mod_q_mask, t1);
176
177 /* t2 = a * b3 */
178 bi += this->indices_len[1].p + this->indices_len[1].m;
179 ring_mult_indices(a, this->indices_len[2], bi, this->N, mod_q_mask, t2);
180
181 /* c = (a * b1 * b2) + (a * b3) */
182 for (i = 0; i < this->N; i++)
183 {
184 c[i] = (t1[i] + t2[i]) & mod_q_mask;
185 }
186
187 /* cleanup */
188 free(t1);
189 free(t2);
190 }
191 }
192
193 METHOD(ntru_poly_t, destroy, void,
194 private_ntru_poly_t *this)
195 {
196 memwipe(this->indices, get_size(this));
197 free(this->indices);
198 free(this);
199 }
200
201 /*
202 * Described in header.
203 */
204 ntru_poly_t *ntru_poly_create(hash_algorithm_t alg, chunk_t seed,
205 uint8_t c_bits, uint16_t N, uint16_t q,
206 uint32_t indices_len_p, uint32_t indices_len_m,
207 bool is_product_form)
208 {
209 private_ntru_poly_t *this;
210 size_t hash_len, octet_count = 0, i;
211 uint8_t octets[HASH_SIZE_SHA512], *used, num_left = 0, num_needed;
212 uint16_t index, limit, left = 0;
213 int n, num_indices, index_i = 0;
214 ntru_mgf1_t *mgf1;
215
216 DBG2(DBG_LIB, "MGF1 is seeded with %u bytes", seed.len);
217 mgf1 = ntru_mgf1_create(alg, seed, TRUE);
218 if (!mgf1)
219 {
220 return NULL;
221 }
222 i = hash_len = mgf1->get_hash_size(mgf1);
223
224 INIT(this,
225 .public = {
226 .get_size = _get_size,
227 .get_indices = _get_indices,
228 .ring_mult = _ring_mult,
229 .destroy = _destroy,
230 },
231 .N = N,
232 .q = q,
233 );
234
235 if (is_product_form)
236 {
237 this->num_polynomials = 3;
238 for (n = 0; n < 3; n++)
239 {
240 this->indices_len[n].p = 0xff & indices_len_p;
241 this->indices_len[n].m = 0xff & indices_len_m;
242 indices_len_p >>= 8;
243 indices_len_m >>= 8;
244 }
245 }
246 else
247 {
248 this->num_polynomials = 1;
249 this->indices_len[0].p = indices_len_p;
250 this->indices_len[0].m = indices_len_m;
251 }
252 this->indices = malloc(sizeof(uint16_t) * get_size(this)),
253
254 used = malloc(N);
255 limit = N * ((1 << c_bits) / N);
256
257 /* generate indices for all polynomials */
258 for (n = 0; n < this->num_polynomials; n++)
259 {
260 memset(used, 0, N);
261 num_indices = this->indices_len[n].p + this->indices_len[n].m;
262
263 /* generate indices for a single polynomial */
264 while (num_indices)
265 {
266 /* generate a random candidate index with a size of c_bits */
267 do
268 {
269 /* use any leftover bits first */
270 index = num_left ? left << (c_bits - num_left) : 0;
271
272 /* get the rest of the bits needed from new octets */
273 num_needed = c_bits - num_left;
274
275 while (num_needed)
276 {
277 if (i == hash_len)
278 {
279 /* get another block from MGF1 */
280 if (!mgf1->get_mask(mgf1, hash_len, octets))
281 {
282 mgf1->destroy(mgf1);
283 destroy(this);
284 free(used);
285 return NULL;
286 }
287 octet_count += hash_len;
288 i = 0;
289 }
290 left = octets[i++];
291
292 if (num_needed <= 8)
293 {
294 /* all bits needed to fill the index are in this octet */
295 index |= left >> (8 - num_needed);
296 num_left = 8 - num_needed;
297 num_needed = 0;
298 left &= 0xff >> (8 - num_left);
299 }
300 else
301 {
302 /* more than one octet will be needed */
303 index |= left << (num_needed - 8);
304 num_needed -= 8;
305 }
306 }
307 }
308 while (index >= limit);
309
310 /* form index and check if unique */
311 index %= N;
312 if (!used[index])
313 {
314 used[index] = 1;
315 this->indices[index_i++] = index;
316 num_indices--;
317 }
318 }
319 }
320
321 DBG2(DBG_LIB, "MGF1 generates %u octets to derive %u indices",
322 octet_count, get_size(this));
323 mgf1->destroy(mgf1);
324 free(used);
325
326 return &this->public;
327 }
328
329 EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create);