Miroslav Stampar

2005-09-29 05:48:31 UTC

Permalink

Before you continue to read further, I suggest you to look/read twoRaw Message

papers:

(easy) http://en.wikipedia.org/wiki/Paillier_cryptosystem

(official)

http://www.gemplus.com/smart/rd/publications/pdf/Pai99pai.pdf

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"

Encryption

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];)

Decryption

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

N^2

But the problem is that r=615 does not have a mod inverse of mod N^2

(N^2=3108169)

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