Botan  2.15.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/rng.h>
15 #include <botan/stream_cipher.h>
16 #include <botan/loadstor.h>
17 
18 namespace Botan {
19 
21  {
23  }
24 
26 
27 namespace {
28 
29 static const uint16_t PARAM_Q = 12289;
30 static 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 
36 inline 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 
49 inline 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 
57 inline 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 */
66 inline 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 = (1ULL << 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 
100 inline 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 
113 inline 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 
155 inline 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 
175 inline 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 
184 inline 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 
192 inline 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 
331 inline 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 
381 inline 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 
522 inline 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 
531 inline 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 
540 inline 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 
552 inline 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 
564 inline int32_t ct_abs(int32_t v)
565  {
566  int32_t mask = v >> 31;
567  return (v ^ mask) - mask;
568  }
569 
570 inline 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 
593 inline 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 
625 inline 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 
645 inline 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 
659 inline 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 
674 void 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 
720 void 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 
742 void newhope_sharedb(uint8_t* sharedkey, uint8_t* send, const uint8_t* received,
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 
779 void 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 }
static std::unique_ptr< HashFunction > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: hash.cpp:344
Newhope_Mode
Definition: newhope.h:58
void newhope_keygen(uint8_t *send, poly *sk, RandomNumberGenerator &rng, Newhope_Mode mode)
Definition: newhope.cpp:720
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
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
uint32_t load_le< uint32_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:198
void newhope_sharedb(uint8_t *sharedkey, uint8_t *send, const uint8_t *received, RandomNumberGenerator &rng, Newhope_Mode mode)
Definition: newhope.cpp:742
Definition: alg_id.cpp:13
void secure_scrub_memory(void *ptr, size_t n)
Definition: os_utils.cpp:66
newhope_poly poly
Definition: newhope.cpp:25
uint16_t coeffs[1024]
Definition: newhope.h:31
MechanismType hash
void newhope_shareda(uint8_t sharedkey[], const poly *sk, const uint8_t received[], Newhope_Mode mode)
Definition: newhope.cpp:779
void zeroise(std::vector< T, Alloc > &vec)
Definition: secmem.h:160