How Paillier cryptosystem can be used practically to encrypt and decrypt big messages "m"?

Question

I want to use the Paillier cryptosystem for encryption and decryption purposes in my research work. But i haven't found a way to encrypt big input messages; As i want to encrypt the message i,e m :

m = 0xa56f89d6aa234776b22347293429ff074928ab3749cc2837c492b874ebfaba78364ba0912efe862f628347982478b

Key Gen:

p =887, q = 907 , n =804509 ,n² = 647234731081;
g = n+1 = 804510;
λ = LCM(p-1,q-1) = 401358;
μ = L(g^λ mod n²)^(-1) mod n = 637146

Encryption:

Let random r = 1987
 c = ((g^m) * (r^n)) (mod n^2)

How can calculate g^m for such big input m?

If encrypted, then how can decryption work for big messages i,e m?

Answer 1

The Paillier cryptosystem allows to encrypt integers modulo $n$. Therefore, if $m$ is bigger than $n$, encrypting it will lose most of the message - only $m \bmod n$ is retrieved through decryption.

To encrypt a message bigger than $n$, you must break it into blocks, which you encrypt separately. You can for example write $m$ in base $n$, as $m = \sum_i m_i n^{i}$, and encrypt the $m_i$'s separately with Paillier.

Also, regarding how to calculate $g^m \bmod n^2$: note that $g = n+1$, hence

$g^m = (1+n)^m = 1 + n\cdot m \bmod n^2$

(if you develop $(1+n)^m$, you get $1 + nm + n^2\cdot \mathsf{something}$, and the $\mathsf{something}$ disappears modulo $n^2$).