The RSA private key contains 2 primes (of about 4096 bits each), and I only know their product (called modulus) and the modular inverse (called coefficient).

How do I recover the RSA primes from the modulus and the coefficient, i.e. how do I implement get_primes below?

def get_modulus_and_coefficient(prime1, prime2):
  assert prime1 > prime2
  coefficient = modinv(prime2, prime1)  # Modular inverse of prime2 modulo prime1.
  assert coefficient * prime2 % prime1 == 1
  modulus = prime1 * prime2
  return modulus, coefficient

def get_primes(modulus, coefficient):
  ... prime1, prime2 = ...
  assert get_modulus_and_coefficient(prime1, prime2) == (modulus, coefficient)
  return prime1, prime2

Is there a well known-recovery method published for this?

FYI This question is different from https://crypto.stackexchange.com/a/25910 . The other question asks for recovery of the primes $p_1$ and $p_2$ from $n$, $e$, $d$. This question asks for recovery of the primes $p_1$ and $p_2$ from $n$ and $q_\mathrm{inv}=p_2^{-1}\mod p_1$. The answer for the other question doesn't help at all with this question.


Your Answer

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

Browse other questions tagged or ask your own question.