LCOV - code coverage report
Current view: top level - src/libzerocoin - ParamGeneration.cpp (source / functions) Hit Total Coverage
Test: total_coverage.info Lines: 194 216 89.8 %
Date: 2025-02-23 09:33:43 Functions: 12 12 100.0 %

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

Generated by: LCOV version 1.14