3 ms·

i'm thinking they grossly overestimate the problem of cracking a 1024-bit prime... based on my dabbling in that area its certainly possible for a network of mac

by jheriko 10y ago

i'm thinking they grossly overestimate the problem of cracking a 1024-bit prime... based on my dabbling in that area its certainly possible for a network of machines to do it, and with modern gpus and good number implementations on them, i don't think that days long, or even overnight, cracking is a stretch if you have a few spare machines lying around....

nkurz 10y ago
Are you possibly misinterpreting the terribly imprecise phrase "cracking a 1024-bit prime" as being the same as factoring a single number with two prime factors? I don't really understand what's involved with the actual process, but there was some discussion here earlier: https://news.ycombinator.com/item?id=10391925 https://news.ycombinator.com/item?id=10391925. Alternatively, if you do correctly understand what's being done, it would be be interesting to hear how you made your estimate. Based on other examples, I agree that it might not be impossible that the "usual approaches" could be sufficiently optimized on commodity hardware to get the 100x or 1000x gain you would need for this.
- jheriko 10y ago
  its the reverse modular exponentiation problem right? e.g. some a is transformed into b by x^a mod y = b where y is a prime and x has special properties relative to it? doing that once each, sharing the resulting b's then using the b from the other person raised to the power of your original input a to create a number that is kept secret (because a was kept secret) - so if you can get a back from b (x and y are not secret) then you can work out the derived secret number and its not so secret anymore its true that for large numbers this becomes harder, and there are many a's for a given b, but iirc the properties of modular arithmetic make them identical in effect, such that finding any a is good enough to crack the key exchange. ... is that right?

by jheriko 10y ago

nkurz 10y ago

Are you possibly misinterpreting the terribly imprecise phrase "cracking a 1024-bit prime" as being the same as factoring a single number with two prime factors? I don't really understand what's involved with the actual process, but there was some discussion here earlier: https://news.ycombinator.com/item?id=10391925 https://news.ycombinator.com/item?id=10391925. Alternatively, if you do correctly understand what's being done, it would be be interesting to hear how you made your estimate. Based on other examples, I agree that it might not be impossible that the "usual approaches" could be sufficiently optimized on commodity hardware to get the 100x or 1000x gain you would need for this.

jheriko 10y ago
its the reverse modular exponentiation problem right? e.g. some a is transformed into b by x^a mod y = b where y is a prime and x has special properties relative to it? doing that once each, sharing the resulting b's then using the b from the other person raised to the power of your original input a to create a number that is kept secret (because a was kept secret) - so if you can get a back from b (x and y are not secret) then you can work out the derived secret number and its not so secret anymore its true that for large numbers this becomes harder, and there are many a's for a given b, but iirc the properties of modular arithmetic make them identical in effect, such that finding any a is good enough to crack the key exchange. ... is that right?