They didn't describe the technique, but the fact that the paper has the keyword "Euclidean algorithm" makes it pretty obvious--they just gathered a list of public keys, took the gcd of all the pairs, and whenever they found a gcd not equal to one, they'd cracked both keys out of that particular pair. See my earlier comment.
Not really - it does make a difference between amateur attackers and professional, but the potential value is high enough that there will probably be plenty of well funded attackers.
