1 /// \file ParamGeneration.cpp
3 /// \brief Parameter manipulation routines for the Zerocoin cryptographic
6 /// \author Ian Miers, Christina Garman and Matthew Green
9 /// \copyright Copyright 2013 Ian Miers, Christina Garman and Matthew Green
10 /// \license This project is released under the MIT license.
17 namespace libzerocoin {
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
24 /// \throws ZerocoinException if the process fails
26 /// Fills in a ZC_Params data structure deterministically from
27 /// a trustworthy RSA modulus "N", which is provided as a Bignum.
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.
38 CalculateParams(Params ¶ms, Bignum N, string aux, uint32_t securityLevel)
40 params.initialized = false;
41 params.accumulatorParams.initialized = false;
43 // Verify that |N| is > 1023 bits.
44 uint32_t NLen = N.bitSize();
46 throw ZerocoinException("Modulus must be at least 1023 bits");
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.");
54 // Set the accumulator modulus to "N".
55 params.accumulatorParams.accumulatorModulus = N;
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.
63 calculateGroupParamLengths(NLen - 2, securityLevel, &pLen, &qLen);
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),
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);
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);
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.
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);
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
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);
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);
107 // If all went well, mark params as successfully initialized.
108 params.accumulatorParams.initialized = true;
110 // If all went well, mark params as successfully initialized.
111 params.initialized = true;
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
121 /// Returns the hash of the value.
124 calculateGeneratorSeed(uint256 seed, uint256 pSeed, uint256 qSeed, string label, uint32_t index, uint32_t count)
126 CHashWriter hasher(0,0);
129 // Compute the hash of:
130 // <modulus>||<securitylevel>||<auxString>||groupName
132 hasher << string("||");
134 hasher << string("||");
136 hasher << string("||");
138 hasher << string("||");
140 hasher << string("||");
143 return hasher.GetHash();
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
153 /// Returns the hash of the value.
156 calculateSeed(Bignum modulus, string auxString, uint32_t securityLevel, string groupName)
158 CHashWriter hasher(0,0);
161 // Compute the hash of:
162 // <modulus>||<securitylevel>||<auxString>||groupName
164 hasher << string("||");
165 hasher << securityLevel;
166 hasher << string("||");
168 hasher << string("||");
171 return hasher.GetHash();
175 calculateHash(uint256 input)
177 CHashWriter hasher(0,0);
179 // Compute the hash of "input"
182 return hasher.GetHash();
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
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:
197 /// securityLevel = 80: pLen = 1024, qLen = 256
198 /// securityLevel = 112: pLen = 2048, qLen = 256
199 /// securityLevel = 128: qLen = 3072, qLen = 320
201 /// If the length of "p" exceeds the length provided in "maxPLen", or
202 /// if "securityLevel < 80" this routine throws an exception.
205 calculateGroupParamLengths(uint32_t maxPLen, uint32_t securityLevel,
206 uint32_t *pLen, uint32_t *qLen)
210 if (securityLevel < 80) {
211 throw ZerocoinException("Security level must be at least 80 bits.");
212 } else if (securityLevel == 80) {
215 } else if (securityLevel <= 112) {
218 } else if (securityLevel <= 128) {
222 throw ZerocoinException("Security level not supported.");
225 if (*pLen > maxPLen) {
226 throw ZerocoinException("Modulus size is too small for this security level.");
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
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".
243 deriveIntegerGroupParams(uint256 seed, uint32_t pLen, uint32_t qLen)
245 IntegerGroupParams result;
248 uint256 pSeed, qSeed;
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);
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);
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");
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
285 /// Given "q" calculates the description of a group G of prime order "q" embedded within
289 deriveIntegerGroupFromOrder(Bignum &groupOrder)
291 IntegerGroupParams result;
293 // Set the order to "groupOrder"
294 result.groupOrder = groupOrder;
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);
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)) {
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);
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");
335 // If we reached this point group generation has failed. Throw an exception.
336 throw ZerocoinException("Too many attempts to generate Schnorr group.");
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.
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".
353 calculateGroupModulusAndOrder(uint256 seed, uint32_t pLen, uint32_t qLen,
354 Bignum *resultModulus, Bignum *resultGroupOrder,
355 uint256 *resultPseed, uint256 *resultQseed)
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.");
363 #ifdef ZEROCOIN_DEBUG
364 cout << "calculateGroupModulusAndOrder: pLen = " << pLen << endl;
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".
371 uint32_t qgen_counter;
372 *resultGroupOrder = generateRandomPrime(qLen, seed, &qseed, &qgen_counter);
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);
378 uint32_t pgen_counter;
379 Bignum p0 = generateRandomPrime(p0len, qseed, &pseed, &pgen_counter);
381 // Set x = 0, old_counter = pgen_counter
382 uint32_t old_counter = pgen_counter;
384 // Generate a random integer "x" of pLen bits
386 Bignum x = generateIntegerFromSeed(pLen, pseed, &iterations);
387 pseed += (iterations + 1);
389 // Set x = 2^{pLen−1} + (x mod 2^{pLen–1}).
390 Bignum powerOfTwo = Bignum(2).pow(pLen-1);
391 x = powerOfTwo + (x % powerOfTwo);
393 // t = ⎡x / (2 * resultGroupOrder * p0)⎤.
394 // TODO: we don't have a ceiling function
395 Bignum t = x / (Bignum(2) * (*resultGroupOrder) * p0);
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);
409 // Compute a candidate prime resultModulus = 2tqp0 + 1.
410 *resultModulus = (Bignum(2) * t * (*resultGroupOrder) * p0) + Bignum(1);
412 // Verify that resultModulus is prime. First generate a pseudorandom integer "a".
413 Bignum a = generateIntegerFromSeed(pLen, pseed, &iterations);
414 pseed += iterations + 1;
416 // Set a = 2 + (a mod (resultModulus–3)).
417 a = Bignum(2) + (a % ((*resultModulus) - Bignum(3)));
419 // Set z = a^{2 * t * resultGroupOrder} mod resultModulus
420 Bignum z = a.pow_mod(Bignum(2) * t * (*resultGroupOrder), (*resultModulus));
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;
432 // This prime did not work out. Increment "t" and try again.
434 } // loop continues until pgen_counter exceeds a limit
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");
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.
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.
455 calculateGroupGenerator(uint256 seed, uint256 pSeed, uint256 qSeed, Bignum modulus, Bignum groupOrder, uint32_t index)
459 // Verify that 0 <= index < 256
461 throw ZerocoinException("Invalid index for group generation");
464 // Compute e = (modulus - 1) / groupOrder
465 Bignum e = (modulus - Bignum(1)) / groupOrder;
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);
473 // Compute result = W^e mod p
474 result = W.pow_mod(e, modulus);
476 // If result > 1, we have a generator
482 // We only get here if we failed to find a generator
483 throw ZerocoinException("Unable to find a generator, too many attempts");
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.
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.
499 generateRandomPrime(uint32_t primeBitLen, uint256 in_seed, uint256 *out_seed,
500 uint32_t *prime_gen_counter)
502 // Verify that primeBitLen is not too small
503 if (primeBitLen < 2) {
504 throw ZerocoinException("Prime length is too short");
507 // If primeBitLen < 33 bits, perform the base case.
508 if (primeBitLen < 33) {
511 // Set prime_seed = in_seed, prime_gen_counter = 0.
512 uint256 prime_seed = in_seed;
513 (*prime_gen_counter) = 0;
515 // Loop up to "4 * primeBitLen" iterations.
516 while ((*prime_gen_counter) < (4 * primeBitLen)) {
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;
526 prime_seed += (iteration_count + 1);
527 (*prime_gen_counter)++;
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;
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.
543 *out_seed = prime_seed;
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");
556 // If primeBitLen >= 33 bits, perform the recursive case.
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);
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;
568 // Compute "t" = ⎡x / (2 * c0⎤
569 // TODO no Ceiling call
570 Bignum t = x / (Bignum(2) * c0);
572 // Repeat the following procedure until we find a prime (or time out)
573 for (uint32_t testNum = 0; testNum < MAX_PRIMEGEN_ATTEMPTS; testNum++) {
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);
581 // Set c = (2 * t * c0) + 1
582 Bignum c = (Bignum(2) * t * c0) + Bignum(1);
584 // Increment prime_gen_counter
585 (*prime_gen_counter)++;
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);
593 // 2. Compute "z" = a^{2*t} mod c
594 Bignum z = a.pow_mod(Bignum(2) * t, c);
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)
605 // 4. If the test did not succeed, increment "t" and loop
607 } // end of test loop
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)");
616 generateIntegerFromSeed(uint32_t numBits, uint256 seed, uint32_t *numIterations)
619 uint32_t iterations = ceil((double)numBits / (double)HASH_OUTPUT_BITS);
621 #ifdef ZEROCOIN_DEBUG
622 cout << "numBits = " << numBits << endl;
623 cout << "iterations = " << iterations << endl;
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);
632 result = Bignum(2).pow(numBits - 1) + (result % (Bignum(2).pow(numBits - 1)));
634 // Return the number of iterations and the result
635 *numIterations = iterations;
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
643 /// Performs trial division to determine whether a uint32_t is prime.
646 primalityTestByTrialDivision(uint32_t candidate)
648 // TODO: HACK HACK WRONG WRONG
649 Bignum canBignum(candidate);
651 return canBignum.isPrime();
654 } // namespace libzerocoin