From 4af1bc5d5b99498fc7da0faf94027c8d6bcb903f Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Wed, 15 Apr 2020 21:23:42 +0200 Subject: [PATCH] Simplified GF(2^255-19) carry propagation There used to be two ways to perform carry propagation: a "fast" one, used after decoding and multiplication by small numbers, and a "safe" one, more conservative, used after full multiplications or squarings. Using the safe carry propagation simplifies the source code and facilitates audits. The cost is a 1% performance hit for X25519. --- src/monocypher.c | 73 +++++++++++++++++++----------------------------- 1 file changed, 29 insertions(+), 44 deletions(-) diff --git a/src/monocypher.c b/src/monocypher.c index 3dd3f26..9f20b65 100644 --- a/src/monocypher.c +++ b/src/monocypher.c @@ -1068,16 +1068,18 @@ static void fe_ccopy(fe f, const fe g, int b) #define FE_CARRY \ i64 c0, c1, c2, c3, c4, c5, c6, c7, c8, c9; \ - c9 = (t9 + ((i64)1<<24)) >> 25; t0 += c9 * 19; t9 -= c9 * ((i64)1 << 25); \ + c0 = (t0 + ((i64)1<<25)) >> 26; t1 += c0; t0 -= c0 * ((i64)1 << 26); \ + c4 = (t4 + ((i64)1<<25)) >> 26; t5 += c4; t4 -= c4 * ((i64)1 << 26); \ c1 = (t1 + ((i64)1<<24)) >> 25; t2 += c1; t1 -= c1 * ((i64)1 << 25); \ - c3 = (t3 + ((i64)1<<24)) >> 25; t4 += c3; t3 -= c3 * ((i64)1 << 25); \ c5 = (t5 + ((i64)1<<24)) >> 25; t6 += c5; t5 -= c5 * ((i64)1 << 25); \ - c7 = (t7 + ((i64)1<<24)) >> 25; t8 += c7; t7 -= c7 * ((i64)1 << 25); \ - c0 = (t0 + ((i64)1<<25)) >> 26; t1 += c0; t0 -= c0 * ((i64)1 << 26); \ c2 = (t2 + ((i64)1<<25)) >> 26; t3 += c2; t2 -= c2 * ((i64)1 << 26); \ - c4 = (t4 + ((i64)1<<25)) >> 26; t5 += c4; t4 -= c4 * ((i64)1 << 26); \ c6 = (t6 + ((i64)1<<25)) >> 26; t7 += c6; t6 -= c6 * ((i64)1 << 26); \ + c3 = (t3 + ((i64)1<<24)) >> 25; t4 += c3; t3 -= c3 * ((i64)1 << 25); \ + c7 = (t7 + ((i64)1<<24)) >> 25; t8 += c7; t7 -= c7 * ((i64)1 << 25); \ + c4 = (t4 + ((i64)1<<25)) >> 26; t5 += c4; t4 -= c4 * ((i64)1 << 26); \ c8 = (t8 + ((i64)1<<25)) >> 26; t9 += c8; t8 -= c8 * ((i64)1 << 26); \ + c9 = (t9 + ((i64)1<<24)) >> 25; t0 += c9 * 19; t9 -= c9 * ((i64)1 << 25); \ + c0 = (t0 + ((i64)1<<25)) >> 26; t1 += c0; t0 -= c0 * ((i64)1 << 26); \ h[0]=(i32)t0; h[1]=(i32)t1; h[2]=(i32)t2; h[3]=(i32)t3; h[4]=(i32)t4; \ h[5]=(i32)t5; h[6]=(i32)t6; h[7]=(i32)t7; h[8]=(i32)t8; h[9]=(i32)t9 @@ -1121,45 +1123,28 @@ static void fe_mul(fe h, const fe f, const fe g) i32 G4 = g4*19; i32 G5 = g5*19; i32 G6 = g6*19; i32 G7 = g7*19; i32 G8 = g8*19; i32 G9 = g9*19; - i64 h0 = f0*(i64)g0 + F1*(i64)G9 + f2*(i64)G8 + F3*(i64)G7 + f4*(i64)G6 + i64 t0 = f0*(i64)g0 + F1*(i64)G9 + f2*(i64)G8 + F3*(i64)G7 + f4*(i64)G6 + F5*(i64)G5 + f6*(i64)G4 + F7*(i64)G3 + f8*(i64)G2 + F9*(i64)G1; - i64 h1 = f0*(i64)g1 + f1*(i64)g0 + f2*(i64)G9 + f3*(i64)G8 + f4*(i64)G7 + i64 t1 = f0*(i64)g1 + f1*(i64)g0 + f2*(i64)G9 + f3*(i64)G8 + f4*(i64)G7 + f5*(i64)G6 + f6*(i64)G5 + f7*(i64)G4 + f8*(i64)G3 + f9*(i64)G2; - i64 h2 = f0*(i64)g2 + F1*(i64)g1 + f2*(i64)g0 + F3*(i64)G9 + f4*(i64)G8 + i64 t2 = f0*(i64)g2 + F1*(i64)g1 + f2*(i64)g0 + F3*(i64)G9 + f4*(i64)G8 + F5*(i64)G7 + f6*(i64)G6 + F7*(i64)G5 + f8*(i64)G4 + F9*(i64)G3; - i64 h3 = f0*(i64)g3 + f1*(i64)g2 + f2*(i64)g1 + f3*(i64)g0 + f4*(i64)G9 + i64 t3 = f0*(i64)g3 + f1*(i64)g2 + f2*(i64)g1 + f3*(i64)g0 + f4*(i64)G9 + f5*(i64)G8 + f6*(i64)G7 + f7*(i64)G6 + f8*(i64)G5 + f9*(i64)G4; - i64 h4 = f0*(i64)g4 + F1*(i64)g3 + f2*(i64)g2 + F3*(i64)g1 + f4*(i64)g0 + i64 t4 = f0*(i64)g4 + F1*(i64)g3 + f2*(i64)g2 + F3*(i64)g1 + f4*(i64)g0 + F5*(i64)G9 + f6*(i64)G8 + F7*(i64)G7 + f8*(i64)G6 + F9*(i64)G5; - i64 h5 = f0*(i64)g5 + f1*(i64)g4 + f2*(i64)g3 + f3*(i64)g2 + f4*(i64)g1 + i64 t5 = f0*(i64)g5 + f1*(i64)g4 + f2*(i64)g3 + f3*(i64)g2 + f4*(i64)g1 + f5*(i64)g0 + f6*(i64)G9 + f7*(i64)G8 + f8*(i64)G7 + f9*(i64)G6; - i64 h6 = f0*(i64)g6 + F1*(i64)g5 + f2*(i64)g4 + F3*(i64)g3 + f4*(i64)g2 + i64 t6 = f0*(i64)g6 + F1*(i64)g5 + f2*(i64)g4 + F3*(i64)g3 + f4*(i64)g2 + F5*(i64)g1 + f6*(i64)g0 + F7*(i64)G9 + f8*(i64)G8 + F9*(i64)G7; - i64 h7 = f0*(i64)g7 + f1*(i64)g6 + f2*(i64)g5 + f3*(i64)g4 + f4*(i64)g3 + i64 t7 = f0*(i64)g7 + f1*(i64)g6 + f2*(i64)g5 + f3*(i64)g4 + f4*(i64)g3 + f5*(i64)g2 + f6*(i64)g1 + f7*(i64)g0 + f8*(i64)G9 + f9*(i64)G8; - i64 h8 = f0*(i64)g8 + F1*(i64)g7 + f2*(i64)g6 + F3*(i64)g5 + f4*(i64)g4 + i64 t8 = f0*(i64)g8 + F1*(i64)g7 + f2*(i64)g6 + F3*(i64)g5 + f4*(i64)g4 + F5*(i64)g3 + f6*(i64)g2 + F7*(i64)g1 + f8*(i64)g0 + F9*(i64)G9; - i64 h9 = f0*(i64)g9 + f1*(i64)g8 + f2*(i64)g7 + f3*(i64)g6 + f4*(i64)g5 + i64 t9 = f0*(i64)g9 + f1*(i64)g8 + f2*(i64)g7 + f3*(i64)g6 + f4*(i64)g5 + f5*(i64)g4 + f6*(i64)g3 + f7*(i64)g2 + f8*(i64)g1 + f9*(i64)g0; -#define CARRY \ - i64 c0, c1, c2, c3, c4, c5, c6, c7, c8, c9; \ - c0 = (h0 + ((i64)1<<25)) >> 26; h1 += c0; h0 -= c0 * ((i64)1 << 26); \ - c4 = (h4 + ((i64)1<<25)) >> 26; h5 += c4; h4 -= c4 * ((i64)1 << 26); \ - c1 = (h1 + ((i64)1<<24)) >> 25; h2 += c1; h1 -= c1 * ((i64)1 << 25); \ - c5 = (h5 + ((i64)1<<24)) >> 25; h6 += c5; h5 -= c5 * ((i64)1 << 25); \ - c2 = (h2 + ((i64)1<<25)) >> 26; h3 += c2; h2 -= c2 * ((i64)1 << 26); \ - c6 = (h6 + ((i64)1<<25)) >> 26; h7 += c6; h6 -= c6 * ((i64)1 << 26); \ - c3 = (h3 + ((i64)1<<24)) >> 25; h4 += c3; h3 -= c3 * ((i64)1 << 25); \ - c7 = (h7 + ((i64)1<<24)) >> 25; h8 += c7; h7 -= c7 * ((i64)1 << 25); \ - c4 = (h4 + ((i64)1<<25)) >> 26; h5 += c4; h4 -= c4 * ((i64)1 << 26); \ - c8 = (h8 + ((i64)1<<25)) >> 26; h9 += c8; h8 -= c8 * ((i64)1 << 26); \ - c9 = (h9 + ((i64)1<<24)) >> 25; h0 += c9 * 19; h9 -= c9 * ((i64)1 << 25); \ - c0 = (h0 + ((i64)1<<25)) >> 26; h1 += c0; h0 -= c0 * ((i64)1 << 26); \ - h[0]=(i32)h0; h[1]=(i32)h1; h[2]=(i32)h2; h[3]=(i32)h3; h[4]=(i32)h4; \ - h[5]=(i32)h5; h[6]=(i32)h6; h[7]=(i32)h7; h[8]=(i32)h8; h[9]=(i32)h9 - - CARRY; + FE_CARRY; } // we could use fe_mul() for this, but this is significantly faster @@ -1172,28 +1157,28 @@ static void fe_sq(fe h, const fe f) i32 f5_38 = f5*38; i32 f6_19 = f6*19; i32 f7_38 = f7*38; i32 f8_19 = f8*19; i32 f9_38 = f9*38; - i64 h0 = f0 *(i64)f0 + f1_2*(i64)f9_38 + f2_2*(i64)f8_19 + i64 t0 = f0 *(i64)f0 + f1_2*(i64)f9_38 + f2_2*(i64)f8_19 + f3_2*(i64)f7_38 + f4_2*(i64)f6_19 + f5 *(i64)f5_38; - i64 h1 = f0_2*(i64)f1 + f2 *(i64)f9_38 + f3_2*(i64)f8_19 + i64 t1 = f0_2*(i64)f1 + f2 *(i64)f9_38 + f3_2*(i64)f8_19 + f4 *(i64)f7_38 + f5_2*(i64)f6_19; - i64 h2 = f0_2*(i64)f2 + f1_2*(i64)f1 + f3_2*(i64)f9_38 + i64 t2 = f0_2*(i64)f2 + f1_2*(i64)f1 + f3_2*(i64)f9_38 + f4_2*(i64)f8_19 + f5_2*(i64)f7_38 + f6 *(i64)f6_19; - i64 h3 = f0_2*(i64)f3 + f1_2*(i64)f2 + f4 *(i64)f9_38 + i64 t3 = f0_2*(i64)f3 + f1_2*(i64)f2 + f4 *(i64)f9_38 + f5_2*(i64)f8_19 + f6 *(i64)f7_38; - i64 h4 = f0_2*(i64)f4 + f1_2*(i64)f3_2 + f2 *(i64)f2 + i64 t4 = f0_2*(i64)f4 + f1_2*(i64)f3_2 + f2 *(i64)f2 + f5_2*(i64)f9_38 + f6_2*(i64)f8_19 + f7 *(i64)f7_38; - i64 h5 = f0_2*(i64)f5 + f1_2*(i64)f4 + f2_2*(i64)f3 + i64 t5 = f0_2*(i64)f5 + f1_2*(i64)f4 + f2_2*(i64)f3 + f6 *(i64)f9_38 + f7_2*(i64)f8_19; - i64 h6 = f0_2*(i64)f6 + f1_2*(i64)f5_2 + f2_2*(i64)f4 + i64 t6 = f0_2*(i64)f6 + f1_2*(i64)f5_2 + f2_2*(i64)f4 + f3_2*(i64)f3 + f7_2*(i64)f9_38 + f8 *(i64)f8_19; - i64 h7 = f0_2*(i64)f7 + f1_2*(i64)f6 + f2_2*(i64)f5 + i64 t7 = f0_2*(i64)f7 + f1_2*(i64)f6 + f2_2*(i64)f5 + f3_2*(i64)f4 + f8 *(i64)f9_38; - i64 h8 = f0_2*(i64)f8 + f1_2*(i64)f7_2 + f2_2*(i64)f6 + i64 t8 = f0_2*(i64)f8 + f1_2*(i64)f7_2 + f2_2*(i64)f6 + f3_2*(i64)f5_2 + f4 *(i64)f4 + f9 *(i64)f9_38; - i64 h9 = f0_2*(i64)f9 + f1_2*(i64)f8 + f2_2*(i64)f7 + i64 t9 = f0_2*(i64)f9 + f1_2*(i64)f8 + f2_2*(i64)f7 + f3_2*(i64)f6 + f4 *(i64)f5_2; - CARRY; + FE_CARRY; } // h = 2 * (f^2) -- 2.47.3