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