| 1 |
/* Copyright (c) 2016, Google Inc. |
| 2 |
* |
| 3 |
* Permission to use, copy, modify, and/or distribute this software for any |
| 4 |
* purpose with or without fee is hereby granted, provided that the above |
| 5 |
* copyright notice and this permission notice appear in all copies. |
| 6 |
* |
| 7 |
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
| 8 |
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| 9 |
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
| 10 |
* SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| 11 |
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION |
| 12 |
* OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN |
| 13 |
* CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ |
| 14 |
|
| 15 |
#include <assert.h> |
| 16 |
#include <string.h> |
| 17 |
|
| 18 |
#include <openssl/aes.h> |
| 19 |
#include <openssl/rand.h> |
| 20 |
|
| 21 |
#include "internal.h" |
| 22 |
|
| 23 |
|
| 24 |
extern uint16_t newhope_omegas_montgomery[]; |
| 25 |
extern uint16_t newhope_omegas_inv_montgomery[]; |
| 26 |
|
| 27 |
extern uint16_t newhope_psis_bitrev_montgomery[]; |
| 28 |
extern uint16_t newhope_psis_inv_montgomery[]; |
| 29 |
|
| 30 |
void NEWHOPE_POLY_frombytes(NEWHOPE_POLY* r, const uint8_t* a) { |
| 31 |
int i; |
| 32 |
for (i = 0; i < PARAM_N / 4; i++) { |
| 33 |
r->coeffs[4 * i + 0] = |
| 34 |
a[7 * i + 0] | (((uint16_t)a[7 * i + 1] & 0x3f) << 8); |
| 35 |
r->coeffs[4 * i + 1] = (a[7 * i + 1] >> 6) | |
| 36 |
(((uint16_t)a[7 * i + 2]) << 2) | |
| 37 |
(((uint16_t)a[7 * i + 3] & 0x0f) << 10); |
| 38 |
r->coeffs[4 * i + 2] = (a[7 * i + 3] >> 4) | |
| 39 |
(((uint16_t)a[7 * i + 4]) << 4) | |
| 40 |
(((uint16_t)a[7 * i + 5] & 0x03) << 12); |
| 41 |
r->coeffs[4 * i + 3] = |
| 42 |
(a[7 * i + 5] >> 2) | (((uint16_t)a[7 * i + 6]) << 6); |
| 43 |
} |
| 44 |
} |
| 45 |
|
| 46 |
void NEWHOPE_POLY_tobytes(uint8_t* r, const NEWHOPE_POLY* p) { |
| 47 |
int i; |
| 48 |
uint16_t t0, t1, t2, t3, m; |
| 49 |
int16_t c; |
| 50 |
for (i = 0; i < PARAM_N / 4; i++) { |
| 51 |
t0 = newhope_barrett_reduce( |
| 52 |
p->coeffs[4 * i + 0]); /* Make sure that coefficients |
| 53 |
have only 14 bits */ |
| 54 |
t1 = newhope_barrett_reduce(p->coeffs[4 * i + 1]); |
| 55 |
t2 = newhope_barrett_reduce(p->coeffs[4 * i + 2]); |
| 56 |
t3 = newhope_barrett_reduce(p->coeffs[4 * i + 3]); |
| 57 |
|
| 58 |
m = t0 - PARAM_Q; |
| 59 |
c = m; |
| 60 |
c >>= 15; |
| 61 |
t0 = m ^ ((t0 ^ m) & c); /* Make sure that coefficients are in [0,q] */ |
| 62 |
|
| 63 |
m = t1 - PARAM_Q; |
| 64 |
c = m; |
| 65 |
c >>= 15; |
| 66 |
t1 = m ^ ((t1 ^ m) & c); /* <Make sure that coefficients are in [0,q] */ |
| 67 |
|
| 68 |
m = t2 - PARAM_Q; |
| 69 |
c = m; |
| 70 |
c >>= 15; |
| 71 |
t2 = m ^ ((t2 ^ m) & c); /* <Make sure that coefficients are in [0,q] */ |
| 72 |
|
| 73 |
m = t3 - PARAM_Q; |
| 74 |
c = m; |
| 75 |
c >>= 15; |
| 76 |
t3 = m ^ ((t3 ^ m) & c); /* Make sure that coefficients are in [0,q] */ |
| 77 |
|
| 78 |
r[7 * i + 0] = t0 & 0xff; |
| 79 |
r[7 * i + 1] = (t0 >> 8) | (t1 << 6); |
| 80 |
r[7 * i + 2] = (t1 >> 2); |
| 81 |
r[7 * i + 3] = (t1 >> 10) | (t2 << 4); |
| 82 |
r[7 * i + 4] = (t2 >> 4); |
| 83 |
r[7 * i + 5] = (t2 >> 12) | (t3 << 2); |
| 84 |
r[7 * i + 6] = (t3 >> 6); |
| 85 |
} |
| 86 |
} |
| 87 |
|
| 88 |
void newhope_poly_uniform(NEWHOPE_POLY* a, const uint8_t* seed) { |
| 89 |
/* The reference implementation uses SHAKE-128 here; this implementation uses |
| 90 |
* AES-CTR. Use half the seed for the initialization vector and half for the |
| 91 |
* key. */ |
| 92 |
#if SEED_LENGTH != 2 * AES_BLOCK_SIZE |
| 93 |
#error "2 * seed length != AES_BLOCK_SIZE" |
| 94 |
#endif |
| 95 |
uint8_t ivec[AES_BLOCK_SIZE]; |
| 96 |
memcpy(ivec, &seed[SEED_LENGTH / 2], SEED_LENGTH / 2); |
| 97 |
AES_KEY key; |
| 98 |
AES_set_encrypt_key(seed, 8 * SEED_LENGTH / 2, &key); |
| 99 |
|
| 100 |
/* AES state. */ |
| 101 |
uint8_t ecount[AES_BLOCK_SIZE]; |
| 102 |
memset(ecount, 0, AES_BLOCK_SIZE); |
| 103 |
|
| 104 |
/* Encrypt a block of zeros just to get the random bytes. With luck, 2688 |
| 105 |
* bytes is enough. */ |
| 106 |
uint8_t buf[AES_BLOCK_SIZE * 168]; |
| 107 |
memset(buf, 0, sizeof(buf)); |
| 108 |
|
| 109 |
unsigned int block_num = 0; |
| 110 |
AES_ctr128_encrypt(buf, buf, sizeof(buf), &key, ivec, ecount, &block_num); |
| 111 |
|
| 112 |
size_t pos = 0, coeff_num = 0; |
| 113 |
while (coeff_num < PARAM_N) { |
| 114 |
/* Specialized for q = 12889 */ |
| 115 |
uint16_t val = (buf[pos] | ((uint16_t)buf[pos + 1] << 8)) & 0x3fff; |
| 116 |
if (val < PARAM_Q) { |
| 117 |
a->coeffs[coeff_num++] = val; |
| 118 |
} |
| 119 |
|
| 120 |
pos += 2; |
| 121 |
if (pos > sizeof(buf) - 2) { |
| 122 |
memset(buf, 0, sizeof(buf)); |
| 123 |
AES_ctr128_encrypt(buf, buf, sizeof(buf), &key, ivec, ecount, &block_num); |
| 124 |
pos = 0; |
| 125 |
} |
| 126 |
} |
| 127 |
} |
| 128 |
|
| 129 |
void NEWHOPE_POLY_noise(NEWHOPE_POLY* r) { |
| 130 |
#if PARAM_K != 16 |
| 131 |
#error "poly_getnoise in poly.c only supports k=16" |
| 132 |
#endif |
| 133 |
|
| 134 |
uint32_t tp[PARAM_N]; |
| 135 |
|
| 136 |
/* The reference implementation calls ChaCha20 here. */ |
| 137 |
RAND_bytes((uint8_t *) tp, sizeof(tp)); |
| 138 |
|
| 139 |
size_t i; |
| 140 |
for (i = 0; i < PARAM_N; i++) { |
| 141 |
const uint32_t t = tp[i]; |
| 142 |
|
| 143 |
size_t j; |
| 144 |
uint32_t d = 0; |
| 145 |
for (j = 0; j < 8; j++) { |
| 146 |
d += (t >> j) & 0x01010101; |
| 147 |
} |
| 148 |
|
| 149 |
const uint32_t a = ((d >> 8) & 0xff) + (d & 0xff); |
| 150 |
const uint32_t b = (d >> 24) + ((d >> 16) & 0xff); |
| 151 |
r->coeffs[i] = a + PARAM_Q - b; |
| 152 |
} |
| 153 |
} |
| 154 |
|
| 155 |
void newhope_poly_pointwise(NEWHOPE_POLY* r, const NEWHOPE_POLY* a, |
| 156 |
const NEWHOPE_POLY* b) { |
| 157 |
size_t i; |
| 158 |
for (i = 0; i < PARAM_N; i++) { |
| 159 |
uint16_t t = newhope_montgomery_reduce(3186 * b->coeffs[i]); |
| 160 |
/* t is now in Montgomery domain */ |
| 161 |
r->coeffs[i] = newhope_montgomery_reduce(a->coeffs[i] * t); |
| 162 |
/* r->coeffs[i] is back in normal domain */ |
| 163 |
} |
| 164 |
} |
| 165 |
|
| 166 |
void newhope_poly_add(NEWHOPE_POLY* r, const NEWHOPE_POLY* a, |
| 167 |
const NEWHOPE_POLY* b) { |
| 168 |
size_t i; |
| 169 |
for (i = 0; i < PARAM_N; i++) { |
| 170 |
r->coeffs[i] = newhope_barrett_reduce(a->coeffs[i] + b->coeffs[i]); |
| 171 |
} |
| 172 |
} |
| 173 |
|
| 174 |
void NEWHOPE_POLY_noise_ntt(NEWHOPE_POLY* r) { |
| 175 |
NEWHOPE_POLY_noise(r); |
| 176 |
/* Forward NTT transformation. Because we're operating on a noise polynomial, |
| 177 |
* we can regard the bits as already reversed and skip the bit-reversal |
| 178 |
* step: |
| 179 |
* |
| 180 |
* newhope_bitrev_vector(r->coeffs); */ |
| 181 |
newhope_mul_coefficients(r->coeffs, newhope_psis_bitrev_montgomery); |
| 182 |
newhope_ntt((uint16_t *) r->coeffs, newhope_omegas_montgomery); |
| 183 |
} |
| 184 |
|
| 185 |
void newhope_poly_invntt(NEWHOPE_POLY* r) { |
| 186 |
newhope_bitrev_vector(r->coeffs); |
| 187 |
newhope_ntt((uint16_t *) r->coeffs, newhope_omegas_inv_montgomery); |
| 188 |
newhope_mul_coefficients(r->coeffs, newhope_psis_inv_montgomery); |
| 189 |
} |