post-e-voting/source-code/scytl-cryptolib/cryptolib-js/lib/commons.mathematical.js

/*
 * 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:
     * <ul>
     * <li><code>element</code> has an integer value between
     * <code>1</code> and <code>p-1</code>:
     * <code>(0 < element < p)</code></li>
     * <li><code>element<sup>q</sup> mod p = 1</code></li>
     * </ul>
     *
     * @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 <code>q</code>, the
     *          same <code>p</code>, and the same <code>generator</code>.
     */
    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.
     * <p>
     * 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.
   *
   * <p>
   * Note: This constructor does not check whether the given value is a valid
   * member of the subgroup. To check subgroup membership the function
   * <code>zpSubgroup.isGroupMember(groupElement)</code> 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 <code>[1..p-1]</code>
   * @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 <code>element</code> by checking if the p and q parameters
     * of both are equal.
     * <p>
     * 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 <code>exponent</code> by checking if the p and q
     * parameters of both are equal.
     * <p>
     * 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:
     * <p>
     * <code>0 >= exponent value <= p-1</code>
     *
     * @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 <code>(this * element) mod p</code>, 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 <code>(this<sup>exponent</sup>) mod p</code>, 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.
     * <p>
     * Elements are considered equal if:
     * <ul>
     * <li>They have the same value.</li>
     * <li>They belong to the same group (which is confirmed here by
     * checking if their p and q parameters are equal).</li>
     * </ul>
     *
     * @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 <code>v</code>,
     *          the same <code>p</code> and the same <code>q</code>.
     */
    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.
     * <p>
     * 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.
   * <p>
   * 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:
   * <p>
   * <code>value = value mod q</code>
   *
   * @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 <code>0</code> and <code>q-1</code> (inclusive),
     * so if it is less than <code>0</code> or greater than
     * <code>q-1</code>, then <code>mod q</code> 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:
     * <p>
     * <code>(this + exponent) mod q</code>
     *
     * @param exponent
     *            {Exponent} the exponent to be added to this exponent.
     * @returns <code>(this + exponent) mod q</code>
     */
    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:
     * <p>
     * <code>(this - exponent) mod q</code>
     *
     * @param exponent
     *            {Exponent} the exponent to be subtracted from this
     *            exponent.
     * @returns <code>(this - exponent) mod q</code>
     */
    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:
     * <p>
     * <code>(this * exponent) mod q</code>
     *
     * @param exponent
     *            {Exponent} the exponent to be multiplied with this
     *            exponent.
     * @returns <code>(this * exponent) mod q</code>
     */
    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 <code>(-this) mod q</code>
     *
     * @returns <code>(-this mod q)</code>
     */
    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.
     * <p>
     * Elements are considered equal if:
     * <ul>
     * <li>They have the same value.</li>
     * <li>They belong to the groups with the same order.</li>
     * </ul>
     *
     * @param {Exponent}
     *            exponent the exponent to be checked against this exponent
     *            for equality.
     * @returns true if the given exponent has the same <code>value</code>
     *          and belongs to the same <code>group</code> 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.
     * <p>
     * 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.
     * <P>
     * 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.
     * <P>
     * 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.
     * <P>
     * 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.
     * <P>
     * 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.
     * <P>
     * The value of the created exponent will be between <code>0</code>
     * 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 <code>k</code>.
     *
     * @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.
     * <P>
     * NOTE: This method builds a particular type of mathematical group with
     * property that:
     * <P>
     * P = (Q * 2) + 1
     * <P>
     * 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.
     * <P>
     * NOTE: This method builds a particular type of Zp subgroup with
     * property that:
     * <P>
     * p = (q * 2) + 1
     * <P>
     * This property holds for all mathematical groups generated using this
     * method, but this property does not hold for all mathematical groups.
     * <P>
     * 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.
     * <p>
     * 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.
     * <p>
     * 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
    };
  })();
};