Re: RSA key length and more

Paul Leyland <paul@leyland.vispa.com> writes:

>"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".

I guess the public key is both the "exponent" which is usually very short,
and the modulus (N) which is much longer. The private key need only have d,
the private exponent which is about as long as N is, but often also
includes the two factors of N as well, which in general would make it about
twice as long as the public key.

The two factors are not necessary but are useful.
Of course all kinds of things could be stored in the "private key" or the
"public key". The date of generation, the address of the person who owns
it, the astrological sign of the owner, a copy of his favourite music, etc.
That is entirely up to the software writer. So the question is really
meaningless. Ie, the length of the private key and public keys are
arbitrary, above some minimum of roughly the length of N.

>> > 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.
Received on Thu Jan 19 03:45:04 2006