Slashdot Mirror
Factors Found in 200-Digit RSA Challenge
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)."
Now the longest /. UID in history can be created!
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)
The dangers of knowledge trigger emotional distress in human beings.
Not really anything to do with this specifically, but this story does have something to do with primes so I will bring it up. I wrote something about prime numbers which might interest a few Slashdot readers.
Prime Numbers
- Jax
Slashdot is a prime factor in how much time I waste day to day.
The article says it took 55 CPU years to factor the number, though they did it in parallel for about a year and a half. I'd hate to imagine the teams that we don't hear about who are, say, 30 CPU years into the problem who just found out it's already been done.
I tried to do it on my TI-85 and I keep getting an error!
May 9, 2005 The two unique prime factors of a 200 digit number have been discovered by researchers at Bonn University.
Note: we need a source on this. All we have now is an anonymous edit on Wikipedia from someone at Cal State Fullerton.
An anonymous edit in Wikipedia. Now there's a source for you!
"I'd rather be a lightning rod than a seismometer." -Ken Kesey
I think these RSA challenges are a waste of computer power. It's trivial to compute how much computing resources it will take to factor numbers using an existing algorithm on paper, and you get a more accurate estimate than you get from sampling experimentally. I'm all for the development of new, faster algorithms and implementations, but the challenge should be for the development and demonstration of these algorithms, not the brute-force months-on-end search that ensues.
The air force has a practical use for this discovery, because when these numbers are fed into an infinite improbability drive, oncoming surface to air missles will be changed into a sperm whale and a harmless bowl of petunias.
My plans for world domination have been foiled.
$ factor --version
factor (GNU sh-utils) 2.0.11
$ factor 10000000000000000000
10000000000000000000: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
$ factor 100000000000000000000
factor: `100000000000000000000' is not a valid positive integer
Try `factor --help' for more information.
On a positive note, I was short only by 179 digits.
An Indian-American Hindu committed to non-violent thought/speech/action alarmed by the global explosion of radical Islam
Factoring numbers looks harder than it is. At first glance, it looks like adding digits makes the factoring problem exponentially harder. The question is: what is the base of the exponent. A naive analysis suggests that adding one binary digit makes the number twice as big and thus makes the factoring problem twice as hard. Such analyses are where get estimates that proclaim it will take a computer the life of the universe to factor an X-digit number.
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.
Two wrongs don't make a right, but three lefts do.
Does anyone know what the notation "11281+1" means?
It means that an incrementally more efficient algorithm has been discovered which allows a slightly larger prime to be factored in a reasonable amount of time. However, this does not represent the sort of breakthrough algorithm that blows the problem wide open and allows factoring of arbitrarily large primes in time polynomial to the size of the input (the length of the prime number to be factored in this case). Thus, this new algorithm does not scale elegantly as one increases the size of the inputs and therefore it does not represent the general solution to the prime number factorization problem. Your public key crypto systems are safe if the prime numbers are large enough...for now.
I can factor primes of any size in constant time. It does not matter how large they are. Let us take a prime number, we'll call it p. What are the factors? The factors are exactly 1 and p. There are no other integer factors of prime number p. :)
Oceania has always been at war with Eastasia.
...the punchline is
6 8, 671,197,400,197,625,023,649,303,468,776,121,253,67 9,423,200,058,547,956,528,088,349, 954,478,333,033,347,085,841,480,059,687, 737,975,857,364,219,960,734,330,341,455,767,872,81 8,152,135,381,409,304,740,185,467
:)
3,532,461,934,402,770,121,272,604,978,198,464,3
and
7,925,869
tip your waitresses!
Well the fact that the researchers from number 1 stated that the factorising took 55 CPU years (based on a 2.2GHz Opteron) pretty much sorts things out for the others. We can realistically assume that anyone with a few-million-$ reason could devote 100+ CPUs to this so basically you have to hope that your data will be outdated in 6 months or so.
Alternatively if you take advantage of Sun's rent-a-cluster for $1/CPU hour you'd get change from $500,000 and get your results faster too, but then you have to pay again for the next problem that needs cracking, so it's probably more economical to purchase a smaller cluster.
I have found a way to crack any code in a matter of minutes. It's simple!!! It works plenty of times!!
:)
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
-=[ Who Is John Galt? ]=-
Btw: Not 11^281+1 itself (which has obviously >281 decimal digits) was the previous world record, but a 176-digit factor of 11^281+1 called "c176":
/graf0z.The time to do it once may or may not be meaningful. Do it six more times and average the results.
Some mornings it's hardly worth chewing through the restraints to get out of bed.