1 #include "inner.h"
2
3 /*
4 * Falcon signature verification.
5 *
6 * ==========================(LICENSE BEGIN)============================
7 *
8 * Copyright (c) 2017-2019 Falcon Project
9 *
10 * Permission is hereby granted, free of charge, to any person obtaining
11 * a copy of this software and associated documentation files (the
12 * "Software"), to deal in the Software without restriction, including
13 * without limitation the rights to use, copy, modify, merge, publish,
14 * distribute, sublicense, and/or sell copies of the Software, and to
15 * permit persons to whom the Software is furnished to do so, subject to
16 * the following conditions:
17 *
18 * The above copyright notice and this permission notice shall be
19 * included in all copies or substantial portions of the Software.
20 *
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
24 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
25 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
26 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
27 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28 *
29 * ===========================(LICENSE END)=============================
30 *
31 * @author Thomas Pornin <thomas.pornin@nccgroup.com>
32 */
33
34
35 /* ===================================================================== */
36 /*
37 * Constants for NTT.
38 *
39 * n = 2^logn (2 <= n <= 1024)
40 * phi = X^n + 1
41 * q = 12289
42 * q0i = -1/q mod 2^16
43 * R = 2^16 mod q
44 * R2 = 2^32 mod q
45 */
46
47 #define Q 12289
48 #define Q0I 12287
49 #define R 4091
50 #define R2 10952
51
52 /*
53 * Table for NTT, binary case:
54 * GMb[x] = R*(g^rev(x)) mod q
55 * where g = 7 (it is a 2048-th primitive root of 1 modulo q)
56 * and rev() is the bit-reversal function over 10 bits.
57 */
58 static const uint16_t GMb[] = {
59 4091, 7888, 11060, 11208, 6960, 4342, 6275, 9759,
60 1591, 6399, 9477, 5266, 586, 5825, 7538, 9710,
61 1134, 6407, 1711, 965, 7099, 7674, 3743, 6442,
62 10414, 8100, 1885, 1688, 1364, 10329, 10164, 9180,
63 12210, 6240, 997, 117, 4783, 4407, 1549, 7072,
64 2829, 6458, 4431, 8877, 7144, 2564, 5664, 4042,
65 12189, 432, 10751, 1237, 7610, 1534, 3983, 7863,
66 2181, 6308, 8720, 6570, 4843, 1690, 14, 3872,
67 5569, 9368, 12163, 2019, 7543, 2315, 4673, 7340,
68 1553, 1156, 8401, 11389, 1020, 2967, 10772, 7045,
69 3316, 11236, 5285, 11578, 10637, 10086, 9493, 6180,
70 9277, 6130, 3323, 883, 10469, 489, 1502, 2851,
71 11061, 9729, 2742, 12241, 4970, 10481, 10078, 1195,
72 730, 1762, 3854, 2030, 5892, 10922, 9020, 5274,
73 9179, 3604, 3782, 10206, 3180, 3467, 4668, 2446,
74 7613, 9386, 834, 7703, 6836, 3403, 5351, 12276,
75 3580, 1739, 10820, 9787, 10209, 4070, 12250, 8525,
76 10401, 2749, 7338, 10574, 6040, 943, 9330, 1477,
77 6865, 9668, 3585, 6633, 12145, 4063, 3684, 7680,
78 8188, 6902, 3533, 9807, 6090, 727, 10099, 7003,
79 6945, 1949, 9731, 10559, 6057, 378, 7871, 8763,
80 8901, 9229, 8846, 4551, 9589, 11664, 7630, 8821,
81 5680, 4956, 6251, 8388, 10156, 8723, 2341, 3159,
82 1467, 5460, 8553, 7783, 2649, 2320, 9036, 6188,
83 737, 3698, 4699, 5753, 9046, 3687, 16, 914,
84 5186, 10531, 4552, 1964, 3509, 8436, 7516, 5381,
85 10733, 3281, 7037, 1060, 2895, 7156, 8887, 5357,
86 6409, 8197, 2962, 6375, 5064, 6634, 5625, 278,
87 932, 10229, 8927, 7642, 351, 9298, 237, 5858,
88 7692, 3146, 12126, 7586, 2053, 11285, 3802, 5204,
89 4602, 1748, 11300, 340, 3711, 4614, 300, 10993,
90 5070, 10049, 11616, 12247, 7421, 10707, 5746, 5654,
91 3835, 5553, 1224, 8476, 9237, 3845, 250, 11209,
92 4225, 6326, 9680, 12254, 4136, 2778, 692, 8808,
93 6410, 6718, 10105, 10418, 3759, 7356, 11361, 8433,
94 6437, 3652, 6342, 8978, 5391, 2272, 6476, 7416,
95 8418, 10824, 11986, 5733, 876, 7030, 2167, 2436,
96 3442, 9217, 8206, 4858, 5964, 2746, 7178, 1434,
97 7389, 8879, 10661, 11457, 4220, 1432, 10832, 4328,
98 8557, 1867, 9454, 2416, 3816, 9076, 686, 5393,
99 2523, 4339, 6115, 619, 937, 2834, 7775, 3279,
100 2363, 7488, 6112, 5056, 824, 10204, 11690, 1113,
101 2727, 9848, 896, 2028, 5075, 2654, 10464, 7884,
102 12169, 5434, 3070, 6400, 9132, 11672, 12153, 4520,
103 1273, 9739, 11468, 9937, 10039, 9720, 2262, 9399,
104 11192, 315, 4511, 1158, 6061, 6751, 11865, 357,
105 7367, 4550, 983, 8534, 8352, 10126, 7530, 9253,
106 4367, 5221, 3999, 8777, 3161, 6990, 4130, 11652,
107 3374, 11477, 1753, 292, 8681, 2806, 10378, 12188,
108 5800, 11811, 3181, 1988, 1024, 9340, 2477, 10928,
109 4582, 6750, 3619, 5503, 5233, 2463, 8470, 7650,
110 7964, 6395, 1071, 1272, 3474, 11045, 3291, 11344,
111 8502, 9478, 9837, 1253, 1857, 6233, 4720, 11561,
112 6034, 9817, 3339, 1797, 2879, 6242, 5200, 2114,
113 7962, 9353, 11363, 5475, 6084, 9601, 4108, 7323,
114 10438, 9471, 1271, 408, 6911, 3079, 360, 8276,
115 11535, 9156, 9049, 11539, 850, 8617, 784, 7919,
116 8334, 12170, 1846, 10213, 12184, 7827, 11903, 5600,
117 9779, 1012, 721, 2784, 6676, 6552, 5348, 4424,
118 6816, 8405, 9959, 5150, 2356, 5552, 5267, 1333,
119 8801, 9661, 7308, 5788, 4910, 909, 11613, 4395,
120 8238, 6686, 4302, 3044, 2285, 12249, 1963, 9216,
121 4296, 11918, 695, 4371, 9793, 4884, 2411, 10230,
122 2650, 841, 3890, 10231, 7248, 8505, 11196, 6688,
123 4059, 6060, 3686, 4722, 11853, 5816, 7058, 6868,
124 11137, 7926, 4894, 12284, 4102, 3908, 3610, 6525,
125 7938, 7982, 11977, 6755, 537, 4562, 1623, 8227,
126 11453, 7544, 906, 11816, 9548, 10858, 9703, 2815,
127 11736, 6813, 6979, 819, 8903, 6271, 10843, 348,
128 7514, 8339, 6439, 694, 852, 5659, 2781, 3716,
129 11589, 3024, 1523, 8659, 4114, 10738, 3303, 5885,
130 2978, 7289, 11884, 9123, 9323, 11830, 98, 2526,
131 2116, 4131, 11407, 1844, 3645, 3916, 8133, 2224,
132 10871, 8092, 9651, 5989, 7140, 8480, 1670, 159,
133 10923, 4918, 128, 7312, 725, 9157, 5006, 6393,
134 3494, 6043, 10972, 6181, 11838, 3423, 10514, 7668,
135 3693, 6658, 6905, 11953, 10212, 11922, 9101, 8365,
136 5110, 45, 2400, 1921, 4377, 2720, 1695, 51,
137 2808, 650, 1896, 9997, 9971, 11980, 8098, 4833,
138 4135, 4257, 5838, 4765, 10985, 11532, 590, 12198,
139 482, 12173, 2006, 7064, 10018, 3912, 12016, 10519,
140 11362, 6954, 2210, 284, 5413, 6601, 3865, 10339,
141 11188, 6231, 517, 9564, 11281, 3863, 1210, 4604,
142 8160, 11447, 153, 7204, 5763, 5089, 9248, 12154,
143 11748, 1354, 6672, 179, 5532, 2646, 5941, 12185,
144 862, 3158, 477, 7279, 5678, 7914, 4254, 302,
145 2893, 10114, 6890, 9560, 9647, 11905, 4098, 9824,
146 10269, 1353, 10715, 5325, 6254, 3951, 1807, 6449,
147 5159, 1308, 8315, 3404, 1877, 1231, 112, 6398,
148 11724, 12272, 7286, 1459, 12274, 9896, 3456, 800,
149 1397, 10678, 103, 7420, 7976, 936, 764, 632,
150 7996, 8223, 8445, 7758, 10870, 9571, 2508, 1946,
151 6524, 10158, 1044, 4338, 2457, 3641, 1659, 4139,
152 4688, 9733, 11148, 3946, 2082, 5261, 2036, 11850,
153 7636, 12236, 5366, 2380, 1399, 7720, 2100, 3217,
154 10912, 8898, 7578, 11995, 2791, 1215, 3355, 2711,
155 2267, 2004, 8568, 10176, 3214, 2337, 1750, 4729,
156 4997, 7415, 6315, 12044, 4374, 7157, 4844, 211,
157 8003, 10159, 9290, 11481, 1735, 2336, 5793, 9875,
158 8192, 986, 7527, 1401, 870, 3615, 8465, 2756,
159 9770, 2034, 10168, 3264, 6132, 54, 2880, 4763,
160 11805, 3074, 8286, 9428, 4881, 6933, 1090, 10038,
161 2567, 708, 893, 6465, 4962, 10024, 2090, 5718,
162 10743, 780, 4733, 4623, 2134, 2087, 4802, 884,
163 5372, 5795, 5938, 4333, 6559, 7549, 5269, 10664,
164 4252, 3260, 5917, 10814, 5768, 9983, 8096, 7791,
165 6800, 7491, 6272, 1907, 10947, 6289, 11803, 6032,
166 11449, 1171, 9201, 7933, 2479, 7970, 11337, 7062,
167 8911, 6728, 6542, 8114, 8828, 6595, 3545, 4348,
168 4610, 2205, 6999, 8106, 5560, 10390, 9321, 2499,
169 2413, 7272, 6881, 10582, 9308, 9437, 3554, 3326,
170 5991, 11969, 3415, 12283, 9838, 12063, 4332, 7830,
171 11329, 6605, 12271, 2044, 11611, 7353, 11201, 11582,
172 3733, 8943, 9978, 1627, 7168, 3935, 5050, 2762,
173 7496, 10383, 755, 1654, 12053, 4952, 10134, 4394,
174 6592, 7898, 7497, 8904, 12029, 3581, 10748, 5674,
175 10358, 4901, 7414, 8771, 710, 6764, 8462, 7193,
176 5371, 7274, 11084, 290, 7864, 6827, 11822, 2509,
177 6578, 4026, 5807, 1458, 5721, 5762, 4178, 2105,
178 11621, 4852, 8897, 2856, 11510, 9264, 2520, 8776,
179 7011, 2647, 1898, 7039, 5950, 11163, 5488, 6277,
180 9182, 11456, 633, 10046, 11554, 5633, 9587, 2333,
181 7008, 7084, 5047, 7199, 9865, 8997, 569, 6390,
182 10845, 9679, 8268, 11472, 4203, 1997, 2, 9331,
183 162, 6182, 2000, 3649, 9792, 6363, 7557, 6187,
184 8510, 9935, 5536, 9019, 3706, 12009, 1452, 3067,
185 5494, 9692, 4865, 6019, 7106, 9610, 4588, 10165,
186 6261, 5887, 2652, 10172, 1580, 10379, 4638, 9949
187 };
188
189 /*
190 * Table for inverse NTT, binary case:
191 * iGMb[x] = R*((1/g)^rev(x)) mod q
192 * Since g = 7, 1/g = 8778 mod 12289.
193 */
194 static const uint16_t iGMb[] = {
195 4091, 4401, 1081, 1229, 2530, 6014, 7947, 5329,
196 2579, 4751, 6464, 11703, 7023, 2812, 5890, 10698,
197 3109, 2125, 1960, 10925, 10601, 10404, 4189, 1875,
198 5847, 8546, 4615, 5190, 11324, 10578, 5882, 11155,
199 8417, 12275, 10599, 7446, 5719, 3569, 5981, 10108,
200 4426, 8306, 10755, 4679, 11052, 1538, 11857, 100,
201 8247, 6625, 9725, 5145, 3412, 7858, 5831, 9460,
202 5217, 10740, 7882, 7506, 12172, 11292, 6049, 79,
203 13, 6938, 8886, 5453, 4586, 11455, 2903, 4676,
204 9843, 7621, 8822, 9109, 2083, 8507, 8685, 3110,
205 7015, 3269, 1367, 6397, 10259, 8435, 10527, 11559,
206 11094, 2211, 1808, 7319, 48, 9547, 2560, 1228,
207 9438, 10787, 11800, 1820, 11406, 8966, 6159, 3012,
208 6109, 2796, 2203, 1652, 711, 7004, 1053, 8973,
209 5244, 1517, 9322, 11269, 900, 3888, 11133, 10736,
210 4949, 7616, 9974, 4746, 10270, 126, 2921, 6720,
211 6635, 6543, 1582, 4868, 42, 673, 2240, 7219,
212 1296, 11989, 7675, 8578, 11949, 989, 10541, 7687,
213 7085, 8487, 1004, 10236, 4703, 163, 9143, 4597,
214 6431, 12052, 2991, 11938, 4647, 3362, 2060, 11357,
215 12011, 6664, 5655, 7225, 5914, 9327, 4092, 5880,
216 6932, 3402, 5133, 9394, 11229, 5252, 9008, 1556,
217 6908, 4773, 3853, 8780, 10325, 7737, 1758, 7103,
218 11375, 12273, 8602, 3243, 6536, 7590, 8591, 11552,
219 6101, 3253, 9969, 9640, 4506, 3736, 6829, 10822,
220 9130, 9948, 3566, 2133, 3901, 6038, 7333, 6609,
221 3468, 4659, 625, 2700, 7738, 3443, 3060, 3388,
222 3526, 4418, 11911, 6232, 1730, 2558, 10340, 5344,
223 5286, 2190, 11562, 6199, 2482, 8756, 5387, 4101,
224 4609, 8605, 8226, 144, 5656, 8704, 2621, 5424,
225 10812, 2959, 11346, 6249, 1715, 4951, 9540, 1888,
226 3764, 39, 8219, 2080, 2502, 1469, 10550, 8709,
227 5601, 1093, 3784, 5041, 2058, 8399, 11448, 9639,
228 2059, 9878, 7405, 2496, 7918, 11594, 371, 7993,
229 3073, 10326, 40, 10004, 9245, 7987, 5603, 4051,
230 7894, 676, 11380, 7379, 6501, 4981, 2628, 3488,
231 10956, 7022, 6737, 9933, 7139, 2330, 3884, 5473,
232 7865, 6941, 5737, 5613, 9505, 11568, 11277, 2510,
233 6689, 386, 4462, 105, 2076, 10443, 119, 3955,
234 4370, 11505, 3672, 11439, 750, 3240, 3133, 754,
235 4013, 11929, 9210, 5378, 11881, 11018, 2818, 1851,
236 4966, 8181, 2688, 6205, 6814, 926, 2936, 4327,
237 10175, 7089, 6047, 9410, 10492, 8950, 2472, 6255,
238 728, 7569, 6056, 10432, 11036, 2452, 2811, 3787,
239 945, 8998, 1244, 8815, 11017, 11218, 5894, 4325,
240 4639, 3819, 9826, 7056, 6786, 8670, 5539, 7707,
241 1361, 9812, 2949, 11265, 10301, 9108, 478, 6489,
242 101, 1911, 9483, 3608, 11997, 10536, 812, 8915,
243 637, 8159, 5299, 9128, 3512, 8290, 7068, 7922,
244 3036, 4759, 2163, 3937, 3755, 11306, 7739, 4922,
245 11932, 424, 5538, 6228, 11131, 7778, 11974, 1097,
246 2890, 10027, 2569, 2250, 2352, 821, 2550, 11016,
247 7769, 136, 617, 3157, 5889, 9219, 6855, 120,
248 4405, 1825, 9635, 7214, 10261, 11393, 2441, 9562,
249 11176, 599, 2085, 11465, 7233, 6177, 4801, 9926,
250 9010, 4514, 9455, 11352, 11670, 6174, 7950, 9766,
251 6896, 11603, 3213, 8473, 9873, 2835, 10422, 3732,
252 7961, 1457, 10857, 8069, 832, 1628, 3410, 4900,
253 10855, 5111, 9543, 6325, 7431, 4083, 3072, 8847,
254 9853, 10122, 5259, 11413, 6556, 303, 1465, 3871,
255 4873, 5813, 10017, 6898, 3311, 5947, 8637, 5852,
256 3856, 928, 4933, 8530, 1871, 2184, 5571, 5879,
257 3481, 11597, 9511, 8153, 35, 2609, 5963, 8064,
258 1080, 12039, 8444, 3052, 3813, 11065, 6736, 8454,
259 2340, 7651, 1910, 10709, 2117, 9637, 6402, 6028,
260 2124, 7701, 2679, 5183, 6270, 7424, 2597, 6795,
261 9222, 10837, 280, 8583, 3270, 6753, 2354, 3779,
262 6102, 4732, 5926, 2497, 8640, 10289, 6107, 12127,
263 2958, 12287, 10292, 8086, 817, 4021, 2610, 1444,
264 5899, 11720, 3292, 2424, 5090, 7242, 5205, 5281,
265 9956, 2702, 6656, 735, 2243, 11656, 833, 3107,
266 6012, 6801, 1126, 6339, 5250, 10391, 9642, 5278,
267 3513, 9769, 3025, 779, 9433, 3392, 7437, 668,
268 10184, 8111, 6527, 6568, 10831, 6482, 8263, 5711,
269 9780, 467, 5462, 4425, 11999, 1205, 5015, 6918,
270 5096, 3827, 5525, 11579, 3518, 4875, 7388, 1931,
271 6615, 1541, 8708, 260, 3385, 4792, 4391, 5697,
272 7895, 2155, 7337, 236, 10635, 11534, 1906, 4793,
273 9527, 7239, 8354, 5121, 10662, 2311, 3346, 8556,
274 707, 1088, 4936, 678, 10245, 18, 5684, 960,
275 4459, 7957, 226, 2451, 6, 8874, 320, 6298,
276 8963, 8735, 2852, 2981, 1707, 5408, 5017, 9876,
277 9790, 2968, 1899, 6729, 4183, 5290, 10084, 7679,
278 7941, 8744, 5694, 3461, 4175, 5747, 5561, 3378,
279 5227, 952, 4319, 9810, 4356, 3088, 11118, 840,
280 6257, 486, 6000, 1342, 10382, 6017, 4798, 5489,
281 4498, 4193, 2306, 6521, 1475, 6372, 9029, 8037,
282 1625, 7020, 4740, 5730, 7956, 6351, 6494, 6917,
283 11405, 7487, 10202, 10155, 7666, 7556, 11509, 1546,
284 6571, 10199, 2265, 7327, 5824, 11396, 11581, 9722,
285 2251, 11199, 5356, 7408, 2861, 4003, 9215, 484,
286 7526, 9409, 12235, 6157, 9025, 2121, 10255, 2519,
287 9533, 3824, 8674, 11419, 10888, 4762, 11303, 4097,
288 2414, 6496, 9953, 10554, 808, 2999, 2130, 4286,
289 12078, 7445, 5132, 7915, 245, 5974, 4874, 7292,
290 7560, 10539, 9952, 9075, 2113, 3721, 10285, 10022,
291 9578, 8934, 11074, 9498, 294, 4711, 3391, 1377,
292 9072, 10189, 4569, 10890, 9909, 6923, 53, 4653,
293 439, 10253, 7028, 10207, 8343, 1141, 2556, 7601,
294 8150, 10630, 8648, 9832, 7951, 11245, 2131, 5765,
295 10343, 9781, 2718, 1419, 4531, 3844, 4066, 4293,
296 11657, 11525, 11353, 4313, 4869, 12186, 1611, 10892,
297 11489, 8833, 2393, 15, 10830, 5003, 17, 565,
298 5891, 12177, 11058, 10412, 8885, 3974, 10981, 7130,
299 5840, 10482, 8338, 6035, 6964, 1574, 10936, 2020,
300 2465, 8191, 384, 2642, 2729, 5399, 2175, 9396,
301 11987, 8035, 4375, 6611, 5010, 11812, 9131, 11427,
302 104, 6348, 9643, 6757, 12110, 5617, 10935, 541,
303 135, 3041, 7200, 6526, 5085, 12136, 842, 4129,
304 7685, 11079, 8426, 1008, 2725, 11772, 6058, 1101,
305 1950, 8424, 5688, 6876, 12005, 10079, 5335, 927,
306 1770, 273, 8377, 2271, 5225, 10283, 116, 11807,
307 91, 11699, 757, 1304, 7524, 6451, 8032, 8154,
308 7456, 4191, 309, 2318, 2292, 10393, 11639, 9481,
309 12238, 10594, 9569, 7912, 10368, 9889, 12244, 7179,
310 3924, 3188, 367, 2077, 336, 5384, 5631, 8596,
311 4621, 1775, 8866, 451, 6108, 1317, 6246, 8795,
312 5896, 7283, 3132, 11564, 4977, 12161, 7371, 1366,
313 12130, 10619, 3809, 5149, 6300, 2638, 4197, 1418,
314 10065, 4156, 8373, 8644, 10445, 882, 8158, 10173,
315 9763, 12191, 459, 2966, 3166, 405, 5000, 9311,
316 6404, 8986, 1551, 8175, 3630, 10766, 9265, 700,
317 8573, 9508, 6630, 11437, 11595, 5850, 3950, 4775,
318 11941, 1446, 6018, 3386, 11470, 5310, 5476, 553,
319 9474, 2586, 1431, 2741, 473, 11383, 4745, 836,
320 4062, 10666, 7727, 11752, 5534, 312, 4307, 4351,
321 5764, 8679, 8381, 8187, 5, 7395, 4363, 1152,
322 5421, 5231, 6473, 436, 7567, 8603, 6229, 8230
323 };
324
325 /*
326 * Reduce a small signed integer modulo q. The source integer MUST
327 * be between -q/2 and +q/2.
328 */
329 static inline uint32_t
mq_conv_small(int x)330 mq_conv_small(int x) {
331 /*
332 * If x < 0, the cast to uint32_t will set the high bit to 1.
333 */
334 uint32_t y;
335
336 y = (uint32_t)x;
337 y += Q & -(y >> 31);
338 return y;
339 }
340
341 /*
342 * Addition modulo q. Operands must be in the 0..q-1 range.
343 */
344 static inline uint32_t
mq_add(uint32_t x,uint32_t y)345 mq_add(uint32_t x, uint32_t y) {
346 /*
347 * We compute x + y - q. If the result is negative, then the
348 * high bit will be set, and 'd >> 31' will be equal to 1;
349 * thus '-(d >> 31)' will be an all-one pattern. Otherwise,
350 * it will be an all-zero pattern. In other words, this
351 * implements a conditional addition of q.
352 */
353 uint32_t d;
354
355 d = x + y - Q;
356 d += Q & -(d >> 31);
357 return d;
358 }
359
360 /*
361 * Subtraction modulo q. Operands must be in the 0..q-1 range.
362 */
363 static inline uint32_t
mq_sub(uint32_t x,uint32_t y)364 mq_sub(uint32_t x, uint32_t y) {
365 /*
366 * As in mq_add(), we use a conditional addition to ensure the
367 * result is in the 0..q-1 range.
368 */
369 uint32_t d;
370
371 d = x - y;
372 d += Q & -(d >> 31);
373 return d;
374 }
375
376 /*
377 * Division by 2 modulo q. Operand must be in the 0..q-1 range.
378 */
379 static inline uint32_t
mq_rshift1(uint32_t x)380 mq_rshift1(uint32_t x) {
381 x += Q & -(x & 1);
382 return (x >> 1);
383 }
384
385 /*
386 * Montgomery multiplication modulo q. If we set R = 2^16 mod q, then
387 * this function computes: x * y / R mod q
388 * Operands must be in the 0..q-1 range.
389 */
390 static inline uint32_t
mq_montymul(uint32_t x,uint32_t y)391 mq_montymul(uint32_t x, uint32_t y) {
392 uint32_t z, w;
393
394 /*
395 * We compute x*y + k*q with a value of k chosen so that the 16
396 * low bits of the result are 0. We can then shift the value.
397 * After the shift, result may still be larger than q, but it
398 * will be lower than 2*q, so a conditional subtraction works.
399 */
400
401 z = x * y;
402 w = ((z * Q0I) & 0xFFFF) * Q;
403
404 /*
405 * When adding z and w, the result will have its low 16 bits
406 * equal to 0. Since x, y and z are lower than q, the sum will
407 * be no more than (2^15 - 1) * q + (q - 1)^2, which will
408 * fit on 29 bits.
409 */
410 z = (z + w) >> 16;
411
412 /*
413 * After the shift, analysis shows that the value will be less
414 * than 2q. We do a subtraction then conditional subtraction to
415 * ensure the result is in the expected range.
416 */
417 z -= Q;
418 z += Q & -(z >> 31);
419 return z;
420 }
421
422 /*
423 * Montgomery squaring (computes (x^2)/R).
424 */
425 static inline uint32_t
mq_montysqr(uint32_t x)426 mq_montysqr(uint32_t x) {
427 return mq_montymul(x, x);
428 }
429
430 /*
431 * Divide x by y modulo q = 12289.
432 */
433 static inline uint32_t
mq_div_12289(uint32_t x,uint32_t y)434 mq_div_12289(uint32_t x, uint32_t y) {
435 /*
436 * We invert y by computing y^(q-2) mod q.
437 *
438 * We use the following addition chain for exponent e = 12287:
439 *
440 * e0 = 1
441 * e1 = 2 * e0 = 2
442 * e2 = e1 + e0 = 3
443 * e3 = e2 + e1 = 5
444 * e4 = 2 * e3 = 10
445 * e5 = 2 * e4 = 20
446 * e6 = 2 * e5 = 40
447 * e7 = 2 * e6 = 80
448 * e8 = 2 * e7 = 160
449 * e9 = e8 + e2 = 163
450 * e10 = e9 + e8 = 323
451 * e11 = 2 * e10 = 646
452 * e12 = 2 * e11 = 1292
453 * e13 = e12 + e9 = 1455
454 * e14 = 2 * e13 = 2910
455 * e15 = 2 * e14 = 5820
456 * e16 = e15 + e10 = 6143
457 * e17 = 2 * e16 = 12286
458 * e18 = e17 + e0 = 12287
459 *
460 * Additions on exponents are converted to Montgomery
461 * multiplications. We define all intermediate results as so
462 * many local variables, and let the C compiler work out which
463 * must be kept around.
464 */
465 uint32_t y0, y1, y2, y3, y4, y5, y6, y7, y8, y9;
466 uint32_t y10, y11, y12, y13, y14, y15, y16, y17, y18;
467
468 y0 = mq_montymul(y, R2);
469 y1 = mq_montysqr(y0);
470 y2 = mq_montymul(y1, y0);
471 y3 = mq_montymul(y2, y1);
472 y4 = mq_montysqr(y3);
473 y5 = mq_montysqr(y4);
474 y6 = mq_montysqr(y5);
475 y7 = mq_montysqr(y6);
476 y8 = mq_montysqr(y7);
477 y9 = mq_montymul(y8, y2);
478 y10 = mq_montymul(y9, y8);
479 y11 = mq_montysqr(y10);
480 y12 = mq_montysqr(y11);
481 y13 = mq_montymul(y12, y9);
482 y14 = mq_montysqr(y13);
483 y15 = mq_montysqr(y14);
484 y16 = mq_montymul(y15, y10);
485 y17 = mq_montysqr(y16);
486 y18 = mq_montymul(y17, y0);
487
488 /*
489 * Final multiplication with x, which is not in Montgomery
490 * representation, computes the correct division result.
491 */
492 return mq_montymul(y18, x);
493 }
494
495 /*
496 * Compute NTT on a ring element.
497 */
498 static void
mq_NTT(uint16_t * a,unsigned logn)499 mq_NTT(uint16_t *a, unsigned logn) {
500 size_t n, t, m;
501
502 n = (size_t)1 << logn;
503 t = n;
504 for (m = 1; m < n; m <<= 1) {
505 size_t ht, i, j1;
506
507 ht = t >> 1;
508 for (i = 0, j1 = 0; i < m; i ++, j1 += t) {
509 size_t j, j2;
510 uint32_t s;
511
512 s = GMb[m + i];
513 j2 = j1 + ht;
514 for (j = j1; j < j2; j ++) {
515 uint32_t u, v;
516
517 u = a[j];
518 v = mq_montymul(a[j + ht], s);
519 a[j] = (uint16_t)mq_add(u, v);
520 a[j + ht] = (uint16_t)mq_sub(u, v);
521 }
522 }
523 t = ht;
524 }
525 }
526
527 /*
528 * Compute the inverse NTT on a ring element, binary case.
529 */
530 static void
mq_iNTT(uint16_t * a,unsigned logn)531 mq_iNTT(uint16_t *a, unsigned logn) {
532 size_t n, t, m;
533 uint32_t ni;
534
535 n = (size_t)1 << logn;
536 t = 1;
537 m = n;
538 while (m > 1) {
539 size_t hm, dt, i, j1;
540
541 hm = m >> 1;
542 dt = t << 1;
543 for (i = 0, j1 = 0; i < hm; i ++, j1 += dt) {
544 size_t j, j2;
545 uint32_t s;
546
547 j2 = j1 + t;
548 s = iGMb[hm + i];
549 for (j = j1; j < j2; j ++) {
550 uint32_t u, v, w;
551
552 u = a[j];
553 v = a[j + t];
554 a[j] = (uint16_t)mq_add(u, v);
555 w = mq_sub(u, v);
556 a[j + t] = (uint16_t)
557 mq_montymul(w, s);
558 }
559 }
560 t = dt;
561 m = hm;
562 }
563
564 /*
565 * To complete the inverse NTT, we must now divide all values by
566 * n (the vector size). We thus need the inverse of n, i.e. we
567 * need to divide 1 by 2 logn times. But we also want it in
568 * Montgomery representation, i.e. we also want to multiply it
569 * by R = 2^16. In the common case, this should be a simple right
570 * shift. The loop below is generic and works also in corner cases;
571 * its computation time is negligible.
572 */
573 ni = R;
574 for (m = n; m > 1; m >>= 1) {
575 ni = mq_rshift1(ni);
576 }
577 for (m = 0; m < n; m ++) {
578 a[m] = (uint16_t)mq_montymul(a[m], ni);
579 }
580 }
581
582 /*
583 * Convert a polynomial (mod q) to Montgomery representation.
584 */
585 static void
mq_poly_tomonty(uint16_t * f,unsigned logn)586 mq_poly_tomonty(uint16_t *f, unsigned logn) {
587 size_t u, n;
588
589 n = (size_t)1 << logn;
590 for (u = 0; u < n; u ++) {
591 f[u] = (uint16_t)mq_montymul(f[u], R2);
592 }
593 }
594
595 /*
596 * Multiply two polynomials together (NTT representation, and using
597 * a Montgomery multiplication). Result f*g is written over f.
598 */
599 static void
mq_poly_montymul_ntt(uint16_t * f,const uint16_t * g,unsigned logn)600 mq_poly_montymul_ntt(uint16_t *f, const uint16_t *g, unsigned logn) {
601 size_t u, n;
602
603 n = (size_t)1 << logn;
604 for (u = 0; u < n; u ++) {
605 f[u] = (uint16_t)mq_montymul(f[u], g[u]);
606 }
607 }
608
609 /*
610 * Subtract polynomial g from polynomial f.
611 */
612 static void
mq_poly_sub(uint16_t * f,const uint16_t * g,unsigned logn)613 mq_poly_sub(uint16_t *f, const uint16_t *g, unsigned logn) {
614 size_t u, n;
615
616 n = (size_t)1 << logn;
617 for (u = 0; u < n; u ++) {
618 f[u] = (uint16_t)mq_sub(f[u], g[u]);
619 }
620 }
621
622 /* ===================================================================== */
623
624 /* see inner.h */
625 void
PQCLEAN_FALCON1024_CLEAN_to_ntt_monty(uint16_t * h,unsigned logn)626 PQCLEAN_FALCON1024_CLEAN_to_ntt_monty(uint16_t *h, unsigned logn) {
627 mq_NTT(h, logn);
628 mq_poly_tomonty(h, logn);
629 }
630
631 /* see inner.h */
632 int
PQCLEAN_FALCON1024_CLEAN_verify_raw(const uint16_t * c0,const int16_t * s2,const uint16_t * h,unsigned logn,uint8_t * tmp)633 PQCLEAN_FALCON1024_CLEAN_verify_raw(const uint16_t *c0, const int16_t *s2,
634 const uint16_t *h, unsigned logn, uint8_t *tmp) {
635 size_t u, n;
636 uint16_t *tt;
637
638 n = (size_t)1 << logn;
639 tt = (uint16_t *)tmp;
640
641 /*
642 * Reduce s2 elements modulo q ([0..q-1] range).
643 */
644 for (u = 0; u < n; u ++) {
645 uint32_t w;
646
647 w = (uint32_t)s2[u];
648 w += Q & -(w >> 31);
649 tt[u] = (uint16_t)w;
650 }
651
652 /*
653 * Compute -s1 = s2*h - c0 mod phi mod q (in tt[]).
654 */
655 mq_NTT(tt, logn);
656 mq_poly_montymul_ntt(tt, h, logn);
657 mq_iNTT(tt, logn);
658 mq_poly_sub(tt, c0, logn);
659
660 /*
661 * Normalize -s1 elements into the [-q/2..q/2] range.
662 */
663 for (u = 0; u < n; u ++) {
664 int32_t w;
665
666 w = (int32_t)tt[u];
667 w -= (int32_t)(Q & -(((Q >> 1) - (uint32_t)w) >> 31));
668 ((int16_t *)tt)[u] = (int16_t)w;
669 }
670
671 /*
672 * Signature is valid if and only if the aggregate (-s1,s2) vector
673 * is short enough.
674 */
675 return PQCLEAN_FALCON1024_CLEAN_is_short((int16_t *)tt, s2, logn);
676 }
677
678 /* see inner.h */
679 int
PQCLEAN_FALCON1024_CLEAN_compute_public(uint16_t * h,const int8_t * f,const int8_t * g,unsigned logn,uint8_t * tmp)680 PQCLEAN_FALCON1024_CLEAN_compute_public(uint16_t *h,
681 const int8_t *f, const int8_t *g, unsigned logn, uint8_t *tmp) {
682 size_t u, n;
683 uint16_t *tt;
684
685 n = (size_t)1 << logn;
686 tt = (uint16_t *)tmp;
687 for (u = 0; u < n; u ++) {
688 tt[u] = (uint16_t)mq_conv_small(f[u]);
689 h[u] = (uint16_t)mq_conv_small(g[u]);
690 }
691 mq_NTT(h, logn);
692 mq_NTT(tt, logn);
693 for (u = 0; u < n; u ++) {
694 if (tt[u] == 0) {
695 return 0;
696 }
697 h[u] = (uint16_t)mq_div_12289(h[u], tt[u]);
698 }
699 mq_iNTT(h, logn);
700 return 1;
701 }
702
703 /* see inner.h */
704 int
PQCLEAN_FALCON1024_CLEAN_complete_private(int8_t * G,const int8_t * f,const int8_t * g,const int8_t * F,unsigned logn,uint8_t * tmp)705 PQCLEAN_FALCON1024_CLEAN_complete_private(int8_t *G,
706 const int8_t *f, const int8_t *g, const int8_t *F,
707 unsigned logn, uint8_t *tmp) {
708 size_t u, n;
709 uint16_t *t1, *t2;
710
711 n = (size_t)1 << logn;
712 t1 = (uint16_t *)tmp;
713 t2 = t1 + n;
714 for (u = 0; u < n; u ++) {
715 t1[u] = (uint16_t)mq_conv_small(g[u]);
716 t2[u] = (uint16_t)mq_conv_small(F[u]);
717 }
718 mq_NTT(t1, logn);
719 mq_NTT(t2, logn);
720 mq_poly_tomonty(t1, logn);
721 mq_poly_montymul_ntt(t1, t2, logn);
722 for (u = 0; u < n; u ++) {
723 t2[u] = (uint16_t)mq_conv_small(f[u]);
724 }
725 mq_NTT(t2, logn);
726 for (u = 0; u < n; u ++) {
727 if (t2[u] == 0) {
728 return 0;
729 }
730 t1[u] = (uint16_t)mq_div_12289(t1[u], t2[u]);
731 }
732 mq_iNTT(t1, logn);
733 for (u = 0; u < n; u ++) {
734 uint32_t w;
735 int32_t gi;
736
737 w = t1[u];
738 w -= (Q & ~ -((w - (Q >> 1)) >> 31));
739 gi = *(int32_t *)&w;
740 if (gi < -127 || gi > +127) {
741 return 0;
742 }
743 G[u] = (int8_t)gi;
744 }
745 return 1;
746 }
747
748 /* see inner.h */
749 int
PQCLEAN_FALCON1024_CLEAN_is_invertible(const int16_t * s2,unsigned logn,uint8_t * tmp)750 PQCLEAN_FALCON1024_CLEAN_is_invertible(
751 const int16_t *s2, unsigned logn, uint8_t *tmp) {
752 size_t u, n;
753 uint16_t *tt;
754 uint32_t r;
755
756 n = (size_t)1 << logn;
757 tt = (uint16_t *)tmp;
758 for (u = 0; u < n; u ++) {
759 uint32_t w;
760
761 w = (uint32_t)s2[u];
762 w += Q & -(w >> 31);
763 tt[u] = (uint16_t)w;
764 }
765 mq_NTT(tt, logn);
766 r = 0;
767 for (u = 0; u < n; u ++) {
768 r |= (uint32_t)(tt[u] - 1);
769 }
770 return (int)(1u - (r >> 31));
771 }
772
773 /* see inner.h */
774 int
PQCLEAN_FALCON1024_CLEAN_verify_recover(uint16_t * h,const uint16_t * c0,const int16_t * s1,const int16_t * s2,unsigned logn,uint8_t * tmp)775 PQCLEAN_FALCON1024_CLEAN_verify_recover(uint16_t *h,
776 const uint16_t *c0, const int16_t *s1, const int16_t *s2,
777 unsigned logn, uint8_t *tmp) {
778 size_t u, n;
779 uint16_t *tt;
780 uint32_t r;
781
782 n = (size_t)1 << logn;
783
784 /*
785 * Reduce elements of s1 and s2 modulo q; then write s2 into tt[]
786 * and c0 - s1 into h[].
787 */
788 tt = (uint16_t *)tmp;
789 for (u = 0; u < n; u ++) {
790 uint32_t w;
791
792 w = (uint32_t)s2[u];
793 w += Q & -(w >> 31);
794 tt[u] = (uint16_t)w;
795
796 w = (uint32_t)s1[u];
797 w += Q & -(w >> 31);
798 w = mq_sub(c0[u], w);
799 h[u] = (uint16_t)w;
800 }
801
802 /*
803 * Compute h = (c0 - s1) / s2. If one of the coefficients of s2
804 * is zero (in NTT representation) then the operation fails. We
805 * keep that information into a flag so that we do not deviate
806 * from strict constant-time processing; if all coefficients of
807 * s2 are non-zero, then the high bit of r will be zero.
808 */
809 mq_NTT(tt, logn);
810 mq_NTT(h, logn);
811 r = 0;
812 for (u = 0; u < n; u ++) {
813 r |= (uint32_t)(tt[u] - 1);
814 h[u] = (uint16_t)mq_div_12289(h[u], tt[u]);
815 }
816 mq_iNTT(h, logn);
817
818 /*
819 * Signature is acceptable if and only if it is short enough,
820 * and s2 was invertible mod phi mod q. The caller must still
821 * check that the rebuilt public key matches the expected
822 * value (e.g. through a hash).
823 */
824 r = ~r & (uint32_t) - PQCLEAN_FALCON1024_CLEAN_is_short(s1, s2, logn);
825 return (int)(r >> 31);
826 }
827
828 /* see inner.h */
829 int
PQCLEAN_FALCON1024_CLEAN_count_nttzero(const int16_t * sig,unsigned logn,uint8_t * tmp)830 PQCLEAN_FALCON1024_CLEAN_count_nttzero(const int16_t *sig, unsigned logn, uint8_t *tmp) {
831 uint16_t *s2;
832 size_t u, n;
833 uint32_t r;
834
835 n = (size_t)1 << logn;
836 s2 = (uint16_t *)tmp;
837 for (u = 0; u < n; u ++) {
838 uint32_t w;
839
840 w = (uint32_t)sig[u];
841 w += Q & -(w >> 31);
842 s2[u] = (uint16_t)w;
843 }
844 mq_NTT(s2, logn);
845 r = 0;
846 for (u = 0; u < n; u ++) {
847 uint32_t w;
848
849 w = (uint32_t)s2[u] - 1u;
850 r += (w >> 31);
851 }
852 return (int)r;
853 }
854