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

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

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

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

    OkamotoUchiyamaRandomizer::OkamotoUchiyamaRandomizer () : RandomizerBase() {
    }

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

    OkamotoUchiyama::OkamotoUchiyama () :
        CryptoProvider<OkamotoUchiyamaPublicKey, OkamotoUchiyamaPrivateKey, OkamotoUchiyamaCiphertext, OkamotoUchiyamaRandomizer>(Utils::Config::GetInstance().GetParameter("Core.OkamotoUchiyama.keySize", 1024)),
        messageSpaceSize(Utils::Config::GetInstance().GetParameter<size_t>("Core.OkamotoUchiyama.messageSpaceSize")) {
    }

    OkamotoUchiyama::OkamotoUchiyama (const OkamotoUchiyamaPublicKey &publicKey) :
        CryptoProvider<OkamotoUchiyamaPublicKey, OkamotoUchiyamaPrivateKey, OkamotoUchiyamaCiphertext, OkamotoUchiyamaRandomizer>(publicKey, Utils::Config::GetInstance().GetParameter("Core.OkamotoUchiyama.keySize", 1024)),
        messageSpaceSize(Utils::Config::GetInstance().GetParameter<size_t>("Core.OkamotoUchiyama.messageSpaceSize")) {
        //precompute values for optimization purposes
        this->doPrecomputations();
    }

    OkamotoUchiyama::OkamotoUchiyama (const OkamotoUchiyamaPublicKey &publicKey, const OkamotoUchiyamaPrivateKey &privateKey) :
        CryptoProvider<OkamotoUchiyamaPublicKey, OkamotoUchiyamaPrivateKey, OkamotoUchiyamaCiphertext, OkamotoUchiyamaRandomizer>(publicKey, privateKey, Utils::Config::GetInstance().GetParameter("Core.OkamotoUchiyama.keySize", 1024)),
        messageSpaceSize(Utils::Config::GetInstance().GetParameter<size_t>("Core.OkamotoUchiyama.messageSpaceSize")) {
        //precompute values for optimization purposes
        this->doPrecomputations();
    }

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

        unsigned int primeLength = static_cast<unsigned int>(this->keyLength / 3);
        if (sizeT >= primeLength) {
            throw std::runtime_error("Key size must be larger than the t parameter.");
        }


        //pick a random prime t of size specified by sizeT
        this->privateKey.t = RandomProvider::GetInstance().GetMaxLengthRandomPrime(sizeT);

        BigInteger u;
        unsigned int sizeU = primeLength - sizeT;
        do {
            //generate a random number in the interval [0, 2^(sizeU - 1))
            u = RandomProvider::GetInstance().GetRandomInteger(sizeU - 1);

            //shift number to the interval [2^(sizeU - 1), 2^sizeU)
            u.SetBit(sizeU - 1);

            //u and t must divide p - 1
            this->privateKey.p = this->privateKey.t * u + 1;
        }
        while (!this->privateKey.p.IsPrime());

        //precompute p^2 and store it for the decryption operation
        this->pSquared = this->privateKey.p.GetPow(2);

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

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

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

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

            //gp = g^(p - 1) (mod p^2)
            this->privateKey.gp = this->g.GetPowModN(this->privateKey.p - 1, this->pSquared);
        }
        //ensure that gp^p = 1 (mod p^2)
        while (this->privateKey.gp.GetPowModN(this->privateKey.p, this->pSquared) != 1);

        this->publicKey.G = this->g.GetPowModN(u, this->publicKey.n);

        BigInteger gPrime;

        do {
            //generate random g' in the interval [0, n)
            gPrime = RandomProvider::GetInstance().GetRandomInteger(this->publicKey.n);
        }
        //ensure that g' is in the cyclic group Z_n*
        while (BigInteger::Gcd(gPrime, this->publicKey.n) != 1);

        //H = g'^(n * u) (mod n)
        this->publicKey.H = gPrime.GetPowModN(this->publicKey.n * u, this->publicKey.n);

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

        return true;
    }

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

        BigInteger output = (this->L(ciphertext.data.GetPowModN(this->privateKey.t, this->pSquared)) * this->lgpInv) % this->privateKey.p;

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

        return output;
    }

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


        if (plaintext < 0) {
            if (this->hasPrivateKey) {
                output.data = this->publicKey.G.GetPowModN(this->GetMessageSpaceUpperBound() + plaintext, this->GetEncryptionModulus());
            }
            else {
                output.data = this->publicKey.G.GetPowModN(plaintext.GetAbs(), this->GetEncryptionModulus()).GetInverseModN(this->GetEncryptionModulus());
            }
        }
        else {
            output.data = this->publicKey.G.GetPowModN(plaintext, this->GetEncryptionModulus());
        }

        return output;
    }

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

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

    const BigInteger &OkamotoUchiyama::GetMessageSpaceUpperBound () const {
        return this->messageSpace;
    }

    size_t OkamotoUchiyama::GetMessageSpaceSize () const {
        return this->messageSpaceSize;
    }

    BigInteger OkamotoUchiyama::L (const BigInteger &input) const {
        BigInteger output;

        output = (input - 1) / this->privateKey.p;

        return output;
    }

    void OkamotoUchiyama::doPrecomputations () {
        if (this->precomputeSpeedupValues) {
            this->pSquared = this->privateKey.p.GetPow(2);
        }

        if (this->hasPrivateKey) {
            this->messageSpace = this->privateKey.p;
            this->messageSpaceSize = this->privateKey.p.GetSize();

            this->lgpInv = this->L(this->privateKey.gp).GetInverseModN(this->privateKey.p);
        }
        else {
            this->messageSpace = BigInteger(2).GetPow(static_cast<unsigned long>(this->messageSpaceSize));
        }

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