当前位置：首页 > backend >正文

Paillier加密方案的原理、实现与应用（dev）

backend 2025/7/14 13:13:57

一、实验目的

1、掌握NTL的基本配置和方法

2、掌握Paillier加密方案的原理与实现

①钥匙生成：首先，生成一把钥匙，包括钥匙和私钥匙。钥匙由两个大素数(p,q)的乘积n和一个整数g组成，私钥匙由这两个大素数组成。

②加密过程：将明文m加密为密文c。加密时使用峰值n和g，以及一个随机数r。加密计算公式为c = E(m,r) = gmrn mod n2，其中m为明文，r为随机数。

③解密过程：利用私钥中的素数p和q，以及密文c进行解密。解密计算公式为[m = m = D(c,lambda) = (L(clambda mod n2) / L（glambda mod n2)) mod n，其中lambda = text{lcm}(p-1, q-1))，mu是模逆，L（u） = （u-1）/ n.

二、实验设计

通过网盘分享的文件：WinNTL-11_5_0
链接: https://pan.baidu.com/s/1rkG9reIxSoJcbuyuEDWJGw?pwd=a898 提取码: a898
--来自百度网盘超级会员v5的分享

关于NTL的基本配置方法：

①在官网Download NTL (libntl.org)下载NTL的压缩文件，选择11.5.0如下：

②打开dev，创建静态库的新项目，命名为CNTL，如下：

③将NTL文件中的src文件夹下的内容全部添加，过程如下：

④将下载来的include文件夹包含进CNTL，如下：

⑤进行编译，自动生成.a的文件

⑥查看项目文件，NTL--->Debug下，存在NTL.lib文件，

⑦生成的CNTL.a文件复制到dev所在文件夹的lib文件夹中，配置完成

进行检测：

①创建一个常规的项目，命名为test，如下：

在WinNTL-11_3_4下include中的test里面找到quicktest，复制其代码放在刚创建好，并按上面配置好环境，如下：

③发现代码运行成功，即检测完成。

Paillier加密方案代码的实现：

Paillier算法加密解密可以自己做，但是由于能力有限，经百度后得到下面的代码：

#include <NTL/ZZ.h>
#include <NTL/ZZ_pXFactoring.h>#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <assert.h>using namespace std;
using namespace NTL;class Paillier {
public:/* 构造函数和完全重新开始生成函数 */Paillier();Paillier(const NTL::ZZ& modulus, const NTL::ZZ& lambda);//分别为找到公钥路径和私钥路径./* Paillier加密函数。接收来自*整数模n（Paillier.module）并以*模n**2的整数。* 参数* ==========* NTL::ZZ message :明文作为一个数字进行加密.* NTL:ZZ ciphertext : 加密过后的信息.*/NTL::ZZ encrypt(const NTL::ZZ& message);/* 提供随机生成的加密函数** Random number should be coprime to modulus.**参数* ==========* NTL::ZZ message : 明文，作为一个数字进行加密.* NTL::ZZ random : 随机生成的掩码.* =======* NTL:ZZ ciphertext : 加密过后的密文.*/NTL::ZZ encrypt(const NTL::ZZ& message, const NTL::ZZ& random);/* Paillier解密函数。接收来自Z mod的密文* n**2并在Z mod n中返回一条消息。** 参数* ==========* NTL::ZZ cipertext :需要解密的密文.* =======* NTL::ZZ 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 lambdaInverse;/*l函数* Parameters* ==========* NTL::ZZ x : l的参量.* NTL::ZZ n : paillier模量.* =======* 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);
};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() {long keyLength = 512;NTL::ZZ p, q;GenPrimePair(p, q, keyLength);modulus = p * q;generator = modulus + 1;NTL::ZZ phi = (p - 1) * (q - 1);lambda = phi / NTL::GCD(p - 1, q - 1);lambdaInverse = NTL::InvMod(lambda, modulus);
}Paillier::Paillier(const NTL::ZZ& modulus, const NTL::ZZ& lambda) {this->modulus = modulus;generator = this->modulus + 1;this->lambda = lambda;lambdaInverse = 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) {NTL::ZZ deMasked = NTL::PowerMod(ciphertext, lambda, modulus * modulus);NTL::ZZ power = L_function(deMasked);return (power * lambdaInverse) % modulus;
}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;  //"随机生成p 为 "cout <<  "q=" <<q<< endl;  //"随机生成q 为”cout << "n=" <<n<< endl;   //"随机生成大素数n 为"cout <<  "lambda=" <<lambda<< endl;  //"生成lamdba为"ZZ c = paillier.encrypt(m, (ZZ)131);cout << "c=" <<c<< endl; //  "密文c 为 "ZZ m2 = paillier.decrypt(c);cout << "m2=" <<m2<< endl;  //"解密得出明文为m2 为"if (m == m2) {cout << "m = m2, encryption and decryption successful" << endl;}system("pause");return 0;
}

③在项目中写入Paillier加密的代码，编译运行实现得到结果。如下：