Re: Two tidbits of potential interest
On Fri, 25 Sep 2009 19:22, marcio.barb...@gmail.com said: And as a conclusion, Elgamal problems would be harder to solve. Is it correct? No; it is not sure that the discrete logarithm problem is harder to solve that the factoring problem. Shalom-Salam, Werner -- Die Gedanken sind frei. Auschnahme regelt ein Bundeschgesetz. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Two tidbits of potential interest
On Thu, 24 Sep 2009 21:13, marcio.barb...@gmail.com said: 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? Yes. All real world asymmetric algorithms are build on a hard so solve computional problem. Factoring is such a hard problem and the RSA algorithm is based on it. Another widely used hard problem is solving the discrete logarithm, the DSA and Elgamal algorithms are based on it. Shalom-Salam, Werner -- Die Gedanken sind frei. Auschnahme regelt ein Bundeschgesetz. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Two tidbits of potential interest
On Sep 24, 2009, at 3:13 PM, M.B.Jr. wrote: On Thu, Sep 24, 2009 at 2:21 PM, David Shaw ds...@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 ds...@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= 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 ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Two tidbits of potential interest
Hi Werner, On Fri, Sep 25, 2009 at 6:19 AM, Werner Koch w...@gnupg.org wrote: On Thu, 24 Sep 2009 21:13, marcio.barb...@gmail.com said: 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? Yes. All real world asymmetric algorithms are build on a hard so solve computional problem. Factoring is such a hard problem and the RSA algorithm is based on it. Another widely used hard problem is solving the discrete logarithm, the DSA and Elgamal algorithms are based on it. so, focusing on key pair generation, one could state RSA keys are built upon the product of large primes, which would put factoring as the main problem to be solved; whereas Elgamal keys are more complex than that, once it involves primes under the discrete logarithms' context. And as a conclusion, Elgamal problems would be harder to solve. Is it correct? Regards, Marcio Barbado, Jr. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Two tidbits of potential interest
Hi David, about the first tidbit: On Tue, Sep 22, 2009 at 6:08 PM, David Shaw ds...@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= dummy question: by factoring a public key integer, one can get somehow to its corresponding private key? Regards, Marcio Barbado, Jr. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Two tidbits of potential interest
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 ds...@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= 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. In the case above, it seems TI was using that 512-bit key to ensure that only TI could generate software images for their calculator. With the key factored, anyone can sign a software image. David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Two tidbits of potential interest
On Thu, Sep 24, 2009 at 2:21 PM, David Shaw ds...@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 ds...@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= 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? Marcio Barbado, Jr. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Two tidbits of potential interest
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= Also, here's the Stick Figure Guide to AES: http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Two tidbits of potential interest
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Hi List readers, thanks to David Shaw for the nice URL: http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html This one I like very much; The pencil and paper approach. Also, here's the Stick Figure Guide to AES: http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html David however we will need elliptic curve ciphers in the next years or so? Sincerely yours, Morten 0x81802954 -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (SunOS) Comment: For keyID and its URL see the OpenPGP message header iEYEARECAAYFAkq5Q6wACgkQ9ymv2YGAKVT7UgCfTAcsbpME8FbBdEhnW7psURR2 5wMAoMb9jmrGS8KrZn0MNGE2YXbMR4+W =ttIc -END PGP SIGNATURE- ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
