paillier cryptosystem

原理

第一种参数模式

随机选择两个大质数$p, q$，满足$\gcd(pq, (p-1)(q-1))=1$。
计算

$n = p \cdot q$

$\lambda = \mathrm{lcm}(p-1, q-1) = \frac{(p-1)(q-1)}{\gcd(p-1, q-1)}$

选择随机整数$g$， 满足$0 < g < n^2$。
定义函数

$L(x) = \frac{x - 1}{n}$

计算

$\mu = \bigl(L(g^{\lambda} \bmod n^2)\bigr)^{-1} \bmod n$

则公钥为$(n, g)$，私钥为$(\lambda, \mu)$

第二种参数模式

其余参数不变，主要改变了$g, \quad \lambda, \quad \mu$的定义：

$g = n + 1$

$\lambda = \varphi(n) = (p-1)(q-1)$

$\mu = \varphi(n)^{-1} \bmod n$

加密过程

设消息为$m$，需满足$0 \le m < n$。选择随机数$r$，满足$\gcd(r, n) = 1$。
计算密文

$c = g^m \cdot r^n \bmod n^2$

解密过程（Decryption）

计算

$m = \left(L\left(c^{\lambda} \bmod n^2\right) \cdot \mu \right) \bmod n$

Proof

第一种参数模式

由解密公式

$m = L\bigl(c^{\lambda} \bmod n^2 \bigr) \cdot \mu \bmod n$

又

$c = g^m \cdot r^n \bmod n^2 ,\mu = \bigl( L(g^\lambda \bmod n^2) \bigr)^{-1} \bmod n$

代入得

$L\left( g^{m \lambda} \cdot r^{n \lambda} \bmod n^2 \right) \cdot L\left( g^{\lambda} \bmod n^2 \right)^{-1} \bmod n$

---

因为

$(p-1) \mid \lambda, \quad (q-1) \mid \lambda$

所以有

$\lambda = k_1 (p-1) = k_2 (q-1)$

则

$g^\lambda = g^{k_1 (p-1)} \equiv 1 \pmod p, \quad g^\lambda = g^{k_2 (q-1)} \equiv 1 \pmod q$

由中国剩余定理得

$g^\lambda \equiv 1 \pmod n$

所以

$g^\lambda \bmod n^2 = k_g n + 1, \quad k_g < n$

同理得到

$r^\lambda \bmod n^2 = k_r n + 1, \quad k_g < n$

因此

$L\left(g^\lambda \bmod n^2\right) = k_g$

---

又因为

$(1 + k n)^m \equiv 1 + k n \cdot m \pmod{n^2}$

所以有

$g^{m \lambda} =(k_g n +1)^{n \lambda} \equiv k_g n \cdot m +1 \pmod{n^2} \\ r^{n \lambda} =(k_r n +1)^{n \lambda} \equiv k_r n \cdot n +1 \equiv 1 \pmod{n^2}$

所以

$g^{m \lambda} \cdot r^{n \lambda} \equiv 1 + k_g n \cdot m \pmod{n^2}$

于是

$L\left(g^{m \lambda} \cdot r^{n \lambda} \bmod n^2\right) = k_g \cdot m$

综上得到：

$L\left( g^{m \lambda} \cdot r^{n \lambda} \bmod n^2 \right) \cdot L\left( g^{\lambda} \bmod n^2 \right)^{-1} \bmod n = k_g \cdot m \cdot k_g^{-1} \equiv m \pmod n$

即得到明文$m$。

第二种参数模式

由解密公式

$m = L\bigl(c^{\lambda} \bmod n^{2}\bigr) \cdot \mu \bmod n$

根据$\lambda = (p - 1) \cdot (q - 1)=\varphi(n), \quad \mu = \varphi(n)^{-1}=\lambda^{-1} \bmod n$可写为

$L\bigl(c^{\lambda} \bmod n^{2}\bigr) \cdot \mu \bmod n = L\bigl(g^{m \lambda} \cdot r^{n \lambda} \bmod n^{2}\bigr) \cdot \lambda^{-1} \bmod n$

其中

$\lambda = (p - 1) \cdot (q - 1), \quad \mu = \varphi(n)^{-1} \bmod n$

又根据欧拉函数的性质得

$r^{n \lambda} = r^{n (p-1)(q-1)} = r^{\varphi(n^{2})} \equiv 1 \pmod{n^{2}}$

由于$g = n + 1$，代入得

$g^{m \lambda} = (1 + n)^{m \lambda} \equiv 1 + n \cdot m \lambda \pmod{n^{2}}$

根据 $L(x) = \frac{x - 1}{n}$，则

$L\bigl(g^{m \lambda} \cdot r^{n \lambda} \bmod n^{2}\bigr)=L(1 + n \cdot m \lambda) = m \lambda$

所以原式等价于

$L\bigl(c^{\lambda} \bmod n^{2}\bigr)=m \lambda \cdot \lambda^{-1} \equiv m \pmod{n}$

即得到明文$m$。

例题

DASCTF四月月赛 not RSA

题目

from Crypto.Util.number import getPrime as bytes_to_long
from secret import flag,p,q
from sympy import isprime,nextprime
import random
m=bytes_to_long(flag)
n=p*q
g=n+1
r=random.randint(1,n)
c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)
print "c=%d"%(c)
print "n=%d"%(n)
"""
n=6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
c=29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
"""

分析

可以看到，这一题就是用的paillier cryptosystem，且参数用的是上文中的第二种参数模式。
这里我们用factordb尝试分解$n$发现可以成功分解，下面直接套公式写脚本即可。

脚本

from Crypto.Util.number import *
import gmpy2
p=80006336965345725157774618059504992841841040207998249416678435780577798937819
q=80006336965345725157774618059504992841841040207998249416678435780577798937447
n=6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
c=29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
phin=(p-1)*(q-1)
mu=gmpy2.invert(phin,n)
m=((pow(c,phin,n**2)-1)//n)*mu%n
print(long_to_bytes(m))
#b'flag{5785203dbe6e8fd8bdbab860f5718155}'