Miroslav Stampar
2005-09-29 05:48:31 UTC
Before you continue to read further, I suggest you to look/read two
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
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