Preface
现代公钥密码系统中，其实远远不止RSA、DSA、ECC等众所周知的公钥密码系统，最近还学习到了一种比较年轻的公钥密码系统 —— paillier cryptosystem 但是wiki上并没有给出该方案的解密的proof。
Introduce
Paillier密码，于1999年由Pascal Paillier发明，是一种用于公钥加密的概率非对称算法。该算法具有加法同态的性质 ; 这意味着，仅给出公钥和m1、m2加密，可以计算出m1 + m2
Key generation
The frist pattern：
- 随机选择两个大质数p、q满足gcd(pq, (p-1)*(q-1))。
- 计算n=p*q，λ = lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1,q-1)
- 选择随机整数g，0<g<n^2
- 定义L(x) = (x-1) / n
- 计算μ = (L(g^λ mod n^2 ))^(-1) mod n
- 公钥为(n，g)
- 私钥为(λ，μ)
The second pattern（a simpler variant）：
其余参数不变，主要改变了g，λ，μ的定义
- g = n+1
- λ = φ(n) = (p-1)*(q-1)
- μ = φ(n)^(-1) (mod n)
Encryption
- 设m为要加密的消息，显然需要满足，0 ≤ m ＜ n
- 选择随机 r，保证gcd(r, n) = 1
- 密文c：c = (g^m) *(r^n) mod n^2
Decryption
- m = ( L( c^λ mod n^2 ) * μ ) mod n
Proof
以下推理过程就用数学公式记录了，如果平台显示不出来的话，建议复制进typora等此类编辑器中食用，下面也会给出截图
The first pattern
由 $L(c^λ pmod{n^2}*μ) pmod{n}$
有 $L(g^{mλ}r^{nλ} pmod{n^2})μ pmod{n}$ ①
其中$λ = frac{(p-1)(q-1)}{gcd((p-1)(q-1))}, μ = L(g^λ pmod{n^2})^{-1} pmod{n}$
所以①式=> $L(g^{mλ}r^{nλ} pmod{n^2})L(g^λ pmod{n^2})^{-1} pmod{n}$ ②
∵$(p-1)|λ, (q-1)|λ$
∴$λ = k_1(p-1) = k_2(q-1)$
∴$g^λ = g^{k_1(p-1)}equiv 1 pmod{p}，即 (g^λ -1) | p$
$ g^λ = g^{k_2(q-1)}equiv 1 pmod{q}， 即 (g^λ -1) | q$
∴$ (g^λ -1) | lcm(p,q) ，即 (g^λ -1) | pq，即g^λ equiv 1 pmod{n} $
∴$g^λ pmod{n^2} equiv 1pmod{n}$
∴$g^λpmod{n^2} = k_gn+1; k<n$
∴$L(g^λpmod{n^2}) = k_g$
且有
- $1+kn equiv 1+kn pmod{m^2}$
- $(1+kn)^2 equiv 1+2kn+(kn)^2 equiv 1+2kn pmod{m^2}$
- $(1+kn)^3 equiv 1+3(kn)^2+3kn+(kn)^3 equiv 1+3kn pmod{m^2}$这里我们就不用数学分析法了，就直接易得了=> $(1+kn)^{m} equiv knm+1 pmod{n^2}$
∴$g^{mλ} = (1+k_gn)^{m} equiv k_gnm+1 pmod{n^2}$
∴$r^{nλ} = (1+k_nn)^{n} equiv k_nn^2+1 equiv 1pmod{n^2}$
∴$L(g^{mλ}*r^{nλ}pmod{n^2}) = L(k_gnm+1)=mk_g$
又∴$L(g^λpmod{n^2}) = k_g$
∴②式： $L(g^{mλ}r^{nλ} pmod{n^2})L(g^λ pmod{n^2})^{-1} pmod{n}$ => $mk_g*k_g^{-1} equiv m pmod n$
证毕
截图：
The second pattern
由 $L(c^λ pmod{n^2}*μ) pmod{n}$
有 $L(g^{mλ}r^{nλ} pmod{n^2}μ) pmod{n}$ ①
其中$λ = (p-1)*(q-1)， μ = φ(n)^{-1} pmod{n}$
∵$r^{nλ} = r^{n(p-1)*(q-1)} = r^{φ(n^2)}$
由欧拉定理：$r^{φ(n^2)} equiv 1 pmod{n^2}$
①式 => $L(g^{mλ} pmod{n^2}*μ) pmod{n}$ ②
∵$g = n+1$
∴$g^{mλ} = (1+n)^{mλ} equiv nmλ+1 pmod{n^2}$
②式=> $L((nmλ+1)*μ) pmod{n}$
=> $ frac{(nmλ+1)-1}{n}*μ pmod{n}$
=>$(mλ*μ) pmod{n}$ ③
∵$λ = φ(n)，μ = φ(n)^{-1} pmod{n}$
∴③式： $(mλ*μ) equiv mpmod{n}$
证毕
截图：
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)
可以看到，这一题就是用的paillier cryptosystem，且参数用的是上文中的The second pattern
但是我们计算λ = φ(n) = (p-1)*(q-1) ，需要用到p和q
这里我们直接上yafu分解n发现可以成功分解，原因是p与q其实非常接近，所以其实直接对n开根然后再在附近寻找素数就能找到p、q了。
所以构造解密脚本
# -*- coding: utf-8 -*-
from Crypto.Util.number import long_to_bytes,inverse
from sympy import nextprime
from gmpy2 import iroot
def L(x,n):
return (x-1)/n
c=
n=
#factor(n)
a = iroot(n,2)[0]
p = nextprime(a)
q = n//p
assert p*q == n
#根据解密公式，计算所需私钥对（λ，μ）
Lambda=(p-1)*(q-1)
miu=inverse(Lambda,n*n)
m=(L(pow(c,Lambda,n**2),n)*miu)%n
print long_to_bytes(m)
Homomorphic properties
Homomorphic addition of plaintexts
设D为解密函数，E为加密函数
即：D(E(m1, r1)*E(m2,r2) mod n^2）≡ m1+m2 (mod n)
proof
C = (g^m1) * (r1^n) * (g^m2) *(r2^n) mod n^2
= g^(m1+m2)*(r1r2)^n mod n^2
首先我们可以将m1+m2看作一个整体M，然后由于r1、r2是随机选的，所以r1*r2可以看作一个整体R，
故C = g^M * R^n mod n^2
由于gcd(r1,n) = 1; gcd(r2,n) = 1； => gcd(r1*r2, n) = 1，故R符合要求
所以D(C) = M ≡ m1 + m2 (mod n)
Homomorphic multiplication of plaintexts
设D为解密函数，E为加密函数
即：D(E(m1, r1)^k mod n^2）≡ km1 (mod n)
proof
C = (g^m1) * (r1^n)^k (mod n^2 )
=(g^km1)*(r1^(kn) ) (mod n^2)
首先我们可以将km1看作一个整体M，然后由于r1是随机选的，所以r1^k可以看作一个整体R，
故C = g^M * R^n mod n^2
由于gcd(r1,n) = 1 => gcd(r1^k, n) = 1，故R符合要求
所以D(C) = M ≡ km1 (mod n)