Implemented ntru_private_key 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_key.h"
40 #include "ntru_crypto_ntru_convert.h"
41 #include "ntru_crypto_ntru_poly.h"
42
43 #include "ntru_param_set.h"
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_param_set_t *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;
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_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 m1 = 0;
306 for (i = 0; i < mprime_len; i++)
307 {
308 tmp_buf[i] = mask_trits[i] + Mtrin_buf[i];
309 if (tmp_buf[i] >= 3)
310 {
311 tmp_buf[i] -= 3;
312 }
313 if (tmp_buf[i] == 1)
314 {
315 ++m1;
316 }
317 else if (tmp_buf[i] == 2)
318 {
319 --m1;
320 }
321 }
322 }
323 else
324 {
325 for (i = 0; i < mprime_len; i++)
326 {
327 tmp_buf[i] = mask_trits[i] + Mtrin_buf[i];
328 if (tmp_buf[i] >= 3)
329 {
330 tmp_buf[i] -= 3;
331 }
332 }
333 }
334 mask->destroy(mask);
335
336 /* check that message representative meets minimum weight
337 * requirements
338 */
339
340 if (params->is_product_form)
341 msg_rep_good = m1 < 0 ? (bool)(-m1 <= params->min_msg_rep_wt) :
342 (bool)( m1 <= params->min_msg_rep_wt);
343 else
344 msg_rep_good = ntru_poly_check_min_weight(mprime_len, tmp_buf,
345 params->min_msg_rep_wt);
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 }