# How can I compute r from: c = g^m * r^N mod N^2

1. Aug 17, 2009

### vanvincent

How can I compute "r" from: c = g^m * r^N mod N^2

How can I compute "r" from: c = g^m * r^N mod N^2, when all values except r are known?

This is the encryption scheme for the paillier cryptosystem. The ciphertext c, plaintext m, and the public key <n, g> is known and I need to find the integer r used for the encryption. My number theory is a little rusty. Thanks!

2. Aug 17, 2009

### vanvincent

Re: How can I compute "r" from: c = g^m * r^N mod N^2

and we also know the prime factors p and q of n, such that n = p * q

3. Aug 18, 2009

### ramsey2879

Re: How can I compute "r" from: c = g^m * r^N mod N^2

My bet is that there is no known solution but trial and error. If you find it submit your resume to the CIA. To start substitute x (found by computation) for g^m then compute c/x mod N^2. For the latter part you add N^2 (Mod x) to c repeatedly until it is divisible by x

Last edited: Aug 18, 2009
4. Aug 18, 2009

### ramsey2879

Re: How can I compute "r" from: c = g^m * r^N mod N^2

Foolish of me to say mod x!! 1/13 mod 25 = 26/13 = 2 mod 25 but if I added only 12 to 1 and divided by 13, I would get 1 but 2*13 = 26 = 1 mod 25 so the correct answer will not be found if you add N^2 (mod x). It can be done the way I first suggested but you must keep track of how many times you added (say n times m is added to c and then divided by x) then to this result you would add n * (N^2-m)/x. 1*(25-12)/13 + 1 = 2 which is correct when you figure 1/13 Mod 25.

Last edited: Aug 18, 2009
5. Aug 18, 2009

### ramsey2879

Re: How can I compute "r" from: c = g^m * r^N mod N^2

So if you had the problem

1 = 17^63 * r^5 mod 25

you would reduce 63 to 3 by repeatedly dividing by 17^20 which = 1 mod 25 since there are 20 numbers that are both prime to 25 and less than 25 (Euler's Theorm) then compute 17^3 = 13 mod 25. Then you would find 1/13 mod 25 which as shown above = 2 (= a)

The problem then becomes finding b from the equation a = b^x mod c which is the topic of your earlier thread.

6. Aug 18, 2009

### vanvincent

Re: How can I compute "r" from: c = g^m * r^N mod N^2

thanks ramsey for the detailed answer! any suggestions then on how to solve a = b^x mod c, for b?