Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Aug 17, 2009 #1
    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. jcsd
  3. Aug 17, 2009 #2
    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
     
  4. Aug 18, 2009 #3
    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
  5. Aug 18, 2009 #4
    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
  6. Aug 18, 2009 #5
    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.
     
  7. Aug 18, 2009 #6
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How can I compute r from: c = g^m * r^N mod N^2
  1. R-n and R-m (Replies: 2)

  2. R^n and R^m (Replies: 3)

Loading...