0
$\begingroup$

I was implementing Paillier cryptosystem when I came across the fact that as soon as I take the primes $p$ = $q$, I start getting incorrect decryption results.
As far as I can understand, when I take $p$ = $q$, the function $L(x)$ returns a fractional value instead of an integer one, meaning that in case when the primes are equal $L($$g^{\lambda}$ mod $n^{2}$) is not an integer. I also get that when the primes are equal, then $\lambda = (p-1)$, since lcm of $(a, a)$ is $a$.
Can someone explain that where do things go wrong when the primes are equal?
Reference for the scheme

$\endgroup$
8
  • 1
    $\begingroup$ The Carmichael function $\lambda(p^2)$ would be $=p(p-1)$. $\endgroup$ Oct 8, 2017 at 22:09
  • $\begingroup$ Yeah, I know that but what if I don't take $\lambda$ as $\phi(n)$. I can take $\lambda = lcm(p-1, q-1) = p-1$ (in this case). $\endgroup$
    – Mayank
    Oct 8, 2017 at 22:11
  • 2
    $\begingroup$ No, I mean the Carmichael function which is $\lambda(pq)=(p-1)(q-1)$ for different odd primes $p,q$. And if you take $p=q$ you should try $\lambda = p(p-1)$ where you get at least $g^\lambda-1\equiv 0 \bmod n$ $\endgroup$ Oct 8, 2017 at 22:24
  • 1
    $\begingroup$ But: Even if this technically would work, it is insecure because you can easily get $\lambda $ from $n$. $\endgroup$ Oct 8, 2017 at 22:28
  • 1
    $\begingroup$ Also, using $p=q$ and $\lambda(pq) = p(p-1)$ only nearly works; non-zero multiples of $p$ do not decipher. $\endgroup$
    – fgrieu
    Oct 9, 2017 at 5:30

1 Answer 1

2
$\begingroup$

Irrespective of the math, you CANNOT take $p=q$ since in this case the scheme is completely insecure. You must choose random, independent primes $p$ and $q$.

$\endgroup$
2
  • $\begingroup$ Am I correct in saying that unless I take the difference of |$p-q$| to be > than the limits of brute attacks, I can consider the implementation to be safe. Though, I am not considering NFS attacks here. I think that they might also come into play and as far as I remember, using meet-in-the-middle algorithms like baby-step-giant-step, we should take this difference to be more, since such algorithms solve integer factorization in close to $O(n^{1/4})$ $\endgroup$
    – Mayank
    Oct 12, 2017 at 17:09
  • 1
    $\begingroup$ No. The standard problem that has been studied is one where $p$ and $q$ are independent and random. Anything else is dangerous. $\endgroup$ Oct 14, 2017 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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