Re: RSA key length and more

"Pubkeybreaker" <Robert_silverman@raytheon.com> writes:

> Paul Leyland wrote:
> > "Pesso" <pesso@no.where> writes:
> >
> > > Why is a private key longer than a public key?
> >
> > It isn't, assuming you mean "exponent" where you used the word "key".
> > Or, to be precise, it need not be shorter. There is absolutely
> > nothing to stop you having a shorter private exponent than an public
> > exponent.
> >
>
> Almost. While it is true that there is nothing in theory that prevents
> it,
> there is a viable attack, using Lattice Basis Reduction that will break
> RSA if the private exponent is less than N^alpha where N is the
> modulus and
> alpha is approximately .29

Thank you. I was insufficiently precise about the practical
implications (but see my final paragraph).

There is, of course, nothing to stop you choosing your private
exponent to have the value 3, in general, other than the uncomfortable
observation that a linear search through possible exponents will very
rapidly break your security. As you note, better algorithms exist
than linear search.

But, hey, this was so obviously a homework question that I regarded it
as fair game to give a correct but seriously misleading answer. If
the guy wants us to do his homework for us, the very least he should
do is either check the answers or take the consequences.

Paul

-- 
Hanging on in quiet desperation is the English way.
The time is gone, the song is over.
Thought I'd something more to say.