/* * Copyright 2018 Scytl Secure Electronic Voting SA * * All rights reserved * * See our extended copyright notice in *file 'Copyright.txt' which is part of this source code package */ cryptolib.modules.commons = cryptolib.modules.commons || {}; /** * @namespace commons/mathematical */ cryptolib.modules.commons.mathematical = function(box) { 'use strict'; box.commons = box.commons || {}; /** * A module the defines mathematical groups, elements, and operations that * can be performed * * @exports commons/mathematical */ box.commons.mathematical = {}; var BigInteger = box.forge.jsbn.BigInteger; var exceptions; var converters; cryptolib('commons.exceptions', 'commons.utils', function(box) { exceptions = box.commons.exceptions; converters = new box.commons.utils.Converters(); }); /** * Given p and Zp representing 'Integers (mod p)' group, a Zp subgroup is a * group where the elements are a subset of elements from Zp. * * The order of the subgroup is q, that is the number of elements. Both Zp * and the ZpSubgroup are finite cyclic groups, it means that all elements * can be generated exponentiating a special group element called generator. * * When the p and q are related with the restriction p = 2q + 1 the subgroup * is also defined as 'Quadratic Residue'. * * @class * @param valueG * {forge.jsbn.BigInteger} The generator of the subgroup, as a * BigInteger. This value must be a group element different from * one. * @param valueP * {forge.jsbn.BigInteger} The modulus, as a BigInteger. * @param valueQ * {forge.jsbn.BigInteger} The order of the subgroup, as a * BigInteger. * * @throws CryptoLibException * if 0 < q < p restriction is not accomplished * @throws CryptoLibException * if subgroup generator is nor between 2 and p-1 * */ box.commons.mathematical.ZpSubgroup = function(valueG, valueP, valueQ) { if ((typeof valueG === 'undefined') || (typeof valueP === 'undefined') || (typeof valueQ === 'undefined')) { throw new exceptions.CryptoLibException( 'The given parameters should be initialized'); } if ((BigInteger.ONE.compareTo(valueG) >= 0) || (valueP.compareTo(valueG) <= 0)) { throw new exceptions.CryptoLibException( 'The generator should be between 2 and p-1'); } if ((BigInteger.ZERO.compareTo(valueQ) >= 0) || (valueP.compareTo(valueQ) <= 0)) { throw new exceptions.CryptoLibException( 'The relationship between the values of the p and q parameters should be such that 0 < q < p'); } var _p = valueP; var _q = valueQ; var generator = new box.commons.mathematical.ZpGroupElement(valueG, _p, _q); var identity = new box.commons.mathematical.ZpGroupElement(BigInteger.ONE, _p, _q); /** * @function * @returns the identity element of the group. */ this.getIdentity = function() { return identity; }; /** * @function * @returns the q parameter (the order of the group). */ this.getQ = function() { return _q; }; /** * @function * @returns the p parameter (the modulus of the group). */ this.getP = function() { return _p; }; /** * @function * @returns {box.commons.mathematical.ZpGroupElement} the generator * element of the group. */ this.getGenerator = function() { return generator; }; }; box.commons.mathematical.ZpSubgroup.prototype = { /** * Checks whether a given element is a member of this MathematicalGroup. * * An element is a member of the group if: * * * @function * @param element * {ZpGroupElement} the element whose group membership should * be checked. * @returns true if the given element is member of the group, otherwise * false. */ isGroupMember: function(element) { if (typeof element !== 'undefined' && element.getP().equals(this.getP())) { var modPow = element.getElementValue().modPow(this.getQ(), this.getP()); return BigInteger.ONE.equals(modPow); } else { return false; } }, /** * Check if this group is equal to the received group. * * @function * @param group * {ZpSubgroup} the group which should be checked against * this group for equality. * @returns true if the given group has the same q, the * same p, and the same generator. */ equals: function(group) { if (typeof group !== 'undefined' && group.getGenerator().equals(this.getGenerator()) && group.getQ().equals(this.getQ()) && group.getP().equals(this.getP())) { return true; } else { return false; } }, /** * Check if this group is a quadratic residue group, which is defined * such that p = 2q + 1. * * @function * @returns true if the given group is a quadratic residue group. */ isQuadraticResidueGroup: function() { return this.getP().equals( new BigInteger('2').multiply(this.getQ()).add(BigInteger.ONE)); }, /** * Displays a string representation of this mathematical group JSON. *

* Note: in order to permit interoperability between libraries, this * representation should match the equivalent representation in Java. * * @function * @returns a string representation of this mathematical group JSON. */ stringify: function() { return JSON.stringify({ zpSubgroup: { p: converters.base64FromBigInteger(this.getP()), q: converters.base64FromBigInteger(this.getQ()), g: converters.base64FromBigInteger( this.getGenerator().getElementValue()) } }); } }; /** * Class representing elements of a Zp group. * *

* Note: This constructor does not check whether the given value is a valid * member of the subgroup. To check subgroup membership the function * zpSubgroup.isGroupMember(groupElement) can be called, * however this is a computationally expensive operation. * * @class * @param value * {forge.jsbn.BigInteger} Value of the element (not null). The * value must be between [1..p-1] * @param groupP * {forge.jsbn.BigInteger} The p parameter, as a BigInteger. * @param groupQ * {forge.jsbn.BigInteger} The q parameter, as a BigInteger. * @throws CryptoLibException * if there are any problems with the inputs. */ box.commons.mathematical.ZpGroupElement = function(value, groupP, groupQ) { if ((typeof value === 'undefined')) { throw new exceptions.CryptoLibException( 'The received value is not the expected object'); } if ((BigInteger.ZERO.compareTo(value) >= 0) || (groupP.compareTo(value) <= 0)) { throw new exceptions.CryptoLibException( 'The value of the element should be between 1 and p-1. P: ' + groupP + ', value: ' + value); } if ((BigInteger.ZERO.compareTo(groupQ) >= 0) || (groupP.compareTo(groupQ) <= 0)) { throw new exceptions.CryptoLibException( 'The relationship between the values of the p and q parameters should hold that 0 < q < p'); } var v = value; var p = groupP; var q = groupQ; /** * Performs a basic check to verify if this element belongs to the same * group as element by checking if the p and q parameters * of both are equal. *

* Note: this function does NOT perform the mathematical operation * needed to actually confirm that a value is an element of a group, * which involves modular exponentiation and is very computationally * costly. Instead, this function simply examines the p and q parameters * that are stored within both elements. * * @function * @param element * {ZpGroupElement} element to by multiplied with this * element. * @throws CryptoLibException * if the p and q parameters of the group that the received * element belongs to are not equal to the p and q * parameters of this element. */ this._validateReceivedElementIsFromSameGroup = function(element) { if (typeof element === 'undefined') { throw new exceptions.CryptoLibException( 'The received value is not the expected object'); } if ((!this.getP().equals(element.getP())) || (!this.getQ().equals(element.getQ()))) { throw new exceptions.CryptoLibException( 'Operations can only be performed on group elements which are members of the same Zp subgroup'); } }; /** * Performs a basic check to verify if this element belongs to the same * group as exponent by checking if the p and q * parameters of both are equal. *

* Note: this function does NOT perform the mathematical operation * needed to actually confirm that an exponent belongs to a particular * group, which would involve confirming the following: *

* 0 >= exponent value <= p-1 * * @function * @param exponent * {Exponent} element to by multiplied with this element. * @throws CryptoLibException * if p and q parameters of the group that the received * element belongs to are not equal to the p and q * parameters of this element. */ this._validateReceivedExponent = function(exponent) { if (typeof exponent === 'undefined') { throw new exceptions.CryptoLibException( 'The received value is not the expected object'); } if (!this.getQ().equals(exponent.getQ())) { throw new exceptions.CryptoLibException( 'The exponent should have the same q as this Zp group element'); } }; /** * @function * @returns The value of this element. */ this.getElementValue = function() { return v; }; /** * @function * @returns The p parameter of the mathematical group to which this * element belongs. */ this.getP = function() { return p; }; /** * @function * @returns The q parameter of the mathematical group to which this * element belongs. */ this.getQ = function() { return q; }; }; box.commons.mathematical.ZpGroupElement.prototype = { /** * Multiple this element by the received element. The operation is * performed mod p. Performs a basic check to confirm that this element * and the received element belong to the same group. * * @function * @param element * {ZpGroupElement} element to by multiplied with this * element. * @returns (this * element) mod p, as a ZpGroupElement. * @throws CryptoLibException * if the p and q parameters of the group that the received * element belongs to are not equal to the p and q * parameters of this element. */ multiply: function(element) { this._validateReceivedElementIsFromSameGroup(element); var result = this.getElementValue() .multiply(element.getElementValue()) .mod(this.getP()); return new box.commons.mathematical.ZpGroupElement( result, this.getP(), this.getQ()); }, /** * Exponentiate this element to the received exponent. * * @function * @param exponent * {Exponent} the exponent used to raise the value of the * group element. * @returns (thisexponent) mod p, as a * ZpGroupElement. * @throws CryptoLibException * if the p and q parameters of the group that the received * exponent belongs to are not equal to the p and q * parameters of this element. */ exponentiate: function(exponent) { this._validateReceivedExponent(exponent); var result = this.getElementValue().modPow(exponent.getValue(), this.getP()); return new box.commons.mathematical.ZpGroupElement( result, this.getP(), this.getQ()); }, /** * Get the inverse of this element, mod p. * * @function * @returns the inverse of this element mod p, as a ZpGroupElement. */ invert: function() { var result = this.getElementValue().modInverse(this.getP()); return new box.commons.mathematical.ZpGroupElement( result, this.getP(), this.getQ()); }, /** * Check if this element is equal to the received element. *

* Elements are considered equal if: *

* * @function * @param element * {ZpGroupElement} the element which should be checked * against this element for equality. * @returns true if the given group element has the same v, * the same p and the same q. */ equals: function(element) { if (typeof element !== 'undefined' && element.getElementValue().equals(this.getElementValue()) && element.getP().equals(this.getP()) && element.getQ().equals(this.getQ())) { return true; } else { return false; } }, /** * Displays a string representation of this Zp group element JSON. *

* Note: in order to permit interoperability between libraries, this * representation should match the equivalent representation in Java. * * @function * @returns a string representation of Zp group element JSON. */ stringify: function() { return JSON.stringify({ zpGroupElement: { p: converters.base64FromBigInteger(this.getP()), q: converters.base64FromBigInteger(this.getQ()), value: converters.base64FromBigInteger(this.getElementValue()) } }); } }; /** * Represents an exponent for a particular mathematical group. *

* The value of an exponent must be within the range [0..q-1]. If the * received value is not within this range, then the value that will be * assigned to the created Exponent will be calculated as follows: *

* value = value mod q * * @class * * @param q * {forge.jsbn.BigInteger} the order of the mathematical group * for which this is an exponent. * @param exponentValue * {forge.jsbn.BigInteger} the value of the exponent. * @throws CryptoLibException * if there are any problems with the inputs. */ box.commons.mathematical.Exponent = function(valueQ, exponentValue) { if (valueQ === 'undefined' || valueQ.compareTo(BigInteger.ZERO) === 0) { throw new exceptions.CryptoLibException( 'Q (the order of the group) cannot be null or zero'); } var _q = valueQ; /** * Gets the value to set for this Exponent. This value has to be a * number between 0 and q-1 (inclusive), * so if it is less than 0 or greater than * q-1, then mod q has to be applied. * * @function * @param {forge.jsbn.BigInteger} * exponentValue the value of the exponent. * @returns the value to set to this exponent. */ function getExponent(exponentValue) { if ((_q.compareTo(exponentValue) > 0) && (BigInteger.ZERO.compareTo(exponentValue) <= 0)) { return exponentValue; } else { return exponentValue.mod(_q); } } var _value = getExponent(exponentValue); /** * Checks if this exponent and the received exponent belong to the same * group. * * @function * @param exponent * {Exponent} the exponent which should be checked to see if * it belongs to the same group as this exponent. * @throws CryptoLibException * if the received exponent is undefined or does not belong * to the same group as this exponent. */ this._confirmSameGroup = function(exponent) { if (typeof exponent === 'undefined') { throw new exceptions.CryptoLibException( 'The received exponent is not the expected object'); } if (!_q.equals(exponent.getQ())) { throw new exceptions.CryptoLibException( 'Operations may only be performed with exponents of the same mathematical group order'); } }; /** * @function * @returns The numeric value of the exponent. */ this.getValue = function() { return _value; }; /** * @function * @returns The numeric value of the exponent. */ this.getQ = function() { return _q; }; }; box.commons.mathematical.Exponent.prototype = { /** * Returns an Exponent whose value is: *

* (this + exponent) mod q * * @param exponent * {Exponent} the exponent to be added to this exponent. * @returns (this + exponent) mod q */ add: function(exponent) { this._confirmSameGroup(exponent); var result = this.getValue().add(exponent.getValue()).mod(this.getQ()); return new box.commons.mathematical.Exponent(this.getQ(), result); }, /** * Returns an Exponent whose value is: *

* (this - exponent) mod q * * @param exponent * {Exponent} the exponent to be subtracted from this * exponent. * @returns (this - exponent) mod q */ subtract: function(exponent) { this._confirmSameGroup(exponent); var result = this.getValue().subtract(exponent.getValue()).mod(this.getQ()); return new box.commons.mathematical.Exponent(this.getQ(), result); }, /** * Returns an Exponent whose value is: *

* (this * exponent) mod q * * @param exponent * {Exponent} the exponent to be multiplied with this * exponent. * @returns (this * exponent) mod q */ multiply: function(exponent) { this._confirmSameGroup(exponent); var result = this.getValue().multiply(exponent.getValue()).mod(this.getQ()); return new box.commons.mathematical.Exponent(this.getQ(), result); }, /** * Returns an Exponent whose value is (-this) mod q * * @returns (-this mod q) */ negate: function() { return new box.commons.mathematical.Exponent( this.getQ(), this.getValue().negate().mod(this.getQ())); }, /** * Check if this exponent is equal to the received exponent. *

* Elements are considered equal if: *

* * @param {Exponent} * exponent the exponent to be checked against this exponent * for equality. * @returns true if the given exponent has the same value * and belongs to the same group as this * exponent. */ equals: function(exponent) { if (exponent.getValue().equals(this.getValue()) && exponent.getQ().equals(this.getQ())) { return true; } else { return false; } }, /** * Displays a string representation of the exponent JSON. *

* Note: in order to permit interoperability between libraries, this * representation should match the equivalent representation in Java. * * @function * @returns a string representation of the exponent JSON. */ stringify: function() { return JSON.stringify({ exponent: { q: converters.base64FromBigInteger(this.getQ()), value: converters.base64FromBigInteger(this.getValue()) } }); } }; /** * Provides utility functionality for working with mathematical groups. * * @class groupUtils * @memberof commons/mathematical */ box.commons.mathematical.groupUtils = (function() { /** * Deserializes a Zp Subgroup string representation to a ZpSubgroup * object. * * @function * @memberof commons/mathematical.groupUtils * @param groupJson * {JSON} a JSON representation of a Zp subgroup. * @returns a new ZpSubgroup, created from the received string. */ function deserializeGroup(groupJson) { var parsed = JSON.parse(groupJson); var p = converters.base64ToBigInteger(parsed.zpSubgroup.p); var q = converters.base64ToBigInteger(parsed.zpSubgroup.q); var g = converters.base64ToBigInteger(parsed.zpSubgroup.g); return new box.commons.mathematical.ZpSubgroup(g, p, q); } /** * Deserializes a Zp Subgroup element string to a ZpGroupElement object. * * @function * @memberof commons/mathematical.groupUtils * @param groupElementJson * {JSON} a JSON representation of a Zp Subgroup element * element. * @returns a new ZpGroupElement, created from the received string. */ function deserializeGroupElement(groupElementJson) { var parsed = JSON.parse(groupElementJson); var value = converters.base64ToBigInteger(parsed.zpGroupElement.value); var p = converters.base64ToBigInteger(parsed.zpGroupElement.p); var q = converters.base64ToBigInteger(parsed.zpGroupElement.q); return new box.commons.mathematical.ZpGroupElement(value, p, q); } /** * Deserializes an exponent string to an Exponent object. * * @function * @memberof commons/mathematical.groupUtils * @param exponentJson * {JSON} a JSON representation of an exponent. * @returns a new Exponent, created from the received string. */ function deserializeExponent(exponentJson) { var parsed = JSON.parse(exponentJson); var q = converters.base64ToBigInteger(parsed.exponent.q); var value = converters.base64ToBigInteger(parsed.exponent.value); return new box.commons.mathematical.Exponent(q, value); } /** * Compress a list of group elements. *

* Note: an exception will be thrown if an array is received which * contains any elements that are not elements of the mathematical * group. * * @function * @memberof commons/mathematical.groupUtils * @param group * {ZpSubgroup} the mathematical group. * @param elementsToBeCompressedArray * {object} the array of group elements to be compressed. * @returns the result of the compression process, as a group element. * @throws CryptoLibException * if there are any problems with the inputs. */ function compressGroupElements(group, elementsToBeCompressedArray) { validateArray(elementsToBeCompressedArray); validateGroup(group); var elem = elementsToBeCompressedArray[0]; for (var i = 1; i < elementsToBeCompressedArray.length; i++) { elem = elem.multiply(elementsToBeCompressedArray[i]); } return elem; } /** * Compress a list of exponents. *

* Note: an exception will be thrown if an array is received which * contains any exponents that are not exponents of the mathematical * group. * * @function * @memberof commons/mathematical.groupUtils * @param group * {ZpSubgroup} the mathematical group * @param exponentsToBeCompressedArray * {object} the array of exponents to be compressed * @returns the result of the compression process, as an exponent. * @throws CryptoLibException * if there are any problems with the inputs. */ function compressExponents(group, exponentsToBeCompressedArray) { validateArray(exponentsToBeCompressedArray); validateGroup(group); validateExponents(group.getQ(), exponentsToBeCompressedArray); var elem = exponentsToBeCompressedArray[0]; for (var i = 1; i < exponentsToBeCompressedArray.length; i++) { elem = elem.add(exponentsToBeCompressedArray[i]); } return elem; } /** * Builds a new array of elements from the input array, where the final * elements from the input array are compressed into a simple element. * * @function * @memberof commons/mathematical.groupUtils * @param group * {ZpSubgroup} the mathematical group that this compressor * operates on. * @param inputArray * {object} the input array of group elements. * @param numElementsRequiredInNewList * {number} the number of elements that should be in the * output array. * @returns a new array of group elements. * @throws CryptoLibException * if there are any problems with the inputs. */ function buildListWithCompressedFinalElement( group, inputArray, numElementsRequiredInNewList) { validateArray(inputArray); validateGroup(group); if (numElementsRequiredInNewList < 1) { throw new exceptions.CryptoLibException( 'The number of elements in the output list must be at least 1'); } var offset = numElementsRequiredInNewList - 1; var outputArray = inputArray.slice(0, offset); var lastElement = compressGroupElements( group, inputArray.slice(offset, inputArray.length)); outputArray.push(lastElement); return outputArray; } /** * Builds a new array of exponents from the input array, where the final * exponents from the input array are compressed into a simple * exponents. * * @function * @memberof commons/mathematical.groupUtils * @param group * {ZpSubgroup} the mathematical group that this compressor * operates on. * @param inputArray * {object} the input array of exponents. * @param numExponentsRequiredInNewList * {number} the number of exponents that should be in the * output array. * @returns a new array of group elements. * @throws CryptoLibException * if there are any problems with the inputs. */ function buildListWithCompressedFinalExponent( group, inputArray, numExponentsRequiredInNewList) { validateArray(inputArray); validateGroup(group); if (numExponentsRequiredInNewList < 1) { throw new exceptions.CryptoLibException( 'The number of exponents in the output list must be at least 1'); } var offset = numExponentsRequiredInNewList - 1; var outputArray = inputArray.slice(0, offset); var lastExponent = compressExponents(group, inputArray.slice(offset, inputArray.length)); outputArray.push(lastExponent); return outputArray; } /** * Given two arrays of group elements, this method produces a new list * of group elements that represents the two input lists combined. *

* The two arrays must only contain values that are elements of the * mathematical group that this divider operates on. If either array * contains any element that is not a group element then an exception * will be thrown. * * @function * @memberof commons/mathematical.groupUtils * @param arrayElements1 * {object} an input array of Zp group elements. * @param arrayElements2 * {object} an input array of Zp group elements. * @returns a new list of group elements. * @throws CryptoLibException * if there are any problems with the inputs. */ function divide(arrayElements1, arrayElements2) { validateArray(arrayElements1); validateArray(arrayElements2); if (arrayElements1.length !== arrayElements2.length) { throw new exceptions.CryptoLibException( 'Both arrays should have the same length'); } var newList = []; var newElement; for (var i = 0; i < arrayElements1.length; i++) { newElement = arrayElements1[i].multiply(arrayElements2[i].invert()); newList.push(newElement); } return newList; } /** * Given an array of group elements and one exponent, this method * produces a new list of group elements that represents the * exponentiation of the group elements to the exponent. *

* The array must contain values that are elements of the mathematical * group that this exponentiation activity operates on. If the array * contains any element that is not a group element then an exception * will be thrown. * * @function * @memberof commons/mathematical.groupUtils * @param {array} arrayElements * an input array of Zp group elements. * @param {object} exponent * An Exponent. * @param {object} group * The mathematical group that all of the elements in * arrayElements belong to. * @param {boolean} validateElements An Exponent. * @return A new list of group elements. * */ function exponentiateArrays( arrayElements, exponent, group, validateElements) { validateArray(arrayElements); validateExponent(exponent); validateGroup(group); // If requested, validate all elements prior to any operations. if (typeof validateElements !== 'undefined' && validateElements) { for (var j = 0; j < arrayElements.length; j++) { if (!group.isGroupMember(arrayElements[j])) { throw new exceptions.CryptoLibException( 'The element does not belong to the group'); } } } var newList = []; var newElement; for (var i = 0; i < arrayElements.length; i++) { newElement = arrayElements[i].exponentiate(exponent); newList.push(newElement); } return newList; } /** * Returns a new random exponent for the received mathematical group. *

* The value of the created exponent will be between 0 * and q-1. * * @function * @memberof commons/mathematical.groupUtils * @param group * {ZpSubgroup} the mathematical group. * @param cryptoRandomInteger * {CryptoScytlRandomInteger} the source of randomness. * @param {boolean} * useShortExponent true if a short exponent is to be * generated. Default value is false. * @returns a new random exponent. * @throws CryptoLibException * if there are any problems with the inputs. */ function generateRandomExponent( group, cryptoRandomInteger, useShortExponent) { validateGroup(group); if (typeof cryptoRandomInteger === 'undefined') { throw new exceptions.CryptoLibException( 'The given parameters should be initialized'); } var _useShortExponent = true; if (!useShortExponent) { _useShortExponent = false; } var q = group.getQ(); var qBitLength = q.bitLength(); var randomExponentLength; if (_useShortExponent) { if (qBitLength < box.SHORT_EXPONENT_BIT_LENGTH) { throw new exceptions.CryptoLibException( 'Zp subgroup order bit length must be greater than or equal to short exponent bit length : ' + box.SHORT_EXPONENT_BIT_LENGTH + '; Found ' + qBitLength); } randomExponentLength = box.SHORT_EXPONENT_BIT_LENGTH; } else { randomExponentLength = qBitLength; } var randomExponentValue; var randomExponentFound = false; while (!randomExponentFound) { randomExponentValue = cryptoRandomInteger.nextRandomByBits(randomExponentLength); if (randomExponentValue.compareTo(q) < 0) { randomExponentFound = true; } } return new box.commons.mathematical.Exponent(q, randomExponentValue); } /** * Returns a group element symmetric key which is obtained by * exponentiating the generator of a given mathematical group to a * random exponent k. * * @function * @memberof commons/mathematical.groupUtils * @param group * {ZpSubgroup} the mathematical group. * @param cryptoRandomInteger * {CryptoScytlRandomInteger} the source of randomness. * @returns the secret key, as a group element. * @throws CryptoLibException * if there are any problems with the inputs. */ function generateGroupElementSecretKey(group, cryptoRandomInteger) { var exponent = generateRandomExponent(group, cryptoRandomInteger); var groupElementSecretKey = group.getGenerator().exponentiate(exponent); return groupElementSecretKey; } /** * Build a ZpSubgroup from the p and g parameters. *

* NOTE: This method builds a particular type of mathematical group with * property that: *

* P = (Q * 2) + 1 *

* This property holds for all groups generated using this method, but * this property does not hold for all mathematical groups. * * @function * @memberof commons/mathematical.groupUtils * @param p * {forge.jsbn.BigInteger} the p parameter of the group. * @param g * {forge.jsbn.BigInteger} the generator of the group. * @returns the generated ZpSubgroup. * @throws CryptoLibException * if there are any problems with the inputs. */ function buildZpSubgroupFromPAndG(p, g) { validateBuildFromPAndGInputs(p, g); var q = p.subtract(BigInteger.ONE).divide(new BigInteger('2')); return new box.commons.mathematical.ZpSubgroup(g, p, q); } /** * Build a random ZpSubgroup whose p parameter will have the specified * bit length. The certainty that both p and q are both prime is * specified by certainty. *

* NOTE: This method builds a particular type of Zp subgroup with * property that: *

* p = (q * 2) + 1 *

* This property holds for all mathematical groups generated using this * method, but this property does not hold for all mathematical groups. *

* Note: the minimum bit length of the p parameter that is permitted by * this method is 2. If a bit length less than 2 is requested then a * CryptoLibException will be thrown. * * @function * @memberof commons/mathematical.groupUtils * @param bitLengthOfP * {number} the bit length that the p parameter of the * generated group should be. * @param cryptoRandomInteger * {CryptoScytlRandomInteger} an instance of * CryptoRandomInteger that can be used as a source of random * integers. * @param certainty * {number} the required level of certainty that the q * parameter of the generated group is prime. * @returns the generated ZpSubgroup. * @throws CryptoLibException * if there are any problems with the inputs. */ function buildRandomZpSubgroupFromLengthOfP( bitLengthOfP, cryptoRandomBytes, certainty) { validateBuildFromLengthPInputs( bitLengthOfP, cryptoRandomBytes, certainty); var p, q; var twoBI = new BigInteger('2'); var randomGroupFound = false; var options = {prng: cryptoRandomBytes}; var callback = function(err, num) { if (err) { throw new exceptions.CryptoLibException( 'Error while generating prime ' + err); } p = num; q = num.subtract(BigInteger.ONE).divide(twoBI); }; while (!randomGroupFound) { forge.prime.generateProbablePrime(bitLengthOfP, options, callback); if (q.isProbablePrime(certainty)) { randomGroupFound = true; } } var generator = findSmallestGenerator(p, q); return new box.commons.mathematical.ZpSubgroup(generator, p, q); } /** * Given an input array containing possible group members, this method * cycles through that array, checking if each element is a group * member. This method attempts to find the specified number of group * members. Once that number has been found, the method will return a * new array containing the specified number of group members. *

* If the required number of group members are not found in the input * array then a CryptoLibException will be thrown. * * @function * @memberof commons/mathematical.groupUtils * @param possibleGroupMembersArray * {object} an array containing possible group members. * @param group * {ZpSubgroup} the Zp subgroup for which the specified * number of group members are required. * @param numMembersRequired * {number} the number of group members of the specified * group that should be added to the output list. * @returns a new array containing the specified number of group * elements, which have been read from the input array. * @throws CryptoLibException * if there are any problems with the inputs. */ function extractNumberOfGroupMembersFromListOfPossibleMembers( possibleGroupMembersArray, group, numMembersRequired) { validateExtractFromListInputs( possibleGroupMembersArray, group, numMembersRequired); var outputArray = []; var membersFound = 0; var candidate; for (var i = 0; i < possibleGroupMembersArray.length; i++) { candidate = new box.commons.mathematical.ZpGroupElement( possibleGroupMembersArray[i], group.getP(), group.getQ()); if (group.isGroupMember(candidate)) { outputArray.push(candidate); membersFound++; } if (membersFound === numMembersRequired) { return outputArray; } } if (membersFound !== numMembersRequired) { throw new exceptions.CryptoLibException( 'Error - did not find the required number of group members in the given list. The required number of was ' + numMembersRequired + ', number of members found was ' + membersFound); } } /** * Find the smallest generator of a mathematical group. *

* Note: starts with a candidate generator value (two is the initial * candidate generator value), and checks if the candidate generator is * a group memeber. If that candidate is a group memeber then return * that value, else increment the candidate by one and again check if * the candidate is a group member. Continue this process until the * candidate value is less than the parameter p. * * @function * @memberof commons/mathematical.groupUtils * @params p {number} the p parameter of the group. * @params q {number} the q parameter of the group. * @throws CryptoLibException */ function findSmallestGenerator(p, q) { var g = new BigInteger('2'); var generatorFound = false; while ((!generatorFound) && (g.compareTo(p) < 0)) { if (g.modPow(q, p).equals(BigInteger.ONE)) { generatorFound = true; } else { g = g.add(BigInteger.ONE); } } if (!generatorFound) { throw new exceptions.CryptoLibException( 'Failed to find a generator, p was: ' + p + ', q was: ' + q); } return g; } /** * Validates a group. * * @function * @memberof commons/mathematical.groupUtils * @params group {ZpSubgroup} the group to be validated. * @throws CryptoLibException * if the received group is undefined. */ function validateGroup(group) { if (typeof group === 'undefined' || null === group) { throw new exceptions.CryptoLibException( 'The given group should be initialized'); } } function validateExponent(exponent) { if (typeof exponent === 'undefined') { throw new exceptions.CryptoLibException( 'The given exponent should be initialized'); } } /** * Validates that an array is initialized and non-empty. * * @function * @memberof commons/mathematical.groupUtils * @params inputArray {object} an array to be validated. * @throws CryptoLibException * if the received array is not initialized or is empty. */ function validateArray(inputArray) { if (typeof inputArray === 'undefined') { throw new exceptions.CryptoLibException( 'The given array should be initialized'); } if (!(inputArray instanceof Array)) { throw new exceptions.CryptoLibException( 'The given array are not from the expected type'); } if (inputArray.length < 1) { throw new exceptions.CryptoLibException( 'The given array cannot be empty'); } } /** * Performs a very basic validation on the received inputs. * * @function * @memberof commons/mathematical.groupUtils * @params p {object} the first parameter. * @params g {object} the second parameter. * @throws CryptoLibException * if either (or both) inputs are undefined. */ function validateBuildFromPAndGInputs(p, g) { if ((typeof p === 'undefined') || (typeof g === 'undefined')) { throw new exceptions.CryptoLibException('p or g are incorrect'); } } /** * Performs a some basic validations on the received inputs. * * @function * @memberof commons/mathematical.groupUtils * @params bitLengthOfP {number} bit length of p parameter. * @params cryptoRandomBytes {CryptoScytlRandomBytes} a secure source of * random bytes. * @params certainty {number} a certainty level. * @throws CryptoLibException * if any of the inputs fail any of the validations. */ function validateBuildFromLengthPInputs( bitLengthOfP, cryptoRandomBytes, certainty) { if (bitLengthOfP < 2) { throw new exceptions.CryptoLibException( 'The bit length should be higher'); } if (typeof cryptoRandomBytes === 'undefined') { throw new exceptions.CryptoLibException( 'The random generator should be initialized'); } if (certainty < box.MINIMUM_PRIME_CERTAINTY_LEVEL) { throw new exceptions.CryptoLibException('Certainty should be higher'); } } /** * Performs some basic validations on the received inputs. * * @function * @memberof commons/mathematical.groupUtils * @params inputArray {object} an array. * @params group {ZpSubgroup} a Zp subgroup. * @params numMembersRequired {number} an integer value. * @throws CryptoLibException * if any of the inputs fail any of the validations. */ function validateExtractFromListInputs( inputArray, group, numMembersRequired) { validateArray(inputArray); validateGroup(group); if (typeof numMembersRequired === 'undefined') { throw new exceptions.CryptoLibException( 'The given objects should be initialized'); } if (typeof numMembersRequired !== 'number') { throw new exceptions.CryptoLibException( 'The given objects are not from the expected type'); } if (numMembersRequired < 1 || numMembersRequired > inputArray.length) { throw new exceptions.CryptoLibException( 'The given number of required elements cannot be higher than the number of elements of the array'); } } /** * Validates that all of the exponents in the received list are * exponents are members of the received group, by checking if the * groups that they contain are equal. * * @function * @memberof commons/mathematical.groupUtils * @params group {ZpSubgroup} a Zp subgroup. * @params exponents {object} a list of exponents. */ function validateExponents(q, exponents) { for (var i = 0; i < exponents.length; i++) { if (!exponents[i].getQ().equals(q)) { throw new exceptions.CryptoLibException( 'The list of exponents contained an exponent which does not belong to the group with the same order.'); } } } return { buildZpSubgroupFromPAndG: buildZpSubgroupFromPAndG, buildRandomZpSubgroupFromLengthOfP: buildRandomZpSubgroupFromLengthOfP, extractNumberOfGroupMembersFromListOfPossibleMembers: extractNumberOfGroupMembersFromListOfPossibleMembers, generateRandomExponent: generateRandomExponent, generateGroupElementSecretKey: generateGroupElementSecretKey, compressGroupElements: compressGroupElements, buildListWithCompressedFinalElement: buildListWithCompressedFinalElement, deserializeGroup: deserializeGroup, deserializeGroupElement: deserializeGroupElement, deserializeExponent: deserializeExponent, compressExponents: compressExponents, buildListWithCompressedFinalExponent: buildListWithCompressedFinalExponent, divide: divide, exponentiateArrays: exponentiateArrays }; })(); };