chg: use GCD of pre-multiplied list of primes to check for known factors

Change-Id: Iae10d67814bed36a8864cccf4d7e33ad3dbefeab

diff --git a/src/club/wpia/gigi/crypto/key/KeyCheckSmallFactors.java b/src/club/wpia/gigi/crypto/key/KeyCheckSmallFactors.java
index a0965344fc103674f2e561741a421a623220f785..8f78c6a51be00c59a4c86ca1ab3a7766437a11d7 100644 (file)
--- 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<BigInteger> 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()));
         }
     }