# Paillier加法同态加密

Paillier公钥加密方案是目前最实用的加法同态加密方案，很多安全方案和密码协议都采用Paillier算法作为同态加密方案。GmSSL项目从版本2.4开始支持Paillier同态加密。

给定Paillier的公私钥对为$(pk, sk)$，Paillier模块支持两种密文计算：

* 密文加法，明文$a_1, a_2$是两个整数，$c_1 = Enc_{pk}(a_1)$和$c_2 = Enc_{pk}(a_2)$是用公钥$pk$加密后得到的密文，密文加法可以计算得到$c_1, c_2$的密文和$c$，即$c$满足$Dec_{sk}(c) = a_1 + a_2$；
* 密文标量乘法：给定明文$a_1$的密文$c_1 = Enc_{pk}(a_1)$和一个整数$k$，密文标量计算得到$k \cdot a_1$的密文$c$，满足$Dec_{sk}(c) = k \cdot a_1$，标量乘法运算上相当于密文的$k$次累加。

Paillier算法基于于整数分解问题，GmSSL中Paillier的密钥比特长度等同于RSA算法的密钥长度，即$N$的长度，其中$N = pq$，通常选择至少为2048比特。由于Paillier的明文和密文都在模$N^2​$的集合中，因此当在GmSSL中选择Paillier密钥长度为2048比特时，明文和密文的长度为4096比特，或512字节。

## 命令行

GmSSL的同态加密功能在命令行工具中由命令`genpkey`、`pkey`、`pkeyutl`提供。通过通用的`genpkey`命令可以生成Paillier私钥，如下所示：

```bash
$ gmssl genpkey -algorithm PAILLIER -sms4 -out pai.pem
```

说明：

* 选项`-algorithm PAILLIER`指定生成Paillier私钥；
* 命令`genpkey`默认会生成相当于$N​$为2048比特的Paillier私钥；
* 参数`-sms4`指定输出采用SM4/SM3加密和完整性保护的私钥文件；
* 用户应选择具有足够强度的口令用于加密Paillier私钥。

通过`pkey`命令可以从私钥中导出对应的公钥，通常可以将导出的公钥上传至执行密文运算的云端服务器环境：

```bash
$ gmssl pkey -in pai.pem -pubout -out paiPub.pem
$ gmssl pkey -text -pubin -in paiPub.pem
```

Paillier加密算法应该仅用于加密数值型的数据，例如：

```bash
$ echo 1111 | gmssl pkeyutl -encrypt -pubin -inkey paiPub.pem -out enced.bin
$ echo 2222 | gmssl pkeyutl -encrypt -pubin -inkey paiPub.pem >> enced.bin
$ echo 3333 | gmssl pkeyutl -encrypt -pubin -inkey paiPub.pem >> enced.bin
```

对所有的密文求和：

```bash
$ gmssl paiutl -add -in enced.bin -pubin -inkey paiPub.pem -out sum.bin
```

注意

1. 目前要求输入为至少2条密文，否则会出错
2. 如果输入包含超过2条密文，那么密文加会计算所有输入密文条目的密文和，生成一条单一的密文。

密文标量乘法：

```bash
$ gmssl paiutl -scalar_mul 5 -in sum.bin -pubin -inkey paiPub.pem -out product.bin
```

注意：

1. 如果输入包含N条密文，那么也会输出N条密文，输出条目为对应输入条目的标量乘法结果。

解密：

```bash
$ gmssl pkeyutl -decrypt -in product.bin -inkey pai.pem
```

解密的结果应该为$(1111 + 2222 + 3333) \times 5 = 33330​$。

注意：

1. `paiutl`是可以处理输入中包含多条密文，`paiutl -scalar_mul`也可能产生包含多条密文的输出，但是由于`pkeyutl`只能处理单条输入，因此无法正确解密此类密文。