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
$\begingroup$
$\endgroup$
8
-
1$\begingroup$ The Carmichael function $\lambda(p^2)$ would be $=p(p-1)$. $\endgroup$– gammatesterCommented 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$– MayankCommented 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$– gammatesterCommented 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$– gammatesterCommented 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 ♦Commented Oct 9, 2017 at 5:30
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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$.
answered Oct 9, 2017 at 10:04
-
$\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$– MayankCommented 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$ Commented Oct 14, 2017 at 18:43