Is it possible to validate a Public Key in RSA? 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)
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.