密码学的数学基础2-Paillier为什么产生密钥对比RSA慢
用到的算法
Paillier 同态加密算法的密钥生成相对较慢，主要原因如下：
1. 需要生成两个大素数（p, q）
Paillier 加密系统的安全性基于大整数分解问题和复合剩余类困难问题。
密钥生成的第一步是生成两个大素数 ppp 和 qqq，通常需要 1024-bit 或更高的长度（如 2048-bit）。
- 素数生成较慢：需要使用素性检测算法（如 Miller-Rabin），这些算法通常需要多个迭代来确定一个数是否为素数。
- 两个素数乘积：N=p⋅qN = p \cdot qN=p⋅q 需要保证 NNN 不可分解，这需要额外的检查步骤。
2. 计算 λ=lcm(p−1,q−1)\lambda = \text{lcm}(p-1, q-1)λ=lcm(p−1,q−1)
- 计算最小公倍数（LCM）： λ=lcm(p−1,q−1)\lambda = \text{lcm}(p-1, q-1)λ=lcm(p−1,q−1) 需要使用 最大公因数（GCD）算法 来计算 LCM，计算量较大。
3. 计算公钥参数 ggg
- 选择 ggg 需要满足特定的数学性质： g≡1+NmodN2g \equiv 1 + N \mod N^2g≡1+NmodN2 这个步骤本身较快，但在某些变种（如 Paillier threshold encryption）中，可能需要更多计算来确定合适的 ggg。
4. 需要大量大整数运算
- Paillier 采用 大整数模运算（mod N²），计算比 RSA 复杂，导致生成密钥比 RSA 慢。
如何优化？
1️⃣ 使用高效素数生成算法（如 OpenSSL BIGNUM 库的素数生成优化）。
2️⃣ 并行计算 ppp 和 qqq，同时运行两个线程分别寻找素数。
3️⃣ 预计算大素数，减少实时生成的开销（适用于批量密钥生成）。
对比：Paillier vs. RSA 密钥生成速度
- RSA 密钥生成：O(n3)O(n^3)O(n3)，主要是素数生成和模运算。
- Paillier 密钥生成：O(n4)O(n^4)O(n4)，因为它涉及 N2N^2N2 的运算，比 RSA 慢。
所以，Paillier 密钥生成比 RSA 更慢，但加解密速度相当。
Paillier 密钥生成过程
RSA 密钥生成过程
附录
椭圆曲线（ECC）密钥生成过程
椭圆曲线密码学基于椭圆曲线上的点运算。设定一个椭圆曲线 EEE 和一个素数 ppp，椭圆曲线上的点满足以下方程：
y2=x3+ax+bmodpy^2 = x^3 + ax + b \mod py2=x3+ax+bmodp
其中 aaa 和 bbb 是曲线参数。ECC 的安全性基于椭圆曲线离散对数问题（ECDLP）的难度，即给定点 PPP 和点 QQQ，找出 kkk 使得 Q=kPQ = kPQ=kP 是困难的。
- 往期精彩回顾:
- 区块链知识系列
- 密码学系列
- 零知识证明系列
- 共识系列
- 公链调研系列
- BTC系列
- 以太坊系列
- EOS系列
- Filecoin系列
- 联盟链系列
- Fabric系列
- 智能合约系列
- Token系列