2 篇博文含有标签「算法」

Tongsuo 支持半同态加密算法 Paillier

2022年11月17日 · 阅读需 16 分钟

Maintainer of Tongsuo

背景

在《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。

Paillier 原理

密钥生成

随机选择两个大素数 $p,q$ ，满足 $gcd(pq, (p-1)(q-1))=1$ ，且满足 p 和 q 的长度相等；
计算 $n=pq$ 以及 $\lambda=lcm(p-1, q-1)$ ， $lcm$ 表示最小公倍数；
随机选择整数 $g\gets \mathbb{Z}_{n^2}^*$ $g \leftarrow Z_{n^{2}}^{*}$ ，一般 $g$ $g$ 的计算公式如下：
1. 随机选择整数 $k \in \mathbb{Z}_{n}^*$
2. 计算： $g=1+kn$ ，为了简化和提高性能， $k$ 一般选1， $g=1+n$
定义 L 函数： $L(x)=\frac{x-1}{n}$ ，计算： $\mu=(L(g^\lambda \space mod \space n^2))^{-1} \space mod \space n$
公钥： $(n, \space g)$ ，私钥： $(\lambda, \space \mu)$

加密

明文 m，满足 $-n < m < n$
选择随机数 r，满足 $0 \leq r<n$ 且 $r\in \mathbb{Z}_n^*$
计算密文： $c=g^mr^n\space mod\space n^2$

解密

密文 c，满足 $c\in \mathbb{Z}_{n^2}^*$
计算明文： $m=L(c^\lambda \space mod \space n^2) \times \mu \space mod \space n$

密文加法

密文： $c_1 \space and \space c_2$ ，计算： $c=c_1 \times c_2 \space mod\space n^2$ ， $c$ 就是密文加法的结果

密文减法

密文： $c_1 \space and \space c_2$ ，计算： $c=\frac{c_1}{c_2} \space mod\space n^2$ ， $c$ 就是密文减法的结果

密文标量乘法

密文： $c_1$ ，明文标量： $a$ ，计算： $c=c_1^a \space mod\space n^2$ ， $c$ 就是密文标量乘法的结果

正确性

加解密正确性

公式推导需要用到 Carmichael 函数和确定合数剩余的公式，下面简单说明一下：

Carmichael 函数
1. 设 $n=pq$ ，其中： $p,q$ 为大素数
2. 欧拉函数： $\phi(n)$ ，Carmichael函数： $\lambda(n)$
3. 当 $\phi(n)=(p-1)(q-1)$ 和 $\lambda(n)=lcm(p-1, q-1)$ 时，其中： $\left|\mathbb{Z}_{n^2}^*\right|=\phi(n^2)=n\phi(n)$ 。对于任意 $w \in \mathbb{Z}_{n^2}^*$ ，有如下性质： $\begin{cases} w^\lambda=1\space mod\space n \\ w^{n\lambda}=1\space mod\space n^2 \end{cases}$
判定合数剩余
1. 判定合数剩余类问题是指 $n=pq$ ，其中： $p,q$ 为大素数，任意给定 $y \in \mathbb{Z}_{n^2}^*$ ，使得 $z=y^n\space mod\space n^2$ ，则说 $z$ 是模 $n^2$ 的第 $n$ 次剩余
2. 第 $n$ 项剩余的集合是 $\mathbb{Z}_{n^2}^*$ 的一个 $\phi(n)$ 阶乘法子集
3. 每个第 $n$ 项剩余 $z$ 都正好拥有 $n$ 个 $n$ 阶的根，其中只有一个是严格小于 $n$ 的（即 $\sqrt[n]{z}\space mod\space n$ ）
4. 第 $n$ 项剩余都可以写成 $(1+n)^x=1+xn\space mod\space n^2$ 的形式
正确性验证

\begin{align} c^\lambda\space mod\space n^2 & =(g^mr^n)^\lambda\space mod\space n^2 \\ & =g^{m\lambda}r^{n\lambda}\space mod\space n^2 \\ & =g^{m\lambda}\space mod\space n^2 \\ & =(1+n)^{m\lambda}\space mod\space n^2 \\ & =1+nm\lambda\space mod\space n^2 \\ \end{align}

\begin{align} g^\lambda\space mod\space n^2 & =(1+n)^\lambda\space mod\space n^2 \\ & =1+n\lambda\space mod\space n^2 \\ \end{align}

L(c^\lambda\space mod\space n^2)=\frac{c^\lambda\space mod\space n^2-1}{n}=\frac{1+nm\lambda\space mod\space n^2-1}{n}=m\lambda\space mod\space n^2

L(g^\lambda\space mod\space n^2)=\frac{g^\lambda\space mod\space n^2-1}{n}=\frac{1+n\lambda\space mod\space n^2-1}{n}=\lambda\space mod\space n^2

解密：

\begin{align} m & = L(c^\lambda \space mod \space n^2) \times \mu \space mod \space n \\ & = \frac{L(c^\lambda \space mod \space n^2)}{L(g^\lambda \space mod \space n^2)}\space mod \space n \\ & = \frac{m\lambda\space mod\space n^2}{\lambda\space mod\space n^2}\space mod \space n \\ & = m\space mod \space n \\ & = m \end{align}

密文加法正确性

$Encrypt(m_1)=c_1$ ， $Encrypt(m_2)=c_2$

\begin{align} Decrypt(c) & = Decrypt(c_1 \times c_2 \space mod\space n^2) = Decrypt((g^{m_1}r_1^n\times g^{m_2}r_2^n)\space mod\space n^2) \\ & = Decrypt((g^{m_1+m_2}(r_1+r_2)^n)\space mod\space n^2)=Decrypt((g^{m_1+m_2}{r}^n)\space mod\space n^2)=m_1+m_2\\ \end{align}

密文减法正确性

$Encrypt(m_1)=c_1$ ， $Encrypt(m_2)=c_2$

\begin{align} Decrypt(c) & = Decrypt(\frac{c_1}{c_2} \space mod\space n^2) = Decrypt(\frac{g^{m_1}r_1^n}{ g^{m_2}r_2^n}\space mod\space n^2) \\ & = Decrypt((g^{m_1}r_1^n\times (g^{m_2}r_2^n)^{-1})\space mod\space n^2) = Decrypt((g^{m_1}r_1^n\times g^{-m_2}r_2^{-n}\space mod\space n^2) \\ & = Decrypt((g^{m_1-m_2}(r_1r_2^{-1})^n)\space mod\space n^2)=Decrypt((g^{m_1-m_2}{r}^n)\space mod\space n^2)=m_1-m_2\\ \end{align}

密文标量乘法正确性

$Encrypt(m_1)=c_1$

\begin{align} Decrypt(c) & = Decrypt(c_1^a \space mod\space n^2) = Decrypt((g^{m_1}r^n)^a\space mod\space n^2) \\ & = Decrypt((g^{am_1}(r^a)^n)\space mod\space n^2)=Decrypt((g^{am_1}r_1^n)\space mod\space n^2)=am_1\\ \end{align}

算法实现

接口定义

对象相关接口

公/私钥对象：PAILLIER_KEY，该对象用来保存 paillier 公钥和私钥的基本信息，比如 $p,q,n,g,\lambda,\mu$ 等信息，私钥保存所有字段，公钥只保存 $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则不能释放其内存
int PAILLIER_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_THRESHOLD
PAILLIER_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

核心实现

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 相关接口就可以，需要注意的是，负数的加密/解密用到模逆运算，不能直接按公式计算（ $c=g^mr^n\space mod\space n^2$ ），这是因为 Openssl 的接口BN_mod_exp没有关注指数（上面公式的 m）是不是负数，如果是负数的话需要做一次模逆运算： $m=-k,c=g^mr^n\space mod\space n^2=g^{-k}r^n\space mod\space n^2=(g^k)^{-1}r^n\space mod\space n^2$ ，这里计算出 $g^k$ 之后做一次模逆运算（BN_mod_inverse）再与 $r^n$ 相乘；解密的时候，需要检查是否检查了阈值（PAILLIER_MAX_THRESHOLD），超出则说明是负数，需要减去 n 才得到真正的结果。密文减法也需要用到模逆运算，通过密文减法的公式（ $c=\frac{c_1}{c_2} \space mod\space n^2=c_1c_2^{-1}\space mod\space n^2$ ）得知， $c_2$ 需要进行模逆运算（BN_mod_inverse）再与 $c_1$ 相乘。详情请查阅代码：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

用法&例子

demo 程序

paillier_test.c
#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;
}

编译和运行

先确保 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

编译 demo 程序

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

生成 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

运行结果

$ ./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 支持半同态加密算法 EC-ElGamal

2022年10月11日 · 阅读需 17 分钟

Jin Jiu

Maintainer of Tongsuo

背景

随着大数据与人工智能的快速发展，个人隐私数据泄露和滥用时有发生，隐私安全问题也越来越被重视，国家于 2020 年施行密码法、2021 年施行个人信息保护法，对个人隐私数据和数据安全加密有更高的要求。因此，隐私计算也不断地被提及和关注，源于其有优秀的数据保护作用，使得『数据不出域、可用不可见』，限定了数据的使用场景，防止了数据的泄露，而引起了业界的热捧。隐私计算是指在保护数据本身不对外泄露的前提下，实现数据共享和计算的技术集合，共享数据价值，而非源数据本身，实现数据可用不可见。隐私计算对于个人用户来说，有助于保障个人信息安全；对于企业来说，隐私计算是数据协作过程中履行数据保护义务的关键路径；对于政府来说，隐私计算实现数据价值最大化的重要支撑。

隐私计算目前在金融、医疗、电信、政务等领域均在开展应用试验，比如：

银行和金融机构在不泄露各方原始数据的前提下，进行分布式模型训练，可以有效降低信贷、欺诈等风险；
医疗机构无需共享原始数据便可进行联合建模和数据分析，数据使用方在不侵犯用户隐私的情况下，可以使用建模运算结果数据，有效推动医疗行业数据高效利用；
……

隐私计算的相关技术有多方安全计算（MPC）、可信执行环境（TEE）、联邦学习（FL）、同态加密（HE）、差分隐私（DP）、零知识证明（ZKP）、区块链（BC）等等。这些技术各有优缺点，隐私计算的产品或者平台也是由这些技术来搭建。

其中与密码学明显相关的是同态加密，目前同态加密算法的开源项目各有千秋，用户使用比较复杂。Tongsuo 作为基础密码库，应该提供一套简单易用和高效的同态加密算法实现和接口，让上层应用更方便简单地使用同态加密算法。

此外，随着隐私计算技术的兴起，蚂蚁集团推出了开箱即用、软硬件结合的隐私计算基础设施，一站式解决方案，即可信原生一体机。Tongsuo 作为蚂蚁可信原生一体机中的核心基础软件密码库，将同态加密等隐私计算所需的相关密码学能力整合其中，为可信原生一体机的用户带来更加便捷高效的使用体验。

同态加密

同态加密（Homomorphic Encryption, HE）是指满足密文同态运算性质的加密算法，按性质分为加法同态和乘法同态：

加法同态
1. 满足： $E(x) \oplus E(y)=E(x+y)$
2. 椭圆曲线加密算法满足加法同态：

$E(x)=g^x \longrightarrow E(x) \oplus E(y)=g^x g^y = g^{x+y} = E(x+y)$

乘法同态
1. 满足： $E(x) \otimes E(y)=E(xy)$
2. RSA加密算法满足乘法同态：

$E(x)=x^e \longrightarrow E(x) \otimes E(y)=x^e y^e = (xy)^e = E(xy)$ 同态加密后得到密文数据，对密文数据进行同态加法或者乘法得到密文结果，将密文结果同态解密后可以得到原始数据直接加法或者乘法的计算结果，如下图：根据满足加法和乘法的运算次数又分为：全同态加密和半同态加密

全同态加密（ Fully Homomorphic Encryption, FHE ）
- 支持任意次的加法和乘法运算
- 难实现、性能差（密钥过大，运行效率低，密文过大）
- 主流算法：Gentry、BFV、BGV、CKKS
- 需要实现的接口：（非本文重点，略）
半同态加密（Partially Homomorphic Encryption, PHE）
- 只支持加法或乘法中的一种运算，或者可同时支持有限次数的加法和乘法运算
- 原理简单、易实现、性能好
- 主流算法：RSA、ElGamal、Paillier
- 需要实现的接口：
  - KeyGen()：密钥生成算法，用于产生加密数据的公钥 PK（Public Key）和私钥 SK（Secret Key），以及一些公共参数 PP（Public Parameter）。
  - Encrypt()：加密算法，使用 PK 对用户数据 Data 进行加密，得到密文 CT（Ciphertext）。
  - Decrypt()：解密算法，使用 SK 对密文 CT 解密得到数据原文 PT（Plaintext）。
  - Add()：密文同态加法，输入两个 CT 进行同态加运算。
  - Sub()：密文同态减法，输入两个 CT 进行同态减法算。
  - ScalaMul() 或者 Mul()：密文同态标量乘法，输入一个 CT 和一个标量 PT，计算 CT 的标量乘结果。

EC-ElGamal 原理

ElGamal 加密算法是基于 Diffie-Hellman 密钥交换的非对称加密算法，EC-ElGamal 是 ECC 的一种，是把ElGamal 移植到椭圆曲线上来的实现，主要计算有：椭圆曲线点加、点减、点乘、模逆和离散对数。

以下是 EC-ElGamal 的算法原理：

公共参数：
- G：椭圆曲线基点
- SK：私钥，SK=d，d 是 0 到椭圆曲线的阶 q 之间的随机数
- PK：公钥，PK=dG
加密
- 明文 m，随机数 r
- 计算密文 C： $C=Encrypt(m,r)=(rG,rPK+mG)$
- 明文 m 的取值范围为模 order(G) 的模空间，但实际使用时 m 需限制为较小的数（例如 32 比特长度），否则椭圆曲线离散对数问题（ECDLP）无法求解。
解密
- 计算 rPK： $𝑟𝑃𝐾=𝑟∗𝑑∗𝐺=𝑑∗𝑟𝐺=𝑑∗𝐶[0]=𝑆𝐾∗𝐶[0]$
- 计算 mG： $𝑚𝐺=𝑟𝑃𝐾+𝑚𝐺−𝑟𝑃𝐾=𝐶[1]−𝑟𝑃𝐾$
- 计算 mG 的 ECDLP，获得明文 m。
密文加法、密文减法
- 两个密文 $C_1 , C_2 \longrightarrow 𝐶_1=(𝑟_1 𝐺, 𝑟_1 𝑃𝐾+𝑚_1 𝐺), 𝐶_2=(𝑟_2 𝐺, 𝑟_2 𝑃𝐾+𝑚_2 𝐺)$
- 密文加：对 2 个密文的 2 个 ECC 点分别做点加，共 2 个点加，公式如下：
  - $𝐴𝑑𝑑(𝐶_1, 𝐶_2 )=(𝑟_1 𝐺+𝑟_2 𝐺, 𝑟_1 𝑃𝐾+𝑚_1 𝐺+𝑟_2 𝑃𝐾+𝑚_2 𝐺)=((𝑟_1+𝑟_2 )𝐺,(𝑟_1+𝑟_2 )𝑃𝐾+(𝑚_1+𝑚_2 )𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡((𝑚_1+𝑚_2 ),(𝑟_1+𝑟_2 ))$
  - 如上公式与明文 $m_1+m_2$ 的同态加密结果一致： $Encrypt((m_1+m_2), r)$ ，这里 $r=r_1+r_2$
- 密文减：对 2 个密文的 2 个 ECC 点分别做点减，共 2 个点减，公式如下：
  - $𝑆𝑢𝑏(𝐶_1,𝐶_2 )=(𝑟_1 𝐺−𝑟_2 𝐺,𝑟_1 𝑃𝐾+𝑚_1 𝐺−𝑟_2 𝑃𝐾−𝑚_2 𝐺)$ $=((𝑟_1−𝑟_2 )𝐺,(𝑟_1−𝑟_2 )𝑃𝐾+(𝑚_1−𝑚_2 )𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡((𝑚_1−𝑚_2 ),(𝑟_1−𝑟_2 ))$
  - 如上公式与明文 $m_1-m_2$ 的同态加密结果一致： $Encrypt((m_1-m_2), r)$ ，这里 $r=r_1-r_2$
密文标量乘法
- 密文： $𝐶_1=(𝑟_1 𝐺, 𝑟_1 𝑃𝐾+𝑚_1 𝐺)$ ，明文： $𝑚_2$
- 对密文的 2 个 ECC 点分别用 𝑚_2 做点乘，共 2 个点乘，公式如下：
  - $𝑀𝑢𝑙(𝐶_1, 𝑚_1 )=(𝑚_2 𝑟_1 𝐺, 𝑚_2 (𝑟_1 𝑃𝐾+𝑚_1 𝐺))$ $=(𝑚_2 𝑟_1 𝐺, 𝑚_2 𝑟_1 𝑃𝐾+𝑚_2 𝑚_1 𝐺)=𝐸𝑛𝑐𝑟𝑦𝑝𝑡(𝑚_2 𝑚_1, 𝑚_2 𝑟_1)$
- 如上公式与明文 $m_2m_1$ 的同态加密结果一致： $Encrypt(m_2m_1, r)$ ，这里 $r=m_2r_1$

算法实现

接口定义

对象相关接口

上下文对象：EC_ELGAMAL_CTX，该对象用来保存公私钥以及一些其他内部用到的信息，是 EC-ElGamal 算法其他接口的第一个参数。接口如下：

//创建 EC_ELGAMAL_CTX 对象，key 为 ECC 公钥或者私钥的 EC_KEY 对象
EC_ELGAMAL_CTX *EC_ELGAMAL_CTX_new(EC_KEY *key);

//释放 EC_ELGAMAL_CTX 对象
void EC_ELGAMAL_CTX_free(EC_ELGAMAL_CTX *ctx);

解密表对象：EC_ELGAMAL_DECRYPT_TABLE，该对象用来保存解密表的内部信息。椭圆曲线离散对数问题（ECDLP）只有爆力破解的方法可求解，而爆力破解的速度比较慢，通常的做法是使用小步大步算法（Baby-Step，Giant-Step，BSGS）。总体思想是提前将所有可能的明文结果提前运算后，保存到 hash 表中，下次只需要进行少量的运算和 hash 表查找就可以得到结果，大大提高 ECDLP 的解密效率，但解密表的初始化可能比较慢，而且解密表的实现事关解密速度，后面考虑可以开放接口的实现给上层应用，所以这里先定义了一个解密表的对象和默认实现。接口如下：

//创建 EC_ELGAMAL_DECRYPT_TABLE 对象
//decrypt_negative 为 1 时表示该解密表可以解密负数，初始化解密表时将可能的负数运算后插入到 hash 中。
EC_ELGAMAL_DECRYPT_TABLE *EC_ELGAMAL_DECRYPT_TABLE_new(EC_ELGAMAL_CTX *ctx,
                                                    int32_t decrypt_negative);

//释放 EC_ELGAMAL_DECRYPT_TABLE 对象
void EC_ELGAMAL_DECRYPT_TABLE_free(EC_ELGAMAL_DECRYPT_TABLE *table);

//设置 EC_ELGAMAL_DECRYPT_TABLE 对象到上下文对象中
//解密时如果存在解密表则使用解密表进行求解，否则直接爆力破解，速度会很慢
void EC_ELGAMAL_CTX_set_decrypt_table(EC_ELGAMAL_CTX *ctx,
                                    EC_ELGAMAL_DECRYPT_TABLE *table);

密文对象：EC_ELGAMAL_CIPHERTEXT，由上面原理可知，加密之后得到的结果是两个点，该对象是用来保存加密后的密文信息（两个点）。接口如下：

//创建 EC_ELGAMAL_CIPHERTEXT 对象
EC_ELGAMAL_CIPHERTEXT *EC_ELGAMAL_CIPHERTEXT_new(EC_ELGAMAL_CTX *ctx);

//释放 EC_ELGAMAL_CIPHERTEXT 对象
void EC_ELGAMAL_CIPHERTEXT_free(EC_ELGAMAL_CIPHERTEXT *ciphertext);

加密/解密接口

//加密，将明文 plaintext 进行加密，结果保存到 EC_ELGAMAL_CIPHERTEXT 对象指针 r 中
int EC_ELGAMAL_encrypt(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r, int32_t plaintext);

//解密，将密文 ciphertext 进行解密，结果保存到 int32_t 指针 r 中
int EC_ELGAMAL_decrypt(EC_ELGAMAL_CTX *ctx, int32_t *r, EC_ELGAMAL_CIPHERTEXT *ciphertext);

密文加/减/标量乘运算接口

//密文加，r = c1 + c2
int EC_ELGAMAL_add(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,
                EC_ELGAMAL_CIPHERTEXT *c1, EC_ELGAMAL_CIPHERTEXT *c2);

//密文减，r = c1 - c2
int EC_ELGAMAL_sub(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,
                EC_ELGAMAL_CIPHERTEXT *c1, EC_ELGAMAL_CIPHERTEXT *c2);

//标量密文乘，r = m * c
int EC_ELGAMAL_mul(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,
                EC_ELGAMAL_CIPHERTEXT *c, int32_t m);

编码/解码接口

同态加密涉及到多方参与，可能会需要网络传输，这就将密文对象 EC_ELGAMAL_CIPHERTEXT 编码后才能传递给对方，对方也需要解码得到 EC_ELGAMAL_CIPHERTEXT 对象后才能调用其他接口进行运算。

接口如下：

//编码，将密文 ciphertext 编码后保存到 out 指针中，out 指针的内存需要提前分配好；
//如果 out 为 NULL，则返回编码所需的内存大小；
//compressed 为是否采用压缩方式编码，1 为压缩编码（编码结果长度较小），0 为正常编码（编码结果长度较大）
size_t EC_ELGAMAL_CIPHERTEXT_encode(EC_ELGAMAL_CTX *ctx, unsigned char *out,
                                    size_t size, EC_ELGAMAL_CIPHERTEXT *ciphertext,
                                    int compressed);

//解码，将长度为 size 的内存数据 in 解码后保存到密文对象 r 中
int EC_ELGAMAL_CIPHERTEXT_decode(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,
                                 unsigned char *in, size_t size);

核心实现

Tongsuo 是 OpenSSL 的衍生版，内部支持了很多椭圆曲线算法的实现。比如，已支持国际（prime256v1、secp384r1 等）和国密（SM2）的大部分椭圆曲线，天生实现了椭圆曲线点运算、公私钥生成等基础算法，所以在 Tongsuo 实现 EC-ElGamal 算法的核心实现主要是 EC-ElGamal 原理的实现和 ECDLP 求解算法的实现，总共几百行代码，查看代码请移步 github：https://github.com/Tongsuo-Project/Tongsuo/blob/master/crypto/ec/ec_elgamal.c

用法&例子

demo 程序

#include <stdio.h>
#include <time.h>
#include <openssl/ec.h>
#include <openssl/pem.h>

#define CLOCKS_PER_MSEC (CLOCKS_PER_SEC/1000)

int main(int argc, char *argv[])
{
    int ret = -1;
    uint32_t r;
    clock_t begin, end;
    EC_KEY *sk_eckey = NULL, *pk_eckey = NULL;
    EC_ELGAMAL_CTX *ctx1 = NULL, *ctx2 = NULL;
    EC_ELGAMAL_CIPHERTEXT *c1 = NULL, *c2 = NULL, *c3 = NULL;
    EC_ELGAMAL_DECRYPT_TABLE *table = NULL;
    FILE *pk_file = fopen("ec-pk.pem", "rb");
    FILE *sk_file = fopen("ec-sk.pem", "rb");

    if ((pk_eckey = PEM_read_EC_PUBKEY(pk_file, NULL, NULL, NULL)) == NULL)
        goto err;
    if ((sk_eckey = PEM_read_ECPrivateKey(sk_file, NULL, NULL, NULL)) == NULL)
        goto err;

    if ((ctx1 = EC_ELGAMAL_CTX_new(pk_eckey)) == NULL)
        goto err;
    if ((ctx2 = EC_ELGAMAL_CTX_new(sk_eckey)) == NULL)
        goto err;

    begin = clock();
    if ((table = EC_ELGAMAL_DECRYPT_TABLE_new(ctx2, 0)) == NULL)
        goto err;

    EC_ELGAMAL_CTX_set_decrypt_table(ctx2, table);
    end = clock();
    printf("EC_ELGAMAL_DECRYPT_TABLE_new(1) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);
    
    if ((c1 = EC_ELGAMAL_CIPHERTEXT_new(ctx1)) == NULL)
        goto err;
    if ((c2 = EC_ELGAMAL_CIPHERTEXT_new(ctx1)) == NULL)
        goto err;

    begin = clock();
    if (!EC_ELGAMAL_encrypt(ctx1, c1, 20000021))
        goto err;
    end = clock();
    printf("EC_ELGAMAL_encrypt(20000021) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

    begin = clock();
    if (!EC_ELGAMAL_encrypt(ctx1, c2, 500))
        goto err;
    end = clock();
    printf("EC_ELGAMAL_encrypt(500) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

    if ((c3 = EC_ELGAMAL_CIPHERTEXT_new(ctx1)) == NULL)
        goto err;

    begin = clock();
    if (!EC_ELGAMAL_add(ctx1, c3, c1, c2))
        goto err;
    end = clock();
    printf("EC_ELGAMAL_add(C2000021,C500) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

    begin = clock();
    if (!(EC_ELGAMAL_decrypt(ctx2, &r, c3)))
        goto err;
    end = clock();
    printf("EC_ELGAMAL_decrypt(C20000021,C500) result: %d, cost: %lfms\n", r, (double)(end - begin)/CLOCKS_PER_MSEC);

    begin = clock();
    if (!EC_ELGAMAL_mul(ctx1, c3, c2, 800))
        goto err;
    end = clock();
    printf("EC_ELGAMAL_mul(C500,800) cost: %lfms\n", (double)(end - begin)/CLOCKS_PER_MSEC);

    begin = clock();
    if (!(EC_ELGAMAL_decrypt(ctx2, &r, c3)))
        goto err;
    end = clock();
    printf("EC_ELGAMAL_decrypt(C500,800) result: %d, cost: %lfms\n", r, (double)(end - begin)/CLOCKS_PER_MSEC);

    
    printf("EC_ELGAMAL_CIPHERTEXT_encode size: %zu\n", EC_ELGAMAL_CIPHERTEXT_encode(ctx2, NULL, 0, NULL, 1));
    
    ret = 0;
err:
    EC_KEY_free(sk_eckey);
    EC_KEY_free(pk_eckey);
    EC_ELGAMAL_DECRYPT_TABLE_free(table);
    EC_ELGAMAL_CIPHERTEXT_free(c1);
    EC_ELGAMAL_CIPHERTEXT_free(c2);
    EC_ELGAMAL_CIPHERTEXT_free(c3);
    EC_ELGAMAL_CTX_free(ctx1);
    EC_ELGAMAL_CTX_free(ctx2);
    fclose(sk_file);
    fclose(pk_file);
    return ret;
}

编译和运行

先确保 Tongsuo 开启 ec_elgamal，如果是手工编译 Tongsuo，可参考如下编译步骤：

# 下载代码
git clone git@github.com:Tongsuo-Project/Tongsuo.git


# 编译参数需要加上：enable-ec_elgamal，我这里是在 macOS 系统上编译，所以是 darwin64-x86_64-cc，其他系统需要切换一下
./Configure darwin64-x86_64-cc --debug no-shared no-threads enable-ec_elgamal --strict-warnings -fPIC --prefix=/usr/local/tongsuo-debug

# 编译
make -j4

# 安装到目录 /usr/local/tongsuo-debug 
sudo make install

编译 demo 程序

gcc -Wall -g -o ec_elgamal_test ./ec_elgamal_test.c -I/usr/local/tongsuo-debug/include -L/usr/local/tongsuo-debug/lib -lssl -lcrypto

生成 ECC 公私钥

# 先生成私钥，这里生成的是 SM2 曲线的私钥
/usr/local/tongsuo-debug/bin/openssl ecparam -genkey -name SM2 -out ec-sk.pem
# 用私钥生成公钥
/usr/local/tongsuo-debug/bin/openssl ec -in ./ec-sk.pem -pubout -out ec-pk.pem

运行结果

$ ./ec_elgamal_test
EC_ELGAMAL_DECRYPT_TABLE_new(0) cost: 2557.715000ms
EC_ELGAMAL_encrypt(20000021) cost: 1.448000ms
EC_ELGAMAL_encrypt(500) cost: 1.605000ms
EC_ELGAMAL_add(C2000021,C500) cost: 0.014000ms
EC_ELGAMAL_decrypt(C20000021,C500) result: 20000521, cost: 12.748000ms
EC_ELGAMAL_mul(C500,800) cost: 1.562000ms
EC_ELGAMAL_decrypt(C500,800) result: 400000, cost: 1.137000ms
EC_ELGAMAL_CIPHERTEXT_encode size: 66

注意事项

EC_ELGAMAL_DECRYPT_TABLE_new 函数第二个参数指定是否支持负数解密，如果支持负数解密会影响解密性能，因为查询解密表的次数变多了，以及点的运算变多了，同时构造支持负数的解密表需要的时间也比较长，如下是支持负数解密的运行结果：

$ ./ec_elgamal_test
EC_ELGAMAL_DECRYPT_TABLE_new(1) cost: 99023.542000ms
EC_ELGAMAL_encrypt(20000021) cost: 1.451000ms
EC_ELGAMAL_encrypt(500) cost: 1.426000ms
EC_ELGAMAL_add(C2000021,C500) cost: 0.021000ms
EC_ELGAMAL_decrypt(C20000021,C500) result: 20000521, cost: 461.471000ms
EC_ELGAMAL_sub(C500,C2000021) cost: 0.025000ms
EC_ELGAMAL_decrypt(C500,C20000021) result: -19999521, cost: 830.430000ms
EC_ELGAMAL_mul(C500,800) cost: 1.568000ms
EC_ELGAMAL_decrypt(C500,800) result: 400000, cost: 261.117000ms
EC_ELGAMAL_CIPHERTEXT_encode size: 66

背景​

Paillier 原理​

密钥生成​

加密​

解密​

密文加法​

密文减法​

密文标量乘法​

正确性​

加解密正确性​

密文加法正确性​

密文减法正确性​

密文标量乘法正确性​

算法实现​

接口定义​

核心实现​

用法&例子​

demo 程序​

编译和运行​

编译 demo 程序​

生成 Paillier 公私钥​

运行结果​

背景​

同态加密​

EC-ElGamal 原理​

算法实现​

接口定义​

核心实现​

用法&例子​

demo 程序​

编译和运行​

背景

Paillier 原理

密钥生成

加密

解密

密文加法

密文减法

密文标量乘法

正确性

加解密正确性

密文加法正确性

密文减法正确性

密文标量乘法正确性

算法实现

接口定义

核心实现

用法&例子

demo 程序

编译和运行

编译 demo 程序

生成 Paillier 公私钥

运行结果

背景

同态加密

EC-ElGamal 原理

算法实现

接口定义

核心实现

用法&例子

demo 程序

编译和运行