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
yes, that isn't even funny
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 wonder how fast Daniel Tammet could factor this number. It's amazing that this man could be able to factor an RSA200 number in milliseconds while it takes combined computing power 50 years to do.
3 ,00.html
Truly, the mind boggles.
http://www.guardian.co.uk/weekend/story/0,,140990
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.
Oh, gee, I guess I could of like RTFA'd or something. But I'm not new here so I don't have to.
ps. Do the factors run Linux? Or can you at least imagine a Be-yo-w0lf of them?
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
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).
Adding a bit always means base 2. Perhaps you meant to say "adding a digit"? Now apart from the basic prooblem that there is no such digit representing 1.01 (orIf anything, in fact factoring would get easier in a larger base, at least this would the complexity of the algorithm somewhere else, e.g. into hardware.
A least you proved that one doesn't need a computer program as a generator(slashdot reported) to generate bu77sh1t.I'm still trying to figure out what people mean by 'social skills' here.
1 is not a prime, by definition. It's a unit in Z.
16724902205674189924062532405987195011865623417058 38624194898511161373322036901579077581447915314162 33316185029961764895435784096438741492052893824186 34748863167742006935642845385934215347033952015248 38654524737808769009507415120245236569375482318908 91385329016453944852396245829396869448643253850391 29578740098099812344478336633091322424294126185031 95461020639580382504322147046425469557460237023925 78959719445843977358027374927457406633776250870 757 98951021784218025560708638069925020925778024695479 05272050811384276761464353909054596949815350050102 64956210420148237495378879950904352760577792675338 09861686957469628183969612393002458845980662329952 59055317675563525138596467389235562362539328216440 57629375394405108792128049027997042269298724715762 810878 9394940861 38633503175744029333463691497599775891271039813222 14612889654832954480313026331709896998734478866409 54061088718900747013230437024175890977537753044820 53879770359035444483009771679041261850399620871563 78478085509013132834229050557857195775362761165394 23517161087058209537342711916284343153793315772921 62024405324144769213177009601102418333770104802547 55641100754450710285369145298735881756671882078360 07988274898451058766181802945933899453735285648998 09876712503991589156397622368672870575936511116980 08550381035807994231519795820733136650344169737431 49983896672114738280970668757459100857664291802835 77251132434367465749578720038003823381742689259826 62162998498498894364219764010709838706874215365180 45839289602229200747351519281915187163885361482956 9
*
8210410812561869915994347427393262616910898564
=
137318317908507236099180308122160545356
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.
1 is not a prime (it is a unit). I appreciate the joke though :-)
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))?
WHY THE HELL does the article mention the size of this number in digits ? Why don't they give us the size in bits ? This would have allowed a much easier comparison with the size of RSA keys (512 bits, 1024 bits, etc). To me it sounds like if a research group announced the invention of a new optical fiber supporting a throughput of N Library of Congress per second, without giving the actual value in Gigabit per second !
So, for the (apparently) little number of scientists out there, a 200 decimal digits number is equivalent to a 664-bit number:
In other words, the factorization of this RSA-200 number is equivalent to having broken a 664-bits RSA key. So 512-bit RSA keys are definitely at risk, they should be extended to 1024 bits (or more).
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.This goes to show that Kleinjung, et al are more interested in the science than the money. Either that or this says something about the worthlessness of the US dollar :) They could have won $20,000 USD if they had chosen to factor the smaller RSA-640 (193 decimal digits) number.
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.
why is this important at all? seriously.
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.
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.
Except that according to the french Mathametician Peniot (sp) ANY set is finite with respect to whole intergers. Now with that in mind anyone know if the work done by the indians and Peniot theorum have any impact on how hard (easy?) it is determine a RSA key of x digits?
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)
don't be so stupid, the point of this was to show that it was factored by prime numbers. read
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?
Surprisingly, it happens that the number also has 2000 digits.
hawk
Got a calulator handy? Just divide by the log (base 10) of two.
Wanna do it in your head? Just multiply by about 3.3. I get 660ish.
(Slap the monkey.)
If you estimate $5/ month in power bill just for the computers to be kept running, then 55 CPU-years = 660 months = $3,300 right there. The computers can maybe be had for free around a business or university, but you still have to add the rent cost for warehousing/ ventilating the cluster.
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)