diff options
Diffstat (limited to 'crypto/newhope/poly.c')
| -rw-r--r-- | crypto/newhope/poly.c | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/crypto/newhope/poly.c b/crypto/newhope/poly.c new file mode 100644 index 00000000..44cd3839 --- /dev/null +++ b/crypto/newhope/poly.c @@ -0,0 +1,189 @@ +/* Copyright (c) 2016, Google Inc. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ + +#include <assert.h> +#include <string.h> + +#include <openssl/aes.h> +#include <openssl/rand.h> + +#include "internal.h" + + +extern uint16_t newhope_omegas_montgomery[]; +extern uint16_t newhope_omegas_inv_montgomery[]; + +extern uint16_t newhope_psis_bitrev_montgomery[]; +extern uint16_t newhope_psis_inv_montgomery[]; + +void NEWHOPE_POLY_frombytes(NEWHOPE_POLY* r, const uint8_t* a) { + int i; + for (i = 0; i < PARAM_N / 4; i++) { + r->coeffs[4 * i + 0] = + a[7 * i + 0] | (((uint16_t)a[7 * i + 1] & 0x3f) << 8); + r->coeffs[4 * i + 1] = (a[7 * i + 1] >> 6) | + (((uint16_t)a[7 * i + 2]) << 2) | + (((uint16_t)a[7 * i + 3] & 0x0f) << 10); + r->coeffs[4 * i + 2] = (a[7 * i + 3] >> 4) | + (((uint16_t)a[7 * i + 4]) << 4) | + (((uint16_t)a[7 * i + 5] & 0x03) << 12); + r->coeffs[4 * i + 3] = + (a[7 * i + 5] >> 2) | (((uint16_t)a[7 * i + 6]) << 6); + } +} + +void NEWHOPE_POLY_tobytes(uint8_t* r, const NEWHOPE_POLY* p) { + int i; + uint16_t t0, t1, t2, t3, m; + int16_t c; + for (i = 0; i < PARAM_N / 4; i++) { + t0 = newhope_barrett_reduce( + p->coeffs[4 * i + 0]); /* Make sure that coefficients + have only 14 bits */ + t1 = newhope_barrett_reduce(p->coeffs[4 * i + 1]); + t2 = newhope_barrett_reduce(p->coeffs[4 * i + 2]); + t3 = newhope_barrett_reduce(p->coeffs[4 * i + 3]); + + m = t0 - PARAM_Q; + c = m; + c >>= 15; + t0 = m ^ ((t0 ^ m) & c); /* Make sure that coefficients are in [0,q] */ + + m = t1 - PARAM_Q; + c = m; + c >>= 15; + t1 = m ^ ((t1 ^ m) & c); /* <Make sure that coefficients are in [0,q] */ + + m = t2 - PARAM_Q; + c = m; + c >>= 15; + t2 = m ^ ((t2 ^ m) & c); /* <Make sure that coefficients are in [0,q] */ + + m = t3 - PARAM_Q; + c = m; + c >>= 15; + t3 = m ^ ((t3 ^ m) & c); /* Make sure that coefficients are in [0,q] */ + + r[7 * i + 0] = t0 & 0xff; + r[7 * i + 1] = (t0 >> 8) | (t1 << 6); + r[7 * i + 2] = (t1 >> 2); + r[7 * i + 3] = (t1 >> 10) | (t2 << 4); + r[7 * i + 4] = (t2 >> 4); + r[7 * i + 5] = (t2 >> 12) | (t3 << 2); + r[7 * i + 6] = (t3 >> 6); + } +} + +void newhope_poly_uniform(NEWHOPE_POLY* a, const uint8_t* seed) { +/* The reference implementation uses SHAKE-128 here; this implementation uses + * AES-CTR. Use half the seed for the initialization vector and half for the + * key. */ +#if SEED_LENGTH != 2 * AES_BLOCK_SIZE +#error "2 * seed length != AES_BLOCK_SIZE" +#endif + uint8_t ivec[AES_BLOCK_SIZE]; + memcpy(ivec, &seed[SEED_LENGTH / 2], SEED_LENGTH / 2); + AES_KEY key; + AES_set_encrypt_key(seed, 8 * SEED_LENGTH / 2, &key); + + /* AES state. */ + uint8_t ecount[AES_BLOCK_SIZE]; + memset(ecount, 0, AES_BLOCK_SIZE); + + /* Encrypt a block of zeros just to get the random bytes. With luck, 2688 + * bytes is enough. */ + uint8_t buf[AES_BLOCK_SIZE * 168]; + memset(buf, 0, sizeof(buf)); + + unsigned int block_num = 0; + AES_ctr128_encrypt(buf, buf, sizeof(buf), &key, ivec, ecount, &block_num); + + size_t pos = 0, coeff_num = 0; + while (coeff_num < PARAM_N) { + /* Specialized for q = 12889 */ + uint16_t val = (buf[pos] | ((uint16_t)buf[pos + 1] << 8)) & 0x3fff; + if (val < PARAM_Q) { + a->coeffs[coeff_num++] = val; + } + + pos += 2; + if (pos > sizeof(buf) - 2) { + memset(buf, 0, sizeof(buf)); + AES_ctr128_encrypt(buf, buf, sizeof(buf), &key, ivec, ecount, &block_num); + pos = 0; + } + } +} + +void NEWHOPE_POLY_noise(NEWHOPE_POLY* r) { +#if PARAM_K != 16 +#error "poly_getnoise in poly.c only supports k=16" +#endif + + uint32_t tp[PARAM_N]; + + /* The reference implementation calls ChaCha20 here. */ + RAND_bytes((uint8_t *) tp, sizeof(tp)); + + size_t i; + for (i = 0; i < PARAM_N; i++) { + const uint32_t t = tp[i]; + + size_t j; + uint32_t d = 0; + for (j = 0; j < 8; j++) { + d += (t >> j) & 0x01010101; + } + + const uint32_t a = ((d >> 8) & 0xff) + (d & 0xff); + const uint32_t b = (d >> 24) + ((d >> 16) & 0xff); + r->coeffs[i] = a + PARAM_Q - b; + } +} + +void newhope_poly_pointwise(NEWHOPE_POLY* r, const NEWHOPE_POLY* a, + const NEWHOPE_POLY* b) { + size_t i; + for (i = 0; i < PARAM_N; i++) { + uint16_t t = newhope_montgomery_reduce(3186 * b->coeffs[i]); + /* t is now in Montgomery domain */ + r->coeffs[i] = newhope_montgomery_reduce(a->coeffs[i] * t); + /* r->coeffs[i] is back in normal domain */ + } +} + +void newhope_poly_add(NEWHOPE_POLY* r, const NEWHOPE_POLY* a, + const NEWHOPE_POLY* b) { + size_t i; + for (i = 0; i < PARAM_N; i++) { + r->coeffs[i] = newhope_barrett_reduce(a->coeffs[i] + b->coeffs[i]); + } +} + +void NEWHOPE_POLY_noise_ntt(NEWHOPE_POLY* r) { + NEWHOPE_POLY_noise(r); + /* Forward NTT transformation. Because we're operating on a noise polynomial, + * we can regard the bits as already reversed and skip the bit-reversal + * step: + * + * newhope_bitrev_vector(r->coeffs); */ + newhope_mul_coefficients(r->coeffs, newhope_psis_bitrev_montgomery); + newhope_ntt((uint16_t *) r->coeffs, newhope_omegas_montgomery); +} + +void newhope_poly_invntt(NEWHOPE_POLY* r) { + newhope_bitrev_vector(r->coeffs); + newhope_ntt((uint16_t *) r->coeffs, newhope_omegas_inv_montgomery); + newhope_mul_coefficients(r->coeffs, newhope_psis_inv_montgomery); +} |