# How to select $g$ in Paillier Cryptosystem

For my cryptography class project in university I have selected Paillier Cryptosystem as a course project http://en.wikipedia.org/wiki/Paillier_cryptosystem#Key_generation

In key generation it says

Choose two large prime numbers $p$ and $q$

I have selected $p$ = 11 and $q$ = 17, it also satisfies the condition

$gcd(pq, (p-1)(q-1))=1$

which makes my $n$ = 187 and ${\lambda}$ = 80

and now in 3rd point it says

Select random integer $g$ where $g \in (\mathbb{Z}_n^∗)^2$

now what does it mean $g \in (\mathbb{Z}_n^∗)^2$?

there is a question What does $(\mathbb{Z}_n^*)^2$ mean? but it doesn't make any sense to me

so the first question is how can I select the random integer g?

In 4th point it says

Ensure $n$ divides the order of $g$ by checking the existence of the following modular multiplicative inverse: $\mu\ = (L(g^{\lambda}\mod n^{2}))^{-1} \mod n$

it further says

where function $L$ is defined as $L(u) = \frac{u-1}{n}$ .

can some one please help me to find out $g$ and $\mu$?

• The public (encryption) key is $(n, g)$.
• The private (decryption) key is $(\lambda, \mu)$.

with any example or link that can guide me to a correct path.

Thanks

The requirement is that your element $g$ is in $\mathbb{Z}_{n^2}^*$ and not in $(\mathbb{Z}_{n}^*)^2$.

The set $\mathbb{Z}_{n^2}^*$ is the set of integers smaller than $n^2$ that are relatively prime to $n^2$, i.e., you require an element $g$ from $\mathbb{Z}_{n^2}$ such that $\gcd(g,n^2)=1$.

$(\mathbb{Z}_{n}^*)^2$ on the other hand is the set of pairs $(a,b)$ such that $a$ and $b$ are from $\mathbb{Z}_n^*$.

You compute $\lambda=lcm(p-1,q-1)$ where $lcm$ is the least common multiple. Then for your chosen $g$ you have to check whether $a=L(g^\lambda \bmod n^2)$ (where $L(u)=\frac{u-1}{n}$ ) has a multiplicative inverse modulo $n$ (is an element in $\mathbb{Z}_n^*$), i.e., you have to check whether $\gcd(a,n)=1$. If this is the case, then compute $\mu$ as $a^{-1} \bmod n$. Otherwise, try with another $g$ until this condition is satisfied.

• thanks alot, what about the other part of the question? do you have any clue? – zzlalani Apr 13 '14 at 19:45
• like how can I find μ – zzlalani Apr 13 '14 at 19:48
• If I remember correctly, $g=n+1$ fulfills the necessary condition and is a viable option if you don't need a random generator. – tylo Apr 14 '14 at 12:15
• @tylo, yes that's correct. at the cost of a larger $\lambda$ ($\varphi(n)$ instead of $lcm(p-1,q-1)$). – DrLecter Apr 14 '14 at 12:19
• @zzlalani first, your $r$ is not co-prime to $n$, lets take $r=3$. Then your ciphertext is 1062. I'm not sure if your inverse is correct. You have to compute inverses in the ring modulo $n$, i.e., $24^{-1}$ should be 19 (an inverse $x^{-1}$ of $x$ modulo $n$ is defined such that $x\cdot x^{-1} \equiv 1 \pmod n$). Then decrypting $1062$ yields $4$, which is correct. – DrLecter Apr 24 '14 at 17:56