Re: gnupg rsa question // why use e of 41 ?

David Wagner wrote:
daniel bleichenbacher wrote:
There are many attacks that work
well with very small exponents such as e=3, but don't work or are much
harder with e=65537 or larger.

Sure, but not if you use proper padding. If you use appropriate padding,
I'm not aware of any attack that works against e=3 but fails against

Coppersmiths short padding attack is just one example.

And you'd have to be crazy not to use proper padding.

Let's call people that make mistakes implementing a padding scheme
careless not crazy.

Of course these attacks can be avoided
if implemented correctly. But implementations do have mistakes.

Well, maybe. Personally I'd be more inclined to spend the time to
examine the implementation to make sure it is done correctly, rather than
increasing e and hoping that the large e will cover up implementation

Certainly, everone should check their implementations carefully.
And just to be clear, I think most implementators are not testing their
implemenation careful enough.
But, can you be sure to find all implementations errors?
So what is wrong with trying to make your implementation a little bit
more robust?

I suspect that, for every possible implementation mistake
that renders e=3 insecure but poses no risk to e=65537, there are a
half dozen possible implementation mistakes that render both choices
insecure, so there is no getting around the need for careful scrutiny
of the implementation.

Mere speculation? It's certainly not my experience.

It's even remotely possible that using e=65537 may make things worse,
because using e=65537 probably requires the encryption routine to
call a general-purpose modular exponentiation subroutine, whereas e=3
only requires the encryption routine to call modular multiplication
and a modular squaring subroutines, which are simpler. When it comes
to risk of implementation mistakes, it is remotely possible that the
added opportunities to make mistakes in the encryption routine might
counterbalance any other benefits of e=65537. I think this is a little
far-fetched, but not entirely impossible.

Have you seen any implementation mistakes in the wild that render the
library insecure with e=3 but secure with e=65537?

I have seen such libraries. And I have a quite educational flaw I'd
to publish sometimes. But the company I worked for has so far not
the paper.

Can you share a
concrete example or two? Maybe I'm just having a hard time imagining
how an implementation error could compromise e=3 but not compromise
e=65537, if the developer knows what they're doing. Seeing an example
might be enlightening.

P.S. In any event, I'm still suspicious that the comment in the GPG
source code indicates a developer who didn't understand these issues
and wasn't doing an analysis of anywhere near this depth.

Well, my first impression was that you tried to ridicule the GPG
for his comment. I personally don't find anything wrong with trying to
an implementation a little bit more robust against unknown attacks.
All he needed to know is that smaller exponents might be more risky
bigger ones. I prefer developers that try to be on the safe side to the
that spend most of their time optimizing the running time of their

Daniel Bleichenbacher