Paillier.hpp

Go to the documentation of this file.

 
#define BITSETSIZE 64
 
#ifndef PAILLIER_CRYPTOSYSTEM
#define PAILLIER_CRYPTOSYSTEM
 
#include <iostream>
#include <bitset>
#include <vector>
#include <random> //Randomdevice and mt19937
 
using namespace std;
 
template <typename T_in, typename T_out>
class Paillier
{
public:
    Paillier(){};
 
    ~Paillier(){};
 
    uint64_t random64(uint64_t min, uint64_t max)
    {
        static std::random_device rd;
        static std::mt19937 gen(rd());
        std::uniform_int_distribution<std::uint64_t> dis(min, max);
        return dis(gen);
    }
 
    uint64_t fastMod_64t(uint64_t x, uint64_t e, uint64_t n)
    {
        uint64_t c = 1;
        bitset<BITSETSIZE> bits = bitset<BITSETSIZE>(e);
 
        for (int i = BITSETSIZE - 1; i >= 0; i--)
        {
            c = c * c % n;
            if (bits[i] & 1)
                c = c * x % n;
        }
 
        return c;
    };
 
    uint64_t gcd_64t(uint64_t a, uint64_t b)
    {
        if (b == 0)
        {
            return a;
        }
        return gcd_64t(b, a % b);
    };
 
    std::vector<uint64_t> calc_set_same_remainder_divide_euclide_64t(uint64_t n)
    {
        std::vector<uint64_t> result;
        for (uint64_t i = 0; i < n; i++)
        {
            if (gcd_64t(i, n) == 1)
            {
                result.push_back(i);
            }
        }
        return result;
    };
 
    std::vector<uint64_t> calc_set_same_remainder_divide_euclide_64t_v2(uint64_t n, const uint64_t &lambda)
    {
        std::vector<uint64_t> result;
 
        uint64_t x, r = 0, mu = 0;
        for (uint64_t g = 0; g < n; g++)
        {
            if (gcd_64t(g, n) == 1)
            {
                uint64_t u = fastMod_64t(g, lambda, n * n);
                uint64_t l = (u - 1) / n;
                r = (x - 1) % n; // Vérifier si x est entier.
                mu = modInverse_64t(l, n);
                if (mu != 0)
                {
                    result.push_back(g);
                }
            }
        }
        return result;
    };
 
    uint64_t choose_g_in_vec_64t(std::vector<uint64_t> &set, const uint64_t &n, const uint64_t &lambda)
    {
        uint64_t x;
        int i_position = 0;
        uint64_t g = 0, r = 1, r2 = 1, mu = 0;
        while (r != 0 && r2 != 0 && mu == 0)
        {
            i_position = rand() % set.size();
            g = set.at(i_position);
            x = fastMod_64t(g, lambda, n * n);
            r = (x - 1) % n;            // Vérifier si L(x) est entier.
            r2 = (x - 1) / n;           // Vérifier si L(x) est entier.
            mu = modInverse_64t(r2, n); // Calculer μ en utilisant la formule donnée et la fonction modular_inverse pour calculer l'inverse modulaire
        }
        return g;
    };
 
    uint64_t choose_g_in_vec_64t_v2(std::vector<uint64_t> &set)
    {
        int i_position = rand() % set.size();
        return set.at(i_position);
    };
 
    uint64_t L_64t(uint64_t x, uint64_t n)
    {
        return (x - 1) / n;
    };
 
    uint64_t lcm_64t(uint64_t a, uint64_t b)
    {
        return a * b / gcd_64t(a, b);
    };
 
    uint64_t modInverse_64t(uint64_t a, uint64_t n)
    {
        a = a % n;
        for (uint64_t x = 1; x < n; x++)
        {
            if ((a * x) % n == 1)
                return x;
        }
 
        return 0;
    };
 
    uint64_t pow_uint64_t(uint64_t x, uint64_t n)
    {
        if (n == 0)
        {
            return 1;
        }
        return x * pow_uint64_t(x, n - 1);
    };
 
    uint64_t randomZNStar(uint64_t n)
    {
        uint64_t r = 0;
        do
        {
            r = random64(1, n);
        } while (r >= 1 && gcd_64t(r, n) != 1);
        return r;
    };
 
    std::vector<uint64_t> get_set_ZNZStar(uint64_t n)
    {
        std::vector<uint64_t> ZNZStar;
        for (uint64_t i = 1; i < n; i++)
        {
            if (gcd_64t(i, n) == 1)
            {
                ZNZStar.push_back(i);
            }
        }
        return ZNZStar;
    }
 
    std::vector<uint64_t> get_set_ZN2ZStar(uint64_t n, uint64_t lambda)
    {
        std::vector<uint64_t> ZN2ZStar;
        for (uint64_t g = 1; g < n * n; g++)
        {
            uint64_t u, l;
            u = fastMod_64t(g, lambda, n * n);
            l = L_64t(u, n);
            if (gcd_64t(l, n) == 1)
            {
                ZN2ZStar.push_back(g);
            }
        }
        return ZN2ZStar;
    }
 
    uint64_t generate_g_64t(uint64_t n, uint64_t lambda)
    {
        uint64_t g, u, l;
        do
        {
            g = randomZNStar(n * n); // generate g, a random integer in Z*_{n^2}
            u = fastMod_64t(g, lambda, n * n);
            l = L_64t(u, n);
        } while (gcd_64t(l, n) != 1);
        return g;
    };
 
    void generateMu_64t(uint64_t &mu, const uint64_t &g, const uint64_t &lambda, const uint64_t &n)
    {
        uint64_t u = fastMod_64t(g, lambda, n * n);
        uint64_t l = (u - 1) / n;
        mu = modInverse_64t(l, n);
    };
 
    void generatePrivateKey_64t(uint64_t &lambda, uint64_t &mu, const uint64_t &p, const uint64_t &q, const uint64_t &n, const uint64_t &g)
    {
        lambda = lcm_64t(p - 1, q - 1);
 
        generateMu_64t(mu, g, lambda, n);
    };
 
    //================ Overload and Generic programming ================//
 
    T_out paillierEncryption(uint64_t n, uint64_t g, T_in m)
    {
        if (m >= std::numeric_limits<uint64_t>::max())
        {
            throw std::runtime_error("Erreur m ne peut pas être stocké dans 64 bits.");
        }
        uint64_t m_64 = static_cast<uint64_t>(m);
 
        uint64_t c;
        // uint64_t r = random64(0,n);
        // while (gcd_64t(r, n) != 1 || r == 0)
        // {
        //     r = random64(0,n);
        // }
        uint64_t r = randomZNStar(n);
 
        // fprintf(stdout, "r : %" PRIu64 "\n", r);
 
        uint64_t fm1 = fastMod_64t(g, m_64, n * n);
        uint64_t fm2 = fastMod_64t(r, n, n * n);
        c = (fm1 * fm2) % (n * n);
 
        if (c >= std::numeric_limits<T_out>::max())
        {
            throw std::runtime_error("Erreur le résultat ne peut pas être stocké dans n*2 bits.");
        }
        return static_cast<T_out>(c);
    };
 
    T_out paillierEncryption(uint64_t n, uint64_t g, T_in m, uint64_t r)
    {
        if (m >= std::numeric_limits<uint64_t>::max())
        {
            throw std::runtime_error("Erreur m ne peut pas être stocké dans 64 bits.");
        }
        uint64_t m_64 = static_cast<uint64_t>(m);
 
        uint64_t c;
        uint64_t fm1 = fastMod_64t(g, m_64, n * n);
        uint64_t fm2 = fastMod_64t(r, n, n * n);
        c = (fm1 * fm2) % (n * n);
 
        if (c >= std::numeric_limits<T_out>::max())
        {
            throw std::runtime_error("Erreur le résultat ne peut pas être stocké dans n*2 bits.");
        }
        return static_cast<T_out>(c);
    };
 
    T_in paillierDecryption(uint64_t n, uint64_t lambda, uint64_t mu, T_out c)
    {
        if (c >= std::numeric_limits<uint64_t>::max())
        {
            throw std::runtime_error("Erreur m ne peut pas être stocké dans 64 bits.");
        }
        uint64_t c_64 = static_cast<uint64_t>(c);
 
        // uint64_t result = (((fastMod_64t(c_64, lambda, n * n) - 1) / n) * mu) % n;
        uint64_t result = ((fastMod_64t(c_64, lambda, n * n) - 1) / n) * mu % n;
 
        if (result >= std::numeric_limits<T_in>::max())
        {
            throw std::runtime_error("Erreur le résultat ne peut pas être stocké dans 8 bits.");
        }
        return static_cast<T_in>(result);
    };
};
 
#endif // PAILLIER_CRYPTOSYSTEM