5 ms·

is that true? are there efficient factoring algorithms that scale better than linearly when given many products? i realise that just enumerating products woul

is that true? are there efficient factoring algorithms that scale better than linearly when given many products? i realise that just enumerating products would scale well, but is that how efficient factoring schemes work? or am i misunderstanding?

kzrdude 14y ago
It relies on there being common factors somewhere between any keys in a big set. That should only happen through a very small chance or through random-generation weaknesses. The point is that it's easy to spot it if there are keys with those weaknesses. This CCC talk is related to this: http://events.ccc.de/congress/2012/Fahrplan/events/5275.en.html http://events.ccc.de/congress/2012/Fahrplan/events/5275.en.h... Since ssh keys are user-submitted, we will have diversity and a chance of some subset of keys which weren't generated safely. EDITED TO ADD: Bad CCC site, it doesn't link to the FactHacks slides: http://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3.pdf http://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3....
- andrewcooke 14y ago
  oh thanks for the edit - also found this https://www.youtube.com/watch?v=IuSnY_O8DqQ https://www.youtube.com/watch?v=IuSnY_O8DqQ and am watching now. and the above tactic starts at 11m in. huh; and it's just euclid - a non-unity gcd means two keys (products) have a shared prime (and you get one of the primes). edit: also, "batch number field sieve" is the answer to my original question.