Annotation of embedaddon/strongswan/src/libstrongswan/plugins/ntru/ntru_public_key.c, revision 1.1
1.1 ! misho 1: /*
! 2: * Copyright (C) 2014-2016 Andreas Steffen
! 3: * HSR Hochschule fuer Technik Rapperswil
! 4: *
! 5: * Copyright (C) 2009-2013 Security Innovation
! 6: *
! 7: * This program is free software; you can redistribute it and/or modify it
! 8: * under the terms of the GNU General Public License as published by the
! 9: * Free Software Foundation; either version 2 of the License, or (at your
! 10: * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
! 11: *
! 12: * This program is distributed in the hope that it will be useful, but
! 13: * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
! 14: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
! 15: * for more details.
! 16: */
! 17:
! 18: #include "ntru_public_key.h"
! 19: #include "ntru_trits.h"
! 20: #include "ntru_poly.h"
! 21: #include "ntru_convert.h"
! 22:
! 23: #include <utils/debug.h>
! 24: #include <utils/test.h>
! 25:
! 26: typedef struct private_ntru_public_key_t private_ntru_public_key_t;
! 27:
! 28: /**
! 29: * Private data of an ntru_public_key_t object.
! 30: */
! 31: struct private_ntru_public_key_t {
! 32: /**
! 33: * Public ntru_public_key_t interface.
! 34: */
! 35: ntru_public_key_t public;
! 36:
! 37: /**
! 38: * NTRU Parameter Set
! 39: */
! 40: const ntru_param_set_t *params;
! 41:
! 42: /**
! 43: * Polynomial h which is the public key
! 44: */
! 45: uint16_t *pubkey;
! 46:
! 47: /**
! 48: * Encoding of the public key
! 49: */
! 50: chunk_t encoding;
! 51:
! 52: /**
! 53: * Deterministic Random Bit Generator
! 54: */
! 55: drbg_t *drbg;
! 56:
! 57: };
! 58:
! 59: METHOD(ntru_public_key_t, get_id, ntru_param_set_id_t,
! 60: private_ntru_public_key_t *this)
! 61: {
! 62: return this->params->id;
! 63: }
! 64:
! 65: /**
! 66: * Generate NTRU encryption public key encoding
! 67: */
! 68: static void generate_encoding(private_ntru_public_key_t *this)
! 69: {
! 70: size_t pubkey_len;
! 71: u_char *enc;
! 72:
! 73: /* compute public key length encoded as packed coefficients */
! 74: pubkey_len = (this->params->N * this->params->q_bits + 7) / 8;
! 75:
! 76: /* allocate memory for public key encoding */
! 77: this->encoding = chunk_alloc(2 + NTRU_OID_LEN + pubkey_len);
! 78: enc = this->encoding.ptr;
! 79:
! 80: /* format header and packed public key */
! 81: *enc++ = NTRU_PUBKEY_TAG;
! 82: *enc++ = NTRU_OID_LEN;
! 83: memcpy(enc, this->params->oid, NTRU_OID_LEN);
! 84: enc += NTRU_OID_LEN;
! 85: ntru_elements_2_octets(this->params->N, this->pubkey,
! 86: this->params->q_bits, enc);
! 87: }
! 88:
! 89: METHOD(ntru_public_key_t, get_encoding, chunk_t,
! 90: private_ntru_public_key_t *this)
! 91: {
! 92: return this->encoding;
! 93: }
! 94:
! 95: #define MAX_SEC_STRENGTH_LEN 32 /* bytes */
! 96:
! 97: /**
! 98: * Shared with ntru_private_key.c
! 99: */
! 100: extern bool ntru_check_min_weight(uint16_t N, uint8_t *t, uint16_t min_wt);
! 101:
! 102: METHOD(ntru_public_key_t, encrypt, bool,
! 103: private_ntru_public_key_t *this, chunk_t plaintext, chunk_t *ciphertext)
! 104: {
! 105: ext_out_function_t alg;
! 106: size_t t_len, seed1_len, seed2_len;
! 107: uint16_t *t1, *t = NULL;
! 108: uint8_t b[MAX_SEC_STRENGTH_LEN];
! 109: uint8_t *t2, *Mtrin, *M, *mask_trits, *ptr;
! 110: uint16_t mod_q_mask, mprime_len = 0;
! 111: int16_t m1 = 0;
! 112: chunk_t seed = chunk_empty;
! 113: ntru_trits_t *mask;
! 114: ntru_poly_t *r_poly;
! 115: bool msg_rep_good, success = FALSE;
! 116: int i;
! 117:
! 118: *ciphertext = chunk_empty;
! 119:
! 120: if (plaintext.len > this->params->m_len_max)
! 121: {
! 122: DBG1(DBG_LIB, "plaintext exceeds maximum size");
! 123: return FALSE;
! 124: }
! 125:
! 126: if (this->params->sec_strength_len > MAX_SEC_STRENGTH_LEN)
! 127: {
! 128: DBG1(DBG_LIB, "required security strength exceeds %d bits",
! 129: MAX_SEC_STRENGTH_LEN * BITS_PER_BYTE);
! 130: return FALSE;
! 131: }
! 132:
! 133: /* allocate temporary array t */
! 134: t_len = (sizeof(uint16_t) + 3*sizeof(uint8_t)) * this->params->N;
! 135: t = malloc(t_len);
! 136: t1 = t;
! 137: t2 = (uint8_t *)(t1 + this->params->N);
! 138: Mtrin = t2 + this->params->N;
! 139: M = Mtrin + this->params->N;
! 140:
! 141: /* set hash algorithm based on security strength */
! 142: alg = (this->params->sec_strength_len <= 20) ? XOF_MGF1_SHA1 :
! 143: XOF_MGF1_SHA256;
! 144: /* set constants */
! 145: mod_q_mask = this->params->q - 1;
! 146:
! 147: /* allocate memory for the larger of the two seeds */
! 148: seed1_len = (this->params->N + 3)/4;
! 149: seed2_len = 3 + 2*this->params->sec_strength_len + plaintext.len;
! 150: seed = chunk_alloc(max(seed1_len, seed2_len));
! 151:
! 152: /* loop until a message representative with proper weight is achieved */
! 153: do
! 154: {
! 155: if (!this->drbg->generate(this->drbg, this->params->sec_strength_len, b))
! 156: {
! 157: goto err;
! 158: }
! 159:
! 160: /* form sData (OID || m || b || hTrunc) */
! 161: ptr = seed.ptr;
! 162: memcpy(ptr, this->params->oid, NTRU_OID_LEN);
! 163: ptr += NTRU_OID_LEN;
! 164: memcpy(ptr, plaintext.ptr, plaintext.len);
! 165: ptr += plaintext.len;
! 166: memcpy(ptr, b, this->params->sec_strength_len);
! 167: ptr += this->params->sec_strength_len;
! 168: memcpy(ptr, this->encoding.ptr + 2 + NTRU_OID_LEN,
! 169: this->params->sec_strength_len);
! 170: ptr += this->params->sec_strength_len;
! 171: seed.len = seed2_len;
! 172:
! 173: DBG2(DBG_LIB, "generate polynomial r");
! 174: r_poly = ntru_poly_create_from_seed(alg, seed, this->params->c_bits,
! 175: this->params->N, this->params->q,
! 176: this->params->dF_r, this->params->dF_r,
! 177: this->params->is_product_form);
! 178: if (!r_poly)
! 179: {
! 180: goto err;
! 181: }
! 182:
! 183: /* form R = h * r */
! 184: r_poly->ring_mult(r_poly, this->pubkey, t1);
! 185: r_poly->destroy(r_poly);
! 186:
! 187: /* form R mod 4 */
! 188: ntru_coeffs_mod4_2_octets(this->params->N, t1, seed.ptr);
! 189: seed.len = seed1_len;
! 190:
! 191: /* form mask */
! 192: mask = ntru_trits_create(this->params->N, alg, seed);
! 193: if (!mask)
! 194: {
! 195: DBG1(DBG_LIB, "mask creation failed");
! 196: goto err;
! 197: }
! 198:
! 199: /* form the padded message M */
! 200: ptr = M;
! 201: memcpy(ptr, b, this->params->sec_strength_len);
! 202: ptr += this->params->sec_strength_len;
! 203: if (this->params->m_len_len == 2)
! 204: {
! 205: *ptr++ = (uint8_t)((plaintext.len >> 8) & 0xff);
! 206: }
! 207: *ptr++ = (uint8_t)(plaintext.len & 0xff);
! 208: memcpy(ptr, plaintext.ptr, plaintext.len);
! 209: ptr += plaintext.len;
! 210:
! 211: /* add an extra zero byte in case without it the bit string
! 212: * is not a multiple of 3 bits and therefore might not be
! 213: * able to produce enough trits
! 214: */
! 215: memset(ptr, 0, this->params->m_len_max - plaintext.len + 2);
! 216:
! 217: /* convert M to trits (Mbin to Mtrin) */
! 218: mprime_len = this->params->N;
! 219: if (this->params->is_product_form)
! 220: {
! 221: --mprime_len;
! 222: }
! 223: ntru_bits_2_trits(M, mprime_len, Mtrin);
! 224: mask_trits = mask->get_trits(mask);
! 225:
! 226:
! 227: /* form the msg representative m' by adding Mtrin to mask, mod p */
! 228: if (this->params->is_product_form)
! 229: {
! 230: m1 = 0;
! 231: for (i = 0; i < mprime_len; i++)
! 232: {
! 233: t2[i] = mask_trits[i] + Mtrin[i];
! 234: if (t2[i] >= 3)
! 235: {
! 236: t2[i] -= 3;
! 237: }
! 238: if (t2[i] == 1)
! 239: {
! 240: ++m1;
! 241: }
! 242: else if (t2[i] == 2)
! 243: {
! 244: --m1;
! 245: }
! 246: }
! 247: }
! 248: else
! 249: {
! 250: for (i = 0; i < mprime_len; i++)
! 251: {
! 252: t2[i] = mask_trits[i] + Mtrin[i];
! 253: if (t2[i] >= 3)
! 254: {
! 255: t2[i] -= 3;
! 256: }
! 257: }
! 258: }
! 259: mask->destroy(mask);
! 260:
! 261: /* check that message representative meets minimum weight
! 262: * requirements
! 263: */
! 264: if (this->params->is_product_form)
! 265: {
! 266: msg_rep_good = (abs(m1) <= this->params->min_msg_rep_wt);
! 267: }
! 268: else
! 269: {
! 270: msg_rep_good = ntru_check_min_weight(mprime_len, t2,
! 271: this->params->min_msg_rep_wt);
! 272: }
! 273: }
! 274: while (!msg_rep_good);
! 275:
! 276: /* form ciphertext e by adding m' to R mod q */
! 277: for (i = 0; i < mprime_len; i++)
! 278: {
! 279: if (t2[i] == 1)
! 280: {
! 281: t1[i] = (t1[i] + 1) & mod_q_mask;
! 282: }
! 283: else if (t2[i] == 2)
! 284: {
! 285: t1[i] = (t1[i] - 1) & mod_q_mask;
! 286: }
! 287: }
! 288: if (this->params->is_product_form)
! 289: {
! 290: t1[i] = (t1[i] - m1) & mod_q_mask;
! 291: }
! 292:
! 293: /* pack ciphertext */
! 294: *ciphertext = chunk_alloc((this->params->N * this->params->q_bits + 7) / 8);
! 295: ntru_elements_2_octets(this->params->N, t1, this->params->q_bits,
! 296: ciphertext->ptr);
! 297:
! 298: memwipe(t, t_len);
! 299: success = TRUE;
! 300:
! 301: err:
! 302: /* cleanup */
! 303: chunk_clear(&seed);
! 304: free(t);
! 305:
! 306: return success;
! 307: }
! 308: METHOD(ntru_public_key_t, destroy, void,
! 309: private_ntru_public_key_t *this)
! 310: {
! 311: this->drbg->destroy(this->drbg);
! 312: chunk_clear(&this->encoding);
! 313: free(this->pubkey);
! 314: free(this);
! 315: }
! 316:
! 317: /*
! 318: * Described in header.
! 319: */
! 320: ntru_public_key_t *ntru_public_key_create(drbg_t *drbg,
! 321: const ntru_param_set_t *params,
! 322: uint16_t *pubkey)
! 323: {
! 324: private_ntru_public_key_t *this;
! 325: int i;
! 326:
! 327: INIT(this,
! 328: .public = {
! 329: .get_id = _get_id,
! 330: .get_encoding = _get_encoding,
! 331: .encrypt = _encrypt,
! 332: .destroy = _destroy,
! 333: },
! 334: .params = params,
! 335: .pubkey = malloc(params->N * sizeof(uint16_t)),
! 336: .drbg = drbg->get_ref(drbg),
! 337: );
! 338:
! 339: for (i = 0; i < params->N; i++)
! 340: {
! 341: this->pubkey[i] = pubkey[i];
! 342: }
! 343:
! 344: /* generate public key encoding */
! 345: generate_encoding(this);
! 346:
! 347: return &this->public;
! 348: }
! 349:
! 350: /*
! 351: * Described in header.
! 352: */
! 353: ntru_public_key_t *ntru_public_key_create_from_data(drbg_t *drbg,
! 354: chunk_t data)
! 355: {
! 356: private_ntru_public_key_t *this;
! 357: size_t header_len, pubkey_packed_len;
! 358: const ntru_param_set_t *params;
! 359:
! 360: header_len = 2 + NTRU_OID_LEN;
! 361:
! 362: /* check the NTRU public key header format */
! 363: if (data.len < header_len ||
! 364: data.ptr[0] != NTRU_PUBKEY_TAG ||
! 365: data.ptr[1] != NTRU_OID_LEN)
! 366: {
! 367: DBG1(DBG_LIB, "received NTRU public key with invalid header");
! 368: return NULL;
! 369: }
! 370: params = ntru_param_set_get_by_oid(data.ptr + 2);
! 371:
! 372: if (!params)
! 373: {
! 374: DBG1(DBG_LIB, "received NTRU public key with unknown OID");
! 375: return NULL;
! 376: }
! 377:
! 378: pubkey_packed_len = (params->N * params->q_bits + 7) / 8;
! 379:
! 380: if (data.len < header_len + pubkey_packed_len)
! 381: {
! 382: DBG1(DBG_LIB, "received NTRU public key with wrong packed key size");
! 383: return NULL;
! 384: }
! 385:
! 386: INIT(this,
! 387: .public = {
! 388: .get_id = _get_id,
! 389: .get_encoding = _get_encoding,
! 390: .encrypt = _encrypt,
! 391: .destroy = _destroy,
! 392: },
! 393: .params = params,
! 394: .pubkey = malloc(params->N * sizeof(uint16_t)),
! 395: .encoding = chunk_clone(data),
! 396: .drbg = drbg->get_ref(drbg),
! 397: );
! 398:
! 399: /* unpack the encoded public key */
! 400: ntru_octets_2_elements(pubkey_packed_len, data.ptr + header_len,
! 401: params->q_bits, this->pubkey);
! 402:
! 403: return &this->public;
! 404: }
! 405:
! 406: EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_public_key_create_from_data);
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>