Paillier 公钥密码系统

前段时间看到一篇关于 Paillier Cryptosystem 的文章，单纯出于对里面的数学推导的兴趣，然后就跟着推导了一下，结果就跟着文章玩了一天 😢。
实话说，这篇文章还是非常有价值的，填补了 Wiki 上对相关过程的证明。略微有点遗憾的是，原文中有些证明有些迂回，也存在些许小错误。（对不起 V 师傅 💔 ）
本着快落的态度 😄，笔者对该公钥密码体制做了更加详细严谨的推导证明，希望对读者有所帮助。

Paillier 公钥密码系统简介

Paillier 密码，于1999年由 Pascal Paillier 发明，是一种用于公钥加密的概率非对称算法，基于复合剩余类困难问题（Composite Degree Residuosity Classes），构造在模数取为 $n^2$ 的剩余类上。
该算法具有加法同态的性质。这意味着，仅给出公钥和 $m_1$、$m_2$ 加密，可以计算出 $m_1 + m_2$.

$(1+x)^n \pmod { n^2 }$ 的处理方法

$$
\begin{aligned}
( 1 + x ) ^n = \sum_{ k = 0 } ^{ n } C_n^k x^k \pmod { n ^2 }
\\
= 1 + nx \pmod { n ^2 }
\end{aligned}
$$

在 Paillier 密码中函数 $L_n(u) = \frac{ u-1 } {n }$ 和这个部分是紧密关联的。

Paillier Keygen

随机选择两个大质数 $p$、$q$，满足 $\left (pq, (p-1) \times (q-1) \right) = 1$
$n = p \times q$，选择随机 $g \in Z_{n^2} $
$\lambda = \left[p-1, q-1\right]，{ \mu } = L(g^{ \lambda } \pmod {n^2} ) ^{ -1 } \pmod {n}$
公钥为 $(n, g)$, 私钥为 $( { \lambda }，{ \mu } )$.

Paillier Enc

设 $m$ 为要加密的消息，显然需要满足，$0 \le m < n$.
选择随机 $r \in Z ^{ \star } _{ n }$.
密文 $c = g^m r^n \pmod { n ^2 }$

Paillier Dec

$m = L( c^{ \lambda } \pmod { n^2 } \times { \mu } ) \pmod n$

Paillier Proof

我们注意到 $\mu$ 的存在有点古怪（没有那么清晰）：${\mu} = L(g ^{ \lambda } \pmod{ n^2 })^{ -1 } \pmod{ n }$，而最后的 $c$ 也涉及到 $\times \mu$，所以，我们可以先入手把 $\mu$ 解析掉：
从 $g^{ \lambda }$ 开始：
$$
\because \lambda = [p-1, q-1]
\\
\therefore (p-1)| , { \lambda }, (q-1) | , {\lambda}
\\
\text{Eular theorem:}
\\
\begin{cases}
g^{ p-1 } = 1 \pmod{ p }
\\
g^{ q-1 } = 1 \pmod{ q }
\end{cases}
\\
\Rightarrow
\begin{cases}
g^{ \lambda } = 1 \pmod{ p }
\\
g^{ \lambda } = 1 \pmod{ q }
\end{cases}
\\
\text{又} \because [p, q] = p \times q = n
\\
\therefore g^{ \lambda } = 1 \pmod{ n }
\\
\Leftrightarrow g^{ \lambda } = k_g n + 1
$$
代入函数 $L$ :
$$
L(g^{ \lambda } \pmod { n^2 }) = \frac{ k_g n + 1 - 1}{n} = k_g
\\
\therefore \mu = k_g^{-1} \pmod{ n }
$$

解析 $\mu$ 的过程中，最大的收获不是结果 $\mu$ 本身，而是发现 $g^\lambda$ 可以这样处理。
⭐️ 其实会发现 $g^{ \lambda } = k_g n + 1$ 只需要满足：
1. $\lambda = \left[p-1, q-1\right]$
2. $g \in Z $
所以，后面相关的指数运算如果不能用 Eular 定理或者 Fermat 定理，都可以这么处理。

继续我们的步伐，聚焦于 Dec 中的 $c^{ \lambda } \pmod{ n^2 }$：
$c^{ \lambda } \pmod{ n^2 }= g^{ m { \lambda } } r^{ n { \lambda } } \pmod{ n^2 }$，结合刚刚的收获+ “$(1+x)^n \pmod{ n^2 }$ 的处理方法”，有：
$$
\begin{cases}
g^{ m{ \lambda } } = (1+k_gn)^{ m } \equiv k_gnm+1 \pmod{ n^2 }
\\
r^{ n{ \lambda } } = (1+k_rn)^{ n } \equiv k_rn^2+1 \equiv 1\pmod{ n^2 }
\end{cases}
\\
\therefore L(g^{ m{ \lambda } } r^{ n{ \lambda } }\pmod{ n^2 }) = L(k_gnm+1 )= mk_g
\\
L( c^{ \lambda } \pmod {n^2}) \times {\mu} \pmod n = mk_g \times k_g^{ -1 } = m \pmod{ n^2 }
$$
证毕.

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 密码的一个变式
其余参数不变，主要改变了 $g，{ \lambda }，{ \mu } $ 的定义：

$g = n+1$
$ { \lambda } = { \varphi } (n) = (p-1) \times (q-1)$
$ { \mu } = { \varphi } (n) ^{ -1 } \pmod n$

公钥为 $(n, g)$, 私钥为 $ ( { \lambda }，{ \mu } ) $.
题目是公开了它的加密方案，问题在于它的解密方案是如何？会和 Paillier 一致吗？需要我们去推导一下。（我们的猜想是 $m = L( c^ { \lambda } \pmod { n^2 } \times { \mu } ) \pmod n$，或者类似的方案）。

猜想验证

总体有：
$$
\text{由} L(c^ { \lambda } \pmod { n^2 } \times {\mu} ) \pmod{ n }
\\
\Leftrightarrow L(g^ { m { \lambda } } r ^ { n{ \lambda } } \pmod{ n^2 } · { \mu } ) \pmod{ n } \text{①}
$$

分析其中的 $r ^ { n{ \lambda } }$:
$$
\text{其中} { \lambda } = (p-1) \times (q-1)， { \mu } = { \varphi } ( n )^{ -1 } \pmod{ n }
\\
\because r^{ n { \lambda } } = r^{ n (p-1) \times (q-1)} = r^{ { \varphi } (n^2) }
\\
\text{Euler theorem}：r^{ { \varphi } (n^2) } \equiv 1 \pmod{ n^2 }
$$

分析其中的 $g^ { m { \lambda } }$:

$$
① \Rightarrow L(g^{ m { \lambda } } \pmod{ n^2 } · { \mu }) \pmod{ n } ②
\\
\because g = n+1
\\
\therefore g^{ m { \lambda } } = (1+n)^{ m { \lambda } } \equiv nm{ \lambda } +1 \pmod{ n^2 }
$$

会师：
$$
② \Rightarrow L( ( nm { \lambda }+1) \times { \mu }) \pmod { n }
\\
\Rightarrow (m { \lambda } \times { \mu }) \pmod{ n } ③
\\
\because { \lambda } = { \varphi } ( n)，{ \mu } = { \varphi } (n) ^{ -1 } \pmod{ n }
\\
③: (m{ \lambda } · { \mu }) \equiv m\pmod{ n }
\\
$$
证毕.

解密

所以构造解密脚本

# -*- 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(m_1, r_1) · E(m_2,r_2) \pmod { n^2 } ）≡ m_1+m_2 \pmod n$

Proof

$$
\begin{align}
C &= (g^{ m_1 }) · (r_1^n) · (g^{m_2}) · (r_2^n) \pmod {n^2}
\\
&= g^{( m_1+m_2 )} · (r_1r_2)^n \pmod { n^2 }
\end{align}
$$
首先我们可以将 $m_1+m_2$ 看作一个整体 $M$，然后由于 $r_1$、$r_2$ 是随机选的，所以 $r_1 \times r_2$ 可以看作一个整体 $R$，
故 $C = g^M * R^n \pmod { n^2 }$
由于$gcd(r_1, n) = 1; gcd(r_2,n) = 1； => gcd(r_1·r_2, n) = 1$，故 $R$ 符合要求。
所以 $D© = M ≡ m_1 + m_2 \pmod n$

Homomorphic multiplication of plaintexts

设D为解密函数，E为加密函数
即：$D(E(m_1, r_1)^k \pmod { n^2 } ≡ km_1 \pmod n$

Proof

$$
\begin{align}
C &= \left( g^{ m_1 } \times r_1^n \right) ^k \pmod { n^2 }
\\
&=(g^{ km_1 })·(r_1^{kn} ) \pmod {n^2}
\end{align}
$$
首先我们可以将 $km_1$ 看作一个整体 $M$，然后由于 $r_1$ 是随机选的，所以 $r_1^k$ 可以看作一个整体 $R$，
故 $C = g^M * R^n \pmod { n^2 }$
由于 $gcd(r_1,n) = 1 => gcd(r_1^k, n) = 1$，故 $R$ 符合要求。
所以 $D© = M ≡ km_1 \pmod n$

参考资料与碎碎念

https://en.wikipedia.org/wiki/Paillier_cryptosystem
https://www.anquanke.com/post/id/204720
PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[C]// International conference on the theory and applications of cryptographic techniques. : Springer, 1999: 223–238.

可能有人会问“复合剩余类困难问题”在本文中哪里有体现呢❓
好问题，去看参考文献里面提到的论文吧 😅

同态加密开启新世界的大门，有时间我想去看看基于格的全同态密码方案！ ❤️