Tell me more ×
IT Security Stack Exchange is a question and answer site for IT security professionals. It's 100% free, no registration required.
up vote 7 down vote favorite
1

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

share|improve this question

1 Answer

up vote 9 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|improve this answer
2  
Thanks. This kinda makes sense, though I had trouble with calculating d. Ended up using the extended Euclidean algorithm. – Josso 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.