Annotation of embedaddon/strongswan/src/libstrongswan/plugins/ntru/ntru_poly.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_poly.h"
! 19:
! 20: #include <crypto/xofs/xof_bitspender.h>
! 21: #include <utils/debug.h>
! 22: #include <utils/test.h>
! 23:
! 24: typedef struct private_ntru_poly_t private_ntru_poly_t;
! 25: typedef struct indices_len_t indices_len_t;
! 26:
! 27: /**
! 28: * Stores number of +1 and -1 coefficients
! 29: */
! 30: struct indices_len_t {
! 31: int p;
! 32: int m;
! 33: };
! 34:
! 35: /**
! 36: * Private data of an ntru_poly_t object.
! 37: */
! 38: struct private_ntru_poly_t {
! 39:
! 40: /**
! 41: * Public ntru_poly_t interface.
! 42: */
! 43: ntru_poly_t public;
! 44:
! 45: /**
! 46: * Ring dimension equal to the number of polynomial coefficients
! 47: */
! 48: uint16_t N;
! 49:
! 50: /**
! 51: * Large modulus
! 52: */
! 53: uint16_t q;
! 54:
! 55: /**
! 56: * Array containing the indices of the non-zero coefficients
! 57: */
! 58: uint16_t *indices;
! 59:
! 60: /**
! 61: * Number of indices of the non-zero coefficients
! 62: */
! 63: size_t num_indices;
! 64:
! 65: /**
! 66: * Number of sparse polynomials
! 67: */
! 68: int num_polynomials;
! 69:
! 70: /**
! 71: * Number of nonzero coefficients for up to 3 sparse polynomials
! 72: */
! 73: indices_len_t indices_len[3];
! 74:
! 75: };
! 76:
! 77: METHOD(ntru_poly_t, get_size, size_t,
! 78: private_ntru_poly_t *this)
! 79: {
! 80: return this->num_indices;
! 81: }
! 82:
! 83: METHOD(ntru_poly_t, get_indices, uint16_t*,
! 84: private_ntru_poly_t *this)
! 85: {
! 86: return this->indices;
! 87: }
! 88:
! 89: /**
! 90: * Multiplication of polynomial a with a sparse polynomial b given by
! 91: * the indices of its +1 and -1 coefficients results in polynomial c.
! 92: * This is a convolution operation
! 93: */
! 94: static void ring_mult_i(uint16_t *a, indices_len_t len, uint16_t *indices,
! 95: uint16_t N, uint16_t mod_q_mask, uint16_t *t,
! 96: uint16_t *c)
! 97: {
! 98: int i, j, k;
! 99:
! 100: /* initialize temporary array t */
! 101: for (k = 0; k < N; k++)
! 102: {
! 103: t[k] = 0;
! 104: }
! 105:
! 106: /* t[(i+k)%N] = sum i=0 through N-1 of a[i], for b[k] = -1 */
! 107: for (j = len.p; j < len.p + len.m; j++)
! 108: {
! 109: k = indices[j];
! 110: for (i = 0; k < N; ++i, ++k)
! 111: {
! 112: t[k] += a[i];
! 113: }
! 114: for (k = 0; i < N; ++i, ++k)
! 115: {
! 116: t[k] += a[i];
! 117: }
! 118: }
! 119:
! 120: /* t[(i+k)%N] = -(sum i=0 through N-1 of a[i] for b[k] = -1) */
! 121: for (k = 0; k < N; k++)
! 122: {
! 123: t[k] = -t[k];
! 124: }
! 125:
! 126: /* t[(i+k)%N] += sum i=0 through N-1 of a[i] for b[k] = +1 */
! 127: for (j = 0; j < len.p; j++)
! 128: {
! 129: k = indices[j];
! 130: for (i = 0; k < N; ++i, ++k)
! 131: {
! 132: t[k] += a[i];
! 133: }
! 134: for (k = 0; i < N; ++i, ++k)
! 135: {
! 136: t[k] += a[i];
! 137: }
! 138: }
! 139:
! 140: /* c = (a * b) mod q */
! 141: for (k = 0; k < N; k++)
! 142: {
! 143: c[k] = t[k] & mod_q_mask;
! 144: }
! 145: }
! 146:
! 147: METHOD(ntru_poly_t, get_array, void,
! 148: private_ntru_poly_t *this, uint16_t *array)
! 149: {
! 150: uint16_t *t, *bi;
! 151: uint16_t mod_q_mask = this->q - 1;
! 152: indices_len_t len;
! 153: int i;
! 154:
! 155: /* form polynomial F or F1 */
! 156: memset(array, 0x00, this->N * sizeof(uint16_t));
! 157: bi = this->indices;
! 158: len = this->indices_len[0];
! 159: for (i = 0; i < len.p + len.m; i++)
! 160: {
! 161: array[bi[i]] = (i < len.p) ? 1 : mod_q_mask;
! 162: }
! 163:
! 164: if (this->num_polynomials == 3)
! 165: {
! 166: /* allocate temporary array t */
! 167: t = malloc(this->N * sizeof(uint16_t));
! 168:
! 169: /* form F1 * F2 */
! 170: bi += len.p + len.m;
! 171: len = this->indices_len[1];
! 172: ring_mult_i(array, len, bi, this->N, mod_q_mask, t, array);
! 173:
! 174: /* form (F1 * F2) + F3 */
! 175: bi += len.p + len.m;
! 176: len = this->indices_len[2];
! 177: for (i = 0; i < len.p + len.m; i++)
! 178: {
! 179: if (i < len.p)
! 180: {
! 181: array[bi[i]] += 1;
! 182: }
! 183: else
! 184: {
! 185: array[bi[i]] -= 1;
! 186: }
! 187: array[bi[i]] &= mod_q_mask;
! 188: }
! 189: free(t);
! 190: }
! 191: }
! 192:
! 193: METHOD(ntru_poly_t, ring_mult, void,
! 194: private_ntru_poly_t *this, uint16_t *a, uint16_t *c)
! 195: {
! 196: uint16_t *t1, *t2;
! 197: uint16_t *bi = this->indices;
! 198: uint16_t mod_q_mask = this->q - 1;
! 199: int i;
! 200:
! 201: /* allocate temporary array t1 */
! 202: t1 = malloc(this->N * sizeof(uint16_t));
! 203:
! 204: if (this->num_polynomials == 1)
! 205: {
! 206: ring_mult_i(a, this->indices_len[0], bi, this->N, mod_q_mask, t1, c);
! 207: }
! 208: else
! 209: {
! 210: /* allocate temporary array t2 */
! 211: t2 = malloc(this->N * sizeof(uint16_t));
! 212:
! 213: /* t1 = a * b1 */
! 214: ring_mult_i(a, this->indices_len[0], bi, this->N, mod_q_mask, t1, t1);
! 215:
! 216: /* t1 = (a * b1) * b2 */
! 217: bi += this->indices_len[0].p + this->indices_len[0].m;
! 218: ring_mult_i(t1, this->indices_len[1], bi, this->N, mod_q_mask, t2, t1);
! 219:
! 220: /* t2 = a * b3 */
! 221: bi += this->indices_len[1].p + this->indices_len[1].m;
! 222: ring_mult_i(a, this->indices_len[2], bi, this->N, mod_q_mask, t2, t2);
! 223:
! 224: /* c = (a * b1 * b2) + (a * b3) */
! 225: for (i = 0; i < this->N; i++)
! 226: {
! 227: c[i] = (t1[i] + t2[i]) & mod_q_mask;
! 228: }
! 229: free(t2);
! 230: }
! 231: free(t1);
! 232: }
! 233:
! 234: METHOD(ntru_poly_t, destroy, void,
! 235: private_ntru_poly_t *this)
! 236: {
! 237: memwipe(this->indices, sizeof(uint16_t) * get_size(this));
! 238: free(this->indices);
! 239: free(this);
! 240: }
! 241:
! 242: /**
! 243: * Creates an empty ntru_poly_t object with space allocated for indices
! 244: */
! 245: static private_ntru_poly_t* ntru_poly_create(uint16_t N, uint16_t q,
! 246: uint32_t indices_len_p,
! 247: uint32_t indices_len_m,
! 248: bool is_product_form)
! 249: {
! 250: private_ntru_poly_t *this;
! 251: int n;
! 252:
! 253: INIT(this,
! 254: .public = {
! 255: .get_size = _get_size,
! 256: .get_indices = _get_indices,
! 257: .get_array = _get_array,
! 258: .ring_mult = _ring_mult,
! 259: .destroy = _destroy,
! 260: },
! 261: .N = N,
! 262: .q = q,
! 263: );
! 264:
! 265: if (is_product_form)
! 266: {
! 267: this->num_polynomials = 3;
! 268: for (n = 0; n < 3; n++)
! 269: {
! 270: this->indices_len[n].p = 0xff & indices_len_p;
! 271: this->indices_len[n].m = 0xff & indices_len_m;
! 272: this->num_indices += this->indices_len[n].p +
! 273: this->indices_len[n].m;
! 274: indices_len_p >>= 8;
! 275: indices_len_m >>= 8;
! 276: }
! 277: }
! 278: else
! 279: {
! 280: this->num_polynomials = 1;
! 281: this->indices_len[0].p = indices_len_p;
! 282: this->indices_len[0].m = indices_len_m;
! 283: this->num_indices = indices_len_p + indices_len_m;
! 284: }
! 285: this->indices = malloc(sizeof(uint16_t) * this->num_indices);
! 286:
! 287: return this;
! 288: }
! 289:
! 290: /*
! 291: * Described in header.
! 292: */
! 293: ntru_poly_t *ntru_poly_create_from_seed(ext_out_function_t mgf1_type,
! 294: chunk_t seed, uint8_t c_bits,
! 295: uint16_t N, uint16_t q,
! 296: uint32_t indices_len_p,
! 297: uint32_t indices_len_m,
! 298: bool is_product_form)
! 299: {
! 300: private_ntru_poly_t *this;
! 301: int n, num_indices, index_i = 0;
! 302: uint32_t index, limit;
! 303: uint8_t *used;
! 304: xof_bitspender_t *bitspender;
! 305:
! 306: bitspender = xof_bitspender_create(mgf1_type, seed, TRUE);
! 307: if (!bitspender)
! 308: {
! 309: return NULL;
! 310: }
! 311: this = ntru_poly_create(N, q, indices_len_p, indices_len_m, is_product_form);
! 312: used = malloc(N);
! 313: limit = N * ((1 << c_bits) / N);
! 314:
! 315: /* generate indices for all polynomials */
! 316: for (n = 0; n < this->num_polynomials; n++)
! 317: {
! 318: memset(used, 0, N);
! 319: num_indices = this->indices_len[n].p + this->indices_len[n].m;
! 320:
! 321: /* generate indices for a single polynomial */
! 322: while (num_indices)
! 323: {
! 324: /* generate a random candidate index with a size of c_bits */
! 325: do
! 326: {
! 327: if (!bitspender->get_bits(bitspender, c_bits, &index))
! 328: {
! 329: bitspender->destroy(bitspender);
! 330: destroy(this);
! 331: free(used);
! 332: return NULL;
! 333: }
! 334: }
! 335: while (index >= limit);
! 336:
! 337: /* form index and check if unique */
! 338: index %= N;
! 339: if (!used[index])
! 340: {
! 341: used[index] = 1;
! 342: this->indices[index_i++] = index;
! 343: num_indices--;
! 344: }
! 345: }
! 346: }
! 347:
! 348: bitspender->destroy(bitspender);
! 349: free(used);
! 350:
! 351: return &this->public;
! 352: }
! 353:
! 354: /*
! 355: * Described in header.
! 356: */
! 357: ntru_poly_t *ntru_poly_create_from_data(uint16_t *data, uint16_t N, uint16_t q,
! 358: uint32_t indices_len_p,
! 359: uint32_t indices_len_m,
! 360: bool is_product_form)
! 361: {
! 362: private_ntru_poly_t *this;
! 363: int i;
! 364:
! 365: this = ntru_poly_create(N, q, indices_len_p, indices_len_m, is_product_form);
! 366:
! 367: for (i = 0; i < this->num_indices; i++)
! 368: {
! 369: this->indices[i] = data[i];
! 370: }
! 371:
! 372: return &this->public;
! 373: }
! 374:
! 375: EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_seed);
! 376:
! 377: EXPORT_FUNCTION_FOR_TESTS(ntru, ntru_poly_create_from_data);
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ntru_poly.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / ntru