BabaSSL：支持半同态加密算法 EC-ElGamal

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

蚂蚁集团开发工程师
担任蚂蚁 Kubernetes 集群容器交付专心于集群交付才干、交付性能及交付 Trace 等相关领域

本文 3063 ****字 阅览 5 ****分钟

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

01 背 景

跟着大数据与人工智能的快速发展，个人隐私数据走漏和滥用时有发生，隐私安全问题也越来越被注重。

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

BabaSSL：支持半同态加密算法 EC-ElGamal

因而，隐私核算也不断地被提及和关注，源于其有优异的数据保护作用，使得**『数据不出域、可用不行见』**，限定了数据的运用场景，防止了数据的走漏，而引起了业界的热捧。

隐私核算是指在保护数据自身不对外走漏的前提下，完成数据同享和核算的技能调集，同享数据价值，而非源数据自身，完成数据可用不行见。

  • 隐私核算关于个人用户来说，有助于保证个人信息安全；

  • 关于企业来说，隐私核算是数据协作过程中履行数据保护责任的关键路径；

  • 关于政府来说，隐私核算完成数据价值最大化的重要支撑。

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

  • 银行和金融机构

在不走漏各方原始数据的前提下，进行分布式模型练习，能够有效下降信贷、欺诈等风险；

  • 医疗机构

无需同享原始数据便可进行联合建模和数据分析，数据运用方在不侵略用户隐私的情况下，能够运用建模运算成果数据，有效推动医疗行业数据高效运用。

隐私核算的相关技能有多方安全核算 （MPC） 、可信履行环境 （TEE） 、联邦学习 （FL） 、同态加密 （HE） 、差分隐私 （DP） 、零知识证明 （ZKP） 、区块链 （BC） 等等。

这些技能各有优缺点，隐私核算的产品或许渠道也是由这些技能来建立。

其中与暗码学明显相关的是同态加密，目前同态加密算法的开源项目各有千秋，用户运用比较复杂。BabaSSL 作为根底暗码库，应该供给一套简略易用和高效的同态加密算法完成和接口，让上层运用更方便简略地运用同态加密算法。

此外，跟着隐私核算技能的鼓起，蚂蚁集团推出了开箱即用、软硬件结合的隐私核算根底设施，一站式解决方案，即可信原生一体机。

BabaSSL 作为蚂蚁可信原生一体机中的中心根底软件暗码库，将同态加密等隐私核算所需的相关暗码学才干整合其中，为可信原生一体机的用户带来更加便捷高效的运用体验。

02 同态加密

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

  • 加法同态

BabaSSL：支持半同态加密算法 EC-ElGamal

  • 乘法同态

BabaSSL：支持半同态加密算法 EC-ElGamal

同态加密后得到密文数据，对密文数据进行同态加法或许乘法得到密文成果，将密文成果同态解密后能够得到原始数据直接加法或许乘法的核算成果。

如下图：

BabaSSL：支持半同态加密算法 EC-ElGamal

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

– 全同态加密

（ 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：

BabaSSL：支持半同态加密算法 EC-ElGamal

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

–解密

1.核算 rPK：

BabaSSL：支持半同态加密算法 EC-ElGamal

2.核算 mG：\

BabaSSL：支持半同态加密算法 EC-ElGamal

3.核算 mG 的 ECDLP，获得明文 m。

–密文加法、密文减法

1.两个密文：

BabaSSL：支持半同态加密算法 EC-ElGamal

2 .密文加：

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

BabaSSL：支持半同态加密算法 EC-ElGamal

3.密文减：

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

BabaSSL：支持半同态加密算法 EC-ElGamal

BabaSSL：支持半同态加密算法 EC-ElGamal

–密文标量乘法

1.密文

BabaSSL：支持半同态加密算法 EC-ElGamal

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

BabaSSL：支持半同态加密算法 EC-ElGamal

3.如上公式与明文m2m1的同态加密成果共同：

BabaSSL：支持半同态加密算法 EC-ElGamal

这里 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 + 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);

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：

github.com/BabaSSL/Bab…

详细的运用方法和案例，能够点击检查。