Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

How would one find the secret key in a simple RSA encryption when given p, q and e?

share

1 Answer 1

up vote 10 down vote accepted

You've already been given everything you need to decrypt any messages.

RSA key generation works by computing:

  • n = pq
  • φ = (p-1)(q-1)
  • d = (1/e) mod φ

So given p, q, you can compute n and φ trivially via multiplication. From e and φ you can compute d, which is the secret key exponent. From there, your public key is [n, e] and your private key is [d, p, q]. Once you know those, you have the keys and can decrypt any messages - no cracking necessary!

More details are available here.

share
2  
Thanks. This kinda makes sense, though I had trouble with calculating d. Ended up using the extended Euclidean algorithm. –  Johan K. Jensen Dec 19 '12 at 11:38
    
@Josso Yeah, that's probably the best way to calculate d, when you consider the 1/e step is really e^-1. –  Polynomial Dec 19 '12 at 12:01
    
@Polynomial - those are the same thing; x^-n = 1/(x^n). The equation can also be stated de = 1 (mod φ), making what you're trying to do easy to explain; find an integer d whose product with e = kφ+1 for an arbitrary k. –  KeithS Dec 19 '12 at 15:23
    
@KeithS I'm aware (they don't call me Polynomial for nothing!). The reason I mentioned the alternative form is that most implementations of large number libraries have the ability to raise an integer to an arbitrary exponent, but not as many have explicit division capabilities. –  Polynomial Dec 19 '12 at 15:28

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .