![Please Enable Javascript]()
{"schema":"libjg2-1",
"vpath":"/git/",
"avatar":"/git/avatar/",
"alang":"",
"gen_ut":1747977766,
"reponame":"openssl",
"desc":"OpenSSL",
"owner": { "name": "Andy Green", "email": "andy@warmcat.com", "md5": "c50933ca2aa61e0fe2c43d46bb6b59cb" },"url":"https://warmcat.com/repo/openssl",
"f":3,
"items": [
{"schema":"libjg2-1",
"cid":"0b355be403918a68c96c124ff28783eb",
"commit": {"type":"commit",
"time": 1515357164,
"time_ofs": 60,
"oid_tree": { "oid": "9ac322323e2a200e963112d3471084c9c3cb129a", "alias": []},
"oid":{ "oid": "10bc3409459a525654d6b986b3cd49d22dd95460", "alias": []},
"msg": "ec/ecp_nistz256.c: switch to faster addition chain in scalar inversion.",
"sig_commit": { "git_time": { "time": 1515357164, "offset": 60 }, "name": "Andy Polyakov", "email": "appro@openssl.org", "md5": "50bd64fa2a792cbbf679fa16213a3b2a" },
"sig_author": { "git_time": { "time": 1514661344, "offset": 60 }, "name": "Andy Polyakov", "email": "appro@openssl.org", "md5": "50bd64fa2a792cbbf679fa16213a3b2a" }},
"body": "ec/ecp_nistz256.c: switch to faster addition chain in scalar inversion.\n\n[and improve formatting]\n\nReviewed-by: Rich Salz \u003crsalz@openssl.org\u003e\n(Merged from https://github.com/openssl/openssl/pull/5001)\n"
,
"diff": "diff --git a/crypto/ec/ecp_nistz256.c b/crypto/ec/ecp_nistz256.c\nindex 6bae3d1..08a7e84 100644\n--- a/crypto/ec/ecp_nistz256.c\n+++ b/crypto/ec/ecp_nistz256.c\n@@ -1515,19 +1515,14 @@ static int ecp_nistz256_inv_mod_ord(const EC_GROUP *group, BIGNUM *r,\n BIGNUM *x, BN_CTX *ctx)\n {\n /* RR \u003d 2^512 mod ord(p256) */\n- static const BN_ULONG RR[P256_LIMBS] \u003d { TOBN(0x83244c95,0xbe79eea2),\n- TOBN(0x4699799c,0x49bd6fa6),\n- TOBN(0x2845b239,0x2b6bec59),\n- TOBN(0x66e12d94,0xf3d95620) };\n+ static const BN_ULONG RR[P256_LIMBS] \u003d {\n+ TOBN(0x83244c95,0xbe79eea2), TOBN(0x4699799c,0x49bd6fa6),\n+ TOBN(0x2845b239,0x2b6bec59), TOBN(0x66e12d94,0xf3d95620)\n+ };\n /* The constant 1 (unlike ONE that is one in Montgomery representation) */\n- static const BN_ULONG one[P256_LIMBS] \u003d { TOBN(0,1),TOBN(0,0),\n- TOBN(0,0),TOBN(0,0) };\n- /* expLo - the low 128bit of the exponent we use (ord(p256) - 2),\n- * split into 4bit windows */\n- static const unsigned char expLo[32] \u003d { 0xb,0xc,0xe,0x6,0xf,0xa,0xa,0xd,\n- 0xa,0x7,0x1,0x7,0x9,0xe,0x8,0x4,\n- 0xf,0x3,0xb,0x9,0xc,0xa,0xc,0x2,\n- 0xf,0xc,0x6,0x3,0x2,0x5,0x4,0xf };\n+ static const BN_ULONG one[P256_LIMBS] \u003d {\n+ TOBN(0,1), TOBN(0,0), TOBN(0,0), TOBN(0,0)\n+ };\n /*\n * We don't use entry 0 in the table, so we omit it and address\n * with -1 offset.\n@@ -1561,6 +1556,10 @@ static int ecp_nistz256_inv_mod_ord(const EC_GROUP *group, BIGNUM *r,\n }\n \n ecp_nistz256_ord_mul_mont(table[0], t, RR);\n+#if 0\n+ /*\n+ * Original sparse-then-fixed-window algorithm, retained for reference.\n+ */\n for (i \u003d 2; i \u003c 16; i +\u003d 2) {\n ecp_nistz256_ord_sqr_mont(table[i-1], table[i/2-1], 1);\n ecp_nistz256_ord_mul_mont(table[i], table[i-1], table[0]);\n@@ -1586,13 +1585,85 @@ static int ecp_nistz256_inv_mod_ord(const EC_GROUP *group, BIGNUM *r,\n ecp_nistz256_ord_mul_mont(out, out, t); /* ffffffff00000000ffffffffffffffff */\n \n /*\n- * The bottom 128 bit of the exponent are easier done with a table\n+ * The bottom 128 bit of the exponent are processed with fixed 4-bit window\n */\n for(i \u003d 0; i \u003c 32; i++) {\n+ /* expLo - the low 128 bits of the exponent we use (ord(p256) - 2),\n+ * split into nibbles */\n+ static const unsigned char expLo[32] \u003d {\n+ 0xb,0xc,0xe,0x6,0xf,0xa,0xa,0xd,0xa,0x7,0x1,0x7,0x9,0xe,0x8,0x4,\n+ 0xf,0x3,0xb,0x9,0xc,0xa,0xc,0x2,0xf,0xc,0x6,0x3,0x2,0x5,0x4,0xf\n+ };\n+\n ecp_nistz256_ord_sqr_mont(out, out, 4);\n /* The exponent is public, no need in constant-time access */\n ecp_nistz256_ord_mul_mont(out, out, table[expLo[i]-1]);\n }\n+#else\n+ /*\n+ * https://briansmith.org/ecc-inversion-addition-chains-01#p256_scalar_inversion\n+ *\n+ * Even though this code path spares 12 squarings, 4.5%, and 13\n+ * multiplications, 25%, on grand scale sign operation is not that\n+ * much faster, not more that 2%...\n+ */\n+ enum {\n+ i_1 \u003d 0, i_10, i_11, i_101, i_111, i_1010, i_1111,\n+ i_10101, i_101010, i_101111, i_x6, i_x8, i_x16, i_x32\n+ };\n+\n+ /* pre-calculate powers */\n+ ecp_nistz256_ord_sqr_mont(table[i_10], table[i_1], 1);\n+\n+ ecp_nistz256_ord_mul_mont(table[i_11], table[i_1], table[i_10]);\n+\n+ ecp_nistz256_ord_mul_mont(table[i_101], table[i_11], table[i_10]);\n+\n+ ecp_nistz256_ord_mul_mont(table[i_111], table[i_101], table[i_10]);\n+\n+ ecp_nistz256_ord_sqr_mont(table[i_1010], table[i_101], 1);\n+\n+ ecp_nistz256_ord_mul_mont(table[i_1111], table[i_1010], table[i_101]);\n+\n+ ecp_nistz256_ord_sqr_mont(table[i_10101], table[i_1010], 1);\n+ ecp_nistz256_ord_mul_mont(table[i_10101], table[i_10101], table[i_1]);\n+\n+ ecp_nistz256_ord_sqr_mont(table[i_101010], table[i_10101], 1);\n+\n+ ecp_nistz256_ord_mul_mont(table[i_101111], table[i_101010], table[i_101]);\n+\n+ ecp_nistz256_ord_mul_mont(table[i_x6], table[i_101010], table[i_10101]);\n+\n+ ecp_nistz256_ord_sqr_mont(table[i_x8], table[i_x6], 2);\n+ ecp_nistz256_ord_mul_mont(table[i_x8], table[i_x8], table[i_11]);\n+\n+ ecp_nistz256_ord_sqr_mont(table[i_x16], table[i_x8], 8);\n+ ecp_nistz256_ord_mul_mont(table[i_x16], table[i_x16], table[i_x8]);\n+\n+ ecp_nistz256_ord_sqr_mont(table[i_x32], table[i_x16], 16);\n+ ecp_nistz256_ord_mul_mont(table[i_x32], table[i_x32], table[i_x16]);\n+\n+ /* calculations */\n+ ecp_nistz256_ord_sqr_mont(out, table[i_x32], 64);\n+ ecp_nistz256_ord_mul_mont(out, out, table[i_x32]);\n+\n+ for (i \u003d 0; i \u003c 27; i++) {\n+ static const struct { unsigned char p, i; } chain[27] \u003d {\n+ { 32, i_x32 }, { 6, i_101111 }, { 5, i_111 },\n+ { 4, i_11 }, { 5, i_1111 }, { 5, i_10101 },\n+ { 4, i_101 }, { 3, i_101 }, { 3, i_101 },\n+ { 5, i_111 }, { 9, i_101111 }, { 6, i_1111 },\n+ { 2, i_1 }, { 5, i_1 }, { 6, i_1111 },\n+ { 5, i_111 }, { 4, i_111 }, { 5, i_111 },\n+ { 5, i_101 }, { 3, i_11 }, { 10, i_101111 },\n+ { 2, i_11 }, { 5, i_11 }, { 5, i_11 },\n+ { 3, i_1 }, { 7, i_10101 }, { 6, i_1111 }\n+ };\n+\n+ ecp_nistz256_ord_sqr_mont(out, out, chain[i].p);\n+ ecp_nistz256_ord_mul_mont(out, out, table[chain[i].i]);\n+ }\n+#endif\n ecp_nistz256_ord_mul_mont(out, out, one);\n \n /*\n@@ -1659,7 +1730,7 @@ const EC_METHOD *EC_GFp_nistz256_method(void)\n 0, /* keycopy */\n 0, /* keyfinish */\n ecdh_simple_compute_key,\n- ecp_nistz256_inv_mod_ord /* can be #defined-ed NULL */\n+ ecp_nistz256_inv_mod_ord /* can be #define-d NULL */\n };\n \n return \u0026ret;\n","s":{"c":1747633378,"u": 36288}}
],"g": 2138,"chitpc": 0,"ehitpc": 0,"indexed":0
,
"ab": 0, "si": 0, "db":0, "di":0, "sat":0, "lfc": "7d0a"}