Factors Found in 200-Digit RSA Challenge 184
diodesign writes "The two unique prime factors of a 200-digit number have been discovered by researchers at Bonn University (Germany) and the CWI (Netherlands). The number is the largest integer yet factored with a general purpose algorithm and was one of a series of such numbers issued as a challenge by security company RSA security in March 1991 in order to track the real-world difficulty of factoring such numbers, used in the public-key encryption algorithm RSA. RSA-200 beats the previous record number 11281+1 (176 digits, factored on May 2nd, 2005), and RSA-576 (174 digits, factored on December 3rd, 2003)."
Hooray! (Score:2, Interesting)
Seriously though... any idea when our databases will enable INTs this high with indexing and normalization? I'd like to see a kind of infinite rid length at some point, and while database character types like varchar in mysql goes to 255, maybe it's really enough? (ducks from incoming Bill Gates quotes)
Prime Numbers (Score:2, Interesting)
Prime Numbers [hopto.org]
Algorithmic difficulty (Score:3, Interesting)
If adding one bit to the number, makes the problem twice as hard, then the base of the exponent for the executive time is 2. But what if the base is not 2, but is only 1.01? Then, adding 200 bits to the number only makes the problem 7 times harder (1.01 ^ 200). The scary part is that we can't prove that factoring has a lower limit to the base of the exponent. It could be 1.1, 1.01, or 1.001, or 1.0001. This means that any crypto based on prime factors has an unknown vulnerability in it.
For now, prime factoring is hard, tomorrow, it might not be.
Re:55 CPU years (Score:3, Interesting)
Actually, if somebody succeeds in finding a way to factor large numbers efficiently, it could cause a lot of disruption. For example, much practical online security relies on the difficulty of factoring, and if that suddenly becomes broken the disruptions could be severe (at least temporarily).
If it continues to take years to factor numbers, we're still safe. If it gets down to hours, watch out!
Re:Waste of time! (Score:1, Interesting)
Certainly knowing how long it actually took to factor one specific example is nice, but that doesn't necessarilly tell us how long it will take to factor another--the algorithm might have "gotten lucky" and hit the right factors early in it's filtering, or might have gotten unlucky and hit it very late in it's scan of the problem space.
You need more than one data point here to make predictions of "how long it will take to factor an arbitrary number." Unfortunatly, given the pace, that's not feasible. But it's extremely dangerous to project from one datapoint that may or may not be "typical" (for some definition of typical).
To give an example--I take an algortihm that starts by trying primes of the form 2^n+1, then 3^n+1, etc. This will be fairly fast, but will not span the problem space (i.e. there is a decided possibility that my algortihm will never hit the number, because most primes cannot be represented by p^n+1.) However, if one of the factors of the semiprime "challenge" just happened to be 2^230+1, then I just "factored" this prime in minutes. The sky is falling! Keys are not safe!
Of course, using 2^230+1 would not be a good test case, and presumably RSA checked for this. My point here, however, is that every algorithm has some things it checks "first" and some things it checks "later". Sometimes you get lucky and your target it well suited to your algortihm, sometimes you don't.
You can work out a probability distribution of how long it takes to cover the whole problem space for a given algorithm, and you can use that to say "here's how long it will take on average" and "here's the maximum time it will take." These are useful numbers, which can be determined theoretically. You can also aproximate them empircally by taking some data points. But you need many data points.
To say "it took this trial 55 CPU-years" means little. To say "and that's how long it takes to factor a similar number" is like taking one draw at random from a normal distribution and assuming "that must be the mean." It's probably close, but it might not be, and it's certainly no guarantee.
In other words, I'm firmly in the camp of "a single empircal result is relatively meaningless."
Real Discovery! (Score:5, Interesting)
Find out where the subject lives that encrypted the data. (1-3 days)
Break into their home. (10 minutes)
Look under their keyboard (1 minute)
Read their private and public key off the notecard taped under the keyboard. (2 minutes.)
Optionally: Steal the notecard and leave a fake one with the wrong key written down.
Laugh maniacally... Done!!!
To date when doing security sweeps at my various clients sites, 80% of staff have their password somewhere in their cube. 50% had their PGP keys under the keyboard, 10% had pen drives marked "Passwords" handing off a thumb tack on their cube wall. Who cares about better encyption, physical security (or perhaps mental security is a better choice) is where we need to focus.
And remember network admins! Have you users spade or neutered