Timeline for modular exponentation for RSA, why is 2^16 + 1 commonly chosen?
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 25, 2018 at 8:54 | comment | added | fgrieu | For why security authorities recommend $e=2^{16}+1$ rather than $e=3$, see this. | |
| Dec 18, 2010 at 10:32 | comment | added | Henno Brandsma | Also, e=3 has the disadvantage that it might be vulnerable to the broadcast attack. If you send a message x using e=3 to 3 different users (with different n_1,n_2,n_3, WLOG, mutually relatively prime (or we'd have a factorisation of 2 of them..) then we could solve x^3 mod n_i (i=1,2,3) using the CRT for x. This is a problem if e=3 were a common exponent. Hence the choice for a relatively large e (also prime and few bits set). | |
| Mar 7, 2010 at 6:08 | vote | accept | sj steve | ||
| Mar 3, 2010 at 14:47 | comment | added | François G. Dorais | Yes, that is fine for e=3. It is already difficult for e=5 without further decreasing the key space and/or increasing the key-generation cost. (Note that the real issue with e=3 is the risk of small exponent attacks.) | |
| Mar 3, 2010 at 14:30 | history | edited | François G. Dorais | CC BY-SA 2.5 |
clarification and correction
|
| Mar 3, 2010 at 6:41 | comment | added | aorq | @François G. Dorais: If e=3, couldn't you just avoid generating primes that are 1 mod 3? I assume 0 mod 2 and 3 are being avoided already to save some time. It's not hard to take a random number k and consider 6k+5 as a potential prime. | |
| Mar 3, 2010 at 0:03 | comment | added | François G. Dorais | I guess a third advantage of 65537 is that it is the smallest exponent allowed by NIST, though they don't give a specific reason for that choice. (Probably to avoid small exponent attacks, which are possible when proper padding is not used.) | |
| Mar 2, 2010 at 23:27 | history | answered | François G. Dorais | CC BY-SA 2.5 |