Paillier cryptosystem has a (serious) flaw
(too old to reply)
Miroslav Stampar
2005-09-29 05:48:31 UTC
Before you continue to read further, I suggest you to look/read two
(easy) http://en.wikipedia.org/wiki/Paillier_cryptosystem

The problem seems to be in encryption part: "select a random r < n".

Now, here is an example that I want you to observe:

1) "Choose two large prime numbers p and q randomly and independently
of each other."
Let p=41, q=43.
2) "Compute N=pq and phi = (p - 1)(q - 1)"
Let N=pq=1763
Let phi=(p-1)(q-1)=1680
3) "The public key is N and the private key is phi"

4) Let m be a message to be encrypted, with 0<m<N.
Let m=1234
5) Let r be some random integer between 0 and N (problematic part)
Let r=615
6) The ciphertext is:
Let c=[(1+N)^m * r^N] mod N^2
=3003947 (Mathematica code: squareN=n^2; c = Mod[PowerMod[1 + n, m,
squareN]*PowerMod[r, n, squareN], squareN];)

7) The recovered r is:
Let r=c^(N^-1 mod phi) mod N
Let r=615 (this part is ok)

here comes THE problem:
8) The recovered plaintext is(should be):
Let m=[( c*r^(-N) mod N^2 ) - 1 ] / N

As you can see here you have to calculate "modular inverse": r^-1 mod
But the problem is that r=615 does not have a mod inverse of mod N^2
Why? If you carefully observe r you can see that factors of r are: {3,
5, 41}. Look at that. 41 is a factor of r and it's also a chosen prime
p from first step, which makes it also a factor of N. That's bad!!

Solution to the problem:
part 5 needs to be changed from..to..
old) Let r be some random integer between 0 and N (problematic part)
new) Let r be some random integer between 0 and N, such that it has a
modular inverse of mod N (this implies that it'll have a modular
inverse of mod N^2)

You can download Mathematica notebook with practical implementation of
all this at: http://www.tekcities.com/mstampar/paillier.zip
Amitabh Saxena
2005-10-01 12:24:45 UTC
This does not seem to be a major problem. for a large enough n, the
probability of generating r such that GCD (r, n) > 1 is very low and
that is the only case when r does not have an inverse mod n.

An alternative way of looking at this is .. if you are able to find an
r such that GCD(r, n) > 1 than you have already broken the underlying
cryptosystem based on the difficulty of factoring.