Paillier暗号 - crypto-writeup-public

パラメータを決め打つかどうかなどで復号処理が一般化されていたりされていなかったりで難しい

鍵生成

素数 $p, q$

秘密鍵

$\phi(N) = lcm(p-1, q-1), \mu = {\phi(N)}^{-1} \mod N$

公開鍵

$N=p*q, g = kN+1$ where $k \in \mathbb{Z}$

暗号化

乱数 $r$ を持ってきて、 $C = g^M r^N \mod N^2$

復号

まず、 $C^{\phi(N)} \equiv g^{M\phi(N)}r^{N\phi(N)} \equiv g^{M\phi(N)} \equiv 1 + NM\phi(N) \mod N^2$

途中で

カーマイケルの定理

の拡張

$a^{n\lambda(N)} \equiv 1 \mod N^2$

（ただし

$\lambda(p_1^{e_1} p_2^{e_2}\dots) = lcm(\lambda(p_1^{e_1}), \lambda(p_2^{e_2}), \dots), \lambda(p^e) = p^{e-1}(p-1)$

と

$(1+N)^x \equiv 1 + xN \mod N^2$

を用いている

これを利用して、復号は

$\frac{(C^{\phi(N)} \mod{N^2}) - 1}{N} \mu \equiv M\phi(N) \mu \equiv M \mod N$

paillier暗号は加法準同型性を持つ。すなわち以下が成り立つ

$E(m_1, r_1)\times E(m_2, r_2) \mod N^2 = E(m_1+m_2, r_1 r_2) \mod N^2$

from Crypto.Util.number import getPrime, getRandomRange, inverse

def encrypt_paillier(m: int, g: int, n: int):
    r = getRandomRange(2, n)
    return pow(g, m, n**2) * pow(r, n, n**2) % (n**2)


def decrypt_paillier(c, p, q, g):
    phi = (p-1)*(q-1)
    mu = inverse(phi, n)
    k = (g - 1) // n
    return ((pow(c, phi, n**2) - 1) // n)  * inverse(k, n) * mu % n


p = getPrime(512)
q = getPrime(512)
n = p * q
g = 2*n + 1

m = getRandomRange(2, n)
c2 = encrypt_paillier(m, g, n)
assert decrypt_paillier(c2, p, q, g) == m