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
NEWHOPE_POLY_frombytes(NEWHOPE_POLY * r,const uint8_t * a)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
NEWHOPE_POLY_tobytes(uint8_t * r,const NEWHOPE_POLY * p)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
newhope_poly_uniform(NEWHOPE_POLY * a,const uint8_t * seed)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
NEWHOPE_POLY_noise(NEWHOPE_POLY * r)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
newhope_poly_pointwise(NEWHOPE_POLY * r,const NEWHOPE_POLY * a,const NEWHOPE_POLY * b)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
newhope_poly_add(NEWHOPE_POLY * r,const NEWHOPE_POLY * a,const NEWHOPE_POLY * b)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
NEWHOPE_POLY_noise_ntt(NEWHOPE_POLY * r)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
newhope_poly_invntt(NEWHOPE_POLY * r)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 }
190