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

[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!

 

[vanvincent]

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

 

[ramsey2879]

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!

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

 

[ramsey2879]

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

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.

 

[ramsey2879]

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.

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 theorem) 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.

 

[vanvincent]

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