random-generator.js 7.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. /*
  2. * Copyright 2018 Scytl Secure Electronic Voting SA
  3. *
  4. * All rights reserved
  5. *
  6. * See our extended copyright notice in *file 'Copyright.txt' which is part of this source code package
  7. */
  8. /* jshint node:true */
  9. 'use strict';
  10. var ZpSubgroup = require('./zp-subgroup');
  11. var Exponent = require('./exponent');
  12. var MathematicalGroupHandler = require('./group-handler');
  13. var constants = require('./constants');
  14. var validator = require('./input-validator');
  15. var forge = require('node-forge');
  16. var BigInteger = forge.jsbn.BigInteger;
  17. module.exports = MathematicalRandomGenerator;
  18. /**
  19. * @class MathematicalRandomGenerator
  20. * @classdesc The mathematical random generator API. To instantiate this object,
  21. * use the method {@link MathematicalService.newRandomGenerator}.
  22. * @hideconstructor
  23. * @param {SeureRandomService}
  24. * secureRandomService The secure random service to use.
  25. */
  26. function MathematicalRandomGenerator(secureRandomService) {
  27. var randomGenerator_ = secureRandomService.newRandomGenerator();
  28. var mathGroupHandler_ = new MathematicalGroupHandler();
  29. /**
  30. * Generates a random Zp group element belonging to the Zp subgroup provided
  31. * as input.
  32. *
  33. * @function nextZpGroupElement
  34. * @memberof MathematicalRandomGenerator
  35. * @param {ZpSubgroup}
  36. * group The Zp subgroup to which the Zp group element belongs.
  37. * @param {Object}
  38. * [options] An object containing optional arguments.
  39. * @param {SecureRandomGenerator}
  40. * [options.secureRandomGenerator=Internal generator used] The
  41. * secure random generator to use.
  42. * @param {boolean}
  43. * [options.useShortExponent=false] If <code>true</code>, then
  44. * a short exponent is to be generated for the exponentiation
  45. * used to generate the Zp group element.
  46. * @returns {ZpGroupElement} The generated Zp group element.
  47. * @throws {Error}
  48. * If the input validation fails.
  49. */
  50. this.nextZpGroupElement = function(group, options) {
  51. validator.checkIsInstanceOf(
  52. group, ZpSubgroup, 'ZpSubgroup',
  53. 'Zp subgroup to which randomly generated element is to belong');
  54. var exponent = this.nextExponent(group, options);
  55. return group.generator.exponentiate(exponent);
  56. };
  57. /**
  58. * Generates a random exponent associated with the Zp subgroup provided as
  59. * input. The value of the exponent will be within the range <code>[0,
  60. * q-1]</code>.
  61. *
  62. * @function nextExponent
  63. * @memberof MathematicalRandomGenerator
  64. * @param {ZpSubgroup}
  65. * group The Zp subgroup to which the exponent is to be
  66. * associated.
  67. * @param {Object}
  68. * [options] An object containing optional arguments.
  69. * @param {SecureRandomGenerator}
  70. * [options.secureRandomGenerator=Internal generator is used] The
  71. * secure random generator to use.
  72. * @param {boolean}
  73. * [options.useShortExponent=false] If <code>true</code>, then
  74. * a short exponent is to be generated.
  75. * @returns {Exponent} The generated exponent.
  76. * @throws {Error}
  77. * If the input validation fails.
  78. */
  79. this.nextExponent = function(group, options) {
  80. validator.checkIsInstanceOf(
  81. group, ZpSubgroup, 'ZpSubgroup',
  82. 'Zp subgroup to which randomly generated exponent is to be associated');
  83. options = options || {};
  84. var randomGenerator = options.secureRandomGenerator || randomGenerator_;
  85. validator.checkIsObjectWithProperties(
  86. randomGenerator,
  87. 'Random BigInteger generator for random exponent generation');
  88. var useShortExponent = options.useShortExponent || false;
  89. var q = group.q;
  90. var qBitLength = q.bitLength();
  91. var randomExponentBitLength;
  92. if (useShortExponent) {
  93. if (qBitLength < constants.SHORT_EXPONENT_BIT_LENGTH) {
  94. throw new Error(
  95. 'Zp subgroup order bit length must be greater than or equal to short exponent bit length : ' +
  96. constants.SHORT_EXPONENT_BIT_LENGTH + '; Found ' + qBitLength);
  97. }
  98. randomExponentBitLength = constants.SHORT_EXPONENT_BIT_LENGTH;
  99. } else {
  100. randomExponentBitLength = qBitLength;
  101. }
  102. var randomExponentValue;
  103. var randomExponentFound = false;
  104. while (!randomExponentFound) {
  105. randomExponentValue =
  106. randomGenerator.nextBigInteger(randomExponentBitLength);
  107. if (randomExponentValue.compareTo(q) < 0) {
  108. randomExponentFound = true;
  109. }
  110. }
  111. return new Exponent(q, randomExponentValue);
  112. };
  113. /**
  114. * Generates a random quadratic residue Zp subgroup, that has the specified
  115. * bit length for its modulus <code>p</code> and the specified certainty
  116. * of having its modulus and the order <code>q</code> being prime.
  117. * <p>
  118. * This method generates a Zp subgroup that satisfies the condition:
  119. * <p>
  120. * <code>p =
  121. * (q * 2) + 1</code>
  122. * <p>
  123. * <b>Note:</b> The minimum bit length of the modulus <code>p</code> that
  124. * is permitted by this method is 2. If a bit length less than 2 is
  125. * requested, then an Error will be thrown.
  126. *
  127. * @function nextQuadraticResidueGroup
  128. * @memberof MathematicalRandomGenerator
  129. * @param {number}
  130. * pBitLength The modulus bit length of the Zp subgroup to
  131. * generate.
  132. * @param {number}
  133. * certainty The level of certainty that the order <code>q</code>
  134. * of the generated group is prime.
  135. * @param {Object}
  136. * [options] An object containing optional arguments.
  137. * @param {SecureRandomGenerator}
  138. * [options.secureRandomGenerator=Internal generator used] The
  139. * secure random generator to use.
  140. * @returns {ZpSubgroup} The generated quadratic residue group.
  141. * @throws {Error}
  142. * If the input validation fails.
  143. */
  144. this.nextQuadraticResidueGroup = function(pBitLength, certainty, options) {
  145. checkQrGroupGenerationData(pBitLength, certainty);
  146. options = options || {};
  147. var randomGenerator = options.secureRandomGenerator || randomGenerator_;
  148. validator.checkIsObjectWithProperties(
  149. randomGenerator,
  150. 'Random bytes generator for random quadratic residue Zp subgroup generation');
  151. var p, q;
  152. var randomGroupFound = false;
  153. var primeOptions = {prng: randomGenerator};
  154. var callback = function(err, num) {
  155. if (err) {
  156. throw new Error('Error while generating prime number; ' + err);
  157. }
  158. p = num;
  159. q = num.subtract(BigInteger.ONE).divide(new BigInteger('2'));
  160. };
  161. while (!randomGroupFound) {
  162. forge.prime.generateProbablePrime(pBitLength, primeOptions, callback);
  163. if (q.isProbablePrime(certainty)) {
  164. randomGroupFound = true;
  165. }
  166. }
  167. var g = mathGroupHandler_.findMinGenerator(p, q);
  168. return new ZpSubgroup(p, q, g);
  169. };
  170. function checkQrGroupGenerationData(pBitLength, certainty) {
  171. validator.checkIsPositiveNumber(pBitLength);
  172. validator.checkIsPositiveNumber(certainty);
  173. if (pBitLength < 2) {
  174. throw new Error(
  175. 'Bit length: ' + pBitLength +
  176. ' of modulus p provided as input for generating quadratic residue group is less than minimum required value of 2.');
  177. }
  178. if (certainty < constants.MINIMUM_PRIME_CERTAINTY_LEVEL) {
  179. throw new Error(
  180. 'Certainty level: ' + certainty +
  181. ' provided as input for generating quadratic residue group is less than minimum required value of ' +
  182. constants.MINIMUM_PRIME_CERTAINTY_LEVEL);
  183. }
  184. }
  185. }