# Choosing primes in the Paillier cryptosystem

1. In the first step of key generation phase in Paillier cryptosystem given here.

It's given that

$$\operatorname{length}(p) = \operatorname{length}(q) ) \implies \operatorname{gcd}(pq,(p-1)(q-1))=1$$

where

$\operatorname{length}(k)$ = # bits in binary representation of $k$

$\operatorname{gcd}(a,b)$= greatest common divisor of $a,b$

How to prove the above equation, or where has it been proven?

2. In the third step of key generation, we have to select a random integer $g$ where $g \in \mathbb{Z}_{n^2}^*$ and in the step 2 of encryption we have to select a random integer $r$ where $r \in \mathbb{Z}_n^*$.

What I am wondering is "what is the known efficient way to select $g,r$ randomly". I mean whether we have to check in $\mathbb{Z}_{n^2}^*,\mathbb{Z}_n^*$ for such $g,r$ until $\operatorname{gcd}(g,n^2)=1$ and $\operatorname{gcd}(r,n)=1$ or is there any simple method while coding cryptosystem.

3. In the first step of encryption, it is given that plain text $m\in \mathbb{Z}_n$ .

So $m < n$ .

Suppose we are going to encrypt $k$-bit messages , so our $n$ must be $l$-bit number, where $l>k$.

We know that product of two $s$-bit numbers gives a number whose number of bits is between $s+1$ to 2$s$ , Suppose we are taking the equal length primes to ensure the property $\operatorname{gcd}(pq,(p-1)(q-1))=1$, then it is necessary to take $k$-bit primes since $m<n$ .

Is this correct?

• I can't understand what you are asking. What does "Give me a reference if proof for above equation complex otherwise provide a proof." mean? Also, what research have you done? Did you read the original research paper? – D.W. Jul 10 '14 at 6:48

1. Since $p$ and $q$ are primes, the only factors you need to rule out are those two numbers.

Suppose $p$ divides $(p-1)(q-1)$. Then it divides either $p-1$ (clearly not true) or $q-1$. The latter means $q-1 = p \cdot x$, for some $x \ge 2$ (if $x = 1$ either $p$ or $q$ is even, which is only possible if the numbers are 2 and 3). However, then $q \ge 2p+1$, so its binary representation is longer.

A similar argument proves $q$ can't be a factor. Thus, the GCD must be $1$.

2. If you just pick a random $g$ modulo $n^2$ the odds that it is a good choice are high (for large primes), so you usually only have to verify once. However, like your Wikipedia link states, you can just choose $g=n+1$ (when your primes are as long).

For $r$ you are also likely to get a good number randomly, but there you do have to check that neither $p$ nor $q$ divides it.

3. We know that product of two $s$-bit numbers gives a number whose number of bits is between $s+1$ to 2$s$ , Suppose we are taking the equal length primes to ensure the property $\operatorname{gcd}(pq,(p-1)(q-1))=1$, then it is necessary to take $k$-bit primes since $m<n$ .

If you multiply two $s$-bit numbers the product is always either a $2s-1$-bit number or a $2s$-bit number. (Here an $s$-bit number means one which has its $s$th bit set.)

To allow any $k$-bit messages, it is necessary that $2s-1>k$, so $s=k/2+1$ is enough.

• 2) how to select r randomly . Is $r=p-1$ suits well? – hanugm Jul 9 '14 at 8:28
• @chanu, no. A new random $r$ must be chosen for every message. You can pick a random number modulo $n$, then find if $p$ or $q$ divides. There may be some shortcut I'm forgetting right now, but that's easy enough. – otus Jul 9 '14 at 8:38