1
$\begingroup$

Given two public keys, n1 and n2 (and e the exponent)--how would one generate a private key for n1? In this scenario, n1 and n2 share primes.

I know I need to use $$d = e^{-1} \space mod \space (p-1)(q-1)$$--but we don't know p or q. How would you go about this?

$\endgroup$
1
$\begingroup$

Assuming that $n_1$ and $n_2$ are RSA moduli: the common prime $p$ is $\gcd(n_1, n_2)$, easily computable by Euclid's algorithm. We then know $q = \frac{n_1}{p}$ and now you're good to go.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! I was just about to post this as an answer myself. $\endgroup$ – throwawayhmwk Mar 28 '17 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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