Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Factors Found in 200-Digit RSA Challenge

Zonk posted more than 9 years ago | from the really-big-numbers dept.

Security 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)."

cancel ×

184 comments

Sorry! There are no comments related to the filter you selected.

FIRST HORSE! (-1, Troll)

Anonymous Coward | more than 9 years ago | (#12492320)

I AM A HORSE!

fuckin a (0, Troll)

Dragoonkain (704719) | more than 9 years ago | (#12492323)

first post

omg fp! (-1, Troll)

Anonymous Coward | more than 9 years ago | (#12492324)

my willy is not kosher!

Hooray! (2, Interesting)

mfh (56) | more than 9 years ago | (#12492330)

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)

Re:Hooray! (1)

Veinor (871770) | more than 9 years ago | (#12492429)

Mathematica, a mathematics package, can handle 2,100,000,000+ bit numbers (I don't have the exact figure), but I don't think that that's the sort of thing you're looking for.

Re:Hooray! (1)

Silverlancer (786390) | more than 9 years ago | (#12492470)

Java's BigInteger class handles integers of any size--although its speed is nothing to be envied.

Re:Hooray! (0)

Anonymous Coward | more than 9 years ago | (#12492720)

That's not true. There is a definite limit to the size Java BigInteger can handle. Admittedly that size is pretty close to most other bignum packages.

Re:Hooray! (0)

Anonymous Coward | more than 9 years ago | (#12492721)

sounds like my girlfriend. she's "been around" as they say.

oh wait you said integers and not DIGITS.

Re:Hooray! (1)

Tim C (15259) | more than 9 years ago | (#12492532)

Oracle's VARCHAR2 type goes up to 4000 chars, while the LOB types (BLOB, CLOB and NCLOB) support up to about 4GB.

For what it's worth though, think about what you're asking. If you have an integer id that increases sequentially from 1, you can already have a huge number of entries in the table before you start running out of ids for them. For any non-trivial table, chances are you're going to run out of disk space long before you run out of ids.

Re:Hooray! (0)

Anonymous Coward | more than 9 years ago | (#12492645)

You'll run into a lot of problems if you make your index a LOB type. Tyring joining two primary key 4gb length fields across tables and report back.

What he was getting at was the keys ID are limited to 255 characters. You cant search lengths longer without using some kind of indexing service.

Re:Hooray! (0, Offtopic)

iMaple (769378) | more than 9 years ago | (#12492626)

Wow , someone had the guts to mod a 56 UID as a troll (of course the fact that the post does not seem to be in anyway a troll, so the moderator was brave and stupid). Serioulsy whats so wrong with the parent post to mark it as a troll? It does not seem absurd to wish for unbounded length ints (BigInteger?).

Prime Numbers (2, Interesting)

JaxWeb (715417) | more than 9 years ago | (#12492344)

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 [hopto.org]

Re:Prime Numbers (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#12492365)

No really anything to do with the above comment, but it is sort of off-topic, so I will bring it up.

I think Kellen Winslow is a prime idiot.

Re:Prime Numbers (0)

Anonymous Coward | more than 9 years ago | (#12492506)

What did he do? Oops. Did a Yahoo search. Motorcycle accident.

You're right. He is a prime idiot.

Re:Prime Numbers (2, Funny)

Thud457 (234763) | more than 9 years ago | (#12492580)

Not really anything to do with this specifically, but this story does have something to do with goatse, so I will bring it up.

Prime numbers for you [surfeu.fi]

Hmmm (3, Funny)

Anonymous Coward | more than 9 years ago | (#12492345)

Slashdot is a prime factor in how much time I waste day to day.

so? (-1, Troll)

Anonymous Coward | more than 9 years ago | (#12492347)

So does that mean it's solved?

Re:so? (-1, Troll)

Anonymous Coward | more than 9 years ago | (#12492370)

So does that mean it's solved?

Yep. They solved math.

Re:so? (3, Informative)

CodeBuster (516420) | more than 9 years ago | (#12492552)

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.

Re:so? (2, Funny)

yamla (136560) | more than 9 years ago | (#12492761)

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. :)

55 CPU years (4, Insightful)

Inkieminstrel (812132) | more than 9 years ago | (#12492368)

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.

Re:55 CPU years (4, Insightful)

0x461FAB0BD7D2 (812236) | more than 9 years ago | (#12492401)

Well, those teams could still pursue with their endeavors, hopefully beating the time used by these researchers.

This would mean that their algorithm and/or heuristics is/are superior, which would be beneficial to everyone, including these researchers who "won".

The good thing about research like this is that no one really loses.

Re:55 CPU years (2, Interesting)

14erCleaner (745600) | more than 9 years ago | (#12492855)

The good thing about research like this is that no one really loses.

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:55 CPU years (3, Funny)

merlin_jim (302773) | more than 9 years ago | (#12492416)

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.

Shutup. I hate you all.

Oh well guess it's time to start looking at RSA-768...

Re:55 CPU years (2, Funny)

stecoop (759508) | more than 9 years ago | (#12492451)

it took 55 CPU years to factor the number

That's not too bad. Look at how long the computer took to get the the question in Hitchhikers guide to the galaxy?

Re:55 CPU years (4, Informative)

TedCheshireAcad (311748) | more than 9 years ago | (#12493054)

Another victory for the General Number Field Sieve (I think). The article was a little light on the details, but it mentioned they used a "general algorithm", which I'm assuming is the GNFS. The original paper [acm.org] may shed some light on the algorithm, for the algebraically inclined Slashdotter. (Link courtesty of Google Scholar [google.com] )

I don't get it... (3, Funny)

neiffer (698776) | more than 9 years ago | (#12492394)

I tried to do it on my TI-85 and I keep getting an error!

Re:I don't get it... (2, Funny)

ArielMT (757715) | more than 9 years ago | (#12492477)

I tried to do it on my TI-85 and I keep getting an error!

Turn your calculator upside down on the step just before the error.

Re:I don't get it... (2, Funny)

SuperBigGulp (177180) | more than 9 years ago | (#12493028)

I have a laptop computer from Ohio Arts, but every time I turn it upside down the screen goes blank. I also wish it had a keyboard...it isn't easy trying to factor large numbers with just the two knobs.

Re:I don't get it... (0)

Anonymous Coward | more than 9 years ago | (#12493148)

Uh I hate to tell you this... you don't have an etch-a-sketch on your lap and... well.. lets just say you cranked the knobs too far :-/

Re:I don't get it... (1)

sam5550 (841429) | more than 9 years ago | (#12492766)

Try it on a TI-89. It will do it, in theory. TI themselves admit, however, that it may take longer than the life of the calculator, the user, and/or the planet to come up with the answer.

primer: get rich quick (-1, Offtopic)

ruxxell (819349) | more than 9 years ago | (#12492395)

Step 1: compute unique factors of 200 digit number
Step 2: ....
Step 3: PROFIT!

sorry, i'm a lamer.

--------------
"eight year olds, dude" - walter sobchak

Re:primer: get rich quick (0)

Anonymous Coward | more than 9 years ago | (#12492496)

yes, that isn't even funny

Did Michelle Deliop write this? (3, Funny)

winkydink (650484) | more than 9 years ago | (#12492404)

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!

Re:Did Michelle Deliop write this? (1)

Silverlancer (786390) | more than 9 years ago | (#12492427)

Well it is pretty easy to test--just multiply the two factors. Its a bit hard to fake factors.

Re:Did Michelle Deliop write this? (1)

Mazem (789015) | more than 9 years ago | (#12492759)

Thats the beauty of math. It doesn't matter who you are, or what sources you have. If you're right, you're right.

Re:Did Michelle Deliop write this? (0)

Anonymous Coward | more than 9 years ago | (#12492865)

Well it is pretty easy to test--just multiply the two factors. Its a bit hard to fake factors.

er...no. It's pretty easy to come up with 2 numbers that multiply to a 20 digit number. That's in no way difficult. I can take any 2 numbers like (small prime)^(some power) + 1 and in a few minutes come up with a 200 digit product.

The INTERESTING question isn't whether "hey, these 2 numbers multiply to form some other number." The INTERESTING question is whether they IN FACT did what is stated--STARTED with the 200 digit number and factored it. This is in no way proved by multiplying the numbers back together. It would be strongly indicated if in fact this is truly a test puzzle pozed by RSA, but I don't see any evidence of that.

The other interesting question (although probably an order of magnitude less interesting) is whether the 2 factors themselves are prime... Again, asserted but not proven.

Easty to test (1)

n1vux (452650) | more than 9 years ago | (#12493103)

Indeed, Factoring is in the class of problems that are seemingly hard to do (non-polynomial time on the best general algorithm known) but easy to check (polynomial time). The classic problems of this form are called NP-Hard [wolfram.com] , and many are NP-Complete [wolfram.com] . Factoring has not yet been proved NP-Hard or NP-Complete, but is assumed to be, and that is the basic assumption of RSA public-key cryptography. This result does not change that, it just encourages use to boost our key sizes if we hadn't lately.

And, using perl [perl.org] and Math::BigInt, I did [perl.org] , 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 [crypto-world.com] on FactorWorld [crypto-world.com] .

IAAAM,

Bill N1VUX
I Am An Apostate Mathematician
I prostitute my math degree sorting ones from zeroes

Re:Did Michelle Deliop write this? (0)

Anonymous Coward | more than 9 years ago | (#12492609)

That's old. Check it again.

Re:Did Michelle Deliop write this? (0, Troll)

TedCheshireAcad (311748) | more than 9 years ago | (#12493120)

In[1]:= 27997833911221327870829467638722601621070446786955 4285375600099293261284001076\ 09345671052955360856061822351910951365788637105954 4820065767750985805576135790\ 98734950144178863178946295187237869221823983 == 35324619344027701212726049781984643686711974001976 2502364930346877612125367942\ 3200058547956528088349 * 79258699544783330333470858414800596877379758573642 1996073433034145576787281815\ 2135381409304740185467

Out[1]= True

Mathematica agrees.

Waste of time! (4, Insightful)

Tom7 (102298) | more than 9 years ago | (#12492411)

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.

Re:Waste of time! (5, Insightful)

Anonymous Coward | more than 9 years ago | (#12492515)

If someone claims to have found a better factoring method, then it's easier for RSA to check that p,q < n and p*q = n, than to read his algorithm and analysis and award a prize based on that. (Imagine how many crackpots would apply with 100 pages long "proofs").

Re:Waste of time! (1, Insightful)

Anonymous Coward | more than 9 years ago | (#12492519)

Except that the majority of the factoring algorithms aren't just an algorithm. They change greatly with various parameters used to start, seed or otherwise define the algorithm.

Add to that little tricks such as using multiple algorithms for different parts of the solution area [because some algorithms work better under different conditions] and even the "paper" estimate becomes hazy.

That's ignoring the advances in computing processing, communication, and programming which have large practical effects on the actual implimentation.

Re:Waste of time! (4, Insightful)

Vellmont (569020) | more than 9 years ago | (#12492529)


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

You can certainly make a decent estimate of how long it will take, but you're never going to get a close approximation of the real-world performance of your implementation until you actually write the code and run it.

The other side is that theoretical calculations are nice, but there's nothing quite like actual verification. It's much easier for a programmer to justify using larger key lengths when someone has actually cracked smaller key lengths rather than using calculations based on estimates of computing power.

Re:Waste of time! (2, Insightful)

Tom7 (102298) | more than 9 years ago | (#12492914)

I said it's worthwhile to make good implementations. I think we should do this. Then, based on our understanding of the code's behavior (and probably some short-lived experiments), we can extrapolate to find the expected time to completion. This is also better for randomized algorithms that actually running it, since by running it we only get one point randomly sampled from the probability distribution. They clearly knew that the experiment would take approximately 1.5 years to run, otherwise they wouldn't run it.

What we should not do is, once we figure out how long something is going to take, to actually run it if the answer is totally pointless. This last step is a waste of time.

Re:Waste of time! (1)

Vellmont (569020) | more than 9 years ago | (#12493033)


What we should not do is, once we figure out how long something is going to take, to actually run it if the answer is totally pointless. This last step is a waste of time.

A waste of who's time? The computers time? The only used an opteron for the sieving. It's never stated how many computers were used for the rest of the cracking. Once you've written the code, it's not much harder to actually perform the experiment. Like I said, actual cracked keys are far easier to justify to a programmer than theoretical calculations. Actual cracked keys can be trusted 100%. Calculations of performance from unknown researches can be trusted much less than that.

Re:Waste of time! (0)

Anonymous Coward | more than 9 years ago | (#12492533)

Well, it made slashdot headlines, didn't it?
Therefore it definitelly was a computing-power-waste.

(just that computing-power-wasting RSA-640 comes along with 20,000 junky dollars)

ps: someone already did the 1..2..3: Profit! Now we're waiting the overlords thingy

Re:Waste of time! (1)

awolk (759539) | more than 9 years ago | (#12492556)

But if there are no real-world-implementations of the algorithms, what good are they?
Also, and more importantly, these challenges show just how good public-key cryptography is, and what is technically feasible to break.

Re:Waste of time! (1)

Tom7 (102298) | more than 9 years ago | (#12492941)

I guess I didn't make myself clear. (clarification post [slashdot.org] ) I whole-heartedly endorse the implementation of algorithms. But once we know it's going to take 1.5 years to run, we shouldn't bother actually running them for 1.5 years!

these challenges show just how good public-key cryptography is, and what is technically feasible to break.

We can know that by paper-and-pencil calculations, once we know how fast our implementation is. And we can know it 1.5 years sooner!

Re:Waste of time! (1, Interesting)

Anonymous Coward | more than 9 years ago | (#12493176)

The problem is that, to actually verify this, you need a heck of a lot more than one data point. What we really need to know is not how long it takes to factor one particular number, but rather how long we should expect it to take to factor an arbitrary semiprime of similar length.

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."

Infinite Improbability... (3, Funny)

wcitech (798381) | more than 9 years ago | (#12492434)

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.

Re:Infinite Improbability... (2, Funny)

Anonymous Coward | more than 9 years ago | (#12492504)

Oh no, not again.

Re:Infinite Improbability... (0)

Anonymous Coward | more than 9 years ago | (#12492917)

As I recall that was both the flowers and the whale!

Re:Infinite Improbability... (1)

Tedington (842076) | more than 9 years ago | (#12492554)

what they need to do is try to use those cpu years to simulate the math done on a waiter's check pad in an italian bistro.... Bistromath! there's gotta be enough room here for another hitchhiker's guide reference

Re:Infinite Improbability... (2, Funny)

Haydn Fenton (752330) | more than 9 years ago | (#12492835)

42.

...Meh, I felt left out.

Re:Infinite Improbability... (1)

Lord Kano (13027) | more than 9 years ago | (#12492599)

Better that than a hot bowl of grits and some whale sperm.

LK

yuk yuk (1)

psbrogna (611644) | more than 9 years ago | (#12492437)

Now that's what I call "long division."

Damn you GNU factor v2.0.11 (3, Funny)

GillBates0 (664202) | more than 9 years ago | (#12492460)

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.

Re:Damn you GNU factor v2.0.11 (0)

Anonymous Coward | more than 9 years ago | (#12492589)

"life, n: The whim of several billion cells to be you for a while."

Your sig: actually it's the collagen [rcsb.org] .

He must be sore! (-1, Troll)

Anonymous Coward | more than 9 years ago | (#12492461)

Where is the prime-number-shitting goatse man when you need him?

Algorithmic difficulty (3, Interesting)

G4from128k (686170) | more than 9 years ago | (#12492501)

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.

Re:Algorithmic difficulty (2, Funny)

ch-chuck (9622) | more than 9 years ago | (#12492612)

so there's still a chance that 'Sneakers' might come true?

Re:Algorithmic difficulty (-1)

Anonymous Coward | more than 9 years ago | (#12492887)

What a bunch of bullshit. While it is true no lower bound for factorization has been proven the thing you write about bases has nothing to do with this. If we used base 1.01 instead (in some obscure sense) we would have to add many more digits to represent the same number. For instance a number representable with 30 digits in base 10 would take roughly 90 digits in base 2 and so even more in base 1.01. But the base representation doesn't even matter because it just makes the number of digits different by a constant factor, but doesn't change the fact that we are still dealing with a problem apparently only solvable in exponential time meaning there is an "order of growth" gap between the cost of encrypting/decrypting and of breaking the encryption so we can just make the keys larger and the attacker will be disadvantaged much more than the legitimate user. Some day a polynomial time algorithm for factoring might be found, but that is a totally different story.

Re:Algorithmic difficulty (0)

Anonymous Coward | more than 9 years ago | (#12493012)

Perhaps the OP is referring to the base of the exponent not the base of representation. FactoringTime = O(B^n), where B is the base of the exponent and n is the number of digits? Maybe it would be clearer to say B is the order of growth and can be potentially small?

Re:Algorithmic difficulty (1)

iammaxus (683241) | more than 9 years ago | (#12492897)

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.
According to what you said, what you really mean is that it is possible that any crpto based on prime factorization has an unknown vulnerability. You can't say that for certain unless it is proven that there is no lower limit on the base exponent. (Again, I'm just using your post as a reference)

Re:Algorithmic difficulty (1)

Soul-Burn666 (574119) | more than 9 years ago | (#12492915)

Not to mention that the density of prime numbers reduces as you enlarge the numbers (iirc the number primes up to n is an order of log(n)).

Because of this, it is possible to reasonably factor numbers made of primes of up to 200-300 bits.

Re:Algorithmic difficulty (1)

DrFalkyn (102068) | more than 9 years ago | (#12492928)

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. The algorithms that exist must search the vast majority of the keyspace. Because we use a binary number system, that is why it is said that adding a single digit increases the running time by 2, because the keyspace has increased by a factor of two. The base has nothing to do with it.

Base and brute force (1)

G4from128k (686170) | more than 9 years ago | (#12493181)

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.

Factoring Alorithms (1)

bobbuck (675253) | more than 9 years ago | (#12493277)

Didn't someone publish an algorithm for factoring that ran on O(n^(1/4))?

Re:Algorithmic difficulty (1)

Woy (606550) | more than 9 years ago | (#12492961)

"For now, prime factoring is hard, tomorrow, it might not be."

It must be tomorrow here, because i can do prime factoring in a heartbeat.

Nice troll Mr. G4 (0)

RedLaggedTeut (216304) | more than 9 years ago | (#12493149)

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 (or .01), the difficulty of factoring is not changed by choosing a lower base. All your posts are saying to us is that the numbers get bigger quickly in comparision to the number of digits added if these digits are in a large base.

If 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.

Re:Algorithmic difficulty (1)

fourtyfive (862341) | more than 9 years ago | (#12493230)

Yep Those unkown vulnerabilities, they really make you vulnerable.

Re:Algorithmic difficulty (2, Informative)

SlashThat (859697) | more than 9 years ago | (#12493243)

At first glance, it looks like adding digits makes the factoring problem exponentially harder. The question is: what is the base of the exponent.
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))) ).
A naive analysis suggests that adding one binary digit makes the number twice as big and thus makes the factoring problem twice as hard.
Well ... no. No one ever claimed that, at least nobody familiar with the subject. It is easily seen not to be the case both from basic complexity analysis and experimental data. Again, the algorithm's complexity is not exponential.

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.

Notation? (3, Insightful)

man1ed (659888) | more than 9 years ago | (#12492520)

Does anyone know what the notation "11281+1" means?

Re:Notation? (5, Informative)

iMaple (769378) | more than 9 years ago | (#12492553)

Does anyone know what the notation "11281+1" means?

It means 11282 :) .
There seems to be a typo in the article post (A typo on slashdaot .. thats news ..I mean just one typo thats cool). Its probably due to some filter. It should say 11^281 +1

Re:Notation? (3, Insightful)

petermgreen (876956) | more than 9 years ago | (#12492803)

^ is kinda a dirty hack notation where you can't superscript

my guess is that someone copypasted it and in doing so lost the superscript (it should be noted that slashdot don't allow superscripting at least in comments)

Re:Notation? (1)

antispam_ben (591349) | more than 9 years ago | (#12492979)

^ is kinda a dirty hack notation where you can't superscript

What's so dirty about that use as the power operator is that it comes from the BASIC programming language. For straight ASCII use (no superscripts), one could instead use ** from FORTRAN, but that's less well known.

Re:Notation? (1)

jZnat (793348) | more than 9 years ago | (#12493143)

Aww, really? I thought it meant 1^1281 + 1. I was like "wtf 2 is a prime number, and that takes me all of no time to calculate."

Re:Notation? (0)

Anonymous Coward | more than 9 years ago | (#12492562)

It's 1337-speak, isn't it?

Re:Notation? (1)

avalys (221114) | more than 9 years ago | (#12492568)

I think it means [2^(11281)] + 1. But I could be wrong.

it's 11^281+1 (1, Informative)

Anonymous Coward | more than 9 years ago | (#12492577)

How fast could he do it? (1)

publicenemy23 (875823) | more than 9 years ago | (#12492669)

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.

Truly, the mind boggles.

http://www.guardian.co.uk/weekend/story/0,,1409903 ,00.html [guardian.co.uk]

Yeah yeah but the question is (0)

Anonymous Coward | more than 9 years ago | (#12492786)

what ARE the freaking factors! Let's see those mofos, if they are as big as claimed!

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?

Re:Yeah yeah but the question is (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#12492851)

GNAA declares victory over Wikipedia
GNAA declares victory over Wikipedia
Zeikfried - Associated Press, Nigeria

In a week which shall be recorded in Wikipedia infamy (and then vandalized and redirected to clitoris), the oft persecuted and never defeated internet missionaries of the Gay Nigger Association of America struck yet another powerful and telling blow against the powerful forces of bigotry and racism. Most notably, the growing zionist community on renowned internet pissing yard wikipedia.org.

And the records have indeed tumbled, with an unheard of third successful survival from the digital shitheap that is "Votes For Deletion". Coming in spite a heinous act of self promotion and cyber terrorism by Pat Gunn/Improv (formerly known as Aharon Meshenstein prior to his infiltration of the United States), who listed and inspired mob vandalism upon the GNAA's entry.

Fresh from his promotion of Wikipedia's $50,000 fundraiser for arms and supplies to the Jewish state of Israel, Improv launched a series of unprovoked and slanderous attacks against the well loved organisations leadership, all the while using foul and unholy necromancies to enlist the dead themselves to vote the entries deletion. Names such as "Wolfman" and "Demonslave" only adding to the damning list of evidence linking Mr Gunn to the occult.

Though Improv's actions gained him a small majority, a shock last minute intervention from Pope John Paul II spared the pages untimely fate, although as yet unconfirmed reports have indicated that several hundred 8-year old negro children were driven to the Basilica to secure the pontiffs support. Others point towards the black curse cast upon the deletion campaign by the support of infamous Brawl Hall mouthpiece "Yoyo" as the main driving force behind the salvation of the aforementioned entry.

But the details are likely to cause few sleepless nights among the group, only one of whom was willing to speak to the press. Namely GNAA Wikipedia contributor Popeye, who interrupted his drawing of pornography to give a brief dismissal the controversy: "Even with Improv's shady dealings, the sheer size and girth of a swollen GNAA phallus enables it both an identity and a vote of it's own. Making such discussion moot".
About Wikipedia:

Wikipedia, a content-free encyclopedia in many languages, started life in January 2001 and has already risen to the status of the internets premiere "trollpedia".

Currently Wikipedia contains 363950 articles, 10032 of which are genuine, and 343 of them factually accurate. Leaving Wikipedia on an academic par with "Star Wars: Incredible Cross-sections: The Ultimate Guide to Star Wars Vehicles and Spacecraft" and "My First Book of Animals from A to Z".

About GNAA:

GNAA (GAY NIGGER ASSOCIATION OF AMERICA) is the first organization which gathers GAY NIGGERS from all over America and abroad for one common goal - being GAY NIGGERS.

Are you GAY?
Are you a NIGGER?
Are you a GAY NIGGER?

If you answered "Yes" to all of the above questions, then GNAA (GAY NIGGER ASSOCIATION OF AMERICA) might be exactly what you've been looking for!
Join GNAA (GAY NIGGER ASSOCIATION OF AMERICA) today, and enjoy all the benefits of being a full-time GNAA member.
GNAA (GAY NIGGER ASSOCIATION OF AMERICA) is the fastest-growing GAY NIGGER community with THOUSANDS of members all over United States of America and the World! You, too, can be a part of GNAA if you join today!

Why not? It's quick and easy - only 3 simple steps!

* First, you have to obtain a copy of GAYNIGGERS FROM OUTER SPACE THE MOVIE and watch it. You can download the movie (~130mb) using BitTorrent.
* Second, you need to succeed in posting a GNAA First Post on slashdot.org, a popular "news for trolls" website.
* Third, you need to join the official GNAA irc channel #GNAA on irc.gnaa.us, and apply for membership.

Talk to one of the ops or any of the other members in the channel to sign up today! Upon submitting your application, you will be required to submit links to your successful First Post, and you will be tested on your knowledge of GAYNIGGERS FROM OUTER SPACE.

If you are having trouble locating #GNAA, the official GAY NIGGER ASSOCIATION OF AMERICA irc channel, you might be on a wrong irc network. The correct network is NiggerNET, and you can connect to irc.gnaa.us as our official server. Follow this link if you are using an irc client such as mIRC.

If you have mod points and would like to support GNAA, please moderate this post up.

"general purpose algorithm" (1)

bradtes (95841) | more than 9 years ago | (#12492793)

I guess using integer factoring algorithms are out of vogue, these days. I wonder how well A* works for factoring.

I don't want to spoil the ending but... (5, Funny)

fxer (84757) | more than 9 years ago | (#12492796)

...the punchline is

3,532,461,934,402,770,121,272,604,978,198,464,36 8, 671,197,400,197,625,023,649,303,468,776,121,253,67 9,423,200,058,547,956,528,088,349
and
7,925,869, 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

tip your waitresses! :)

Great! (1)

qualico (731143) | more than 9 years ago | (#12492818)

Now I can use that number in my encryption! ..oh wait...nevermind.

there are two kinds of people... (1)

museumpeace (735109) | more than 9 years ago | (#12492849)

trying to crack RSA challenges:
  1. those with a university's budget and hardware and what might be called an academic interest or mild economic incentive. I'd put hackers and organized criminals in the same category as far as budget and power available. This crowd took 14 years to crack a 200 digit public key
  2. NSA and its equivelents in UK, Russia, China [maybe Israel? they have some good academic papers on highly paralell factoring methods]. They had far greater incentive and in NSA's case, far greater resources for either assuring the security or compromizing the security of RSA PK encryption. Who thinks they would ever do a press release if/when they factored those numbers?

Re:there are two kinds of people... (3, Insightful)

MoonBuggy (611105) | more than 9 years ago | (#12493162)

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.

Re:there are two kinds of people... (0)

Anonymous Coward | more than 9 years ago | (#12493174)

You forgot to include Matt Damon from the "I'm a janitor who's smarter than you" movie...

like my post? yeah? well, how bout them apples?

If this was about hash collisions... (1)

SLi (132609) | more than 9 years ago | (#12492872)

... 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.

In other news, (0, Offtopic)

btnheazy03 (829328) | more than 9 years ago | (#12492905)

A little boy watches grass grow, while another witnesses the miracle of drying paint

Big Deal! (-1, Troll)

HtR (240250) | more than 9 years ago | (#12493069)

I found a much larger number with two unique prime factors!


The number is (2^25964951) - 1


I won't tell you what both the prime factors are, but I'll give you a hint. One of them is 1.

Re:Big Deal! (1)

TedCheshireAcad (311748) | more than 9 years ago | (#12493153)

1 is not a prime, by definition. It's a unit in Z.

Re:Big Deal! (0)

Anonymous Coward | more than 9 years ago | (#12493237)

1 is not a prime (it is a unit). I appreciate the joke though :-)

Down with redundant headlines! (1)

xoran99 (745620) | more than 9 years ago | (#12493089)

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 [wolfram.com] .

In case of slashdotting... (2, Funny)

yogikoudou (806237) | more than 9 years ago | (#12493165)

16724902205674189924062532405987195011865623417058 38624194898511161373322036901579077581447915314162 33316185029961764895435784096438741492052893824186 34748863167742006935642845385934215347033952015248 38654524737808769009507415120245236569375482318908 91385329016453944852396245829396869448643253850391 29578740098099812344478336633091322424294126185031 95461020639580382504322147046425469557460237023925 7895971944584397735802737492745740663377625087
*
82104108125618699159943474273932626169108985640 757 98951021784218025560708638069925020925778024695479 05272050811384276761464353909054596949815350050102 64956210420148237495378879950904352760577792675338 09861686957469628183969612393002458845980662329952 59055317675563525138596467389235562362539328216440 57629375394405108792128049027997042269298724715762 81087
=
1373183179085072360991803081221605453568 9394940861 38633503175744029333463691497599775891271039813222 14612889654832954480313026331709896998734478866409 54061088718900747013230437024175890977537753044820 53879770359035444483009771679041261850399620871563 78478085509013132834229050557857195775362761165394 23517161087058209537342711916284343153793315772921 62024405324144769213177009601102418333770104802547 55641100754450710285369145298735881756671882078360 07988274898451058766181802945933899453735285648998 09876712503991589156397622368672870575936511116980 08550381035807994231519795820733136650344169737431 49983896672114738280970668757459100857664291802835 77251132434367465749578720038003823381742689259826 62162998498498894364219764010709838706874215365180 45839289602229200747351519281915187163885361482956 9

Real Discovery! (4, Interesting)

kenp2002 (545495) | more than 9 years ago | (#12493264)

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 :)

In Other Words: A 664-bit Number Has Been Factored (0)

Anonymous Coward | more than 9 years ago | (#12493282)

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:

$ python -c 'import math;print math.log(10**200, 2)'
664.385618977

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).

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>