證明Paillier密碼解密過程的正確性
市場上有許多不同類型的密碼系統。
現在是隨機整數 $ g $ 被選擇的形式$$ g=(1+n)^{\alpha}\beta^{n}\bmod n $$， 在哪裡 $ \alpha $ 和 $ \beta $ 在 $ \mathbb{Z}_{n}^{*} $ . 證明 $$ m;=;L(c^{\lambda}\bmod n^{2})\mu\bmod n;=;\frac{L(c^{\lambda})\bmod n^{2}}{L(g^{\lambda})\bmod n^{2}}\bmod n $$， 在哪裡 $ L(x)=\displaystyle\left\lfloor\frac{x-1}{n}\right\rfloor $ 表示商時 $ x-1 $ 被除以 $ n $ 和 $ \mu=\left(L\left(g^{\lambda}\bmod n^{2}\right)\right)^{-1}\bmod n $ .
（**卡邁克爾定理：**對於任何 $ r\in \mathbb{Z}_{n^{2}}^{*} $ ， 我們有 $ r^{n\lambda}\equiv1\bmod n^{2} $ .)
以上是問題描述。以下是我想出的。
$$ \begin{align*} L(c^{\lambda}\bmod n^{2}) &= \frac{c^{\lambda}\bmod n^{2}-1}{n} \ &= \frac{g^{m\lambda}r^{n\lambda}\bmod n^{2}-1}{n} \ &= \frac{(g^{m\lambda}-1)r^{n\lambda}\bmod n^{2}}{n} \ &= \frac{g^{m\lambda}-1 \bmod n^{2}}{n} \end{align*} $$ $$ \begin{align*} L(g^{\lambda}\bmod n^{2}) &= \frac{g^{\lambda}\bmod n^{2}-1}{n} \ &= \frac{g^{\lambda}-1 \bmod n^{2}}{n} \end{align*} $$
但我不知道如何進行。我還沒有使用公式 $ g $ . 我認為解決方案可能涉及一些有限域定理，但我真的想不起來。
首先，我們簡化 $ \mu $ . $$ \begin{align*} g &= (1+n)^{\alpha}\beta^{n} \bmod n^{2} \ g^{\lambda} &= (1+n)^{\alpha\lambda}\beta^{n\lambda}\bmod n \ &= (1+n)^{\alpha\lambda}\bmod n^{2} \ &= (1+n\alpha\lambda)\bmod n^{2} \ L(g^{\lambda}\bmod n^{2}) &= (\alpha\lambda)\bmod n^{2} \end{align*} $$ 那麼，我們一起來看看 $ L(c^{\lambda}\bmod n^{2}) $ . $$ \begin{align*} c &= g^{m}r^{n}\bmod n^{2} \ c^{\lambda} &= g^{m\lambda}r^{n\lambda}\bmod n^{2} \ &= g^{m\lambda}\bmod n^{2} \ &= (1+n\alpha\lambda)^{m}\bmod n^{2} \ &= (1+mn\alpha\lambda)\bmod n^{2} \ L(c^{\lambda}\bmod n^{2}) &= (m\alpha\lambda)\bmod n^{2} \end{align*} $$
因此， $ \frac{L(c^{\lambda}\bmod n^{2})}{L(g^{\lambda}\bmod n^{2})}=m\bmod n $ ，Paillier密碼的解密過程是正確的。