el_gamal.cpp

Go to the documentation of this file.

/*
SeComLib
Copyright 2012-2013 TU Delft, Information Security & Privacy Lab (http://isplab.tudelft.nl/)

Contributors:
Inald Lagendijk (R.L.Lagendijk@TUDelft.nl)
Mihai Todor (todormihai@gmail.com)
Thijs Veugen (P.J.M.Veugen@tudelft.nl)
Zekeriya Erkin (z.erkin@tudelft.nl)

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
#include "el_gamal.h"

namespace SeComLib {
namespace Core {
    ElGamalRandomizer::ElGamalRandomizer () {
    }

    ElGamalRandomizer::ElGamalRandomizer (const BigInteger &x, const BigInteger &y) : x(x), y(y) {
    }

    ElGamal::ElGamal (const bool precomputeDecryptionMap) : CryptoProvider<ElGamalPublicKey, ElGamalPrivateKey, ElGamalCiphertext, ElGamalRandomizer>(Utils::Config::GetInstance().GetParameter("Core.ElGamal.keySize", 1024)),
        messageSpaceThreshold(BigInteger(2).Pow(Utils::Config::GetInstance().GetParameter<unsigned long>("Core.ElGamal.messageSpaceThresholdBitSize"))),
        precomputeDecryptionMap(precomputeDecryptionMap) {
    }

    ElGamal::ElGamal (const ElGamalPublicKey &publicKey) : CryptoProvider<ElGamalPublicKey, ElGamalPrivateKey, ElGamalCiphertext, ElGamalRandomizer>(publicKey, Utils::Config::GetInstance().GetParameter("Core.ElGamal.keySize", 1024)),
        messageSpaceThreshold(BigInteger(2).Pow(Utils::Config::GetInstance().GetParameter<unsigned long>("Core.ElGamal.messageSpaceThresholdBitSize"))) {
        //C++ doesn't allow us to call a virtual method in the constructor of the base class
        this->doPrecomputations();
    }

    ElGamal::ElGamal (const ElGamalPublicKey &publicKey, const ElGamalPrivateKey &privateKey, const bool precomputeDecryptionMap) : CryptoProvider<ElGamalPublicKey, ElGamalPrivateKey, ElGamalCiphertext, ElGamalRandomizer>(publicKey, privateKey, Utils::Config::GetInstance().GetParameter("Core.ElGamal.keySize", 1024)),
        messageSpaceThreshold(BigInteger(2).Pow(Utils::Config::GetInstance().GetParameter<unsigned long>("Core.ElGamal.messageSpaceThresholdBitSize"))),
        precomputeDecryptionMap(precomputeDecryptionMap) {
        //C++ doesn't allow us to call a virtual method in the constructor of the base class
        this->doPrecomputations();
    }

    bool ElGamal::GenerateKeys () {
        unsigned int largePrimeFactorSize = Utils::Config::GetInstance().GetParameter("Core.ElGamal.largePrimeFactorSize", 160);

        if (largePrimeFactorSize >= this->keyLength) {
            throw std::runtime_error("Please choose a smaller prime factor size.");
        }


        BigInteger r, m, n;
        unsigned int sizeR = this->keyLength - largePrimeFactorSize;
        unsigned int sizeMN = (sizeR - 1) / 2;
        do {
            //pick a random prime @f$ q @f$ of size specified by largePrimeFactorSize
            this->publicKey.q = RandomProvider::GetInstance().GetMaxLengthRandomPrime(largePrimeFactorSize);

            //generate two random primes in the interval (0, 2^((sizeR - 1) / 2))
            m = RandomProvider::GetInstance().GetMaxLengthRandomPrime(sizeMN);
            n = RandomProvider::GetInstance().GetMaxLengthRandomPrime(sizeMN);

            //compute r
            r = m * n * 2;

            //q and r must divide p - 1
            this->publicKey.p = this->publicKey.q * r + 1;
        }
        while (!this->publicKey.p.IsPrime());

        do {
            //generate random g in the interval [0, p)
            this->g = RandomProvider::GetInstance().GetRandomInteger(this->publicKey.p);
        }
        //ensure that g is a generator of Z_{p}^*
        while (BigInteger::Gcd(this->g, this->publicKey.p) != 1 ||
                this->g.GetPowModN(this->publicKey.q * m * n, this->publicKey.p) == 1 ||
                this->g.GetPowModN(this->publicKey.q * m * 2, this->publicKey.p) == 1 ||
                this->g.GetPowModN(this->publicKey.q * n * 2, this->publicKey.p) == 1 ||
                this->g.GetPowModN(m * n * 2, this->publicKey.p) == 1);

        this->publicKey.gq = this->g.GetPowModN(r, this->publicKey.p);

        do {
            this->privateKey.s = RandomProvider::GetInstance().GetRandomInteger(this->publicKey.q);
        }
        //s must be != 0
        while (this->privateKey.s == 0);

        this->publicKey.h = this->publicKey.gq.GetPowModN(this->privateKey.s, this->publicKey.p);

        //precompute values for optimization purposes
        this->doPrecomputations();

        return true;
    }

    BigInteger ElGamal::DecryptInteger (const ElGamal::Ciphertext &ciphertext) const {
        if (!this->hasPrivateKey) {
            throw std::runtime_error("This operation requires the private key.");
        }

        if (!this->precomputeDecryptionMap) {
            throw std::runtime_error("This operation requires the decryption map.");
        }

        BigInteger cyCxPowMinusSModP = (ciphertext.data.y * ciphertext.data.x.GetPowModN(-this->privateKey.s, this->publicKey.p)) % this->publicKey.p;

        if (cyCxPowMinusSModP == 1) {
            return 0;
        }

        BigInteger output;

        //get an iterator to the required element
        DecryptionMap::const_iterator iterator = this->decryptionMap.find(cyCxPowMinusSModP);

        //make sure the key exists
        if (this->decryptionMap.end() != iterator) {
            output = BigInteger(iterator->second);
        }
        else {
            throw std::runtime_error("Can't decrypt ciphertext.");
        }

        if (output > this->positiveNegativeBoundary) {
            output -= this->GetMessageSpaceUpperBound();
        }
        
        return output;
    }

    ElGamal::Ciphertext ElGamal::EncryptIntegerNonrandom (const BigInteger &plaintext) const {
        ElGamal::Ciphertext output(this->encryptionModulus);


        output.data.x = 1;
        if (plaintext < 0) {
            output.data.y = this->publicKey.gq.GetPowModN(this->GetMessageSpaceUpperBound() + plaintext, this->publicKey.p);
        }
        else {
            output.data.y = this->publicKey.gq.GetPowModN(plaintext, this->publicKey.p);
        }

        return output;
    }

    ElGamal::Randomizer ElGamal::GetRandomizer () const {
        BigInteger random = RandomProvider::GetInstance().GetRandomInteger(this->publicKey.q);

        return Randomizer(this->publicKey.gq.GetPowModN(random, this->publicKey.p), this->publicKey.h.GetPowModN(random, this->publicKey.p));
    }

    ElGamal::Ciphertext ElGamal::RandomizeCiphertext (const ElGamal::Ciphertext &ciphertext) const {
        //assign a randomizer to the output
        Randomizer randomizer = this->randomizerCache->Pop().randomizer;
        Ciphertext output(this->encryptionModulus);

        //compose the output with the ciphertext
        output.data.x = ciphertext.data.x * randomizer.x % this->GetEncryptionModulus();
        output.data.y = ciphertext.data.y * randomizer.y % this->GetEncryptionModulus();
        
        return output;
    }

#ifdef ENABLE_CRYPTO_PROVIDER_HOMOMORPHIC_OPERATIONS

    ElGamal::Ciphertext ElGamal::HomomorphicAdd (const ElGamal::Ciphertext &lhs, const ElGamal::Ciphertext &rhs) const {
        ElGamal::Ciphertext output;

        output.x = (lhs.x * rhs.x) % this->GetEncryptionModulus();
        output.y = (lhs.y * rhs.y) % this->GetEncryptionModulus();

        return output;
    }

    ElGamal::Ciphertext ElGamal::GetHomomorphicInverse (const ElGamal::Ciphertext &input) const {
        ElGamal::Ciphertext output;

        output.x = input.x.GetInverseModN(this->GetEncryptionModulus());
        output.y = input.y.GetInverseModN(this->GetEncryptionModulus());

        return output;
    }

    ElGamal::Ciphertext ElGamal::HomomorphicSubtract (const ElGamal::Ciphertext &lhs, const ElGamal::Ciphertext &rhs) const {
        ElGamal::Ciphertext output;

        output.x = (lhs.x * rhs.x.GetInverseModN(this->GetEncryptionModulus())) % this->GetEncryptionModulus();
        output.y = (lhs.y * rhs.y.GetInverseModN(this->GetEncryptionModulus())) % this->GetEncryptionModulus();

        return output;
    }

    ElGamal::Ciphertext ElGamal::HomomorphicMultiply (const ElGamal::Ciphertext &lhs, const BigInteger &rhs) const {
        if (rhs == 0) {
            throw std::runtime_error("The plaintext term should not be 0.");
        }

        ElGamal::Ciphertext output = lhs;

        output.x = output.x.GetPowModN(rhs, this->GetEncryptionModulus());
        output.y = output.y.GetPowModN(rhs, this->GetEncryptionModulus());

        return output;
    }
#endif

    const BigInteger &ElGamal::GetMessageSpaceUpperBound () const {
        return this->publicKey.q;
    }

    size_t ElGamal::GetMessageSpaceSize () const {
        return this->publicKey.q.GetSize();
    }

    bool ElGamal::IsEncryptedZero (const Ciphertext &ciphertext) const {
        if (!this->hasPrivateKey) {
            throw std::runtime_error("This operation requires the private key.");
        }

        BigInteger test = (ciphertext.data.y * ciphertext.data.x.GetPowModN(-this->privateKey.s, this->publicKey.p)) % this->publicKey.p;

        return test == 1 ? true : false;
    }

    void ElGamal::doPrecomputations () {
        if (this->hasPrivateKey) {
            if (this->precomputeDecryptionMap) {
                //we handle the first part (for m >= 0)
                for (BigInteger i = 0; i < this->messageSpaceThreshold; ++i) {
                    this->decryptionMap[this->publicKey.gq.GetPowModN(i, this->publicKey.p)] = i;
                }
                //and the second part (for m < 0) - we do one less iteration here, because size(positives \ {0}) = size(negatives)
                for (BigInteger i = this->publicKey.q - this->messageSpaceThreshold + 1; i < this->publicKey.q; ++i) {
                    this->decryptionMap[this->publicKey.gq.GetPowModN(i, this->publicKey.p)] = i;
                }
            }
        }
        
        //set the encryption modulus, @f$ p @f$
        this->encryptionModulus = std::make_shared<BigInteger>(this->publicKey.p);

        this->positiveNegativeBoundary = this->messageSpaceThreshold;
        
        this->randomizerCache = std::unique_ptr<RandomizerCacheType>(new RandomizerCacheType(*this, "Core.RandomizerCache"));

        this->encryptedZero = this->EncryptInteger(BigInteger(0));

        this->encryptedOne = this->EncryptInteger(BigInteger(1));
    }

}//namespace Core
}//namespace SeComLib