文|王祖熙（花名：金九 )
蚂蚁团体开发工程师
负责国产化明码库 Tongsuo 的开发和保护
专一于密码学、高性能网络、网络安全等畛域
本文 4316 字 浏览 10 分钟
1. 背景
在《Tongsuo 反对半同态加密算法 EC-ElGamal》中，曾经论述了同态和半同态加密算法的背景和原理，能够移步查阅。总之，同态算法在隐衷计算畛域有着重要的作用，目前利用比拟宽泛的是 Paillier 和 EC-ElGamal 半同态加密算法，它们接口相似且只反对加法同态。
然而它们两者的性能和原理有很大的差别：
原理方面 ，Paillier 是基于复合残余类的困难性问题 （大数合成难题） 的公钥加密算法，有点相似 RSA；而 EC-ElGamal 是基于椭圆曲线数学实践的公钥加密算法，其安全性实践上要比 Paillier 要更好。
性能方面 ，EC-ElGamal 的加密和密文加法性能要比 Paillier 好；而 Paillier 的解密和密文标量乘法性能要比起 EC-ElGamal 要更好更稳固 （EC-ElGamal 的解密性能与解密的数字大小有关系，数字越大可能须要解密的工夫越长，这与 EC-ElGamal 解密用到的解密表有关系，而 Paillier 的解密就没有这个问题。）。
所以这两个产品各有优劣，大家能够依据本人的业务特点抉择应用 Paillier 还是 EC-ElGamal。
2. Paillier 原理
2.1 密钥生成
1. 随机抉择两个大素数 p、q，满足，且满足 p 和 q 的长度相等；
2. 计算以及，示意最小公倍数；
3. 随机抉择整数，个别 g 的计算公式如下：
a. 随机抉择整数；
b. 计算：，为了简化和进步性能，k 个别选 1，g=1+n；
4. 定义 L 函数：，计算：；
5. 公钥：(n, g)，私钥：(λ, μ)。
2.2 加密
- 明文 m，满足 −n<m<n；
- 抉择随机数 r，满足 0≤r<n 且；
- 计算密文：。
2.3 解密
- 密文 c，满足；
- 计算明文：。
2.4 密文加法
- 密文：c1 和 c2，，c 就是密文加法的后果。
2.5 密文减法
- 密文：c1 和 c2，计算：，c 就是密文减法的后果。
2.6 密文标量乘法
- 密文：c1，明文标量：a，计算：，c 就是密文标量乘法的后果。
3. 正确性
3.1 加解密正确性
公式推导须要用到 Carmichael 函数和确定合数残余的公式，上面简略阐明一下：
● Carmichael 函数
a. 设 n=pq，其中：p、q 为大素数；
b. 欧拉函数：ϕ(n)，Carmichael 函数：λ(n)；
c. 当 和 时，
其中：。
对于任意，有如下性质：。
● 断定合数残余
a. 断定合数残余类问题是指 n=pq，其中：p、q 为大素数，任意给定，使得，则说 z 是模 的第 n 次残余；
b. 第 n 项残余的汇合是 的一个 阶乘法子集；
c. 每个第 n 项残余 z 都正好领有 n 个 n 阶的根，其中只有一个是严格小于 n 的 （即 ）；d. 第 n 项残余都能够写成 的模式。
● 正确性验证
解密：
3.2 密文加法正确性
3.3 密文减法正确性
3.4 密文标量乘法正确性
4. 算法实现
4.1 接口定义
●对象相干接口
○公 / 私钥对象：PAILLIER_KEY，该对象用来保留 Paillier 公钥和私钥的根本信息，比方 p、q、n、g、λ、μ 等信息，私钥保留所有字段，公钥只保留 n、g，其余字段为空或者 0。相干接口如下：
// 创立 PAILLIER_KEY 对象
\PAILLIER_KEY *PAILLIER_KEY_new(void);
// 开释 PAILLIER_KEY 对象
void PAILLIER_KEY_free(PAILLIER_KEY *key);
// 拷贝 PAILLIER_KEY 对象，将 src 拷贝到 dest 中
PAILLIER_KEY *PAILLIER_KEY_copy(PAILLIER_KEY *dest, PAILLIER_KEY *src);
// 复制 PAILLIER_KEY 对象
PAILLIER_KEY *PAILLIER_KEY_dup(PAILLIER_KEY *key);
// 将 PAILLIER_KEY 对象援用计数加 1，开释 PAILLIER_KEY 对象时若援用计数不为 0 则不能开释其内存
intPAILLIER_KEY_up_ref(PAILLIER_KEY *key);
// 生成 PAILLIER_KEY 对象中的参数，bits 为随机大素数 p、q 的二进制位长度
int PAILLIER_KEY_generate_key(PAILLIER_KEY *key, int bits);
// 获取 key 的类型：公钥 or 私钥
// PAILLIER_KEY_TYPE_PUBLIC 为私钥，PAILLIER_KEY_TYPE_PRIVATE 为私钥
int PAILLIER_KEY_type(PAILLIER_KEY *key);○上下文对象：PAILLIER_CTX，该对象用来保留公私钥对象以及一些其余外部用到的信息，是 Paillier 算法其余接口的第一个参数。相干接口如下：
// 创立 PAILLIER_CTX 对象，key 为 paillier 公钥或者私钥，threshold 为反对最大的数字阈值，加密场景可设置为 0，解密场景可应用默认值：PAILLIER_MAX_THRESHOLDPAILLIER_CTX *PAILLIER_CTX_new(PAILLIER_KEY *key, int64_t threshold);
// 开释 PAILLIER_CTX 对象
void PAILLIER_CTX_free(PAILLIER_CTX *ctx);
// 拷贝 PAILLIER_CTX 对象，将 src 拷贝到 dest 中
PAILLIER_CTX *PAILLIER_CTX_copy(PAILLIER_CTX *dest, PAILLIER_CTX *src);
// 复制 PAILLIER_CTX 对象
PAILLIER_CTX *PAILLIER_CTX_dup(PAILLIER_CTX *src);○密文对象：PAILLIER_CIPHERTEXT，该对象是用来保留 Paillier 加密后的后果信息，用到 PAILLIER_CIPHERTEXT 的中央，可调用如下接口：
// 创立 PAILLIER_CIPHERTEXT 对象
PAILLIER_CIPHERTEXT *PAILLIER_CIPHERTEXT_new(PAILLIER_CTX *ctx);
// 开释 PAILLIER_CIPHERTEXT 对象
void PAILLIER_CIPHERTEXT_free(PAILLIER_CIPHERTEXT *ciphertext);●加密 / 解密接口
// 加密，将明文 m 进行加密，后果保留到 PAILLIER_CIPHERTEXT 对象指针 out 中
int PAILLIER_encrypt(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *out, int32_t m);
// 解密，将密文 c 进行解密，后果保留到 int32_t 指针 out 中
int PAILLIER_decrypt(PAILLIER_CTX *ctx, int32_t *out, PAILLIER_CIPHERTEXT *c);●密文加 / 减 / 标量乘运算接口
// 密文加，r = c1 + c2
int PAILLIER_add(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,
PAILLIER_CIPHERTEXT *c1, PAILLIER_CIPHERTEXT *c2);
// 密文标量加，r = c1 * m
int PAILLIER_add_plain(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r, PAILLIER_CIPHERTEXT *c1, int32_t m);
// 密文减，r = c1 - c2
int PAILLIER_sub(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,
PAILLIER_CIPHERTEXT *c1, PAILLIER_CIPHERTEXT *c2);
// 密文标量乘，r = c * m
int PAILLIER_mul(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,
PAILLIER_CIPHERTEXT *c, int32_t m);●编码 / 解码接口
同态加密波及到多方参加，可能会须要网络传输，这就须要将密文对象 PAILLIER_CIPHERTEXT 编码后能力传递给对方，对方也须要解码失去 PAILLIER_CIPHERTEXT 对象后能力调用其余接口进行运算。
接口如下：
// 编码，将密文 ciphertext 编码后保留到 out 指针中，out 指针的内存须要提前调配好；// 如果 out 为 NULL，则返回编码所需的内存大小；// flag：标记位，预留，临时没有用 size_t PAILLIER_CIPHERTEXT_encode(PAILLIER_CTX *ctx, unsigned char *out,
size_t size,
const PAILLIER_CIPHERTEXT *ciphertext,
int flag);
// 解码，将长度为 size 的内存数据 in 解码后保留到密文对象 r 中
int PAILLIER_CIPHERTEXT_decode(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r, unsigned char *in, size_t size);以上所有接口具体阐明请参考 Paillier API 文档：https://www.yuque.com/tsdoc/api/slgr6f
4.2 外围实现
●Paillier Key
Paillier 不像 EC-ElGamal，EC-ElGamal 在 Tongsuo 外面间接复用 EC_KEY 即可，Paillier Key 在 Tongsuo 外面则须要实现一遍，次要性能有：公 / 私钥的生成、PEM 格局存储、公 / 私钥解析和文本展现，详情请查阅代码：
crypto/paillier/paillier_key.c、
crypto/paillier/paillier_asn1.c、
crypto/paillier/paillier_prn.c。
●Paillier 加解密、密文运算
Paillier 的加解密和密文运算算法非常简单，次要是大数的模幂运算，应用 Tongsuo 外面的 BN 相干接口就能够，须要留神的是，正数的加密 / 解密用到模逆运算，不能间接按公式计算 （），这是因为 OpenSSL 的接口 BN_mod_exp 没有关注指数 （下面公式的 m） 是不是正数，如果是正数的话须要做一次模逆运算：，这里计算出 之后做一次模逆运算 （BN_mod_inverse） 再与相乘；解密的时候，须要确认是否查看了阈值 （ PAILLIER_MAX_THRESHOLD），超出则阐明是正数，须要减去 n 才失去真正的后果。密文减法也须要用到模逆运算，通过密文减法的公式 （） 得悉，须要进行模逆运算 （ BN_mod_inverse） 再与 相乘。
详情请查阅代码：
crypto/paillier/paillier_crypt.c
●Paillier 命令行
为了进步 Paillier 的易用性，Tongsuo 实现了如下 Paillier 子命令：
$ /opt/tongsuo-debug/bin/openssl paillier -help
Usage: paillier [action options] [input/output options] [arg1] [arg2]
General options:
-help Display this summary
Action options:
-keygen Generate a paillier private key
-pubgen Generate a paillier public key
-key Display/Parse a paillier private key
-pub Display/Parse a paillier public key
-encrypt Encrypt a number with the paillier public key, usage: -encrypt 99, 99 is an example number
-decrypt Decrypt a ciphertext using the paillier private key, usage:-decrypt c1, c1 is an example ciphertext
-add Paillier homomorphic addition: add two ciphertexts, usage: -add c1 c2, c1 and c2 are tow example ciphertexts, result: E(c1) + E(c2)
-add_plain Paillier homomorphic addition: add a ciphertext to a plaintext, usage: -add_plain c1 99, c1 is an example ciphertext, 99 is an example number, result: E(c1) + 99
-sub Paillier homomorphic subtraction: sub two ciphertexts, usage: -sub c1 c2, c1 and c2 are tow example ciphertexts, result: E(c1) - E(c2)
-mul Paillier homomorphic scalar multiplication: multiply a ciphertext by a known plaintext, usage: -mul c1 99, c1 is an example ciphertext, 99 is an example number, result: E(c1) * 99
Input options:
-in val Input file
-key_in val Input is a paillier private key used to generate public key
Output options:
-out outfile Output the paillier key to specified file
-noout Don't print paillier key out
-text Print the paillier key in text
-verbose Verbose output
Parameters:
arg1 Argument for encryption/decryption, or the first argument of a homomorphic operation
arg2 The second argument of a homomorphic operation次要命令有：
– keygen： 生成 Paillier 私钥；
– pubgen： 用 Paillier 私钥生成公钥；
– key： 文本显示 Paillier 私钥；
– pub： 文本显示 Paillier 公钥；
– encrypt： 对数字进行加密，输入 Paillier 加密的后果，须要通过参数 -key_in 参数指定 Paillier 公钥文件门路，如果加密正数则须要将 - 用 _ 代替，因为 - 会被 OpenSSL 解析成预约义参数了 （下同）；
– decrypt： 对 Paillier 密文进行解密，输入解密后果，须要通过 -key_in 参数指定 Paillier 私钥文件门路；
– add： 对两个 Paillier 密文进行同态加法操作，输入同态加法密文后果，须要通过参数 -key_in 参数指定 Paillier 公钥文件门路；
– add_plain： 将 Paillier 密文和明文相加，输入同态加法密文后果，须要通过参数 -key_in 参数指定 Paillier 公钥文件门路；
– sub： 对两个 Paillier 密文进行同态减法操作，输入同态减法密文后果，须要通过参数 -key_in 参数指定 Paillier 公钥文件门路；
– mul： 将 Paillier 密文和明文相乘，输入同态标量乘法密文后果，须要通过参数 -key_in 参数指定 Paillier 公钥文件门路。
通过以上命令即可在命令行进行 Paillier 算法试验，升高入门门槛，详情请查阅代码：apps/paillier.c。
另外还实现了 Paillier 的 speed 命令，能够进行性能测试，详情请查阅代码：apps/speed.c。
5. 用法 & 例子
5.1 demo 程序
#include <stdio.h>
#include <time.h>
#include <openssl/paillier.h>
#include <openssl/pem.h>
#define CLOCKS_PER_MSEC (CLOCKS_PER_SEC/1000)
int main(int argc, char *argv[])
{
int ret = -1;
int32_t r;
clock_t begin, end;
PAILLIER_KEY *pail_key = NULL, *pail_pub = NULL;
PAILLIER_CTX *ctx1 = NULL, *ctx2 = NULL;
PAILLIER_CIPHERTEXT *c1 = NULL, *c2 = NULL, *c3 = NULL;
FILE *pk_file = fopen("pail-pub.pem", "rb");
FILE *sk_file = fopen("pail-key.pem", "rb");
if ((pail_pub = PEM_read_PAILLIER_PublicKey(pk_file, NULL, NULL, NULL)) == NULL)
goto err;
if ((pail_key = PEM_read_PAILLIER_PrivateKey(sk_file, NULL, NULL, NULL)) == NULL)
goto err;
if ((ctx1 = PAILLIER_CTX_new(pail_pub, PAILLIER_MAX_THRESHOLD)) == NULL)
goto err;
if ((ctx2 = PAILLIER_CTX_new(pail_key, PAILLIER_MAX_THRESHOLD)) == NULL)
goto err;
if ((c1 = PAILLIER_CIPHERTEXT_new(ctx1)) == NULL)
goto err;
if ((c2 = PAILLIER_CIPHERTEXT_new(ctx1)) == NULL)
goto err;
begin = clock();
if (!PAILLIER_encrypt(ctx1, c1, 20000021))
goto err;
end = clock();
printf("PAILLIER_encrypt(20000021) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);
begin = clock();
if (!PAILLIER_encrypt(ctx1, c2, 500))
goto err; end = clock();
printf("PAILLIER_encrypt(500) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);
if ((c3 = PAILLIER_CIPHERTEXT_new(ctx1)) == NULL)
goto err;
begin = clock();
if (!PAILLIER_add(ctx1, c3, c1, c2))
goto err; end = clock();
printf("PAILLIER_add(C2000021,C500) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);
begin = clock();
if (!(PAILLIER_decrypt(ctx2, &r, c3)))
goto err; end = clock();
printf("PAILLIER_decrypt(C20000021,C500) result: %d, cost: %lfms\n", r, (double)(end - begin)/CLOCKS_PER_MSEC);
begin = clock();
if (!PAILLIER_mul(ctx1, c3, c2, 800))
goto err;
end = clock();
printf("PAILLIER_mul(C500,800) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);
begin = clock();
if (!(PAILLIER_decrypt(ctx2, &r, c3)))
goto err; end = clock();
printf("PAILLIER_decrypt(C500,800) result: %d, cost: %lfms\n", r, (double)(end - begin)/CLOCKS_PER_MSEC);
printf("PAILLIER_CIPHERTEXT_encode size: %zu\n", PAILLIER_CIPHERTEXT_encode(ctx2, NULL, 0, NULL, 1));
ret = 0;
err: PAILLIER_KEY_free(pail_key);
PAILLIER_KEY_free(pail_pub);
PAILLIER_CIPHERTEXT_free(c1);
PAILLIER_CIPHERTEXT_free(c2);
PAILLIER_CIPHERTEXT_free(c3);
PAILLIER_CTX_free(ctx1);
PAILLIER_CTX_free(ctx2);
fclose(sk_file);
fclose(pk_file);
return ret;
}5.2 编译和运行
先确保 Tongsuo 开启 Paillier，如果是手工编译 Tongsuo，可参考如下编译步骤：
# 下载代码
git clone git@github.com:Tongsuo-Project/Tongsuo.git
# 编译参数须要加上：enable-paillier
./config --debug no-shared no-threads enable-paillier --strict-warnings -fPIC --prefix=/opt/tongsuo
# 编译
make -j
# 装置到目录
/opt/tongsuo sudo make install5.3 编译 demo 程序
gcc -Wall -g -o paillier_test ./paillier_test.c -I/opt/tongsuo/include -L/opt/tongsuo/lib -lssl -lcrypto5.4 生成 Paillier 公私钥
# 学生成私钥
/opt/tongsuo/bin/openssl paillier -keygen -out pail-key.pem#
用私钥生成公钥
/opt/tongsuo/bin/openssl paillier -pubgen -key_in ./pail-key.pem -out pail-pub.pem5.5 运行后果
$ ./paillier_test
PAILLIER_encrypt(20000021) cost: 3.202000ms
PAILLIER_encrypt(500) cost: 0.442000ms
PAILLIER_add(C2000021,C500) cost: 0.047000ms
PAILLIER_decrypt(C20000021,C500) result: 20000521, cost: 0.471000ms
PAILLIER_mul(C500,800) cost: 0.056000ms
PAILLIER_decrypt(C500,800) result: 400000, cost: 0.464000ms
PAILLIER_CIPHERTEXT_encode size: 0本周举荐浏览
你好，我的新名字叫“铜锁 /Tongsuo”
BabaSSL：反对半同态加密算法 EC-ElGamal
BabaSSL 公布 8.3.0|实现相应隐衷计算的需要
开源我的项目文档社区化！Tongsuo/ 铜锁实际