Is it possible to validate a Public Key in RSA?

Question

If I have a 1024-bit number, and someone is telling me that it is in fact a valid RSA public key, is there any way I can quickly validate that it is indeed so (without cracking RSA)?

(I suppose I am asking if it's possible to quickly tell if a number only has 2 prime factors)

Answer 1

There are two approaches to such a validation:

• Test: you can look at the number and decide without involving the person who gave it to you.
• Proof: The person who generated the number can also give you additional information that will convince you it is a correct RSA number.

There are no tests for RSA numbers.

There are proofs for RSA numbers, including "zero-knowledge" proofs. Zero-knowledge means that the person who generated the number can convince you it has two prime factors without giving you any information about what the two factors are.

A zero-knowledge proof can be interactive: you and the generating party exchange messages (akin to challenges/responses) that lead you to become convinced. It can also be non-interactive: its a transcript that convinces anyone who looks at it. Thus if the generating party gives you the number and the proof, you can forward that to anyone else and they too will be convinced. With interactive proofs, unless you are watching each message go back and forth and know that the two parties that are interacting are not colluding, you can't be convinced it is correct.

Answer 2

No, we do not know an algorithm running in linear time (or even polynomial time, relative to the number of digits in $n$) that outputs 'true' if $n$ is the product of exactly two prime numbers, and 'false' otherwise.

If such an algorithm existed, I do not see that it would imply possibility to factor $n$, or otherwise break RSA. For sure, it would not be a good test that an RSA key is secure (we know ways to generate valid RSA keys that in fact are factorisable by one knowing some secret, and can't be detected even with knowledge of the factorization of $n$).

To my knowledge, the closest thing we have is

• testing if $n$ is prime, and in that case output "false";
• else, try factoring $n$ using a state of the art implementation of ECM (e.g. EECM-MPFQ) for an effort having good odds to factor $n$ assuming its smallest factor was about $n^{1/3}$, and
• if that fails to exhibit a factor, either
  • output "likely true" if that's good enough a result, or
  • factor $n$ using GNFS then proceed
• run a primality test on the exhibited factors and output "true" (for two prime factors) or "false" (otherwise).

For small odds of falsely outputting "likely true" (including zero if we are willing to run GNFS), that algorithm is sub-exponential (in the number of digits in $n$), but super-polynomial.

---

With the above negative answer, the question as formulated explicitly does not ask if we can test in polynomial time whether $\gcd(\phi(n),e)=1$ given $(n,e)$; but I wish I knew the answer!

Answer 3

If you just have a 1024-bit number then no, you cannot tell if it is an RSA key. You could encrypt something via RSA with any number.

You could disprove it is a key by checking it against common prime factors and seeing if it has more than 2 of them. There may be other estimation methods, but without checking every possible prime you cannot prove it only has two primes.

Answer 4

You cannot determine nature of factors before factorization.

In RSA, time required to factorize public key is directly proportional to smaller of the two factors.

Keeping this in mind, you can use some heuristics to conclude probable RSA public key. All you have to do is pick a large number X, and try to find divisor of N from 2 to X. If you do not find anything, you can assume that N is public key in RSA and both of its factors are greater than X.