# How Paillier cryptosystem can be used practically to encrypt and decrypt big messages “m”?

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?

• Related to this question. – Hilder Vitor Lima Pereira Sep 3 '19 at 11:29
• The entire reason Pallier is interesting is because of the partial homomorphic properties; that is, given $E(a)$ and $E(b)$, someone with only the public key can compute $E(a + b \bmod n)$. What are your homomorphic goals if $a > n$? If "none at all", then standard hybrid crypto (use Pallier to encrypt a symmetric key, and then use the symmetric key to encrypt the actual message) is your answer. – poncho Sep 3 '19 at 12:19
• No i don't want to use Pallier to encrypt only symmetric key, i want to encrypt some big data(hexadecimal values) – abbasi_ahsan Sep 3 '19 at 12:26
• But what is your goal? What problem are you trying to solve? "Using Pallier to encrypt a large amount of data" is a solution, not a goal. – poncho Sep 3 '19 at 12:37
• @poncho here i define my goal crypto.stackexchange.com/questions/73023/… – abbasi_ahsan Sep 3 '19 at 19:46

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$$).

• Is there material/ paper which can help me to implement this – abbasi_ahsan Sep 3 '19 at 11:07
• There are probably plenty of resources online about implementations of the Paillier cryptosystem in all major languages. I do not know much about that, since I never implemented it myself. – Geoffroy Couteau Sep 3 '19 at 11:19
• @Geoffory Thankyou – abbasi_ahsan Sep 3 '19 at 11:28
• This does not give an IND-CCA2/NM-CCA2 public-key encryption scheme as one usually expects from the term ‘public-key encryption’. – Squeamish Ossifrage Sep 3 '19 at 14:17