文|王祖熙(花名:金九 )

蚂蚁团体开发工程师

负责国产化明码库 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 加密

  1. 明文 m,满足 −n<m<n;
  2. 抉择随机数 r,满足  0≤r<n  且  ;
  3. 计算密文:。

2.3 解密

  1. 密文 c,满足;
  2. 计算明文:。

2.4 密文加法

  1. 密文:c1 和 c2,,c 就是密文加法的后果。

2.5 密文减法

  1. 密文:c1 和 c2,计算:,c 就是密文减法的后果。

2.6 密文标量乘法

  1. 密文: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 + c2int PAILLIER_add(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,PAILLIER_CIPHERTEXT *c1, PAILLIER_CIPHERTEXT *c2);// 密文标量加,r = c1 * mint PAILLIER_add_plain(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,                       PAILLIER_CIPHERTEXT *c1, int32_t m);// 密文减,r = c1 - c2int PAILLIER_sub(PAILLIER_CTX *ctx, PAILLIER_CIPHERTEXT *r,PAILLIER_CIPHERTEXT *c1, PAILLIER_CIPHERTEXT *c2);// 密文标量乘,r = c * mint 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 -helpUsage: paillier [action options] [input/output options] [arg1] [arg2]General options:-help         Display this summaryAction 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) * 99Input options:-in val       Input file-key_in val   Input is a paillier private key used to generate public keyOutput 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 outputParameters:arg1          Argument for encryption/decryption, or the first argument of a homomorphic operationarg2          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_testPAILLIER_encrypt(20000021) cost: 3.202000msPAILLIER_encrypt(500) cost: 0.442000msPAILLIER_add(C2000021,C500) cost: 0.047000msPAILLIER_decrypt(C20000021,C500) result: 20000521, cost: 0.471000msPAILLIER_mul(C500,800) cost: 0.056000msPAILLIER_decrypt(C500,800) result: 400000, cost: 0.464000msPAILLIER_CIPHERTEXT_encode size: 0

本周举荐浏览

你好,我的新名字叫“铜锁/Tongsuo”

BabaSSL:反对半同态加密算法 EC-ElGamal

BabaSSL 公布 8.3.0|实现相应隐衷计算的需要

开源我的项目文档社区化!Tongsuo/铜锁实际