From b96ca7c830dd110a489619561fdc271af2d8ae63 Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Sat, 4 Aug 2018 21:08:53 +0200 Subject: [PATCH] Comb for EdDSA signatures in Niels coordinates While it takes a bit more space to encode, this also avoids some initial overhead, and significantly reduces stack size. Note: we could do away with the T2 coordinate to reduce the overhead of constant time lookup, but this would also require more work per point addition. Experiments suggest the bigger table is a little faster. --- src/monocypher.c | 227 +++++++++++++++++++++++++---------------------- 1 file changed, 122 insertions(+), 105 deletions(-) diff --git a/src/monocypher.c b/src/monocypher.c index a8934e6..361d0ed 100644 --- a/src/monocypher.c +++ b/src/monocypher.c @@ -1471,17 +1471,18 @@ static void ge_add(ge *s, const ge *p, const ge_cached *q) fe_mul(s->Z, a , b ); } -static void ge_madd(ge *s, const ge *p, const ge_cached *q, fe a, fe b) +static void ge_madd(ge *s, const ge *p, const fe yp, const fe ym, const fe t2, + fe a, fe b) { fe_add(a , p->Y, p->X ); fe_sub(b , p->Y, p->X ); - fe_mul(a , a , q->Yp); - fe_mul(b , b , q->Ym); + fe_mul(a , a , yp ); + fe_mul(b , b , ym ); fe_add(s->Y, a , b ); fe_sub(s->X, a , b ); fe_add(s->Z, p->Z, p->Z ); - fe_mul(s->T, p->T, q->T2); + fe_mul(s->T, p->T, t2 ); fe_add(a , s->Z, s->T ); fe_sub(b , s->Z, s->T ); @@ -1547,92 +1548,16 @@ static void ge_precompute(ge_cached lut[8], const ge *P1) } } -static const fe base_comb [32] = { - {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, - {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, - - {-14297830, -7645148, 16144683, -16471763, 27570974, - -2696100, -26142465, 8378389, 20764389, 8758491}, - {-26843541, -6710886, 13421773, -13421773, 26843546, - 6710886, -13421773, 13421773, -26843546, -6710886}, - - {15573525, 14345213, -21141567, -612142, 123758, - 10521238, 28338138, -12928375, 9171680, -7828746}, - {-18590957, -4287007, 23122404, 4576385, 22037208, - 1801295, 32339603, 310189, 3056877, 825069}, - - {30210978, 104920, -15170738, -6817324, 11761033, - -15118165, -20055778, -18672, -25574763, 3861063}, - {-28221882, -9451648, -21791555, -3983251, 23779144, - -13855839, -7901342, -1724237, -1392984, 6340893}, - - {12052535, 1174424, 8175504, 5117753, -27026921, - -11654751, -23281039, 6656678, -801697, -13590848}, - {-678274, 11486291, 9685879, 15895846, -29146376, - 12753979, 9394963, -15748418, -26925347, -8605080}, - - {825005, 12536410, -6496388, 4296550, -20735056, - 12804180, 31514438, 9564502, 22198414, -4615275}, - {-5255013, -11888353, -29227865, 12908075, 14214213, - -4697787, -16889443, -15217324, 16403638, 14741828}, - - {-5518824, 12818641, 13119870, 10280901, 21889473, - -7381370, 451058, 9009411, 31293939, -4732176}, - {-4310457, 16627320, 3420478, 15531175, -5933775, - -7190110, 11110264, 15405360, -15500696, -8287368}, - - {-6464925, -9329913, -31634864, -16035764, 30395596, - -16310495, 13483582, 7871241, -17358241, 13088374}, - {3552871, 6590485, 16923854, 10315913, 32380106, - -12863682, -7468635, 6673921, -2106711, 16063652}, - - {-2436467, 11899186, -5973137, -15875860, 32143228, - 8263549, -25027698, -3177038, 31687046, 7282364}, - {3229766, 12424768, 14809438, 9640153, 7604728, - -10633143, -8928323, -1708212, 25515618, -7904217}, - - {-5216200, -12638014, -1961798, -13948316, -1316146, - -9481306, -14271890, 4221131, -23614114, 727153}, - {15882703, 1629505, 389272, -5031709, -31879178, - 12581620, 1501550, 7844402, -26322285, -16029646}, - - {-17511878, 12267674, 13296274, 7242520, -5498795, - -11577238, -3808580, -5120487, -12974513, -3827469}, - {-19255847, 4162371, -15956754, -4730560, -23805568, - 14314510, 3092857, 14313711, -3031034, -9142948}, - - {16019263, -4229613, -6740766, 385371, 9412243, - -6356439, -726247, 2003675, 14726638, 15972428}, - {32697609, 14966159, 30602392, 8666789, 6543735, - -14868665, 31979828, 15873036, 5848962, 16551381}, - - {-5377564, 14235465, -33017134, -5260292, -24500568, - -7491531, -24324338, 7014691, 22574802, -2489028}, - {-21683205, -13945861, 4837803, 8345978, 27487628, - -3168201, -25504314, -11350571, -1217757, 3602043}, - - {-5684537, 10535028, -20389135, 1979940, 3036178, - 13177340, -16360399, -12898161, -3169412, -4781580}, - {11746923, -1888575, -29914862, -3251907, 6589152, - -16175485, -26429093, 2728843, -15679830, -3661028}, - - {-25524410, 9805852, -4714175, 11753615, -8577161, - 14211345, -2605451, -4194190, 4783123, 12799649}, - {27429126, -13939394, 28352636, 1391247, 24616562, - 824146, 11390233, -15116964, -5844948, 15386449}, - - {29253635, 12845933, 25577229, -1309771, 29774635, - -3542406, -1108709, -16177068, -3493870, -7212097}, - {-29534145, 16176741, 30088034, -4259757, 2173511, - 3069472, 31761054, 15672049, 26807422, 9724138}, -}; - // Variable time! P, sP, and sB must not be secret! static void ge_double_scalarmult_vartime(ge *sum, const ge *P, u8 p[32], u8 b[32]) { + static const fe X = { -14297830, -7645148, 16144683, -16471763, 27570974, + -2696100, -26142465, 8378389, 20764389, 8758491 }; + static const fe Y = { -26843541, -6710886, 13421773, -13421773, 26843546, + 6710886, -13421773, 13421773, -26843546, -6710886 }; ge B; - ge_from_xy(&B, base_comb[2], base_comb[3]); + ge_from_xy(&B, X, Y); // cached points for addition ge_cached cP[8]; ge_precompute(cP, P); @@ -1649,41 +1574,133 @@ static void ge_double_scalarmult_vartime(ge *sum, const ge *P, } } +// 4-bit comb in cached format (Niels coordinates, Z=1) +static const fe comb_Yp[16] = { + {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, + {25967493, -14356035, 29566456, 3660896, -12694345, + 4014787, 27544626, -11754271, -6079156, 2047605}, + {-3017432, 10058206, 1980837, 3964243, 22160966, + 12322533, -6431123, -12618185, 12228557, -7003677}, + {1989096, -9346728, 30146571, -10800576, -31568687, + 4580429, -27957121, -1742909, -26967747, 10201956}, + {11374242, 12660715, 17861383, -12540833, 10935568, + 1099227, -13886076, -9091740, -27727044, 11358504}, + {-4430008, 648057, 31384611, -16349808, -6520842, + 8106393, 14624995, -5652822, -28506812, 10126554}, + {-9829281, -4108471, 16540349, -7742356, 15955699, + -14571480, 11561322, -9139661, 15793244, -13019544}, + {-2912035, -2739428, -14711010, -5719851, -4333162, + 4380256, 6014946, 14545162, -19464952, -4402406}, + {793299, -9230478, 8836302, -6235707, -27360908, + -2369593, 33152843, -4885251, -9906200, -621852}, + {10666503, -11008509, -1572526, 14574407, -33195325, + 3100314, -12770340, 12065533, 17172465, -15302494}, + {30341139, 16430044, -2660480, 2511960, -29304363, + 2737272, -715723, 9193224, -16005547, -12970417}, + {-18391973, 10736547, 23861626, 9052160, 15955978, + 12329328, 31253580, -15677721, 20575601, -1030623}, + {-27060769, 289604, -28179331, 3085686, 2987060, + -10659732, 17280212, -4335881, 21357045, 1113015}, + {6062386, 8646453, 16804867, -1271968, 9625330, + -2998145, 24319372, -10169319, -18849242, -8442608}, + {1904735, -4133542, 23638461, 13144862, 16039401, + 15035491, 8784782, 14243278, -1061826, -5368334}, + {-280510, -4531758, -11443600, -5569527, 31948146, + -472934, 30652345, -505019, 23313552, 2512041}, +}; +static const fe comb_Ym[16] = { + {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, + {-12545711, 934262, -2722910, 3049990, -727428, + 9406986, 12720692, 5043384, 19500929, -15469378}, + {32944382, 14922211, -22844894, 5188528, 21913450, + -8719943, 4001465, 13238564, -6114803, 8653815}, + {8676004, -9556569, -6620817, 2834073, 12018111, + 1262326, 12154436, -1705565, 24181779, 2479830}, + {-12730809, 10311867, 1510375, 10778093, -2119455, + -9145702, 32676003, 11149336, -26123651, 4985768}, + {-6079999, 9129669, -22731478, 8611525, -32159595, + 16052466, 18704982, 8772605, -5794777, -14197329}, + {1208367, 3808679, -9699392, 5250274, -27823248, + 191260, 10659206, 6395949, 20314229, -3555193}, + {10017796, 15920398, -18550146, -7202754, 1984511, + 3446813, -20952217, -1197320, 15251530, 2975278}, + {5666233, 525582, 20782575, -8038419, -24538499, + 14657740, 16099374, 1468826, -6171428, -15186581}, + {21098903, 14267519, 2351070, 8916607, -30563032, + -11491506, 15773441, 3623271, -2708171, -16756799}, + {-1743969, -8105303, -29253028, -11973080, -18306773, + -7662684, 6901438, -14120234, 9943480, -5315479}, + {16678346, -14358660, -29765705, 8281419, -2868508, + -8512226, 32706075, 13869361, -8877676, 578953}, + {-16305641, 5373106, -29253928, 13606271, -15120668, + 4323331, -1179976, 15189170, -23792560, 6091071}, + {17431460, -12423603, -9525727, -5231847, 3552974, + 4201607, -10068695, 15627004, -12510418, 1120552}, + {-14155328, 9809187, 33066810, -10362368, 33193723, + -13387199, 13995684, -10922774, -10628071, 2586800}, + {8321103, 3330807, 4510805, -2949986, -27601124, + 6611878, 32869763, -1705315, 30301293, -16618197}, +}; +static const fe comb_T2[16] = { + {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, + {-8738181, 4489570, 9688441, -14785194, 10184609, + -12363380, 29287919, 11864899, -24514362, -4438546}, + {22865569, -4652735, 27603668, -12545395, 14348958, + 8234005, 24808405, 5719875, 28483275, 2841751}, + {-27547818, -3620617, -11678598, 694158, 1244790, + 7563226, -3643307, 12404327, 7987052, -11724351}, + {-19096303, 341147, -6197485, -239033, 15756973, + -8796662, -983043, 13794114, -19414307, -15621255}, + {22472240, 9473251, 20136607, 3545737, 6583525, + -5394043, -22300972, -4701040, -29716529, -13074752}, + {-2153423, 4260298, 27710638, -11168640, -8579137, + 10918623, -9589200, 245710, -16745540, -7081251}, + {12777116, -1023357, 29704762, 4041038, -33274600, + 743745, 31466336, 14221651, -16049466, -16481117}, + {-4859255, -3779343, -2917758, -6748019, 7778750, + 11688288, -30404353, -9871238, -1558923, -9863646}, + {-18848289, 10532636, 13162400, -1502633, 14345812, + 12380276, -11703169, -3544470, 1941255, -14644905}, + {31969798, 7967153, 8955209, 7115550, -20644889, + -5549409, 28734583, 7563797, -6615362, 8601078}, + {22694915, -4456776, 29402143, 10609596, 12393514, + 10083943, -24837634, 9465663, 9244769, 14895110}, + {-24249916, 8034341, -20600914, 3251099, 23984608, + 9786034, 2664017, 9329462, -28732468, 7907777}, + {26747231, -11981979, 5341570, -13213261, 7208513, + 1498346, -15226184, 11658866, -5911538, 3287152}, + {-1021806, 4455676, -9156738, -5796068, 24832937, + -10091699, -13593841, 5856404, -22267100, -9627207}, + {-12365609, -11571615, 11962523, 2961320, -31152564, + -11927760, 24989997, -5464220, -26196392, -5839453}, +}; + static void ge_scalarmult_base(ge *p, const u8 scalar[32]) { - // Expand the comb into a proper look up table - ge_cached ccomb[16]; - FOR (i, 0, 16) { - ge tmp; - ge_from_xy(&tmp, base_comb[i*2], base_comb[i*2+1]); - ge_cache(&ccomb[i], &tmp); - } - // Double and add ladder - ge_cached tmp; - fe a, b; // temporaries for addition - ge dbl; // temporary for doublings + fe yp, ym, t2, a, b; // temporaries for addition + ge dbl; // temporary for doublings ge_zero(p); for (int i = 63; i >= 0; i--) { ge_double(p, p, &dbl); - fe_1(tmp.Ym); fe_1(tmp.Yp); - fe_1(tmp.Z ); fe_0(tmp.T2); + fe_1(yp); + fe_1(ym); + fe_0(t2); u8 nibble = scalar_bit(scalar, i) | (scalar_bit(scalar, i + 64) << 1) | (scalar_bit(scalar, i + 128) << 2) | (scalar_bit(scalar, i + 192) << 3); FOR (i, 1, 16) { i32 select = (1 & (((i ^ nibble) - 1) >> 8)) - 1; - fe_ccopy(tmp.Ym, ccomb[i].Ym, select); - fe_ccopy(tmp.Yp, ccomb[i].Yp, select); - fe_ccopy(tmp.T2, ccomb[i].T2, select); + fe_ccopy(yp, comb_Yp[i], select); + fe_ccopy(ym, comb_Ym[i], select); + fe_ccopy(t2, comb_T2[i], select); } - ge_madd(p, p, &tmp, a, b); + ge_madd(p, p, yp, ym, t2, a, b); } - WIPE_CTX(&tmp); WIPE_CTX(&dbl); - WIPE_BUFFER(a); - WIPE_BUFFER(b); + WIPE_BUFFER(ym); WIPE_BUFFER(yp); WIPE_BUFFER(t2); + WIPE_BUFFER(a ); WIPE_BUFFER(b ); } static void modL(u8 *r, i64 x[64]) -- 2.47.3