common-data.js 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401
  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 elGamal = require('scytl-elgamal');
  11. var mathematical = require('scytl-mathematical');
  12. var forge = require('node-forge');
  13. module.exports = CommonTestData;
  14. var BigInteger = forge.jsbn.BigInteger;
  15. /**
  16. * Provides the common data and functions needed by the zero-knowledge proof of
  17. * knowledge unit tests.
  18. */
  19. function CommonTestData() {
  20. var mathService = mathematical.newService();
  21. var mathRandomGenerator_ = mathService.newRandomGenerator();
  22. var elGamalService_ = elGamal.newService();
  23. var p_ = new BigInteger(
  24. '25701322016688441576103032148674110774925156427397637132202577741938936247112125492211659378990027134829873026348759004510642939209382852797923423233606398455768339503774439196473285206499419017249519687083918862292745452369770073017370862703937184066962152692474974647384317528679859283948201449898123774491462507974828236623365121967170401847974506359775053259024902177376974036791676038887180065668218851769610708183278395407393103098286493672450097566567641277262751905925272593655979627326843104589717100845609213331825322091528671293329804211235906640910489075537455976735341285644494144220105240375300711488393');
  25. var q_ = new BigInteger(
  26. '81259987775362040571620137377019110900790585487969528507141757273696249070213');
  27. var g_ = new BigInteger(
  28. '21303916314604998551484796420422871007468543247831789236879215369694842734099405650535148287249791144057375987697205687518340016316179892851284240278138045703633698036256611527988640313051528625117090689542380890153876064768602704006774164341226969138952495075758675629665109761968589385514561688161321002676900768077022957299407868881468752268501397255241070908793893954188678747644443826465068701078202311876709764302561277744548084228639372458598925393551439452959527949768006498598646518365505226629313181567048632516237514971091380204424481498506499338185144271546651990709723565928420753129878206710329253950578');
  29. var group_ = mathService.newZpSubgroup(p_, q_, g_);
  30. var anotherP_ = new BigInteger(
  31. '22115396014581083143553195792384915983375949993753365299824374182778648887213105675373952839695834312125954513956465041609718392131788741228259266178434294275575978809365653903991346366383637500069010795276889266879661859362340655085050484891149389971190945080643692669920059928787982790808824970597361825060408436004650739931286605415552480363242364319544423959620330010413847743583301091182870021747196927889763205955078275353307312408480155002017730305672359814713050632922694161739281353676187308501682728826507718002850698488786266115311952718697872338756199429262811547458969260835283688979875294699655014592833');
  32. var anotherQ_ = new BigInteger(
  33. '79783631514788897688995869254536231266441581267248557197866166084121363399063');
  34. var anotherG_ = new BigInteger(
  35. '9484337033848536557358945372517536146444081505783459082983213315915020922388822299017798461933010391712259501201285084235930755858547311934865298396110947362913733900057881561201738951725697128822802249693116611294569213895789823297341865759919045291915705783128173481781221176839434866976235031358969583527093743179257827355453820268832913547364509208164670680381449515691300440305333919098105147193087681183020489724214850151272955879869448467832934822639783688344322183540621808345771717172404141548242866493539424279296365911355186761897533654055060787119955689115570505208857288933136456026541073605147828202749');
  36. var anotherGroup_ =
  37. mathService.newZpSubgroup(anotherP_, anotherQ_, anotherG_);
  38. /**
  39. * @function getP
  40. * @returns {forge.jsbn.BigInteger} The modulus of a Zp subgroup.
  41. */
  42. this.getP = function() {
  43. return p_;
  44. };
  45. /**
  46. * @function getQ
  47. * @returns {forge.jsbn.BigInteger} The order of a Zp subgroup.
  48. */
  49. this.getQ = function() {
  50. return q_;
  51. };
  52. /**
  53. * @function getG
  54. * @returns {forge.jsbn.BigInteger} The generator of a Zp subgroup.
  55. */
  56. this.getG = function() {
  57. return g_;
  58. };
  59. /**
  60. * @function getGroup
  61. * @returns {ZpSubgroup} A Zp subgroup.
  62. */
  63. this.getGroup = function() {
  64. return group_;
  65. };
  66. /**
  67. * @function getAnotherP
  68. * @returns {forge.jsbn.BigInteger} The modulus of another Zp subgroup.
  69. */
  70. this.getAnotherP = function() {
  71. return anotherP_;
  72. };
  73. /**
  74. * @function getAnotherQ
  75. * @returns {forge.jsbn.BigInteger} The order of another Zp subgroup.
  76. */
  77. this.getAnotherQ = function() {
  78. return anotherQ_;
  79. };
  80. /**
  81. * @function getAnotherG
  82. * @returns {forge.jsbn.BigInteger} The generator of another Zp subgroup.
  83. */
  84. this.getAnotherG = function() {
  85. return anotherG_;
  86. };
  87. /**
  88. * @function getAnotherGroup
  89. * @returns {ZpSubgroup} Another Zp subgroup.
  90. */
  91. this.getAnotherGroup = function() {
  92. return anotherGroup_;
  93. };
  94. /**
  95. * Generates a random string.
  96. *
  97. * @function generateRandomString
  98. * @param {number}
  99. * length The number of characters that are to constitute the
  100. * string.
  101. * @returns {string} The random string.
  102. */
  103. this.generateRandomString = function(length) {
  104. var charset = 'abcdefghijklmnopqrstuvwxyz0123456789';
  105. var string = '';
  106. for (var i = 0; i < length; i++) {
  107. string += charset.charAt(Math.floor(Math.random() * charset.length));
  108. }
  109. return string;
  110. };
  111. /**
  112. * Generates a random integer whose value is within a specified range.
  113. *
  114. * @function generateRandomInteger
  115. * @param {number}
  116. * min The minimum value of the integer.
  117. * @param {number}
  118. * max The maximum value of the integer.
  119. * @returns {number} The random integer.
  120. */
  121. this.generateRandomInteger = function(min, max) {
  122. return Math.floor(Math.random() * (max - min + 1)) + min;
  123. };
  124. /**
  125. * Generates an ElGamal key pair.
  126. *
  127. * @function generateKeyPair
  128. * @param {ZpSubgroup}
  129. * group The Zp subgroup to which the public key elements belong
  130. * and to which the private key exponents are associated.
  131. * @param {number}
  132. * numElements The number of Zp group elements in the public key.
  133. * @returns {ElGamalKeyPair} The ElGamal key pair.
  134. */
  135. this.generateKeyPair = function(group, numElements) {
  136. var elements = [];
  137. var exponents = [];
  138. var exponent;
  139. var element;
  140. for (var i = 0; i < numElements; i++) {
  141. exponent = mathRandomGenerator_.nextExponent(group);
  142. exponents.push(exponent);
  143. element = group.generator.exponentiate(exponent);
  144. elements.push(element);
  145. }
  146. var publicKey = elGamalService_.newPublicKey(group, elements);
  147. var privateKey = elGamalService_.newPrivateKey(group, exponents);
  148. return elGamalService_.newKeyPair(publicKey, privateKey);
  149. };
  150. /**
  151. * Generates a random array of Zp group elements.
  152. *
  153. * @function generateRandomGroupElements
  154. * @param {ZpSubgroup}
  155. * group The Zp subgroup to which the Zp group elements belong.
  156. * @param {number}
  157. * numElements The number of Zp group elements to generate.
  158. * @returns {ZpGroupElement[]} The array of Zp group elements.
  159. */
  160. this.generateRandomGroupElements = function(group, numElements) {
  161. var elements = [];
  162. for (var i = 0; i < numElements; i++) {
  163. elements.push(mathRandomGenerator_.nextZpGroupElement(group));
  164. }
  165. return elements;
  166. };
  167. /**
  168. * Exponentiates an array of Zp group base elements with an exponent.
  169. *
  170. * @function exponentiateElements
  171. * @param {ZpGroupElement[]}
  172. * baseElements The Zp group base elements to exponentiate.
  173. * @param {Exponent}
  174. * exponent The exponent to use for the exponentiation.
  175. * @return {ZpGroupElement[]} The array of exponentiated Zp group base
  176. * elements.
  177. */
  178. this.exponentiateElements = function(baseElements, exponent) {
  179. var exponentiatedElements = [];
  180. for (var i = 0; i < baseElements.length; i++) {
  181. exponentiatedElements.push(baseElements[i].exponentiate(exponent));
  182. }
  183. return exponentiatedElements;
  184. };
  185. /**
  186. *
  187. * Generates an array of simple plaintext Zp group elements. By definition,
  188. * all of these elements will have the same value. The number of elements
  189. * requested must be an even number
  190. *
  191. * @function generateSimplePlaintext
  192. * @param {ZpSubgroup}
  193. * group The Zp subgroup to which the simple plaintext Zp group
  194. * elements belong.
  195. * @param {number}
  196. * numElements The number of simple plaintext Zp group elements
  197. * to generate.
  198. * @returns {ZpGroupElement[]} The array of simple plaintext Zp group
  199. * elements.
  200. * @throws {Error}
  201. * If the number of simple plaintext Zp group elements requested
  202. * was an odd number.
  203. */
  204. this.generateSimplePlaintext = function(group, numElements) {
  205. var simplePlaintext = [];
  206. if ((numElements % 2) !== 0) {
  207. throw new Error(
  208. 'Simple plaintext must be generated using an even number of elements; Found ' +
  209. numElements);
  210. }
  211. var element = mathRandomGenerator_.nextZpGroupElement(group);
  212. for (var i = 0; i < numElements; i++) {
  213. simplePlaintext.push(element);
  214. }
  215. return simplePlaintext;
  216. };
  217. /**
  218. * Generates an array of non-simple plaintext Zp group elements. By
  219. * definition, the array is non-simple because if it contains at least 2
  220. * elements whose values are different.
  221. *
  222. * @function generateNonSimplePlaintext
  223. * @param {ZpSubgroup}
  224. * group The Zp subgroup to which all of the generated Zp group
  225. * elements belong.
  226. * @param {number}
  227. * numElements The number of non-simple Zp group elements to
  228. * generate.
  229. * @returns {ZpGroupElement[]} The array of non-simple Zp group elements.
  230. */
  231. this.generateNonSimplePlaintext = function(group, numElements) {
  232. var nonSimplePlaintext = [];
  233. var element = mathRandomGenerator_.nextZpGroupElement(group);
  234. nonSimplePlaintext.push(element);
  235. for (var i = 1; i < numElements; i++) {
  236. do {
  237. element = mathRandomGenerator_.nextZpGroupElement(group);
  238. } while (element.value.equals(nonSimplePlaintext[i - 1].value));
  239. nonSimplePlaintext.push(element);
  240. }
  241. return nonSimplePlaintext;
  242. };
  243. /**
  244. * Retrieves an ElGamal public subkey from an existing ElGamal public key.
  245. *
  246. * @function getSubPublicKey
  247. * @param {ZpSubgroup}
  248. * group The Zp subgroup to which all Zp group elements of the
  249. * subkey belong.
  250. * @param {ElGamalPublicKey}
  251. * publicKey The ElGamal public from which to extract the subkey.
  252. * @param {number}
  253. * fromIndex The index (inclusive) of the array of Zp group
  254. * elements of the existing key that marks the beginning of the
  255. * subkey.
  256. * @param {number}
  257. * toIndex The index (exlusive) of the array of Zp group elements
  258. * of the existing key that marks the end of the subkey.
  259. * @returns {ElGamalPublic} The ElGamal public subkey.
  260. */
  261. this.getSubPublicKey = function(group, publicKey, fromIndex, toIndex) {
  262. var subElements = [];
  263. var elements = publicKey.elements;
  264. for (var i = fromIndex; i < toIndex; i++) {
  265. subElements.push(elements[i]);
  266. }
  267. return elGamalService_.newPublicKey(group, subElements);
  268. };
  269. /**
  270. * Retrieves an ElGamalEncryptedElements object from an existing
  271. * ElGamalEncryptedElements object that contains a subset of the phi
  272. * elements of the existing object.
  273. *
  274. * @function getSubEncryptedElements
  275. * @param {ElGamalEncryptedElements}
  276. * encryptedElements The ElGamalEncryptedElements object from
  277. * which to extract the new object.
  278. * @param {number}
  279. * fromIndex The index (inclusive) of the phi array of the
  280. * existing ElGamalEncryptedElements object that marks the
  281. * beginning of the new phi array.
  282. * @param {number}
  283. * toIndex The index (exclusive) of the phi array of the
  284. * ElGamalEncryptedElements object that marks the end of the
  285. * new phi array.
  286. * @returns {ElGamalEncryptedElements} The new ElGamalEncryptedElements
  287. * object that contains a subset of the phis.
  288. */
  289. this.getSubEncryptedElements = function(
  290. encryptedElements, fromIndex, toIndex) {
  291. var gamma = encryptedElements.gamma;
  292. var phis = encryptedElements.phis;
  293. var subPhis = [];
  294. for (var i = fromIndex; i < toIndex; i++) {
  295. subPhis.push(phis[i]);
  296. }
  297. return elGamalService_.newEncryptedElements(
  298. gamma, subPhis, encryptedElements.secret);
  299. };
  300. /**
  301. * Generates the ciphertext needed to generate a plaintext exponent equality
  302. * zero-knowledge proof of knowledge. The array of base elements provided as
  303. * input must have an odd number of elements.
  304. *
  305. * The procedure is the following:
  306. * <ol>
  307. * <li>Generate the plaintext to encrypt by exponentiating a subset of the
  308. * base elements with the ephermeral key</li>
  309. * <li>Construct the ElGamal public key from an equal number of remaining
  310. * base elements</li>
  311. * <li>Generate the gamma element of the ciphertext by exponentiating the
  312. * remaining base element with the ephemeral key</li>
  313. * <li>Generate the phi array of the ciphertext by multiplying each
  314. * plaintext element with its corresponding public key element, the latter
  315. * being exponentiated with the message key</li>
  316. * <li>The resulting ciphertext can be used in a zero knowledge proof of
  317. * knowledge to show that each plaintext element was generated from the same
  318. * ephemeral key and that each phi element was generated from the same
  319. * message key.</li>
  320. * </ol>
  321. *
  322. * @param {ZpGroupElement[]}
  323. * baseElements The array of base elements.
  324. * @param {Exponent}
  325. * ephemeralKey The ephemeral key.
  326. * @param {Exponent}
  327. * messageKey The message key.
  328. * @returns {ElGamalEncryptedElements} The ciphertext.
  329. * @throws {Error}
  330. * If the number base elements provided as input is not an odd
  331. * number.
  332. */
  333. this.generatePlaintextExponentEqualityProofCiphertext = function(
  334. baseElements, ephemeralKey, messageKey) {
  335. var numBaseElements = baseElements.length;
  336. if ((numBaseElements % 2) === 0) {
  337. throw new Error(
  338. 'Number of base elements must be an odd number for plaintext exponent equality proof generation; Found ' +
  339. numBaseElements);
  340. }
  341. var numPlaintextElements = ((numBaseElements - 1) / 2);
  342. var plaintext = [];
  343. for (var i = 0; i < numPlaintextElements; i++) {
  344. plaintext.push(baseElements[1 + i].exponentiate(ephemeralKey));
  345. }
  346. var publicKeyElements = [];
  347. for (var j = 0; j < numPlaintextElements; j++) {
  348. publicKeyElements.push(baseElements[1 + numPlaintextElements + j]);
  349. }
  350. var gamma = baseElements[0].exponentiate(ephemeralKey);
  351. var phis = [];
  352. for (var k = 0; k < numPlaintextElements; k++) {
  353. phis.push(
  354. plaintext[k].multiply(publicKeyElements[k].exponentiate(messageKey)));
  355. }
  356. return elGamalService_.newEncryptedElements(gamma, phis);
  357. };
  358. }