11

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

1 Answer 1

15

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.

4
  • 2
    Thanks. This kinda makes sense, though I had trouble with calculating d. Ended up using the extended Euclidean algorithm.
    – johankj
    Dec 19, 2012 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, 2012 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, 2012 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, 2012 at 15:28

You must log in to answer this question.

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