How would one find the secret key in a simple RSA encryption when given p, q and e?
Add a comment
|
1 Answer
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.
answered Dec 19, 2012 at 10:13
-
2Thanks. This kinda makes sense, though I had trouble with calculating d. Ended up using the extended Euclidean algorithm.– johankjDec 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. 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.– KeithSDec 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. Dec 19, 2012 at 15:28