context: using System;
  using System.Collections;
  
  using Nequeo.Cryptography.Key.Crypto;
  using Nequeo.Cryptography.Key.Crypto.Parameters;
  using Nequeo.Cryptography.Key.Math;
  using Nequeo.Cryptography.Key.Security;
  using Nequeo.Cryptography.Key.Utilities;
  using Nequeo.Cryptography.Key.Utilities.Collections;
  
  namespace Nequeo.Cryptography.Key.Crypto.Generators
  {
  	/**
  	 * Key generation parameters for NaccacheStern cipher. For details on this cipher, please see
  	 *
  	 * http://www.gemplus.com/smart/rd/publications/pdf/NS98pkcs.pdf
  	 */
  	public class NaccacheSternKeyPairGenerator
  		: IAsymmetricCipherKeyPairGenerator
  	{
  		private static readonly int[] smallPrimes =
  		{
  			3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
  			71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
  			151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
  			239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331,
  			337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
  			433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523,
  			541, 547, 557
  		};
  
  		private NaccacheSternKeyGenerationParameters param;
  
  		/*
  		 * (non-Javadoc)
  		 *
  		 * @see Nequeo.Cryptography.Key.crypto.AsymmetricCipherKeyPairGenerator#init(Nequeo.Cryptography.Key.crypto.KeyGenerationParameters)
  		 */
  		public void Init(KeyGenerationParameters parameters)
  		{
  			this.param = (NaccacheSternKeyGenerationParameters)parameters;
  		}
  
  		/*
  		 * (non-Javadoc)
  		 *
  		 * @see Nequeo.Cryptography.Key.crypto.AsymmetricCipherKeyPairGenerator#generateKeyPair()
  		 */
  		public AsymmetricCipherKeyPair GenerateKeyPair()
  		{
  			int strength = param.Strength;
  			SecureRandom rand = param.Random;
  			int certainty = param.Certainty;
  			bool debug = param.IsDebug;
  
  			if (debug)
  			{
  				Console.WriteLine("Fetching first " + param.CountSmallPrimes + " primes.");
  			}
  
  			IList smallPrimes = findFirstPrimes(param.CountSmallPrimes);
  
  			smallPrimes = permuteList(smallPrimes, rand);
  
  			BigInteger u = BigInteger.One;
  			BigInteger v = BigInteger.One;
  
  			for (int i = 0; i < smallPrimes.Count / 2; i++)
  			{
  				u = u.Multiply((BigInteger)smallPrimes[i]);
  			}
  			for (int i = smallPrimes.Count / 2; i < smallPrimes.Count; i++)
  			{
  				v = v.Multiply((BigInteger)smallPrimes[i]);
  			}
  
  			BigInteger sigma = u.Multiply(v);
  
  			// n = (2 a u _p + 1 ) ( 2 b v _q + 1)
  			// -> |n| = strength
  			// |2| = 1 in bits
  			// -> |a| * |b| = |n| - |u| - |v| - |_p| - |_q| - |2| -|2|
  			// remainingStrength = strength - sigma.bitLength() - _p.bitLength() -
  			// _q.bitLength() - 1 -1
  			int remainingStrength = strength - sigma.BitLength - 48;
  			BigInteger a = generatePrime(remainingStrength / 2 + 1, certainty, rand);
  			BigInteger b = generatePrime(remainingStrength / 2 + 1, certainty, rand);
  
  			BigInteger _p;
  			BigInteger _q;
  			BigInteger p;
  			BigInteger q;
  
  			long tries = 0;
  			if (debug)
  			{
  				Console.WriteLine("generating p and q");
  			}
  
  			BigInteger _2au = a.Multiply(u).ShiftLeft(1);
  			BigInteger _2bv = b.Multiply(v).ShiftLeft(1);
  
  			for (;;)
  			{
  				tries++;
  
  				_p = generatePrime(24, certainty, rand);
  
  				p = _p.Multiply(_2au).Add(BigInteger.One);
  
  				if (!p.IsProbablePrime(certainty))
  					continue;
  
  				for (;;)
  				{
  					_q = generatePrime(24, certainty, rand);
  
  					if (_p.Equals(_q))
  						continue;
  
  					q = _q.Multiply(_2bv).Add(BigInteger.One);
  
  					if (q.IsProbablePrime(certainty))
  						break;
  				}
  
  				if (!sigma.Gcd(_p.Multiply(_q)).Equals(BigInteger.One))
  				{
  					Console.WriteLine("sigma.gcd(_p.mult(_q)) != 1!\n _p: " + _p +"\n _q: "+ _q );
  					continue;
  				}
  
  				if (p.Multiply(q).BitLength < strength)
  				{
  					if (debug)
  					{
  						Console.WriteLine("key size too small. Should be " + strength + " but is actually "
  							+ p.Multiply(q).BitLength);
  					}
  					continue;
  				}
  				break;
  			}
  
  			if (debug)
  			{
  				Console.WriteLine("needed " + tries + " tries to generate p and q.");
  			}
  
  			BigInteger n = p.Multiply(q);
  			BigInteger phi_n = p.Subtract(BigInteger.One).Multiply(q.Subtract(BigInteger.One));
  			BigInteger g;
  			tries = 0;
  			if (debug)
  			{
  				Console.WriteLine("generating g");
  			}
  			for (;;)
  			{
  				// TODO After the first loop, just regenerate one randomly-selected gPart each time?
  				IList gParts = Platform.CreateArrayList();
  				for (int ind = 0; ind != smallPrimes.Count; ind++)
  				{
  					BigInteger i = (BigInteger)smallPrimes[ind];
  					BigInteger e = phi_n.Divide(i);
  
  					for (;;)
  					{
  						tries++;
  
  						g = generatePrime(strength, certainty, rand);
  
  						if (!g.ModPow(e, n).Equals(BigInteger.One))
  						{
  							gParts.Add(g);
  							break;
  						}
  					}
  				}
  				g = BigInteger.One;
  				for (int i = 0; i < smallPrimes.Count; i++)
  				{
  					BigInteger gPart = (BigInteger) gParts[i];
  					BigInteger smallPrime = (BigInteger) smallPrimes[i];
  					g = g.Multiply(gPart.ModPow(sigma.Divide(smallPrime), n)).Mod(n);
  				}
  
  				// make sure that g is not divisible by p_i or q_i
  				bool divisible = false;
  				for (int i = 0; i < smallPrimes.Count; i++)
  				{
  					if (g.ModPow(phi_n.Divide((BigInteger)smallPrimes[i]), n).Equals(BigInteger.One))
  					{
  						if (debug)
  						{
  							Console.WriteLine("g has order phi(n)/" + smallPrimes[i] + "\n g: " + g);
  						}
  						divisible = true;
  						break;
  					}
  				}
  
  				if (divisible)
  				{
  					continue;
  				}
  
  				// make sure that g has order > phi_n/4
  
  				//if (g.ModPow(phi_n.Divide(BigInteger.ValueOf(4)), n).Equals(BigInteger.One))
  				if (g.ModPow(phi_n.ShiftRight(2), n).Equals(BigInteger.One))
  				{
  					if (debug)
  					{
  
gt: 						Console.WriteLine("g has order phi(n)/4\n g:" + g);