1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

RSA encryption problem

  1. May 14, 2009 #1
    1. The problem statement, all variables and given/known data
    This is a problem my lecturer did in class but I'm a bit confused.

    We have 2 large primes p=137 and q=131, choose e = 3
    n = pq = 137.131 = 17947
    (p-1)(q-1) = 136.130 = 17680

    Compute d = e-1 mod (p-1)(q-1) = 3-1 mod 17680 = 11787.

    This is where I'm confused. How did he get d=11787?

    2. Relevant equations


    3. The attempt at a solution
    I think I'm supposed to use the Euclidean algorithm to find d, but he didn't show how.
     
    Last edited: May 14, 2009
  2. jcsd
  3. May 14, 2009 #2
    for d to be the multiplicative inverse of 3 mod 17680 you need 3*d = 1 mod 17680; there will be a unique positive d < 17680 for which this is true, and this d can be found using the extended euclidean algorithm. the following page will be helpful:
    http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html [Broken]

    for your problem you will start
    17680 = 5893(3) + 1
    and the euclidean algorithm terminates quickly because
    3 = 3(1) + 0
    rearranging the line above you get
    1 = 17680 - 5893(3)
    so you know that d = -5893, which is 11787 mod 17680.
     
    Last edited by a moderator: May 4, 2017
  4. May 15, 2009 #3
    Lindsay Childs in "A Concrete Introduction to Higher Algebra" deals with RSA details if you need more information.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: RSA encryption problem
  1. RSA Encryption (Replies: 2)

Loading...