Paillier同态加密的介绍以及c++实现我们先来简短认识⼀下Paillier同态加密算法：
如果就这么按照定义来⽤最简朴的c++程序写就像这样：
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include<cmath>肺结核不能吃什么
#define MIN 32768 //随机数产⽣的范围
#define MAX 65536
using namespace std;
int p, q;茶饮
bool judgeprime(int i) {
int j;
for (j = 2; j <= sqrt(i); j++)
if (i % j == 0)
break;
if (j > sqrt(i))
return true;
}
int gcd(int a, int b)///辗转相除法求最⼤公约数最朴实的求法
{
int t = a;
while (a % b)
{
a = b;
b = t % b;
t = a;
}
return b;
}
int lcm(int a,int b)
{
return a * b / gcd(a, b);
}
void get2prime()
{
srand((unsigned)time(NULL));
while (1)
{
p = MIN + (rand() % (MAX - MIN));
q = MIN + (rand() % (MAX - MIN));
if (gcd(p * q, (p - 1) * (q - 1)) == 1 && judgeprime(p) && judgeprime(q))
break;
}
}
int N;
int Lfun(int x)
{
int b; b = (x - 1) / N;
return b;
}
int main()
{
get2prime();
N = p*q;
cout << "p:" << p << "" << "q:" << q << endl;
int lan;
lan = lcm(p - 1, q - 1);
int g = 0;
int k;
k = Lfun( int (pow(g, lan)) % (N * N));
srand((unsigned)time(NULL));
while (1)
{
g = rand() % (N * N);
if (gcd(k, N) == 1)
break;
}
cout << "算法公钥为 " << g << " ," << N << endl;
孕妇要吃什么}
这个代码当时写错了
当时没有系统学习数论对于乘法群⽣成元循环群的理解有差错诈骗短信范本
不过先不影响这个
得...这时间复杂度...
光这个公钥就跑不出来
但是怎么去缩⼩时间复杂度⾄今没有办法
去gayhub找了找别⼈的代码这没办法我真不知道有NTL这玩意这个只能⾃⼰多敲代码多实践才能发现
原来 c++还有⼀种便携结构和算法库叫做NTL
赞美母亲的优美句子可实现任意长度的整数，向量，矩阵和整系数多项式和有限域上的运算。
在当前平台⽀持C++11，NTL可以编译线程安全的和异常安全模式
说⽩了就是⼀个C++的⾮标准外部库⽂件。要使⽤的的话得⾃⼰编译安装。⼀般利⽤C++实现某些公钥密码算法会⽤到，可以提⾼运算效率。实现全同态密码算法会常⽤到。
所以对于应⽤密码学来说还挺有⽤的！
这个NTL 不是标准库中的所以要⾃⼰装同时你找c reference也是找不到注解的
安装教程：/p/cfe0a8072be7
手机服务密码怎么查然后看⼀下代码的实现
以下是主程序main.cpp：
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <asrt.h>
#include "paillier.h"
using namespace std;
using namespace NTL;
ZZ lcm(ZZ x, ZZ y){
ZZ ans = (x * y) / NTL::GCD(x,y);
return ans;
}
int main()
{
ZZ p = ZZ(43);
ZZ q = ZZ(41);
ZZ lambda = lcm(p - 1, q - 1);
Paillier paillier(p*q, lambda);
ZZ m = ZZ(10);
ZZ n = p * q;
cout << "p = " << p << endl;
cout << "q = " << q << endl;
cout << "n = " << n << endl;
cout << "lamdba = " << lambda << endl;
ZZ c = pt(m, (ZZ)131 );
cout << "c = " << c << endl;
ZZ m2 = paillier.decrypt(c);
cout << "m2 = " << m2 << endl;
if (m == m2){
cout << "m = m2, encryption and decryption successful" << endl; }
return0;
}
以下是
paillier.cpp⽂件
#include "paillier.h"
NTL::ZZ generateCoprimeNumber(const NTL::ZZ& n) {
NTL::ZZ ret;
while (true) {
ret = RandomBnd(n);
if (NTL::GCD(ret, n) == 1) { return ret; }
}
}
Paillier::Paillier() {
/* Length in bits. */
long keyLength = 512;
NTL::ZZ p, q;
GenPrimePair(p, q, keyLength);
modulus = p * q;
generator = modulus + 1;
NTL::ZZ phi = (p - 1) * (q - 1);
// LCM(p, q) = p * q / GCD(p, q);
lambda = phi / NTL::GCD(p - 1, q - 1);
lambdaInver = NTL::InvMod(lambda, modulus);
}
Paillier::Paillier(const NTL::ZZ& modulus, const NTL::ZZ& lambda) { this->modulus = modulus;
generator = this->modulus + 1;
this->lambda = lambda;
lambdaInver = NTL::InvMod(this->lambda, this->modulus);
}
void Paillier::GenPrimePair(NTL::ZZ& p, NTL::ZZ& q,
long keyLength) {
while (true) {
long err = 80;
p = NTL::GenPrime_ZZ(keyLength/2, err);
NTL::ZZ q = NTL::GenPrime_ZZ(keyLength/2, err);
while (p != q) {
q = NTL::GenPrime_ZZ(keyLength/2, err);
}
NTL::ZZ n = p * q;
NTL::ZZ phi = (p - 1) * (q - 1);
if (NTL::GCD(n, phi) == 1) return;
}
}
NTL::ZZ Paillier::encrypt(const NTL::ZZ& message) {
NTL::ZZ random = generateCoprimeNumber(modulus);
NTL::ZZ ciphertext =
NTL::PowerMod(generator, message, modulus * modulus) *
NTL::PowerMod(random, modulus, modulus * modulus);
return ciphertext % (modulus * modulus);
}
NTL::ZZ Paillier::encrypt(const NTL::ZZ& message, const NTL::ZZ& random) { NTL::ZZ ciphertext =
NTL::PowerMod(generator, message, modulus * modulus) *
NTL::PowerMod(random, modulus, modulus * modulus);
return ciphertext % (modulus * modulus);
}
NTL::ZZ Paillier::decrypt(const NTL::ZZ& ciphertext) {
/* NOTE: NTL::PowerMod will fail if the first input is too large
* (which I assume means larger than modulus).
*/
NTL::ZZ deMasked = NTL::PowerMod(
ciphertext, lambda, modulus * modulus);
NTL::ZZ power = L_function(deMasked);
return (power * lambdaInver) % modulus;
}
以下是paillier.h⽂件
#include <NTL/ZZ.h>
#include <NTL/ZZ_pXFactoring.h>
class Paillier {
public:
/* Completely generate everything, from scratch */
Paillier();
Paillier(const NTL::ZZ& modulus, const NTL::ZZ& lambda);
//Paillier(path to public key, path to private key).
/* Paillier encryption function. Takes in a message from the
* integers modulo n (dulus) and returns a message in
* the integers modulo n**2.
*
* Parameters
* ==========
* NTL::ZZ message : The message to encrypt, as a number.
*
* Returns
* =======
* NTL:ZZ ciphertext : The encyrpted message.
*/
NTL::ZZ encrypt(const NTL::ZZ& message);
/* Paillier encryption function with provided randomness, if ur
* wants to provide their own randomness.
*
* Random number should be coprime to modulus.
*
* Parameters
* ==========
* NTL::ZZ message : The message to encrypt, as a number.
* NTL::ZZ random : The random mask.
*
* Returns
* =======
* NTL:ZZ ciphertext : The encyrpted message.
*/
NTL::ZZ encrypt(const NTL::ZZ& message, const NTL::ZZ& random); /* Paillier decryption function. Takes in a cipertext from Z mod
* n**2 and returns a message in the Z mod n.
*
* Parameters
* ==========
* NTL::ZZ cipertext : The encrypted message.
*
* Returns
* =======
* NTL::ZZ message : The original message.
*/
NTL::ZZ decrypt(const NTL::ZZ& ciphertext);
private:
/* modulus = pq, where p and q are primes */
NTL::ZZ modulus;
NTL::ZZ generator;
NTL::ZZ lambda;
NTL::ZZ lambdaInver;
/* The L function in the paillier cryptosystem. See
* <en.wikipedia/wiki/Paillier_cryptosystem> for more
* details.
*
* Parameters
* ==========
美文摘抄赏析* NTL::ZZ x : The argument to L.
* NTL::ZZ n : The paillier modulus.内质
*
* Returns
* =======
* NTL::ZZ result : (x - 1) / n
*/
NTL::ZZ L_function(const NTL::ZZ& n) { return (n - 1) / modulus; } void GenPrimePair(NTL::ZZ& p, NTL::ZZ& q, long keyLength);
};
