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 ¶ms, 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
|
