Talk:TWINKLE
|
|
special structure for nrs sieveable by TWINKLE?
Arvindn, I can surmise, but I'm loath to do so as assumptions often land one in the soup. Does the existence of a proper TWINKLE (or TWIRL) implementation imply that 512 digit numbers are so easily factored that they should not be used in crypto applications depending on difficulty of factoring? If so, does this malediction for numbers with some properties extend to others; even if not so drastically? For example, would a 513 digit number be much easier to factor as being 'closely related' to 512 digit numbers? This is something which, I think, ought to be addressed here.
By the way, excellent enlargement of this article. It clearly took some effort to be that clear on such a topic. Thanks for it. ww 14:15, 19 Jul 2004 (UTC)
- Hi,
- First of all, the hardness is not dependent on any special property of the number 512. (Its bits by the way, not digits.) If 512 bits is easy then 513 is equally easy. Hardness grows superpolynomially but subexponentially with key size. RSA implementations almost always use power-of-two moduli, so that's why one considers the hardness of factoring 512 bits rather than (say) 500.
- As for whether TWINKLE/TWIRL renders 512/1024 bit exponents useless, what I know is this:
- There are two steps in QS/NFS. Although the sieving step is much more time consuming than the second step (matrix step), it is highly parallelizable but the matrix step is not. In the squeamish ossifrage cracking effort, for example, the second step was done on a big iron Sun Sparc with over a gig of RAM.
- TWINKLE can trivially do the sieving step for 512 bit exponents. TWIRL can do the sieving for 1024 bit exponents, but only just. It will cost a lot more money to build than TWINKLE, and Shamir says it is infeasible for the moment to extend it to about 1100 bits without improvements in the math.
- The matrix step (for 1024 bits) is much less clear. I read a paper that disputes Shamir et al's assertion that the sieving step is costlier for 1024 bits. Hardware devices for implementing the matrix step have also been proposed, but on the whole it has received much less research attention and it is not very clear what its cost is.
- So the conclusion is, until such time as an analog of the EFF DES cracker is built, the answer to "can 1024 bit moduli be used" is "depends on who your enemies are". For 512 bits the threshold is much lower. Arvindn 19:56, 19 Jul 2004 (UTC)
finger gremlins
- Arvindn, Thanks for the reply. It's finger gremlins that think it's digits, not me. I knew it was bits, all along! So then, it's not a special structure of a number, it's any number at all, with capacity limitations depending on size. I wish Shamir would quit changing everything under our feet all the time. The quicksand feeling is most disturbing! ww 15:16, 20 Jul 2004 (UTC)