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.
Now that's what I call "long division."
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.
Here's the factorization
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.
I guess using integer factoring algorithms are out of vogue, these days. I wonder how well A* works for factoring.
...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!
Now I can use that number in my encryption! ..oh wait...nevermind.
SLASHDOT: news for people who can't concentrate on work or have no life at all and got tired of yelling back at the TV.
... people who miss the point would be saying "of course there are collisions in hashes". Well, now I'm going to say the obvious in the same tone.
Of course there are factors in a composite number. Nothing new to see here. Move along.
FWIW: ANY factorization of a number into two primes is unique, as any number is uniquely factored into primes.
For a second source, see Mathworld.
Karma: Bad (mostly due to all those "In Soviet Russia" jokes)
And, using perl and Math::BigInt, I did, and it checked out. Also useful is to verify that the number really was RSA200, as other anonymous Wiki-troll-edits were changing the number like a flickering flame.
And the source of the original Anon-Wiki edit was an email from the academic ring-leader, available on FactorRecords on FactorWorld.
IAAAM,
Bill N1VUX
I Am An Apostate Mathematician
I prostitute my math degree sorting ones from zeroes
1 is not a prime, by definition. It's a unit in Z.
The base is superflous. Factoring is approximately linear in the key size as a number, but said to be 'exponential' in the number of digits in the key.
Agreed. I was referring to the base of the exponent in the exponential formula for the factoring time. If the running time of the algorithm is t = A * B ^ N. A is a speed constant (decreasing with Moore's law). N is the number of bits in the number and B is the (perhaps misnamed) base of the exponent. For a brute-force algorithm, B = 2. For a better algorithm, B is less than 2. How much less than 2 is the issue.
The algorithms that exist must search the vast majority of the keyspace.
No, only brute force algorithms must search the vast majority of the keyspace. Can anyone prove that all possible algorithms have to do this? If, not, then factoring may be easier than we think or want.
The base has nothing to do with it.
Agreed, sorry for the confusion.
Two wrongs don't make a right, but three lefts do.
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? ]=-
Didn't someone publish an algorithm for factoring that ran on O(n^(1/4))?
you can get rich by solving famous mathematical problems:
http://www.claymath.org/millennium/
I'm sure there are other prices for cracking crypto-problems and/or factoring large integers.
This is an interesting analysis, but unfortunately completely wrong. The thing is that the Number Field Sieve algorithm's complexity is sub- exponential in number length. (To be precise, it's O(exp(c*log(n)^(1/3)*loglog(n)^(2/3)+o(1))) ).
Thanks for the info! What is the value of c? Does it have a lower bound? This is what I am talking about. All of these t = O(???) equations have constants in them that may be lower than people think.
That said, it doesn't seem that the factoring problem will become any easier, at least not before Quantum computers are built. The factoring problem is considered "the holy grail" of cryptography for 3 decades now, and there were hardly any advances in the last 15 years, despite the huge interest in the problem
True. But can future progress be extrapolated from past progress? I suspect that technical progress probably acts like a punctuated equilibrium system. A new advance creates massive innovation and progress that then hits some asymptotic limit until the next innovation hits.
Two wrongs don't make a right, but three lefts do.
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 c factor is 64/9, from the wikipedia link in the article.
a,e,i,o,u and sometimes w and y (at be if of up cwm by)
which allows a slightly larger prime to be factored
I believe Bill Gates once made this mistake too. Primes are trivially easy to factorise, it's composites that are hard.
I wonder how quickly the google cluster in the US could factor these numbers. Days, perhaps, if they used all of their computers?
I'm sure there are other prices for cracking crypto-problems and/or factoring large integers.
Yeah, they are called bank accounts, credit card numbers, military secrets...the list goes on.
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.
"The number is the largest integer yet factored with a general purpose algorithm[...]" The largest integer yet factored that we know about. I wouldn't be surprised if the NSA or other intelligence agencies have the ability to factor even larger numbers. BTW, I've developed a constant-time algorithm for factoring prime numbers of any magnitude. Let me know if you're interested.
Of course it is a waste of time. This is the exact goal of such a challenge. It is good PR for RSA if it takes long, they want to show the world their encryption can only be broken using LOTS of computer power. If someone finds a new FAST algorithm, obviously he will win the contest (in a spectacular time, because it is fast) and RSA will need to think of a better encryption.
Funny - I was confused reading his post too - he said "adding 1 bit" and then added "10"....
For a second there I felt pretty stupid...
Wait... Still... Feeling it....
09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0
But it's not really a very good reason to moderate his comments as "Troll" regardless of the content. Moderators should look at the contents of a comment when moderating, not at the poster's UID or whether or not he bought it off eBay. :-)
The point of the mod system is to highlight comments that are worth reading, not to be a tool for those who hold grudges against specific people.
I'd like to claim a new record. This number only had 200 digits. I've just factored a number with 2000 digits. The number is 10^2000. I'll leave the factorisation as an exercise.
In August 2002, Agrawal et al. discovered a deterministic algorithm (AKS ) for determining if a number is prime that runs in polynomial time (large polynomial though).
This means that prime testing is not NP-Hard or NP-Complete as many thought (not proved though!) it was. The same can happen to factorization. There is no guarantee that one day some smart guy will come up with a revolutionary idea that would lead many cryptosystems into oblivion. Who knows?
If you don't fail at least 90 percent of the time, you're not aiming high enough. (Alan Kay)
I've just factored a number with 2000 digits. The number is 10^2000.
That number has 2001 digits.
</pedant>
That would be 2001 digits (even more pedantically)
Tubby or not tubby. Fat is the question
You don't do stuff like this for the money!! 55 CPU years probably costs $20k in the first place. (Unless they leased out a zombie-net or something.)
-a
Prime Factorization = The factorization of a number into its constituent primes, also called prime decomposition.
Factoring ~= Factorization
Can you really do prime factoring in a heartbeat then?
If you don't fail at least 90 percent of the time, you're not aiming high enough. (Alan Kay)
Why do I first think of the "Centrum voor Werk en Inkomen" (Centre for Work and Income) and only later of the "Centrum voor Wiskunde en Informatica" (Centre for Mathematics and Information Technology) :-(
I'd prefer a more useful unit of measurement. How long is it in bits?
hawk
Now if hackers took over SETI, the last 24 hour progress was 795.926 years CPU time.
Total CPU time on SETI@home - 2,286,333 years.
Leave the house before the owner returns!
To Slashdot or not to Slashdot. That is the question (that will cause me to fail an interview)