123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626 |
- // ECOin - Copyright (c) - 2014/2022 - GPLv3 - epsylon@riseup.net (https://03c8.net)
- #include <string>
- #include "Zerocoin.h"
- using namespace std;
- namespace libzerocoin {
- void
- CalculateParams(Params ¶ms, CBigNum N, string aux, uint32_t securityLevel)
- {
- params.initialized = false;
- params.accumulatorParams.initialized = false;
- // Verify that |N| is > 1023 bits.
- uint32_t NLen = N.bitSize();
- if (NLen < 1023) {
- throw ZerocoinException("Modulus must be at least 1023 bits");
- }
- // Verify that "securityLevel" is at least 80 bits (minimum).
- if (securityLevel < 80) {
- throw ZerocoinException("Security level must be at least 80 bits.");
- }
- // Set the accumulator modulus to "N".
- params.accumulatorParams.accumulatorModulus = N;
- // Calculate the required size of the field "F_p" into which
- // we're embedding the coin commitment group. This may throw an
- // exception if the securityLevel is too large to be supported
- // by the current modulus.
- uint32_t pLen = 0;
- uint32_t qLen = 0;
- calculateGroupParamLengths(NLen - 2, securityLevel, &pLen, &qLen);
- // Calculate candidate parameters ("p", "q") for the coin commitment group
- // using a deterministic process based on "N", the "aux" string, and
- // the dedicated string "COMMITMENTGROUP".
- params.coinCommitmentGroup = deriveIntegerGroupParams(calculateSeed(N, aux, securityLevel, STRING_COMMIT_GROUP),
- pLen, qLen);
- // Next, we derive parameters for a second Accumulated Value commitment group.
- // This is a Schnorr group with the specific property that the order of the group
- // must be exactly equal to "q" from the commitment group. We set
- // the modulus of the new group equal to "2q+1" and test to see if this is prime.
- params.serialNumberSoKCommitmentGroup = deriveIntegerGroupFromOrder(params.coinCommitmentGroup.modulus);
- // Calculate the parameters for the internal commitment
- // using the same process.
- params.accumulatorParams.accumulatorPoKCommitmentGroup = deriveIntegerGroupParams(calculateSeed(N, aux, securityLevel, STRING_AIC_GROUP),
- qLen + 300, qLen + 1);
- // Calculate the parameters for the accumulator QRN commitment generators. This isn't really
- // a whole group, just a pair of random generators in QR_N.
- uint32_t resultCtr;
- params.accumulatorParams.accumulatorQRNCommitmentGroup.g = generateIntegerFromSeed(NLen - 1,
- calculateSeed(N, aux, securityLevel, STRING_QRNCOMMIT_GROUPG),
- &resultCtr).pow_mod(CBigNum(2), N);
- params.accumulatorParams.accumulatorQRNCommitmentGroup.h = generateIntegerFromSeed(NLen - 1,
- calculateSeed(N, aux, securityLevel, STRING_QRNCOMMIT_GROUPG),
- &resultCtr).pow_mod(CBigNum(2), N);
- // Calculate the accumulator base, which we calculate as "u = C**2 mod N"
- // where C is an arbitrary value. In the unlikely case that "u = 1" we increment
- // "C" and repeat.
- CBigNum constant(ACCUMULATOR_BASE_CONSTANT);
- params.accumulatorParams.accumulatorBase = CBigNum(1);
- for (uint32_t count = 0; count < MAX_ACCUMGEN_ATTEMPTS && params.accumulatorParams.accumulatorBase.isOne(); count++) {
- params.accumulatorParams.accumulatorBase = constant.pow_mod(CBigNum(2), params.accumulatorParams.accumulatorModulus);
- }
- // Compute the accumulator range. The upper range is the largest possible coin commitment value.
- // The lower range is sqrt(upper range) + 1. Since OpenSSL doesn't have
- // a square root function we use a slightly higher approximation.
- params.accumulatorParams.maxCoinValue = params.coinCommitmentGroup.modulus;
- params.accumulatorParams.minCoinValue = CBigNum(2).pow((params.coinCommitmentGroup.modulus.bitSize() / 2) + 3);
- // If all went well, mark params as successfully initialized.
- params.accumulatorParams.initialized = true;
- // If all went well, mark params as successfully initialized.
- params.initialized = true;
- }
- /// \brief Format a seed string by hashing several values.
- /// \param N A CBigNum
- /// \param aux An auxiliary string
- /// \param securityLevel The security level in bits
- /// \param groupName A group description string
- /// \throws ZerocoinException if the process fails
- ///
- /// Returns the hash of the value.
- uint256
- calculateGeneratorSeed(uint256 seed, uint256 pSeed, uint256 qSeed, string label, uint32_t index, uint32_t count)
- {
- CHashWriter hasher(0,0);
- uint256 hash;
- // Compute the hash of:
- // <modulus>||<securitylevel>||<auxString>||groupName
- hasher << seed;
- hasher << string("||");
- hasher << pSeed;
- hasher << string("||");
- hasher << qSeed;
- hasher << string("||");
- hasher << label;
- hasher << string("||");
- hasher << index;
- hasher << string("||");
- hasher << count;
- return hasher.GetHash();
- }
- /// \brief Format a seed string by hashing several values.
- /// \param N A CBigNum
- /// \param aux An auxiliary string
- /// \param securityLevel The security level in bits
- /// \param groupName A group description string
- /// \throws ZerocoinException if the process fails
- ///
- /// Returns the hash of the value.
- uint256
- calculateSeed(CBigNum modulus, string auxString, uint32_t securityLevel, string groupName)
- {
- CHashWriter hasher(0,0);
- uint256 hash;
- // Compute the hash of:
- // <modulus>||<securitylevel>||<auxString>||groupName
- hasher << modulus;
- hasher << string("||");
- hasher << securityLevel;
- hasher << string("||");
- hasher << auxString;
- hasher << string("||");
- hasher << groupName;
- return hasher.GetHash();
- }
- uint256
- calculateHash(uint256 input)
- {
- CHashWriter hasher(0,0);
- // Compute the hash of "input"
- hasher << input;
- return hasher.GetHash();
- }
- /// \brief Calculate field/group parameter sizes based on a security level.
- /// \param maxPLen Maximum size of the field (modulus "p") in bits.
- /// \param securityLevel Required security level in bits (at least 80)
- /// \param pLen Result: length of "p" in bits
- /// \param qLen Result: length of "q" in bits
- /// \throws ZerocoinException if the process fails
- ///
- /// Calculates the appropriate sizes of "p" and "q" for a prime-order
- /// subgroup of order "q" embedded within a field "F_p". The sizes
- /// are based on a 'securityLevel' provided in symmetric-equivalent
- /// bits. Our choices slightly exceed the specs in FIPS 186-3:
- ///
- /// securityLevel = 80: pLen = 1024, qLen = 256
- /// securityLevel = 112: pLen = 2048, qLen = 256
- /// securityLevel = 128: qLen = 3072, qLen = 320
- ///
- /// If the length of "p" exceeds the length provided in "maxPLen", or
- /// if "securityLevel < 80" this routine throws an exception.
- void
- calculateGroupParamLengths(uint32_t maxPLen, uint32_t securityLevel,
- uint32_t *pLen, uint32_t *qLen)
- {
- *pLen = *qLen = 0;
- if (securityLevel < 80) {
- throw ZerocoinException("Security level must be at least 80 bits.");
- } else if (securityLevel == 80) {
- *qLen = 256;
- *pLen = 1024;
- } else if (securityLevel <= 112) {
- *qLen = 256;
- *pLen = 2048;
- } else if (securityLevel <= 128) {
- *qLen = 320;
- *pLen = 3072;
- } else {
- throw ZerocoinException("Security level not supported.");
- }
- if (*pLen > maxPLen) {
- throw ZerocoinException("Modulus size is too small for this security level.");
- }
- }
- /// \brief Deterministically compute a set of group parameters using NIST procedures.
- /// \param seedStr A byte string seeding the process.
- /// \param pLen The desired length of the modulus "p" in bits
- /// \param qLen The desired length of the order "q" in bits
- /// \return An IntegerGroupParams object
- ///
- /// Calculates the description of a group G of prime order "q" embedded within
- /// a field "F_p". The input to this routine is in arbitrary seed. It uses the
- /// algorithms described in FIPS 186-3 Appendix A.1.2 to calculate
- /// primes "p" and "q". It uses the procedure in Appendix A.2.3 to
- /// derive two generators "g", "h".
- IntegerGroupParams
- deriveIntegerGroupParams(uint256 seed, uint32_t pLen, uint32_t qLen)
- {
- IntegerGroupParams result;
- CBigNum p;
- CBigNum q;
- uint256 pSeed, qSeed;
- // Calculate "p" and "q" and "domain_parameter_seed" from the
- // "seed" buffer above, using the procedure described in NIST
- // FIPS 186-3, Appendix A.1.2.
- calculateGroupModulusAndOrder(seed, pLen, qLen, result.modulus,
- result.groupOrder, &pSeed, &qSeed);
- // Calculate the generators "g", "h" using the process described in
- // NIST FIPS 186-3, Appendix A.2.3. This algorithm takes ("p", "q",
- // "domain_parameter_seed", "index"). We use "index" value 1
- // to generate "g" and "index" value 2 to generate "h".
- result.g = calculateGroupGenerator(seed, pSeed, qSeed, result.modulus, result.groupOrder, 1);
- result.h = calculateGroupGenerator(seed, pSeed, qSeed, result.modulus, result.groupOrder, 2);
- // Perform some basic tests to make sure we have good parameters
- if ((uint32_t)(result.modulus.bitSize()) < pLen || // modulus is pLen bits long
- (uint32_t)(result.groupOrder.bitSize()) < qLen || // order is qLen bits long
- !(result.modulus.isPrime()) || // modulus is prime
- !(result.groupOrder.isPrime()) || // order is prime
- !((result.g.pow_mod(result.groupOrder, result.modulus)).isOne()) || // g^order mod modulus = 1
- !((result.h.pow_mod(result.groupOrder, result.modulus)).isOne()) || // h^order mod modulus = 1
- ((result.g.pow_mod(CBigNum(100), result.modulus)).isOne()) || // g^100 mod modulus != 1
- ((result.h.pow_mod(CBigNum(100), result.modulus)).isOne()) || // h^100 mod modulus != 1
- result.g == result.h || // g != h
- result.g.isOne()) { // g != 1
- // If any of the above tests fail, throw an exception
- throw ZerocoinException("Group parameters are not valid");
- }
- return result;
- }
- /// \brief Deterministically compute a set of group parameters with a specified order.
- /// \param groupOrder The order of the group
- /// \return An IntegerGroupParams object
- ///
- /// Given "q" calculates the description of a group G of prime order "q" embedded within
- /// a field "F_p".
- IntegerGroupParams
- deriveIntegerGroupFromOrder(CBigNum &groupOrder)
- {
- IntegerGroupParams result;
- // Set the order to "groupOrder"
- result.groupOrder = groupOrder;
- // Try possible values for "modulus" of the form "groupOrder * 2 * i" where
- // "p" is prime and i is a counter starting at 1.
- for (uint32_t i = 1; i < NUM_SCHNORRGEN_ATTEMPTS; i++) {
- // Set modulus equal to "groupOrder * 2 * i"
- result.modulus = (result.groupOrder * CBigNum(i*2)) + CBigNum(1);
- // Test the result for primality
- // TODO: This is a probabilistic routine and thus not the right choice
- if (result.modulus.isPrime(256)) {
- // Success.
- //
- // Calculate the generators "g", "h" using the process described in
- // NIST FIPS 186-3, Appendix A.2.3. This algorithm takes ("p", "q",
- // "domain_parameter_seed", "index"). We use "index" value 1
- // to generate "g" and "index" value 2 to generate "h".
- uint256 seed = calculateSeed(groupOrder, "", 128, "");
- uint256 pSeed = calculateHash(seed);
- uint256 qSeed = calculateHash(pSeed);
- result.g = calculateGroupGenerator(seed, pSeed, qSeed, result.modulus, result.groupOrder, 1);
- result.h = calculateGroupGenerator(seed, pSeed, qSeed, result.modulus, result.groupOrder, 2);
- // Perform some basic tests to make sure we have good parameters
- if (!(result.modulus.isPrime()) || // modulus is prime
- !(result.groupOrder.isPrime()) || // order is prime
- !((result.g.pow_mod(result.groupOrder, result.modulus)).isOne()) || // g^order mod modulus = 1
- !((result.h.pow_mod(result.groupOrder, result.modulus)).isOne()) || // h^order mod modulus = 1
- ((result.g.pow_mod(CBigNum(100), result.modulus)).isOne()) || // g^100 mod modulus != 1
- ((result.h.pow_mod(CBigNum(100), result.modulus)).isOne()) || // h^100 mod modulus != 1
- result.g == result.h || // g != h
- result.g.isOne()) { // g != 1
- // If any of the above tests fail, throw an exception
- throw ZerocoinException("Group parameters are not valid");
- }
- return result;
- }
- }
- // If we reached this point group generation has failed. Throw an exception.
- throw ZerocoinException("Too many attempts to generate Schnorr group.");
- }
- /// \brief Deterministically compute a group description using NIST procedures.
- /// \param seed A byte string seeding the process.
- /// \param pLen The desired length of the modulus "p" in bits
- /// \param qLen The desired length of the order "q" in bits
- /// \param resultModulus A value "p" describing a finite field "F_p"
- /// \param resultGroupOrder A value "q" describing the order of a subgroup
- /// \param resultDomainParameterSeed A resulting seed for use in later calculations.
- ///
- /// Calculates the description of a group G of prime order "q" embedded within
- /// a field "F_p". The input to this routine is in arbitrary seed. It uses the
- /// algorithms described in FIPS 186-3 Appendix A.1.2 to calculate
- /// primes "p" and "q".
- void calculateGroupModulusAndOrder(uint256 seed, uint32_t pLen, uint32_t qLen,
- CBigNum &resultModulus, CBigNum &resultGroupOrder,
- uint256 *resultPseed, uint256 *resultQseed)
- {
- // Verify that the seed length is >= qLen
- if (qLen > (sizeof(seed)) * 8) {
- // TODO: The use of 256-bit seeds limits us to 256-bit group orders. We should probably change this.
- // throw ZerocoinException("Seed is too short to support the required security level.");
- }
- #ifdef ZEROCOIN_DEBUG
- cout << "calculateGroupModulusAndOrder: pLen = " << pLen << endl;
- #endif
- // Generate a random prime for the group order.
- // This may throw an exception, which we'll pass upwards.
- // Result is the value "resultGroupOrder", "qseed" and "qgen_counter".
- uint256 qseed;
- uint32_t qgen_counter;
- resultGroupOrder = generateRandomPrime(qLen, seed, &qseed, &qgen_counter);
- // Using ⎡pLen / 2 + 1⎤ as the length and qseed as the input_seed, use the random prime
- // routine to obtain p0 , pseed, and pgen_counter. We pass exceptions upward.
- uint32_t p0len = ceil((pLen / 2.0) + 1);
- uint256 pseed;
- uint32_t pgen_counter;
- CBigNum p0 = generateRandomPrime(p0len, qseed, &pseed, &pgen_counter);
- // Set x = 0, old_counter = pgen_counter
- uint32_t old_counter = pgen_counter;
- // Generate a random integer "x" of pLen bits
- uint32_t iterations;
- CBigNum x = generateIntegerFromSeed(pLen, pseed, &iterations);
- pseed += (iterations + 1);
- // Set x = 2^{pLen−1} + (x mod 2^{pLen–1}).
- CBigNum powerOfTwo = CBigNum(2).pow(pLen-1);
- x = powerOfTwo + (x % powerOfTwo);
- // t = ⎡x / (2 * resultGroupOrder * p0)⎤.
- // TODO: we don't have a ceiling function
- CBigNum t = x / (CBigNum(2) * resultGroupOrder * p0);
- // Now loop until we find a valid prime "p" or we fail due to
- // pgen_counter exceeding ((4*pLen) + old_counter).
- for ( ; pgen_counter <= ((4*pLen) + old_counter) ; pgen_counter++) {
- // If (2 * t * resultGroupOrder * p0 + 1) > 2^{pLen}, then
- // t = ⎡2^{pLen−1} / (2 * resultGroupOrder * p0)⎤.
- powerOfTwo = CBigNum(2).pow(pLen);
- CBigNum prod = (CBigNum(2) * t * resultGroupOrder * p0) + CBigNum(1);
- if (prod > powerOfTwo) {
- // TODO: implement a ceil function
- t = CBigNum(2).pow(pLen-1) / (CBigNum(2) * resultGroupOrder * p0);
- }
- // Compute a candidate prime resultModulus = 2tqp0 + 1.
- resultModulus = (CBigNum(2) * t * resultGroupOrder * p0) + CBigNum(1);
- // Verify that resultModulus is prime. First generate a pseudorandom integer "a".
- CBigNum a = generateIntegerFromSeed(pLen, pseed, &iterations);
- pseed += iterations + 1;
- // Set a = 2 + (a mod (resultModulus–3)).
- a = CBigNum(2) + (a % (resultModulus - CBigNum(3)));
- // Set z = a^{2 * t * resultGroupOrder} mod resultModulus
- CBigNum z = a.pow_mod(CBigNum(2) * t * resultGroupOrder, resultModulus);
- // If GCD(z–1, resultModulus) == 1 AND (z^{p0} mod resultModulus == 1)
- // then we have found our result. Return.
- if ((resultModulus.gcd(z - CBigNum(1))).isOne() &&
- (z.pow_mod(p0, resultModulus)).isOne()) {
- // Success! Return the seeds and primes.
- *resultPseed = pseed;
- *resultQseed = qseed;
- return;
- }
- // This prime did not work out. Increment "t" and try again.
- t = t + CBigNum(1);
- } // loop continues until pgen_counter exceeds a limit
- // We reach this point only if we exceeded our maximum iteration count.
- // Throw an exception.
- throw ZerocoinException("Unable to generate a prime modulus for the group");
- }
- /// \brief Deterministically compute a generator for a given group.
- /// \param seed A first seed for the process.
- /// \param pSeed A second seed for the process.
- /// \param qSeed A third seed for the process.
- /// \param modulus Proposed prime modulus for the field.
- /// \param groupOrder Proposed order of the group.
- /// \param index Index value, selects which generator you're building.
- /// \return The resulting generator.
- /// \throws A ZerocoinException if error.
- ///
- /// Generates a random group generator deterministically as a function of (seed,pSeed,qSeed)
- /// Uses the algorithm described in FIPS 186-3 Appendix A.2.3.
- CBigNum
- calculateGroupGenerator(uint256 seed, uint256 pSeed, uint256 qSeed, CBigNum modulus, CBigNum groupOrder, uint32_t index)
- {
- CBigNum result;
- // Verify that 0 <= index < 256
- if (index > 255) {
- throw ZerocoinException("Invalid index for group generation");
- }
- // Compute e = (modulus - 1) / groupOrder
- CBigNum e = (modulus - CBigNum(1)) / groupOrder;
- // Loop until we find a generator
- for (uint32_t count = 1; count < MAX_GENERATOR_ATTEMPTS; count++) {
- // hash = Hash(seed || pSeed || qSeed || “ggen” || index || count
- uint256 hash = calculateGeneratorSeed(seed, pSeed, qSeed, "ggen", index, count);
- CBigNum W(hash);
- // Compute result = W^e mod p
- result = W.pow_mod(e, modulus);
- // If result > 1, we have a generator
- if (result > 1) {
- return result;
- }
- }
- // We only get here if we failed to find a generator
- throw ZerocoinException("Unable to find a generator, too many attempts");
- }
- /// \brief Deterministically compute a random prime number.
- /// \param primeBitLen Desired bit length of the prime.
- /// \param in_seed Input seed for the process.
- /// \param out_seed Result: output seed from the process.
- /// \param prime_gen_counter Result: number of iterations required.
- /// \return The resulting prime number.
- /// \throws A ZerocoinException if error.
- ///
- /// Generates a random prime number of primeBitLen bits from a given input
- /// seed. Uses the Shawe-Taylor algorithm as described in FIPS 186-3
- /// Appendix C.6. This is a recursive function.
- CBigNum
- generateRandomPrime(uint32_t primeBitLen, uint256 in_seed, uint256 *out_seed,
- uint32_t *prime_gen_counter)
- {
- // Verify that primeBitLen is not too small
- if (primeBitLen < 2) {
- throw ZerocoinException("Prime length is too short");
- }
- // If primeBitLen < 33 bits, perform the base case.
- if (primeBitLen < 33) {
- CBigNum result(0);
- // Set prime_seed = in_seed, prime_gen_counter = 0.
- uint256 prime_seed = in_seed;
- (*prime_gen_counter) = 0;
- // Loop up to "4 * primeBitLen" iterations.
- while ((*prime_gen_counter) < (4 * primeBitLen)) {
- // Generate a pseudorandom integer "c" of length primeBitLength bits
- uint32_t iteration_count;
- CBigNum c = generateIntegerFromSeed(primeBitLen, prime_seed, &iteration_count);
- #ifdef ZEROCOIN_DEBUG
- cout << "generateRandomPrime: primeBitLen = " << primeBitLen << endl;
- cout << "Generated c = " << c << endl;
- #endif
- prime_seed += (iteration_count + 1);
- (*prime_gen_counter)++;
- // Set "intc" to be the least odd integer >= "c" we just generated
- uint32_t intc = c.getulong();
- intc = (2 * floor(intc / 2.0)) + 1;
- #ifdef ZEROCOIN_DEBUG
- cout << "Should be odd. c = " << intc << endl;
- cout << "The big num is: c = " << c << endl;
- #endif
- // Perform trial division on this (relatively small) integer to determine if "intc"
- // is prime. If so, return success.
- if (primalityTestByTrialDivision(intc)) {
- // Return "intc" converted back into a CBigNum and "prime_seed". We also updated
- // the variable "prime_gen_counter" in previous statements.
- result = intc;
- *out_seed = prime_seed;
- // Success
- return result;
- }
- } // while()
- // If we reached this point there was an error finding a candidate prime
- // so throw an exception.
- throw ZerocoinException("Unable to find prime in Shawe-Taylor algorithm");
- // END OF BASE CASE
- }
- // If primeBitLen >= 33 bits, perform the recursive case.
- else {
- // Recurse to find a new random prime of roughly half the size
- uint32_t newLength = ceil((double)primeBitLen / 2.0) + 1;
- CBigNum c0 = generateRandomPrime(newLength, in_seed, out_seed, prime_gen_counter);
- // Generate a random integer "x" of primeBitLen bits using the output
- // of the previous call.
- uint32_t numIterations;
- CBigNum x = generateIntegerFromSeed(primeBitLen, *out_seed, &numIterations);
- (*out_seed) += numIterations + 1;
- // Compute "t" = ⎡x / (2 * c0⎤
- // TODO no Ceiling call
- CBigNum t = x / (CBigNum(2) * c0);
- // Repeat the following procedure until we find a prime (or time out)
- for (uint32_t testNum = 0; testNum < MAX_PRIMEGEN_ATTEMPTS; testNum++) {
- // If ((2 * t * c0) + 1 > 2^{primeBitLen}),
- // then t = ⎡2^{primeBitLen} – 1 / (2 * c0)⎤.
- if ((CBigNum(2) * t * c0) > (CBigNum(2).pow(CBigNum(primeBitLen)))) {
- t = ((CBigNum(2).pow(CBigNum(primeBitLen))) - CBigNum(1)) / (CBigNum(2) * c0);
- }
- // Set c = (2 * t * c0) + 1
- CBigNum c = (CBigNum(2) * t * c0) + CBigNum(1);
- // Increment prime_gen_counter
- (*prime_gen_counter)++;
- // Test "c" for primality as follows:
- // 1. First pick an integer "a" in between 2 and (c - 2)
- CBigNum a = generateIntegerFromSeed(c.bitSize(), (*out_seed), &numIterations);
- a = CBigNum(2) + (a % (c - CBigNum(3)));
- (*out_seed) += (numIterations + 1);
- // 2. Compute "z" = a^{2*t} mod c
- CBigNum z = a.pow_mod(CBigNum(2) * t, c);
- // 3. Check if "c" is prime.
- // Specifically, verify that gcd((z-1), c) == 1 AND (z^c0 mod c) == 1
- // If so we return "c" as our result.
- if (c.gcd(z - CBigNum(1)).isOne() && z.pow_mod(c0, c).isOne()) {
- // Return "c", out_seed and prime_gen_counter
- // (the latter two of which were already updated)
- return c;
- }
- // 4. If the test did not succeed, increment "t" and loop
- t = t + CBigNum(1);
- } // end of test loop
- }
- // We only reach this point if the test loop has iterated MAX_PRIMEGEN_ATTEMPTS
- // and failed to identify a valid prime. Throw an exception.
- throw ZerocoinException("Unable to generate random prime (too many tests)");
- }
- CBigNum
- generateIntegerFromSeed(uint32_t numBits, uint256 seed, uint32_t *numIterations)
- {
- CBigNum result(0);
- uint32_t iterations = ceil((double)numBits / (double)HASH_OUTPUT_BITS);
- #ifdef ZEROCOIN_DEBUG
- cout << "numBits = " << numBits << endl;
- cout << "iterations = " << iterations << endl;
- #endif
- // Loop "iterations" times filling up the value "result" with random bits
- for (uint32_t count = 0; count < iterations; count++) {
- // result += ( H(pseed + count) * 2^{count * p0len} )
- result += CBigNum(calculateHash(seed + count)) * CBigNum(2).pow(count * HASH_OUTPUT_BITS);
- }
- result = CBigNum(2).pow(numBits - 1) + (result % (CBigNum(2).pow(numBits - 1)));
- // Return the number of iterations and the result
- *numIterations = iterations;
- return result;
- }
- /// \brief Determines whether a uint32_t is a prime through trial division.
- /// \param candidate Candidate to test.
- /// \return true if the value is prime, false otherwise
- ///
- /// Performs trial division to determine whether a uint32_t is prime.
- bool
- primalityTestByTrialDivision(uint32_t candidate)
- {
- CBigNum canBignum(candidate);
- return canBignum.isPrime();
- }
- } // namespace libzerocoin
|