|
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:
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. |
|||
|
|
|
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. |
|||
|
|
|
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. |
|||
|
|
