dgk.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 "dgk.h"

namespace SeComLib {
namespace Core {
    DgkCiphertext::DgkCiphertext () :
        CiphertextBase<DgkCiphertext> () {
    }

    DgkCiphertext::DgkCiphertext (const std::shared_ptr<BigInteger> &encryptionModulus) :
        CiphertextBase<DgkCiphertext> (encryptionModulus) {
    }

    DgkCiphertext::DgkCiphertext (const BigInteger &data, const std::shared_ptr<BigInteger> &encryptionModulus) :
        CiphertextBase<DgkCiphertext> (data, encryptionModulus) {
    }

    DgkRandomizer::DgkRandomizer () : RandomizerBase() {
    }

    DgkRandomizer::DgkRandomizer (const BigInteger &data) : RandomizerBase(data) {
    }

    Dgk::Dgk (const bool precomputeDecryptionMap) : CryptoProvider<DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer>(Utils::Config::GetInstance().GetParameter("Core.Dgk.k", 1024)),
        t(Utils::Config::GetInstance().GetParameter("Core.Dgk.t", 160)),
        l(Utils::Config::GetInstance().GetParameter("Core.Dgk.l", 16)),
        precomputeDecryptionMap(precomputeDecryptionMap) {
        this->validateParameters();
    }

    Dgk::Dgk (const DgkPublicKey &publicKey) : CryptoProvider<DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer>(publicKey, Utils::Config::GetInstance().GetParameter("Core.Dgk.k", 1024)),
        t(Utils::Config::GetInstance().GetParameter("Core.Dgk.t", 160)),
        l(Utils::Config::GetInstance().GetParameter("Core.Dgk.l", 16)) {
        this->validateParameters();

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

    Dgk::Dgk (const DgkPublicKey &publicKey, const DgkPrivateKey &privateKey, const bool precomputeDecryptionMap) : CryptoProvider<DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer>(publicKey, privateKey, Utils::Config::GetInstance().GetParameter("Core.Dgk.k", 1024)),
        t(Utils::Config::GetInstance().GetParameter("Core.Dgk.t", 160)),
        l(Utils::Config::GetInstance().GetParameter("Core.Dgk.l", 16)),
        precomputeDecryptionMap(precomputeDecryptionMap) {
        this->validateParameters();

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

    bool Dgk::GenerateKeys() {
        this->publicKey.u = BigInteger(2).GetPow(this->l + 2).GetNextPrime();

        //std::cout << "Message space: " << this->publicKey.u.ToString(10).c_str() << std::endl;

        this->privateKey.vp = RandomProvider::GetInstance().GetMaxLengthRandomPrime(this->t);
        do {
            this->privateKey.vq = RandomProvider::GetInstance().GetMaxLengthRandomPrime(this->t);
        }
        while (this->privateKey.vq == this->privateKey.vp);

        BigInteger pRand, qRand;
        BigInteger aux;
        size_t sizeRand;

        //precompute 2 * u * vp
        aux = BigInteger(2) * this->publicKey.u * this->privateKey.vp;
        //compute the required length of the random part of p
        sizeRand = this->keyLength / 2 - aux.GetSize();

        if (0 == sizeRand) {
            throw std::runtime_error("Parameter k is too small.");
        }

        do {
            //generate a prime number in the interval [0, 2^sizeRand)
            pRand = RandomProvider::GetInstance().GetMaxLengthRandomPrime(sizeRand);

            //p = pRand * 2 * u * vp + 1
            this->privateKey.p = pRand * aux + 1;
        }
        while (!this->privateKey.p.IsPrime());

        //precompute 2 * u * vq
        aux = BigInteger(2) * this->publicKey.u * this->privateKey.vq;

        sizeRand = this->keyLength / 2 - aux.GetSize();

        if (0 == sizeRand) {
            throw std::runtime_error("Parameter k is too small.");
        }

        do {
            //generate a prime number in the interval [0, 2^sizeRand)
            qRand = RandomProvider::GetInstance().GetMaxLengthRandomPrime(sizeRand);
            
            //q = qRand * 2 * u * vq + 1
            this->privateKey.q = qRand * aux + 1;
        }
        while (!this->privateKey.q.IsPrime());

        this->publicKey.n = this->privateKey.p * this->privateKey.q;
        

        BigInteger hRandP;
        do {
            //generate a random number in the interval [0, p)
            hRandP = RandomProvider::GetInstance().GetRandomInteger(this->privateKey.p);
        }
        //this loop can be optimized by precomputing the partial products
        while (hRandP == 1 ||
                BigInteger::Gcd(hRandP, this->privateKey.p) != 1 ||
                hRandP.GetPowModN(this->privateKey.vp * this->publicKey.u * 2, this->privateKey.p) == 1 ||
                hRandP.GetPowModN(pRand * this->publicKey.u * 2, this->privateKey.p) == 1 ||
                hRandP.GetPowModN(pRand * this->privateKey.vp * 2, this->privateKey.p) == 1 ||
                hRandP.GetPowModN(pRand * this->privateKey.vp * this->publicKey.u, this->privateKey.p) == 1);

        BigInteger hRandQ;
        do {
            //generate a random number in the interval [0, q)
            hRandQ = RandomProvider::GetInstance().GetRandomInteger(this->privateKey.q);
        }
        //this loop can be optimized by precomputing the partial products
        while (hRandQ == 1 ||
                BigInteger::Gcd(hRandQ, this->privateKey.q) != 1 ||
                hRandQ.GetPowModN(this->privateKey.vq * this->publicKey.u * 2, this->privateKey.q) == 1 ||
                hRandQ.GetPowModN(qRand * this->publicKey.u * 2, this->privateKey.q) == 1 ||
                hRandQ.GetPowModN(qRand * this->privateKey.vq * 2, this->privateKey.q) == 1 ||
                hRandQ.GetPowModN(qRand * this->privateKey.vq * this->publicKey.u, this->privateKey.q) == 1);

        //construct hRand with the Chinese Remainder Theorem
        BigInteger hRand = (hRandP * this->privateKey.q * this->privateKey.q.GetInverseModN(this->privateKey.p) + hRandQ * this->privateKey.p * this->privateKey.p.GetInverseModN(this->privateKey.q)) % this->publicKey.n;

        this->publicKey.h = hRand.GetPowModN(BigInteger(2) * this->publicKey.u * pRand * qRand, this->publicKey.n);

        BigInteger gRandP;
        do {
            //generate a random number in the interval [0, p)
            gRandP = RandomProvider::GetInstance().GetRandomInteger(this->privateKey.p);
            
        }
        //this loop can be optimized by precomputing the partial products
        while (gRandP == 1 ||
                BigInteger::Gcd(gRandP, this->privateKey.p) != 1 ||
                gRandP.GetPowModN(this->privateKey.vp * this->publicKey.u * 2, this->privateKey.p) == 1 ||
                gRandP.GetPowModN(pRand * this->publicKey.u * 2, this->privateKey.p) == 1 ||
                gRandP.GetPowModN(pRand * this->privateKey.vp * 2, this->privateKey.p) == 1 ||
                gRandP.GetPowModN(pRand * this->privateKey.vp * this->publicKey.u, this->privateKey.p) == 1);
        
        BigInteger gRandQ;
        do {
            //generate a random number in the interval [0, q)
            gRandQ = RandomProvider::GetInstance().GetRandomInteger(this->privateKey.q);
            
        }
        //this loop can be optimized by precomputing the partial products
        while (gRandQ == 1 ||
                BigInteger::Gcd(gRandQ, this->privateKey.q) != 1 ||
                gRandQ.GetPowModN(this->privateKey.vq * this->publicKey.u * 2, this->privateKey.q) == 1 ||
                gRandQ.GetPowModN(qRand * this->publicKey.u * 2, this->privateKey.q) == 1 ||
                gRandQ.GetPowModN(qRand * this->privateKey.vq * 2, this->privateKey.q) == 1 ||
                gRandQ.GetPowModN(qRand * this->privateKey.vq * this->publicKey.u, this->privateKey.q) == 1);

        //construct gRand with the Chinese Remainder Theorem
        BigInteger gRand = (gRandP * this->privateKey.q * this->privateKey.q.GetInverseModN(this->privateKey.p) + gRandQ * this->privateKey.p * this->privateKey.p.GetInverseModN(this->privateKey.q)) % this->publicKey.n;

        this->publicKey.g = gRand.GetPowModN(pRand * qRand * 2, this->publicKey.n);

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

        return true;
    }

    BigInteger Dgk::DecryptInteger (const Dgk::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 cPowVpModP = ciphertext.data.GetPowModN(this->privateKey.vp, this->privateKey.p);

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

        BigInteger output;

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

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

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

        return output;
    }

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



        if (!this->hasPrivateKey) {
            if (plaintext < 0) {
                output.data = this->publicKey.g.GetPowModN(this->GetMessageSpaceUpperBound() + plaintext, this->publicKey.n);
            }
            else {
                output.data = this->publicKey.g.GetPowModN(plaintext, this->publicKey.n);
            }
        }
        else {
            if (plaintext < 0) {
                output.data = (this->publicKey.g.GetPowModN(this->GetMessageSpaceUpperBound() + plaintext, this->privateKey.p) * this->qTimesQInvModP + this->publicKey.g.GetPowModN(this->GetMessageSpaceUpperBound() + plaintext, this->privateKey.q) * this->pTimesPInvModQ) % this->publicKey.n;
            }
            else {
                output.data = (this->publicKey.g.GetPowModN(plaintext, this->privateKey.p) * this->qTimesQInvModP + this->publicKey.g.GetPowModN(plaintext, this->privateKey.q) * this->pTimesPInvModQ) % this->publicKey.n;
            }
        }

        return output;
    }

    Dgk::Randomizer Dgk::GetRandomizer () const {
        /*
        Notes from the paper:

        A final word on performance of encryption: if we want to make sure
        that h^r mod n is uniform in the group generated by h, we should choose
        r somewhat longer than 2t bits, say of length 2.5t bits - since in the cor-
        rected system, the order of h is 2t bits long. This will cause the encryption
        to take about 25% more time compared to the original system. However, if
        one is willing to make the additional assumption that raising h to a 2t-bit
        exponent produces an element that is computationally indistinguishable
        from uniform in H, then one can keep the original encryption algorithm
        and this means that using the corrected system in the protocols from
        [1, 2] will produce exactly the same performance as reported there.
        */

        BigInteger random = RandomProvider::GetInstance().GetRandomInteger(2 * this->t);

        if (!this->hasPrivateKey) {
            return Randomizer(this->publicKey.h.GetPowModN(random, this->publicKey.n));
        }
        else {
            return Randomizer((this->publicKey.h.GetPowModN(random, this->privateKey.p) * this->qTimesQInvModP + this->publicKey.h.GetPowModN(random, this->privateKey.q) * this->pTimesPInvModQ) % this->publicKey.n);
        }
    }

    Dgk::Ciphertext Dgk::RandomizeCiphertext (const Dgk::Ciphertext &ciphertext) const {
        return Ciphertext((ciphertext.data * this->randomizerCache->Pop().randomizer.data) % this->GetEncryptionModulus(), this->encryptionModulus);
    }

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

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

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

        BigInteger test = ciphertext.data.GetPowModN(this->privateKey.vp, this->privateKey.p);

        return test == 1 ? true : false;
    }

    void Dgk::validateParameters () {
        /* See here https://www.cryptool.org/trac/CrypTool2/browser/trunk/CrypPlugins/DGK/DGKKeyGenerator.cs for the original source of parameter validation */
        if (this->l < 8 || this->l > 32) {
            throw std::runtime_error("The l parameter must obey the following constraints: 8 <= l <= 32.");
        }
        if (this->t <= this->l) {
            throw std::runtime_error("Parameter t must be greater than l.");
        }
        if (this->keyLength <= this->t) {
            throw std::runtime_error("Parameter k must be greater than t.");
        }

        if (this->keyLength % 2 != 0) {
            throw std::runtime_error("The k parameter must be even.");
        }
        /* These need to be revised...
        if (!((this->keyLength / 2 > (this->l + 4)) && (this->keyLength / 2 > (this->t + 1)))) {
            throw std::runtime_error("The k parameter must obey the following constraints: k / 2 > l + 4 and k / 2 > t + 1.");
        }
        */
        if (this->keyLength / 2 < this->l + this->t + 10) {
            throw std::runtime_error("Choose parameters k, l, t such that k / 2 >= l + t + 10.");
        }
    }

    void Dgk::doPrecomputations () {
        if (this->hasPrivateKey) {
            if (this->precomputeDecryptionMap) {
                for (BigInteger i = 0; i < this->publicKey.u; ++i) {
                    this->decryptionMap[this->publicKey.g.GetPowModN(this->privateKey.vp * i, this->privateKey.p)] = i;
                }
            }

            try {
                this->pTimesPInvModQ = this->privateKey.p * this->privateKey.p.GetInverseModN(this->privateKey.q);
                this->qTimesQInvModP = this->privateKey.q * this->privateKey.q.GetInverseModN(this->privateKey.p);
            }
            catch (std::runtime_error) {
                //if gcd(p, q) != 1, throw an error
                throw std::runtime_error("p and q are not coprime.");
            }
        }

        //set the encryption modulus, @f$ n @f$
        this->encryptionModulus = std::make_shared<BigInteger>(this->publicKey.n);

        //precompute the limit between positive and negative values in the message space
        this->positiveNegativeBoundary = this->GetMessageSpaceUpperBound() / 2;
        
        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