2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.