From 6b208420c30a220bae1931d9238bae649db1a556 Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Mon, 6 Aug 2018 21:20:13 +0200 Subject: [PATCH] Separated odd/even tables --- src/monocypher.c | 226 ++++++++++++++++++++++++++--------------------- 1 file changed, 123 insertions(+), 103 deletions(-) diff --git a/src/monocypher.c b/src/monocypher.c index cca32e2..ff40a97 100644 --- a/src/monocypher.c +++ b/src/monocypher.c @@ -1621,201 +1621,211 @@ static void ge_double_scalarmult_vartime(ge *sum, const ge *P, } } -// 5-bit comb in cached format (Niels coordinates, Z=1) -static const fe comb_Yp[32] = { - {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, +// 5-bit signed comb in cached format (Niels coordinates, Z=1) +static const fe comb_Yp[16] = { {25967493, -14356035, 29566456, 3660896, -12694345, 4014787, 27544626, -11754271, -6079156, 2047605}, - {8139927, -6546497, 32257646, -5890546, 30375719, - 1886181, -21175108, 15441252, 28826358, -4123029}, {12703444, -2181316, 10152129, -12508779, -5890437, 8946832, -21924701, 3818978, -33057372, 12911566}, - {12375359, -4411558, 31344248, -8172991, -15128721, - -3466513, -8976863, 16561847, -26205910, -9394891}, {8306194, -14143118, -10238858, -5405183, -14037323, 12068501, -1236090, -5245176, 10851181, -12607714}, - {5672113, -9124294, -1153635, 16200026, 4750103, - -868183, -32786869, -1085024, 22886357, -12780530}, {18120131, 12071608, 21125717, -6606711, 10355655, -14711729, 3787738, -13860694, -982779, 14558359}, - {-27589786, 15456424, 8972517, 8469608, 15640622, - 4439847, 3121995, -10329713, 27842616, -202328}, {25858668, -4985677, 2120505, 16091305, 7391348, 10610365, -7335597, -7439596, -23104129, -3797161}, - {-23961442, 121162, -2045597, -15635244, 19886304, - -7310988, -29349367, -13584897, 3520224, 3633220}, {-11686658, 1497415, -8778369, -14202781, -18579236, -4311975, -23453531, -6830706, 30506490, -9775077}, - {8090147, 8790016, 449697, -10577993, 11766947, - 4216756, 918446, 6634564, 32210904, -6727292}, {25600883, 2071823, 9941416, -10896661, 23423401, -12500258, -19655462, 2856297, 312875, -10613450}, - {-21804323, 8005040, 6397302, -10337488, 24348829, - 7241770, 27495234, 10640943, 20217084, -454582}, {-32121761, -15207754, 33396618, -14723121, -29516292, -13925373, -13713381, 3392439, 30639929, -13408905}, - {4863460, 14069888, 16285550, 1692464, 13072445, - -14101095, -20389917, 10588017, -27305040, -11077015}, {-7117140, 15747832, -16514178, -12254753, 24130398, 3093491, -32353403, 8545235, -6665045, 9257947}, - {-10118202, 3263221, -4936628, 8899399, -16136943, - -5101892, 16431484, -226575, -18572303, -12258891}, {14992745, 8361823, 3523482, -12218453, -13219075, 8315164, 21328819, 5128180, -27386578, -4323884}, - {-28014796, -15700773, 31136919, 519458, -2440987, - 13592724, -6767822, -13230802, -25553264, -2407731}, {2251652, -15991143, -27468306, 4453039, -13768446, -7370491, 27022281, 10825033, -32667079, 1858662}, - {-32640426, -5743025, 32609830, -8654924, 31361747, - 12775980, -21332773, 13875817, 21821094, -8652457}, {23611106, -15249653, -19685306, 13099590, -10624350, -9959547, 16366399, -16114031, 22782403, 15145768}, - {-28613603, 6939974, 22623732, 16619607, -30491547, - 5957027, 26348619, 15039407, 14684390, -5397141}, {-13227726, 16304883, -31598943, 13984156, -2131232, -9009443, -15013664, -13542868, 23206632, 12931274}, - {27298351, 13775929, -21326558, -1077239, 18110625, - 14598175, -31434652, -15040910, 25583567, -14088282}, {32013400, 16045921, -5902503, -4718653, -30908032, 5434957, 7979181, 2981327, 22526677, -1341427}, - {4800045, -7834842, -17079780, -3259306, 21016073, - 8953142, 19571676, 4495590, 12798022, 3022178}, {24504806, -3332404, 12079903, 8273693, 17724206, -13296059, -22616184, 520111, 3513144, -14290270}, - {11019068, -862246, -33061352, 4411014, -5100554, - 5234401, -32712505, 461306, -1380880, 369367}, {6211591, -11166015, 24568352, 2768318, -10822221, 11922793, 33211827, 3852290, -13160369, -8855385}, }; -static const fe comb_Ym[32] = { - {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, +static const fe comb_Ym[16] = { {-12545711, 934262, -2722910, 3049990, -727428, 9406986, 12720692, 5043384, 19500929, -15469378}, - {6267086, 9695052, 7709135, -16603597, -32869068, - -1886135, 14795160, -7840124, 13746021, -1742048}, {-2541856, -15652776, -22572529, 2937461, -28190001, 7762515, -16373974, -15951908, 18716257, -10045968}, - {29358073, -9242956, -18683448, 1114915, -14399942, - -15164073, -26780152, 13440858, -23247769, 7151756}, {-31997307, 11002537, 7008281, -3595452, -3480679, -12111922, -1023122, 4888710, 804395, -15235524}, - {-4521623, -9128180, 28747111, -6365311, 13736975, - 12157269, -537752, -771176, 28980578, -12876400}, {21556615, -12052277, 15356468, 4995449, -25231578, -2508891, 22136302, -7228911, 17286986, -11904201}, - {-15306973, 2839644, 22530074, 10026331, 4602058, - 5048462, 28248656, 5031932, -11375082, 12714369}, {8940223, -14841663, 31805643, 4808690, -25598595, 9667370, 22176936, 14438497, 16102536, 9530208}, - {28836705, -16712272, -4579874, 14001135, 1109810, - 4084919, -26582118, -9467125, -9779734, -10000302}, {-513608, 5665157, 15850712, -16377571, 23125808, -14972265, 4662333, 4483302, -19709326, -8557028}, - {-2034699, 12490540, -2448120, -7595302, 25652641, - 3471679, -7115178, 7315513, 26363807, 12997302}, {-32428919, -1092435, 4438817, 16271742, -27086888, -14077861, 16193549, -10458721, -19538508, 15374214}, - {10198429, -6000884, 26618853, -13048682, 14754110, - -12404941, 30671730, -16616407, 32552008, -5857090}, {15097618, -15514804, 23528738, 2718105, -14965989, -75291, -3316581, -8787944, -12379603, 2753851}, - {-294417, 2704020, 1566698, 4841377, -20479788, - 11152593, 21433955, -12053643, -31481288, 13143650}, {-9016734, -5834817, 2507013, 449862, -9227931, 12425140, 8659221, 7705156, 22877471, 16439162}, - {18195253, 16321521, 27188492, 12667955, 20209480, - 14758081, -10746377, -7266089, -22372639, 16180284}, {20381484, -11701888, -167638, 3410941, 27656484, 197244, 11466046, 9333664, -6767222, 11691372}, - {-21088231, -188311, -28992217, -1649664, 13000611, - 14825040, 8325320, 5804136, 18606155, -117168}, {-13741093, -7715345, 6233150, 4810508, -4455410, -12367010, -5301374, -8937525, -18031988, 14315228}, - {16594455, 9319367, -6423651, -3559043, -21252111, - 13660649, -9884331, -12055445, -21145519, -1293304}, {-32341463, 11469835, -28995996, 412669, 140779, 13156277, 8885959, -4149359, 29659155, -5285104}, - {19832645, 1708656, -12762708, -4853593, 1494175, - -4474888, -10277076, -6135229, -11277231, -5142705}, {28050332, -9488439, 29708789, 8836987, 20609920, 10375719, -12837336, 1299100, 18013708, 13790596}, - {-31048391, -13925096, 20093520, 7214946, -26801904, - 10601108, -4790697, 221595, 24880163, -16708777}, {28462938, 3608914, -27674252, 9509233, 6615097, -2406698, 6041816, 9458568, -12047933, -10733308}, - {-26626321, 14406406, -63530, -205771, 8512176, - 9673854, 27048942, 1913860, -17819408, 16454650}, {12339828, 12058078, 2236717, 16133048, -11285450, -898441, -27185848, 5510434, 23495542, -16198691}, - {8924341, -6653045, -8837937, -10765319, 3736593, - -9780510, -10581361, 549251, -17371668, 154076}, {14864569, -6319076, -3080, -8151104, 4994948, -1572144, -41927, 9269803, 13881712, -13439497}, }; -static const fe comb_T2[32] = { - {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, +static const fe comb_T2[16] = { {-8738181, 4489570, 9688441, -14785194, 10184609, -12363380, 29287919, 11864899, -24514362, -4438546}, - {28584902, 7787108, -6732942, -15050729, 22846041, - -7571236, -3181936, -363524, 4771362, -8419958}, {-28632456, 12329109, -19410662, -11463601, -11053622, -5099938, 2652101, 2320975, -15698833, -12287929}, - {22427521, -8216631, -13953689, 5390460, 9717898, - -15420189, -24996943, -3843860, -27420816, 8959577}, {-1490997, -9232695, -24211518, -2303084, -18220935, -4262650, 1068496, -4126981, -16264398, 5241568}, - {29342198, -1823891, -4253845, 11207787, -16647413, - 14626122, 5121439, -335267, 31927899, -9060714}, {20125930, -815698, 20840232, 16004199, -11556539, -3245887, -18976105, 12900346, 18459564, 5752563}, - {20807691, -7270825, 29286141, 11421711, -27876523, - -13868230, -21227475, 1035546, -19733229, 12796920}, {26967266, -16601161, -10657915, 87217, 1727566, 1497406, -13515504, -5456408, 32651057, 9710054}, - {15554029, 5127777, -1098013, -10121195, 12263567, - 15547017, -8328245, -3822824, -14157861, -13790817}, {20197822, -4899798, -16177166, -5352984, -9284084, 2805338, -13072075, 4614713, 18850966, -16397716}, - {-7359158, 14389823, 21772213, 1873152, 15078797, - 5920264, -21701662, -12609839, -21310850, -7119010}, {-1474803, -212087, -3073091, -10505895, -410585, 8399972, -19670402, -4141995, -19831605, 13699714}, - {25191621, 10749150, 22202340, -12035550, -2719594, - -8184793, -27284878, -9585083, -5705096, -14668150}, {-28538760, 11251873, -23016488, -720416, -13774196, -6177771, 4413497, -11733994, -3360469, -14948519}, - {-2409006, 1487693, -21216864, -1833630, 280270, - -7803925, 23803448, -8804078, -15314800, -2344265}, {-24477152, 10391690, -22997974, -882728, -18025249, 12073870, 9148442, -9747879, -18426788, -1526651}, - {-13273196, -14077009, -11385297, -10310726, 4522817, - -5191996, -16656966, 7205163, -15142090, 12473328}, {-32864534, 6943932, -7676139, -353447, 3121044, 3379647, -26292389, -5432970, 29973600, 3630729}, - {17643776, 1609678, 7836646, -1569095, -4578804, - 11015057, 7825694, 10368213, 8398504, 2990775}, {20640018, 16600644, 26982832, -1561105, -25182143, -2578743, -29287948, 8699974, -21726675, -3367281}, - {17328815, -7903176, -2809665, -4965470, -21037243, - 11149062, 19007364, 13951561, 15372728, -5840160}, {-3410623, 16632932, 16197115, 9110253, 18609126, -10417714, -11341312, -8532918, -8219649, 10152430}, - {15920578, -8431856, 2595288, -3083306, -30062761, - -6195525, -27792643, -5545052, -29016491, -13637576}, {-5353296, -11167786, -25924919, 7391152, 13155856, 914209, 17837044, 6421676, 30654154, 8336228}, - {-32812244, -4382699, -6991810, 3747558, -10418863, - 16310993, -22164605, -9436575, -6511940, 12025763}, {-7433539, 6535306, -23600888, -8695956, -2124920, -2785760, 30087084, -8943800, -8270697, -5419195}, - {14237071, 10832242, 17826062, 16679148, -9268304, - -9558784, 17290007, -10390378, 30557094, -13262406}, {-22897924, 10685796, -1320866, 918812, 21158046, 11755018, -28211505, -9155956, -19151907, -225908}, - {16285903, -8276545, 30306997, 11370524, -7436543, - -10311215, -22053106, 13854464, 30623892, 16371753}, {-25233439, -9389070, -6618212, -3268087, -521386, -7350198, 21035059, -14970947, 25910190, 11122681}, + +}; +static const fe comb_Yp_even[16] = { + {1, 0, 0, 0, 0, + 0, 0, 0, 0, 0}, + {8139927, -6546497, 32257646, -5890546, 30375719, + 1886181, -21175108, 15441252, 28826358, -4123029}, + {12375359, -4411558, 31344248, -8172991, -15128721, + -3466513, -8976863, 16561847, -26205910, -9394891}, + {5672113, -9124294, -1153635, 16200026, 4750103, + -868183, -32786869, -1085024, 22886357, -12780530}, + {-27589786, 15456424, 8972517, 8469608, 15640622, + 4439847, 3121995, -10329713, 27842616, -202328}, + {-23961442, 121162, -2045597, -15635244, 19886304, + -7310988, -29349367, -13584897, 3520224, 3633220}, + {8090147, 8790016, 449697, -10577993, 11766947, + 4216756, 918446, 6634564, 32210904, -6727292}, + {-21804323, 8005040, 6397302, -10337488, 24348829, + 7241770, 27495234, 10640943, 20217084, -454582}, + {4863460, 14069888, 16285550, 1692464, 13072445, + -14101095, -20389917, 10588017, -27305040, -11077015}, + {-10118202, 3263221, -4936628, 8899399, -16136943, + -5101892, 16431484, -226575, -18572303, -12258891}, + {-28014796, -15700773, 31136919, 519458, -2440987, + 13592724, -6767822, -13230802, -25553264, -2407731}, + {-32640426, -5743025, 32609830, -8654924, 31361747, + 12775980, -21332773, 13875817, 21821094, -8652457}, + {-28613603, 6939974, 22623732, 16619607, -30491547, + 5957027, 26348619, 15039407, 14684390, -5397141}, + {27298351, 13775929, -21326558, -1077239, 18110625, + 14598175, -31434652, -15040910, 25583567, -14088282}, + {4800045, -7834842, -17079780, -3259306, 21016073, + 8953142, 19571676, 4495590, 12798022, 3022178}, + {11019068, -862246, -33061352, 4411014, -5100554, + 5234401, -32712505, 461306, -1380880, 369367}, +}; +static const fe comb_Ym_even[16] = { + {1, 0, 0, 0, 0, + 0, 0, 0, 0, 0}, + {6267086, 9695052, 7709135, -16603597, -32869068, + -1886135, 14795160, -7840124, 13746021, -1742048}, + {29358073, -9242956, -18683448, 1114915, -14399942, + -15164073, -26780152, 13440858, -23247769, 7151756}, + {-4521623, -9128180, 28747111, -6365311, 13736975, + 12157269, -537752, -771176, 28980578, -12876400}, + {-15306973, 2839644, 22530074, 10026331, 4602058, + 5048462, 28248656, 5031932, -11375082, 12714369}, + {28836705, -16712272, -4579874, 14001135, 1109810, + 4084919, -26582118, -9467125, -9779734, -10000302}, + {-2034699, 12490540, -2448120, -7595302, 25652641, + 3471679, -7115178, 7315513, 26363807, 12997302}, + {10198429, -6000884, 26618853, -13048682, 14754110, + -12404941, 30671730, -16616407, 32552008, -5857090}, + {-294417, 2704020, 1566698, 4841377, -20479788, + 11152593, 21433955, -12053643, -31481288, 13143650}, + {18195253, 16321521, 27188492, 12667955, 20209480, + 14758081, -10746377, -7266089, -22372639, 16180284}, + {-21088231, -188311, -28992217, -1649664, 13000611, + 14825040, 8325320, 5804136, 18606155, -117168}, + {16594455, 9319367, -6423651, -3559043, -21252111, + 13660649, -9884331, -12055445, -21145519, -1293304}, + {19832645, 1708656, -12762708, -4853593, 1494175, + -4474888, -10277076, -6135229, -11277231, -5142705}, + {-31048391, -13925096, 20093520, 7214946, -26801904, + 10601108, -4790697, 221595, 24880163, -16708777}, + {-26626321, 14406406, -63530, -205771, 8512176, + 9673854, 27048942, 1913860, -17819408, 16454650}, + {8924341, -6653045, -8837937, -10765319, 3736593, + -9780510, -10581361, 549251, -17371668, 154076}, +}; +static const fe comb_T2_even[16] = { + {0, 0, 0, 0, 0, + 0, 0, 0, 0, 0}, + {28584902, 7787108, -6732942, -15050729, 22846041, + -7571236, -3181936, -363524, 4771362, -8419958}, + {22427521, -8216631, -13953689, 5390460, 9717898, + -15420189, -24996943, -3843860, -27420816, 8959577}, + {29342198, -1823891, -4253845, 11207787, -16647413, + 14626122, 5121439, -335267, 31927899, -9060714}, + {20807691, -7270825, 29286141, 11421711, -27876523, + -13868230, -21227475, 1035546, -19733229, 12796920}, + {15554029, 5127777, -1098013, -10121195, 12263567, + 15547017, -8328245, -3822824, -14157861, -13790817}, + {-7359158, 14389823, 21772213, 1873152, 15078797, + 5920264, -21701662, -12609839, -21310850, -7119010}, + {25191621, 10749150, 22202340, -12035550, -2719594, + -8184793, -27284878, -9585083, -5705096, -14668150}, + {-2409006, 1487693, -21216864, -1833630, 280270, + -7803925, 23803448, -8804078, -15314800, -2344265}, + {-13273196, -14077009, -11385297, -10310726, 4522817, + -5191996, -16656966, 7205163, -15142090, 12473328}, + {17643776, 1609678, 7836646, -1569095, -4578804, + 11015057, 7825694, 10368213, 8398504, 2990775}, + {17328815, -7903176, -2809665, -4965470, -21037243, + 11149062, 19007364, 13951561, 15372728, -5840160}, + {15920578, -8431856, 2595288, -3083306, -30062761, + -6195525, -27792643, -5545052, -29016491, -13637576}, + {-32812244, -4382699, -6991810, 3747558, -10418863, + 16310993, -22164605, -9436575, -6511940, 12025763}, + {14237071, 10832242, 17826062, 16679148, -9268304, + -9558784, 17290007, -10390378, 30557094, -13262406}, + {16285903, -8276545, 30306997, 11370524, -7436543, + -10311215, -22053106, 13854464, 30623892, 16371753}, }; static void ge_scalarmult_base(ge *p, const u8 scalar[32]) @@ -1831,16 +1841,26 @@ static void ge_scalarmult_base(ge *p, const u8 scalar[32]) fe_1(yp); fe_1(ym); fe_0(t2); - u8 index = scalar_bit(scalar, i) + u8 teeth = scalar_bit(scalar, i) | (scalar_bit(scalar, i + 51) << 1) | (scalar_bit(scalar, i + 102) << 2) | (scalar_bit(scalar, i + 153) << 3) | (scalar_bit(scalar, i + 204) << 4); - FOR (j, 1, 32) { - i32 select = (1 & (((j ^ index) - 1) >> 8)) - 1; - fe_ccopy(yp, comb_Yp[j], select); - fe_ccopy(ym, comb_Ym[j], select); - fe_ccopy(t2, comb_T2[j], select); + u8 index = teeth / 2; + if (teeth & 1) { + FOR (j, 0, 16) { + i32 select = (1 & (((j ^ index) - 1) >> 8)) - 1; + fe_ccopy(yp, comb_Yp[j], select); + fe_ccopy(ym, comb_Ym[j], select); + fe_ccopy(t2, comb_T2[j], select); + } + } else { + FOR (j, 1, 16) { + i32 select = (1 & (((j ^ index) - 1) >> 8)) - 1; + fe_ccopy(yp, comb_Yp_even[j], select); + fe_ccopy(ym, comb_Ym_even[j], select); + fe_ccopy(t2, comb_T2_even[j], select); + } } ge_madd(p, p, yp, ym, t2, a, b); } -- 2.47.3