Paillier-Cryptosystem

Two different approaches to homomorphic encryption. These ways are called as “paillier-cryptosystem”.

And to understand the principle behind them, I do the proof.

INIT

FIRST PATTERN

• produce two large primes $p$, $q$, assert them that $gcd(p\times q, (p-1)\times(q-1) = 1$

• calculate $n = p\times q$, define that $\lambda = lcm(p-1, q-1) = \frac{(p-1)\times(q-1)}{gcd(p-1, q-1)}$

• produce random $g$, and $0<g<n^{2}$

• define that $L(x) = \frac{x-1}{n}$

• define that $\mu = (L(g^{\lambda} \mod n^{2}))^{-1} \mod n$

SECOND PATTERN

• define that $g = n + 1$

• define that $\lambda = \varphi(n) = (p-1)\times (q-1) $

• and also define that $\mu = \varphi(n)^{-1} \mod n$

KEYS

• PK = {$n$, $g$}
• SK = {$\lambda$, $\mu$}

ENCRYPT AND DECRYPT

ENCRYPT

• assert that $0<m<n$
• produce a random $r$, assert that $gcd(r, n) = 1$
• $c \equiv g^{m} \cdot r^{n} \mod n^{2}$

DECRYPT

• $m \equiv (L(c^{\lambda} \mod n^{2})\cdot \mu)\mod n$

PROOF

PATTERN 1

• substitute the equation of $c$ into $m$, we get the $eq1$

$$
m \equiv (L(g^{m\lambda}\cdot r^{n\lambda} \mod n^{2})\cdot \mu)\mod n
$$ {eq1}

• substitute $\mu$ to ${eq1}$, we get the $eq2$

$$
m \equiv L(g^{m\lambda}\cdot r^{n\lambda} \mod n^{2}) \cdot (L(g^{\lambda} \mod n^{2}))^{-1} \mod n
$$ {eq2}

• make some deductions to get the $g^{\lambda}$

$$
p-1 | \lambda and q-1 | \lambda
$$

so we can get the equations that:
$$
\lambda = k_1(p-1) and \lambda = k_2(q-1)
$$
fermat little theorem:
$$
g^{\lambda} = g^{k_1(p-1)} \equiv 1 \mod p
$$

$$
g^{\lambda} = g^{k_2(q-1)} \equiv 1 \mod q
$$

$$
\Longrightarrow g^{\lambda} - 1 | q and g^{\lambda} - 1 | p
$$

$$
\Longrightarrow g^{\lambda} - 1 | lcm(p, q)
$$

$$
\Longrightarrow g^{\lambda} - 1 | n
$$

at last, we get the key equation:
$$
g^{\lambda} \equiv 1 \mod n
$$

$$
\Longrightarrow g^{\lambda} \mod n^{2} \equiv 1 \mod n
$$

$$
\Longrightarrow g^{\lambda} = 1 + k_g \cdot n
$$

the $k_g$ is less than $n$

substitute $g^{\lambda}$ into $L(x)$:
$$
L(g^{\lambda} \mod n^{2}) = k_g
$$

• also make some deductions to get $g^{m\lambda}$

$$
1 + kn \equiv 1 + kn \mod n^{2}
$$

$$
(1 + kn)^{2} \equiv 1 + 2kn + (kn)^{2} \mod n^{2} \equiv 1 + 2kn \mod n^{2}
$$

$$
(1 + kn)^{3} \equiv 1 + 3kn + 3(kn)^{2} + (kn)^{3} \equiv 1+3kn \mod n^{2}
$$

$$
\Longrightarrow (1 + kn)^{m}\equiv 1+mkn \mod n^{2}
$$

$$
\Longrightarrow g^{m\lambda}=(1+k_gn)^{m}\equiv 1 + mk_gn \mod n^{2}
$$

• same to get $r^{n\lambda}$

$$
r^{n\lambda} =(1+k_rn)^{n}\equiv 1 + k_r n^{2} \mod n^{2} \equiv 1\mod n^{2}
$$

• substitute $g^{m\lambda}$ , $r^{n\lambda}$ and $L(g^{\lambda} \mod n^{2})$ into $eq2$

$$
m \equiv L(1 + mk_gn \mod n^{2}) \cdot (L(g^{\lambda} \mod n^{2}))^{-1} \mod n
$$

$$
m \equiv k_g m \cdot k_g^{-1} \mod n \equiv m \mod n
$$

Proved.

PATTERN 2

• also substitute $c$ into $m$

$$
L(g^{m\lambda}\cdot r^{n\lambda} \mod n^{2})\cdot \mu \mod n
$$

• substitute $\lambda$ into $r^{n\lambda}$ and make some deductions

$$
r^{n\lambda} = r^{n(p-1)(q-1)} = r^{p(p-1) \cdot q(q-1)}
$$

using Euler’s totient function 3 that $\varphi(p^k) = p^k - p^{k-1} = (p-1)\cdot p^{k-1} = \varphi(p) \cdot p^{k-1}$ and fermat little theorem
$$
r^{p(p-1) \cdot q(q-1)} = r^{\varphi(n^2)} \equiv 1 \mod n^{2}
$$

$$
r^{n\lambda} \equiv 1 \mod n^{2}
$$

• get the simple equation, we get the $eq3$

$$
(L(g^{m\lambda} \mod n^{2})\cdot \mu) \mod n
$$ {eq3}

• make some deductions about $g^{m\lambda}$

$$
g^{m\lambda} \equiv (n + 1)^{m\lambda} \mod n^{2}
$$

$$
\Longrightarrow g^{m\lambda} \equiv 1 + mn\lambda \mod n^{2}
$$

• substitute $g^{m\lambda}$ into $eq3$

$$
L(1 + mn\lambda)\cdot \mu \mod n \equiv m\lambda \mu \mod n
$$

as $\lambda = (p-1)(q-1) = \varphi(n)$ and $\mu \equiv \varphi(n)^{-1}\mod n$, we will get that:
$$
m \varphi(n)\cdot \varphi(n)^{-1} \equiv m \mod n
$$
Proved.

EXERCISE

FIRST

from gmpy2 import *
from Crypto.Util.number import *
from flag import flag
import random

p = getPrime(512)
q = next_prime(p)
assert gcd(p*q, (p-1)*(q-1)) == 1
n = p*q
print('n = ' + str(n))

g = random.randint(1, n*n)
print('g = ' + str(g))
r = random.randint(1, n)
assert gcd(r, n) == 1

m = bytes_to_long(flag)
c = (pow(g, m, n*n) * pow(r, n, n*n)) % (n*n)
print('c = ' + str(c))
"""
n, g, c
"""

SECOND

from gmpy2 import *
from Crypto.Util.number import *
from flag import flag, p, q
import random

p = getPrime(512)
q = next_prime(p)

n = p*q
g = n + 1
print('n = ' + str(n))
print('g = ' + str(g))

r = random.randint(1, n)
assert gcd(r, n) == 1

m = bytes_to_long(flag)
c = (pow(g, m, n*n) * pow(r, n, n*n)) % (n*n)
print('c = ' + str(c))
"""
n, g, c
"""

Follow the PROOF, and we can write scripts to decrypt.