Stop Gpcode!

[Visu]

Originally Posted by xilman

How about a side bet?

Same conditions except that there's no requirement that the factorization be performed by GNFS but, rather, is a demonstration of an algorithm and its implementation which is capable of factoring a hard 1024-bit (or greater) integer.

The quantum computer people, last time I heard (8 years ago) were also predicting "15-20 years" for kilobit factorizations by Shor's algorithm. We've no idea (at least, I've no idea) whether a new algorithm will turn up in the near future. If it does, or if the QC people hit their target, it may well be possible to perform a kilobit GNFS within ten years but not cost-effective to do so. Compare the situation with 512-bit factorizations. It's undoubtedly possible to do one with QS now but there's no real incentive to prove that claim.


Paul

Seems to me that if you win this bet, you might lose the other one. If there is another even better algorithm, people would be less inclined to use GNFS.

[xilman]

Originally Posted by Visu

Seems to me that if you win this bet, you might lose the other one. If there is another even better algorithm, people would be less inclined to use GNFS.

Think about my possible reason(s) for making the second bet.

Paul

[Visu]

Originally Posted by xilman

Think about my possible reason(s) for making the second bet.

Paul

Well you seem to have increased your chances of not losing by adding the second bet.

[Robert Holmes]

At Crypto 2008 was presented an attack against GPcode.

Unsurprisingly, the attack vector was not the RSA modulus, but the weak stream cipher used to encrypt the files (RC4, sigh).

[xilman]

Originally Posted by R.D. Silverman

The progress has come from two sources: new algorithms and faster/bigger
computers. We have not had a new algorithm in 20 years. Determining how
much more can be squeezed from NFS via faster/bigger computers is
problematic. Note that new algorithms alone have not helped. GNFS
could not have even been run on computers from (say) 1987. They did not
have enough memory.

Bob, you disappoint me. You've a well-deserved reputation for requiring posters to use precise language and then you fall down on this one.

There's no doubt that GNFS could have run on 1987-era machines. Out-of-core sieving and linear algebra could have been done. A gigabyte or few of disk space was relatively cheap even then. At that time the oil companies already had terabyte disk arrays and petabyte tape libaries to hold all their seismological data.

If you had written something like "GNFS would have been very slow" or "GNFS would not have been cost-effective" I'd have no argument.

Paul

[R.D. Silverman]

Originally Posted by xilman

Bob, you disappoint me. You've a well-deserved reputation for requiring posters to use precise language and then you fall down on this one.

There's no doubt that GNFS could have run on 1987-era machines. Out-of-core sieving and linear algebra could have been done. A gigabyte or few of disk space was relatively cheap even then. At that time the oil companies already had terabyte disk arrays and petabyte tape libaries to hold all their seismological data.

If you had written something like "GNFS would have been very slow" or "GNFS would not have been cost-effective" I'd have no argument.

Paul

Please. A new workstation in 1987 was a SUN-3/75 or perhaps a SPARC-1.
It had (fully loaded) 4-8Mbytes (not Gbytes) of memory. The factor base
for even 100-digit SNFS jobs would not have fit in memory. An out-of-core
siever would have been so slow that it would not be worth doing. The
LA would have been even worse. QS would have been faster. And the
largest matrices that we could deal with at that time had only about 80K
rows.

[xilman]

Originally Posted by R.D. Silverman

Please. A new workstation in 1987 was a SUN-3/75 or perhaps a SPARC-1.
It had (fully loaded) 4-8Mbytes (not Gbytes) of memory. The factor base
for even 100-digit SNFS jobs would not have fit in memory. An out-of-core
siever would have been so slow that it would not be worth doing. The
LA would have been even worse. QS would have been faster. And the
largest matrices that we could deal with at that time had only about 80K
rows.

I'm not denying any of that, apart from the last (a 1M dense bit-matrix fits into 128G, slow but possible). I'm asking only for precision in language.



Paul

[jasonp]

Originally Posted by Robert Holmes

At Crypto 2008 was presented an attack against GPcode.

Unsurprisingly, the attack vector was not the RSA modulus, but the weak stream cipher used to encrypt the files (RC4, sigh).

This is very cool, but I predict the next gpcode version will use 128-bit AES. Good luck cryptanalyzing that...

It's just another escalation in the malware arms race. Meanwhile the authors continue to get rich.