Defined ntru_poly_create_from_seed() and ntru_poly_create_from_data() constructors...
[strongswan.git] / src / libstrongswan / plugins / ntru / ntru_crypto / ntru_crypto_ntru_encrypt.c
1 /******************************************************************************
2 * NTRU Cryptography Reference Source Code
3 * Copyright (c) 2009-2013, by Security Innovation, Inc. All rights reserved.
4 *
5 * ntru_crypto_ntru_encrypt.c is a component of ntru-crypto.
6 *
7 * Copyright (C) 2009-2013 Security Innovation
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22 *
23 *****************************************************************************/
24
25 /******************************************************************************
26 *
27 * File: ntru_crypto_ntru_encrypt.c
28 *
29 * Contents: Routines implementing NTRUEncrypt encryption and decryption and
30 * key generation.
31 *
32 *****************************************************************************/
33
34
35 #include <stdlib.h>
36 #include <string.h>
37 #include <assert.h>
38 #include "ntru_crypto.h"
39 #include "ntru_crypto_ntru_encrypt_param_sets.h"
40 #include "ntru_crypto_ntru_encrypt_key.h"
41 #include "ntru_crypto_ntru_convert.h"
42 #include "ntru_crypto_ntru_poly.h"
43 #
44 #include "ntru_trits.h"
45 #include "ntru_poly.h"
46
47 /* ntru_crypto_ntru_encrypt
48 *
49 * Implements NTRU encryption (SVES) for the parameter set specified in
50 * the public key blob.
51 *
52 * Before invoking this function, a DRBG must be instantiated using
53 * ntru_crypto_drbg_instantiate() to obtain a DRBG handle, and in that
54 * instantiation the requested security strength must be at least as large
55 * as the security strength of the NTRU parameter set being used.
56 * Failure to instantiate the DRBG with the proper security strength will
57 * result in this function returning DRBG_ERROR_BASE + DRBG_BAD_LENGTH.
58 *
59 * The required minimum size of the output ciphertext buffer (ct) may be
60 * queried by invoking this function with ct = NULL. In this case, no
61 * encryption is performed, NTRU_OK is returned, and the required minimum
62 * size for ct is returned in ct_len.
63 *
64 * When ct != NULL, at invocation *ct_len must be the size of the ct buffer.
65 * Upon return it is the actual size of the ciphertext.
66 *
67 * Returns NTRU_OK if successful.
68 * Returns NTRU_DRBG_FAIL if the DRBG handle is invalid.
69 * Returns NTRU_BAD_PARAMETER if an argument pointer (other than ct) is NULL.
70 * Returns NTRU_BAD_LENGTH if a length argument (pubkey_blob_len or pt_len) is
71 * zero, or if pt_len exceeds the maximum plaintext length for the parameter set.
72 * Returns NTRU_BAD_PUBLIC_KEY if the public-key blob is invalid
73 * (unknown format, corrupt, bad length).
74 * Returns NTRU_BUFFER_TOO_SMALL if the ciphertext buffer is too small.
75 * Returns NTRU_NO_MEMORY if memory needed cannot be allocated from the heap.
76 */
77
78 uint32_t
79 ntru_crypto_ntru_encrypt(
80 ntru_drbg_t *drbg, /* in - handle of DRBG */
81 uint16_t pubkey_blob_len, /* in - no. of octets in public key
82 blob */
83 uint8_t const *pubkey_blob, /* in - pointer to public key */
84 uint16_t pt_len, /* in - no. of octets in plaintext */
85 uint8_t const *pt, /* in - pointer to plaintext */
86 uint16_t *ct_len, /* in/out - no. of octets in ct, addr for
87 no. of octets in ciphertext */
88 uint8_t *ct) /* out - address for ciphertext */
89 {
90 NTRU_ENCRYPT_PARAM_SET *params = NULL;
91 uint8_t const *pubkey_packed = NULL;
92 uint8_t pubkey_pack_type = 0x00;
93 uint16_t packed_ct_len;
94 size_t scratch_buf_len;
95 uint32_t dr;
96 uint32_t dr1 = 0;
97 uint32_t dr2 = 0;
98 uint32_t dr3 = 0;
99 uint16_t ring_mult_tmp_len;
100 int16_t m1 = 0;
101 uint16_t *scratch_buf = NULL;
102 uint16_t *ringel_buf = NULL;
103 uint8_t *b_buf = NULL;
104 uint8_t *tmp_buf = NULL;
105 bool msg_rep_good = FALSE;
106 hash_algorithm_t hash_algid;
107 uint16_t mprime_len = 0;
108 uint16_t mod_q_mask;
109 uint32_t result = NTRU_OK;
110 ntru_trits_t *mask;
111 uint8_t *mask_trits;
112 chunk_t seed;
113 ntru_poly_t *r_poly;
114
115 /* check for bad parameters */
116
117 if (!pubkey_blob || !pt || !ct_len)
118 {
119 return NTRU_BAD_PARAMETER;
120 }
121 if ((pubkey_blob_len == 0) || (pt_len == 0))
122 {
123 return NTRU_BAD_LENGTH;
124 }
125
126 /* get a pointer to the parameter-set parameters, the packing type for
127 * the public key, and a pointer to the packed public key
128 */
129
130 if (!ntru_crypto_ntru_encrypt_key_parse(TRUE /* pubkey */, pubkey_blob_len,
131 pubkey_blob, &pubkey_pack_type,
132 NULL, &params, &pubkey_packed,
133 NULL))
134 {
135 return NTRU_BAD_PUBLIC_KEY;
136 }
137
138 /* return the ciphertext size if requested */
139
140 packed_ct_len = (params->N * params->q_bits + 7) >> 3;
141 if (!ct)
142 {
143 *ct_len = packed_ct_len;
144 return NTRU_OK;
145 }
146
147 /* check the ciphertext buffer size */
148
149 if (*ct_len < packed_ct_len)
150 {
151 return NTRU_BUFFER_TOO_SMALL;
152 }
153
154 /* check the plaintext length */
155
156 if (pt_len > params->m_len_max)
157 {
158 return NTRU_BAD_LENGTH;
159 }
160
161 /* allocate memory for all operations */
162
163 if (params->is_product_form)
164 {
165 ring_mult_tmp_len = params->N << 1; /* 2N 16-bit word buffer */
166 dr1 = params->dF_r & 0xff;
167 dr2 = (params->dF_r >> 8) & 0xff;
168 dr3 = (params->dF_r >> 16) & 0xff;
169 dr = dr1 + dr2 + dr3;
170 }
171 else
172 {
173 ring_mult_tmp_len = params->N; /* N 16-bit word buffer */
174 dr = params->dF_r;
175 }
176 scratch_buf_len = (ring_mult_tmp_len << 1) +
177 /* X-byte temp buf for ring mult and
178 other intermediate results */
179 (params->N << 1) + /* 2N-byte buffer for ring elements
180 and overflow from temp buffer */
181 (dr << 2) + /* buffer for r indices */
182 params->sec_strength_len;
183 /* buffer for b */
184 scratch_buf = malloc(scratch_buf_len);
185 if (!scratch_buf)
186 {
187 return NTRU_OUT_OF_MEMORY;
188 }
189 ringel_buf = scratch_buf + ring_mult_tmp_len;
190 b_buf = (uint8_t *)(ringel_buf + params->N);
191 tmp_buf = (uint8_t *)scratch_buf;
192
193 /* set hash algorithm based on security strength */
194 hash_algid = (params->sec_strength_len <= 20) ? HASH_SHA1 : HASH_SHA256;
195
196 /* set constants */
197 mod_q_mask = params->q - 1;
198
199 /* loop until a message representative with proper weight is achieved */
200
201 do {
202 uint8_t *ptr = tmp_buf;
203
204 /* get b */
205 if (drbg->generate(drbg, params->sec_strength_len * BITS_PER_BYTE,
206 params->sec_strength_len, b_buf))
207 {
208 result = NTRU_OK;
209 }
210 else
211 {
212 result = NTRU_FAIL;
213 }
214
215 if (result == NTRU_OK)
216 {
217
218 /* form sData (OID || m || b || hTrunc) */
219 memcpy(ptr, params->OID, 3);
220 ptr += 3;
221 memcpy(ptr, pt, pt_len);
222 ptr += pt_len;
223 memcpy(ptr, b_buf, params->sec_strength_len);
224 ptr += params->sec_strength_len;
225 memcpy(ptr, pubkey_packed, params->sec_strength_len);
226 ptr += params->sec_strength_len;
227
228 DBG2(DBG_LIB, "generate polynomial r");
229
230 seed = chunk_create(tmp_buf, ptr - tmp_buf);
231 r_poly = ntru_poly_create_from_seed(hash_algid, seed, params->c_bits,
232 params->N, params->q,
233 params->dF_r, params->dF_r,
234 params->is_product_form);
235 if (!r_poly)
236 {
237 result = NTRU_MGF1_FAIL;
238 }
239 }
240
241 if (result == NTRU_OK)
242 {
243 uint16_t pubkey_packed_len;
244
245 /* unpack the public key */
246 assert(pubkey_pack_type == NTRU_ENCRYPT_KEY_PACKED_COEFFICIENTS);
247 pubkey_packed_len = (params->N * params->q_bits + 7) >> 3;
248 ntru_octets_2_elements(pubkey_packed_len, pubkey_packed,
249 params->q_bits, ringel_buf);
250
251 /* form R = h * r */
252 r_poly->ring_mult(r_poly, ringel_buf, ringel_buf);
253 r_poly->destroy(r_poly);
254
255 /* form R mod 4 */
256 ntru_coeffs_mod4_2_octets(params->N, ringel_buf, tmp_buf);
257
258 /* form mask */
259 seed = chunk_create(tmp_buf, (params->N + 3)/4);
260 mask = ntru_trits_create(params->N, hash_algid, seed);
261 if (!mask)
262 {
263 result = NTRU_MGF1_FAIL;
264 }
265 }
266
267 if (result == NTRU_OK)
268 {
269 uint8_t *Mtrin_buf = tmp_buf + params->N;
270 uint8_t *M_buf = Mtrin_buf + params->N -
271 (params->sec_strength_len + params->m_len_len +
272 params->m_len_max + 2);
273 uint16_t i;
274
275 /* form the padded message M */
276 ptr = M_buf;
277 memcpy(ptr, b_buf, params->sec_strength_len);
278 ptr += params->sec_strength_len;
279 if (params->m_len_len == 2)
280 *ptr++ = (uint8_t)((pt_len >> 8) & 0xff);
281 *ptr++ = (uint8_t)(pt_len & 0xff);
282 memcpy(ptr, pt, pt_len);
283 ptr += pt_len;
284
285 /* add an extra zero byte in case without it the bit string
286 * is not a multiple of 3 bits and therefore might not be
287 * able to produce enough trits
288 */
289
290 memset(ptr, 0, params->m_len_max - pt_len + 2);
291
292 /* convert M to trits (Mbin to Mtrin) */
293 mprime_len = params->N;
294 if (params->is_product_form)
295 {
296 --mprime_len;
297 }
298
299 ntru_bits_2_trits(M_buf, mprime_len, Mtrin_buf);
300 mask_trits = mask->get_trits(mask);
301
302 /* form the msg representative m' by adding Mtrin to mask, mod p */
303 if (params->is_product_form)
304 {
305 for (i = 0; i < mprime_len; i++)
306 {
307 tmp_buf[i] = mask_trits[i] + Mtrin_buf[i];
308 if (tmp_buf[i] >= 3)
309 {
310 tmp_buf[i] -= 3;
311 }
312 if (tmp_buf[i] == 1)
313 {
314 ++m1;
315 }
316 else if (tmp_buf[i] == 2)
317 {
318 --m1;
319 }
320 }
321 }
322 else
323 {
324 for (i = 0; i < mprime_len; i++)
325 {
326 tmp_buf[i] = mask_trits[i] + Mtrin_buf[i];
327 if (tmp_buf[i] >= 3)
328 {
329 tmp_buf[i] -= 3;
330 }
331 }
332 }
333 mask->destroy(mask);
334
335 /* check that message representative meets minimum weight
336 * requirements
337 */
338
339 if (params->is_product_form)
340 msg_rep_good = m1 < 0 ? (bool)(-m1 <= params->min_msg_rep_wt) :
341 (bool)( m1 <= params->min_msg_rep_wt);
342 else
343 msg_rep_good = ntru_poly_check_min_weight(mprime_len, tmp_buf,
344 params->min_msg_rep_wt);
345 msg_rep_good = TRUE;
346 }
347 } while ((result == NTRU_OK) && !msg_rep_good);
348
349 if (result == NTRU_OK)
350 {
351 uint16_t i;
352
353 /* form ciphertext e by adding m' to R mod q */
354
355 for (i = 0; i < mprime_len; i++) {
356 if (tmp_buf[i] == 1)
357 ringel_buf[i] = (ringel_buf[i] + 1) & mod_q_mask;
358 else if (tmp_buf[i] == 2)
359 ringel_buf[i] = (ringel_buf[i] - 1) & mod_q_mask;
360 }
361 if (params->is_product_form)
362 ringel_buf[i] = (ringel_buf[i] - m1) & mod_q_mask;
363
364 /* pack ciphertext */
365 ntru_elements_2_octets(params->N, ringel_buf, params->q_bits, ct);
366 *ct_len = packed_ct_len;
367 }
368
369 /* cleanup */
370 memset(scratch_buf, 0, scratch_buf_len);
371 free(scratch_buf);
372
373 return result;
374 }
375
376
377 /* ntru_crypto_ntru_decrypt
378 *
379 * Implements NTRU decryption (SVES) for the parameter set specified in
380 * the private key blob.
381 *
382 * The maximum size of the output plaintext may be queried by invoking
383 * this function with pt = NULL. In this case, no decryption is performed,
384 * NTRU_OK is returned, and the maximum size the plaintext could be is
385 * returned in pt_len.
386 * Note that until the decryption is performed successfully, the actual size
387 * of the resulting plaintext cannot be known.
388 *
389 * When pt != NULL, at invocation *pt_len must be the size of the pt buffer.
390 * Upon return it is the actual size of the plaintext.
391 *
392 * Returns NTRU_OK if successful.
393 * Returns NTRU_BAD_PARAMETER if an argument pointer (other than pt) is NULL.
394 * Returns NTRU_BAD_LENGTH if a length argument (privkey_blob) is zero, or if
395 * ct_len is invalid for the parameter set.
396 * Returns NTRU_BAD_PRIVATE_KEY if the private-key blob is invalid
397 * (unknown format, corrupt, bad length).
398 * Returns NTRU_BUFFER_TOO_SMALL if the plaintext buffer is too small.
399 * Returns NTRU_NO_MEMORY if memory needed cannot be allocated from the heap.
400 * Returns NTRU_FAIL if a decryption error occurs.
401 */
402
403 uint32_t
404 ntru_crypto_ntru_decrypt(
405 uint16_t privkey_blob_len, /* in - no. of octets in private key
406 blob */
407 uint8_t const *privkey_blob, /* in - pointer to private key */
408 uint16_t ct_len, /* in - no. of octets in ciphertext */
409 uint8_t const *ct, /* in - pointer to ciphertext */
410 uint16_t *pt_len, /* in/out - no. of octets in pt, addr for
411 no. of octets in plaintext */
412 uint8_t *pt) /* out - address for plaintext */
413 {
414 NTRU_ENCRYPT_PARAM_SET *params = NULL;
415 uint8_t const *privkey_packed = NULL;
416 uint8_t const *pubkey_packed = NULL;
417 uint8_t privkey_pack_type = 0x00;
418 uint8_t pubkey_pack_type = 0x00;
419 size_t scratch_buf_len;
420 uint32_t dF_r;
421 uint32_t dF_r1 = 0;
422 uint32_t dF_r2 = 0;
423 uint32_t dF_r3 = 0;
424 uint16_t ring_mult_tmp_len;
425 int16_t m1 = 0;
426 uint16_t *scratch_buf = NULL;
427 uint16_t *ringel_buf1 = NULL;
428 uint16_t *ringel_buf2 = NULL;
429 uint16_t *i_buf = NULL;
430 uint8_t *m_buf = NULL;
431 uint8_t *tmp_buf = NULL;
432 uint8_t *Mtrin_buf = NULL;
433 uint8_t *M_buf = NULL;
434 uint8_t *ptr = NULL;
435 hash_algorithm_t hash_algid;
436 uint16_t cmprime_len;
437 uint16_t mod_q_mask;
438 uint16_t q_mod_p;
439 uint16_t cm_len = 0;
440 uint16_t num_zeros;
441 uint16_t i;
442 bool decryption_ok = TRUE;
443 uint32_t result = NTRU_OK;
444 ntru_trits_t *mask;
445 uint8_t *mask_trits;
446 chunk_t seed;
447 ntru_poly_t *F_poly, *r_poly;
448
449 /* check for bad parameters */
450 if (!privkey_blob || !ct || !pt_len)
451 {
452 return NTRU_BAD_PARAMETER;
453 }
454 if ((privkey_blob_len == 0) || (ct_len == 0))
455 {
456 return NTRU_BAD_LENGTH;
457 }
458
459 /* get a pointer to the parameter-set parameters, the packing types for
460 * the public and private keys, and pointers to the packed public and
461 * private keys
462 */
463
464 if (!ntru_crypto_ntru_encrypt_key_parse(FALSE /* privkey */,
465 privkey_blob_len,
466 privkey_blob, &pubkey_pack_type,
467 &privkey_pack_type, &params,
468 &pubkey_packed, &privkey_packed))
469 {
470 return NTRU_BAD_PRIVATE_KEY;
471 }
472
473 /* return the max plaintext size if requested */
474
475 if (!pt)
476 {
477 *pt_len = params->m_len_max;
478 return NTRU_OK;
479 }
480
481 /* cannot check the plaintext buffer size until after the plaintext
482 * is derived, if we allow plaintext buffers only as large as the
483 * actual plaintext
484 */
485
486 /* check the ciphertext length */
487
488 if (ct_len != (params->N * params->q_bits + 7) >> 3)
489 {
490 return NTRU_BAD_LENGTH;
491 }
492
493 /* allocate memory for all operations */
494
495 if (params->is_product_form)
496 {
497 ring_mult_tmp_len = params->N << 1; /* 2N 16-bit word buffer */
498 dF_r1 = params->dF_r & 0xff;
499 dF_r2 = (params->dF_r >> 8) & 0xff;
500 dF_r3 = (params->dF_r >> 16) & 0xff;
501 dF_r = dF_r1 + dF_r2 + dF_r3;
502 } else {
503 ring_mult_tmp_len = params->N; /* N 16-bit word buffer */
504 dF_r = params->dF_r;
505 }
506 scratch_buf_len = (ring_mult_tmp_len << 1) +
507 /* X-byte temp buf for ring mult and
508 other intermediate results */
509 (params->N << 2) + /* 2 2N-byte bufs for ring elements
510 and overflow from temp buffer */
511 (dF_r << 2) + /* buffer for F, r indices */
512 params->m_len_max; /* buffer for plaintext */
513 scratch_buf = malloc(scratch_buf_len);
514 if (!scratch_buf)
515 {
516 return NTRU_OUT_OF_MEMORY;
517 }
518 ringel_buf1 = scratch_buf + ring_mult_tmp_len;
519 ringel_buf2 = ringel_buf1 + params->N;
520 i_buf = ringel_buf2 + params->N;
521 m_buf = (uint8_t *)(i_buf + (dF_r << 1));
522 tmp_buf = (uint8_t *)scratch_buf;
523 Mtrin_buf = (uint8_t *)ringel_buf1;
524 M_buf = Mtrin_buf + params->N;
525
526 /* set hash algorithm based on security strength */
527 hash_algid = (params->sec_strength_len <= 20) ? HASH_SHA1 : HASH_SHA256;
528
529 /* set constants */
530 mod_q_mask = params->q - 1;
531 q_mod_p = params->q % 3;
532
533 /* unpack the ciphertext */
534 ntru_octets_2_elements(ct_len, ct, params->q_bits, ringel_buf2);
535
536 /* unpack the private key */
537 if (privkey_pack_type == NTRU_ENCRYPT_KEY_PACKED_TRITS)
538 {
539 ntru_packed_trits_2_indices(privkey_packed, params->N, i_buf,
540 i_buf + dF_r);
541
542 }
543 else if (privkey_pack_type == NTRU_ENCRYPT_KEY_PACKED_INDICES)
544 {
545 ntru_octets_2_elements(
546 (((uint16_t)dF_r << 1) * params->N_bits + 7) >> 3,
547 privkey_packed, params->N_bits, i_buf);
548
549 }
550 else
551 {
552 assert(FALSE);
553 }
554
555 /* form cm':
556 * F * e
557 * A = e * (1 + pF) mod q = e + pFe mod q
558 * a = A in the range [-q/2, q/2)
559 * cm' = a mod p
560 */
561 F_poly = ntru_poly_create_from_data(i_buf, params->N, params->q,
562 params->dF_r, params->dF_r,
563 params->is_product_form);
564 F_poly->ring_mult(F_poly, ringel_buf2, ringel_buf1);
565 F_poly->destroy(F_poly);
566
567 cmprime_len = params->N;
568 if (params->is_product_form)
569 {
570 --cmprime_len;
571 for (i = 0; i < cmprime_len; i++)
572 {
573 ringel_buf1[i] = (ringel_buf2[i] + 3 * ringel_buf1[i]) & mod_q_mask;
574 if (ringel_buf1[i] >= (params->q >> 1))
575 {
576 ringel_buf1[i] = ringel_buf1[i] - q_mod_p;
577 }
578 Mtrin_buf[i] = (uint8_t)(ringel_buf1[i] % 3);
579 if (Mtrin_buf[i] == 1)
580 {
581 ++m1;
582 }
583 else if (Mtrin_buf[i] == 2)
584 {
585 --m1;
586 }
587 }
588 }
589 else
590 {
591 for (i = 0; i < cmprime_len; i++)
592 {
593 ringel_buf1[i] = (ringel_buf2[i] + 3 * ringel_buf1[i]) & mod_q_mask;
594 if (ringel_buf1[i] >= (params->q >> 1))
595 {
596 ringel_buf1[i] = ringel_buf1[i] - q_mod_p;
597 }
598 Mtrin_buf[i] = (uint8_t)(ringel_buf1[i] % 3);
599 }
600 }
601
602 /* check that the candidate message representative meets minimum weight
603 * requirements
604 */
605
606 if (params->is_product_form)
607 {
608 decryption_ok = m1 < 0 ? (bool)(-m1 <= params->min_msg_rep_wt) :
609 (bool)( m1 <= params->min_msg_rep_wt);
610 }
611 else
612 {
613 decryption_ok = ntru_poly_check_min_weight(cmprime_len, Mtrin_buf,
614 params->min_msg_rep_wt);
615 }
616
617 /* form cR = e - cm' mod q */
618 for (i = 0; i < cmprime_len; i++)
619 {
620 if (Mtrin_buf[i] == 1)
621 {
622 ringel_buf2[i] = (ringel_buf2[i] - 1) & mod_q_mask;
623 }
624 else if (Mtrin_buf[i] == 2)
625 {
626 ringel_buf2[i] = (ringel_buf2[i] + 1) & mod_q_mask;
627 }
628 }
629 if (params->is_product_form)
630 {
631 ringel_buf2[i] = (ringel_buf2[i] + m1) & mod_q_mask;
632 }
633
634 /* form cR mod 4 */
635 ntru_coeffs_mod4_2_octets(params->N, ringel_buf2, tmp_buf);
636
637 /* form mask */
638 seed = chunk_create(tmp_buf, (params->N + 3)/4);
639 mask = ntru_trits_create(params->N, hash_algid, seed);
640 if (!mask)
641 {
642 result = NTRU_MGF1_FAIL;
643 }
644 else
645 {
646 mask_trits = mask->get_trits(mask);
647
648 /* form cMtrin by subtracting mask from cm', mod p */
649 for (i = 0; i < cmprime_len; i++)
650 {
651 Mtrin_buf[i] = Mtrin_buf[i] - mask_trits[i];
652 if (Mtrin_buf[i] >= 3)
653 {
654 Mtrin_buf[i] += 3;
655 }
656 }
657 mask->destroy(mask);
658
659 if (params->is_product_form)
660
661 /* set the last trit to zero since that's what it was, and
662 * because it can't be calculated from (cm' - mask) since
663 * we don't have the correct value for the last cm' trit
664 */
665
666 Mtrin_buf[i] = 0;
667
668 /* convert cMtrin to cM (Mtrin to Mbin) */
669
670 if (!ntru_trits_2_bits(Mtrin_buf, params->N, M_buf))
671 decryption_ok = FALSE;
672
673 /* validate the padded message cM and copy cm to m_buf */
674
675 ptr = M_buf + params->sec_strength_len;
676 if (params->m_len_len == 2)
677 cm_len = (uint16_t)(*ptr++) << 16;
678 cm_len |= (uint16_t)(*ptr++);
679 if (cm_len > params->m_len_max) {
680 cm_len = params->m_len_max;
681 decryption_ok = FALSE;
682 }
683 memcpy(m_buf, ptr, cm_len);
684 ptr += cm_len;
685 num_zeros = params->m_len_max - cm_len + 1;
686 for (i = 0; i < num_zeros; i++) {
687 if (ptr[i] != 0)
688 decryption_ok = FALSE;
689 }
690
691 /* form sData (OID || m || b || hTrunc) */
692
693 ptr = tmp_buf;
694 memcpy(ptr, params->OID, 3);
695 ptr += 3;
696 memcpy(ptr, m_buf, cm_len);
697 ptr += cm_len;
698 memcpy(ptr, M_buf, params->sec_strength_len);
699 ptr += params->sec_strength_len;
700 memcpy(ptr, pubkey_packed, params->sec_strength_len);
701 ptr += params->sec_strength_len;
702
703 /* generate cr */
704 DBG2(DBG_LIB, "generate polynomial r");
705
706 seed = chunk_create(tmp_buf, ptr - tmp_buf);
707 r_poly = ntru_poly_create_from_seed(hash_algid, seed, params->c_bits,
708 params->N, params->q,
709 params->dF_r, params->dF_r,
710 params->is_product_form);
711 if (!r_poly)
712 {
713 result = NTRU_MGF1_FAIL;
714 }
715 }
716
717 if (result == NTRU_OK)
718 {
719 /* unpack the public key */
720 {
721 uint16_t pubkey_packed_len;
722
723 assert(pubkey_pack_type == NTRU_ENCRYPT_KEY_PACKED_COEFFICIENTS);
724 pubkey_packed_len = (params->N * params->q_bits + 7) >> 3;
725 ntru_octets_2_elements(pubkey_packed_len, pubkey_packed,
726 params->q_bits, ringel_buf1);
727 }
728
729 /* form cR' = h * cr */
730 r_poly->ring_mult(r_poly, ringel_buf1, ringel_buf1);
731 r_poly->destroy(r_poly);
732
733 /* compare cR' to cR */
734 for (i = 0; i < params->N; i++)
735 {
736 if (ringel_buf1[i] != ringel_buf2[i])
737 {
738 decryption_ok = FALSE;
739 }
740 }
741
742 /* output plaintext and plaintext length */
743 if (decryption_ok)
744 {
745 if (*pt_len < cm_len)
746 {
747 return NTRU_BUFFER_TOO_SMALL;
748 }
749 memcpy(pt, m_buf, cm_len);
750 *pt_len = cm_len;
751 }
752 }
753
754 /* cleanup */
755 memset(scratch_buf, 0, scratch_buf_len);
756 free(scratch_buf);
757
758 if (!decryption_ok)
759 {
760 return NTRU_FAIL;
761 }
762
763 return result;
764 }
765
766
767 /* ntru_crypto_ntru_encrypt_keygen
768 *
769 * Implements key generation for NTRUEncrypt for the parameter set specified.
770 *
771 * The required minimum size of the output public-key buffer (pubkey_blob)
772 * may be queried by invoking this function with pubkey_blob = NULL.
773 * In this case, no key generation is performed, NTRU_OK is returned, and
774 * the required minimum size for pubkey_blob is returned in pubkey_blob_len.
775 *
776 * The required minimum size of the output private-key buffer (privkey_blob)
777 * may be queried by invoking this function with privkey_blob = NULL.
778 * In this case, no key generation is performed, NTRU_OK is returned, and
779 * the required minimum size for privkey_blob is returned in privkey_blob_len.
780 *
781 * The required minimum sizes of both pubkey_blob and privkey_blob may be
782 * queried as described above, in a single invocation of this function.
783 *
784 * When pubkey_blob != NULL and privkey_blob != NULL, at invocation
785 * *pubkey_blob_len must be the size of the pubkey_blob buffer and
786 * *privkey_blob_len must be the size of the privkey_blob buffer.
787 * Upon return, *pubkey_blob_len is the actual size of the public-key blob
788 * and *privkey_blob_len is the actual size of the private-key blob.
789 *
790 * Returns NTRU_OK if successful.
791 * Returns NTRU_BAD_PARAMETER if an argument pointer (other than pubkey_blob or
792 * privkey_blob) is NULL.
793 * Returns NTRU_INVALID_PARAMETER_SET if the parameter-set ID is invalid.
794 * Returns NTRU_BAD_LENGTH if a length argument is invalid.
795 * Returns NTRU_BUFFER_TOO_SMALL if either the pubkey_blob buffer or the
796 * privkey_blob buffer is too small.
797 * Returns NTRU_NO_MEMORY if memory needed cannot be allocated from the heap.
798 * Returns NTRU_FAIL if the polynomial generated for f is not invertible in
799 * (Z/qZ)[X]/(X^N - 1), which is extremely unlikely.
800 * Should this occur, this function should simply be invoked again.
801 */
802
803 uint32_t
804 ntru_crypto_ntru_encrypt_keygen(
805 ntru_drbg_t *drbg, /* in - handle of DRBG */
806 NTRU_ENCRYPT_PARAM_SET_ID param_set_id, /* in - parameter set ID */
807 uint16_t *pubkey_blob_len, /* in/out - no. of octets in
808 pubkey_blob, addr
809 for no. of octets
810 in pubkey_blob */
811 uint8_t *pubkey_blob, /* out - address for
812 public key blob */
813 uint16_t *privkey_blob_len, /* in/out - no. of octets in
814 privkey_blob, addr
815 for no. of octets
816 in privkey_blob */
817 uint8_t *privkey_blob) /* out - address for
818 private key blob */
819 {
820 NTRU_ENCRYPT_PARAM_SET *params = NULL;
821 uint16_t public_key_blob_len;
822 uint16_t private_key_blob_len;
823 uint8_t pubkey_pack_type;
824 uint8_t privkey_pack_type;
825 size_t scratch_buf_len;
826 uint32_t dF;
827 uint32_t dF1 = 0;
828 uint32_t dF2 = 0;
829 uint32_t dF3 = 0;
830 uint16_t *scratch_buf = NULL;
831 uint16_t *ringel_buf1 = NULL;
832 uint16_t *ringel_buf2 = NULL;
833 uint8_t *tmp_buf = NULL;
834 uint16_t mod_q_mask;
835 hash_algorithm_t hash_algid;
836 uint16_t seed_len;
837 chunk_t seed;
838 uint32_t result = NTRU_OK;
839 ntru_poly_t *F_poly = NULL;
840 ntru_poly_t *g_poly = NULL;
841 uint16_t *F_indices;
842
843 /* get a pointer to the parameter-set parameters */
844
845 if ((params = ntru_encrypt_get_params_with_id(param_set_id)) == NULL)
846 {
847 return NTRU_INVALID_PARAMETER_SET;
848 }
849
850 /* check for bad parameters */
851
852 if (!pubkey_blob_len || !privkey_blob_len)
853 {
854 return NTRU_BAD_PARAMETER;
855 }
856
857 /* get public and private key packing types and blob lengths */
858
859 ntru_crypto_ntru_encrypt_key_get_blob_params(params, &pubkey_pack_type,
860 &public_key_blob_len,
861 &privkey_pack_type,
862 &private_key_blob_len);
863
864 /* return the pubkey_blob size and/or privkey_blob size if requested */
865
866 if (!pubkey_blob || !privkey_blob)
867 {
868 if (!pubkey_blob)
869 *pubkey_blob_len = public_key_blob_len;
870 if (!privkey_blob)
871 *privkey_blob_len = private_key_blob_len;
872 return NTRU_OK;
873 }
874
875 /* check size of output buffers */
876
877 if ((*pubkey_blob_len < public_key_blob_len) ||
878 (*privkey_blob_len < private_key_blob_len))
879 {
880 return NTRU_BUFFER_TOO_SMALL;
881 }
882
883 /* allocate memory for all operations */
884 if (params->is_product_form) {
885 dF1 = params->dF_r & 0xff;
886 dF2 = (params->dF_r >> 8) & 0xff;
887 dF3 = (params->dF_r >> 16) & 0xff;
888 dF = dF1 + dF2 + dF3;
889 } else {
890 dF = params->dF_r;
891 }
892
893 scratch_buf_len = (params->N * 8) + /* 4N-byte temp buffer for ring inv
894 and other intermediate results,
895 2N-byte buffer for f, g indices
896 and overflow from temp buffer,
897 2N-byte buffer for f^-1 */
898 (dF << 2); /* buffer for F indices */
899 scratch_buf = malloc(scratch_buf_len);
900 if (!scratch_buf)
901 {
902 return NTRU_OUT_OF_MEMORY;
903 }
904 ringel_buf1 = scratch_buf + (params->N << 1);
905 ringel_buf2 = ringel_buf1 + params->N;
906 tmp_buf = (uint8_t *)scratch_buf;
907
908 /* set hash algorithm and seed length based on security strength */
909 if (params->sec_strength_len <= 20)
910 {
911 hash_algid = HASH_SHA1;
912 }
913 else
914 {
915 hash_algid = HASH_SHA256;
916 }
917 seed_len = params->sec_strength_len + 8;
918
919 /* set constants */
920
921 mod_q_mask = params->q - 1;
922
923 /* get random bytes for seed for generating trinary F
924 * as a list of indices
925 */
926
927 if (drbg->generate(drbg, params->sec_strength_len * BITS_PER_BYTE,
928 seed_len, tmp_buf))
929 {
930 result = NTRU_OK;
931 }
932 else
933 {
934 result = NTRU_DRBG_FAIL;
935 }
936
937 if (result == NTRU_OK)
938 {
939 DBG2(DBG_LIB, "generate polynomial F");
940
941 seed = chunk_create(tmp_buf, seed_len);
942 F_poly = ntru_poly_create_from_seed(hash_algid, seed, params->c_bits,
943 params->N, params->q,
944 params->dF_r, params->dF_r,
945 params->is_product_form);
946 if (!F_poly)
947 {
948 result = NTRU_MGF1_FAIL;
949 }
950 }
951
952 if (result == NTRU_OK)
953 {
954 uint32_t i;
955
956 memset(ringel_buf1, 0, params->N * sizeof(uint16_t));
957 F_indices = F_poly->get_indices(F_poly);
958
959 /* form F as a ring element */
960 if (params->is_product_form)
961 {
962 uint32_t dF3_offset = (dF1 + dF2) << 1;
963
964 /* form F1 as a ring element */
965 for (i = 0; i < dF1; i++)
966 {
967 ringel_buf1[F_indices[i]] = 1;
968 }
969 for (; i < (dF1 << 1); i++)
970 {
971 ringel_buf1[F_indices[i]] = mod_q_mask;
972 }
973
974 /* form F1 * F2 */
975 ntru_ring_mult_indices(ringel_buf1, (uint16_t)dF2, (uint16_t)dF2,
976 F_indices + (dF1 << 1), params->N, params->q,
977 scratch_buf, ringel_buf1);
978
979 /* form (F1 * F2) + F3 */
980 for (i = 0; i < dF3; i++)
981 {
982 uint16_t index = F_indices[dF3_offset + i];
983
984 ringel_buf1[index] = (ringel_buf1[index] + 1) & mod_q_mask;
985 }
986 for (; i < (dF3 << 1); i++)
987 {
988 uint16_t index = F_indices[dF3_offset + i];
989
990 ringel_buf1[index] = (ringel_buf1[index] - 1) & mod_q_mask;
991 }
992 }
993 else
994 {
995 /* form F as a ring element */
996 for (i = 0; i < dF; i++)
997 {
998 ringel_buf1[F_indices[i]] = 1;
999 }
1000 for (; i < (dF << 1); i++)
1001 {
1002 ringel_buf1[F_indices[i]] = mod_q_mask;
1003 }
1004 }
1005
1006 /* form f = 1 + pF */
1007 for (i = 0; i < params->N; i++)
1008 {
1009 ringel_buf1[i] = (ringel_buf1[i] * 3) & mod_q_mask;
1010 }
1011 ringel_buf1[0] = (ringel_buf1[0] + 1) & mod_q_mask;
1012
1013 /* find f^-1 in (Z/qZ)[X]/(X^N - 1) */
1014 if (!ntru_ring_inv(ringel_buf1, params->N, params->q,
1015 scratch_buf, ringel_buf2))
1016 {
1017 result = NTRU_FAIL;
1018 }
1019 }
1020
1021 if (result == NTRU_OK)
1022 {
1023
1024 /* get random bytes for seed for generating trinary polynomial g
1025 * as a list of indices
1026 */
1027 if (!drbg->generate(drbg, params->sec_strength_len * BITS_PER_BYTE,
1028 seed_len, tmp_buf))
1029 {
1030 result = NTRU_DRBG_FAIL;
1031 }
1032 }
1033
1034 if (result == NTRU_OK)
1035 {
1036 DBG2(DBG_LIB, "generate polynomial g");
1037
1038 seed = chunk_create(tmp_buf, seed_len);
1039 g_poly = ntru_poly_create_from_seed(hash_algid, seed, params->c_bits,
1040 params->N, params->q,
1041 params->dg + 1, params->dg, FALSE);
1042 if (!g_poly)
1043 {
1044 result = NTRU_MGF1_FAIL;
1045 }
1046 }
1047
1048 if (result == NTRU_OK)
1049 {
1050 uint16_t i;
1051
1052 /* compute h = p * (f^-1 * g) mod q */
1053 g_poly->ring_mult(g_poly, ringel_buf2, ringel_buf2);
1054 g_poly->destroy(g_poly);
1055
1056 for (i = 0; i < params->N; i++)
1057 {
1058 ringel_buf2[i] = (ringel_buf2[i] * 3) & mod_q_mask;
1059 }
1060
1061 /* create public key blob */
1062 ntru_crypto_ntru_encrypt_key_create_pubkey_blob(params, ringel_buf2,
1063 pubkey_pack_type,
1064 pubkey_blob);
1065 *pubkey_blob_len = public_key_blob_len;
1066
1067 /* create private key blob */
1068 ntru_crypto_ntru_encrypt_key_create_privkey_blob(params, ringel_buf2,
1069 F_indices,
1070 privkey_pack_type,
1071 tmp_buf, privkey_blob);
1072 *privkey_blob_len = private_key_blob_len;
1073 }
1074
1075 /* cleanup */
1076 DESTROY_IF(F_poly);
1077 memset(scratch_buf, 0, scratch_buf_len);
1078 free(scratch_buf);
1079
1080 return result;
1081 }