index.spec.js 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520
  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 mathematical = require('../lib/index');
  11. var CommonTestData = require('./data/common-data');
  12. var secureRandom = require('scytl-securerandom');
  13. var forge = require('node-forge');
  14. var BigInteger = forge.jsbn.BigInteger;
  15. describe('The mathematical module should be able to ...', function() {
  16. var TEST_SEED = new Uint8Array([18, 58, 188]);
  17. var mathService_;
  18. var mathArrayCompressor_;
  19. var mathRandomGenerator_;
  20. var mathGroupHandler_;
  21. var g_;
  22. var p_;
  23. var q_;
  24. var group_;
  25. var anotherGroup_;
  26. var qrGroup_;
  27. var elementValue_;
  28. var element_;
  29. var exponentValue_;
  30. var exponent_;
  31. var element1Value_;
  32. var element2Value_;
  33. var element3Value_;
  34. var elements_;
  35. var exponents_;
  36. var qrGroupLarge_;
  37. var exponent1Large_;
  38. var exponent2Large_;
  39. var multiGroupElementValueArray_;
  40. var multiGroupElementValues_;
  41. var multiGroupElements_;
  42. var minCertaintyLevel_;
  43. beforeAll(function() {
  44. mathService_ = mathematical.newService();
  45. mathArrayCompressor_ = mathService_.newArrayCompressor();
  46. mathRandomGenerator_ = mathService_.newRandomGenerator();
  47. mathGroupHandler_ = mathService_.newGroupHandler();
  48. var testData = new CommonTestData();
  49. p_ = testData.getP();
  50. q_ = testData.getQ();
  51. g_ = testData.getG();
  52. group_ = testData.getGroup();
  53. anotherGroup_ = testData.getAnotherGroup();
  54. qrGroup_ = testData.getQuadraticResidueGroup();
  55. elementValue_ = testData.getElementValue();
  56. element_ = testData.getElement();
  57. exponentValue_ = testData.getExponentValue();
  58. exponent_ = testData.getExponent();
  59. element1Value_ = testData.getElement1Value();
  60. element2Value_ = testData.getElement2Value();
  61. element3Value_ = testData.getElement3Value();
  62. elements_ = testData.getElements();
  63. exponents_ = testData.getExponents();
  64. qrGroupLarge_ = testData.getLargeQuadraticResidueGroup();
  65. exponent1Large_ = testData.getExponent1Large();
  66. exponent2Large_ = testData.getExponent2Large();
  67. multiGroupElementValueArray_ = testData.getMultiGroupElementValueArray();
  68. multiGroupElementValues_ = testData.multiGroupElementValues();
  69. multiGroupElements_ = testData.getMultiGroupElements();
  70. minCertaintyLevel_ = testData.getMinimumCertaintyLevel();
  71. });
  72. describe('create a mathematical service that should be able to ..', function() {
  73. it('be created from a secure random service object provided as input',
  74. function() {
  75. var mathService = mathematical.newService(
  76. {secureRandomService: secureRandom.newService()});
  77. var mathRandomGenerator = mathService.newRandomGenerator();
  78. var randomExponent = mathRandomGenerator.nextExponent(qrGroup_);
  79. expect(randomExponent).toBeDefined();
  80. });
  81. describe(
  82. 'create a new ZpSubgroup object that should be able to ..', function() {
  83. it('be defined', function() {
  84. expect(group_).toBeDefined();
  85. expect(group_.identity).toBeDefined();
  86. });
  87. it('check group membership', function() {
  88. var element =
  89. mathService_.newZpGroupElement(p_, q_, BigInteger.ONE);
  90. expect(group_.isGroupMember(element)).toBeTruthy();
  91. // Check membership of element with wrong q.
  92. var q2 = new BigInteger('19');
  93. var p2 = new BigInteger('37');
  94. var group2 = mathService_.newZpSubgroup(p2, q2, g_);
  95. var element2 = mathService_.newZpGroupElement(
  96. group2.p, group2.q, BigInteger.ONE);
  97. expect(!group_.isGroupMember(element2)).toBeTruthy();
  98. // Check membership of non-member element.
  99. element =
  100. mathService_.newZpGroupElement(p_, q_, new BigInteger('5'));
  101. expect(!group_.isGroupMember(element)).toBeTruthy();
  102. });
  103. it('be compared with another ZpSubgroup object', function() {
  104. var group2 = mathService_.newZpSubgroup(p_, q_, g_);
  105. var q2 = new BigInteger('19');
  106. var p2 = new BigInteger('37');
  107. var group3 = mathService_.newZpSubgroup(p2, q2, g_);
  108. expect(group_.equals(group2)).toBeTruthy();
  109. expect(!group_.equals(group3)).toBeTruthy();
  110. });
  111. it('be serialized and deserialized', function() {
  112. var groupJson = group_.toJson();
  113. var groupFromJson = mathService_.newZpSubgroup(groupJson);
  114. expect(groupFromJson).toBeDefined();
  115. expect(groupFromJson.equals(group_)).toBeTruthy();
  116. });
  117. });
  118. describe(
  119. 'create a new ZpGroupElement object that should be able to ..',
  120. function() {
  121. it('be defined', function() {
  122. expect(element_).toBeDefined();
  123. expect(element_.value.equals(elementValue_)).toBeTruthy();
  124. });
  125. it('be multiplied with another ZpGroupElement object', function() {
  126. var value = new BigInteger('2');
  127. var element2 = mathService_.newZpGroupElement(p_, q_, value);
  128. var groupResult = element_.multiply(element2);
  129. expect(groupResult).toBeDefined();
  130. expect(groupResult.value.equals(new BigInteger('6'))).toBeTruthy();
  131. });
  132. it('be exponentiated with an Exponent object', function() {
  133. var value = new BigInteger('2');
  134. var exponent = mathService_.newExponent(q_, value);
  135. var groupResult = element_.exponentiate(exponent);
  136. expect(groupResult).toBeDefined();
  137. expect(groupResult.value.equals(new BigInteger('9'))).toBeTruthy();
  138. });
  139. it('be inverted', function() {
  140. var groupResult = element_.invert();
  141. expect(groupResult).toBeDefined();
  142. expect(groupResult.value.equals(new BigInteger('8'))).toBeTruthy();
  143. });
  144. it('be serialized and deserialized', function() {
  145. var elementJson = element_.toJson();
  146. var elementFromJson = mathService_.newZpGroupElement(elementJson);
  147. expect(elementFromJson).toBeDefined();
  148. expect(elementFromJson.equals(element_)).toBeTruthy();
  149. });
  150. });
  151. describe(
  152. 'create a new Exponent object that should be able to ..', function() {
  153. it('be defined', function() {
  154. expect(exponent_).toBeDefined();
  155. expect(exponent_.value.equals(exponentValue_)).toBeTruthy();
  156. });
  157. it('be added to another Exponent object', function() {
  158. var value = new BigInteger('3');
  159. var exponent2 = mathService_.newExponent(q_, value);
  160. var exponentResult = exponent_.add(exponent2);
  161. expect(exponentResult).toBeDefined();
  162. expect(exponentResult.value.equals(new BigInteger('5')))
  163. .toBeTruthy();
  164. });
  165. it('subtract another Exponent object from itself', function() {
  166. var value = new BigInteger('5');
  167. var exponent2 = mathService_.newExponent(q_, value);
  168. var exponentResult = exponent2.subtract(exponent_);
  169. expect(exponentResult).toBeDefined();
  170. expect(exponentResult.value.equals(new BigInteger('3')))
  171. .toBeTruthy();
  172. });
  173. it('be multiplied with another Exponent object', function() {
  174. var value = new BigInteger('3');
  175. var exponent2 = mathService_.newExponent(q_, value);
  176. var exponentResult = exponent_.multiply(exponent2);
  177. expect(exponentResult).toBeDefined();
  178. expect(exponentResult.value.toString())
  179. .toEqual('' + exponent_.value * exponent2.value % q_);
  180. });
  181. it('be multiplied with Exponent objects encapsulating large values',
  182. function() {
  183. var exponentResult = exponent1Large_.multiply(exponent2Large_);
  184. expect(exponentResult).toBeDefined();
  185. });
  186. it('be negated', function() {
  187. var exponentResult = exponent_.negate();
  188. expect(exponentResult).toBeDefined();
  189. expect(exponentResult.value.equals(new BigInteger('9')))
  190. .toBeTruthy();
  191. });
  192. it('be serialized and deserialized', function() {
  193. var exponentJson = exponent_.toJson();
  194. var exponentFromJson = mathService_.newExponent(exponentJson);
  195. expect(exponentFromJson).toBeDefined();
  196. expect(exponentFromJson.equals(exponent_)).toBeTruthy();
  197. });
  198. });
  199. it('create a new quadratic residue Zp subgroup', function() {
  200. var group = mathService_.newQuadraticResidueGroup(p_, g_);
  201. expect(group).toBeDefined();
  202. });
  203. describe(
  204. 'create a new MathematicalArrayCompressor object that should be able to ..',
  205. function() {
  206. it('compress Zp group elements', function() {
  207. var compressedElement =
  208. mathArrayCompressor_.compressZpGroupElements(elements_);
  209. expect(compressedElement).toBeDefined();
  210. expect(compressedElement.value.equals(new BigInteger('8')))
  211. .toBeTruthy();
  212. compressedElement = mathArrayCompressor_.compressZpGroupElements(
  213. multiGroupElements_, group_);
  214. expect(compressedElement).toBeDefined();
  215. expect(compressedElement.value.equals(new BigInteger('6')))
  216. .toBeTruthy();
  217. });
  218. it('compress a desired number of trailing Zp group elements',
  219. function() {
  220. var requiredLength = 4;
  221. var compressedArray =
  222. mathArrayCompressor_.compressTrailingZpGroupElements(
  223. multiGroupElements_, requiredLength);
  224. expect(compressedArray.length).toBe(requiredLength);
  225. var expectedCompressedArray = [];
  226. var expectedCompressedArrayValues = [3, 4, 5, 7];
  227. for (var i = 0; i < expectedCompressedArrayValues.length; i++) {
  228. var value =
  229. new BigInteger('' + expectedCompressedArrayValues[i]);
  230. var element = mathService_.newZpGroupElement(p_, q_, value);
  231. expectedCompressedArray.push(element);
  232. }
  233. var equals = true;
  234. for (var j = 0; j < compressedArray.length; j++) {
  235. if (!compressedArray[j].equals(expectedCompressedArray[j])) {
  236. equals = false;
  237. }
  238. }
  239. expect(equals).toBeTruthy();
  240. });
  241. it('compress exponents', function() {
  242. var compressedExponent =
  243. mathArrayCompressor_.compressExponents(exponents_);
  244. expect(compressedExponent).toBeDefined();
  245. expect(compressedExponent.value.equals(new BigInteger('7')))
  246. .toBeTruthy();
  247. });
  248. it('compress a desired number of trailing exponents', function() {
  249. var requiredLength = 2;
  250. var compressedArray =
  251. mathArrayCompressor_.compressTrailingExponents(
  252. exponents_, requiredLength);
  253. expect(compressedArray.length).toBe(requiredLength);
  254. var value;
  255. var exponent;
  256. var expectedCompressedArrayValues = [2, 5];
  257. var expectedCompressedArray = [];
  258. for (var i = 0; i < expectedCompressedArrayValues.length; i++) {
  259. value = new BigInteger('' + expectedCompressedArrayValues[i]);
  260. exponent = mathService_.newExponent(q_, value);
  261. expectedCompressedArray.push(exponent);
  262. }
  263. var equals = true;
  264. for (var j = 0; j < compressedArray.length; j++) {
  265. if (!compressedArray[j].equals(expectedCompressedArray[j])) {
  266. equals = false;
  267. }
  268. }
  269. expect(equals).toBeTruthy();
  270. });
  271. });
  272. describe(
  273. 'create a new MathematicalRandomGenerator object that should be able to ..',
  274. function() {
  275. it('generate a random Exponent', function() {
  276. var randomExponent = mathRandomGenerator_.nextExponent(qrGroup_);
  277. expect(randomExponent).toBeDefined();
  278. });
  279. it('generate a short random Exponent', function() {
  280. var randomExponent = mathRandomGenerator_.nextExponent(
  281. qrGroupLarge_, {useShortExponent: true});
  282. expect(randomExponent).toBeDefined();
  283. expect(function() {
  284. mathRandomGenerator_.nextExponent(
  285. qrGroup_, {useShortExponent: true});
  286. }).toThrow();
  287. });
  288. it('generate a random Exponent, using chosen source of randomness',
  289. function() {
  290. var secureRandomService =
  291. secureRandom.newService({prngSeed: TEST_SEED});
  292. var randomGenerator = secureRandomService.newRandomGenerator();
  293. var randomExponent = mathRandomGenerator_.nextExponent(
  294. qrGroup_, {secureRandomGenerator: randomGenerator});
  295. expect(randomExponent.value.toString()).toBe('9');
  296. });
  297. it('generate a random Zp group element', function() {
  298. for (var i = 0; i < 100; i++) {
  299. var element = mathRandomGenerator_.nextZpGroupElement(qrGroup_);
  300. expect(element).toBeDefined();
  301. expect(qrGroup_.isGroupMember(element)).toBeTruthy();
  302. }
  303. });
  304. it('generate a random Zp group element, using a short exponent',
  305. function() {
  306. var element = mathRandomGenerator_.nextZpGroupElement(
  307. qrGroupLarge_, {useShortExponent: true});
  308. expect(element).toBeDefined();
  309. expect(qrGroupLarge_.isGroupMember(element)).toBeTruthy();
  310. });
  311. it('generate a random Zp group element, using a chosen source of randomness',
  312. function() {
  313. var secureRandomService =
  314. secureRandom.newService({prngSeed: TEST_SEED});
  315. var randomGenerator = secureRandomService.newRandomGenerator();
  316. var randomElement = mathRandomGenerator_.nextZpGroupElement(
  317. qrGroup_, {secureRandomGenerator: randomGenerator});
  318. expect(randomElement.value.toString()).toBe('6');
  319. });
  320. it('generate a random quadratic residue Zp subgroup', function() {
  321. var bitLengthOfP = 16;
  322. var certainty = minCertaintyLevel_;
  323. var group = mathRandomGenerator_.nextQuadraticResidueGroup(
  324. bitLengthOfP, certainty);
  325. expect(group).toBeDefined();
  326. });
  327. it('generate a random quadratic residue Zp subgroup, using a chosen source of randomness',
  328. function() {
  329. var bitLengthOfP = 16;
  330. var certainty = minCertaintyLevel_;
  331. var secureRandomService =
  332. secureRandom.newService({prngSeed: TEST_SEED});
  333. var randomGenerator = secureRandomService.newRandomGenerator();
  334. var group = mathRandomGenerator_.nextQuadraticResidueGroup(
  335. bitLengthOfP, certainty,
  336. {secureRandomGenerator: randomGenerator});
  337. expect(group.p.toString()).toBe('41843');
  338. expect(group.q.toString()).toBe('20921');
  339. expect(group.generator.value.toString()).toBe('3');
  340. });
  341. });
  342. describe(
  343. 'create a new MathematicalGroupHandler object that should be able to ..',
  344. function() {
  345. it('exponentiate an array of Zp group elements', function() {
  346. var exponentiatedElements = mathGroupHandler_.exponentiateElements(
  347. group_, elements_, exponent_);
  348. expect(exponentiatedElements).toBeDefined();
  349. expect(exponentiatedElements.length).toEqual(elements_.length);
  350. expect(exponentiatedElements[0].value.toString())
  351. .toEqual('' + (Math.pow(element1Value_, exponentValue_) % p_));
  352. expect(exponentiatedElements[1].value.toString())
  353. .toEqual('' + (Math.pow(element2Value_, exponentValue_) % p_));
  354. expect(exponentiatedElements[2].value.toString())
  355. .toEqual('' + (Math.pow(element3Value_, exponentValue_) % p_));
  356. expect(exponentiatedElements[0].p).toEqual(p_);
  357. expect(exponentiatedElements[1].p).toEqual(p_);
  358. expect(exponentiatedElements[2].p).toEqual(p_);
  359. expect(exponentiatedElements[0].q).toEqual(q_);
  360. expect(exponentiatedElements[1].q).toEqual(q_);
  361. expect(exponentiatedElements[2].q).toEqual(q_);
  362. });
  363. it('honor the validation flag when exponentiating an array of Zp group elements',
  364. function() {
  365. // Confirm that no error is thrown when exponentiating some
  366. // elements that do not belong to group but validation flag is
  367. // not set.
  368. mathGroupHandler_.exponentiateElements(
  369. group_, multiGroupElements_, exponent_);
  370. // Confirm that no error is thrown when exponentiating some
  371. // elements that do not belong to group but validation flag is
  372. // set to false.
  373. mathGroupHandler_.exponentiateElements(
  374. group_, multiGroupElements_, exponent_, false);
  375. // Confirm that error is thrown when exponentiating some elements
  376. // that do not belong to group and validation flag is set to
  377. // true.
  378. expect(function() {
  379. mathGroupHandler_.exponentiateElements(
  380. group_, multiGroupElements_, exponent_, true);
  381. }).toThrow();
  382. });
  383. it('divide two Zp group element arrays', function() {
  384. var value;
  385. var element;
  386. var elements = [];
  387. value = new BigInteger('1');
  388. element = mathService_.newZpGroupElement(p_, q_, value);
  389. elements.push(element);
  390. value = new BigInteger('2');
  391. element = mathService_.newZpGroupElement(p_, q_, value);
  392. elements.push(element);
  393. value = new BigInteger('16');
  394. element = mathService_.newZpGroupElement(p_, q_, value);
  395. elements.push(element);
  396. var dividedElements =
  397. mathGroupHandler_.divideElements(elements_, elements, group_);
  398. expect(dividedElements).toBeDefined();
  399. });
  400. it('check the Zp subgroup membership of an array of Zp group elements, for which all elements are members',
  401. function() {
  402. mathGroupHandler_.checkGroupMembership(group_, elements_);
  403. });
  404. it('check the Zp subgroup membership of an array of Zp group elements, for which not all elements are members',
  405. function() {
  406. expect(function() {
  407. mathGroupHandler_.checkGroupMembership(
  408. anotherGroup_, elements_);
  409. }).toThrow();
  410. });
  411. it('extract a specified number of Zp subgroup members from an array of Zp group element values',
  412. function() {
  413. var numMembersRequired = multiGroupElementValueArray_.length - 2;
  414. var extractedElements = mathGroupHandler_.extractGroupMembers(
  415. group_, multiGroupElementValues_, numMembersRequired);
  416. expect(extractedElements).toBeDefined();
  417. expect(extractedElements.length).toBe(numMembersRequired);
  418. });
  419. });
  420. });
  421. });