)]}' { "commit": "32e0d1006953ab2bdd83afbd26b564b7dd894625", "tree": "904a4fb22fc3b4d3a12678d7c86195321b7727bc", "parents": [ "6a289b3ec439d24729cdbdb69b8d99b82a9904fc" ], "author": { "name": "David Benjamin", "email": "davidben@google.com", "time": "Sun Apr 22 21:39:34 2018 -0400" }, "committer": { "name": "Adam Langley", "email": "agl@google.com", "time": "Wed Apr 25 16:39:58 2018 +0000" }, "message": "Add EC_FELEM for EC_POINTs and related temporaries.\n\nThis introduces EC_FELEM, which is analogous to EC_SCALAR. It is used\nfor EC_POINT\u0027s representation in the generic EC_METHOD, as well as\nrandom operations on tuned EC_METHODs that still are implemented\ngenericly.\n\nUnlike EC_SCALAR, EC_FELEM\u0027s exact representation is awkwardly specific\nto the EC_METHOD, analogous to how the old values were BIGNUMs but may\nor may not have been in Montgomery form. This is kind of a nuisance, but\nno more than before. (If p224-64.c were easily convertable to Montgomery\nform, we could say |EC_FELEM| is always in Montgomery form. If we\nexposed the internal add and double implementations in each of the\ncurves, we could give |EC_POINT| an |EC_METHOD|-specific representation\nand |EC_FELEM| is purely a |EC_GFp_mont_method| type. I\u0027ll leave this\nfor later.)\n\nThe generic add and doubling formulas are aligned with the formulas\nproved in fiat-crypto. Those only applied to a \u003d -3, so I\u0027ve proved a\ngeneric one in https://github.com/mit-plv/fiat-crypto/pull/356, in case\nsomeone uses a custom curve. The new formulas are verified,\nconstant-time, and swap a multiply for a square. As expressed in\nfiat-crypto they do use more temporaries, but this seems to be fine with\nstack-allocated EC_FELEMs. (We can try to help the compiler later,\nbut benchamrks below suggest this isn\u0027t necessary.)\n\nUnlike BIGNUM, EC_FELEM can be stack-allocated. It also captures the\nbounds in the type system and, in particular, that the width is correct,\nwhich will make it easier to select a point in constant-time in the\nfuture. (Indeed the old code did not always have the correct width. Its\npoint formula involved halving and implemented this in variable time and\nvariable width.)\n\nBefore:\nDid 77274 ECDH P-256 operations in 10046087us (7692.0 ops/sec)\nDid 5959 ECDH P-384 operations in 10031701us (594.0 ops/sec)\nDid 10815 ECDSA P-384 signing operations in 10087892us (1072.1 ops/sec)\nDid 8976 ECDSA P-384 verify operations in 10071038us (891.3 ops/sec)\nDid 2600 ECDH P-521 operations in 10091688us (257.6 ops/sec)\nDid 4590 ECDSA P-521 signing operations in 10055195us (456.5 ops/sec)\nDid 3811 ECDSA P-521 verify operations in 10003574us (381.0 ops/sec)\n\nAfter:\nDid 77736 ECDH P-256 operations in 10029858us (7750.5 ops/sec) [+0.8%]\nDid 7519 ECDH P-384 operations in 10068076us (746.8 ops/sec) [+25.7%]\nDid 13335 ECDSA P-384 signing operations in 10029962us (1329.5 ops/sec) [+24.0%]\nDid 11021 ECDSA P-384 verify operations in 10088600us (1092.4 ops/sec) [+22.6%]\nDid 2912 ECDH P-521 operations in 10001325us (291.2 ops/sec) [+13.0%]\nDid 5150 ECDSA P-521 signing operations in 10027462us (513.6 ops/sec) [+12.5%]\nDid 4264 ECDSA P-521 verify operations in 10069694us (423.4 ops/sec) [+11.1%]\n\nThis more than pays for removing points_make_affine previously and even\nspeeds up ECDH P-256 slightly. (The point-on-curve check uses the\ngeneric code.)\n\nNext is to push the stack-allocating up to ec_wNAF_mul, followed by a\nconstant-time single-point multiplication.\n\nBug: 239\nChange-Id: I44a2dff7c52522e491d0f8cffff64c4ab5cd353c\nReviewed-on: https://boringssl-review.googlesource.com/27668\nReviewed-by: Adam Langley \u003cagl@google.com\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "f3823132ec86b6bf8da8206248ec37a5a36a176e", "old_mode": 33188, "old_path": "crypto/fipsmodule/bcm.c", "new_id": "5d9ebfc726a68f770c8497c7fdea531d14e266f8", "new_mode": 33188, "new_path": "crypto/fipsmodule/bcm.c" }, { "type": "modify", "old_id": "1950561ef99ab21083fe3ec23be1f81c469aa2da", "old_mode": 33188, "old_path": "crypto/fipsmodule/bn/div.c", "new_id": "a350fbfa3158c6717ced5102b96aff2be28dc2a5", "new_mode": 33188, "new_path": "crypto/fipsmodule/bn/div.c" }, { "type": "modify", "old_id": "2fc38df876903add42cbd67aa0e4ae2950160fd9", "old_mode": 33188, "old_path": "crypto/fipsmodule/bn/internal.h", "new_id": "ab2a9256034668d3ca9aab03791d9818da5dd450", "new_mode": 33188, "new_path": "crypto/fipsmodule/bn/internal.h" }, { "type": "modify", "old_id": "1b6832768ebcb3e5d1fdb5b672e92aba5dbb0c72", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/ec.c", "new_id": "b559b541e0f3f8233b5e83cb19dfd1b720ba86c9", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/ec.c" }, { "type": "modify", "old_id": "d80fa23c614b9e585de565d165003256d786f39a", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/ec_montgomery.c", "new_id": "c90b9f1c65b268325324e7c8f2cc49a4b9d3aba1", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/ec_montgomery.c" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "d32ff23d509fa50566b1b9a5345849c2e5747673", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/felem.c" }, { "type": "modify", "old_id": "66e18436373035dc1bac6557e55765fe77187a4e", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/internal.h", "new_id": "891591f6cd7224f7d65345b421f7921849747459", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/internal.h" }, { "type": "modify", "old_id": "0a379fe6ee49c96e1e7f58702970f3f4cb4ce8da", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p224-64.c", "new_id": "96ca04112350f12e7eb29173fddd67df82494316", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p224-64.c" }, { "type": "modify", "old_id": "d8d3a399123c71a01bc6f0da4b875f24f5386441", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p256-x86_64.c", "new_id": "ea9749f60f8d01fdc51ed6331fa301ecd8f3a06f", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p256-x86_64.c" }, { "type": "modify", "old_id": "511788c47540e39ec8e7ee89fb632f45a3b9f009", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/simple.c", "new_id": "995b421c8e365d88bfdece4ac3ffe9a1550855d5", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/simple.c" }, { "type": "modify", "old_id": "02719c5562417dcae874d03f33adf9f0c0e2fef0", "old_mode": 33188, "old_path": "third_party/fiat/p256.c", "new_id": "53ae9ed1e0c35999c5625b8f2d490c8669a42eb4", "new_mode": 33188, "new_path": "third_party/fiat/p256.c" } ] }