关于隐私:BabaSSL支持半同态加密算法-ECElGamal

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

蚂蚁团体开发工程师\
负责蚂蚁 Kubernetes 集群容器交付专一于集群交付能力、交付性能及交付 Trace 等相干畛域

本文 3063 字 浏览 5 分钟

—— 数据不出域、可用不可见

01 背 景

随着大数据与人工智能的疾速倒退，个人隐私数据泄露和滥用时有发生，隐衷平安问题也越来越被器重。

国家于 2020 年实施明码法、2021 年实施个人信息保护法，对个人隐私数据和数据安全加密有更高的要求。

因而，隐衷计算也一直地被提及和关注，源于其有优良的数据保护作用，使得『数据不出域、可用不可见』，限定了数据的应用场景，避免了数据的泄露，而引起了业界的热捧。

隐衷计算是指在爱护数据自身不对外泄露的前提下，实现数据共享和计算的技术汇合，共享数据价值，而非源数据自身，实现数据可用不可见。

• 隐衷计算对于个人用户来说，有助于保障集体信息安全；
• 对于企业来说，隐衷计算是数据合作过程中履行数据保护任务的要害门路；
• 对于政府来说，隐衷计算实现数据价值最大化的重要撑持。

隐衷计算目前在金融、医疗、电信、政务等畛域均在发展利用试验，比方：

• 银行和金融机构

在不泄露各方原始数据的前提下，进行分布式模型训练，能够无效升高信贷、欺诈等危险；

• 医疗机构

无需共享原始数据便可进行联结建模和数据分析，数据应用方在不进犯用户隐衷的状况下，能够应用建模运算后果数据，无效推动医疗行业数据高效利用。

隐衷计算的相干技术有多方平安计算 （MPC） 、可信执行环境 （TEE） 、联邦学习 （FL） 、同态加密 （HE） 、差分隐衷 （DP） 、零常识证实 （ZKP） 、区块链 （BC） 等等。

这些技术各有优缺点，隐衷计算的产品或者平台也是由这些技术来搭建。

其中与密码学显著相干的是同态加密，目前同态加密算法的开源我的项目各有千秋，用户应用比较复杂。BabaSSL 作为根底明码库，应该提供一套简略易用和高效的同态加密算法实现和接口，让下层利用更不便简略地应用同态加密算法。

此外，随着隐衷计算技术的衰亡，蚂蚁团体推出了开箱即用、软硬件联合的隐衷计算基础设施，一站式解决方案，即可信原生一体机。

BabaSSL 作为蚂蚁可信原生一体机中的外围根底软件明码库，将同态加密等隐衷计算所需的相干密码学能力整合其中，为可信原生一体机的用户带来更加便捷高效的应用体验。

02 同态加密

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

• 加法同态

• 乘法同态

同态加密后失去密文数据，对密文数据进行同态加法或者乘法失去密文后果，将密文后果同态解密后能够失去原始数据间接加法或者乘法的计算结果。

如下图：

依据满足加法和乘法的运算次数又分为：全同态加密和半同态加密。

- 全同态加密

（ Fully Homomorphic Encryption, FHE ）

1.反对任意次的加法和乘法运算

2.难实现、性能差 （密钥过大，运行效率低，密文过大）

3.支流算法：Gentry、BFV、BGV、CKKS

4.须要实现的接口

• 半同态加密

（Partially Homomorphic Encryption, PHE）

1.只反对加法或乘法中的一种运算，或者可同时反对无限次数的加法和乘法运算

2.原理简略、易实现、性能好

3.支流算法：RSA、ElGamal、Paillier

4.须要实现的接口：

（1）KeyGen()： 密钥生成算法，用于产生加密数据的公钥 PK（ Public Key）和私钥 SK（Secret Key），以及一些公共参数 PP（Public Parameter）。\
 

（2）Encrypt()： 加密算法，应用 PK 对用户数据 Data 进行加密，失去密文 CT（Ciphertext）。

（3）Decrypt()： 解密算法，应用 SK 对密文 CT 解密失去数据原文 PT（Plaintext）。

（4）Add()： 密文同态加法，输出两个 CT 进行同态加运算。

（5）Sub()： 密文同态减法，输出两个 CT 进行同态减法算。

（6）ScalaMul() 或者 Mul() ：密文同态标量乘法，输出一个 CT 和一个标量 PT，计算 CT 的标量乘后果。

EC-ElGamal 原理

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

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

- 公共参数

1.G：椭圆曲线基点\
 

2.SK：私钥，SK=d

（d 是 0 到椭圆曲线的阶 q 之间的随机数）

3.PK：公钥，PK=dG

- 加密

1.明文 m，随机数 r

2.计算密文 C：

（3）明文 m 的取值范畴为模 order(G) 的模空间，但理论应用时 m 需限度为较小的数 （例如 32 比特长度） ，否则椭圆曲线离散对数问题 （ECDLP） 无奈求解。

-解密\
 

1.计算 rPK：\
 

2.计算 mG：\

3.计算 mG 的 ECDLP，取得明文 m。\
 

- 密文加法、密文减法

1.两个密文：

2 .密文加：

对 2 个密文的 2 个 ECC 点别离做点加，共 2 个点加，公式如下：\
 

3.密文减：

对 2 个密文的 2 个 ECC 点别离做点减，共 2 个点减，公式如下：\
 

- 密文标量乘法

1.密文

2.对密文的 2 个 ECC 点别离用 _2 做点乘，共 2 个点乘，公式如下：

3.如上公式与明文m2m1的同态加密后果统一：

这里 r=m2r1

03 算法实现

接口定义

• 对象相干接口

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

接口如下：

//创立 EC_ELGAMAL_CTX 对象，key 为 ECC 公钥或者私钥的 EC_KEY 对象

2.解密表对象：

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);

3.密文对象：

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);

4.加密/解密接口

//加密，将明文 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);

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

//密文加，r = c1 + c2int EC_ELGAMAL_add(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,                   EC_ELGAMAL_CIPHERTEXT *c1, EC_ELGAMAL_CIPHERTEXT *c2);//密文减，r = c1 - c2int EC_ELGAMAL_sub(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,                   EC_ELGAMAL_CIPHERTEXT *c1, EC_ELGAMAL_CIPHERTEXT *c2);//标量密文乘，r = m * cint EC_ELGAMAL_mul(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r,                   EC_ELGAMAL_CIPHERTEXT *c, int32_t m);

6.编码/解码接口

同态加密波及到多方参加，可能会须要网络传输，这就将密文对象 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);

外围实现

BabaSSL 是 OpenSSL 的衍生版，外部反对了很多椭圆曲线算法的实现。

 比方，已反对国内 （prime256v1、secp384r1 等） 和国密 （SM2） 的大部分椭圆曲线，天生实现了椭圆曲线点运算、公私钥生成等根底算法，所以在 BabaSSL 实现 EC-ElGamal 算法的外围实现次要是 EC-ElGamal 原理的实现和 ECDLP 求解算法的实现。

因为代码过长，查看代码辛苦移步 GitHub：

https://github.com/BabaSSL/Ba...

具体的应用办法和案例，能够点击查看