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