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

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

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

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

    PaillierRandomizer::PaillierRandomizer () : RandomizerBase() {
    }

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

    Paillier::Paillier () : CryptoProvider<PaillierPublicKey, PaillierPrivateKey, PaillierCiphertext, PaillierRandomizer>(Utils::Config::GetInstance().GetParameter("Core.Paillier.keySize", 1024)) {
    }

    Paillier::Paillier (const PaillierPublicKey &publicKey) : CryptoProvider<PaillierPublicKey, PaillierPrivateKey, PaillierCiphertext, PaillierRandomizer>(publicKey, Utils::Config::GetInstance().GetParameter("Core.Paillier.keySize", 1024)) {
        //C++ doesn't allow us to call a virtual method in the constructor of the base class
        this->doPrecomputations();
    }

    Paillier::Paillier (const PaillierPublicKey &publicKey, const PaillierPrivateKey &privateKey) :
        CryptoProvider<PaillierPublicKey, PaillierPrivateKey, PaillierCiphertext, PaillierRandomizer>(publicKey, privateKey, Utils::Config::GetInstance().GetParameter("Core.Paillier.keySize", 1024)) {
        //C++ doesn't allow us to call a virtual method in the constructor of the base class
        this->doPrecomputations();
    }

    bool Paillier::GenerateKeys () {
        unsigned int primeLength = (unsigned int)(this->keyLength / 2);

        do {
            this->privateKey.p = RandomProvider::GetInstance().GetMaxLengthRandomPrime(primeLength);
            this->privateKey.q = RandomProvider::GetInstance().GetMaxLengthRandomPrime(primeLength);

            //std::cout << this->privateKey.p.GetSize() << std::endl;
            //std::cout << this->privateKey.q.GetSize() << std::endl;
    
            while (this->privateKey.p == this->privateKey.q) {
                this->privateKey.p = RandomProvider::GetInstance().GetMaxLengthRandomPrime(primeLength);
            }

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

            this->nMinusOne = this->publicKey.n - 1;
            this->nSquared = this->publicKey.n.GetPow(2);

            //std::cout << this->n.GetSize() << std::endl;
        }
        while (this->publicKey.n.GetSize() != this->keyLength);

        //std::cout << this->publicKey.n.GetSize() << std::endl;

    #ifdef USE_STANDARD_PAILLIER_ALGORITHM
        
        this->privateKey.lambda = BigInteger::Lcm(this->privateKey.p - 1, this->privateKey.q - 1);

        this->publicKey.g = RandomProvider::GetInstance().GetRandomInteger(this->keyLength * this->keyLength);

        this->privateKey.mu = this->L(this->publicKey.g.GetPowModN(this->privateKey.lambda, this->nSquared), this->publicKey.n).InvertModN(this->publicKey.n);

    #else

        this->publicKey.g = this->publicKey.n + 1;

        /*
        BigInteger phi = (this->privateKey.p - 1) * (this->privateKey.q - 1);
        this->privateKey.lambda = phi;
        this->privateKey.mu = phi.InvertModN(this->publicKey.n);
        */

    #endif

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

        return true;
    }

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

    #ifdef USE_STANDARD_PAILLIER_ALGORITHM
        BigInteger output = (this->L(ciphertext.data.GetPowModN(this->privateKey.lambda, this->nSquared), this->publicKey.n) * this->privateKey.mu) % this->publicKey.n;
    #else

        BigInteger mp = (this->L(ciphertext.data.GetPowModN(this->pMinusOne, this->pSquared), this->privateKey.p) * this->hp) % this->privateKey.p;
        BigInteger mq = (this->L(ciphertext.data.GetPowModN(this->qMinusOne, this->qSquared), this->privateKey.q) * this->hq) % this->privateKey.q;
        BigInteger output = (mp * this->qTimesQInvModP + mq * this->pTimesPInvModQ) % this->publicKey.n;
    #endif

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

        return output;
    }

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


    #ifdef USE_STANDARD_PAILLIER_ALGORITHM

        //compute c = g^m (mod n^2)
        if (plaintext < 0) {
            output.data = this->publicKey.g.GetPowModN(this->GetMessageSpaceUpperBound() + plaintext, this->nSquared);
        }
        else {
            output.data = this->publicKey.g.GetPowModN(plaintext, this->nSquared);
        }
    #else

        //compute c = n * m + 1 (we skip the modulo operation, since it's done in RandomizeCiphertext)
        if (plaintext < 0) {
            output.data = this->publicKey.n * (this->GetMessageSpaceUpperBound() + plaintext) + 1;
        }
        else {
            output.data = this->publicKey.n * plaintext + 1;
        }
    #endif

        return output;
    }

    Paillier::Randomizer Paillier::GetRandomizer () const {
        return Randomizer((RandomProvider::GetInstance().GetRandomInteger(this->nMinusOne) + 1).GetPowModN(this->publicKey.n, this->nSquared));
    }

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

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

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

    BigInteger Paillier::L (const BigInteger &input, const BigInteger &d) const {
        BigInteger output;

        output = (input - 1) / d;

        return output;
    }

    void Paillier::doPrecomputations () {
        if (this->precomputeSpeedupValues) {
            this->nSquared = this->publicKey.n.GetPow(2);
            this->nMinusOne = this->publicKey.n - 1;
        }

        if (this->hasPrivateKey) {
            this->pMinusOne = this->privateKey.p - 1;
            this->qMinusOne = this->privateKey.q - 1;
            this->pSquared = this->privateKey.p * this->privateKey.p;
            this->qSquared = this->privateKey.q * this->privateKey.q;
            this->hp = this->L(this->publicKey.g.GetPowModN(this->pMinusOne, this->pSquared), this->privateKey.p).InvertModN(this->privateKey.p);
            this->hq = this->L(this->publicKey.g.GetPowModN(this->qMinusOne, this->qSquared), this->privateKey.q).InvertModN(this->privateKey.q);

            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^2 @f$
        this->encryptionModulus = std::make_shared<BigInteger>(this->nSquared);

        //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