3
$\begingroup$

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.

$\endgroup$

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.