Tongsuo 支持半同态加密算法 Paillier

文｜王祖熙（花名：金九)

蚂蚁集团开发工程师

负责国产化密码库 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，满意

Tongsuo 支持半同态加密算法 Paillier
，且满意 p 和 q 的长度相等；

2.核算以及

Tongsuo 支持半同态加密算法 Paillier
，
Tongsuo 支持半同态加密算法 Paillier
表示最小公倍数；

3.随机挑选整数

Tongsuo 支持半同态加密算法 Paillier
，一般g的核算公式如下：

a. 随机挑选整数

Tongsuo 支持半同态加密算法 Paillier
；

b. 核算：

Tongsuo 支持半同态加密算法 Paillier
，为了简化和进步功能，k一般选 1，g=1+n；

4.界说 L 函数：

Tongsuo 支持半同态加密算法 Paillier
，核算：
Tongsuo 支持半同态加密算法 Paillier
；

5.公钥：(n,g)，私钥：(, )。

2.2加密

  1. 明文 m，满意−n<m<n；

  2. 挑选随机数 r，满意0≤r<n且

    Tongsuo 支持半同态加密算法 Paillier
    ；

  3. 核算密文：

    Tongsuo 支持半同态加密算法 Paillier
    。

2.3 解密

  1. 密文 c，满意

    Tongsuo 支持半同态加密算法 Paillier
    ；

  2. 核算明文：

    Tongsuo 支持半同态加密算法 Paillier
    。

2.4 密文加法

  1. 密文：c1和c2，
    Tongsuo 支持半同态加密算法 Paillier
    ，c便是密文加法的成果。

2.5 密文减法

  1. 密文：c1和c2，核算：
    Tongsuo 支持半同态加密算法 Paillier
    ，c便是密文减法的成果。

2.6 密文标量乘法

  1. 密文：c1，明文标量：a，核算：
    Tongsuo 支持半同态加密算法 Paillier
    ，c便是密文标量乘法的成果。

3. 正确性

3.1 加解密正确性

公式推导需求用到 Carmichael 函数和确定合数剩下的公式，下面简略阐明一下：

● Carmichael 函数

a. 设n=pq，其间：p、q为大素数；

b. 欧拉函数：(n)，Carmichael 函数：(n)；

c. 当

Tongsuo 支持半同态加密算法 Paillier
和
Tongsuo 支持半同态加密算法 Paillier
时，

其间：

Tongsuo 支持半同态加密算法 Paillier
。

关于恣意

Tongsuo 支持半同态加密算法 Paillier
，有如下性质：
Tongsuo 支持半同态加密算法 Paillier
。

● 断定合数剩下

a. 断定合数剩下类问题是指n=pq，其间：p、q为大素数，恣意给定

Tongsuo 支持半同态加密算法 Paillier
，使得
Tongsuo 支持半同态加密算法 Paillier
，则说z是模的第n次剩下；

b. 第n项剩下的集合是

Tongsuo 支持半同态加密算法 Paillier
的一个
Tongsuo 支持半同态加密算法 Paillier
阶乘法子集；

c. 每个第n项剩下z都正好拥有n个n阶的根，其间只要一个是严格小于n的 （即

Tongsuo 支持半同态加密算法 Paillier
） ；d. 第n项剩下都能够写成
Tongsuo 支持半同态加密算法 Paillier
的方式。

● 正确性验证

Tongsuo 支持半同态加密算法 Paillier

解密：

Tongsuo 支持半同态加密算法 Paillier

3.2 密文加法正确性

Tongsuo 支持半同态加密算法 Paillier

3.3 密文减法正确性

Tongsuo 支持半同态加密算法 Paillier

3.4 密文标量乘法正确性

Tongsuo 支持半同态加密算法 Paillier

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 文档：www.yuque.com/tsdoc/api/s…

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 ） 是不是负数，假如是负数的话需求做一次模逆运算：

Tongsuo 支持半同态加密算法 Paillier
，这里核算出之后做一次模逆运算 （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 install

5.3 编译 demo 程序

gcc -Wall -g -o paillier_test ./paillier_test.c -I/opt/tongsuo/include -L/opt/tongsuo/lib -lssl -lcrypto

5.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.pem

5.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/铜锁实践