- public-key keys homomorphic-encryption paillier
- Updated Sat, 21 May 2022 16:01:24 GMT

I'm trying to implement the Paillier cryptosystem in Matlab using the key generation guidance available here: https://en.wikipedia.org/wiki/Paillier_cryptosystem#Key_generation, but the problem is that with any combination of prime numbers I try, I get a float `mu`

required for the private key.

The first step is:

Choose two large prime numbers p and q

Just for a starting point I chose `p = 17 and q = 19`

.

Compute ${\displaystyle n=pq}$ and ${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)} $.

Which I achieved in Matlab using:

```
n = p*q;
lambda = lcm((p - 1), (q - 1));
```

This gives me `n = 323`

and `lambda = 144`

Third step:

Select random integer ${\displaystyle g}$ where $g\in {\mathbb Z}_{{n^{{2}}}}^{{*}}$

I read that `g = n + 1`

satisfies all the required conditions so I went with that, which gives me a `g = 324`

.

Fourth step is to compute ${\displaystyle \mu}$ using:

${\displaystyle \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$

where, ${\displaystyle L}$ is defined as ${\displaystyle L(x)={\frac {x-1}{n}}} $

I achieved this using:

```
a = (powermod(g, lambda, n*n) - 1) / n;
gMu = mod(inv(a),n);
```

So at this stage, the public key is supposed to be `(n,g) = (323,324)`

and the private key would be `(lambda,mu)`

which in my case comes to `(144,0.0069)`

.

Why am I getting a float value of `gMu`

whereas all the implementations I have seen online provide a integer value of private keys.

Where am I getting this wrong?

Looks like you missed the note on wikipedia:

Note that the notation ${\frac {a}{b}}$ does not denote the modular multiplication of $a$ times the modular multiplicative inverse of $b$ but rather the quotient of $a$ divided by $b$, i.e., the largest integer value $v\geq 0$ to satisfy the relation $a\geq vb$.

As a side note, to make key generation even simpler, there is another note on wikipedia you may be interested in:

If using $p,q$ of equivalent length, a simpler variant of the above key generation steps would be to set $g=n+1,\lambda =\varphi (n)$, and $\mu =\varphi (n)^{{-1}}{\bmod n}$, where $\varphi (n)=(p-1)(q-1)$.

External links referenced by this document: