/*
 * 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;
  }
}