src/main/java/org/apache/pirk/encryption/PrimeGenerator.java - incubator-retired-pirk - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */
 package org.apache.pirk.encryption;

 import java.math.BigDecimal;
 import java.math.BigInteger;
 import java.util.HashMap;
 import java.util.Random;

 import org.apache.pirk.utils.SystemConfiguration;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;

 /**
  * Class to generate the primes used in the Paillier cryptosystem
  * <p>
  * This class will either:
  * <p>
  * (1) Generate the primes according to Java's BigInteger prime generation methods, which satisfy ANSI X9.80
  * <p>
  * or
  * <p>
  * (2) Bolster Java BigInteger's prime generation to meet the requirements of NIST SP 800-56B ("Recommendation for Pair-Wise Key Establishment Schemes Using
  * Integer Factorization Cryptography") and FIPS 186-4 ("Digital Signature Standard (DSS)") for key generation using probable primes.
  * <p>
  * Relevant page: SP 800-56B: p30 http://csrc.nist.gov/publications/nistpubs/800-56B/sp800-56B.pdf#page=30 Heading: 5.4 Prime Number Generators
  * <p>
  * Relevant pages FIPS 186-4: p50-p53, p55, p71: Sections B.3.1, B.3.3
  * <p>
  * http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=61
  * <p>
  * http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=80
  * <p>
  * Headings of most interest: Table C.2 "Minimum number of rounds of M-R testing when generating primes for use in RSA Digital Signatures" and "The primes p and
  * q shall be selected with the following constraints"
  *
  */
 public class PrimeGenerator
 {
   private static final Logger logger = LoggerFactory.getLogger(PrimeGenerator.class);

   private static final BigDecimal SQRT_2 = BigDecimal.valueOf(Math.sqrt(2));

   private static final HashMap<Integer,BigInteger> lowerBoundCache = new HashMap<>();
   private static final HashMap<Integer,BigInteger> minimumDifferenceCache = new HashMap<>();

   private static boolean additionalChecksEnabled = SystemConfiguration.isSetTrue("pallier.FIPSPrimeGenerationChecks");

   /**
    * Method to generate a single prime
    * <p>
    * Will optionally ensure that the prime meets the requirements in NIST SP 800-56B and FIPS 186-4
    * <p>
    * NOTE: bitLength corresponds to the FIPS 186-4 nlen parameter
    */
   public static BigInteger getSinglePrime(int bitLength, int certainty, Random rnd)
   {
     BigInteger p;

     logger.debug("bitLength " + bitLength + " certainty " + certainty + " random " + rnd);

     // If the additional checks are disabled, don't waste time on anything else
     if (!additionalChecksEnabled)
     {
       p = new BigInteger(bitLength / 2, certainty, rnd);
     }
     else
     {
       // Calculate the number of Miller-Rabin rounds that we need in addition to
       // the number that BigInteger will do to comply with FIPS 186-4, Appendix C.2
       int roundsLeft = calcNumAdditionalMillerRabinRounds(bitLength);

       // Calculate the lower bound (\sqrt(2))(2^(bitLength/2) – 1)) for use in FIPS 186-4 B.3.3, step 4.4
       BigInteger lowerBound;
       if (!lowerBoundCache.containsKey(bitLength))
       {
         lowerBound = SQRT_2.multiply(BigDecimal.valueOf(2).pow((bitLength / 2) - 1)).toBigInteger();
         lowerBoundCache.put(bitLength, lowerBound);
       }
       else
       {
         lowerBound = lowerBoundCache.get(bitLength);
       }

       // Complete FIPS 186-4 B.3.3, steps 4.2 - 4.5
       while (true)
       {
         // FIPS 186-4 B.3.3, step 4.2 and 4.3
         // 4.2: Obtain a string p of (bitLength/2) bits from an RBG that supports the security_strength.
         // 4.3: If (p is not odd), then p = p + 1. -- BigInteger hands us a prime (hence odd) with the call below
         p = new BigInteger(bitLength / 2, certainty, rnd);

         // FIPS 186-4 B.3.3, step 4.4
         // 4.4: If p < (\sqrt(2))(2^(bitLength/2) – 1)), then go to step 4.2.
         if (p.compareTo(lowerBound) > -1)
         {
           // FIPS 186-4, step 4.5
           // Run however many more rounds of Miller-Rabin are needed
           if (passesMillerRabin(p, roundsLeft, rnd))
           {
             // We have winner
             break;
           }
         }
       }
     }
     return p;
   }

   /**
    * Method to generate a second prime, q, in relation to a (p,q) RSA key pair
    * <p>
    * Will optionally ensure that the prime meets the requirements in NIST SP 800-56B and FIPS 186-4
    * <p>
    * NOTE: bitLength corresponds to the FIPS 186-4 nlen parameter
    */
   public static BigInteger getSecondPrime(int bitLength, int certainty, Random rnd, BigInteger p)
   {
     BigInteger q;

     logger.debug("bitLength " + bitLength + " certainty " + certainty + " random " + rnd);

     // If the additional checks are disabled, don't waste time on anything else
     if (!additionalChecksEnabled)
     {
       q = new BigInteger(bitLength / 2, certainty, rnd);
     }
     else
     {
       // Calculate the number of Miller-Rabin rounds that we need in addition to
       // the number that BigInteger will do to comply with FIPS 186-4, Appendix C.2
       int roundsLeft = calcNumAdditionalMillerRabinRounds(bitLength);

       // Calculate the lower bound (\sqrt(2))(2^(bitLength/2) – 1)) for use in FIPS 186-4 B.3.3, step 5.5
       BigInteger lowerBound;
       if (!lowerBoundCache.containsKey(bitLength))
       {
         lowerBound = SQRT_2.multiply(BigDecimal.valueOf(2).pow((bitLength / 2) - 1)).toBigInteger();
         lowerBoundCache.put(bitLength, lowerBound);
       }
       else
       {
         lowerBound = lowerBoundCache.get(bitLength);
       }

       // Compute the minimumDifference 2^((bitLength/2) – 100) for use in FIPS 186-4 B.3.3, step 5.4
       BigInteger minimumDifference;
       if (!minimumDifferenceCache.containsKey(bitLength))
       {
         minimumDifference = BigDecimal.valueOf(2).pow(bitLength / 2 - 100).toBigInteger();
         minimumDifferenceCache.put(bitLength, minimumDifference);
       }
       else
       {
         minimumDifference = minimumDifferenceCache.get(bitLength);
       }

       // Complete FIPS 186-4 B.3.3, steps 5.2 - 5.6
       while (true)
       {
         // FIPS 186-4 B.3.3, step 5.2 and 5.3
         // 5.2: Obtain a string q of (bitLength/2) bits from an RBG that supports the security_strength.
         // 5.3: If (q is not odd), then q = q + 1. -- BigInteger hands us a prime (hence odd) with the call below
         q = new BigInteger(bitLength / 2, certainty, rnd);

         // FIPS 186-4 B.3.3, step 5.4 & 5.5
         // 5.4 If (|p – q| ≤ 2^((bitLength/2) – 100), then go to step 5.2
         // 5.5: If q < (\sqrt(2))(2^(bitLength/2) – 1)), then go to step 5.2.
         BigInteger absDiff = (p.subtract(q)).abs();
         if ((q.compareTo(lowerBound) > -1) && (absDiff.compareTo(minimumDifference) > 0))
         {
           // FIPS 186-4, step 5.6
           // Run however many more rounds of Miller-Rabin are needed
           if (passesMillerRabin(q, roundsLeft, rnd))
           {
             // We have winner
             break;
           }
         }
       }
     }
     return q;
   }

   /**
    * This method returns a two-long array containing a viable RSA p and q meeting FIPS 186-4 and SP 800-56B
    */
   public static BigInteger[] getPrimePair(int bitLength, int certainty, Random rnd)
   {
     BigInteger[] toReturn = {null, null};

     toReturn[0] = getSinglePrime(bitLength, certainty, rnd);
     toReturn[1] = getSecondPrime(bitLength, certainty, rnd, toReturn[0]);

     return toReturn;
   }

   /**
    * Method to return the number of Miller-Rabin rounds that we need in addition to those that BigInteger will do
    */
   private static int calcNumAdditionalMillerRabinRounds(int bitLength)
   {
     // The code in BigInteger.java:primeToCertainty(...) that selects the number of MR rounds is excerpted below:
     // if (sizeInBits < 100) { rounds = 50; rounds = n < rounds ? n : rounds; return passesMillerRabin(rounds, random); }
     // if (sizeInBits < 256) { rounds = 27; }
     // else if (sizeInBits < 512) { rounds = 15; }
     // else if (sizeInBits < 768) { rounds = 8; }
     // else if (sizeInBits < 1024) { rounds = 4; }
     // else { rounds = 2; } rounds = n < rounds ? n : rounds;
     int roundsLeft = 0;

     if (bitLength >= 1536)
     {
       roundsLeft = 2; // BigInteger prime generation performs 2 rounds of MR tests; 4 is FIPS 186-4 compliant
     }
     else if (bitLength >= 1024)
     {
       roundsLeft = 3; // BigInteger prime generation performs 2 rounds of MR tests; 5 is FIPS 186-4 compliant
     }

     return roundsLeft;
   }

   /**
    * Returns true iff this BigInteger passes the specified number of Miller-Rabin tests.
    * <p>
    * This test is taken from the FIPS 186-4, C.3.1
    * <p>
    * The following assumptions are made:
    * <p>
    * This BigInteger is a positive, odd number greater than 2. iterations<=50.
    */
   private static boolean passesMillerRabin(BigInteger w, int iterations, Random rnd)
   {
     // Find a and m:
     // a is the largest int such that 2^a | (w-1)
     // and m = (w-1) / 2^a
     BigInteger wMinusOne = w.subtract(BigInteger.ONE);
     BigInteger m = wMinusOne;
     int a = m.getLowestSetBit();
     m = m.shiftRight(a);

     for (int i = 0; i < iterations; i++)
     {
       // Generate a random b, of length len(w) bits, such that 1 < b < (w-1), steps 4.1-4.2
       BigInteger b = new BigInteger(w.bitLength(), rnd);
       while (b.compareTo(BigInteger.ONE) <= 0 || b.compareTo(w) >= 0)
       {
         b = new BigInteger(w.bitLength(), rnd);
       }

       // Construct z = b^m mod w, step 4.3
       int j = 0;
       BigInteger z = ModPowAbstraction.modPow(b, m, w);
       while (!((j == 0 && z.equals(BigInteger.ONE)) || z.equals(wMinusOne))) // step 4.4-4.5
       {
         if (j > 0 && z.equals(BigInteger.ONE) || ++j == a)
         {
           return false;
         }
         z = ModPowAbstraction.modPow(z, BigInteger.valueOf(2), w); // step 4.5.1
       }
     }
     return true;
   }
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/
	package org.apache.pirk.encryption;

	import java.math.BigDecimal;
	import java.math.BigInteger;
	import java.util.HashMap;
	import java.util.Random;

	import org.apache.pirk.utils.SystemConfiguration;
	import org.slf4j.Logger;
	import org.slf4j.LoggerFactory;

	/**
	* Class to generate the primes used in the Paillier cryptosystem
	* <p>
	* This class will either:
	* <p>
	* (1) Generate the primes according to Java's BigInteger prime generation methods, which satisfy ANSI X9.80
	* <p>
	* or
	* <p>
	* (2) Bolster Java BigInteger's prime generation to meet the requirements of NIST SP 800-56B ("Recommendation for Pair-Wise Key Establishment Schemes Using
	* Integer Factorization Cryptography") and FIPS 186-4 ("Digital Signature Standard (DSS)") for key generation using probable primes.
	* <p>
	* Relevant page: SP 800-56B: p30 http://csrc.nist.gov/publications/nistpubs/800-56B/sp800-56B.pdf#page=30 Heading: 5.4 Prime Number Generators
	* <p>
	* Relevant pages FIPS 186-4: p50-p53, p55, p71: Sections B.3.1, B.3.3
	* <p>
	* http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=61
	* <p>
	* http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=80
	* <p>
	* Headings of most interest: Table C.2 "Minimum number of rounds of M-R testing when generating primes for use in RSA Digital Signatures" and "The primes p and
	* q shall be selected with the following constraints"
	*
	*/
	public class PrimeGenerator
	{
	private static final Logger logger = LoggerFactory.getLogger(PrimeGenerator.class);

	private static final BigDecimal SQRT_2 = BigDecimal.valueOf(Math.sqrt(2));

	private static final HashMap<Integer,BigInteger> lowerBoundCache = new HashMap<>();
	private static final HashMap<Integer,BigInteger> minimumDifferenceCache = new HashMap<>();

	private static boolean additionalChecksEnabled = SystemConfiguration.isSetTrue("pallier.FIPSPrimeGenerationChecks");

	/**
	* Method to generate a single prime
	* <p>
	* Will optionally ensure that the prime meets the requirements in NIST SP 800-56B and FIPS 186-4
	* <p>
	* NOTE: bitLength corresponds to the FIPS 186-4 nlen parameter
	*/
	public static BigInteger getSinglePrime(int bitLength, int certainty, Random rnd)
	{
	BigInteger p;

	logger.debug("bitLength " + bitLength + " certainty " + certainty + " random " + rnd);

	// If the additional checks are disabled, don't waste time on anything else
	if (!additionalChecksEnabled)
	{
	p = new BigInteger(bitLength / 2, certainty, rnd);
	}
	else
	{
	// Calculate the number of Miller-Rabin rounds that we need in addition to
	// the number that BigInteger will do to comply with FIPS 186-4, Appendix C.2
	int roundsLeft = calcNumAdditionalMillerRabinRounds(bitLength);

	// Calculate the lower bound (\sqrt(2))(2^(bitLength/2) – 1)) for use in FIPS 186-4 B.3.3, step 4.4
	BigInteger lowerBound;
	if (!lowerBoundCache.containsKey(bitLength))
	{
	lowerBound = SQRT_2.multiply(BigDecimal.valueOf(2).pow((bitLength / 2) - 1)).toBigInteger();
	lowerBoundCache.put(bitLength, lowerBound);
	}
	else
	{
	lowerBound = lowerBoundCache.get(bitLength);
	}

	// Complete FIPS 186-4 B.3.3, steps 4.2 - 4.5
	while (true)
	{
	// FIPS 186-4 B.3.3, step 4.2 and 4.3
	// 4.2: Obtain a string p of (bitLength/2) bits from an RBG that supports the security_strength.
	// 4.3: If (p is not odd), then p = p + 1. -- BigInteger hands us a prime (hence odd) with the call below
	p = new BigInteger(bitLength / 2, certainty, rnd);

	// FIPS 186-4 B.3.3, step 4.4
	// 4.4: If p < (\sqrt(2))(2^(bitLength/2) – 1)), then go to step 4.2.
	if (p.compareTo(lowerBound) > -1)
	{
	// FIPS 186-4, step 4.5
	// Run however many more rounds of Miller-Rabin are needed
	if (passesMillerRabin(p, roundsLeft, rnd))
	{
	// We have winner
	break;
	}
	}
	}
	}
	return p;
	}

	/**
	* Method to generate a second prime, q, in relation to a (p,q) RSA key pair
	* <p>
	* Will optionally ensure that the prime meets the requirements in NIST SP 800-56B and FIPS 186-4
	* <p>
	* NOTE: bitLength corresponds to the FIPS 186-4 nlen parameter
	*/
	public static BigInteger getSecondPrime(int bitLength, int certainty, Random rnd, BigInteger p)
	{
	BigInteger q;

	logger.debug("bitLength " + bitLength + " certainty " + certainty + " random " + rnd);

	// If the additional checks are disabled, don't waste time on anything else
	if (!additionalChecksEnabled)
	{
	q = new BigInteger(bitLength / 2, certainty, rnd);
	}
	else
	{
	// Calculate the number of Miller-Rabin rounds that we need in addition to
	// the number that BigInteger will do to comply with FIPS 186-4, Appendix C.2
	int roundsLeft = calcNumAdditionalMillerRabinRounds(bitLength);

	// Calculate the lower bound (\sqrt(2))(2^(bitLength/2) – 1)) for use in FIPS 186-4 B.3.3, step 5.5
	BigInteger lowerBound;
	if (!lowerBoundCache.containsKey(bitLength))
	{
	lowerBound = SQRT_2.multiply(BigDecimal.valueOf(2).pow((bitLength / 2) - 1)).toBigInteger();
	lowerBoundCache.put(bitLength, lowerBound);
	}
	else
	{
	lowerBound = lowerBoundCache.get(bitLength);
	}

	// Compute the minimumDifference 2^((bitLength/2) – 100) for use in FIPS 186-4 B.3.3, step 5.4
	BigInteger minimumDifference;
	if (!minimumDifferenceCache.containsKey(bitLength))
	{
	minimumDifference = BigDecimal.valueOf(2).pow(bitLength / 2 - 100).toBigInteger();
	minimumDifferenceCache.put(bitLength, minimumDifference);
	}
	else
	{
	minimumDifference = minimumDifferenceCache.get(bitLength);
	}

	// Complete FIPS 186-4 B.3.3, steps 5.2 - 5.6
	while (true)
	{
	// FIPS 186-4 B.3.3, step 5.2 and 5.3
	// 5.2: Obtain a string q of (bitLength/2) bits from an RBG that supports the security_strength.
	// 5.3: If (q is not odd), then q = q + 1. -- BigInteger hands us a prime (hence odd) with the call below
	q = new BigInteger(bitLength / 2, certainty, rnd);

	// FIPS 186-4 B.3.3, step 5.4 & 5.5
	// 5.4 If (\|p – q\| ≤ 2^((bitLength/2) – 100), then go to step 5.2
	// 5.5: If q < (\sqrt(2))(2^(bitLength/2) – 1)), then go to step 5.2.
	BigInteger absDiff = (p.subtract(q)).abs();
	if ((q.compareTo(lowerBound) > -1) && (absDiff.compareTo(minimumDifference) > 0))
	{
	// FIPS 186-4, step 5.6
	// Run however many more rounds of Miller-Rabin are needed
	if (passesMillerRabin(q, roundsLeft, rnd))
	{
	// We have winner
	break;
	}
	}
	}
	}
	return q;
	}

	/**
	* This method returns a two-long array containing a viable RSA p and q meeting FIPS 186-4 and SP 800-56B
	*/
	public static BigInteger[] getPrimePair(int bitLength, int certainty, Random rnd)
	{
	BigInteger[] toReturn = {null, null};

	toReturn[0] = getSinglePrime(bitLength, certainty, rnd);
	toReturn[1] = getSecondPrime(bitLength, certainty, rnd, toReturn[0]);

	return toReturn;
	}

	/**
	* Method to return the number of Miller-Rabin rounds that we need in addition to those that BigInteger will do
	*/
	private static int calcNumAdditionalMillerRabinRounds(int bitLength)
	{
	// The code in BigInteger.java:primeToCertainty(...) that selects the number of MR rounds is excerpted below:
	// if (sizeInBits < 100) { rounds = 50; rounds = n < rounds ? n : rounds; return passesMillerRabin(rounds, random); }
	// if (sizeInBits < 256) { rounds = 27; }
	// else if (sizeInBits < 512) { rounds = 15; }
	// else if (sizeInBits < 768) { rounds = 8; }
	// else if (sizeInBits < 1024) { rounds = 4; }
	// else { rounds = 2; } rounds = n < rounds ? n : rounds;
	int roundsLeft = 0;

	if (bitLength >= 1536)
	{
	roundsLeft = 2; // BigInteger prime generation performs 2 rounds of MR tests; 4 is FIPS 186-4 compliant
	}
	else if (bitLength >= 1024)
	{
	roundsLeft = 3; // BigInteger prime generation performs 2 rounds of MR tests; 5 is FIPS 186-4 compliant
	}

	return roundsLeft;
	}

	/**
	* Returns true iff this BigInteger passes the specified number of Miller-Rabin tests.
	* <p>
	* This test is taken from the FIPS 186-4, C.3.1
	* <p>
	* The following assumptions are made:
	* <p>
	* This BigInteger is a positive, odd number greater than 2. iterations<=50.
	*/
	private static boolean passesMillerRabin(BigInteger w, int iterations, Random rnd)
	{
	// Find a and m:
	// a is the largest int such that 2^a \| (w-1)
	// and m = (w-1) / 2^a
	BigInteger wMinusOne = w.subtract(BigInteger.ONE);
	BigInteger m = wMinusOne;
	int a = m.getLowestSetBit();
	m = m.shiftRight(a);

	for (int i = 0; i < iterations; i++)
	{
	// Generate a random b, of length len(w) bits, such that 1 < b < (w-1), steps 4.1-4.2
	BigInteger b = new BigInteger(w.bitLength(), rnd);
	while (b.compareTo(BigInteger.ONE) <= 0 \|\| b.compareTo(w) >= 0)
	{
	b = new BigInteger(w.bitLength(), rnd);
	}

	// Construct z = b^m mod w, step 4.3
	int j = 0;
	BigInteger z = ModPowAbstraction.modPow(b, m, w);
	while (!((j == 0 && z.equals(BigInteger.ONE)) \|\| z.equals(wMinusOne))) // step 4.4-4.5
	{
	if (j > 0 && z.equals(BigInteger.ONE) \|\| ++j == a)
	{
	return false;
	}
	z = ModPowAbstraction.modPow(z, BigInteger.valueOf(2), w); // step 4.5.1
	}
	}
	return true;
	}
	}