diff options
| author | Pete Bentley <prb@google.com> | 2019-07-01 16:22:06 +0100 |
|---|---|---|
| committer | Pete Bentley <prb@google.com> | 2019-07-09 16:52:01 +0100 |
| commit | 3e10d60db4dd81ab376be4a1d4f770589de39eb6 (patch) | |
| tree | 7cd50edb75852a4b725eb7e0385e5a11f12468df /bcprov | |
| parent | d7e9756c384c9c65ad5e35af939bdebf755fd762 (diff) | |
| download | bouncycastle-3e10d60db4dd81ab376be4a1d4f770589de39eb6.tar.gz | |
Cherrypick BigIntegers code from BouncyCastle v1.62.
Contains performance fixes to this class made between
BC version 1.61 (latest in AOSP) and 1.62 (latest public release)
in response to https://github.com/bcgit/bc-java/issues/484
Combines 3 BC commits which together apply cleanly to AOSP:-
https://github.com/bcgit/bc-java/commit/f72dd46
https://github.com/bcgit/bc-java/commit/522f6de
https://github.com/bcgit/bc-java/commit/a34ea0e
Does not contain the regression test added as part of those commits
as AOSP does not use or contain the relevant test framework.
Patch applies cleanly, and so should not cause any problems
when AOSP is updated to the rest of BC 1.62, or later.
Looking at the numbers logged by DHParametersHelper:-
$ adb logcat -d -e 'Generated safe primes'
07-01 15:57:09.417 3694 3726 I DHParametersHelper: Generated safe primes: 2248 tries took 896694ms
07-01 16:03:06.522 4518 4539 I DHParametersHelper: Generated safe primes: 922 tries took 346307ms
07-01 16:06:28.482 4832 4854 I DHParametersHelper: Generated safe primes: 507 tries took 191524ms
07-01 16:06:58.632 5082 5103 I DHParametersHelper: Generated safe primes: 50 tries took 19845ms
07-01 16:10:04.858 5273 5294 I DHParametersHelper: Generated safe primes: 433 tries took 176079ms
07-01 16:16:47.069 5519 5540 I DHParametersHelper: Generated safe primes: 953 tries took 391526ms
=> 5113 tries took 2021975ms, or 395ms per try.
From a taimen-eng build without the patch:-
07-01 13:41:55.800 14783 14804 I DHParametersHelper: Generated safe primes: 375 tries took 452465ms
07-01 13:57:51.450 15234 15255 I DHParametersHelper: Generated safe primes: 698 tries took 886154ms
07-01 14:13:59.091 15891 15912 I DHParametersHelper: Generated safe primes: 308 tries took 410750ms
07-01 14:33:30.084 16531 16552 I DHParametersHelper: Generated safe primes: 513 tries took 671493ms
=> 1894 tries took 2420862ms, or 1276ms per try.
Bug: 136447095
Test: atest CtsLibcoreTestCases
Change-Id: Iacd883187cc8249d287c8e5ef92ce7811d4cd540
Diffstat (limited to 'bcprov')
| -rw-r--r-- | bcprov/src/main/java/org/bouncycastle/util/BigIntegers.java | 16 |
1 files changed, 16 insertions, 0 deletions
diff --git a/bcprov/src/main/java/org/bouncycastle/util/BigIntegers.java b/bcprov/src/main/java/org/bouncycastle/util/BigIntegers.java index a118ba5a..62be36ec 100644 --- a/bcprov/src/main/java/org/bouncycastle/util/BigIntegers.java +++ b/bcprov/src/main/java/org/bouncycastle/util/BigIntegers.java @@ -141,6 +141,15 @@ public final class BigIntegers return new BigInteger(1, createRandom(bitLength, random)); } + // Hexadecimal value of the product of the 131 smallest odd primes from 3 to 743 + private static final BigInteger SMALL_PRIMES_PRODUCT = new BigInteger( + "8138e8a0fcf3a4e84a771d40fd305d7f4aa59306d7251de54d98af8fe95729a1f" + + "73d893fa424cd2edc8636a6c3285e022b0e3866a565ae8108eed8591cd4fe8d2" + + "ce86165a978d719ebf647f362d33fca29cd179fb42401cbaf3df0c614056f9c8" + + "f3cfd51e474afb6bc6974f78db8aba8e9e517fded658591ab7502bd41849462f", + 16); + private static final int SQR_MAX_SMALL = 20; // bitlength of 743 * 743 + /** * Return a prime number candidate of the specified bit length. * @@ -174,6 +183,13 @@ public final class BigIntegers base[base.length - 1] |= 0x01; rv = new BigInteger(1, base); + if (bitLength > SQR_MAX_SMALL) + { + while (!rv.gcd(SMALL_PRIMES_PRODUCT).equals(ONE)) + { + rv = rv.add(TWO); + } + } } while (!rv.isProbablePrime(certainty)); |