group-handler.js 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310
  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 ZpGroupElement = require('./zp-group-element');
  12. var Exponent = require('./exponent');
  13. var validator = require('./input-validator');
  14. var forge = require('node-forge');
  15. var BigInteger = forge.jsbn.BigInteger;
  16. module.exports = MathematicalGroupHandler;
  17. /**
  18. * @class MathematicalGroupHandler
  19. * @classdesc The mathematical group handler API. To instantiate this object,
  20. * use the method {@link MathematicalService.newGroupHandler}.
  21. * @hideconstructor
  22. */
  23. function MathematicalGroupHandler() {}
  24. MathematicalGroupHandler.prototype = {
  25. /**
  26. * Exponentiates an array of Zp group elements with the exponent provided as
  27. * input.
  28. * <p>
  29. * The array of Zp group elements must only contain members of the Zp
  30. * subgroup provided as input. Otherwise, an error will be thrown.
  31. *
  32. * @function exponentiateElements
  33. * @memberof MathematicalGroupHandler
  34. * @param {ZpSubgroup}
  35. * group The Zp subgroup to which the elements must belong.
  36. * @param {ZpGroupElement[]}
  37. * elements The array of Zp group elements to exponentiate.
  38. * @param {Exponent}
  39. * exponent The exponent to use for the exponentiation
  40. * @param {boolean}
  41. * validate If set to true, then the elements are validated
  42. * @return {ZpGroupElement[]} The array of exponentiated group elements.
  43. * @throws {Error}
  44. * If the input data or group membership validation fails.
  45. */
  46. exponentiateElements: function(group, elements, exponent, validate) {
  47. validator.checkIsInstanceOf(
  48. group, ZpSubgroup, 'ZpSubgroup',
  49. 'Zp subgroup of elements to exponentiate', group);
  50. checkZpGroupElements(elements, 'Zp group elements to exponentiate', group);
  51. checkExponent(
  52. exponent, 'Exponent to use for exponentiating Zp group elements',
  53. group.q);
  54. if (typeof validate !== 'undefined') {
  55. validator.checkIsDefinedAndNotNull(
  56. validate, 'Zp group element exponentiation \"validate\" flag');
  57. validator.checkIsType(
  58. validate, 'boolean',
  59. 'Zp group element exponentiation \"validate\" flag');
  60. }
  61. if (validate) {
  62. for (var i = 0; i < elements.length; i++) {
  63. if (!group.isGroupMember(elements[i])) {
  64. throw new Error(
  65. 'Found Zp group element with value: ' + elements[i].value +
  66. ' that does not belong to Zp subgroup provided as input: p = ' +
  67. group.p + ' ; q = ' + group.q);
  68. }
  69. }
  70. }
  71. var exponentiatedElements = [];
  72. for (var j = 0; j < elements.length; j++) {
  73. exponentiatedElements.push(elements[j].exponentiate(exponent));
  74. }
  75. return exponentiatedElements;
  76. },
  77. /**
  78. * Divides the elements of one array of Zp group elements by the
  79. * corresponding members of another array of Zp group elements and creates a
  80. * new array of Zp group elements from the results of this operation.
  81. * <p>
  82. * The two arrays must only contain elements that belong to the Zp subgroup
  83. * group that this divider operates on. If either array contains any element
  84. * that is does not belong to this Zp subgroup, then an Error will be
  85. * thrown.
  86. *
  87. * @function divideElements
  88. * @memberof MathematicalGroupHandler
  89. * @param {ZpGroupElement[]}
  90. * dividendElements The array of Zp group elements to act as the
  91. * <code>dividend</code>.
  92. * @param {ZpGroupElement[]}
  93. * divisorElements The array Zp group elements to act as the
  94. * <code>divisor</code>.
  95. * @returns {ZpGroupElement[]} The array of <code>quotient</code> Zp group
  96. * elements resulting from this operation.
  97. * @throws {Error}
  98. * If the input or group membership validation fails.
  99. */
  100. divideElements: function(dividendElements, divisorElements) {
  101. checkDivisionData(dividendElements, divisorElements);
  102. var quotientArray = [];
  103. var quotient;
  104. for (var i = 0; i < dividendElements.length; i++) {
  105. quotient = dividendElements[i].multiply(divisorElements[i].invert());
  106. quotientArray.push(quotient);
  107. }
  108. return quotientArray;
  109. },
  110. /**
  111. * Iterates through an array of Zp group elements, checking if each element
  112. * is a member of the Zp subgroup provided as input.
  113. * <p>
  114. * If any element is found that is not a member of the Zp subgroup, then an
  115. * Error will be thrown.
  116. *
  117. * @function checkGroupMembership
  118. * @memberof MathematicalGroupHandler
  119. * @param {ZpSubgroup}
  120. * group The Zp subgroup to which the Zp group elements provided
  121. * as input must belong.
  122. * @param {ZpGroupElement[]}
  123. * elements The array of Zp group elements to check for group
  124. * membership.
  125. * @throws {Error}
  126. * If the input validation fails or any Zp group element in the
  127. * array fails the group membership check.
  128. */
  129. checkGroupMembership: function(group, elements) {
  130. validator.checkIsInstanceOf(
  131. group, ZpSubgroup, 'ZpSubgroup',
  132. 'Zp subgroup for group membership check');
  133. checkZpGroupElements(
  134. elements, 'Zp group elements for group membership check');
  135. for (var i = 0; i < elements.length; i++) {
  136. if (!group.isGroupMember(elements[i])) {
  137. throw new Error(
  138. 'Zp group element with value: ' + elements[i].value +
  139. ' is not a member of the Zp subgroup with modulus p: ' + group.p +
  140. ' and order q: ' + group.q);
  141. }
  142. }
  143. },
  144. /**
  145. * Iterates through an array of Zp group element values, checking if each
  146. * value is a member of the Zp subgroup provided as input. If a given value
  147. * is a member of the subgroup, it is encapsulated in a ZpGroupElement
  148. * object and added to an output array. The method stops iterating once it
  149. * has found the number of Zp subgroup members provided as input. At that
  150. * point, the output array containing all of the members found is returned.
  151. * <p>
  152. * If the required number of Zp subgroup members are not found then an Error
  153. * will be thrown.
  154. *
  155. * @function extractGroupMembers
  156. * @memberof MathematicalGroupHandler
  157. * @param {ZpSubgroup}
  158. * group The Zp subgroup to which the output Zp group elements
  159. * must belong.
  160. * @param {forge.jsbn.BigInteger[]}
  161. * values The array of Zp group element values from which to
  162. * obtain the members.
  163. * @param {number}
  164. * numMembersRequired The required number of Zp subgroup members
  165. * to be returned.
  166. * @returns {ZpGroupElement[]} The array of requested Zp subgroup members.
  167. * @throws {Error}
  168. * If the input validation fails or the required number of Zp
  169. * subgroup members was not found.
  170. */
  171. extractGroupMembers: function(group, values, numMembersRequired) {
  172. checkExtractionData(values, group, numMembersRequired);
  173. var outputArray = [];
  174. var membersFound = 0;
  175. var candidate;
  176. for (var i = 0; i < values.length; i++) {
  177. candidate = new ZpGroupElement(group.p, group.q, values[i]);
  178. if (group.isGroupMember(candidate)) {
  179. outputArray.push(candidate);
  180. membersFound++;
  181. }
  182. if (membersFound === numMembersRequired) {
  183. return outputArray;
  184. }
  185. }
  186. if (membersFound !== numMembersRequired) {
  187. throw new Error(
  188. 'Did not find the required number of group members in the given list. The required number of was ' +
  189. numMembersRequired + ', number of members found was ' +
  190. membersFound);
  191. }
  192. },
  193. /**
  194. * Finds the smallest generator for a given Zp subgroup.
  195. * <p>
  196. * This method starts with a candidate generator element of value 2 and
  197. * checks if this element is a group member. If that element is a group
  198. * member then it is returned. Otherwise, the candidate element value is
  199. * incremented by 1 the check is performed again. This process continues
  200. * until a generator is found or the candidate element value equals the p
  201. * parameter of the Zp subgroup, in which case an Error is thrown.
  202. *
  203. * @function findMinGenerator
  204. * @memberof MathematicalGroupHandler
  205. * @param {forge.jsbn.BigInteger}
  206. * p The modulus of the Zp subgroup.
  207. * @param {forge.jsbn.BigInteger}
  208. * q The order of the Zp subgroup.
  209. * @returns {forge.jsbn.BigInteger} The smallest generator.
  210. * @throws {Error}
  211. * If the input data validation failes or a generator cannot be
  212. * found.
  213. */
  214. findMinGenerator: function(p, q) {
  215. validator.checkZpSubgroupModulus(
  216. p, 'Modulus p of Zp subgroup for which to find smallest generator');
  217. validator.checkZpSubgroupOrder(
  218. q, 'Order q of Zp subgroup for which to find smallest generator', p);
  219. var g = new BigInteger('2');
  220. var generatorFound = false;
  221. while ((!generatorFound) && (g.compareTo(p) < 0)) {
  222. if (g.modPow(q, p).equals(BigInteger.ONE)) {
  223. generatorFound = true;
  224. } else {
  225. g = g.add(BigInteger.ONE);
  226. }
  227. }
  228. if (!generatorFound) {
  229. throw new Error(
  230. 'Failed to find a generator for modulus p: ' + p +
  231. ' and order q: ' + q);
  232. }
  233. return g;
  234. }
  235. };
  236. function checkDivisionData(dividendElements, divisorElements) {
  237. checkZpGroupElements(
  238. dividendElements,
  239. 'Dividend Zp group elements to use for element array division operation');
  240. checkZpGroupElements(
  241. divisorElements,
  242. 'Divisor Zp group elements to use for element array division operation');
  243. var numDividendElements = dividendElements.length;
  244. var numDivisorElements = divisorElements.length;
  245. if (numDividendElements !== numDivisorElements) {
  246. throw new Error(
  247. 'Expected number of divisor elements to equal number of dividend elements: ' +
  248. numDividendElements + ' ; Found: ' + numDivisorElements);
  249. }
  250. }
  251. function checkExtractionData(values, group, numMembersRequired) {
  252. validator.checkIsNonEmptyArray(
  253. values, 'Zp group element values from which to extract group members');
  254. validator.checkIsInstanceOf(
  255. group, ZpSubgroup, 'ZpSubgroup',
  256. 'Zp subgroup to which extracted members are to belong');
  257. validator.checkIsPositiveNumber(
  258. numMembersRequired,
  259. 'Number of group members required by extraction process');
  260. if (numMembersRequired > values.length) {
  261. throw new Error(
  262. 'Required number of group members provided as input: ' +
  263. numMembersRequired +
  264. ' is greater then the number of element values provided as input: ' +
  265. values.length);
  266. }
  267. }
  268. function checkZpGroupElements(elements, label, group) {
  269. validator.checkZpGroupElements(elements, label, group);
  270. for (var i = 0; i < elements.length; i++) {
  271. validator.checkIsInstanceOf(
  272. elements[i], ZpGroupElement, 'ZpGroupElement',
  273. 'element ' + i + ' of ' + label);
  274. }
  275. }
  276. function checkExponent(exponent, label, q) {
  277. validator.checkExponent(exponent, label, q);
  278. validator.checkIsInstanceOf(exponent, Exponent, 'Exponent', label);
  279. }