## Factors Found in 200-Digit RSA Challenge 184

Posted
by
Zonk

from the really-big-numbers dept.

from the really-big-numbers dept.

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)

## Re:Hooray! (Score:1)

## Re:Hooray! (Score:2)

## Re:Hooray! (Score:2)

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! (Score:2)

It's all find and dandy that you have a way to store it, but you really don't have much way to work with it do you?

## Re:Hooray! (Score:2)

## Re:Hooray! (Score:2)

## Re:Hooray! (Score:2)

## Yes, most people know by now... (Score:2)

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.

## Prime Numbers (Score:2, Interesting)

Prime Numbers [hopto.org]

## Re:Prime Numbers (Score:2, Funny)

Prime numbers for you [surfeu.fi]

## Re:Prime Numbers (Score:2)

A few corrections as I read through. Your definition of divisibility lacks rigor and needlessly invokes the division algorithm. Try instead: let a,b be integers, then b divides a if there exists an integer c such that a=bc. T

## Re:Prime Numbers (Score:2)

I wrote this for people who don't know mathematics, so I do not feel I should go into more complicated topics. The sieve of Erathosthenes would be do-able, but I don't really think there is much of interest to prove in it. Mersenne and Fermat numbers both get a bit complicated when they get interesting, so I will not include those either. They are interesting topics though, I agree.

I don't think I could explain the proof of the Prime Number Theorem, and I do not have enoug

## Re:Prime Numbers (Score:2)

Anyway, I've credited you as pilkul on my maths page, http://jax.hopto.org/maths/ [hopto.org]. Is that what you would like to be known as?

Thank you again for taking the time to read this.

## Re:Prime Numbers (Score:2)

One interesting and easy-to-prove thing to say about Mersenne and Fermat numbers is the following: let a,b be integers greater than 1, then a^b-1 is composite if it is not a Mersenne number, and a^b+1 is composite if it is not a Ferm

## Re:Prime Numbers (Score:2)

## Re:Prime Numbers (Score:2)

I'm not too bothered about Transfinite Set Theory being a bit removed from things. I understand the opinion though. Anything which could change my life away from Computer S

## Re:Prime Numbers (Score:2)

(The theorem which got me was the proof that for any set A, the powerset, P(A), has more elements, even for infinite sets A)Yeah, that's what exactly what I was talking about (that's the "diagonalization argument" I mentioned).

When you have done your major, do you think you will keep with mathematics or do something else? (Like computer science, etc)Nah, I think I'm not cut out for doing maths in grad school. Even though I may have the raw intelligence (maybe) I don't have the monomanical passion

## Hmmm (Score:3, Funny)

## 55 CPU years (Score:4, Insightful)

## Re:55 CPU years (Score:5, Insightful)

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 (Score:3, Interesting)

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!

## Could google do it? (Score:2)

## Re:55 CPU years (Score:4, Funny)

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 (Score:2, Funny)

it took 55 CPU years to factor the numberThat'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 (Score:1)

## Re:55 CPU years (Score:4, Informative)

## Re:55 CPU years (Score:2)

## I don't get it... (Score:4, Funny)

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

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... (Score:2, Funny)

## Re:I don't get it... (Score:2)

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

## Did Michelle Deliop write this? (Score:4, Funny)

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? (Score:2)

## Re:Did Michelle Deliop write this? (Score:2)

## Easty to test (Score:1)

And, using per [perl.org]

## Re:Did Michelle Deliop write this? (Score:2)

## Those unique factors . . . (Score:2)

hawk

## Waste of time! (Score:5, Insightful)

## Re:Waste of time! (Score:5, Insightful)

## Re:Waste of time! (Score:1, Insightful)

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 t

## Re:Waste of time! (Score:5, Insightful)

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! (Score:3, Insightful)

## Re:Waste of time! (Score:2)

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 theo

## Re:Waste of time! (Score:3, Insightful)

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.I strongly disagree. A theoretical analysis is better because you can prove that

## Re:Waste of time! (Score:1)

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! (Score:2)

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!

## Waste of time intentional (Score:2)

## Re:Waste of time! (Score:2, Funny)

## Infinite Improbability... (Score:3, Funny)

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

## Re:Infinite Improbability... (Score:2, Informative)

## Re:Infinite Improbability... (Score:1)

## Re:Infinite Improbability... (Score:3, Funny)

...Meh, I felt left out.

## Re:Infinite Improbability... (Score:1)

LK

## yuk yuk (Score:1)

## Damn you GNU factor v2.0.11 (Score:4, Funny)

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.

## 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:Algorithmic difficulty (Score:2, Funny)

## Re:Algorithmic difficulty (Score:2)

According to what you said, what you really mean is that it is

possiblethat 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 p## Re:Algorithmic difficulty (Score:2)

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

## Re:Algorithmic difficulty (Score:1)

## Base and brute force (Score:2)

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

## Re:Algorithmic difficulty (Score:1)

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

## Nice troll Mr. G4 (Score:1)

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

## Re:Nice troll Mr. G4 (Score:2)

For a second there I felt pretty stupid...

Wait... Still... Feeling it....

## Re:Algorithmic difficulty (Score:2, Informative)

This is an interesting analysis, but unfortunately completely wrong. The thing is that the Number Field Sieve algorithm's complexity isexponential in number length. (To be precise, it's O(exp(c*log(n)^(1/3)*loglog(n)^(2/3)+o(1))) ).

sub-## Re: Number Field Sieve (Score:2)

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 becom## Re:Algorithmic difficulty (Score:2)

## Notation? (Score:3, Insightful)

## Re:Notation? (Score:5, Informative)

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

11^281 +1## Re:Notation? (Score:3, Insightful)

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? (Score:2)

^ is kinda a dirty hack notation where you can't superscriptWhat'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? (Score:2)

## Re:Notation? (Score:1)

## Re:Notation? (Score:2)

## Re:Notation? (Score:2)

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

## "general purpose algorithm" (Score:1)

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

3,532,461,934,402,770,121,272,604,978,198,464,3

and

7,925,869

tip your waitresses!

## Great! (Score:2)

## there are two kinds of people... (Score:2)

## Re:there are two kinds of people... (Score:4, Insightful)

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.

## If this was about hash collisions... (Score:2)

Of course there are factors in a composite number. Nothing new to see here. Move along.

## Down with redundant headlines! (Score:1)

For a second source, see Mathworld [wolfram.com].

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

## Re:Real Discovery! (Score:2)

The Music of the PrimesRivest (the 'R' in RSA) threw away the prime numbers in one of the RSA challenges.## Verify yourself! (Score:4, Informative)

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.## Repeatability (Score:3)

## 200 digits? (Score:2)

## Re:200 digits? (Score:2)

RSA-200 is 663 bits long. It's interesting to contrast it with RSA-640 (640 bits long). RSA-640 is shorter, so should be easier to factor. And unlike RSA-200, RSA-640 carries a cash prize of US$20,000 for its factorisation. So, a puzzling question is why did the team take on RSA-200 rather than RSA-640?

## Re:200 digits? (Score:2)

Oh, interesting -- how come? The difficulty in working out the share of everyone involved in the effort?

## Re:so? (Score:4, Informative)

## Re:so? (Score:3, Funny)

anysize 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.## Re:primer: get rich quick (Score:2)

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.

## Re:largest integer yet factored? (Score:2)

BTW, I've developed a constant-time algorithm for factoring prime numbers of any magnitude. Let me know if you're interested.I'm interested in this constant-time factorization algorithm. Tell me more. :)He's playing with you. Given a prime number, x, of any magnitude, the factors are 1 and x. People like to say "factor prime numbers" when they really mean "factor products of primes".

Seriously, though. If you come up with a constant time algorithm for factoring products of primes, watch out. I never s

## Re:largest integer yet factored? (Score:2)

OK, Mr. Skeptic, here's the algorithm:Did you read my post?

## Re:largest integer yet factored (a pedant writes.. (Score:2)

I've just factored a number with 2000 digits. The number is 10^2000.That number has 2001 digits.

</pedant>

## Re:Interesting that they chose not to crack RSA-64 (Score:2)

-a