)]}' { "commit": "3d450d2844db825a906fc19f7bb1e6ce765047db", "tree": "47cd307935f4e8e74eba618187fdaa6a666bd2c2", "parents": [ "7f7e5e231efec6e86d6c7d3fd1b759be1cece156" ], "author": { "name": "Nir Drucker", "email": "ndrucker@amazon.com", "time": "Fri Aug 24 10:18:09 2018 +0300" }, "committer": { "name": "CQ bot account: commit-bot@chromium.org", "email": "commit-bot@chromium.org", "time": "Mon Nov 05 23:48:07 2018 +0000" }, "message": "Speed up ECDSA verify on x86-64.\n\nThis commit improves the performance of ECDSA signature verification\n(over NIST P-256 curve) for x86 platforms. The speedup is by a factor of 1.15x.\nIt does so by:\n 1) Leveraging the fact that the verification does not need\n to run in constant time. To this end, we implemented:\n a) the function ecp_nistz256_points_mul_public in a similar way to\n the current ecp_nistz256_points_mul function by removing its constant\n time features.\n b) the Binary Extended Euclidean Algorithm (BEEU) in x86 assembly to\n replace the current modular inverse function used for the inversion.\n 2) The last step in the ECDSA_verify function compares the (x) affine\n coordinate with the signature (r) value. Converting x from the Jacobian\u0027s\n representation to the affine coordinate requires to perform one inversions\n (x_affine \u003d x * z^(-2)). We save this inversion and speed up the computations\n by instead bringing r to x (r_jacobian \u003d r*z^2) which is faster.\n\nThe measured results are:\nBefore (on a Kaby Lake desktop with gcc-5):\nDid 26000 ECDSA P-224 signing operations in 1002372us (25938.5 ops/sec)\nDid 11000 ECDSA P-224 verify operations in 1043821us (10538.2 ops/sec)\nDid 55000 ECDSA P-256 signing operations in 1017560us (54050.9 ops/sec)\nDid 17000 ECDSA P-256 verify operations in 1051280us (16170.8 ops/sec)\n\nAfter (on a Kaby Lake desktop with gcc-5):\nDid 27000 ECDSA P-224 signing operations in 1011287us (26698.7 ops/sec)\nDid 11640 ECDSA P-224 verify operations in 1076698us (10810.8 ops/sec)\nDid 55000 ECDSA P-256 signing operations in 1016880us (54087.0 ops/sec)\nDid 20000 ECDSA P-256 verify operations in 1038736us (19254.2 ops/sec)\n\nBefore (on a Skylake server platform with gcc-5):\nDid 25000 ECDSA P-224 signing operations in 1021651us (24470.2 ops/sec)\nDid 10373 ECDSA P-224 verify operations in 1046563us (9911.5 ops/sec)\nDid 50000 ECDSA P-256 signing operations in 1002774us (49861.7 ops/sec)\nDid 15000 ECDSA P-256 verify operations in 1006471us (14903.6 ops/sec)\n\nAfter (on a Skylake server platform with gcc-5):\nDid 25000 ECDSA P-224 signing operations in 1020958us (24486.8 ops/sec)\nDid 10373 ECDSA P-224 verify operations in 1046359us (9913.4 ops/sec)\nDid 50000 ECDSA P-256 signing operations in 1003996us (49801.0 ops/sec)\nDid 18000 ECDSA P-256 verify operations in 1021604us (17619.4 ops/sec)\n\nDevelopers and authors:\n***************************************************************************\nNir Drucker (1,2), Shay Gueron (1,2)\n(1) Amazon Web Services Inc.\n(2) University of Haifa, Israel\n***************************************************************************\n\nChange-Id: Idd42a7bc40626bce974ea000b61fdb5bad33851c\nReviewed-on: https://boringssl-review.googlesource.com/c/31304\nCommit-Queue: Adam Langley \u003cagl@google.com\u003e\nCQ-Verified: CQ bot account: commit-bot@chromium.org \u003ccommit-bot@chromium.org\u003e\nReviewed-by: David Benjamin \u003cdavidben@google.com\u003e\nReviewed-by: Adam Langley \u003cagl@google.com\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "e6c8cc69eca6ed9913173a03d4af27917614e21c", "old_mode": 33188, "old_path": "crypto/fipsmodule/CMakeLists.txt", "new_id": "463febbf82fe2dfc56cf4378fde3e322eb5b1b32", "new_mode": 33188, "new_path": "crypto/fipsmodule/CMakeLists.txt" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "12b9f5af2e9db7f6e799f084495cb2828c8cab89", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/asm/p256_beeu-x86_64-asm.pl" }, { "type": "modify", "old_id": "908e35e9d04e657c13ba61c8ea5bf4a4519228c5", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/ec.c", "new_id": "e9b1e978e264dfa005915ccc6a866d4c2056497c", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/ec.c" }, { "type": "modify", "old_id": "9eace95f3dbad59ffee1026acd5871f9674df6a6", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/ec_montgomery.c", "new_id": "cd6bbfd7aa0c07482385375a119a451eb21ab555", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/ec_montgomery.c" }, { "type": "modify", "old_id": "bb172b26062a5a6ab8dcea71875565e23d527a6e", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/internal.h", "new_id": "02cd04ac325ea3bd4db66c27bfc0ea01b42cfca2", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/internal.h" }, { "type": "modify", "old_id": "606108fc051ca4573f0d9dd5bb9971ed74fb6538", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p224-64.c", "new_id": "8c7a812f0f3d2bc9910cf46f3b109ea08e3d4fad", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p224-64.c" }, { "type": "modify", "old_id": "a4f65156bd5bdc7a489c1cc618661af3dce2229c", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p256-x86_64.c", "new_id": "e630cb7769c323af733f4dc0942915c4b38a717c", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p256-x86_64.c" }, { "type": "modify", "old_id": "21b461cf1798b2058d12a4c790e820f589d301c4", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p256-x86_64.h", "new_id": "9de32406e010232bbcefb969609e643cf2e8fa64", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p256-x86_64.h" }, { "type": "modify", "old_id": "8ed1dd4d4e5ddde6aa47eeedeedfb6a22625c4ae", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/p256-x86_64_test.cc", "new_id": "68749e23ccc2f716c8db153e0d295b7e64d9e1ab", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/p256-x86_64_test.cc" }, { "type": "modify", "old_id": "1bd6b02494f329e657cb5f701fcc1e38ecba26a0", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/scalar.c", "new_id": "88678a932185fea4e8a3701db6a99c7e053e779f", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/scalar.c" }, { "type": "modify", "old_id": "5c637118dc9af61d829a4a6d6456fa270c4b833d", "old_mode": 33188, "old_path": "crypto/fipsmodule/ec/simple.c", "new_id": "854da1efce35f5ee19c19b30f7a8f34b13069666", "new_mode": 33188, "new_path": "crypto/fipsmodule/ec/simple.c" }, { "type": "modify", "old_id": "f3ce214774b3d8cfc7e2550e3b15f0c7faf499e9", "old_mode": 33188, "old_path": "crypto/fipsmodule/ecdsa/ecdsa.c", "new_id": "7ec45655498eb641e8f526394d1a277871192c1b", "new_mode": 33188, "new_path": "crypto/fipsmodule/ecdsa/ecdsa.c" }, { "type": "modify", "old_id": "f42f8fe28f169055ad727eef054548bf0fc7c402", "old_mode": 33188, "old_path": "third_party/fiat/p256.c", "new_id": "e962d5600689ddd145b7bc9ce0e35c9900fa5834", "new_mode": 33188, "new_path": "third_party/fiat/p256.c" } ] }