Timeline for Bleichenbacher's Attack on high public exponent RSA keys?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 18, 2017 at 13:28 | comment | added | Squeamish Ossifrage | @fgrieu: 15 is just a couple off-by-one errors away from 8 in that formula, and as we all know, there are only two hard problems in computing: naming, cache invalidation, and off-by-one errors! As for RSA-FDH, I'm not aware of a standard, but, e.g., djb's Rabin–Williams instantiation uses a prescribed hash function, and you could trivially instantiate it with SHAKE256. | |
| Sep 18, 2017 at 13:06 | comment | added | fgrieu♦ | @Squeamish Ossifrage: The difference in RSA public-key function timing between $e=65537$ and $e=3$ is usually by about a factor slightly below $(16+1)/(1+1)$ (that is like eight, not "fifteen"), often less for implementations using Montgomery arithmetic or DPA countermeasures (the later makes sense for encryption, and the former allows code reuse). I'm seeing RSA-FDH as a design principle for deterministic RSA signature schemes, prescribing to use a public hash into $\mathbb Z_N$. Is there a specification for RSA-FDH, in the sense that it allows implementations to inter-operate? | |
| Sep 18, 2017 at 10:36 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Well, 65537 is not quite "prescribed" quite "everywhere" by quite all security authorities.
|
| Sep 18, 2017 at 6:24 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Polish
|
| Sep 17, 2017 at 23:41 | comment | added | Squeamish Ossifrage | @fgrieu: Don't forget the much simpler, faster, safer schemes RSA-FDH and RSA-KEM! | |
| Sep 17, 2017 at 23:27 | comment | added | Squeamish Ossifrage | Are you measuring the public-key operation or the private-key operation? The performance of the private-key operation is independent of the public exponent (unless you choose a small private exponent and derive the public one from that, but that's a bad idea). The performance of the public-key operation is $(\text{cost of $|n|$-bit squaring})\cdot\log_2 e + (\text{cost of $|n|$-bit multiply})\cdot\operatorname{Hamming-Weight}(e)$. It is usually quite easy to measure the difference in public-key operations between $e = 3$ and $e = 65537$: the latter is approximately fifteen times slower. | |
| Sep 17, 2017 at 21:50 | comment | added | Maarten Bodewes♦ | Trying different values for $e$ didn't produce any noticeable slowdown using the default Java RSA implementation, so it may be common to chose F4 but in real life the expected speedup may be non-existent. By now it is just a sensible default, I guess. | |
| Sep 17, 2017 at 19:28 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Polish
|
| Sep 17, 2017 at 15:47 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Split
|
| Sep 17, 2017 at 10:11 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Polish
|
| Sep 17, 2017 at 10:00 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Polish
|
| Sep 17, 2017 at 9:50 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Polish
|
| Sep 17, 2017 at 8:13 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
deleted 49 characters in body; edited body
|
| Sep 17, 2017 at 7:51 | history | answered | fgrieu♦ | CC BY-SA 3.0 |