Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)

share|improve this question
2  
There are (rarely used) variants of RSA with more than two prime factors, so as long as the modulus $m$ and the public exponent $e$ are coprime, you can encrypt data with them. A sensible sanity check would be to verify that (1) gcd($m$, $e$) = 1; (2) $m$ does not have small prime divisors (test division with primes up to $2^{16}$) and (3) (only if you want to be extra sure) use Lenstra's elliptic curve factorization algorithm to check that $m$ does not have smallish factors. If anyone is able to decrypt, you cannot check. –  j.p. Jan 10 '12 at 9:05
add comment

3 Answers

up vote 7 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
downvote without a comment is lame! –  hrishikeshp19 Mar 4 at 1:32
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.