密码学学习笔记之pailliercryptosystem

Preface

现代公钥密码系统中，其实远远不止RSA、DSA、ECC等众所周知的公钥密码系统，最近还学习到了一种比较年轻的公钥密码系统 —— paillier cryptosystem 但是wiki上并没有给出该方案的解密的proof。

Introduce

Paillier密码，于1999年由Pascal Paillier发明，是一种用于公钥加密的概率非对称算法。该算法具有加法同态的性质 ; 这意味着，仅给出公钥和m1、m2加密，可以计算出m1 + m2

Key generation

The frist pattern：

1. 随机选择两个大质数p、q满足gcd(pq, (p-1)*(q-1))。


2. 计算n=p*q，λ = lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1,q-1)


3. 选择随机整数g，0
   
4. 定义L(x) = (x-1) / n


5. 计算μ = (L(g^λ mod n^2 ))^(-1) mod n


6. 公钥为(n，g)


7. 私钥为(λ，μ)

The second pattern（a simpler variant）：

其余参数不变，主要改变了g，λ，μ的定义

1. g = n+1


2. λ = φ(n) = (p-1)*(q-1)


3. μ = φ(n)^(-1) (mod n)

Encryption

1. 设m为要加密的消息，显然需要满足，0 ≤ m ＜ n


2. 选择随机 r，保证gcd(r, n) = 1


3. 密文c：c = (g^m) *(r^n) mod n^2

Decryption

1. 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

∴$L(g^λpmod{n^2}) = k_g$

且有

1. $1+kn equiv 1+kn pmod{m^2}$


2. $(1+kn)^2 equiv 1+2kn+(kn)^2 equiv 1+2kn pmod{m^2}$


3. $(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)

Reference

https://en.wikipedia.org/wiki/Paillier_cryptosystem