crypto/ecdsa: use bigmod and nistec instead of math/big and crypto/elliptic

Ignoring custom curves, this makes the whole package constant-time.
There is a slight loss in performance for P-384 and P-521 because bigmod
is slower than math/big (but P-256 has an assembly scalar field
inversion, so doesn't use bigmod for anything big).

name                old time/op    new time/op    delta
Sign/P256-8           19.2µs ± 2%    19.1µs ± 2%     ~     (p=0.268 n=9+10)
Sign/P384-8            166µs ± 3%     188µs ± 2%  +13.52%  (p=0.000 n=10+10)
Sign/P521-8            337µs ± 2%     359µs ± 2%   +6.46%  (p=0.000 n=10+10)
Verify/P256-8         58.1µs ± 2%    58.1µs ± 2%     ~     (p=0.971 n=10+10)
Verify/P384-8          484µs ± 2%     569µs ±12%  +17.65%  (p=0.000 n=10+10)
Verify/P521-8         1.03ms ± 4%    1.14ms ± 2%  +11.02%  (p=0.000 n=10+10)
GenerateKey/P256-8    12.4µs ±12%    12.0µs ± 2%     ~     (p=0.063 n=10+10)
GenerateKey/P384-8     129µs ±18%     119µs ± 2%     ~     (p=0.190 n=10+10)
GenerateKey/P521-8     241µs ± 2%     240µs ± 2%     ~     (p=0.436 n=10+10)

name                old alloc/op   new alloc/op   delta
Sign/P256-8           3.08kB ± 0%    2.47kB ± 0%  -19.77%  (p=0.000 n=10+10)
Sign/P384-8           6.16kB ± 0%    2.64kB ± 0%  -57.16%  (p=0.000 n=10+10)
Sign/P521-8           7.87kB ± 0%    3.01kB ± 0%  -61.80%  (p=0.000 n=10+10)
Verify/P256-8         1.29kB ± 1%    0.48kB ± 0%  -62.69%  (p=0.000 n=10+10)
Verify/P384-8         2.49kB ± 1%    0.64kB ± 0%  -74.25%  (p=0.000 n=10+10)
Verify/P521-8         3.31kB ± 0%    0.96kB ± 0%  -71.02%  (p=0.000 n=7+10)
GenerateKey/P256-8      720B ± 0%      920B ± 0%  +27.78%  (p=0.000 n=10+10)
GenerateKey/P384-8      921B ± 0%     1120B ± 0%  +21.61%  (p=0.000 n=9+10)
GenerateKey/P521-8    1.30kB ± 0%    1.44kB ± 0%  +10.45%  (p=0.000 n=10+10)

name                old allocs/op  new allocs/op  delta
Sign/P256-8             45.0 ± 0%      33.0 ± 0%  -26.67%  (p=0.000 n=10+10)
Sign/P384-8             69.0 ± 0%      34.0 ± 0%  -50.72%  (p=0.000 n=10+10)
Sign/P521-8             71.0 ± 0%      35.0 ± 0%  -50.70%  (p=0.000 n=10+10)
Verify/P256-8           23.0 ± 0%      10.0 ± 0%  -56.52%  (p=0.000 n=10+10)
Verify/P384-8           43.0 ± 0%      14.0 ± 0%  -67.44%  (p=0.000 n=10+10)
Verify/P521-8           45.0 ± 0%      14.0 ± 0%  -68.89%  (p=0.000 n=7+10)
GenerateKey/P256-8      13.0 ± 0%      14.0 ± 0%   +7.69%  (p=0.000 n=10+10)
GenerateKey/P384-8      16.0 ± 0%      17.0 ± 0%   +6.25%  (p=0.000 n=10+10)
GenerateKey/P521-8      16.5 ± 3%      17.0 ± 0%   +3.03%  (p=0.033 n=10+10)

Change-Id: I4e074ef039b0f7ffbc436a4cdbe4ef90c647018d
Reviewed-on: https://go-review.googlesource.com/c/go/+/353849
Auto-Submit: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Than McIntosh <thanm@google.com>
Reviewed-by: David Chase <drchase@google.com>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Roland Shoemaker <roland@golang.org>

1 files changed, 40 insertions, 40 deletions

diff --git a/src/crypto/tls/testdata/Client-TLSv10-ClientCert-ECDSA-RSA b/src/crypto/tls/testdata/Client-TLSv10-ClientCert-ECDSA-RSA
index 81e5191925..afe6e10906 100644
--- a/src/crypto/tls/testdata/Client-TLSv10-ClientCert-ECDSA-RSA
+++ b/src/crypto/tls/testdata/Client-TLSv10-ClientCert-ECDSA-RSA
@@ -16,11 +16,11 @@
 000000e0  e5 7d a3 47 cd 62 43 15  28 da ac 5f bb 29 07 30  |.}.G.bC.(.._.).0|
 000000f0  ff f6 84 af c4 cf c2 ed  90 99 5f 58 cb 3b 74     |.........._X.;t|
 >>> Flow 2 (server to client)
-00000000  16 03 01 00 59 02 00 00  55 03 01 ca 72 6a a1 69  |....Y...U...rj.i|
-00000010  18 a4 f8 76 4a c3 5c e8  d5 c1 fb 06 c6 9a 14 67  |...vJ.\........g|
-00000020  ce e4 f6 52 67 ab 64 48  28 5a 63 20 55 ea ff 87  |...Rg.dH(Zc U...|
-00000030  5a 78 5c cb 21 af 83 a5  ed 1b d3 2c 39 81 e5 ca  |Zx\.!......,9...|
-00000040  63 d2 5c 57 27 1d d0 f9  41 40 43 b0 c0 13 00 00  |c.\W'...A@C.....|
+00000000  16 03 01 00 59 02 00 00  55 03 01 b5 1a 96 ea d5  |....Y...U.......|
+00000010  01 ef fb 42 1d 49 e1 1b  7c e4 15 ec cc 7f b9 fc  |...B.I..|.......|
+00000020  22 e0 0b 1d 66 0e c8 d6  9b cd ec 20 d5 2b fe 9a  |"...f...... .+..|
+00000030  f7 e7 10 1c c4 15 10 f1  24 8d 8f f6 25 90 aa 1c  |........$...%...|
+00000040  10 c4 87 c6 36 23 5b 6a  c1 ae 20 5e c0 13 00 00  |....6#[j.. ^....|
 00000050  0d ff 01 00 01 00 00 0b  00 04 03 00 01 02 16 03  |................|
 00000060  01 02 59 0b 00 02 55 00  02 52 00 02 4f 30 82 02  |..Y...U..R..O0..|
 00000070  4b 30 82 01 b4 a0 03 02  01 02 02 09 00 e8 f0 9d  |K0..............|
@@ -60,17 +60,17 @@
 00000290  77 8d 0c 1c f1 0f a1 d8  40 83 61 c9 4c 72 2b 9d  |w.......@.a.Lr+.|
 000002a0  ae db 46 06 06 4d f4 c1  b3 3e c0 d1 bd 42 d4 db  |..F..M...>...B..|
 000002b0  fe 3d 13 60 84 5c 21 d3  3b e9 fa e7 16 03 01 00  |.=.`.\!.;.......|
-000002c0  aa 0c 00 00 a6 03 00 1d  20 e8 a5 9c e4 73 3d 75  |........ ....s=u|
-000002d0  0c 3e f2 de 21 9c 0f 91  b4 fd 94 f0 27 f6 d9 7d  |.>..!.......'..}|
-000002e0  cd 0c 4c 50 b0 47 db dd  12 00 80 04 c0 be d5 bb  |..LP.G..........|
-000002f0  e8 e2 a2 2e d9 2e 75 fa  b6 07 d0 f7 75 52 fb 2f  |......u.....uR./|
-00000300  50 cd 43 68 bd 42 11 6d  d6 9f a3 d1 00 fd a9 14  |P.Ch.B.m........|
-00000310  0c 2a dd 76 ea 73 21 52  00 3a 83 cf d7 07 c7 bd  |.*.v.s!R.:......|
-00000320  78 21 ce 35 80 b3 06 22  f1 96 a7 20 41 f8 aa 61  |x!.5..."... A..a|
-00000330  94 b4 77 d4 d9 92 f2 66  c5 1c d1 82 f3 b9 e2 9d  |..w....f........|
-00000340  a9 30 1c e2 4e ec 0d 32  3d 0d 61 22 c8 e5 95 9f  |.0..N..2=.a"....|
-00000350  cf 3e fc a8 c5 c3 f8 45  45 29 ea a7 e7 b7 a6 17  |.>.....EE)......|
-00000360  9e 5f 83 d4 b3 f0 da 31  73 94 f2 16 03 01 00 0a  |._.....1s.......|
+000002c0  aa 0c 00 00 a6 03 00 1d  20 87 d5 d1 27 70 92 d9  |........ ...'p..|
+000002d0  15 56 e4 fd a8 52 a9 a5  f6 db ab f5 e2 61 fa 5d  |.V...R.......a.]|
+000002e0  64 ba c2 ee 37 0b 53 cf  3c 00 80 71 cd eb 4b 1c  |d...7.S.<..q..K.|
+000002f0  f7 84 85 6a 20 5c c8 40  59 1c b0 8e 1b b6 b6 19  |...j \.@Y.......|
+00000300  f1 66 ad 7d 1d d5 58 da  c3 c4 dd 12 57 04 05 0d  |.f.}..X.....W...|
+00000310  79 46 20 0b 8c a3 49 95  e0 96 22 75 56 44 21 6b  |yF ...I..."uVD!k|
+00000320  42 17 ed 32 eb 9c f3 fd  b0 b3 08 da 61 7e f3 9b  |B..2........a~..|
+00000330  43 51 c0 09 e3 53 17 5d  84 3f c4 52 db 73 f9 d1  |CQ...S.].?.R.s..|
+00000340  21 0e 55 a4 bc a1 1b b6  3a 5a d1 cb 15 7e 8b a4  |!.U.....:Z...~..|
+00000350  fb 0f e7 7e 36 a7 1b a4  c0 1f 79 37 49 17 84 d3  |...~6.....y7I...|
+00000360  97 39 78 1f 55 77 e8 aa  37 2a 36 16 03 01 00 0a  |.9x.Uw..7*6.....|
 00000370  0d 00 00 06 03 01 02 40  00 00 16 03 01 00 04 0e  |.......@........|
 00000380  00 00 00                                          |...|
 >>> Flow 3 (client to server)
@@ -110,29 +110,29 @@
 00000210  03 01 00 25 10 00 00 21  20 2f e5 7d a3 47 cd 62  |...%...! /.}.G.b|
 00000220  43 15 28 da ac 5f bb 29  07 30 ff f6 84 af c4 cf  |C.(.._.).0......|
 00000230  c2 ed 90 99 5f 58 cb 3b  74 16 03 01 00 91 0f 00  |...._X.;t.......|
-00000240  00 8d 00 8b 30 81 88 02  42 00 9a b9 f6 98 e3 ed  |....0...B.......|
-00000250  ed 0d a3 0e 54 51 9f 73  d4 87 40 4e a9 39 4b 2d  |....TQ.s..@N.9K-|
-00000260  2a b9 4d 8d e3 46 c3 b6  39 f2 ca a9 c9 0f 79 c1  |*.M..F..9.....y.|
-00000270  0c 90 6f de 58 97 72 fc  a8 c1 4c 12 aa a4 85 57  |..o.X.r...L....W|
-00000280  50 7c a0 02 8a 12 c5 80  aa b6 39 02 42 00 9c b7  |P|........9.B...|
-00000290  95 b4 04 83 5b 3a e1 ac  da 78 86 11 f5 30 75 4a  |....[:...x...0uJ|
-000002a0  25 67 6c fd ef 5a d8 56  d3 60 93 cf 65 07 2b 1f  |%gl..Z.V.`..e.+.|
-000002b0  a9 40 a8 ba cd 0e 41 2d  10 43 a4 61 93 b7 0a 11  |.@....A-.C.a....|
-000002c0  78 d1 72 2b 20 07 49 5a  76 02 17 57 87 78 c7 14  |x.r+ .IZv..W.x..|
-000002d0  03 01 00 01 01 16 03 01  00 30 93 de 1b 64 0e 56  |.........0...d.V|
-000002e0  d9 a8 da f7 37 cb ac ac  3e f5 e2 f9 87 19 f2 79  |....7...>......y|
-000002f0  24 76 19 a4 a2 41 d6 9e  7d ca aa 3e 1d d7 22 dd  |$v...A..}..>..".|
-00000300  05 aa dd 74 03 db fd a2  de ee                    |...t......|
+00000240  00 8d 00 8b 30 81 88 02  42 01 e7 32 ab 5d d7 f8  |....0...B..2.]..|
+00000250  b6 25 f9 b6 e6 19 eb 20  75 99 90 bc 41 06 74 ce  |.%..... u...A.t.|
+00000260  92 31 fc 9e cd f3 b4 b1  b1 f7 1e d3 3c 5e 01 92  |.1..........<^..|
+00000270  a0 c6 24 05 6e 3b ba 6c  51 61 6c 11 fd fe d7 9f  |..$.n;.lQal.....|
+00000280  0b 16 b3 1a f7 20 fa b2  3d 92 c9 02 42 01 d7 dc  |..... ..=...B...|
+00000290  20 50 f6 91 a3 63 2a 79  37 d4 8b 71 0a 1e 73 f8  | P...c*y7..q..s.|
+000002a0  1e 1c 04 c5 c8 66 bc 5e  67 5e bb 94 76 87 23 12  |.....f.^g^..v.#.|
+000002b0  64 18 cb 09 66 58 f1 06  17 93 1e b9 83 67 9d 3d  |d...fX.......g.=|
+000002c0  39 0a fb 37 7b a9 bf d2  59 1a 49 0f 4c 10 df 14  |9..7{...Y.I.L...|
+000002d0  03 01 00 01 01 16 03 01  00 30 4f 0e ba fc 20 81  |.........0O... .|
+000002e0  73 58 e0 47 33 b9 5e c4  6a 10 c2 1a 42 c3 85 2b  |sX.G3.^.j...B..+|
+000002f0  20 38 80 5d 40 81 4a 78  40 d9 13 ac af b3 45 e7  | 8.]@.Jx@.....E.|
+00000300  1e 19 c6 b5 63 6e 9c 5c  8a 8d                    |....cn.\..|
 >>> Flow 4 (server to client)
-00000000  14 03 01 00 01 01 16 03  01 00 30 4d 4f d6 67 05  |..........0MO.g.|
-00000010  32 8c 16 cb 19 35 b3 b9  02 d8 5e 24 b6 c8 b7 3a  |2....5....^$...:|
-00000020  17 34 98 77 e1 73 e0 cd  a9 30 a8 15 60 8c f4 9a  |.4.w.s...0..`...|
-00000030  dc cf 7a fd 86 85 1c 2b  33 21 e8                 |..z....+3!.|
+00000000  14 03 01 00 01 01 16 03  01 00 30 c6 bb 74 56 db  |..........0..tV.|
+00000010  fd f7 a7 dd 3b a3 50 10  11 44 83 a1 c6 b1 6e 70  |....;.P..D....np|
+00000020  37 6e 68 b2 5a 45 6b fb  e9 9d 4e 68 cf ba ea af  |7nh.ZEk...Nh....|
+00000030  7d f6 65 ee 22 14 9e 5a  a7 85 65                 |}.e."..Z..e|
 >>> Flow 5 (client to server)
-00000000  17 03 01 00 20 b8 c5 17  b7 92 d8 93 7a b2 fd 4f  |.... .......z..O|
-00000010  15 d1 db b9 47 54 00 a0  f6 77 92 03 a8 89 e5 ba  |....GT...w......|
-00000020  cc eb d9 bd 27 17 03 01  00 20 57 d5 9a f6 36 b2  |....'.... W...6.|
-00000030  57 ba cd 64 77 36 b9 74  fb bd 95 51 03 61 e8 45  |W..dw6.t...Q.a.E|
-00000040  cb b8 35 f0 05 17 b3 08  c6 cb 15 03 01 00 20 28  |..5........... (|
-00000050  43 03 ab 3f e2 f5 d0 33  4c 7f 50 a4 ee 7b 46 e6  |C..?...3L.P..{F.|
-00000060  12 76 d0 fd c3 99 5c 63  a4 04 ea 4b e3 bd 99     |.v....\c...K...|
+00000000  17 03 01 00 20 c7 78 67  68 03 48 2e a5 c3 7a 0a  |.... .xgh.H...z.|
+00000010  56 73 14 02 12 f7 26 ac  48 19 3e e6 4b 0f ac d0  |Vs....&.H.>.K...|
+00000020  4e 74 dc 66 68 17 03 01  00 20 bf db fb e7 85 35  |Nt.fh.... .....5|
+00000030  50 4d 39 3f ab 25 95 30  4c 7a 20 d8 89 db 74 ff  |PM9?.%.0Lz ...t.|
+00000040  e6 e1 05 30 98 17 f3 93  8a 0d 15 03 01 00 20 f9  |...0.......... .|
+00000050  33 18 32 46 d3 28 46 a4  06 8c e1 9b 9b 1d d1 d8  |3.2F.(F.........|
+00000060  7b 9f 6c ad 5d 2a 36 10  2c dd f8 30 23 54 ac     |{.l.]*6.,..0#T.|