src/zerocoin/ParamGeneration.cpp

   1 /// \file       ParamGeneration.cpp
   2 ///
   3 /// \brief      Parameter manipulation routines for the Zerocoin cryptographic
   4 ///             components.
   5 ///
   6 /// \author     Ian Miers, Christina Garman and Matthew Green
   7 /// \date       June 2013
   8 ///
   9 /// \copyright  Copyright 2013 Ian Miers, Christina Garman and Matthew Green
  10 /// \license    This project is released under the MIT license.
  11
  12 #include <string>
  13 #include "Zerocoin.h"
  14
  15 using namespace std;
  16
  17 namespace libzerocoin {
  18
  19 /// \brief Fill in a set of Zerocoin parameters from a modulus "N".
  20 /// \param N                A trusted RSA modulus
  21 /// \param aux              An optional auxiliary string used in derivation
  22 /// \param securityLevel    A security level
  23 ///
  24 /// \throws         ZerocoinException if the process fails
  25 ///
  26 /// Fills in a ZC_Params data structure deterministically from
  27 /// a trustworthy RSA modulus "N", which is provided as a Bignum.
  28 ///
  29 /// Note: this routine makes the fundamental assumption that "N"
  30 /// encodes a valid RSA-style modulus of the form "e1*e2" for some
  31 /// unknown safe primes "e1" and "e2". These factors must not
  32 /// be known to any party, or the security of Zerocoin is
  33 /// compromised. The integer "N" must be a MINIMUM of 1023
  34 /// in length, and 3072 bits is strongly recommended.
  35 ///
  36
  37 void
  38 CalculateParams(Params &params, Bignum N, string aux, uint32_t securityLevel)
  39 {
  40         params.initialized = false;
  41         params.accumulatorParams.initialized = false;
  42
  43         // Verify that |N| is > 1023 bits.
  44         uint32_t NLen = N.bitSize();
  45         if (NLen < 1023) {
  46                 throw ZerocoinException("Modulus must be at least 1023 bits");
  47         }
  48
  49         // Verify that "securityLevel" is  at least 80 bits (minimum).
  50         if (securityLevel < 80) {
  51                 throw ZerocoinException("Security level must be at least 80 bits.");
  52         }
  53
  54         // Set the accumulator modulus to "N".
  55         params.accumulatorParams.accumulatorModulus = N;
  56
  57         // Calculate the required size of the field "F_p" into which
  58         // we're embedding the coin commitment group. This may throw an
  59         // exception if the securityLevel is too large to be supported
  60         // by the current modulus.
  61         uint32_t pLen = 0;
  62         uint32_t qLen = 0;
  63         calculateGroupParamLengths(NLen - 2, securityLevel, &pLen, &qLen);
  64
  65         // Calculate candidate parameters ("p", "q") for the coin commitment group
  66         // using a deterministic process based on "N", the "aux" string, and
  67         // the dedicated string "COMMITMENTGROUP".
  68         params.coinCommitmentGroup = deriveIntegerGroupParams(calculateSeed(N, aux, securityLevel, STRING_COMMIT_GROUP),
  69                                      pLen, qLen);
  70
  71         // Next, we derive parameters for a second Accumulated Value commitment group.
  72         // This is a Schnorr group with the specific property that the order of the group
  73         // must be exactly equal to "q" from the commitment group. We set
  74         // the modulus of the new group equal to "2q+1" and test to see if this is prime.
  75         params.serialNumberSoKCommitmentGroup = deriveIntegerGroupFromOrder(params.coinCommitmentGroup.modulus);
  76
  77         // Calculate the parameters for the internal commitment
  78         // using the same process.
  79         params.accumulatorParams.accumulatorPoKCommitmentGroup = deriveIntegerGroupParams(calculateSeed(N, aux, securityLevel, STRING_AIC_GROUP),
  80                 qLen + 300, qLen + 1);
  81
  82         // Calculate the parameters for the accumulator QRN commitment generators. This isn't really
  83         // a whole group, just a pair of random generators in QR_N.
  84         uint32_t resultCtr;
  85         params.accumulatorParams.accumulatorQRNCommitmentGroup.g = generateIntegerFromSeed(NLen - 1,
  86                 calculateSeed(N, aux, securityLevel, STRING_QRNCOMMIT_GROUPG),
  87                 &resultCtr).pow_mod(Bignum(2), N);
  88         params.accumulatorParams.accumulatorQRNCommitmentGroup.h = generateIntegerFromSeed(NLen - 1,
  89                 calculateSeed(N, aux, securityLevel, STRING_QRNCOMMIT_GROUPG),
  90                 &resultCtr).pow_mod(Bignum(2), N);
  91
  92         // Calculate the accumulator base, which we calculate as "u = C**2 mod N"
  93         // where C is an arbitrary value. In the unlikely case that "u = 1" we increment
  94         // "C" and repeat.
  95         Bignum constant(ACCUMULATOR_BASE_CONSTANT);
  96         params.accumulatorParams.accumulatorBase = Bignum(1);
  97         for (uint32_t count = 0; count < MAX_ACCUMGEN_ATTEMPTS && params.accumulatorParams.accumulatorBase.isOne(); count++) {
  98                 params.accumulatorParams.accumulatorBase = constant.pow_mod(Bignum(2), params.accumulatorParams.accumulatorModulus);
  99         }
 100
 101         // Compute the accumulator range. The upper range is the largest possible coin commitment value.
 102         // The lower range is sqrt(upper range) + 1. Since OpenSSL doesn't have
 103         // a square root function we use a slightly higher approximation.
 104         params.accumulatorParams.maxCoinValue = params.coinCommitmentGroup.modulus;
 105         params.accumulatorParams.minCoinValue = Bignum(2).pow((params.coinCommitmentGroup.modulus.bitSize() / 2) + 3);
 106
 107         // If all went well, mark params as successfully initialized.
 108         params.accumulatorParams.initialized = true;
 109
 110         // If all went well, mark params as successfully initialized.
 111         params.initialized = true;
 112 }
 113
 114 /// \brief Format a seed string by hashing several values.
 115 /// \param N                A Bignum
 116 /// \param aux              An auxiliary string
 117 /// \param securityLevel    The security level in bits
 118 /// \param groupName        A group description string
 119 /// \throws         ZerocoinException if the process fails
 120 ///
 121 /// Returns the hash of the value.
 122
 123 uint256
 124 calculateGeneratorSeed(uint256 seed, uint256 pSeed, uint256 qSeed, string label, uint32_t index, uint32_t count)
 125 {
 126         CHashWriter hasher(0,0);
 127         uint256     hash;
 128
 129         // Compute the hash of:
 130         // <modulus>||<securitylevel>||<auxString>||groupName
 131         hasher << seed;
 132         hasher << string("||");
 133         hasher << pSeed;
 134         hasher << string("||");
 135         hasher << qSeed;
 136         hasher << string("||");
 137         hasher << label;
 138         hasher << string("||");
 139         hasher << index;
 140         hasher << string("||");
 141         hasher << count;
 142
 143         return hasher.GetHash();
 144 }
 145
 146 /// \brief Format a seed string by hashing several values.
 147 /// \param N                A Bignum
 148 /// \param aux              An auxiliary string
 149 /// \param securityLevel    The security level in bits
 150 /// \param groupName        A group description string
 151 /// \throws         ZerocoinException if the process fails
 152 ///
 153 /// Returns the hash of the value.
 154
 155 uint256
 156 calculateSeed(Bignum modulus, string auxString, uint32_t securityLevel, string groupName)
 157 {
 158         CHashWriter hasher(0,0);
 159         uint256     hash;
 160
 161         // Compute the hash of:
 162         // <modulus>||<securitylevel>||<auxString>||groupName
 163         hasher << modulus;
 164         hasher << string("||");
 165         hasher << securityLevel;
 166         hasher << string("||");
 167         hasher << auxString;
 168         hasher << string("||");
 169         hasher << groupName;
 170
 171         return hasher.GetHash();
 172 }
 173
 174 uint256
 175 calculateHash(uint256 input)
 176 {
 177         CHashWriter hasher(0,0);
 178
 179         // Compute the hash of "input"
 180         hasher << input;
 181
 182         return hasher.GetHash();
 183 }
 184
 185 /// \brief Calculate field/group parameter sizes based on a security level.
 186 /// \param maxPLen          Maximum size of the field (modulus "p") in bits.
 187 /// \param securityLevel    Required security level in bits (at least 80)
 188 /// \param pLen             Result: length of "p" in bits
 189 /// \param qLen             Result: length of "q" in bits
 190 /// \throws                 ZerocoinException if the process fails
 191 ///
 192 /// Calculates the appropriate sizes of "p" and "q" for a prime-order
 193 /// subgroup of order "q" embedded within a field "F_p". The sizes
 194 /// are based on a 'securityLevel' provided in symmetric-equivalent
 195 /// bits. Our choices slightly exceed the specs in FIPS 186-3:
 196 ///
 197 /// securityLevel = 80:     pLen = 1024, qLen = 256
 198 /// securityLevel = 112:    pLen = 2048, qLen = 256
 199 /// securityLevel = 128:    qLen = 3072, qLen = 320
 200 ///
 201 /// If the length of "p" exceeds the length provided in "maxPLen", or
 202 /// if "securityLevel < 80" this routine throws an exception.
 203
 204 void
 205 calculateGroupParamLengths(uint32_t maxPLen, uint32_t securityLevel,
 206                            uint32_t *pLen, uint32_t *qLen)
 207 {
 208         *pLen = *qLen = 0;
 209
 210         if (securityLevel < 80) {
 211                 throw ZerocoinException("Security level must be at least 80 bits.");
 212         } else if (securityLevel == 80) {
 213                 *qLen = 256;
 214                 *pLen = 1024;
 215         } else if (securityLevel <= 112) {
 216                 *qLen = 256;
 217                 *pLen = 2048;
 218         } else if (securityLevel <= 128) {
 219                 *qLen = 320;
 220                 *pLen = 3072;
 221         } else {
 222                 throw ZerocoinException("Security level not supported.");
 223         }
 224
 225         if (*pLen > maxPLen) {
 226                 throw ZerocoinException("Modulus size is too small for this security level.");
 227         }
 228 }
 229
 230 /// \brief Deterministically compute a set of group parameters using NIST procedures.
 231 /// \param seedStr  A byte string seeding the process.
 232 /// \param pLen     The desired length of the modulus "p" in bits
 233 /// \param qLen     The desired length of the order "q" in bits
 234 /// \return         An IntegerGroupParams object
 235 ///
 236 /// Calculates the description of a group G of prime order "q" embedded within
 237 /// a field "F_p". The input to this routine is in arbitrary seed. It uses the
 238 /// algorithms described in FIPS 186-3 Appendix A.1.2 to calculate
 239 /// primes "p" and "q". It uses the procedure in Appendix A.2.3 to
 240 /// derive two generators "g", "h".
 241
 242 IntegerGroupParams
 243 deriveIntegerGroupParams(uint256 seed, uint32_t pLen, uint32_t qLen)
 244 {
 245         IntegerGroupParams result;
 246         Bignum p;
 247         Bignum q;
 248         uint256 pSeed, qSeed;
 249
 250         // Calculate "p" and "q" and "domain_parameter_seed" from the
 251         // "seed" buffer above, using the procedure described in NIST
 252         // FIPS 186-3, Appendix A.1.2.
 253         calculateGroupModulusAndOrder(seed, pLen, qLen, &(result.modulus),
 254                                       &(result.groupOrder), &pSeed, &qSeed);
 255
 256         // Calculate the generators "g", "h" using the process described in
 257         // NIST FIPS 186-3, Appendix A.2.3. This algorithm takes ("p", "q",
 258         // "domain_parameter_seed", "index"). We use "index" value 1
 259         // to generate "g" and "index" value 2 to generate "h".
 260         result.g = calculateGroupGenerator(seed, pSeed, qSeed, result.modulus, result.groupOrder, 1);
 261         result.h = calculateGroupGenerator(seed, pSeed, qSeed, result.modulus, result.groupOrder, 2);
 262
 263         // Perform some basic tests to make sure we have good parameters
 264         if ((uint32_t)(result.modulus.bitSize()) < pLen ||          // modulus is pLen bits long
 265                 (uint32_t)(result.groupOrder.bitSize()) < qLen ||       // order is qLen bits long
 266                 !(result.modulus.isPrime()) ||                          // modulus is prime
 267                 !(result.groupOrder.isPrime()) ||                       // order is prime
 268                 !((result.g.pow_mod(result.groupOrder, result.modulus)).isOne()) || // g^order mod modulus = 1
 269                 !((result.h.pow_mod(result.groupOrder, result.modulus)).isOne()) || // h^order mod modulus = 1
 270                 ((result.g.pow_mod(Bignum(100), result.modulus)).isOne()) ||        // g^100 mod modulus != 1
 271                 ((result.h.pow_mod(Bignum(100), result.modulus)).isOne()) ||        // h^100 mod modulus != 1
 272                 result.g == result.h ||                                 // g != h
 273                 result.g.isOne()) {                                     // g != 1
 274                 // If any of the above tests fail, throw an exception
 275                 throw ZerocoinException("Group parameters are not valid");
 276         }
 277
 278         return result;
 279 }
 280
 281 /// \brief Deterministically compute a  set of group parameters with a specified order.
 282 /// \param groupOrder   The order of the group
 283 /// \return         An IntegerGroupParams object
 284 ///
 285 /// Given "q" calculates the description of a group G of prime order "q" embedded within
 286 /// a field "F_p".
 287
 288 IntegerGroupParams
 289 deriveIntegerGroupFromOrder(Bignum &groupOrder)
 290 {
 291         IntegerGroupParams result;
 292
 293         // Set the order to "groupOrder"
 294         result.groupOrder = groupOrder;
 295
 296         // Try possible values for "modulus" of the form "groupOrder * 2 * i" where
 297         // "p" is prime and i is a counter starting at 1.
 298         for (uint32_t i = 1; i < NUM_SCHNORRGEN_ATTEMPTS; i++) {
 299                 // Set modulus equal to "groupOrder * 2 * i"
 300                 result.modulus = (result.groupOrder * Bignum(i*2)) + Bignum(1);
 301
 302                 // Test the result for primality
 303                 // TODO: This is a probabilistic routine and thus not the right choice
 304                 if (result.modulus.isPrime(256)) {
 305
 306                         // Success.
 307                         //
 308                         // Calculate the generators "g", "h" using the process described in
 309                         // NIST FIPS 186-3, Appendix A.2.3. This algorithm takes ("p", "q",
 310                         // "domain_parameter_seed", "index"). We use "index" value 1
 311                         // to generate "g" and "index" value 2 to generate "h".
 312                         uint256 seed = calculateSeed(groupOrder, "", 128, "");
 313                         uint256 pSeed = calculateHash(seed);
 314                         uint256 qSeed = calculateHash(pSeed);
 315                         result.g = calculateGroupGenerator(seed, pSeed, qSeed, result.modulus, result.groupOrder, 1);
 316                         result.h = calculateGroupGenerator(seed, pSeed, qSeed, result.modulus, result.groupOrder, 2);
 317
 318                         // Perform some basic tests to make sure we have good parameters
 319                         if (!(result.modulus.isPrime()) ||                          // modulus is prime
 320                                 !(result.groupOrder.isPrime()) ||                       // order is prime
 321                                 !((result.g.pow_mod(result.groupOrder, result.modulus)).isOne()) || // g^order mod modulus = 1
 322                                 !((result.h.pow_mod(result.groupOrder, result.modulus)).isOne()) || // h^order mod modulus = 1
 323                                 ((result.g.pow_mod(Bignum(100), result.modulus)).isOne()) ||        // g^100 mod modulus != 1
 324                                 ((result.h.pow_mod(Bignum(100), result.modulus)).isOne()) ||        // h^100 mod modulus != 1
 325                                 result.g == result.h ||                                 // g != h
 326                                 result.g.isOne()) {                                     // g != 1
 327                                 // If any of the above tests fail, throw an exception
 328                                 throw ZerocoinException("Group parameters are not valid");
 329                         }
 330
 331                         return result;
 332                 }
 333         }
 334
 335         // If we reached this point group generation has failed. Throw an exception.
 336         throw ZerocoinException("Too many attempts to generate Schnorr group.");
 337 }
 338
 339 /// \brief Deterministically compute a group description using NIST procedures.
 340 /// \param seed                         A byte string seeding the process.
 341 /// \param pLen                         The desired length of the modulus "p" in bits
 342 /// \param qLen                         The desired length of the order "q" in bits
 343 /// \param resultModulus                A value "p" describing a finite field "F_p"
 344 /// \param resultGroupOrder             A value "q" describing the order of a subgroup
 345 /// \param resultDomainParameterSeed    A resulting seed for use in later calculations.
 346 ///
 347 /// Calculates the description of a group G of prime order "q" embedded within
 348 /// a field "F_p". The input to this routine is in arbitrary seed. It uses the
 349 /// algorithms described in FIPS 186-3 Appendix A.1.2 to calculate
 350 /// primes "p" and "q".
 351
 352 void
 353 calculateGroupModulusAndOrder(uint256 seed, uint32_t pLen, uint32_t qLen,
 354                               Bignum *resultModulus, Bignum *resultGroupOrder,
 355                               uint256 *resultPseed, uint256 *resultQseed)
 356 {
 357         // Verify that the seed length is >= qLen
 358         if (qLen > (sizeof(seed)) * 8) {
 359                 // TODO: The use of 256-bit seeds limits us to 256-bit group orders. We should probably change this.
 360                 // throw ZerocoinException("Seed is too short to support the required security level.");
 361         }
 362
 363 #ifdef ZEROCOIN_DEBUG
 364         cout << "calculateGroupModulusAndOrder: pLen = " << pLen << endl;
 365 #endif
 366
 367         // Generate a random prime for the group order.
 368         // This may throw an exception, which we'll pass upwards.
 369         // Result is the value "resultGroupOrder", "qseed" and "qgen_counter".
 370         uint256     qseed;
 371         uint32_t    qgen_counter;
 372         *resultGroupOrder = generateRandomPrime(qLen, seed, &qseed, &qgen_counter);
 373
 374         // Using ⎡pLen / 2 + 1⎤ as the length and qseed as the input_seed, use the random prime
 375         // routine to obtain p0 , pseed, and pgen_counter. We pass exceptions upward.
 376         uint32_t    p0len = ceil((pLen / 2.0) + 1);
 377         uint256     pseed;
 378         uint32_t    pgen_counter;
 379         Bignum p0 = generateRandomPrime(p0len, qseed, &pseed, &pgen_counter);
 380
 381         // Set x = 0, old_counter = pgen_counter
 382         uint32_t    old_counter = pgen_counter;
 383
 384         // Generate a random integer "x" of pLen bits
 385         uint32_t iterations;
 386         Bignum x = generateIntegerFromSeed(pLen, pseed, &iterations);
 387         pseed += (iterations + 1);
 388
 389         // Set x = 2^{pLen−1} + (x mod 2^{pLen–1}).
 390         Bignum powerOfTwo = Bignum(2).pow(pLen-1);
 391         x = powerOfTwo + (x % powerOfTwo);
 392
 393         // t = ⎡x / (2 * resultGroupOrder * p0)⎤.
 394         // TODO: we don't have a ceiling function
 395         Bignum t = x / (Bignum(2) * (*resultGroupOrder) * p0);
 396
 397         // Now loop until we find a valid prime "p" or we fail due to
 398         // pgen_counter exceeding ((4*pLen) + old_counter).
 399         for ( ; pgen_counter <= ((4*pLen) + old_counter) ; pgen_counter++) {
 400                 // If (2 * t * resultGroupOrder * p0 + 1) > 2^{pLen}, then
 401                 // t = ⎡2^{pLen−1} / (2 * resultGroupOrder * p0)⎤.
 402                 powerOfTwo = Bignum(2).pow(pLen);
 403                 Bignum prod = (Bignum(2) * t * (*resultGroupOrder) * p0) + Bignum(1);
 404                 if (prod > powerOfTwo) {
 405                         // TODO: implement a ceil function
 406                         t = Bignum(2).pow(pLen-1) / (Bignum(2) * (*resultGroupOrder) * p0);
 407                 }
 408
 409                 // Compute a candidate prime resultModulus = 2tqp0 + 1.
 410                 *resultModulus = (Bignum(2) * t * (*resultGroupOrder) * p0) + Bignum(1);
 411
 412                 // Verify that resultModulus is prime. First generate a pseudorandom integer "a".
 413                 Bignum a = generateIntegerFromSeed(pLen, pseed, &iterations);
 414                 pseed += iterations + 1;
 415
 416                 // Set a = 2 + (a mod (resultModulus–3)).
 417                 a = Bignum(2) + (a % ((*resultModulus) - Bignum(3)));
 418
 419                 // Set z = a^{2 * t * resultGroupOrder} mod resultModulus
 420                 Bignum z = a.pow_mod(Bignum(2) * t * (*resultGroupOrder), (*resultModulus));
 421
 422                 // If GCD(z–1, resultModulus) == 1 AND (z^{p0} mod resultModulus == 1)
 423                 // then we have found our result. Return.
 424                 if ((resultModulus->gcd(z - Bignum(1))).isOne() &&
 425                         (z.pow_mod(p0, (*resultModulus))).isOne()) {
 426                         // Success! Return the seeds and primes.
 427                         *resultPseed = pseed;
 428                         *resultQseed = qseed;
 429                         return;
 430                 }
 431
 432                 // This prime did not work out. Increment "t" and try again.
 433                 t = t + Bignum(1);
 434         } // loop continues until pgen_counter exceeds a limit
 435
 436         // We reach this point only if we exceeded our maximum iteration count.
 437         // Throw an exception.
 438         throw ZerocoinException("Unable to generate a prime modulus for the group");
 439 }
 440
 441 /// \brief Deterministically compute a generator for a given group.
 442 /// \param seed                         A first seed for the process.
 443 /// \param pSeed                        A second seed for the process.
 444 /// \param qSeed                        A third seed for the process.
 445 /// \param modulus                      Proposed prime modulus for the field.
 446 /// \param groupOrder                   Proposed order of the group.
 447 /// \param index                        Index value, selects which generator you're building.
 448 /// \return                             The resulting generator.
 449 /// \throws                             A ZerocoinException if error.
 450 ///
 451 /// Generates a random group generator deterministically as a function of (seed,pSeed,qSeed)
 452 /// Uses the algorithm described in FIPS 186-3 Appendix A.2.3.
 453
 454 Bignum
 455 calculateGroupGenerator(uint256 seed, uint256 pSeed, uint256 qSeed, Bignum modulus, Bignum groupOrder, uint32_t index)
 456 {
 457         Bignum result;
 458
 459         // Verify that 0 <= index < 256
 460         if (index > 255) {
 461                 throw ZerocoinException("Invalid index for group generation");
 462         }
 463
 464         // Compute e = (modulus - 1) / groupOrder
 465         Bignum e = (modulus - Bignum(1)) / groupOrder;
 466
 467         // Loop until we find a generator
 468         for (uint32_t count = 1; count < MAX_GENERATOR_ATTEMPTS; count++) {
 469                 // hash = Hash(seed || pSeed || qSeed || “ggen” || index || count
 470                 uint256 hash = calculateGeneratorSeed(seed, pSeed, qSeed, "ggen", index, count);
 471                 Bignum W(hash);
 472
 473                 // Compute result = W^e mod p
 474                 result = W.pow_mod(e, modulus);
 475
 476                 // If result > 1, we have a generator
 477                 if (result > 1) {
 478                         return result;
 479                 }
 480         }
 481
 482         // We only get here if we failed to find a generator
 483         throw ZerocoinException("Unable to find a generator, too many attempts");
 484 }
 485
 486 /// \brief Deterministically compute a random prime number.
 487 /// \param primeBitLen                  Desired bit length of the prime.
 488 /// \param in_seed                      Input seed for the process.
 489 /// \param out_seed                     Result: output seed from the process.
 490 /// \param prime_gen_counter            Result: number of iterations required.
 491 /// \return                             The resulting prime number.
 492 /// \throws                             A ZerocoinException if error.
 493 ///
 494 /// Generates a random prime number of primeBitLen bits from a given input
 495 /// seed. Uses the Shawe-Taylor algorithm as described in FIPS 186-3
 496 /// Appendix C.6. This is a recursive function.
 497
 498 Bignum
 499 generateRandomPrime(uint32_t primeBitLen, uint256 in_seed, uint256 *out_seed,
 500                     uint32_t *prime_gen_counter)
 501 {
 502         // Verify that primeBitLen is not too small
 503         if (primeBitLen < 2) {
 504                 throw ZerocoinException("Prime length is too short");
 505         }
 506
 507         // If primeBitLen < 33 bits, perform the base case.
 508         if (primeBitLen < 33) {
 509                 Bignum result(0);
 510
 511                 // Set prime_seed = in_seed, prime_gen_counter = 0.
 512                 uint256     prime_seed = in_seed;
 513                 (*prime_gen_counter) = 0;
 514
 515                 // Loop up to "4 * primeBitLen" iterations.
 516                 while ((*prime_gen_counter) < (4 * primeBitLen)) {
 517
 518                         // Generate a pseudorandom integer "c" of length primeBitLength bits
 519                         uint32_t iteration_count;
 520                         Bignum c = generateIntegerFromSeed(primeBitLen, prime_seed, &iteration_count);
 521 #ifdef ZEROCOIN_DEBUG
 522                         cout << "generateRandomPrime: primeBitLen = " << primeBitLen << endl;
 523                         cout << "Generated c = " << c << endl;
 524 #endif
 525
 526                         prime_seed += (iteration_count + 1);
 527                         (*prime_gen_counter)++;
 528
 529                         // Set "intc" to be the least odd integer >= "c" we just generated
 530                         uint32_t intc = c.getulong();
 531                         intc = (2 * floor(intc / 2.0)) + 1;
 532 #ifdef ZEROCOIN_DEBUG
 533                         cout << "Should be odd. c = " << intc << endl;
 534                         cout << "The big num is: c = " << c << endl;
 535 #endif
 536
 537                         // Perform trial division on this (relatively small) integer to determine if "intc"
 538                         // is prime. If so, return success.
 539                         if (primalityTestByTrialDivision(intc)) {
 540                                 // Return "intc" converted back into a Bignum and "prime_seed". We also updated
 541                                 // the variable "prime_gen_counter" in previous statements.
 542                                 result = intc;
 543                                 *out_seed = prime_seed;
 544
 545                                 // Success
 546                                 return result;
 547                         }
 548                 } // while()
 549
 550                 // If we reached this point there was an error finding a candidate prime
 551                 // so throw an exception.
 552                 throw ZerocoinException("Unable to find prime in Shawe-Taylor algorithm");
 553
 554                 // END OF BASE CASE
 555         }
 556         // If primeBitLen >= 33 bits, perform the recursive case.
 557         else {
 558                 // Recurse to find a new random prime of roughly half the size
 559                 uint32_t newLength = ceil((double)primeBitLen / 2.0) + 1;
 560                 Bignum c0 = generateRandomPrime(newLength, in_seed, out_seed, prime_gen_counter);
 561
 562                 // Generate a random integer "x" of primeBitLen bits using the output
 563                 // of the previous call.
 564                 uint32_t numIterations;
 565                 Bignum x = generateIntegerFromSeed(primeBitLen, *out_seed, &numIterations);
 566                 (*out_seed) += numIterations + 1;
 567
 568                 // Compute "t" = ⎡x / (2 * c0⎤
 569                 // TODO no Ceiling call
 570                 Bignum t = x / (Bignum(2) * c0);
 571
 572                 // Repeat the following procedure until we find a prime (or time out)
 573                 for (uint32_t testNum = 0; testNum < MAX_PRIMEGEN_ATTEMPTS; testNum++) {
 574
 575                         // If ((2 * t * c0) + 1 > 2^{primeBitLen}),
 576                         // then t = ⎡2^{primeBitLen} – 1 / (2 * c0)⎤.
 577                         if ((Bignum(2) * t * c0) > (Bignum(2).pow(Bignum(primeBitLen)))) {
 578                                 t = ((Bignum(2).pow(Bignum(primeBitLen))) - Bignum(1)) / (Bignum(2) * c0);
 579                         }
 580
 581                         // Set c = (2 * t * c0) + 1
 582                         Bignum c = (Bignum(2) * t * c0) + Bignum(1);
 583
 584                         // Increment prime_gen_counter
 585                         (*prime_gen_counter)++;
 586
 587                         // Test "c" for primality as follows:
 588                         // 1. First pick an integer "a" in between 2 and (c - 2)
 589                         Bignum a = generateIntegerFromSeed(c.bitSize(), (*out_seed), &numIterations);
 590                         a = Bignum(2) + (a % (c - Bignum(3)));
 591                         (*out_seed) += (numIterations + 1);
 592
 593                         // 2. Compute "z" = a^{2*t} mod c
 594                         Bignum z = a.pow_mod(Bignum(2) * t, c);
 595
 596                         // 3. Check if "c" is prime.
 597                         //    Specifically, verify that gcd((z-1), c) == 1 AND (z^c0 mod c) == 1
 598                         // If so we return "c" as our result.
 599                         if (c.gcd(z - Bignum(1)).isOne() && z.pow_mod(c0, c).isOne()) {
 600                                 // Return "c", out_seed and prime_gen_counter
 601                                 // (the latter two of which were already updated)
 602                                 return c;
 603                         }
 604
 605                         // 4. If the test did not succeed, increment "t" and loop
 606                         t = t + Bignum(1);
 607                 } // end of test loop
 608         }
 609
 610         // We only reach this point if the test loop has iterated MAX_PRIMEGEN_ATTEMPTS
 611         // and failed to identify a valid prime. Throw an exception.
 612         throw ZerocoinException("Unable to generate random prime (too many tests)");
 613 }
 614
 615 Bignum
 616 generateIntegerFromSeed(uint32_t numBits, uint256 seed, uint32_t *numIterations)
 617 {
 618         Bignum      result(0);
 619         uint32_t    iterations = ceil((double)numBits / (double)HASH_OUTPUT_BITS);
 620
 621 #ifdef ZEROCOIN_DEBUG
 622         cout << "numBits = " << numBits << endl;
 623         cout << "iterations = " << iterations << endl;
 624 #endif
 625
 626         // Loop "iterations" times filling up the value "result" with random bits
 627         for (uint32_t count = 0; count < iterations; count++) {
 628                 // result += ( H(pseed + count) * 2^{count * p0len} )
 629                 result += Bignum(calculateHash(seed + count)) * Bignum(2).pow(count * HASH_OUTPUT_BITS);
 630         }
 631
 632         result = Bignum(2).pow(numBits - 1) + (result % (Bignum(2).pow(numBits - 1)));
 633
 634         // Return the number of iterations and the result
 635         *numIterations = iterations;
 636         return result;
 637 }
 638
 639 /// \brief Determines whether a uint32_t is a prime through trial division.
 640 /// \param candidate       Candidate to test.
 641 /// \return                true if the value is prime, false otherwise
 642 ///
 643 /// Performs trial division to determine whether a uint32_t is prime.
 644
 645 bool
 646 primalityTestByTrialDivision(uint32_t candidate)
 647 {
 648         // TODO: HACK HACK WRONG WRONG
 649         Bignum canBignum(candidate);
 650
 651         return canBignum.isPrime();
 652 }
 653
 654 } // namespace libzerocoin