How to select $g$ in Paillier Cryptosystem

Question

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

Answer 1

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.