Arduino Cryptography Library
NewHope.cpp
1 /*
2  * Copyright (C) 2016 Southern Storm Software, Pty Ltd.
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included
12  * in all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20  * DEALINGS IN THE SOFTWARE.
21  */
22 
23 #include "NewHope.h"
24 #include <Crypto.h>
25 #include <ChaCha.h>
26 #include <SHA3.h>
27 #include <SHAKE.h>
28 #include <RNG.h>
29 #include <string.h>
30 
33 // Older Arduino IDE's don't define placement new. Provide our own definition.
34 void *operator new(size_t size, void *ptr)
35 {
36  return ptr;
37 }
38 
39 #if defined(ESP8266)
40 #include <pgmspace.h>
41 #define table_read(name, index) (pgm_read_word(&((name)[(index)])))
42 #elif defined(__AVR__)
43 #include <avr/pgmspace.h>
44 #define table_read(name, index) (pgm_read_word(&((name)[(index)])))
45 #else
46 #define PROGMEM
47 #define table_read(name, index) ((name)[(index)])
48 #endif
49 
161 typedef struct
162 {
163  uint32_t input[16];
164  uint32_t output[16];
165 
166 } NewHopeChaChaState;
167 
168 // The following is public domain code from the reference C version of
169 // New Hope at https://cryptojedi.org/crypto/#newhope. This part of
170 // the Arduino port remains public domain. Original authors:
171 // Erdem Alkim, Léo Ducas, Thomas Pöppelmann, Peter Schwabe
172 
173 #define PARAM_N 1024
174 #define PARAM_K 16
175 #define PARAM_Q ((int32_t)12289)
176 #define POLY_BYTES 1792
177 #define NEWHOPE_SEEDBYTES 32
178 #define NEWHOPE_RECBYTES 256
179 
180 static uint16_t const omegas_montgomery[PARAM_N/2] PROGMEM = {
181  4075,6974,7373,7965,3262,5079,522,2169,6364,1018,1041,8775,2344,
182  11011,5574,1973,4536,1050,6844,3860,3818,6118,2683,1190,4789,7822,
183  7540,6752,5456,4449,3789,12142,11973,382,3988,468,6843,5339,6196,
184  3710,11316,1254,5435,10930,3998,10256,10367,3879,11889,1728,6137,
185  4948,5862,6136,3643,6874,8724,654,10302,1702,7083,6760,56,3199,9987,
186  605,11785,8076,5594,9260,6403,4782,6212,4624,9026,8689,4080,11868,
187  6221,3602,975,8077,8851,9445,5681,3477,1105,142,241,12231,1003,
188  3532,5009,1956,6008,11404,7377,2049,10968,12097,7591,5057,3445,
189  4780,2920,7048,3127,8120,11279,6821,11502,8807,12138,2127,2839,
190  3957,431,1579,6383,9784,5874,677,3336,6234,2766,1323,9115,12237,
191  2031,6956,6413,2281,3969,3991,12133,9522,4737,10996,4774,5429,11871,
192  3772,453,5908,2882,1805,2051,1954,11713,3963,2447,6142,8174,3030,
193  1843,2361,12071,2908,3529,3434,3202,7796,2057,5369,11939,1512,6906,
194  10474,11026,49,10806,5915,1489,9789,5942,10706,10431,7535,426,8974,
195  3757,10314,9364,347,5868,9551,9634,6554,10596,9280,11566,174,2948,
196  2503,6507,10723,11606,2459,64,3656,8455,5257,5919,7856,1747,9166,
197  5486,9235,6065,835,3570,4240,11580,4046,10970,9139,1058,8210,11848,
198  922,7967,1958,10211,1112,3728,4049,11130,5990,1404,325,948,11143,
199  6190,295,11637,5766,8212,8273,2919,8527,6119,6992,8333,1360,2555,
200  6167,1200,7105,7991,3329,9597,12121,5106,5961,10695,10327,3051,9923,
201  4896,9326,81,3091,1000,7969,4611,726,1853,12149,4255,11112,2768,
202  10654,1062,2294,3553,4805,2747,4846,8577,9154,1170,2319,790,11334,
203  9275,9088,1326,5086,9094,6429,11077,10643,3504,3542,8668,9744,1479,
204  1,8246,7143,11567,10984,4134,5736,4978,10938,5777,8961,4591,5728,
205  6461,5023,9650,7468,949,9664,2975,11726,2744,9283,10092,5067,12171,
206  2476,3748,11336,6522,827,9452,5374,12159,7935,3296,3949,9893,4452,
207  10908,2525,3584,8112,8011,10616,4989,6958,11809,9447,12280,1022,
208  11950,9821,11745,5791,5092,2089,9005,2881,3289,2013,9048,729,7901,
209  1260,5755,4632,11955,2426,10593,1428,4890,5911,3932,9558,8830,3637,
210  5542,145,5179,8595,3707,10530,355,3382,4231,9741,1207,9041,7012,1168,
211  10146,11224,4645,11885,10911,10377,435,7952,4096,493,9908,6845,6039,
212  2422,2187,9723,8643,9852,9302,6022,7278,1002,4284,5088,1607,7313,
213  875,8509,9430,1045,2481,5012,7428,354,6591,9377,11847,2401,1067,
214  7188,11516,390,8511,8456,7270,545,8585,9611,12047,1537,4143,4714,
215  4885,1017,5084,1632,3066,27,1440,8526,9273,12046,11618,9289,3400,
216  9890,3136,7098,8758,11813,7384,3985,11869,6730,10745,10111,2249,
217  4048,2884,11136,2126,1630,9103,5407,2686,9042,2969,8311,9424,
218  9919,8779,5332,10626,1777,4654,10863,7351,3636,9585,5291,8374,
219  2166,4919,12176,9140,12129,7852,12286,4895,10805,2780,5195,2305,
220  7247,9644,4053,10600,3364,3271,4057,4414,9442,7917,2174
221 };
222 
223 static uint16_t const omegas_inv_montgomery[PARAM_N/2] PROGMEM = {
224  4075,5315,4324,4916,10120,11767,7210,9027,10316,6715,1278,9945,
225  3514,11248,11271,5925,147,8500,7840,6833,5537,4749,4467,7500,11099,
226  9606,6171,8471,8429,5445,11239,7753,9090,12233,5529,5206,10587,
227  1987,11635,3565,5415,8646,6153,6427,7341,6152,10561,400,8410,1922,
228  2033,8291,1359,6854,11035,973,8579,6093,6950,5446,11821,8301,11907,
229  316,52,3174,10966,9523,6055,8953,11612,6415,2505,5906,10710,11858,
230  8332,9450,10162,151,3482,787,5468,1010,4169,9162,5241,9369,7509,
231  8844,7232,4698,192,1321,10240,4912,885,6281,10333,7280,8757,11286,
232  58,12048,12147,11184,8812,6608,2844,3438,4212,11314,8687,6068,421,
233  8209,3600,3263,7665,6077,7507,5886,3029,6695,4213,504,11684,2302,
234  1962,1594,6328,7183,168,2692,8960,4298,5184,11089,6122,9734,10929,
235  3956,5297,6170,3762,9370,4016,4077,6523,652,11994,6099,1146,11341,
236  11964,10885,6299,1159,8240,8561,11177,2078,10331,4322,11367,441,
237  4079,11231,3150,1319,8243,709,8049,8719,11454,6224,3054,6803,3123,
238  10542,4433,6370,7032,3834,8633,12225,9830,683,1566,5782,9786,9341,
239  12115,723,3009,1693,5735,2655,2738,6421,11942,2925,1975,8532,3315,
240  11863,4754,1858,1583,6347,2500,10800,6374,1483,12240,1263,1815,
241  5383,10777,350,6920,10232,4493,9087,8855,8760,9381,218,9928,10446,
242  9259,4115,6147,9842,8326,576,10335,10238,10484,9407,6381,11836,8517,
243  418,6860,7515,1293,7552,2767,156,8298,8320,10008,5876,5333,10258,
244  10115,4372,2847,7875,8232,9018,8925,1689,8236,2645,5042,9984,7094,
245  9509,1484,7394,3,4437,160,3149,113,7370,10123,3915,6998,2704,8653,
246  4938,1426,7635,10512,1663,6957,3510,2370,2865,3978,9320,3247,9603,
247  6882,3186,10659,10163,1153,9405,8241,10040,2178,1544,5559,420,8304,
248  4905,476,3531,5191,9153,2399,8889,3000,671,243,3016,3763,10849,12262,
249  9223,10657,7205,11272,7404,7575,8146,10752,242,2678,3704,11744,
250  5019,3833,3778,11899,773,5101,11222,9888,442,2912,5698,11935,4861,
251  7277,9808,11244,2859,3780,11414,4976,10682,7201,8005,11287,5011,
252  6267,2987,2437,3646,2566,10102,9867,6250,5444,2381,11796,8193,4337,
253  11854,1912,1378,404,7644,1065,2143,11121,5277,3248,11082,2548,8058,
254  8907,11934,1759,8582,3694,7110,12144,6747,8652,3459,2731,8357,6378,
255  7399,10861,1696,9863,334,7657,6534,11029,4388,11560,3241,10276,9000,
256  9408,3284,10200,7197,6498,544,2468,339,11267,9,2842,480,5331,7300,
257  1673,4278,4177,8705,9764,1381,7837,2396,8340,8993,4354,130,6915,
258  2837,11462,5767,953,8541,9813,118,7222,2197,3006,9545,563,9314,
259  2625,11340,4821,2639,7266,5828,6561,7698,3328,6512,1351,7311,6553,
260  8155,1305,722,5146,4043,12288,10810,2545,3621,8747,8785,1646,1212,
261  5860,3195,7203,10963,3201,3014,955,11499,9970,11119,3135,3712,7443,
262  9542,7484,8736,9995,11227,1635,9521,1177,8034,140,10436,11563,7678,
263  4320,11289,9198,12208,2963,7393,2366,9238
264 };
265 
266 static uint16_t const psis_bitrev_montgomery[PARAM_N] PROGMEM = {
267  4075,6974,7373,7965,3262,5079,522,2169,6364,1018,1041,8775,2344,
268  11011,5574,1973,4536,1050,6844,3860,3818,6118,2683,1190,4789,7822,
269  7540,6752,5456,4449,3789,12142,11973,382,3988,468,6843,5339,6196,3710,
270  11316,1254,5435,10930,3998,10256,10367,3879,11889,1728,6137,4948,
271  5862,6136,3643,6874,8724,654,10302,1702,7083,6760,56,3199,9987,605,
272  11785,8076,5594,9260,6403,4782,6212,4624,9026,8689,4080,11868,6221,
273  3602,975,8077,8851,9445,5681,3477,1105,142,241,12231,1003,3532,5009,
274  1956,6008,11404,7377,2049,10968,12097,7591,5057,3445,4780,2920,
275  7048,3127,8120,11279,6821,11502,8807,12138,2127,2839,3957,431,1579,
276  6383,9784,5874,677,3336,6234,2766,1323,9115,12237,2031,6956,6413,
277  2281,3969,3991,12133,9522,4737,10996,4774,5429,11871,3772,453,
278  5908,2882,1805,2051,1954,11713,3963,2447,6142,8174,3030,1843,2361,
279  12071,2908,3529,3434,3202,7796,2057,5369,11939,1512,6906,10474,
280  11026,49,10806,5915,1489,9789,5942,10706,10431,7535,426,8974,3757,
281  10314,9364,347,5868,9551,9634,6554,10596,9280,11566,174,2948,2503,
282  6507,10723,11606,2459,64,3656,8455,5257,5919,7856,1747,9166,5486,
283  9235,6065,835,3570,4240,11580,4046,10970,9139,1058,8210,11848,922,
284  7967,1958,10211,1112,3728,4049,11130,5990,1404,325,948,11143,6190,
285  295,11637,5766,8212,8273,2919,8527,6119,6992,8333,1360,2555,6167,
286  1200,7105,7991,3329,9597,12121,5106,5961,10695,10327,3051,9923,
287  4896,9326,81,3091,1000,7969,4611,726,1853,12149,4255,11112,2768,
288  10654,1062,2294,3553,4805,2747,4846,8577,9154,1170,2319,790,11334,
289  9275,9088,1326,5086,9094,6429,11077,10643,3504,3542,8668,9744,1479,
290  1,8246,7143,11567,10984,4134,5736,4978,10938,5777,8961,4591,5728,
291  6461,5023,9650,7468,949,9664,2975,11726,2744,9283,10092,5067,12171,
292  2476,3748,11336,6522,827,9452,5374,12159,7935,3296,3949,9893,4452,
293  10908,2525,3584,8112,8011,10616,4989,6958,11809,9447,12280,1022,
294  11950,9821,11745,5791,5092,2089,9005,2881,3289,2013,9048,729,7901,
295  1260,5755,4632,11955,2426,10593,1428,4890,5911,3932,9558,8830,3637,
296  5542,145,5179,8595,3707,10530,355,3382,4231,9741,1207,9041,7012,
297  1168,10146,11224,4645,11885,10911,10377,435,7952,4096,493,9908,6845,
298  6039,2422,2187,9723,8643,9852,9302,6022,7278,1002,4284,5088,1607,
299  7313,875,8509,9430,1045,2481,5012,7428,354,6591,9377,11847,2401,
300  1067,7188,11516,390,8511,8456,7270,545,8585,9611,12047,1537,4143,
301  4714,4885,1017,5084,1632,3066,27,1440,8526,9273,12046,11618,9289,
302  3400,9890,3136,7098,8758,11813,7384,3985,11869,6730,10745,10111,
303  2249,4048,2884,11136,2126,1630,9103,5407,2686,9042,2969,8311,9424,
304  9919,8779,5332,10626,1777,4654,10863,7351,3636,9585,5291,8374,
305  2166,4919,12176,9140,12129,7852,12286,4895,10805,2780,5195,2305,
306  7247,9644,4053,10600,3364,3271,4057,4414,9442,7917,2174,3947,
307  11951,2455,6599,10545,10975,3654,2894,7681,7126,7287,12269,4119,
308  3343,2151,1522,7174,7350,11041,2442,2148,5959,6492,8330,8945,5598,
309  3624,10397,1325,6565,1945,11260,10077,2674,3338,3276,11034,506,
310  6505,1392,5478,8778,1178,2776,3408,10347,11124,2575,9489,12096,
311  6092,10058,4167,6085,923,11251,11912,4578,10669,11914,425,10453,
312  392,10104,8464,4235,8761,7376,2291,3375,7954,8896,6617,7790,1737,
313  11667,3982,9342,6680,636,6825,7383,512,4670,2900,12050,7735,994,
314  1687,11883,7021,146,10485,1403,5189,6094,2483,2054,3042,10945,
315  3981,10821,11826,8882,8151,180,9600,7684,5219,10880,6780,204,
316  11232,2600,7584,3121,3017,11053,7814,7043,4251,4739,11063,6771,
317  7073,9261,2360,11925,1928,11825,8024,3678,3205,3359,11197,5209,
318  8581,3238,8840,1136,9363,1826,3171,4489,7885,346,2068,1389,8257,
319  3163,4840,6127,8062,8921,612,4238,10763,8067,125,11749,10125,5416,
320  2110,716,9839,10584,11475,11873,3448,343,1908,4538,10423,7078,
321  4727,1208,11572,3589,2982,1373,1721,10753,4103,2429,4209,5412,
322  5993,9011,438,3515,7228,1218,8347,5232,8682,1327,7508,4924,448,
323  1014,10029,12221,4566,5836,12229,2717,1535,3200,5588,5845,412,
324  5102,7326,3744,3056,2528,7406,8314,9202,6454,6613,1417,10032,7784,
325  1518,3765,4176,5063,9828,2275,6636,4267,6463,2065,7725,3495,8328,
326  8755,8144,10533,5966,12077,9175,9520,5596,6302,8400,579,6781,11014,
327  5734,11113,11164,4860,1131,10844,9068,8016,9694,3837,567,9348,7000,
328  6627,7699,5082,682,11309,5207,4050,7087,844,7434,3769,293,9057,
329  6940,9344,10883,2633,8190,3944,5530,5604,3480,2171,9282,11024,2213,
330  8136,3805,767,12239,216,11520,6763,10353,7,8566,845,7235,3154,4360,
331  3285,10268,2832,3572,1282,7559,3229,8360,10583,6105,3120,6643,6203,
332  8536,8348,6919,3536,9199,10891,11463,5043,1658,5618,8787,5789,4719,
333  751,11379,6389,10783,3065,7806,6586,2622,5386,510,7628,6921,578,
334  10345,11839,8929,4684,12226,7154,9916,7302,8481,3670,11066,2334,
335  1590,7878,10734,1802,1891,5103,6151,8820,3418,7846,9951,4693,417,
336  9996,9652,4510,2946,5461,365,881,1927,1015,11675,11009,1371,12265,
337  2485,11385,5039,6742,8449,1842,12217,8176,9577,4834,7937,9461,2643,
338  11194,3045,6508,4094,3451,7911,11048,5406,4665,3020,6616,11345,
339  7519,3669,5287,1790,7014,5410,11038,11249,2035,6125,10407,4565,
340  7315,5078,10506,2840,2478,9270,4194,9195,4518,7469,1160,6878,2730,
341  10421,10036,1734,3815,10939,5832,10595,10759,4423,8420,9617,7119,
342  11010,11424,9173,189,10080,10526,3466,10588,7592,3578,11511,7785,
343  9663,530,12150,8957,2532,3317,9349,10243,1481,9332,3454,3758,7899,
344  4218,2593,11410,2276,982,6513,1849,8494,9021,4523,7988,8,457,648,
345  150,8000,2307,2301,874,5650,170,9462,2873,9855,11498,2535,11169,
346  5808,12268,9687,1901,7171,11787,3846,1573,6063,3793,466,11259,
347  10608,3821,6320,4649,6263,2929
348 };
349 
350 static uint16_t const psis_inv_montgomery[PARAM_N] PROGMEM = {
351  256,10570,1510,7238,1034,7170,6291,7921,11665,3422,4000,2327,
352  2088,5565,795,10647,1521,5484,2539,7385,1055,7173,8047,11683,
353  1669,1994,3796,5809,4341,9398,11876,12230,10525,12037,12253,
354  3506,4012,9351,4847,2448,7372,9831,3160,2207,5582,2553,7387,6322,
355  9681,1383,10731,1533,219,5298,4268,7632,6357,9686,8406,4712,9451,
356  10128,4958,5975,11387,8649,11769,6948,11526,12180,1740,10782,
357  6807,2728,7412,4570,4164,4106,11120,12122,8754,11784,3439,5758,
358  11356,6889,9762,11928,1704,1999,10819,12079,12259,7018,11536,
359  1648,1991,2040,2047,2048,10826,12080,8748,8272,8204,1172,1923,
360  7297,2798,7422,6327,4415,7653,6360,11442,12168,7005,8023,9924,
361  8440,8228,2931,7441,1063,3663,5790,9605,10150,1450,8985,11817,
362  10466,10273,12001,3470,7518,1074,1909,7295,9820,4914,702,5367,
363  7789,8135,9940,1420,3714,11064,12114,12264,1752,5517,9566,11900,
364  1700,3754,5803,829,1874,7290,2797,10933,5073,7747,8129,6428,
365  6185,11417,1631,233,5300,9535,10140,11982,8734,8270,2937,10953,
366  8587,8249,2934,9197,4825,5956,4362,9401,1343,3703,529,10609,
367  12049,6988,6265,895,3639,4031,4087,4095,585,10617,8539,4731,
368  4187,9376,3095,9220,10095,10220,1460,10742,12068,1724,5513,
369  11321,6884,2739,5658,6075,4379,11159,10372,8504,4726,9453,3106,
370  7466,11600,10435,8513,9994,8450,9985,3182,10988,8592,2983,9204,
371  4826,2445,5616,6069,867,3635,5786,11360,5134,2489,10889,12089,
372  1727,7269,2794,9177,1311,5454,9557,6632,2703,9164,10087,1441,
373  3717,531,3587,2268,324,5313,759,1864,5533,2546,7386,9833,8427,
374  4715,11207,1601,7251,4547,11183,12131,1733,10781,10318,1474,
375  10744,5046,4232,11138,10369,6748,964,7160,4534,7670,8118,8182,
376  4680,11202,6867,981,8918,1274,182,26,7026,8026,11680,12202,
377  10521,1503,7237,4545,5916,9623,8397,11733,10454,3249,9242,6587,
378  941,1890,270,10572,6777,9746,6659,6218,6155,6146,878,1881,7291,
379  11575,12187,1741,7271,8061,11685,6936,4502,9421,4857,4205,7623,
380  1089,10689,1527,8996,10063,11971,10488,6765,2722,3900,9335,11867,
381  6962,11528,5158,4248,4118,5855,2592,5637,6072,2623,7397,8079,
382  9932,4930,5971,853,3633,519,8852,11798,3441,11025,1575,225,8810,
383  11792,12218,3501,9278,3081,9218,4828,7712,8124,11694,12204,3499,
384  4011,573,3593,5780,7848,9899,10192,1456,208,7052,2763,7417,11593,
385  10434,12024,8740,11782,10461,3250,5731,7841,9898,1414,202,3540,
386  7528,2831,2160,10842,5060,4234,4116,588,84,12,7024,2759,9172,6577,
387  11473,1639,9012,3043,7457,6332,11438,1634,1989,9062,11828,8712,
388  11778,12216,10523,6770,9745,10170,4964,9487,6622,946,8913,6540,
389  6201,4397,9406,8366,9973,8447,8229,11709,8695,10020,3187,5722,
390  2573,10901,6824,4486,4152,9371,8361,2950,2177,311,1800,9035,
391  8313,11721,3430,490,70,10,1757,251,3547,7529,11609,3414,7510,
392  4584,4166,9373,1339,5458,7802,11648,1664,7260,9815,10180,6721,
393  9738,10169,8475,8233,9954,1422,8981,1283,5450,11312,1616,3742,
394  11068,10359,4991,713,3613,9294,8350,4704,672,96,7036,9783,11931,
395  3460,5761,823,10651,12055,10500,1500,5481,783,3623,11051,8601,
396  8251,8201,11705,10450,5004,4226,7626,2845,2162,3820,7568,9859,
397  3164,452,10598,1514,5483,6050,6131,4387,7649,8115,6426,918,8909,
398  8295,1185,5436,11310,8638,1234,5443,11311,5127,2488,2111,10835,
399  5059,7745,2862,3920,560,80,1767,2008,3798,11076,6849,2734,10924,
400  12094,8750,1250,10712,6797,971,7161,1023,8924,4786,7706,4612,4170,
401  7618,6355,4419,5898,11376,10403,10264,6733,4473,639,5358,2521,
402  9138,3061,5704,4326,618,5355,765,5376,768,7132,4530,9425,3102,
403  9221,6584,11474,10417,10266,12000,6981,6264,4406,2385,7363,4563,
404  4163,7617,9866,3165,9230,11852,10471,5007,5982,11388,5138,734,
405  3616,11050,12112,6997,11533,12181,10518,12036,3475,2252,7344,
406  9827,4915,9480,6621,4457,7659,9872,6677,4465,4149,7615,4599,657,
407  3605,515,10607,6782,4480,640,1847,3775,5806,2585,5636,9583,1369,
408  10729,8555,10000,11962,5220,7768,8132,8184,9947,1421,203,29,8782,
409  11788,1684,10774,10317,4985,9490,8378,4708,11206,5112,5997,7879,
410  11659,12199,8765,10030,4944,5973,6120,6141,6144,7900,11662,1666,
411  238,34,3516,5769,9602,8394,9977,6692,956,10670,6791,9748,11926,
412  8726,11780,5194,742,106,8793,10034,3189,10989,5081,4237,5872,4350,
413  2377,10873,6820,6241,11425,10410,10265,3222,5727,9596,4882,2453,
414  2106,3812,11078,12116,5242,4260,11142,8614,11764,12214,5256,4262,
415  4120,11122,5100,11262,5120,2487,5622,9581,8391,8221,2930,10952,
416  12098,6995,6266,9673,4893,699,3611,4027,5842,11368,1624,232,8811,
417  8281,1183,169,8802,3013,2186,5579,797,3625,4029,11109,1587,7249,
418  11569,8675,6506,2685,10917,12093,12261,12285,1755,7273,1039,1904,
419  272,3550,9285,3082,5707,6082,4380,7648,11626,5172,4250,9385,8363,
420  8217,4685,5936,848,8899,6538,934,1889,3781,9318,10109,10222,6727,
421  961,5404,772,5377,9546,8386,1198,8949,3034,2189,7335,4559,5918,2601,
422  10905,5069,9502,3113,7467,8089,11689,5181,9518,8382,2953,3933,4073,
423  4093,7607,8109,2914,5683,4323,11151,1593,10761,6804,972,3650,2277,
424  5592,4310,7638,9869,4921,703,1856,9043,4803,9464,1352,8971,11815,
425  5199,7765,6376,4422,7654,2849,407,8836,6529,7955,2892,9191,1313,
426  10721,12065,12257,1751,9028,8312,2943,2176,3822,546,78,8789,11789,
427  10462,12028,6985,4509,9422,1346,5459,4291,613,10621,6784,9747,3148,
428  7472,2823,5670,810,7138,8042,4660,7688,6365,6176,6149,2634,5643,
429  9584,10147,11983,5223,9524,11894,10477,8519,1217,3685,2282,326,
430  10580,3267,7489,4581,2410,5611,11335,6886,8006,8166,11700,3427,
431  11023,8597,10006,3185,455,65,5276,7776,4622,5927,7869,9902,11948,
432  5218,2501,5624,2559,10899,1557,1978,10816,10323,8497,4725,675,1852,
433  10798,12076,10503,3256,9243,3076,2195,10847,12083,10504,12034,10497
434 };
435 
436 static uint16_t const bitrev_table[PARAM_N] PROGMEM = {
437  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,
438  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,
439  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,
440  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,
441  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,
442  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,
443  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,
444  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,
445  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,
446  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,
447  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,
448  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,
449  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,
450  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,
451  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,
452  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,
453  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,
454  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,
455  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,
456  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,
457  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,
458  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,
459  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,
460  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,
461  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,
462  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,
463  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,
464  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,
465  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,
466  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,
467  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,
468  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
469 };
470 
471 /* Incomplete-reduction routines; for details on allowed input ranges
472  * and produced output ranges, see the description in the paper:
473  * https://cryptojedi.org/papers/#newhope */
474 
475 #define qinv 12287 // -inverse_mod(p,2^18)
476 #define rlog 18
477 
478 inline uint16_t montgomery_reduce(uint32_t a)
479 {
480  uint32_t u;
481 
482  u = (a * qinv);
483  u &= ((((uint32_t)1)<<rlog)-1);
484  u *= PARAM_Q;
485  a = a + u;
486  return a >> 18;
487 }
488 
489 inline uint16_t barrett_reduce(uint16_t a)
490 {
491  uint32_t u;
492 
493  u = ((uint32_t) a * 5) >> 16;
494  u *= PARAM_Q;
495  a -= u;
496  return a;
497 }
498 
499 static void bitrev_vector(uint16_t* poly)
500 {
501  unsigned int i,r;
502  uint16_t tmp;
503 
504  for(i = 0; i < PARAM_N; i++)
505  {
506  r = table_read(bitrev_table,i);
507  if (i < r)
508  {
509  tmp = poly[i];
510  poly[i] = poly[r];
511  poly[r] = tmp;
512  }
513  }
514 }
515 
516 static void mul_coefficients(uint16_t* poly, const uint16_t* factors)
517 {
518  unsigned int i;
519 
520  for(i = 0; i < PARAM_N; i++)
521  poly[i] = montgomery_reduce((poly[i] * (uint32_t)table_read(factors,i)));
522 }
523 
524 /* GS_bo_to_no; omegas need to be in Montgomery domain */
525 static void ntt(uint16_t * a, const uint16_t* omega)
526 {
527  int i, start, j, jTwiddle, distance;
528  uint16_t temp, W;
529 
530 
531  for(i=0;i<10;i+=2)
532  {
533  // Even level
534  distance = (1<<i);
535  for(start = 0; start < distance;start++)
536  {
537  jTwiddle = 0;
538  for(j=start;j<PARAM_N-1;j+=2*distance)
539  {
540  W = table_read(omega,jTwiddle++);
541  temp = a[j];
542  a[j] = (temp + a[j + distance]); // Omit reduction (be lazy)
543  a[j + distance] = montgomery_reduce((W * ((uint32_t)temp + 3*PARAM_Q - a[j + distance])));
544  }
545  }
546 
547  // Odd level
548  distance <<= 1;
549  for(start = 0; start < distance;start++)
550  {
551  jTwiddle = 0;
552  for(j=start;j<PARAM_N-1;j+=2*distance)
553  {
554  W = table_read(omega,jTwiddle++);
555  temp = a[j];
556  a[j] = barrett_reduce((temp + a[j + distance]));
557  a[j + distance] = montgomery_reduce((W * ((uint32_t)temp + 3*PARAM_Q - a[j + distance])));
558  }
559  }
560  }
561 }
562 
563 static int32_t abs(int32_t v)
564 {
565  int32_t mask = v >> 31;
566  return (v ^ mask) - mask;
567 }
568 
569 static int32_t f(int32_t *v0, int32_t *v1, uint32_t x)
570 {
571  int32_t xit, t, r, b;
572 
573  // Next 6 lines compute t = x/PARAM_Q;
574  b = x*2730;
575  t = b >> 25;
576  b = x - t*12289;
577  b = 12288 - b;
578  b >>= 31;
579  t -= b;
580 
581  r = t & 1;
582  xit = (t>>1);
583  *v0 = xit+r; // v0 = round(x/(2*PARAM_Q))
584 
585  t -= 1;
586  r = t & 1;
587  *v1 = (t>>1)+r;
588 
589  return abs(x-((*v0)*2*PARAM_Q));
590 }
591 
592 static int32_t g(int32_t x)
593 {
594  int32_t t,c,b;
595 
596  // Next 6 lines compute t = x/(4*PARAM_Q);
597  b = x*2730;
598  t = b >> 27;
599  b = x - t*49156;
600  b = 49155 - b;
601  b >>= 31;
602  t -= b;
603 
604  c = t & 1;
605  t = (t >> 1) + c; // t = round(x/(8*PARAM_Q))
606 
607  t *= 8*PARAM_Q;
608 
609  return abs(t - x);
610 }
611 
612 static int16_t LDDecode(int32_t xi0, int32_t xi1, int32_t xi2, int32_t xi3)
613 {
614  int32_t t;
615 
616  t = g(xi0);
617  t += g(xi1);
618  t += g(xi2);
619  t += g(xi3);
620 
621  t -= 8*PARAM_Q;
622  t >>= 31;
623  return t&1;
624 }
625 
626 static void helprec(NewHopeChaChaState *chacha, uint16_t *c, const uint16_t *v, unsigned char nonce)
627 {
628  int32_t v0[4], v1[4], v_tmp[4], k;
629  unsigned char rbit;
630  unsigned char *rand;
631  int i;
632 
633  chacha->input[12] = 0;
634  chacha->input[13] = 0;
635  chacha->input[14] = 0;
636  chacha->input[15] = (((uint32_t)nonce) << 24); // Assumes little-endian.
637  ChaCha::hashCore(chacha->output, chacha->input, 20);
638  rand = (unsigned char *)chacha->output;
639 
640  for(i=0; i<256; i++)
641  {
642  rbit = (rand[i>>3] >> (i&7)) & 1;
643 
644  k = f(v0+0, v1+0, 8*(int32_t)v[ 0+i] + 4*rbit);
645  k += f(v0+1, v1+1, 8*(int32_t)v[256+i] + 4*rbit);
646  k += f(v0+2, v1+2, 8*(int32_t)v[512+i] + 4*rbit);
647  k += f(v0+3, v1+3, 8*(int32_t)v[768+i] + 4*rbit);
648 
649  k = (2*PARAM_Q-1-k) >> 31;
650 
651  v_tmp[0] = ((~k) & v0[0]) ^ (k & v1[0]);
652  v_tmp[1] = ((~k) & v0[1]) ^ (k & v1[1]);
653  v_tmp[2] = ((~k) & v0[2]) ^ (k & v1[2]);
654  v_tmp[3] = ((~k) & v0[3]) ^ (k & v1[3]);
655 
656  c[ 0+i] = (v_tmp[0] - v_tmp[3]) & 3;
657  c[256+i] = (v_tmp[1] - v_tmp[3]) & 3;
658  c[512+i] = (v_tmp[2] - v_tmp[3]) & 3;
659  c[768+i] = ( -k + 2*v_tmp[3]) & 3;
660  }
661 
662  clean(&chacha, sizeof(chacha));
663 }
664 
665 static void rec(unsigned char *key, const uint16_t *v, const uint16_t *c)
666 {
667  int i;
668  int32_t tmp[4];
669 
670  for(i=0;i<32;i++)
671  key[i] = 0;
672 
673  for(i=0; i<256; i++)
674  {
675  tmp[0] = 16*PARAM_Q + 8*(int32_t)v[ 0+i] - PARAM_Q * (2*(int32_t)c[ 0+i]+c[768+i]);
676  tmp[1] = 16*PARAM_Q + 8*(int32_t)v[256+i] - PARAM_Q * (2*(int32_t)c[256+i]+c[768+i]);
677  tmp[2] = 16*PARAM_Q + 8*(int32_t)v[512+i] - PARAM_Q * (2*(int32_t)c[512+i]+c[768+i]);
678  tmp[3] = 16*PARAM_Q + 8*(int32_t)v[768+i] - PARAM_Q * ( c[768+i]);
679 
680  key[i>>3] |= LDDecode(tmp[0], tmp[1], tmp[2], tmp[3]) << (i & 7);
681  }
682 }
683 
684 static void poly_frombytes(uint16_t *r, const unsigned char *a)
685 {
686  int i;
687  for(i=0;i<PARAM_N/4;i++)
688  {
689  r[4*i+0] = a[7*i+0] | (((uint16_t)a[7*i+1] & 0x3f) << 8);
690  r[4*i+1] = (a[7*i+1] >> 6) | (((uint16_t)a[7*i+2]) << 2) | (((uint16_t)a[7*i+3] & 0x0f) << 10);
691  r[4*i+2] = (a[7*i+3] >> 4) | (((uint16_t)a[7*i+4]) << 4) | (((uint16_t)a[7*i+5] & 0x03) << 12);
692  r[4*i+3] = (a[7*i+5] >> 2) | (((uint16_t)a[7*i+6]) << 6);
693  }
694 }
695 
696 static void poly_tobytes(unsigned char *r, const uint16_t *p)
697 {
698  int i;
699  uint16_t t0,t1,t2,t3,m;
700  int16_t c;
701  for(i=0;i<PARAM_N/4;i++)
702  {
703  t0 = barrett_reduce(p[4*i+0]); //Make sure that coefficients have only 14 bits
704  t1 = barrett_reduce(p[4*i+1]);
705  t2 = barrett_reduce(p[4*i+2]);
706  t3 = barrett_reduce(p[4*i+3]);
707 
708  m = t0 - PARAM_Q;
709  c = m;
710  c >>= 15;
711  t0 = m ^ ((t0^m)&c); // <Make sure that coefficients are in [0,q]
712 
713  m = t1 - PARAM_Q;
714  c = m;
715  c >>= 15;
716  t1 = m ^ ((t1^m)&c); // <Make sure that coefficients are in [0,q]
717 
718  m = t2 - PARAM_Q;
719  c = m;
720  c >>= 15;
721  t2 = m ^ ((t2^m)&c); // <Make sure that coefficients are in [0,q]
722 
723  m = t3 - PARAM_Q;
724  c = m;
725  c >>= 15;
726  t3 = m ^ ((t3^m)&c); // <Make sure that coefficients are in [0,q]
727 
728  r[7*i+0] = t0 & 0xff;
729  r[7*i+1] = (t0 >> 8) | (t1 << 6);
730  r[7*i+2] = (t1 >> 2);
731  r[7*i+3] = (t1 >> 10) | (t2 << 4);
732  r[7*i+4] = (t2 >> 4);
733  r[7*i+5] = (t2 >> 12) | (t3 << 2);
734  r[7*i+6] = (t3 >> 6);
735  }
736 }
737 
738 static void poly_pointwise(uint16_t *r, const uint16_t *a, const uint16_t *b)
739 {
740  int i;
741  uint16_t t;
742  for(i=0;i<PARAM_N;i++)
743  {
744  t = montgomery_reduce(3186*(uint32_t)b[i]); /* t is now in Montgomery domain */
745  r[i] = montgomery_reduce(a[i] * (uint32_t)t); /* r->coeffs[i] is back in normal domain */
746  }
747 }
748 
749 static void poly_add(uint16_t *r, const uint16_t *a, const uint16_t *b)
750 {
751  int i;
752  for(i=0;i<PARAM_N;i++)
753  r[i] = barrett_reduce(a[i] + (uint32_t)b[i]);
754 }
755 
756 static void poly_ntt(uint16_t *r)
757 {
758  mul_coefficients(r, psis_bitrev_montgomery);
759  ntt(r, omegas_montgomery);
760 }
761 
762 static void poly_invntt(uint16_t *r)
763 {
764  bitrev_vector(r);
765  ntt(r, omegas_inv_montgomery);
766  mul_coefficients(r, psis_inv_montgomery);
767 }
768 
769 static void encode_b_2nd_half(unsigned char *r, const uint16_t *c)
770 {
771  int i;
772  for(i=0;i<PARAM_N/4;i++)
773  r[POLY_BYTES+i] = c[4*i] | (c[4*i+1] << 2) | (c[4*i+2] << 4) | (c[4*i+3] << 6);
774 }
775 
776 static void decode_b_2nd_half(uint16_t *c, const unsigned char *r)
777 {
778  int i;
779  for(i=0;i<PARAM_N/4;i++)
780  {
781  c[4*i+0] = r[POLY_BYTES+i] & 0x03;
782  c[4*i+1] = (r[POLY_BYTES+i] >> 2) & 0x03;
783  c[4*i+2] = (r[POLY_BYTES+i] >> 4) & 0x03;
784  c[4*i+3] = (r[POLY_BYTES+i] >> 6);
785  }
786 }
787 
788 #define _5q (5*PARAM_Q)
789 
790 #define compare_and_swap(x,i,j) \
791  c = _5q - 1 - x[16*(i)];\
792  c >>= 31;\
793  t = x[16*(i)] ^ x[16*(j)];\
794  t &= c;\
795  x[16*(i)] ^= t;\
796  x[16*(j)] ^= t;
797 
798 static void batcher84(uint16_t *x);
799 
800 static int discardtopoly(uint16_t *x)
801 {
802  int32_t i, r=0;
803 
804  for(i=0;i<16;i++)
805  batcher84(x+i);
806 
807  // Check whether we're safe:
808  for(i=1008;i<1024;i++)
809  r |= 61444 - x[i];
810  if(r >>= 31) return -1;
811 
812  return 0;
813 }
814 
815 // End of public domain code imported from the C reference code.
816 
817 // Code size efficient (but slower) version of the Batcher sort.
818 // https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
819 static void oddeven_merge(uint16_t *x, unsigned lo, unsigned hi, unsigned r)
820 {
821  unsigned step = r * 2;
822  unsigned i;
823  int32_t c;
824  uint16_t t;
825  if (lo >= 84)
826  return;
827  if (step < (hi - lo)) {
828  if ((step * 2) >= (hi - lo) && hi < 84) {
829  // The next recursion down is a leaf, so unroll a little.
830  compare_and_swap(x, lo, lo + step);
831  compare_and_swap(x, lo + r, lo + r + step);
832  compare_and_swap(x, lo + r, lo + step);
833  return;
834  }
835  oddeven_merge(x, lo, hi, step);
836  oddeven_merge(x, lo + r, hi, step);
837  for (i = lo + r; i < (hi - r) && (i + r) < 84; i += step) {
838  compare_and_swap(x, i, i + r);
839  }
840  } else if ((lo + r) < 84) {
841  compare_and_swap(x, lo, lo + r);
842  }
843 }
844 static void oddeven_merge_sort_range(uint16_t *x, unsigned lo, unsigned hi)
845 {
846  if (lo == hi || lo >= 84)
847  return;
848  unsigned mid = lo + ((hi - lo) / 2);
849  if ((hi - lo) == 3 && hi < 84) {
850  // Optimization for sub lists of size 4. Unroll the comparisons.
851  int32_t c;
852  uint16_t t;
853  compare_and_swap(x, lo , lo + 1);
854  compare_and_swap(x, lo + 2, lo + 3);
855  compare_and_swap(x, lo , lo + 2);
856  compare_and_swap(x, lo + 1, lo + 3);
857  compare_and_swap(x, lo + 1, lo + 2);
858  return;
859  }
860  oddeven_merge_sort_range(x, lo, mid);
861  oddeven_merge_sort_range(x, mid + 1, hi);
862  oddeven_merge(x, lo, hi, 1);
863 }
864 static void batcher84(uint16_t *x)
865 {
866  // Batcher sort is defined over a power of two list size but 84
867  // is not a power of two. Round up to the next power of two and
868  // then ignore any swap with an index that is out of range.
869  oddeven_merge_sort_range(x, 0, 127);
870 }
871 
872 // Formats the ChaCha20 input block using a key.
873 static void crypto_chacha20_set_key(uint32_t *block, const unsigned char *k)
874 {
875  static const char tag256[] PROGMEM = "expand 32-byte k";
876 #if defined(__AVR__)
877  memcpy_P(block, tag256, 16);
878 #else
879  memcpy(block, tag256, 16);
880 #endif
881  memcpy(block + 4, k, 32);
882  memset(block + 12, 0, 8);
883 }
884 
885 static void poly_uniform(SHAKE128 *shake, uint16_t *a, const unsigned char *seed)
886 {
887  int ctr = 0;
888  int posn = PARAM_N;
889  uint16_t val;
890 
891  // Absorb the seed material into the SHAKE128 object.
892  shake->update(seed, NEWHOPE_SEEDBYTES);
893 
894  while (ctr < PARAM_N) {
895  // Extract data from the SHAKE128 object directly into "a".
896  if (posn >= PARAM_N) {
897  shake->extend((uint8_t *)(a + ctr),
898  (PARAM_N - ctr) * sizeof(uint16_t));
899  posn = ctr;
900  }
901 
902  // Process as much of the data as we can, discarding values
903  // that are greater than or equal to 5 * PARAM_Q.
904  while (posn < PARAM_N) {
905  val = a[posn++];
906  if (val < (5 * PARAM_Q))
907  a[ctr++] = val;
908  }
909  }
910 }
911 
912 static void poly_uniform_torref(SHAKE128 *shake, uint16_t *a, const unsigned char *seed)
913 {
914  shake->update(seed, 32);
915  do {
916  shake->extend((uint8_t *)a, 84 * 16 * sizeof(uint16_t));
917  } while (discardtopoly(a));
918 }
919 
920 static void poly_getnoise(uint16_t *r, NewHopeChaChaState *chacha, unsigned char nonce)
921 {
922  int i, j;
923  uint32_t a, b;
924 
925  // Note: The rest of this function assumes that we are running on a
926  // little-endian CPU. Since we're generating random noise from a
927  // random seed, it doesn't actually matter what the endian-ness is
928  // as it will be just as random in both directions. It's only a
929  // problem for verifying fixed test vectors.
930 
931  chacha->input[12] = 0;
932  chacha->input[13] = 0;
933  chacha->input[14] = nonce; // Assumes little-endian.
934  chacha->input[15] = 0;
935 
936  for (i = 0; i < PARAM_N; ++i) {
937  // Generate a new block of random data if necessary.
938  j = i % 16;
939  if (j == 0) {
940  ChaCha::hashCore(chacha->output, chacha->input, 20);
941  ++(chacha->input[12]); // Assumes little-endian.
942  }
943 
944  // This is a slightly more efficient way to count bits than in
945  // the reference C implementation. The technique is from:
946  // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
947  a = chacha->output[j] & 0xFFFF; // Assumes little-endian.
948  a = a - ((a >> 1) & 0x5555);
949  a = (a & 0x3333) + ((a >> 2) & 0x3333);
950  a = ((a >> 4) + a) & 0x0F0F;
951  a = ((a >> 8) + a) & 0x00FF;
952 
953  b = (chacha->output[j] >> 16) & 0xFFFF; // Assumes little-endian.
954  b = b - ((b >> 1) & 0x5555);
955  b = (b & 0x3333) + ((b >> 2) & 0x3333);
956  b = ((b >> 4) + b) & 0x0F0F;
957  b = ((b >> 8) + b) & 0x00FF;
958 
959  r[i] = a + PARAM_Q - b;
960  }
961 
962  clean(&chacha, sizeof(chacha));
963 }
964 
987 #define ALLOC_OBJ(type, name) \
988  uint64_t name##_x[(sizeof(type) + sizeof(uint64_t) - 1) / sizeof(uint64_t)]
989 
990 #define INIT_OBJ(type, name) \
991  type *name = new (state.name##_x) type
992 
993 #if defined(ESP8266)
994 // If we try to put the state on the stack, then it causes a stack smash.
995 // Possibly a system stack size limitation. Allocate the NewHope state on
996 // the heap instead for ESP8266.
997 #define NEWHOPE_HEAP_STATE 1
998 #define NEWHOPE_BYTE_ALIGNED 0
999 #elif defined(__AVR__)
1000 #define NEWHOPE_HEAP_STATE 0
1001 #define NEWHOPE_BYTE_ALIGNED 1
1002 #else
1003 #define NEWHOPE_HEAP_STATE 0
1004 #define NEWHOPE_BYTE_ALIGNED 0
1005 #endif
1006 
1025 void NewHope::keygen(uint8_t send[NEWHOPE_SENDABYTES], NewHopePrivateKey &sk,
1026  Variant variant, const uint8_t *random_seed)
1027 {
1028  // The order of calls is rearranged compared to the reference C version.
1029  // This allows us to get away with two temporary poly objects (a, pk)
1030  // instead of four (a, e, r, pk). This saves 4k of stack space.
1031  //
1032  // We also combine most of the state into a single union, which allows
1033  // us to overlap some of the larger objects and reuse the stack space
1034  // at different points within this function.
1035  typedef union {
1036  struct {
1037  uint16_t a[PARAM_N]; // Value of "a" as a "poly" object.
1038  uint16_t pk[PARAM_N]; // Value of "pk" as a "poly" object.
1039  };
1040  struct {
1041  uint16_t a_ext[84 * 16]; // Value of "a" for torref uniform.
1042  ALLOC_OBJ(SHAKE128, shake); // SHAKE128 object for poly_uniform().
1043  };
1044  ALLOC_OBJ(SHA3_256, sha3); // SHA3 object for hashing the seed.
1045  } NewHopeKeygenState;
1046 #if NEWHOPE_HEAP_STATE
1047  NewHopeKeygenState *heapState = new NewHopeKeygenState();
1048  #define state (*heapState)
1049 #else
1050  NewHopeKeygenState state;
1051 #endif
1052 
1053  // Hide the ChaCha state and the noise seed inside "send".
1054 #if NEWHOPE_BYTE_ALIGNED
1055  #define chacha (*((NewHopeChaChaState *)send))
1056 #else
1057  NewHopeChaChaState chacha;
1058 #endif
1059 #if NEWHOPE_SMALL_FOOTPRINT
1060  #define noiseseed (sk.seed)
1061 #else
1062  #define noiseseed (send + sizeof(NewHopeChaChaState))
1063 #endif
1064 
1065  if (!random_seed) {
1066  RNG.rand(send + POLY_BYTES, NEWHOPE_SEEDBYTES);
1067  RNG.rand(noiseseed, 32);
1068  } else {
1069  memcpy(send + POLY_BYTES, random_seed, NEWHOPE_SEEDBYTES);
1070  memcpy(noiseseed, random_seed + NEWHOPE_SEEDBYTES, 32);
1071  }
1072  INIT_OBJ(SHA3_256, sha3);
1073  sha3->update(send + POLY_BYTES, NEWHOPE_SEEDBYTES);
1074  sha3->finalize(send + POLY_BYTES, NEWHOPE_SEEDBYTES);
1075 
1076  INIT_OBJ(SHAKE128, shake);
1077  if (variant == Ref)
1078  poly_uniform(shake, state.a, send + POLY_BYTES);
1079  else
1080  poly_uniform_torref(shake, state.a_ext, send + POLY_BYTES);
1081 
1082  crypto_chacha20_set_key(chacha.input, noiseseed);
1083 
1084 #if NEWHOPE_SMALL_FOOTPRINT
1085  poly_getnoise(state.pk, &chacha, 0);
1086  poly_ntt(state.pk);
1087  poly_pointwise(state.pk, state.pk, state.a);
1088 #else
1089  poly_getnoise(sk.coeffs, &chacha, 0);
1090  poly_ntt(sk.coeffs);
1091  poly_pointwise(state.pk, sk.coeffs, state.a);
1092 #endif
1093 
1094  poly_getnoise(state.a, &chacha, 1);
1095  poly_ntt(state.a);
1096 
1097  poly_add(state.pk, state.a, state.pk);
1098 
1099  poly_tobytes(send, state.pk);
1100 
1101  clean(&state, sizeof(state));
1102 #if !NEWHOPE_BYTE_ALIGNED
1103  clean(&chacha, sizeof(chacha));
1104 #endif
1105  #undef noiseseed
1106  #undef chacha
1107 #if NEWHOPE_HEAP_STATE
1108  delete heapState;
1109  #undef state
1110 #endif
1111 }
1112 
1137 void NewHope::sharedb(uint8_t shared_key[NEWHOPE_SHAREDBYTES],
1138  uint8_t send[NEWHOPE_SENDBBYTES],
1139  uint8_t received[NEWHOPE_SENDABYTES],
1140  Variant variant, const uint8_t *random_seed)
1141 {
1142 #if NEWHOPE_SMALL_FOOTPRINT && NEWHOPE_BYTE_ALIGNED
1143  // The order of calls is rearranged compared to the reference C version.
1144  // This allows us to get away with 2 temporary poly objects (v, a)
1145  // instead of 8 (sp, ep, v, a, pka, c, epp, bp). Saves 12k of stack space.
1146  // To achieve this, we reuse "send" as the third temporary poly object bp.
1147  //
1148  // We also combine most of the state into a single union, which allows
1149  // us to overlap some of the larger objects and reuse the stack space
1150  // at different points within this function.
1151  union {
1152  struct {
1153  uint16_t a[PARAM_N]; // Value of "a" as a "poly" object.
1154  uint16_t v[PARAM_N]; // Value of "v" as a "poly" object.
1155  };
1156  struct {
1157  uint16_t a_ext[84 * 16]; // Value of "a" for torref uniform.
1158  ALLOC_OBJ(SHAKE128, shake); // SHAKE128 object for poly_uniform().
1159  };
1160  ALLOC_OBJ(SHA3_256, sha3); // SHA3 object for hashing the result.
1161  } state;
1162  uint8_t seed[32];
1163  NewHopeChaChaState chacha;
1164  #define bp ((uint16_t *)send)
1165 
1166  if (!random_seed) {
1167  RNG.rand(seed, 32);
1168  crypto_chacha20_set_key(chacha.input, seed);
1169  } else {
1170  crypto_chacha20_set_key(chacha.input, random_seed);
1171  }
1172 
1173  poly_frombytes(state.a, received);
1174  memcpy(seed, received + POLY_BYTES, 32);
1175 
1176  poly_getnoise(bp, &chacha, 0);
1177  poly_ntt(bp);
1178 
1179  poly_pointwise(state.v, state.a, bp);
1180  poly_invntt(state.v);
1181 
1182  poly_getnoise(bp, &chacha, 2);
1183 
1184  poly_add(state.v, state.v, bp);
1185 
1186  helprec(&chacha, state.a, state.v, 3);
1187 
1188  encode_b_2nd_half(send, state.a);
1189 
1190  rec(shared_key, state.v, state.a);
1191 
1192  INIT_OBJ(SHA3_256, sha3);
1193  sha3->update(shared_key, 32);
1194  sha3->finalize(shared_key, 32);
1195 
1196  INIT_OBJ(SHAKE128, shake);
1197  if (variant == Ref)
1198  poly_uniform(shake, state.a, seed);
1199  else
1200  poly_uniform_torref(shake, state.a_ext, seed);
1201 
1202  poly_getnoise(state.v, &chacha, 0);
1203  poly_ntt(state.v);
1204 
1205  poly_pointwise(state.a, state.a, state.v);
1206 
1207  poly_getnoise(state.v, &chacha, 1);
1208  poly_ntt(state.v);
1209 
1210  poly_add(state.a, state.a, state.v);
1211 
1212  poly_tobytes(send, state.a);
1213 
1214  clean(&state, sizeof(state));
1215  clean(&chacha, sizeof(chacha));
1216  clean(seed, sizeof(seed));
1217  #undef bp
1218 #else
1219  // The order of calls is rearranged compared to the reference C version.
1220  // This allows us to get away with 3 temporary poly objects (v, a, bp)
1221  // instead of 8 (sp, ep, v, a, pka, c, epp, bp). Saves 10k of stack space.
1222  //
1223  // We also combine most of the state into a single union, which allows
1224  // us to overlap some of the larger objects and reuse the stack space
1225  // at different points within this function.
1226  typedef union {
1227  struct {
1228  uint16_t a[PARAM_N]; // Value of "a" as a "poly" object.
1229  uint16_t v[PARAM_N]; // Value of "v" as a "poly" object.
1230  uint16_t bp[PARAM_N]; // Value of "bp" as a "poly" object.
1231  };
1232  struct {
1233  uint16_t a_ext[84 * 16]; // Value of "a" for torref uniform.
1234  ALLOC_OBJ(SHAKE128, shake); // SHAKE128 object for poly_uniform().
1235  };
1236  ALLOC_OBJ(SHA3_256, sha3); // SHA3 object for hashing the result.
1237  } NewHopeSharedBState;
1238 #if NEWHOPE_HEAP_STATE
1239  NewHopeSharedBState *heapState = new NewHopeSharedBState();
1240  #define state (*heapState)
1241 #else
1242  NewHopeSharedBState state;
1243 #endif
1244 
1245  // Hide the ChaCha state and the noise seed inside "send".
1246  // Put them at the end of the "send" buffer in case "received"
1247  // overlaps with the start of "send".
1248 #if NEWHOPE_BYTE_ALIGNED
1249  #define chacha (*((NewHopeChaChaState *)(send + NEWHOPE_SENDABYTES)))
1250 #else
1251  NewHopeChaChaState chacha;
1252 #endif
1253  #define noiseseed (send + NEWHOPE_SENDABYTES + sizeof(NewHopeChaChaState))
1254 
1255  if (!random_seed)
1256  RNG.rand(noiseseed, 32);
1257  else
1258  memcpy(noiseseed, random_seed, 32);
1259 
1260  INIT_OBJ(SHAKE128, shake);
1261  if (variant == Ref)
1262  poly_uniform(shake, state.a, received + POLY_BYTES);
1263  else
1264  poly_uniform_torref(shake, state.a_ext, received + POLY_BYTES);
1265 
1266  crypto_chacha20_set_key(chacha.input, noiseseed);
1267 
1268  poly_getnoise(state.v, &chacha, 0);
1269  poly_ntt(state.v);
1270 
1271  poly_pointwise(state.bp, state.a, state.v);
1272 
1273  poly_getnoise(state.a, &chacha, 1);
1274  poly_ntt(state.a);
1275 
1276  poly_add(state.bp, state.bp, state.a);
1277 
1278  poly_frombytes(state.a, received);
1279 
1280  poly_pointwise(state.v, state.a, state.v);
1281  poly_invntt(state.v);
1282 
1283  poly_getnoise(state.a, &chacha, 2);
1284  poly_add(state.v, state.v, state.a);
1285 
1286  helprec(&chacha, state.a, state.v, 3);
1287 
1288  poly_tobytes(send, state.bp);
1289  encode_b_2nd_half(send, state.a);
1290 
1291  rec(shared_key, state.v, state.a);
1292 
1293  INIT_OBJ(SHA3_256, sha3);
1294  sha3->update(shared_key, 32);
1295  sha3->finalize(shared_key, 32);
1296 
1297  clean(&state, sizeof(state));
1298 #if !NEWHOPE_BYTE_ALIGNED
1299  clean(&chacha, sizeof(chacha));
1300 #endif
1301 #undef noiseseed
1302 #undef chacha
1303 #endif
1304 #if NEWHOPE_HEAP_STATE
1305  delete heapState;
1306  #undef state
1307 #endif
1308 }
1309 
1319 void NewHope::shareda(uint8_t shared_key[NEWHOPE_SHAREDBYTES],
1320  const NewHopePrivateKey &sk,
1321  uint8_t received[NEWHOPE_SENDBBYTES])
1322 {
1323  // The order of calls is rearranged compared to the reference C version.
1324  // This allows us to get away with two temporary poly objects (v, bp)
1325  // instead of three (v, bp, c). This saves 2k of stack space.
1326  //
1327  // We also combine most of the state into a single union, which allows
1328  // us to overlap some of the larger objects and reuse the stack space
1329  // at different points within this function.
1330  typedef union {
1331  struct {
1332  uint16_t v[PARAM_N]; // Value of "v" as a "poly" object.
1333  uint16_t bp[PARAM_N]; // Value of "bp" as a "poly" object.
1334  };
1335  struct {
1336  uint16_t v_alt[PARAM_N];
1337  ALLOC_OBJ(NewHopeChaChaState, chacha);
1338  };
1339  ALLOC_OBJ(SHA3_256, sha3); // SHA3 object for hashing the result.
1340  } NewHopeSharedAState;
1341 #if NEWHOPE_HEAP_STATE
1342  NewHopeSharedAState *heapState = new NewHopeSharedAState();
1343  #define state (*heapState)
1344 #else
1345  NewHopeSharedAState state;
1346 #endif
1347 
1348 #if NEWHOPE_SMALL_FOOTPRINT
1349  // Re-create the full private key for Alice from the seed.
1350  INIT_OBJ(NewHopeChaChaState, chacha);
1351  crypto_chacha20_set_key(chacha->input, sk.seed);
1352  poly_getnoise(state.v, chacha, 0);
1353  poly_ntt(state.v);
1354  poly_frombytes(state.bp, received);
1355  poly_pointwise(state.v, state.v, state.bp);
1356  poly_invntt(state.v);
1357 #else
1358  // Alice's full private key was supplied.
1359  poly_frombytes(state.bp, received);
1360  poly_pointwise(state.v, sk.coeffs, state.bp);
1361  poly_invntt(state.v);
1362 #endif
1363 
1364  decode_b_2nd_half(state.bp, received);
1365 
1366  rec(shared_key, state.v, state.bp);
1367 
1368  INIT_OBJ(SHA3_256, sha3);
1369  sha3->update(shared_key, 32);
1370  sha3->finalize(shared_key, 32);
1371 
1372  clean(&state, sizeof(state));
1373 #if NEWHOPE_HEAP_STATE
1374  delete heapState;
1375  #undef state
1376 #endif
1377 }
static void hashCore(uint32_t *output, const uint32_t *input, uint8_t rounds)
Executes the ChaCha hash core on an input memory block.
Definition: ChaCha.cpp:253
static void sharedb(uint8_t shared_key[NEWHOPE_SHAREDBYTES], uint8_t send[NEWHOPE_SENDBBYTES], uint8_t received[NEWHOPE_SENDABYTES], Variant variant=Ref, const uint8_t *random_seed=0)
Generates the public key and shared secret for Bob.
Definition: NewHope.cpp:1137
static void keygen(uint8_t send[NEWHOPE_SENDABYTES], NewHopePrivateKey &sk, Variant variant=Ref, const uint8_t *random_seed=0)
Generates the key pair for Alice in a New Hope key exchange.
Definition: NewHope.cpp:1025
Variant
Describes the variant of the New Hope algorithm to implement.
Definition: NewHope.h:58
@ Ref
The standard "reference" version of the New Hope algorithm.
Definition: NewHope.h:59
static void shareda(uint8_t shared_key[NEWHOPE_SHAREDBYTES], const NewHopePrivateKey &sk, uint8_t received[NEWHOPE_SENDBBYTES])
Generates the shared secret for Alice.
Definition: NewHope.cpp:1319
void rand(uint8_t *data, size_t len)
Generates random bytes into a caller-supplied buffer.
Definition: RNG.cpp:660
SHA3-256 hash algorithm.
Definition: SHA3.h:30
SHAKE Extendable-Output Function (XOF) with 128-bit security.
Definition: SHAKE.h:53
void update(const void *data, size_t len)
Updates the XOF with more data.
Definition: SHAKE.cpp:64
void extend(uint8_t *data, size_t len)
Generates extendable output from this XOF.
Definition: SHAKE.cpp:71
NewHope private key representation.
Definition: NewHope.h:39