post-e-voting/source-code/scytl-cryptolib/cryptolib-js/lib/homomorphic.cipher.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.homomorphic = cryptolib.modules.homomorphic || {};

cryptolib.modules.homomorphic.cipher = function(box) {
  'use strict';

  box.homomorphic = box.homomorphic || {};
  box.homomorphic.cipher = {};
  /**
   * A submodule that holds ElGamal cipher functionalities.
   *
   * @exports homomorphic/cipher/factory
   */
  box.homomorphic.cipher.factory = {};

  var converters, exceptions, randomFactory, mathematical, keyPairFactory;

  var f = function(box) {
    converters = new box.commons.utils.Converters();
    exceptions = box.commons.exceptions;
    mathematical = box.commons.mathematical;
    randomFactory =
        new box.primitives.securerandom.factory.SecureRandomFactory();
    keyPairFactory = new box.homomorphic.keypair.factory.KeyFactory();
  };

  f.policies = {
    primitives: {
      secureRandom:
          {provider: box.policies.homomorphic.cipher.secureRandom.provider}
    }
  };

  cryptolib('commons', 'primitives.securerandom', 'homomorphic.keypair', f);

  /** @class */
  box.homomorphic.cipher.factory.ElGamalCipherFactory = function() {

  };

  box.homomorphic.cipher.factory.ElGamalCipherFactory.prototype = {

    /**
     * @function createEncrypter
     * @returns ElGamalEncrypter
     */
    createEncrypter: function(elGamalPublicKey, cryptoRandomInteger) {

      if (typeof cryptoRandomInteger === 'undefined') {
        cryptoRandomInteger = randomFactory.getCryptoRandomInteger();
      }

      return new ElGamalEncrypter(elGamalPublicKey, cryptoRandomInteger);
    },

    /**
     * @function createDecrypter
     * @returns ElGamalDecrypter
     */
    createDecrypter: function(elGamalPrivateKey) {
      return new ElGamalDecrypter(elGamalPrivateKey);
    },

    /**
     * @function createRandomDecrypter
     * @returns ElGamalRandomDecrypter
     */
    createRandomDecrypter: function(elGamalPublicKey, cryptoRandomInteger) {
      return new ElGamalRandomDecrypter(elGamalPublicKey, cryptoRandomInteger);
    }
  };

  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 === []) {
      throw new exceptions.CryptoLibException(
          'The given array cannot be empty');
    }
  }

  /**
   * Defines an ElGamal encrypter.
   * <P>
   * The methods specified in this object allow data to be encrypted using an
   * implementation of the ElGamal cryptosystem.
   *
   * @class ElGamalEncrypter
   * @param {ElGamalPublicKey}
   *            elGamalPublicKey The public key.
   * @param {Object}
   *            cryptoRandomInteger The source of randomness.
   * @returns {ElGamalEncrypter}
   */
  function ElGamalEncrypter(elGamalPublicKey, cryptoRandomInteger) {
    var _elGamalPublicKey = elGamalPublicKey;
    var _cryptoRandomInteger = cryptoRandomInteger;

    /**
     * @function getElGamalPublicKey
     *
     * @returns {ElGamalPublicKey}
     */
    this.getElGamalPublicKey = function() {
      return _elGamalPublicKey;
    };

    /**
     * @function getCryptoRandomInteger
     *
     * @returns {ElGamalPublicKey}
     */
    this.getCryptoRandomInteger = function() {
      return _cryptoRandomInteger;
    };

    // Private methods
    this._validateMessagesNotLargerThanKeySize = function(length) {
      if (_elGamalPublicKey.getGroupElementsArray().length < length) {
        throw new exceptions.CryptoLibException(
            'The list of messages to encrypt was larger than the number of public key elements.');
      }
    };

    this._validatePrePhisNotLargerThanKeySize = function(phis) {
      if (_elGamalPublicKey.getGroupElementsArray().length < phis.length) {
        throw new exceptions.CryptoLibException(
            'The list of prePhis was larger than the number of public key elements.');
      }
    };

    this._preCompute = function(useShortExponent) {

      var gamma;
      var prePhis = [];

      try {
        var publicKeyElements = _elGamalPublicKey.getGroupElementsArray();
        var group = _elGamalPublicKey.getGroup();

        if (useShortExponent &&
           !group.isQuadraticResidueGroup()) {
            throw new exceptions.CryptoLibException(
                'Attempt to ElGamal encrypt using short exponent for Zp subgroup that is not of type quadratic residue.');
        }

        var randomExponent = mathematical.groupUtils.generateRandomExponent(
            group, _cryptoRandomInteger, useShortExponent);

        gamma = group.getGenerator().exponentiate(randomExponent);

        // For each element in the array of public key elements, compute the
        // following: element: prephi[i] = pubKey[i]^(random)
        var pubKeyElementRaised;

        for (var i = 0; i < publicKeyElements.length; i++) {
          pubKeyElementRaised =
              publicKeyElements[i].exponentiate(randomExponent);
          prePhis.push(pubKeyElementRaised);
        }

        return new ElGamalEncrypterValues(randomExponent, gamma, prePhis);
      } catch (error) {
        throw new exceptions.CryptoLibException(
            'There was an error while precomputing values.', error);
      }
    };

    this._compute = function(messages, computationValues) {

      var compressedComputationValues = compressComputationValuesIfNecessary(
          messages.length, computationValues);

      var phis = [];

      // For each element in the array of messages, compute the following:
      // element:phi[i]=message[i]*prePhi[i]
      for (var i = 0; i < compressedComputationValues.getPhis().length; i++) {
        phis.push(
            messages[i].multiply(compressedComputationValues.getPhis()[i]));
      }

      return new box.homomorphic.cipher.ElGamalComputationValues(
          compressedComputationValues.getGamma(), phis);
    };

    this._getListAsQuadraticResidues = function(messages) {
      var valuesZpSubgroupElements = [];

      var group = _elGamalPublicKey.getGroup();
      var groupElement;

      for (var i = 0; i < messages.length; i++) {
        groupElement = new mathematical.ZpGroupElement(
            new box.forge.jsbn.BigInteger(messages[i]), group.getP(),
            group.getQ());
        valuesZpSubgroupElements.push(groupElement);
      }

      return valuesZpSubgroupElements;
    };

    function compressComputationValuesIfNecessary(
        numMessages, computationValues) {
      var phis = computationValues.getPhis();

      if (phis.length <= numMessages) {
        return computationValues;
      }

      var compressedPhiArray =
          mathematical.groupUtils.buildListWithCompressedFinalElement(
              _elGamalPublicKey.getGroup(), phis, numMessages);

      return new box.homomorphic.cipher.ElGamalComputationValues(
          computationValues.getGamma(), compressedPhiArray);
    }
  }

  ElGamalEncrypter.prototype = {

    /**
     * Encrypt the received list of messages (which are represented as
     * ZpGroupElements).
     * <p>
     * The length of the received list of messages must be equal to, or less
     * than, the length of the public key of this encrypter. If this
     * condition is not met, then an exception will be thrown.
     *
     * @function encryptGroupElements
     *
     * @param {Array}
     *            messages an array of ZpGroupElements.
     * @param {Object} [encryptionOption] an optional input parameter. If this option is of type
     *            {boolean}, then the encryption will be pre-computed, using
     *            the value of the boolean to determine whether or not to
     *            use a short random exponent for the pre-computation. If
     *            the option is of type {ElGamalEncrypterValues} then it
     *            will be used as the pre-computation of the encryption.
     *
     * @returns {ElGamalEncrypterValues}
     */
    encryptGroupElements: function(messages, encryptionOption) {

      validateArray(messages);
      this._validateMessagesNotLargerThanKeySize(messages.length);

      var useShortExponent;
      var preComputedValues;
      if (typeof encryptionOption !== 'undefined' &&
          typeof encryptionOption === 'boolean') {
          useShortExponent = encryptionOption;
      } else {
          preComputedValues = encryptionOption;
      }
      
      if (!preComputedValues) {
        preComputedValues = this._preCompute(useShortExponent);
      } else {
        var prePhis = preComputedValues.getPhis();
        validateArray(prePhis);
        this._validatePrePhisNotLargerThanKeySize(prePhis);
      }

      var computationValues = this._compute(
          messages, preComputedValues.getElGamalComputationValues());

      return new ElGamalEncrypterValues(
          preComputedValues.getR(), computationValues.getGamma(),
          computationValues.getPhis());
    },

    /**
     * Pre-compute the ElGamal encrypter values, based on the ElGamal public
     * key provided to the encrypter.
     *
     * @param {boolean}
     *            [useShortExponent] true if a short exponent is to be used
     *            for the pre-computations. Default value is false.
     * @returns {ElGamalEncrypterValues}
     */
    preCompute: function(useShortExponent) {

      return this._preCompute(useShortExponent);
    },

    /**
     * Encrypt the received list of messages (which are represented as
     * Strings).
     * <p>
     * The length of the received list of messages must be equal to, or less
     * than, the length of the public key of this encrypter. If this
     * condition is not met, then an exception will be thrown.
     *
     * @function encryptStrings
     *
     * @param {Array}
     *            messages an array of strings.
     * @param {ElGamalEncrypterValues}
     *            [preComputedValues] an optional parameter. If it is not
     *            provided, then pre-computations are made.
     *
     * @returns {ElGamalEncrypterValues} the pre-computed values.
     */
    encryptStrings: function(messages, preComputedValues) {

      var messagesAsGroupElements = this._getListAsQuadraticResidues(messages);

      if (!preComputedValues) {
        return this.encryptGroupElements(messagesAsGroupElements);
      } else {
        return this.encryptGroupElements(
            messagesAsGroupElements, preComputedValues);
      }
    }
  };

  /**
   * Defines an ElGamal decrypter.
   *
   * @class ElGamalDecrypter
   * @param {ElGamalPrivateKey}
   *            elGamalPrivateKey The ElGamal private key.
   * @returns {ElGamalDecrypter}
   */
  function ElGamalDecrypter(elGamalPrivateKey) {
    function validateCorrectGroup(elGamalPrivateKey) {
      var exponentsArray = elGamalPrivateKey.getExponentsArray();
      var group = elGamalPrivateKey.getGroup();

      for (var i = 0; i < exponentsArray.length; i++) {
        if (!(group.getQ().equals(exponentsArray[i].getQ()))) {
          throw new exceptions.CryptoLibException(
              'Each Exponent must be of the specified group order.');
        }
      }
    }

    validateCorrectGroup(elGamalPrivateKey);

    var _elGamalPrivateKey = elGamalPrivateKey;

    this.getElGamalPrivateKey = function() {
      return _elGamalPrivateKey;
    };

    this._areGroupMembers = function(cipherText) {

      for (var i = 0; i < cipherText.getPhis().length; i++) {
        var next = cipherText.getPhis()[i];
        if (!(_elGamalPrivateKey.getGroup().isGroupMember(next))) {
          return false;
        }
      }

      return true;
    };

    this._validateCiphertextSize = function(cipherText) {
      if (_elGamalPrivateKey.getExponentsArray().length <
          cipherText.getPhis().length) {
        throw new exceptions.CryptoLibException(
            'The list of ciphertext was larger than the number of private key exponents.');
      }
    };

    this._compressKeyIfNecessary = function(numRequired) {

      var exponents = _elGamalPrivateKey.getExponentsArray();
      var group = _elGamalPrivateKey.getGroup();

      if (exponents.length <= numRequired) {
        return _elGamalPrivateKey;
      }

      var listWithCompressedFinalExponent =
          mathematical.groupUtils.buildListWithCompressedFinalExponent(
              group, exponents, numRequired);

      return keyPairFactory.createPrivateKey(
          listWithCompressedFinalExponent, _elGamalPrivateKey.getGroup());
    };
  }

  ElGamalDecrypter.prototype = {

    /**
     * Decrypts a ciphertext.
     * <P>
     * The encrypted message parameter will be a list of group elements,
     * encapsulated within an ComputationValues object.
     * <P>
     * The length of the received ciphertext (number of group elements
     * contained within it) must be equal to, or less than, the length of
     * the private key of this decrypter. If this condition is not met, then
     * an exception will be thrown.
     *
     * @function decrypt
     *
     * @param {Array}
     *            cipherText the encrypted message to be decrypted.
     * @param {Boolean}
     *            [confirmGroupMembership] if true, a confirmation is made that
     * each element in
     *            {@code ciphertext} is a member of the mathematical group
     *            over which this decrypter operates. Default value is false.
     * @returns {Array} the decrypted ciphertext.
     */
    decrypt: function(cipherText, confirmGroupMembership) {

      if (confirmGroupMembership === true &&
          !this._areGroupMembers(cipherText)) {
          throw new exceptions.CryptoLibException(
              'All values to decrypt must be group elements.');
      }

      this._validateCiphertextSize(cipherText);

      var privateKeyAfterCompression =
          this._compressKeyIfNecessary(cipherText.getPhis().length);

      var plaintext = [];
      var negatedExponent;
      var exponentsArray = privateKeyAfterCompression.getExponentsArray();

      for (var i = 0; i < cipherText.getPhis().length; i++) {
        // Compute the e = negate (-) of privKey[i]
        negatedExponent = exponentsArray[i].negate();

        // Compute dm[i]= gamma^(e) * phi[i]
        plaintext.push(cipherText.getGamma()
                           .exponentiate(negatedExponent)
                           .multiply(cipherText.getPhis()[i]));
      }

      return plaintext;
    }
  };

  /**
   * Defines an ElGamal decrypter that can be used to decrypt some ciphertext,
   * given the public key and the source of randomness used to generate the
   * ciphertext.
   *
   * @class ElGamalRandomDecrypter
   * @param {ElGamalPublicKey}
   *            elGamalPublicKey The ElGamal public key.
   * @param {Object} cryptoRandomInteger The source of randomness.
   * @returns {ElGamalDecrypter} The ElGamal decrypter.
   */
  function ElGamalRandomDecrypter(elGamalPublicKey, cryptoRandomInteger) {
    function validateCorrectGroup(elGamalPublicKey) {
      var elementsArray = elGamalPublicKey.getGroupElementsArray();
      var group = elGamalPublicKey.getGroup();

      for (var i = 0; i < elementsArray.length; i++) {
        if (!(group.getP().equals(elementsArray[i].getP()))) {
          throw new exceptions.CryptoLibException(
              'Each element must be of the specified group modulus.');
        }

        if (!(group.getQ().equals(elementsArray[i].getQ()))) {
          throw new exceptions.CryptoLibException(
              'Each element must be of the specified group order.');
        }
      }
    }

    validateCorrectGroup(elGamalPublicKey);

    var _elGamalPublicKey = elGamalPublicKey;

    var _cryptoRandomInteger = cryptoRandomInteger;

    this.getElGamalPublicKey = function() {
      return _elGamalPublicKey;
    };

    this.getCryptoRandomInteger = function() {
      return _cryptoRandomInteger;
    };

    this._areGroupMembers = function(cipherText) {
      for (var i = 0; i < cipherText.getPhis().length; i++) {
        var next = cipherText.getPhis()[i];
        if (!(_elGamalPublicKey.getGroup().isGroupMember(next))) {
          return false;
        }
      }

      return true;
    };

    this._validateCiphertextSize = function(cipherText) {
      if (_elGamalPublicKey.getGroupElementsArray().length <
          cipherText.getPhis().length) {
        throw new exceptions.CryptoLibException(
            'The list of ciphertext was larger than the number of public key elements.');
      }
    };

    this._compressKeyIfNecessary = function(numRequired) {

      var publicKeyElements = _elGamalPublicKey.getGroupElementsArray();
      var group = _elGamalPublicKey.getGroup();

      if (publicKeyElements.length <= numRequired) {
        return _elGamalPublicKey;
      }

      var listWithCompressedFinalElement =
          mathematical.groupUtils.buildListWithCompressedFinalElement(
              group, publicKeyElements, numRequired);

      return keyPairFactory.createPublicKey(
          listWithCompressedFinalElement, _elGamalPublicKey.getGroup());
    };
  }

  ElGamalRandomDecrypter.prototype = {

    /**
     * Decrypts a ciphertext, using the public key and the source of randomness
     * used to generate the ciphertext. <P> The encrypted message parameter will
     * be a list of group elements, encapsulated within an ComputationValues
     * object. <P> The length of the received ciphertext (number of group
     * elements contained within it) must be equal to, or less than, the length
     * of the public key of this decrypter. If this condition is not met, then
     * an exception will be thrown.
     *
     * @function decrypt
     *
     * @param {Array}
     *            cipherText the encrypted message to be decrypted.
     * @param {Boolean}
     *            [confirmGroupMembership] if true, a confirmation is made that
     * each element in
     *            {@code ciphertext} is a member of the mathematical group
     *            over which this decrypter operates. Default value is false.
     * @param {boolean}
     *            [useShortExponent] set to true if a short exponent was used
     * for the encryption. Default value is false.
     * @returns {Array} the decrypted messages.
     */
    decrypt: function(cipherText, confirmGroupMembership, useShortExponent) {

      if (confirmGroupMembership === true &&
          !this._areGroupMembers(cipherText)) {
          throw new exceptions.CryptoLibException(
              'All values to decrypt must be group elements.');
      }

      if (typeof useShortExponent === 'undefined') {
        useShortExponent = false;
      }

      this._validateCiphertextSize(cipherText);

      var publicKeyAfterCompression =
          this._compressKeyIfNecessary(cipherText.getPhis().length);

      var group = publicKeyAfterCompression.getGroup();
      var publicKeyElements = publicKeyAfterCompression.getGroupElementsArray();
      var plaintext = [];
      var negatedExponent;

      var randomExponent = mathematical.groupUtils.generateRandomExponent(
          group, this.getCryptoRandomInteger(), useShortExponent);
      negatedExponent = randomExponent.negate();

      for (var i = 0; i < cipherText.getPhis().length; i++) {
        // Compute dm[i]= publicKeyElement^(-e) * phi[i]
        plaintext.push(publicKeyElements[i]
                           .exponentiate(negatedExponent)
                           .multiply(cipherText.getPhis()[i]));
      }

      return plaintext;
    }
  };

  /**
   * Class which encapsulates an 'r' value (random exponent) and a set of
   * ElGamal encryption values (a gamma value and a list of phi values).
   *
   * @class ElGamalEncrypterValues
   * @param {Exponent}
   *            exponent the Exponent to set.
   * @param {ZpGroupElement}
   *            gamma the gamma (first element) of the ciphertext.
   * @param {Array}
   *            phis the phi values of the ciphertext.
   * @returns {ElGamalEncrypterValues}
   */
  function ElGamalEncrypterValues(exponent, gamma, phis) {
    var _r = exponent;
    var _gamma = gamma;
    var _phis = phis;

    /**
     * @function
     *
     * @returns {Exponent}
     */
    this.getR = function() {
      return _r;
    };

    /**
     * @function
     *
     * @returns {ZpGroupElement}
     */
    this.getGamma = function() {
      return _gamma;
    };

    /**
     * @function
     *
     * @returns {Array}
     */
    this.getPhis = function() {
      return _phis;
    };

    this.getElGamalComputationValues = function() {
      return new box.homomorphic.cipher.ElGamalComputationValues(_gamma, _phis);
    };
  }

  box.homomorphic.cipher.ElGamalEncrypterValues = ElGamalEncrypterValues;

  /**
   * Encapsulates encryption parameters.
   * <p>
   * These parameters should have been generated as defined below:
   * <ul>
   * <li> For p and q:
   * http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
   * <li> For g:
   * http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
   * <li> For f:
   * http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
   * </ul>
   * <p>
   * Note that p, q, and g are received within the mathematical group.
   *
   *
   * @class EncryptionParameters
   * @param {ZpSubgroup}
   *            group the group of the encryption parameters.
   *
   * @returns {EncryptionParameters}
   */
  box.homomorphic.cipher.EncryptionParameters = function(group) {

    var _group = group;

    /**
     * @function
     *
     * @returns {ZpSubgroup}
     */
    this.getEncParamGroup = function() {
      return _group;
    };
  };

  /**
   * Class which encapsulates a gamma and a set of phi values that are Zp
   * subgroup elements.
   *
   * @class ElGamalComputationValues
   * @param {ZpGroupElement}
   *            gamma the gamma (first element) of the ciphertext.
   * @param {Array}
   *            phis the phi values of the ciphertext.
   */
  box.homomorphic.cipher.ElGamalComputationValues = function(gamma, phis) {
    this._gamma = gamma;
    this._phis = phis;
  };

  box.homomorphic.cipher.ElGamalComputationValues.prototype = {

    getGamma: function() {
      return this._gamma;
    },

    getPhis: function() {
      return this._phis;
    },

    stringify: function() {
      var phis = Array();

      for (var i = 0; i < this._phis.length; i++) {
        phis[i] =
            converters.base64FromBigInteger(this._phis[i].getElementValue());
      }

      return JSON.stringify({
        ciphertext: {
          p: converters.base64FromBigInteger(this._gamma.getP()),
          q: converters.base64FromBigInteger(this._gamma.getQ()),
          gamma: converters.base64FromBigInteger(this._gamma.getElementValue()),
          phis: phis
        }
      });
    }
  };

  box.homomorphic.cipher.deserializeElGamalComputationValues = function(
      serializedObject) {

    var valuesJson = JSON.parse(serializedObject).ciphertext;

    var p = converters.base64ToBigInteger(valuesJson.p);
    var q = converters.base64ToBigInteger(valuesJson.q);

    var gamma = new mathematical.ZpGroupElement(
        converters.base64ToBigInteger(valuesJson.gamma), p, q);

    var phis = [];
    for (var i = 0; i < valuesJson.phis.length; i++) {
      phis.push(new mathematical.ZpGroupElement(
          converters.base64ToBigInteger(valuesJson.phis[i]), p, q));
    }

    return new box.homomorphic.cipher.ElGamalComputationValues(gamma, phis);
  };
};