projects / strongswan.git / blob
? search:


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