Botan 2.19.2
Crypto and TLS for C&
newhope.cpp
Go to the documentation of this file.
1/*
2* NEWHOPE Ring-LWE scheme
3* Based on the public domain reference implementation by the
4* designers (https://github.com/tpoeppelmann/newhope)
5*
6* Further changes
7* (C) 2016 Jack Lloyd
8*
9* Botan is released under the Simplified BSD License (see license.txt)
10*/
11
12#include <botan/newhope.h>
13#include <botan/hash.h>
14#include <botan/rng.h>
15#include <botan/stream_cipher.h>
16#include <botan/loadstor.h>
17
18namespace Botan {
19
20newhope_poly::~newhope_poly()
21 {
22 secure_scrub_memory(coeffs, sizeof(coeffs));
23 }
24
25typedef newhope_poly poly;
26
27namespace {
28
29static const uint16_t PARAM_Q = 12289;
30static const size_t PARAM_N = 1024;
31
32/* Incomplete-reduction routines; for details on allowed input ranges
33 * and produced output ranges, see the description in the paper:
34 * https://cryptojedi.org/papers/#newhope */
35
36inline uint16_t montgomery_reduce(uint32_t a)
37 {
38 const uint32_t qinv = 12287; // -inverse_mod(p,2^18)
39 const uint32_t rlog = 18;
40 const uint32_t rlog_mask = ((1 << rlog) - 1);
41
42 uint32_t u = (a * qinv);
43 u &= rlog_mask;
44 u *= PARAM_Q;
45 u += a;
46 return (u >> rlog);
47 }
48
49inline uint16_t barrett_reduce(uint16_t a)
50 {
51 uint32_t u = (static_cast<uint32_t>(a) * 5) >> 16;
52 u *= PARAM_Q;
53 a = static_cast<uint16_t>(a - u);
54 return a;
55 }
56
57inline void mul_coefficients(uint16_t* poly, const uint16_t* factors)
58 {
59 for(size_t i = 0; i < PARAM_N; i++)
60 {
61 poly[i] = montgomery_reduce(poly[i] * factors[i]);
62 }
63 }
64
65/* GS_bo_to_no; omegas need to be in Montgomery domain */
66inline void ntt(uint16_t* a, const uint16_t* omega)
67 {
68 for(size_t i = 0; i < 10; i+=2)
69 {
70 // Even level
71 size_t distance = static_cast<size_t>(1) << i;
72 for(size_t start = 0; start < distance; start++)
73 {
74 size_t jTwiddle = 0;
75 for(size_t j = start; j < PARAM_N-1; j += 2*distance)
76 {
77 uint16_t W = omega[jTwiddle++];
78 uint16_t temp = a[j];
79 a[j] = (temp + a[j + distance]); // Omit reduction (be lazy)
80 a[j + distance] = montgomery_reduce((W * (static_cast<uint32_t>(temp) + 3*PARAM_Q - a[j + distance])));
81 }
82 }
83
84 // Odd level
85 distance <<= 1;
86 for(size_t start = 0; start < distance; start++)
87 {
88 size_t jTwiddle = 0;
89 for(size_t j = start; j < PARAM_N-1; j += 2*distance)
90 {
91 uint16_t W = omega[jTwiddle++];
92 uint16_t temp = a[j];
93 a[j] = barrett_reduce((temp + a[j + distance]));
94 a[j + distance] = montgomery_reduce((W * (static_cast<uint32_t>(temp) + 3*PARAM_Q - a[j + distance])));
95 }
96 }
97 }
98 }
99
100inline void poly_frombytes(poly* r, const uint8_t* a)
101 {
102 for(size_t i = 0; i < PARAM_N/4; i++)
103 {
104 r->coeffs[4*i+0] = a[7*i+0] | ((static_cast<uint16_t>(a[7*i+1]) & 0x3f) << 8);
105 r->coeffs[4*i+1] = (a[7*i+1] >> 6) | (static_cast<uint16_t>(a[7*i+2]) << 2) | (static_cast<uint16_t>
106 (a[7*i+3] & 0x0f) << 10);
107 r->coeffs[4*i+2] = (a[7*i+3] >> 4) | (static_cast<uint16_t>(a[7*i+4]) << 4) | (static_cast<uint16_t>
108 (a[7*i+5] & 0x03) << 12);
109 r->coeffs[4*i+3] = (a[7*i+5] >> 2) | (static_cast<uint16_t>(a[7*i+6]) << 6);
110 }
111 }
112
113inline void poly_tobytes(uint8_t* r, const poly* p)
114 {
115 for(size_t i = 0; i < PARAM_N/4; i++)
116 {
117 uint16_t t0 = barrett_reduce(p->coeffs[4*i+0]); //Make sure that coefficients have only 14 bits
118 uint16_t t1 = barrett_reduce(p->coeffs[4*i+1]);
119 uint16_t t2 = barrett_reduce(p->coeffs[4*i+2]);
120 uint16_t t3 = barrett_reduce(p->coeffs[4*i+3]);
121
122 uint16_t m;
123 int16_t c;
124
125 m = t0 - PARAM_Q;
126 c = m;
127 c >>= 15;
128 t0 = m ^ ((t0^m)&c); // <Make sure that coefficients are in [0,q]
129
130 m = t1 - PARAM_Q;
131 c = m;
132 c >>= 15;
133 t1 = m ^ ((t1^m)&c); // <Make sure that coefficients are in [0,q]
134
135 m = t2 - PARAM_Q;
136 c = m;
137 c >>= 15;
138 t2 = m ^ ((t2^m)&c); // <Make sure that coefficients are in [0,q]
139
140 m = t3 - PARAM_Q;
141 c = m;
142 c >>= 15;
143 t3 = m ^ ((t3^m)&c); // <Make sure that coefficients are in [0,q]
144
145 r[7*i+0] = t0 & 0xff;
146 r[7*i+1] = static_cast<uint8_t>((t0 >> 8) | (t1 << 6));
147 r[7*i+2] = static_cast<uint8_t>((t1 >> 2));
148 r[7*i+3] = static_cast<uint8_t>((t1 >> 10) | (t2 << 4));
149 r[7*i+4] = static_cast<uint8_t>((t2 >> 4));
150 r[7*i+5] = static_cast<uint8_t>((t2 >> 12) | (t3 << 2));
151 r[7*i+6] = static_cast<uint8_t>((t3 >> 6));
152 }
153 }
154
155inline void poly_getnoise(Botan::RandomNumberGenerator& rng, poly* r)
156 {
157 uint8_t buf[4*PARAM_N];
158
159 rng.randomize(buf, 4*PARAM_N);
160
161 for(size_t i = 0; i < PARAM_N; i++)
162 {
163 const uint32_t t = load_le<uint32_t>(buf, i);
164 uint32_t d = 0;
165 for(size_t j = 0; j < 8; j++)
166 {
167 d += (t >> j) & 0x01010101;
168 }
169 const uint32_t a = ((d >> 8) & 0xff) + (d & 0xff);
170 const uint32_t b = (d >> 24) + ((d >> 16) & 0xff);
171 r->coeffs[i] = static_cast<uint16_t>(a + PARAM_Q - b);
172 }
173 }
174
175inline void poly_pointwise(poly* r, const poly* a, const poly* b)
176 {
177 for(size_t i = 0; i < PARAM_N; i++)
178 {
179 const uint16_t t = montgomery_reduce(3186*b->coeffs[i]); /* t is now in Montgomery domain */
180 r->coeffs[i] = montgomery_reduce(a->coeffs[i] * t); /* r->coeffs[i] is back in normal domain */
181 }
182 }
183
184inline void poly_add(poly* r, const poly* a, const poly* b)
185 {
186 for(size_t i = 0; i < PARAM_N; i++)
187 {
188 r->coeffs[i] = barrett_reduce(a->coeffs[i] + b->coeffs[i]);
189 }
190 }
191
192inline void poly_ntt(poly* r)
193 {
194 static const uint16_t omegas_montgomery[PARAM_N/2] =
195 {
196 4075, 6974, 7373, 7965, 3262, 5079, 522, 2169, 6364, 1018, 1041, 8775, 2344,
197 11011, 5574, 1973, 4536, 1050, 6844, 3860, 3818, 6118, 2683, 1190, 4789,
198 7822, 7540, 6752, 5456, 4449, 3789, 12142, 11973, 382, 3988, 468, 6843, 5339,
199 6196, 3710, 11316, 1254, 5435, 10930, 3998, 10256, 10367, 3879, 11889, 1728,
200 6137, 4948, 5862, 6136, 3643, 6874, 8724, 654, 10302, 1702, 7083, 6760, 56,
201 3199, 9987, 605, 11785, 8076, 5594, 9260, 6403, 4782, 6212, 4624, 9026, 8689,
202 4080, 11868, 6221, 3602, 975, 8077, 8851, 9445, 5681, 3477, 1105, 142, 241,
203 12231, 1003, 3532, 5009, 1956, 6008, 11404, 7377, 2049, 10968, 12097, 7591,
204 5057, 3445, 4780, 2920, 7048, 3127, 8120, 11279, 6821, 11502, 8807, 12138,
205 2127, 2839, 3957, 431, 1579, 6383, 9784, 5874, 677, 3336, 6234, 2766, 1323,
206 9115, 12237, 2031, 6956, 6413, 2281, 3969, 3991, 12133, 9522, 4737, 10996,
207 4774, 5429, 11871, 3772, 453, 5908, 2882, 1805, 2051, 1954, 11713, 3963,
208 2447, 6142, 8174, 3030, 1843, 2361, 12071, 2908, 3529, 3434, 3202, 7796,
209 2057, 5369, 11939, 1512, 6906, 10474, 11026, 49, 10806, 5915, 1489, 9789,
210 5942, 10706, 10431, 7535, 426, 8974, 3757, 10314, 9364, 347, 5868, 9551,
211 9634, 6554, 10596, 9280, 11566, 174, 2948, 2503, 6507, 10723, 11606, 2459,
212 64, 3656, 8455, 5257, 5919, 7856, 1747, 9166, 5486, 9235, 6065, 835, 3570,
213 4240, 11580, 4046, 10970, 9139, 1058, 8210, 11848, 922, 7967, 1958, 10211,
214 1112, 3728, 4049, 11130, 5990, 1404, 325, 948, 11143, 6190, 295, 11637, 5766,
215 8212, 8273, 2919, 8527, 6119, 6992, 8333, 1360, 2555, 6167, 1200, 7105, 7991,
216 3329, 9597, 12121, 5106, 5961, 10695, 10327, 3051, 9923, 4896, 9326, 81,
217 3091, 1000, 7969, 4611, 726, 1853, 12149, 4255, 11112, 2768, 10654, 1062,
218 2294, 3553, 4805, 2747, 4846, 8577, 9154, 1170, 2319, 790, 11334, 9275, 9088,
219 1326, 5086, 9094, 6429, 11077, 10643, 3504, 3542, 8668, 9744, 1479, 1, 8246,
220 7143, 11567, 10984, 4134, 5736, 4978, 10938, 5777, 8961, 4591, 5728, 6461,
221 5023, 9650, 7468, 949, 9664, 2975, 11726, 2744, 9283, 10092, 5067, 12171,
222 2476, 3748, 11336, 6522, 827, 9452, 5374, 12159, 7935, 3296, 3949, 9893,
223 4452, 10908, 2525, 3584, 8112, 8011, 10616, 4989, 6958, 11809, 9447, 12280,
224 1022, 11950, 9821, 11745, 5791, 5092, 2089, 9005, 2881, 3289, 2013, 9048,
225 729, 7901, 1260, 5755, 4632, 11955, 2426, 10593, 1428, 4890, 5911, 3932,
226 9558, 8830, 3637, 5542, 145, 5179, 8595, 3707, 10530, 355, 3382, 4231, 9741,
227 1207, 9041, 7012, 1168, 10146, 11224, 4645, 11885, 10911, 10377, 435, 7952,
228 4096, 493, 9908, 6845, 6039, 2422, 2187, 9723, 8643, 9852, 9302, 6022, 7278,
229 1002, 4284, 5088, 1607, 7313, 875, 8509, 9430, 1045, 2481, 5012, 7428, 354,
230 6591, 9377, 11847, 2401, 1067, 7188, 11516, 390, 8511, 8456, 7270, 545, 8585,
231 9611, 12047, 1537, 4143, 4714, 4885, 1017, 5084, 1632, 3066, 27, 1440, 8526,
232 9273, 12046, 11618, 9289, 3400, 9890, 3136, 7098, 8758, 11813, 7384, 3985,
233 11869, 6730, 10745, 10111, 2249, 4048, 2884, 11136, 2126, 1630, 9103, 5407,
234 2686, 9042, 2969, 8311, 9424, 9919, 8779, 5332, 10626, 1777, 4654, 10863,
235 7351, 3636, 9585, 5291, 8374, 2166, 4919, 12176, 9140, 12129, 7852, 12286,
236 4895, 10805, 2780, 5195, 2305, 7247, 9644, 4053, 10600, 3364, 3271, 4057,
237 4414, 9442, 7917, 2174
238 };
239
240 static const uint16_t psis_bitrev_montgomery[PARAM_N] =
241 {
242 4075, 6974, 7373, 7965, 3262, 5079, 522, 2169, 6364, 1018, 1041, 8775, 2344,
243 11011, 5574, 1973, 4536, 1050, 6844, 3860, 3818, 6118, 2683, 1190, 4789,
244 7822, 7540, 6752, 5456, 4449, 3789, 12142, 11973, 382, 3988, 468, 6843, 5339,
245 6196, 3710, 11316, 1254, 5435, 10930, 3998, 10256, 10367, 3879, 11889, 1728,
246 6137, 4948, 5862, 6136, 3643, 6874, 8724, 654, 10302, 1702, 7083, 6760, 56,
247 3199, 9987, 605, 11785, 8076, 5594, 9260, 6403, 4782, 6212, 4624, 9026, 8689,
248 4080, 11868, 6221, 3602, 975, 8077, 8851, 9445, 5681, 3477, 1105, 142, 241,
249 12231, 1003, 3532, 5009, 1956, 6008, 11404, 7377, 2049, 10968, 12097, 7591,
250 5057, 3445, 4780, 2920, 7048, 3127, 8120, 11279, 6821, 11502, 8807, 12138,
251 2127, 2839, 3957, 431, 1579, 6383, 9784, 5874, 677, 3336, 6234, 2766, 1323,
252 9115, 12237, 2031, 6956, 6413, 2281, 3969, 3991, 12133, 9522, 4737, 10996,
253 4774, 5429, 11871, 3772, 453, 5908, 2882, 1805, 2051, 1954, 11713, 3963,
254 2447, 6142, 8174, 3030, 1843, 2361, 12071, 2908, 3529, 3434, 3202, 7796,
255 2057, 5369, 11939, 1512, 6906, 10474, 11026, 49, 10806, 5915, 1489, 9789,
256 5942, 10706, 10431, 7535, 426, 8974, 3757, 10314, 9364, 347, 5868, 9551,
257 9634, 6554, 10596, 9280, 11566, 174, 2948, 2503, 6507, 10723, 11606, 2459,
258 64, 3656, 8455, 5257, 5919, 7856, 1747, 9166, 5486, 9235, 6065, 835, 3570,
259 4240, 11580, 4046, 10970, 9139, 1058, 8210, 11848, 922, 7967, 1958, 10211,
260 1112, 3728, 4049, 11130, 5990, 1404, 325, 948, 11143, 6190, 295, 11637, 5766,
261 8212, 8273, 2919, 8527, 6119, 6992, 8333, 1360, 2555, 6167, 1200, 7105, 7991,
262 3329, 9597, 12121, 5106, 5961, 10695, 10327, 3051, 9923, 4896, 9326, 81,
263 3091, 1000, 7969, 4611, 726, 1853, 12149, 4255, 11112, 2768, 10654, 1062,
264 2294, 3553, 4805, 2747, 4846, 8577, 9154, 1170, 2319, 790, 11334, 9275, 9088,
265 1326, 5086, 9094, 6429, 11077, 10643, 3504, 3542, 8668, 9744, 1479, 1, 8246,
266 7143, 11567, 10984, 4134, 5736, 4978, 10938, 5777, 8961, 4591, 5728, 6461,
267 5023, 9650, 7468, 949, 9664, 2975, 11726, 2744, 9283, 10092, 5067, 12171,
268 2476, 3748, 11336, 6522, 827, 9452, 5374, 12159, 7935, 3296, 3949, 9893,
269 4452, 10908, 2525, 3584, 8112, 8011, 10616, 4989, 6958, 11809, 9447, 12280,
270 1022, 11950, 9821, 11745, 5791, 5092, 2089, 9005, 2881, 3289, 2013, 9048,
271 729, 7901, 1260, 5755, 4632, 11955, 2426, 10593, 1428, 4890, 5911, 3932,
272 9558, 8830, 3637, 5542, 145, 5179, 8595, 3707, 10530, 355, 3382, 4231, 9741,
273 1207, 9041, 7012, 1168, 10146, 11224, 4645, 11885, 10911, 10377, 435, 7952,
274 4096, 493, 9908, 6845, 6039, 2422, 2187, 9723, 8643, 9852, 9302, 6022, 7278,
275 1002, 4284, 5088, 1607, 7313, 875, 8509, 9430, 1045, 2481, 5012, 7428, 354,
276 6591, 9377, 11847, 2401, 1067, 7188, 11516, 390, 8511, 8456, 7270, 545, 8585,
277 9611, 12047, 1537, 4143, 4714, 4885, 1017, 5084, 1632, 3066, 27, 1440, 8526,
278 9273, 12046, 11618, 9289, 3400, 9890, 3136, 7098, 8758, 11813, 7384, 3985,
279 11869, 6730, 10745, 10111, 2249, 4048, 2884, 11136, 2126, 1630, 9103, 5407,
280 2686, 9042, 2969, 8311, 9424, 9919, 8779, 5332, 10626, 1777, 4654, 10863,
281 7351, 3636, 9585, 5291, 8374, 2166, 4919, 12176, 9140, 12129, 7852, 12286,
282 4895, 10805, 2780, 5195, 2305, 7247, 9644, 4053, 10600, 3364, 3271, 4057,
283 4414, 9442, 7917, 2174, 3947, 11951, 2455, 6599, 10545, 10975, 3654, 2894,
284 7681, 7126, 7287, 12269, 4119, 3343, 2151, 1522, 7174, 7350, 11041, 2442,
285 2148, 5959, 6492, 8330, 8945, 5598, 3624, 10397, 1325, 6565, 1945, 11260,
286 10077, 2674, 3338, 3276, 11034, 506, 6505, 1392, 5478, 8778, 1178, 2776,
287 3408, 10347, 11124, 2575, 9489, 12096, 6092, 10058, 4167, 6085, 923, 11251,
288 11912, 4578, 10669, 11914, 425, 10453, 392, 10104, 8464, 4235, 8761, 7376,
289 2291, 3375, 7954, 8896, 6617, 7790, 1737, 11667, 3982, 9342, 6680, 636, 6825,
290 7383, 512, 4670, 2900, 12050, 7735, 994, 1687, 11883, 7021, 146, 10485, 1403,
291 5189, 6094, 2483, 2054, 3042, 10945, 3981, 10821, 11826, 8882, 8151, 180,
292 9600, 7684, 5219, 10880, 6780, 204, 11232, 2600, 7584, 3121, 3017, 11053,
293 7814, 7043, 4251, 4739, 11063, 6771, 7073, 9261, 2360, 11925, 1928, 11825,
294 8024, 3678, 3205, 3359, 11197, 5209, 8581, 3238, 8840, 1136, 9363, 1826,
295 3171, 4489, 7885, 346, 2068, 1389, 8257, 3163, 4840, 6127, 8062, 8921, 612,
296 4238, 10763, 8067, 125, 11749, 10125, 5416, 2110, 716, 9839, 10584, 11475,
297 11873, 3448, 343, 1908, 4538, 10423, 7078, 4727, 1208, 11572, 3589, 2982,
298 1373, 1721, 10753, 4103, 2429, 4209, 5412, 5993, 9011, 438, 3515, 7228, 1218,
299 8347, 5232, 8682, 1327, 7508, 4924, 448, 1014, 10029, 12221, 4566, 5836,
300 12229, 2717, 1535, 3200, 5588, 5845, 412, 5102, 7326, 3744, 3056, 2528, 7406,
301 8314, 9202, 6454, 6613, 1417, 10032, 7784, 1518, 3765, 4176, 5063, 9828,
302 2275, 6636, 4267, 6463, 2065, 7725, 3495, 8328, 8755, 8144, 10533, 5966,
303 12077, 9175, 9520, 5596, 6302, 8400, 579, 6781, 11014, 5734, 11113, 11164,
304 4860, 1131, 10844, 9068, 8016, 9694, 3837, 567, 9348, 7000, 6627, 7699, 5082,
305 682, 11309, 5207, 4050, 7087, 844, 7434, 3769, 293, 9057, 6940, 9344, 10883,
306 2633, 8190, 3944, 5530, 5604, 3480, 2171, 9282, 11024, 2213, 8136, 3805, 767,
307 12239, 216, 11520, 6763, 10353, 7, 8566, 845, 7235, 3154, 4360, 3285, 10268,
308 2832, 3572, 1282, 7559, 3229, 8360, 10583, 6105, 3120, 6643, 6203, 8536,
309 8348, 6919, 3536, 9199, 10891, 11463, 5043, 1658, 5618, 8787, 5789, 4719,
310 751, 11379, 6389, 10783, 3065, 7806, 6586, 2622, 5386, 510, 7628, 6921, 578,
311 10345, 11839, 8929, 4684, 12226, 7154, 9916, 7302, 8481, 3670, 11066, 2334,
312 1590, 7878, 10734, 1802, 1891, 5103, 6151, 8820, 3418, 7846, 9951, 4693, 417,
313 9996, 9652, 4510, 2946, 5461, 365, 881, 1927, 1015, 11675, 11009, 1371,
314 12265, 2485, 11385, 5039, 6742, 8449, 1842, 12217, 8176, 9577, 4834, 7937,
315 9461, 2643, 11194, 3045, 6508, 4094, 3451, 7911, 11048, 5406, 4665, 3020,
316 6616, 11345, 7519, 3669, 5287, 1790, 7014, 5410, 11038, 11249, 2035, 6125,
317 10407, 4565, 7315, 5078, 10506, 2840, 2478, 9270, 4194, 9195, 4518, 7469,
318 1160, 6878, 2730, 10421, 10036, 1734, 3815, 10939, 5832, 10595, 10759, 4423,
319 8420, 9617, 7119, 11010, 11424, 9173, 189, 10080, 10526, 3466, 10588, 7592,
320 3578, 11511, 7785, 9663, 530, 12150, 8957, 2532, 3317, 9349, 10243, 1481,
321 9332, 3454, 3758, 7899, 4218, 2593, 11410, 2276, 982, 6513, 1849, 8494, 9021,
322 4523, 7988, 8, 457, 648, 150, 8000, 2307, 2301, 874, 5650, 170, 9462, 2873,
323 9855, 11498, 2535, 11169, 5808, 12268, 9687, 1901, 7171, 11787, 3846, 1573,
324 6063, 3793, 466, 11259, 10608, 3821, 6320, 4649, 6263, 2929
325 };
326
327 mul_coefficients(r->coeffs, psis_bitrev_montgomery);
328 ntt(r->coeffs, omegas_montgomery);
329 }
330
331inline void bitrev_vector(uint16_t* poly)
332 {
333 static const uint16_t bitrev_table[1024] =
334 {
335 0, 512, 256, 768, 128, 640, 384, 896, 64, 576, 320, 832, 192, 704, 448, 960, 32, 544, 288, 800, 160, 672, 416, 928, 96, 608, 352, 864, 224, 736, 480, 992,
336 16, 528, 272, 784, 144, 656, 400, 912, 80, 592, 336, 848, 208, 720, 464, 976, 48, 560, 304, 816, 176, 688, 432, 944, 112, 624, 368, 880, 240, 752, 496, 1008,
337 8, 520, 264, 776, 136, 648, 392, 904, 72, 584, 328, 840, 200, 712, 456, 968, 40, 552, 296, 808, 168, 680, 424, 936, 104, 616, 360, 872, 232, 744, 488, 1000,
338 24, 536, 280, 792, 152, 664, 408, 920, 88, 600, 344, 856, 216, 728, 472, 984, 56, 568, 312, 824, 184, 696, 440, 952, 120, 632, 376, 888, 248, 760, 504, 1016,
339 4, 516, 260, 772, 132, 644, 388, 900, 68, 580, 324, 836, 196, 708, 452, 964, 36, 548, 292, 804, 164, 676, 420, 932, 100, 612, 356, 868, 228, 740, 484, 996,
340 20, 532, 276, 788, 148, 660, 404, 916, 84, 596, 340, 852, 212, 724, 468, 980, 52, 564, 308, 820, 180, 692, 436, 948, 116, 628, 372, 884, 244, 756, 500, 1012,
341 12, 524, 268, 780, 140, 652, 396, 908, 76, 588, 332, 844, 204, 716, 460, 972, 44, 556, 300, 812, 172, 684, 428, 940, 108, 620, 364, 876, 236, 748, 492, 1004,
342 28, 540, 284, 796, 156, 668, 412, 924, 92, 604, 348, 860, 220, 732, 476, 988, 60, 572, 316, 828, 188, 700, 444, 956, 124, 636, 380, 892, 252, 764, 508, 1020,
343 2, 514, 258, 770, 130, 642, 386, 898, 66, 578, 322, 834, 194, 706, 450, 962, 34, 546, 290, 802, 162, 674, 418, 930, 98, 610, 354, 866, 226, 738, 482, 994,
344 18, 530, 274, 786, 146, 658, 402, 914, 82, 594, 338, 850, 210, 722, 466, 978, 50, 562, 306, 818, 178, 690, 434, 946, 114, 626, 370, 882, 242, 754, 498, 1010,
345 10, 522, 266, 778, 138, 650, 394, 906, 74, 586, 330, 842, 202, 714, 458, 970, 42, 554, 298, 810, 170, 682, 426, 938, 106, 618, 362, 874, 234, 746, 490, 1002,
346 26, 538, 282, 794, 154, 666, 410, 922, 90, 602, 346, 858, 218, 730, 474, 986, 58, 570, 314, 826, 186, 698, 442, 954, 122, 634, 378, 890, 250, 762, 506, 1018,
347 6, 518, 262, 774, 134, 646, 390, 902, 70, 582, 326, 838, 198, 710, 454, 966, 38, 550, 294, 806, 166, 678, 422, 934, 102, 614, 358, 870, 230, 742, 486, 998,
348 22, 534, 278, 790, 150, 662, 406, 918, 86, 598, 342, 854, 214, 726, 470, 982, 54, 566, 310, 822, 182, 694, 438, 950, 118, 630, 374, 886, 246, 758, 502, 1014,
349 14, 526, 270, 782, 142, 654, 398, 910, 78, 590, 334, 846, 206, 718, 462, 974, 46, 558, 302, 814, 174, 686, 430, 942, 110, 622, 366, 878, 238, 750, 494, 1006,
350 30, 542, 286, 798, 158, 670, 414, 926, 94, 606, 350, 862, 222, 734, 478, 990, 62, 574, 318, 830, 190, 702, 446, 958, 126, 638, 382, 894, 254, 766, 510, 1022,
351 1, 513, 257, 769, 129, 641, 385, 897, 65, 577, 321, 833, 193, 705, 449, 961, 33, 545, 289, 801, 161, 673, 417, 929, 97, 609, 353, 865, 225, 737, 481, 993,
352 17, 529, 273, 785, 145, 657, 401, 913, 81, 593, 337, 849, 209, 721, 465, 977, 49, 561, 305, 817, 177, 689, 433, 945, 113, 625, 369, 881, 241, 753, 497, 1009,
353 9, 521, 265, 777, 137, 649, 393, 905, 73, 585, 329, 841, 201, 713, 457, 969, 41, 553, 297, 809, 169, 681, 425, 937, 105, 617, 361, 873, 233, 745, 489, 1001,
354 25, 537, 281, 793, 153, 665, 409, 921, 89, 601, 345, 857, 217, 729, 473, 985, 57, 569, 313, 825, 185, 697, 441, 953, 121, 633, 377, 889, 249, 761, 505, 1017,
355 5, 517, 261, 773, 133, 645, 389, 901, 69, 581, 325, 837, 197, 709, 453, 965, 37, 549, 293, 805, 165, 677, 421, 933, 101, 613, 357, 869, 229, 741, 485, 997,
356 21, 533, 277, 789, 149, 661, 405, 917, 85, 597, 341, 853, 213, 725, 469, 981, 53, 565, 309, 821, 181, 693, 437, 949, 117, 629, 373, 885, 245, 757, 501, 1013,
357 13, 525, 269, 781, 141, 653, 397, 909, 77, 589, 333, 845, 205, 717, 461, 973, 45, 557, 301, 813, 173, 685, 429, 941, 109, 621, 365, 877, 237, 749, 493, 1005,
358 29, 541, 285, 797, 157, 669, 413, 925, 93, 605, 349, 861, 221, 733, 477, 989, 61, 573, 317, 829, 189, 701, 445, 957, 125, 637, 381, 893, 253, 765, 509, 1021,
359 3, 515, 259, 771, 131, 643, 387, 899, 67, 579, 323, 835, 195, 707, 451, 963, 35, 547, 291, 803, 163, 675, 419, 931, 99, 611, 355, 867, 227, 739, 483, 995,
360 19, 531, 275, 787, 147, 659, 403, 915, 83, 595, 339, 851, 211, 723, 467, 979, 51, 563, 307, 819, 179, 691, 435, 947, 115, 627, 371, 883, 243, 755, 499, 1011,
361 11, 523, 267, 779, 139, 651, 395, 907, 75, 587, 331, 843, 203, 715, 459, 971, 43, 555, 299, 811, 171, 683, 427, 939, 107, 619, 363, 875, 235, 747, 491, 1003,
362 27, 539, 283, 795, 155, 667, 411, 923, 91, 603, 347, 859, 219, 731, 475, 987, 59, 571, 315, 827, 187, 699, 443, 955, 123, 635, 379, 891, 251, 763, 507, 1019,
363 7, 519, 263, 775, 135, 647, 391, 903, 71, 583, 327, 839, 199, 711, 455, 967, 39, 551, 295, 807, 167, 679, 423, 935, 103, 615, 359, 871, 231, 743, 487, 999,
364 23, 535, 279, 791, 151, 663, 407, 919, 87, 599, 343, 855, 215, 727, 471, 983, 55, 567, 311, 823, 183, 695, 439, 951, 119, 631, 375, 887, 247, 759, 503, 1015,
365 15, 527, 271, 783, 143, 655, 399, 911, 79, 591, 335, 847, 207, 719, 463, 975, 47, 559, 303, 815, 175, 687, 431, 943, 111, 623, 367, 879, 239, 751, 495, 1007,
366 31, 543, 287, 799, 159, 671, 415, 927, 95, 607, 351, 863, 223, 735, 479, 991, 63, 575, 319, 831, 191, 703, 447, 959, 127, 639, 383, 895, 255, 767, 511, 1023
367 };
368
369 for(size_t i = 0; i < PARAM_N; i++)
370 {
371 const uint16_t r = bitrev_table[i];
372 if(i < r)
373 {
374 const uint16_t tmp = poly[i];
375 poly[i] = poly[r];
376 poly[r] = tmp;
377 }
378 }
379 }
380
381inline void poly_invntt(poly* r)
382 {
383 static const uint16_t omegas_inv_montgomery[PARAM_N/2] =
384 {
385 4075, 5315, 4324, 4916, 10120, 11767, 7210, 9027, 10316, 6715, 1278, 9945,
386 3514, 11248, 11271, 5925, 147, 8500, 7840, 6833, 5537, 4749, 4467, 7500,
387 11099, 9606, 6171, 8471, 8429, 5445, 11239, 7753, 9090, 12233, 5529, 5206,
388 10587, 1987, 11635, 3565, 5415, 8646, 6153, 6427, 7341, 6152, 10561, 400,
389 8410, 1922, 2033, 8291, 1359, 6854, 11035, 973, 8579, 6093, 6950, 5446,
390 11821, 8301, 11907, 316, 52, 3174, 10966, 9523, 6055, 8953, 11612, 6415,
391 2505, 5906, 10710, 11858, 8332, 9450, 10162, 151, 3482, 787, 5468, 1010,
392 4169, 9162, 5241, 9369, 7509, 8844, 7232, 4698, 192, 1321, 10240, 4912, 885,
393 6281, 10333, 7280, 8757, 11286, 58, 12048, 12147, 11184, 8812, 6608, 2844,
394 3438, 4212, 11314, 8687, 6068, 421, 8209, 3600, 3263, 7665, 6077, 7507, 5886,
395 3029, 6695, 4213, 504, 11684, 2302, 1962, 1594, 6328, 7183, 168, 2692, 8960,
396 4298, 5184, 11089, 6122, 9734, 10929, 3956, 5297, 6170, 3762, 9370, 4016,
397 4077, 6523, 652, 11994, 6099, 1146, 11341, 11964, 10885, 6299, 1159, 8240,
398 8561, 11177, 2078, 10331, 4322, 11367, 441, 4079, 11231, 3150, 1319, 8243,
399 709, 8049, 8719, 11454, 6224, 3054, 6803, 3123, 10542, 4433, 6370, 7032,
400 3834, 8633, 12225, 9830, 683, 1566, 5782, 9786, 9341, 12115, 723, 3009, 1693,
401 5735, 2655, 2738, 6421, 11942, 2925, 1975, 8532, 3315, 11863, 4754, 1858,
402 1583, 6347, 2500, 10800, 6374, 1483, 12240, 1263, 1815, 5383, 10777, 350,
403 6920, 10232, 4493, 9087, 8855, 8760, 9381, 218, 9928, 10446, 9259, 4115,
404 6147, 9842, 8326, 576, 10335, 10238, 10484, 9407, 6381, 11836, 8517, 418,
405 6860, 7515, 1293, 7552, 2767, 156, 8298, 8320, 10008, 5876, 5333, 10258,
406 10115, 4372, 2847, 7875, 8232, 9018, 8925, 1689, 8236, 2645, 5042, 9984,
407 7094, 9509, 1484, 7394, 3, 4437, 160, 3149, 113, 7370, 10123, 3915, 6998,
408 2704, 8653, 4938, 1426, 7635, 10512, 1663, 6957, 3510, 2370, 2865, 3978,
409 9320, 3247, 9603, 6882, 3186, 10659, 10163, 1153, 9405, 8241, 10040, 2178,
410 1544, 5559, 420, 8304, 4905, 476, 3531, 5191, 9153, 2399, 8889, 3000, 671,
411 243, 3016, 3763, 10849, 12262, 9223, 10657, 7205, 11272, 7404, 7575, 8146,
412 10752, 242, 2678, 3704, 11744, 5019, 3833, 3778, 11899, 773, 5101, 11222,
413 9888, 442, 2912, 5698, 11935, 4861, 7277, 9808, 11244, 2859, 3780, 11414,
414 4976, 10682, 7201, 8005, 11287, 5011, 6267, 2987, 2437, 3646, 2566, 10102,
415 9867, 6250, 5444, 2381, 11796, 8193, 4337, 11854, 1912, 1378, 404, 7644,
416 1065, 2143, 11121, 5277, 3248, 11082, 2548, 8058, 8907, 11934, 1759, 8582,
417 3694, 7110, 12144, 6747, 8652, 3459, 2731, 8357, 6378, 7399, 10861, 1696,
418 9863, 334, 7657, 6534, 11029, 4388, 11560, 3241, 10276, 9000, 9408, 3284,
419 10200, 7197, 6498, 544, 2468, 339, 11267, 9, 2842, 480, 5331, 7300, 1673,
420 4278, 4177, 8705, 9764, 1381, 7837, 2396, 8340, 8993, 4354, 130, 6915, 2837,
421 11462, 5767, 953, 8541, 9813, 118, 7222, 2197, 3006, 9545, 563, 9314, 2625,
422 11340, 4821, 2639, 7266, 5828, 6561, 7698, 3328, 6512, 1351, 7311, 6553,
423 8155, 1305, 722, 5146, 4043, 12288, 10810, 2545, 3621, 8747, 8785, 1646,
424 1212, 5860, 3195, 7203, 10963, 3201, 3014, 955, 11499, 9970, 11119, 3135,
425 3712, 7443, 9542, 7484, 8736, 9995, 11227, 1635, 9521, 1177, 8034, 140,
426 10436, 11563, 7678, 4320, 11289, 9198, 12208, 2963, 7393, 2366, 9238
427 };
428
429 static const uint16_t psis_inv_montgomery[PARAM_N] =
430 {
431 256, 10570, 1510, 7238, 1034, 7170, 6291, 7921, 11665, 3422, 4000, 2327,
432 2088, 5565, 795, 10647, 1521, 5484, 2539, 7385, 1055, 7173, 8047, 11683,
433 1669, 1994, 3796, 5809, 4341, 9398, 11876, 12230, 10525, 12037, 12253, 3506,
434 4012, 9351, 4847, 2448, 7372, 9831, 3160, 2207, 5582, 2553, 7387, 6322, 9681,
435 1383, 10731, 1533, 219, 5298, 4268, 7632, 6357, 9686, 8406, 4712, 9451,
436 10128, 4958, 5975, 11387, 8649, 11769, 6948, 11526, 12180, 1740, 10782, 6807,
437 2728, 7412, 4570, 4164, 4106, 11120, 12122, 8754, 11784, 3439, 5758, 11356,
438 6889, 9762, 11928, 1704, 1999, 10819, 12079, 12259, 7018, 11536, 1648, 1991,
439 2040, 2047, 2048, 10826, 12080, 8748, 8272, 8204, 1172, 1923, 7297, 2798,
440 7422, 6327, 4415, 7653, 6360, 11442, 12168, 7005, 8023, 9924, 8440, 8228,
441 2931, 7441, 1063, 3663, 5790, 9605, 10150, 1450, 8985, 11817, 10466, 10273,
442 12001, 3470, 7518, 1074, 1909, 7295, 9820, 4914, 702, 5367, 7789, 8135, 9940,
443 1420, 3714, 11064, 12114, 12264, 1752, 5517, 9566, 11900, 1700, 3754, 5803,
444 829, 1874, 7290, 2797, 10933, 5073, 7747, 8129, 6428, 6185, 11417, 1631, 233,
445 5300, 9535, 10140, 11982, 8734, 8270, 2937, 10953, 8587, 8249, 2934, 9197,
446 4825, 5956, 4362, 9401, 1343, 3703, 529, 10609, 12049, 6988, 6265, 895, 3639,
447 4031, 4087, 4095, 585, 10617, 8539, 4731, 4187, 9376, 3095, 9220, 10095,
448 10220, 1460, 10742, 12068, 1724, 5513, 11321, 6884, 2739, 5658, 6075, 4379,
449 11159, 10372, 8504, 4726, 9453, 3106, 7466, 11600, 10435, 8513, 9994, 8450,
450 9985, 3182, 10988, 8592, 2983, 9204, 4826, 2445, 5616, 6069, 867, 3635, 5786,
451 11360, 5134, 2489, 10889, 12089, 1727, 7269, 2794, 9177, 1311, 5454, 9557,
452 6632, 2703, 9164, 10087, 1441, 3717, 531, 3587, 2268, 324, 5313, 759, 1864,
453 5533, 2546, 7386, 9833, 8427, 4715, 11207, 1601, 7251, 4547, 11183, 12131,
454 1733, 10781, 10318, 1474, 10744, 5046, 4232, 11138, 10369, 6748, 964, 7160,
455 4534, 7670, 8118, 8182, 4680, 11202, 6867, 981, 8918, 1274, 182, 26, 7026,
456 8026, 11680, 12202, 10521, 1503, 7237, 4545, 5916, 9623, 8397, 11733, 10454,
457 3249, 9242, 6587, 941, 1890, 270, 10572, 6777, 9746, 6659, 6218, 6155, 6146,
458 878, 1881, 7291, 11575, 12187, 1741, 7271, 8061, 11685, 6936, 4502, 9421,
459 4857, 4205, 7623, 1089, 10689, 1527, 8996, 10063, 11971, 10488, 6765, 2722,
460 3900, 9335, 11867, 6962, 11528, 5158, 4248, 4118, 5855, 2592, 5637, 6072,
461 2623, 7397, 8079, 9932, 4930, 5971, 853, 3633, 519, 8852, 11798, 3441, 11025,
462 1575, 225, 8810, 11792, 12218, 3501, 9278, 3081, 9218, 4828, 7712, 8124,
463 11694, 12204, 3499, 4011, 573, 3593, 5780, 7848, 9899, 10192, 1456, 208,
464 7052, 2763, 7417, 11593, 10434, 12024, 8740, 11782, 10461, 3250, 5731, 7841,
465 9898, 1414, 202, 3540, 7528, 2831, 2160, 10842, 5060, 4234, 4116, 588, 84,
466 12, 7024, 2759, 9172, 6577, 11473, 1639, 9012, 3043, 7457, 6332, 11438, 1634,
467 1989, 9062, 11828, 8712, 11778, 12216, 10523, 6770, 9745, 10170, 4964, 9487,
468 6622, 946, 8913, 6540, 6201, 4397, 9406, 8366, 9973, 8447, 8229, 11709, 8695,
469 10020, 3187, 5722, 2573, 10901, 6824, 4486, 4152, 9371, 8361, 2950, 2177,
470 311, 1800, 9035, 8313, 11721, 3430, 490, 70, 10, 1757, 251, 3547, 7529,
471 11609, 3414, 7510, 4584, 4166, 9373, 1339, 5458, 7802, 11648, 1664, 7260,
472 9815, 10180, 6721, 9738, 10169, 8475, 8233, 9954, 1422, 8981, 1283, 5450,
473 11312, 1616, 3742, 11068, 10359, 4991, 713, 3613, 9294, 8350, 4704, 672, 96,
474 7036, 9783, 11931, 3460, 5761, 823, 10651, 12055, 10500, 1500, 5481, 783,
475 3623, 11051, 8601, 8251, 8201, 11705, 10450, 5004, 4226, 7626, 2845, 2162,
476 3820, 7568, 9859, 3164, 452, 10598, 1514, 5483, 6050, 6131, 4387, 7649, 8115,
477 6426, 918, 8909, 8295, 1185, 5436, 11310, 8638, 1234, 5443, 11311, 5127,
478 2488, 2111, 10835, 5059, 7745, 2862, 3920, 560, 80, 1767, 2008, 3798, 11076,
479 6849, 2734, 10924, 12094, 8750, 1250, 10712, 6797, 971, 7161, 1023, 8924,
480 4786, 7706, 4612, 4170, 7618, 6355, 4419, 5898, 11376, 10403, 10264, 6733,
481 4473, 639, 5358, 2521, 9138, 3061, 5704, 4326, 618, 5355, 765, 5376, 768,
482 7132, 4530, 9425, 3102, 9221, 6584, 11474, 10417, 10266, 12000, 6981, 6264,
483 4406, 2385, 7363, 4563, 4163, 7617, 9866, 3165, 9230, 11852, 10471, 5007,
484 5982, 11388, 5138, 734, 3616, 11050, 12112, 6997, 11533, 12181, 10518, 12036,
485 3475, 2252, 7344, 9827, 4915, 9480, 6621, 4457, 7659, 9872, 6677, 4465, 4149,
486 7615, 4599, 657, 3605, 515, 10607, 6782, 4480, 640, 1847, 3775, 5806, 2585,
487 5636, 9583, 1369, 10729, 8555, 10000, 11962, 5220, 7768, 8132, 8184, 9947,
488 1421, 203, 29, 8782, 11788, 1684, 10774, 10317, 4985, 9490, 8378, 4708,
489 11206, 5112, 5997, 7879, 11659, 12199, 8765, 10030, 4944, 5973, 6120, 6141,
490 6144, 7900, 11662, 1666, 238, 34, 3516, 5769, 9602, 8394, 9977, 6692, 956,
491 10670, 6791, 9748, 11926, 8726, 11780, 5194, 742, 106, 8793, 10034, 3189,
492 10989, 5081, 4237, 5872, 4350, 2377, 10873, 6820, 6241, 11425, 10410, 10265,
493 3222, 5727, 9596, 4882, 2453, 2106, 3812, 11078, 12116, 5242, 4260, 11142,
494 8614, 11764, 12214, 5256, 4262, 4120, 11122, 5100, 11262, 5120, 2487, 5622,
495 9581, 8391, 8221, 2930, 10952, 12098, 6995, 6266, 9673, 4893, 699, 3611,
496 4027, 5842, 11368, 1624, 232, 8811, 8281, 1183, 169, 8802, 3013, 2186, 5579,
497 797, 3625, 4029, 11109, 1587, 7249, 11569, 8675, 6506, 2685, 10917, 12093,
498 12261, 12285, 1755, 7273, 1039, 1904, 272, 3550, 9285, 3082, 5707, 6082,
499 4380, 7648, 11626, 5172, 4250, 9385, 8363, 8217, 4685, 5936, 848, 8899, 6538,
500 934, 1889, 3781, 9318, 10109, 10222, 6727, 961, 5404, 772, 5377, 9546, 8386,
501 1198, 8949, 3034, 2189, 7335, 4559, 5918, 2601, 10905, 5069, 9502, 3113,
502 7467, 8089, 11689, 5181, 9518, 8382, 2953, 3933, 4073, 4093, 7607, 8109,
503 2914, 5683, 4323, 11151, 1593, 10761, 6804, 972, 3650, 2277, 5592, 4310,
504 7638, 9869, 4921, 703, 1856, 9043, 4803, 9464, 1352, 8971, 11815, 5199, 7765,
505 6376, 4422, 7654, 2849, 407, 8836, 6529, 7955, 2892, 9191, 1313, 10721,
506 12065, 12257, 1751, 9028, 8312, 2943, 2176, 3822, 546, 78, 8789, 11789,
507 10462, 12028, 6985, 4509, 9422, 1346, 5459, 4291, 613, 10621, 6784, 9747,
508 3148, 7472, 2823, 5670, 810, 7138, 8042, 4660, 7688, 6365, 6176, 6149, 2634,
509 5643, 9584, 10147, 11983, 5223, 9524, 11894, 10477, 8519, 1217, 3685, 2282,
510 326, 10580, 3267, 7489, 4581, 2410, 5611, 11335, 6886, 8006, 8166, 11700,
511 3427, 11023, 8597, 10006, 3185, 455, 65, 5276, 7776, 4622, 5927, 7869, 9902,
512 11948, 5218, 2501, 5624, 2559, 10899, 1557, 1978, 10816, 10323, 8497, 4725,
513 675, 1852, 10798, 12076, 10503, 3256, 9243, 3076, 2195, 10847, 12083, 10504,
514 12034, 10497
515 };
516
517 bitrev_vector(r->coeffs);
518 ntt(r->coeffs, omegas_inv_montgomery);
519 mul_coefficients(r->coeffs, psis_inv_montgomery);
520 }
521
522inline void encode_a(uint8_t* r, const poly* pk, const uint8_t* seed)
523 {
524 poly_tobytes(r, pk);
525 for(size_t i = 0; i < NEWHOPE_SEED_BYTES; i++)
526 {
527 r[NEWHOPE_POLY_BYTES+i] = seed[i];
528 }
529 }
530
531inline void decode_a(poly* pk, uint8_t* seed, const uint8_t* r)
532 {
533 poly_frombytes(pk, r);
534 for(size_t i = 0; i < NEWHOPE_SEED_BYTES; i++)
535 {
536 seed[i] = r[NEWHOPE_POLY_BYTES+i];
537 }
538 }
539
540inline void encode_b(uint8_t* r, const poly* b, const poly* c)
541 {
542 poly_tobytes(r, b);
543 for(size_t i = 0; i < PARAM_N/4; i++)
544 {
545 r[NEWHOPE_POLY_BYTES+i] = static_cast<uint8_t>(c->coeffs[4*i] |
546 (c->coeffs[4*i+1] << 2) |
547 (c->coeffs[4*i+2] << 4) |
548 (c->coeffs[4*i+3] << 6));
549 }
550 }
551
552inline void decode_b(poly* b, poly* c, const uint8_t* r)
553 {
554 poly_frombytes(b, r);
555 for(size_t i = 0; i < PARAM_N/4; i++)
556 {
557 c->coeffs[4*i+0] = r[NEWHOPE_POLY_BYTES+i] & 0x03;
558 c->coeffs[4*i+1] = (r[NEWHOPE_POLY_BYTES+i] >> 2) & 0x03;
559 c->coeffs[4*i+2] = (r[NEWHOPE_POLY_BYTES+i] >> 4) & 0x03;
560 c->coeffs[4*i+3] = (r[NEWHOPE_POLY_BYTES+i] >> 6);
561 }
562 }
563
564inline int32_t ct_abs(int32_t v)
565 {
566 int32_t mask = v >> 31;
567 return (v ^ mask) - mask;
568 }
569
570inline int32_t f(int32_t* v0, int32_t* v1, int32_t x)
571 {
572 int32_t xit, t, r, b;
573
574 // Next 6 lines compute t = x/PARAM_Q;
575 b = x*2730;
576 t = b >> 25;
577 b = x - t*12289;
578 b = 12288 - b;
579 b >>= 31;
580 t -= b;
581
582 r = t & 1;
583 xit = (t>>1);
584 *v0 = xit+r; // v0 = round(x/(2*PARAM_Q))
585
586 t -= 1;
587 r = t & 1;
588 *v1 = (t>>1)+r;
589
590 return ct_abs(x-((*v0)*2*PARAM_Q));
591 }
592
593inline void helprec(poly* c, const poly* v, RandomNumberGenerator& rng)
594 {
595 uint8_t rand[32];
596
597 rng.randomize(rand, 32);
598
599 for(size_t i = 0; i < 256; i++)
600 {
601 int32_t v0[4], v1[4];
602 uint8_t rbit = (rand[i>>3] >> (i&7)) & 1;
603 int32_t k;
604
605 k = f(v0+0, v1+0, 8*v->coeffs[ 0+i] + 4*rbit);
606 k += f(v0+1, v1+1, 8*v->coeffs[256+i] + 4*rbit);
607 k += f(v0+2, v1+2, 8*v->coeffs[512+i] + 4*rbit);
608 k += f(v0+3, v1+3, 8*v->coeffs[768+i] + 4*rbit);
609
610 k = (2*PARAM_Q-1-k) >> 31;
611
612 int32_t v_tmp[4];
613 v_tmp[0] = ((~k) & v0[0]) ^ (k & v1[0]);
614 v_tmp[1] = ((~k) & v0[1]) ^ (k & v1[1]);
615 v_tmp[2] = ((~k) & v0[2]) ^ (k & v1[2]);
616 v_tmp[3] = ((~k) & v0[3]) ^ (k & v1[3]);
617
618 c->coeffs[ 0+i] = (v_tmp[0] - v_tmp[3]) & 3;
619 c->coeffs[256+i] = (v_tmp[1] - v_tmp[3]) & 3;
620 c->coeffs[512+i] = (v_tmp[2] - v_tmp[3]) & 3;
621 c->coeffs[768+i] = (- k + 2*v_tmp[3]) & 3;
622 }
623 }
624
625inline int32_t g(int32_t x)
626 {
627 int32_t t, c, b;
628
629 // Next 6 lines compute t = x/(4*PARAM_Q);
630 b = x*2730;
631 t = b >> 27;
632 b = x - t*49156;
633 b = 49155 - b;
634 b >>= 31;
635 t -= b;
636
637 c = t & 1;
638 t = (t >> 1) + c; // t = round(x/(8*PARAM_Q))
639
640 t *= 8*PARAM_Q;
641
642 return ct_abs(t - x);
643 }
644
645inline int16_t LDDecode(int32_t xi0, int32_t xi1, int32_t xi2, int32_t xi3)
646 {
647 int32_t t;
648
649 t = g(xi0);
650 t += g(xi1);
651 t += g(xi2);
652 t += g(xi3);
653
654 t -= 8*PARAM_Q;
655 t >>= 31;
656 return t&1;
657 }
658
659inline void rec(uint8_t* key, const poly* v, const poly* c)
660 {
661 clear_mem(key, 32);
662
663 for(size_t i = 0; i < 256; i++)
664 {
665 const int32_t tmp0 = 16*PARAM_Q + 8*static_cast<int32_t>(v->coeffs[ 0+i]) - PARAM_Q * (2*c->coeffs[ 0+i]+c->coeffs[768+i]);
666 const int32_t tmp1 = 16*PARAM_Q + 8*static_cast<int32_t>(v->coeffs[256+i]) - PARAM_Q * (2*c->coeffs[256+i]+c->coeffs[768+i]);
667 const int32_t tmp2 = 16*PARAM_Q + 8*static_cast<int32_t>(v->coeffs[512+i]) - PARAM_Q * (2*c->coeffs[512+i]+c->coeffs[768+i]);
668 const int32_t tmp3 = 16*PARAM_Q + 8*static_cast<int32_t>(v->coeffs[768+i]) - PARAM_Q * (c->coeffs[768+i]);
669
670 key[i>>3] |= LDDecode(tmp0, tmp1, tmp2, tmp3) << (i & 7);
671 }
672 }
673
674void gen_a(poly* a, const uint8_t* seed, Newhope_Mode mode)
675 {
676 std::vector<uint8_t> buf(168*16);
677
678 std::unique_ptr<StreamCipher> xof;
679
680 if(mode == Newhope_Mode::BoringSSL)
681 {
682 xof = StreamCipher::create_or_throw("CTR-BE(AES-128)");
683 xof->set_key(seed, 16);
684 xof->set_iv(seed + 16, 16);
685 }
686 else
687 {
688 xof = StreamCipher::create_or_throw("SHAKE-128");
689 xof->set_key(seed, NEWHOPE_SEED_BYTES);
690 }
691
692 zeroise(buf);
693 xof->encrypt(buf);
694
695 size_t pos = 0, ctr = 0;
696
697 while(ctr < PARAM_N)
698 {
699 // Specialized for q = 12889
700 const uint16_t val = (buf[pos] | (static_cast<uint16_t>(buf[pos+1]) << 8)) & 0x3fff;
701
702 if(val < PARAM_Q)
703 {
704 a->coeffs[ctr++] = val;
705 }
706 pos += 2;
707 if(pos >= buf.size())
708 {
709 zeroise(buf);
710 xof->encrypt(buf);
711 pos = 0;
712 }
713 }
714 }
715
716}
717
718// API FUNCTIONS
719
720void newhope_keygen(uint8_t* send, poly* sk, RandomNumberGenerator& rng,
721 Newhope_Mode mode)
722 {
723 poly a, e, r, pk;
724 uint8_t seed[NEWHOPE_SEED_BYTES];
725
726 rng.randomize(seed, NEWHOPE_SEED_BYTES);
727
728 gen_a(&a, seed, mode);
729
730 poly_getnoise(rng, sk);
731 poly_ntt(sk);
732
733 poly_getnoise(rng, &e);
734 poly_ntt(&e);
735
736 poly_pointwise(&r, sk, &a);
737 poly_add(&pk, &e, &r);
738
739 encode_a(send, &pk, seed);
740 }
741
742void newhope_sharedb(uint8_t* sharedkey, uint8_t* send, const uint8_t* received,
743 RandomNumberGenerator& rng,
744 Newhope_Mode mode)
745 {
746 poly sp, ep, v, a, pka, c, epp, bp;
747 uint8_t seed[NEWHOPE_SEED_BYTES];
748
749 decode_a(&pka, seed, received);
750 gen_a(&a, seed, mode);
751
752 poly_getnoise(rng, &sp);
753 poly_ntt(&sp);
754 poly_getnoise(rng, &ep);
755 poly_ntt(&ep);
756
757 poly_pointwise(&bp, &a, &sp);
758 poly_add(&bp, &bp, &ep);
759
760 poly_pointwise(&v, &pka, &sp);
761 poly_invntt(&v);
762
763 poly_getnoise(rng, &epp);
764 poly_add(&v, &v, &epp);
765
766 helprec(&c, &v, rng);
767
768 encode_b(send, &bp, &c);
769
770 rec(sharedkey, &v, &c);
771
772 const std::string kdf_hash = (mode == Newhope_Mode::SHA3) ? "SHA-3(256)" : "SHA-256";
773 std::unique_ptr<HashFunction> hash = HashFunction::create_or_throw(kdf_hash);
774
775 hash->update(sharedkey, 32);
776 hash->final(sharedkey);
777 }
778
779void newhope_shareda(uint8_t sharedkey[],
780 const poly* sk,
781 const uint8_t received[],
782 Newhope_Mode mode)
783 {
784 poly v, bp, c;
785
786 decode_b(&bp, &c, received);
787
788 poly_pointwise(&v, sk, &bp);
789 poly_invntt(&v);
790
791 rec(sharedkey, &v, &c);
792
793 const std::string kdf_hash = (mode == Newhope_Mode::SHA3) ? "SHA-3(256)" : "SHA-256";
794 std::unique_ptr<HashFunction> hash = HashFunction::create_or_throw(kdf_hash);
795
796 hash->update(sharedkey, 32);
797 hash->final(sharedkey);
798 }
799
800}
Botan::HashFunction::create_or_throw
static std::unique_ptr< HashFunction > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: hash.cpp:329
Botan::RandomNumberGenerator::randomize
virtual void randomize(uint8_t output[], size_t length)=0
Botan::StreamCipher::create_or_throw
static std::unique_ptr< StreamCipher > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: stream_cipher.cpp:123
Botan::newhope_poly
Definition: newhope.h:29
Botan::newhope_poly::~newhope_poly
~newhope_poly()
Definition: newhope.cpp:20
Botan::newhope_poly::coeffs
uint16_t coeffs[1024]
Definition: newhope.h:31
Botan
Definition: alg_id.cpp:13
Botan::zeroise
void zeroise(std::vector< T, Alloc > &vec)
Definition: secmem.h:114
Botan::poly
newhope_poly poly
Definition: newhope.cpp:25
Botan::load_le< uint32_t >
uint32_t load_le< uint32_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:198
Botan::Newhope_Mode
Newhope_Mode
Definition: newhope.h:59
Botan::NEWHOPE_POLY_BYTES
@ NEWHOPE_POLY_BYTES
Definition: newhope.h:45
Botan::NEWHOPE_SEED_BYTES
@ NEWHOPE_SEED_BYTES
Definition: newhope.h:44
Botan::secure_scrub_memory
void secure_scrub_memory(void *ptr, size_t n)
Definition: os_utils.cpp:66
Botan::newhope_shareda
void newhope_shareda(uint8_t sharedkey[], const poly *sk, const uint8_t received[], Newhope_Mode mode)
Definition: newhope.cpp:779
Botan::newhope_sharedb
void newhope_sharedb(uint8_t *sharedkey, uint8_t *send, const uint8_t *received, RandomNumberGenerator &rng, Newhope_Mode mode)
Definition: newhope.cpp:742
Botan::newhope_keygen
void newhope_keygen(uint8_t *send, poly *sk, RandomNumberGenerator &rng, Newhope_Mode mode)
Definition: newhope.cpp:720
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
hash
MechanismType hash
Definition: p11_mechanism.cpp:64
Generated by doxygen 1.9.3