2
$\begingroup$

I have placed a bet that I can create a public key such that my adversary will not be able to crack (decrypt) it for at least one week. For my primes $p$ and $q$, I chose very large numbers that are $101$ digits long, each. I also tried to make them to be as distinct as possible.

Now what I am wondering is whether to choose a big encryption exponent or a small one. Since I have began my study of Cryptography about a month ago, I am not too familiar with choosing a solid encryption exponent. I heard that choosing the digits $3, 5, 17, 257$ or $65537$ would give me a good security but I have not read about it. I was thinking of going with $257$ because intuition tells me that there exists a inverse relation between the two: when choosing large primes for $p$ and $q$, then pick a small encryption exponent and vice versa. But I don't know if this makes complete sense in some regards.

Any input is appreciated.

Improve this question
$\endgroup$
7
  • $\begingroup$ By RSA standards, 101 digit primes isn't long enough; modulii larger than 202 digits have been factored. It has taken longer than one week; however that will probably change as the adversary's computers get faster. $\endgroup$
    – poncho
    Oct 24, 2013 at 18:22
  • $\begingroup$ @poncho We have agreed on fixed 101 digits. $\endgroup$
    – hhel uilop
    Oct 24, 2013 at 18:23
  • $\begingroup$ Then, it doesn't really matter what encryption exponent you use; it all comes down to what resources your adversary has. If it is, say, the NSA (or anyone else with access to both the expertise with NFS and significant amounts of computing resources), you've just lost your bet; they are likely to be able to factor the modulus within a week, and at that point, it won't matter what exponent you use. If it is, say, a lone hacker with just his laptop, you're pretty safe. $\endgroup$
    – poncho
    Oct 24, 2013 at 18:37
  • $\begingroup$ It is a lone hacker who has as much training as I have (I hope at least) with access to Maple. $\endgroup$
    – hhel uilop
    Oct 24, 2013 at 18:44
  • $\begingroup$ So is there much difference between choosing 257 or 65537 for encryption exponent? $\endgroup$
    – hhel uilop
    Oct 24, 2013 at 18:45

1 Answer 1

Reset to default
2
$\begingroup$

Factoring the modulus, by definition, does not uses the public exponent, just the modulus. In fact, it is easy to see that the public exponent has no impact whatsoever on security until it is actually used, e.g. something is decrypted or signed.

For the security of the algorithm (not just the key), it is not known whether a short public exponent induces extra weaknesses. Some people have feared it so, but in fact, for all we know, the shortest possible public exponent ($e = 3$) is as good as any other.

With some details:

  • All other things being equal, a short public exponent implies better performance of public-key operations (message encryption, signature verification), so that's a good idea.
  • Some widely deployed implementations of RSA cannot use public exponents which do not fit in 32 bits, so you need, for interoperability, to keep your public exponent short.
  • A short private exponent may induce trouble. If you want to force the private exponent to be short (and that's a bad idea) then you must allow the public exponent to be big (about as big as the modulus). So this is an argument for a short public exponent: it prevents the private key generation system from doing something tempting (for performance) but stupid (for security).
  • There is a widespread tradition of using $e = 65537$ and not $e = 3$, because of an old myth about a possible attack which does not actually apply to properly used RSA (see this for some details).

As has been pointed out, two 101-digit primes imply, in bits, a 670-bit or so modulus. It so happens that the current World record for a RSA modulus factorization is for a 768-bit integer -- and it took a lot more than one week (depending on how you look at it, it took between two and four years; and it included some heavy thinking by really smart people). So your bet is quite safe, provided that you did not botch the prime generation. In particular, sentences like this:

I also tried to make them to be as distinct as possible.

make me fear the worst. The good way to generate the two primes is to generate both of them randomly with, as most as is feasible, uniform generation. A lot of well-intentioned "fixes" like the one you may allude to above can easily turn, in fact, into big weaknesses. You should refrain from that. Randomness is enough.

(Similarly, I hope you used a proper cryptographically strong source of randomness. And, more generally, just use some existing software like OpenSSL: this will be vastly easier and safer.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Minor nit: two 101-digit primes imply a 670 bit (or so) modulus; somewhat smaller than the current World record. $\endgroup$
    – poncho
    Oct 24, 2013 at 19:45
  • $\begingroup$ You're absolutely right. It seems that in the afternoon I no longer succeed at multiplying 335 by 2 correctly. I shall presently fix my answer. $\endgroup$
    – Thomas Pornin
    Oct 24, 2013 at 19:49
  • $\begingroup$ uses $\mapsto$ use $\;$ $\endgroup$
    – user991
    Oct 24, 2013 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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