tree 426a768a06f13bcc10d03dcfd5f996a14a6d9c7a
parent 1044553d6d43632d0272e60b21166bb41e49bfa2
author David Benjamin <davidben@google.com> 1520132654 -0500
committer Adam Langley <alangley@gmail.com> 1522439624 +0000

Add a constant-time generic modular inverse function.

This uses the full binary GCD algorithm, where all four of A, B, C, and
D must be retained. (BN_mod_inverse_odd implements the odd number
version which only needs A and C.) It is patterned after the version
in the Handbook of Applied Cryptography, but tweaked so the coefficients
are non-negative and bounded.

Median of 29 RSA keygens: 0m0.225s -> 0m0.220s
(Accuracy beyond 0.1s is questionable.)

Bug: 238
Change-Id: I6dc13524ea7c8ac1072592857880ddf141d87526
Reviewed-on: https://boringssl-review.googlesource.com/26370
Reviewed-by: Adam Langley <alangley@gmail.com>