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