From 1c27d8c199a50ddb3ed509530273642489cba0ee Mon Sep 17 00:00:00 2001 From: Benny Baumann Date: Tue, 7 Nov 2017 21:20:05 +0100 Subject: [PATCH] chg: use GCD of pre-multiplied list of primes to check for known factors Change-Id: Iae10d67814bed36a8864cccf4d7e33ad3dbefeab --- .../gigi/crypto/key/KeyCheckSmallFactors.java | 22 ++++++++----------- 1 file changed, 9 insertions(+), 13 deletions(-) diff --git a/src/club/wpia/gigi/crypto/key/KeyCheckSmallFactors.java b/src/club/wpia/gigi/crypto/key/KeyCheckSmallFactors.java index a0965344..8f78c6a5 100644 --- a/src/club/wpia/gigi/crypto/key/KeyCheckSmallFactors.java +++ b/src/club/wpia/gigi/crypto/key/KeyCheckSmallFactors.java @@ -3,7 +3,6 @@ package club.wpia.gigi.crypto.key; import java.math.BigInteger; import java.security.PublicKey; import java.security.interfaces.RSAPublicKey; -import java.util.ArrayList; import club.wpia.gigi.GigiApiException; import club.wpia.gigi.output.template.SprintfCommand; @@ -12,23 +11,21 @@ public class KeyCheckSmallFactors extends KeyCheck { private static final long MAX_CHECKED_SMALL_PRIME_BOUNDARY = 10000; - private static final BigInteger[] primes; + private static final BigInteger primeProduct; static { - ArrayList prims = new ArrayList<>(1024); + BigInteger prod = BigInteger.ONE; NextPrime: for (long i = 2; i < MAX_CHECKED_SMALL_PRIME_BOUNDARY; i++) { - for (BigInteger p : prims) { - if (BigInteger.ZERO.equals(BigInteger.valueOf(i).mod(p))) { - continue NextPrime; - } + if ( !BigInteger.ONE.equals(BigInteger.valueOf(i).gcd(prod))) { + continue NextPrime; } - prims.add(BigInteger.valueOf(i)); + prod = prod.multiply(BigInteger.valueOf(i)); } - primes = prims.toArray(new BigInteger[0]); + primeProduct = prod; register(new KeyCheckSmallFactors()); } @@ -42,10 +39,9 @@ public class KeyCheckSmallFactors extends KeyCheck { BigInteger modulus = ((RSAPublicKey) key).getModulus(); // Check for small prime factors below 10000 - for (BigInteger n : primes) { - if (BigInteger.ZERO.equals(modulus.mod(n))) { - throw new GigiApiException(SprintfCommand.createSimple("Small factors check of public key: Key is divisible by {0}.", n.toString())); - } + BigInteger n = modulus.gcd(primeProduct); + if ( !BigInteger.ONE.equals(n)) { + throw new GigiApiException(SprintfCommand.createSimple("Small factors check of public key: Key has known factor of {0}.", n.toString())); } } -- 2.39.2