Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my project I'm using the value of public exponent of 4451h. I thought it's safe and ok until I started to use one commercial RSA encryption library. If I use this exponent with this library, it throws exception.

I contacted developpers of this library and got the following reply: "This feature is to prevent some attacks on RSA keys. The consequence is that the exponent value is limited to {3, 5, 17, 257 or 65537}. Deactivating this check is still being investigated, as the risks may be great."

It's the first time in my life I hear that values other than {3, 5, 17, 257 or 65537} are used to break RSA. I knew only of using 3 with improper padding being vulnerable.

Is that really so? Surely, I can use another library, but after such answer I worried about security of my solution.

share|improve this question
2  
You can ask the developers for references, too... :) –  Mariano Suárez-Alvarez Feb 28 '11 at 14:29
3  
Don't try to do your own cryptography. Stick to what the package says. –  Yuval Filmus Feb 28 '11 at 15:44
1  
Of course, in your case, the package doesn't seem very trustworthy. So find a different one. –  Yuval Filmus Feb 28 '11 at 15:46
    
fermat primes ($2^n+1$) have simple binary representation so are used for computational convenience. –  yoyo Feb 28 '11 at 16:28
4  
If $2^m+1$ is a prime, $m$ is a power of $2$. –  Plop Feb 28 '11 at 19:30

3 Answers 3

up vote 5 down vote accepted

Like Yuval said, there is a performance reason: if you use $e = 2^k + 1$ for some (small) $k$, then computing $x^e \mod n$ is going to be faster than for most other exponents. Taking $k=16$ is very common and gives $e = 65537$, while taking $k$ equal to 1,2,4 or 8 give the other values in your library. Also, as these are (Fermat) primes, all $n = pq$ with $p \mod e \neq 1$ and $q \mod e \neq 1$ will give a valid $(n,e)$-combination, and many libraries build their $n$ this way, for efficient testing and generation of $n$. A small $e$ is potentially dangerous because of so-called broadcast attacks (sending 3 times the same message with $e = 3$ to 3 different people (with different moduli) compromises the message), even though this can be thwarted by padding, and small $e$ are thus often avoided. But in principle any large enough $e$ that is coprime with $\phi(n)$ can be used, provided that $d$ is not too small etc. So this library has chosen to optimize its generation and testing (take shortcuts that can be made for these choices of $e$) and disallow other $e$. There are standards that always take 65537 for $e$ (so you don't have to transmit that info), so this library is even flexible compared to that.

share|improve this answer

That sounds like rubbish to me. I think they are just trying to shut you up.

share|improve this answer

Actually, a small exponent like $3$ could spell trouble, at least if you're doing your best to do things wrong (say if the message, as a number, is "small") - something that can never be ruled out when cryptography is involved.

The reason that these exponents are used is that they're fast to compute. They can be computed by repeated squaring plus one multiplication (we need the exponent to be odd).

share|improve this answer

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.