Two tidbits of potential interest

[David Shaw]

On Sep 24, 2009, at 3:13 PM, M.B.Jr. wrote:

> On Thu, Sep 24, 2009 at 2:21 PM, David Shaw <dshaw at jabberwocky.com>  
> wrote:
>> On Sep 24, 2009, at 12:30 PM, M.B.Jr. wrote:
>>
>>> Hi David,
>>>
>>> about the first "tidbit":
>>>
>>>
>>> On Tue, Sep 22, 2009 at 6:08 PM, David Shaw  
>>> <dshaw at jabberwocky.com> wrote:
>>>>
>>>> First of all, someone has factored a 512-bit RSA key (the one  
>>>> used to
>>>> protect a TI programmable calculator, it seems).  It took 73 days  
>>>> on a
>>>> dual-core 1900Mhz Athlon64.  It took just under 5 gigs of storage  
>>>> and
>>>> around
>>>> 2.5 gigs of RAM.  In other words: not much at all.  It's not some  
>>>> big
>>>> distributed project - rather it's a single guy who wanted to  
>>>> factor it
>>>> and
>>>> just left it running in the background for 2 and a half months.   
>>>> (This is
>>>> actually a month old - forgot to send it before now).
>>>>
>>>> http://www.unitedti.org/index.php?showtopic=8888
>>>>
>>>
>>>
>>> dummy question:
>>>
>>> by factoring a public key integer, one can get somehow to its
>>> corresponding private key?
>>
>> Yes, that's exactly what happens.  If you factor the public key,  
>> you can
>> derive the private key.
>>
>
>
> Is this a generic asymmetric premise?
> I mean: is it valid both to the (computational) Mathematics behind
> OpenPGP's and X.509's public keys' integers?

Factoring is an attack against RSA.  It applies to wherever RSA keys  
are used, whether OpenPGP, X.509, or whatever you like.

This idea is not specific to RSA though: there are other, similar (in  
general concept, though not in the specific math of course) attacks  
against other asymmetric systems.  The goal is to make it hard (for  
whatever definition of "hard" works for your particular environment)  
to derive anything non-public from the public key.

Keep in mind that nobody has used a 512-bit key in many years (they're  
too small, as this result makes clear).  It seems TI's mistake here  
was in choosing a 512-bit key in the (around) 1999-2001 time frame,  
and not realizing that less than a decade later, that key length would  
be small enough for someone to factor in their spare time.  It's a  
little surprising, as it was well known around that time that 512 bits  
were not sufficient.  I wonder if the memory size and CPU capability  
of what is essentially a pocket calculator influenced that decision.

David