Please create an account to participate in the Slashdot moderation system

typodupeerror

## Factorization of a 768-Bit RSA Modulus192

dtmos writes "The 768-bit, 232-digit number RSA-768 has been factored. 'The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus. This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one. Because the first factorization of a 512-bit RSA modulus was reported only a decade ago it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours . . . . Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.'"
This discussion has been archived. No new comments can be posted.

## Factorization of a 768-Bit RSA Modulus

• #### Can someone explain this to me? (Score:3, Interesting)

on Thursday January 07, 2010 @12:37PM (#30684814) Journal

So I just did a Wikipedia Crash course on RSA (I knew it was for public/private key encryption) and how it all works mathematically.

But I still don't know what they mean by Factorization, or what that exactly means.

I'm guessing they found all and compiled and tested the possible values and now have a nice big chart? Is 768-bit RSA now considered "broken"?

• #### Re:Can someone explain this to me? (Score:5, Informative)

on Thursday January 07, 2010 @12:47PM (#30684970)
It's been a while since I studied this so take this with a grain of salt. I believe RSA involves 2 random large primes, 'p' and 'q' which are multiplied together to form a bigger number, 'n'. There is a bunch of other math to generate two more values 'd' and 'e' from 'p' and 'q'. The public key is 'n' and 'e', the private key is 'n' and 'd'. The math works that you can't get 'd' from 'e'. Factorization means just that, finding the factors of a number. In this case you're given 'n' which you know has only 2 factors ('p' and 'q' are both prime) so if you can factor 'n' and get 'p' and 'q' you can recalculate 'd' yourself and you now have the private key.
• #### Re: (Score:2)

For someone who hasn't studied in a while, you seem to have a good grasp. To me, this seems to make sense now given the info you have provided. :)
• #### Re:Can someone explain this to me? (Score:5, Informative)

on Thursday January 07, 2010 @01:19PM (#30685422)
Just to be accurate, I do not believe that in RSA you pick two primes but instead pick two values that are at least psuedoprime. Testing large numbers for primality is time consuming, but quick tests can eliminate nearly all composite numbers. The set of numbers that pass these quick tests but are not prime are called psuedoprimes, and are still usually pretty hard to factor.
• #### Re:Can someone explain this to me? (Score:5, Informative)

<shawn-ds@willden.org> on Thursday January 07, 2010 @02:30PM (#30686290) Homepage Journal

Testing large numbers for primality is time consuming, but quick tests can eliminate nearly all composite numbers.

More precisely probabilistic primality testing can be used to ensure that a number is not composite to any required degree of certainty. For example, with the Miller-Rabin test, each time you run the test you have a 3/4 chance of discovering that the number is not prime (assuming it's not). So, you run the test enough time to achieve the degree of certainty you desire. If you run it 100 times and each time the result is "prime", then there is only a 1 in 10^-13 chance that it is composite. Given that level of assurance, it's very reasonable to simply say "it's prime".

If it's not prime then the key will be significantly easier to break, but we just ensure that the odds of that are negligible and go about our business.

• #### Re:Can someone explain this to me? (Score:5, Informative)

<delirium-slashdot&hackish,org> on Thursday January 07, 2010 @02:49PM (#30686536)

Some software, such as GPG, uses primality tests that don't actually converge to arbitrary certainty regardless of the number of iterations, because certain rare types of non-primes known as "pseudoprimes", which satisfy tests that usually only prime numbers satisfy, will pass all iterations. For example, GPG uses the Fermat primality test [wikipedia.org], which will always pass Carmichael numbers [wikipedia.org]. Since Carmichael numbers are extremely rare, though, it doesn't make a whole lot of practical difference.

(The Miller-Rabin test that you mention doesn't have any such category of pseudoprime.)

• #### Re: (Score:2, Informative)

At university, we used to call them 'industrial grade primes'.

No real point to this post, just a memory from 1987.
• #### Re: (Score:2)

Don't worry, I'm puzzled by this too. My profs in school taught us that RSA can't be broken unless you know how to solve discrete logarithms so I am unsure what factoring has to do with it? Although I suppose if I know all the factors of a certain number, I could try to test all possible relatively prime inverses...
• #### Re: (Score:2)

RSA uses semiprimes - numbers with only two prime factors. If you know the factors p and q, you can derive the private key from the public key through multiplication mod (p-1)(q-1). There are much faster ways to factorize numbers than brute force - the best is the general number field sieve. It is Diffie-Hellman which uses discrete logs. There are better attacks against discrete logs than brute force, too. Once we have sufficiently powerful quantum computers, both the factorization problem and the discre
• #### Re: (Score:2)

I think it means you can find the private key for a given public key.

• #### Re:Can someone explain this to me? (Score:5, Informative)

on Thursday January 07, 2010 @12:52PM (#30685030) Homepage

What they did was factor a 768-bit number, like one that could be used as a 768-bit RSA public key. e.g. to factor 15, you need to find that it is equal to 3*5, which can be easily done by dividing the first few primes and finding that 3 divides 15. To factor a very large number, like a 768-bit number that is semiprime with the two factors both about the same size, (as is the case with RSA public keys) is a very difficult task. It is currently best done by the General Number Field Sieve (GNFS). For more info on any of these concepts, use Wikipedia.
This demonstrates the possibility of breaking any given 768-bit RSA key by factoring the public modulus, and shows how much work that takes. Note, however, that it is still very difficult, and in this case took multiple years of calendar time and hundreds of years of CPU time to crack.
This does not mean that every 768-bit RSA key can be cracked any more easily than it could before, it just demonstrates that we have the ability to crack any 768-bit RSA key (given the time and resources).

• #### Re: (Score:3, Insightful)

Like say, a botnet.

Let’s calculate this:
So taking you \$defaultCPU, whatever that is, a botnet of hundrets of thousands of systems, with (for simplicity let’s say) 1 core, you could crack a 768-bit RSA in... roughly guessed... ...a third of a day. (hundrets of years * 365 / hundrets of thousands of sytems)

I need a botnet! ^^
By the way: It is possible to infect a botnet by infecting the botnet client itself? Should be doable, right?
Or do those clients have some extreme self-protection form being c

• #### Re: (Score:3, Informative)

you could crack a 768-bit RSA in... roughly guessed... ...a third of a day.

Sorry, no. That doesn't take into account the fact that some parts can't be run in parallel on many home computers. Not to mention that the longest part, sieving, for a number this size, needs about 1 GB of RAM free, which I'd think people would be likely to notice and shut down pretty quickly...
Sieving is the step that takes the most time, in this case 1500 CPU years ("On a single core 2.2 GHz AMD Opteron processor with 2 GB RAM per core, sieving would have taken about fifteen hundred years."), but can e

• #### Re: (Score:2)

The very short version of it is that a private key is a set of two very large prime numbers. The public key is these two prime numbers multiplied together. If you have the public key, and are able to factor it, you can determine the private key.

The security of RSA relies on the assumption that integer factorization is hard. So far that assumption, at least publically, has not been shown false (unless you have a quantum computer).

• #### Re: (Score:2)

No, 768-bit RSA is not broken. they just found the factors for a single number. It only took them 2.5 years, and over 5 terabytes of data too. I don't consider this making 768-bit RSA "broken" any more than 56bit DES is "broken", because they didn't find a way to solve it faster than brute force. The point is that it is now possible to solve this kind of problem. And if they can do it in 2.5 years with 3 supercomputers, a dedicated adversary could probably do it in a few months with a couple dozen.

Factoriza

• #### Re:Can someone explain this to me? (Score:4, Interesting)

<sirlewk&gmail,com> on Thursday January 07, 2010 @01:24PM (#30685496)

That is like saying RSA-16 (if such a thing existed) is not broken because the fasted way of cracking it is factorization. Brute force is a legitimate form of cryptoanalysis, particularly when it is computationally feasible. Calling an encryption scheme "broken" when an attack such as this is demonstrated is quite reasonable, no matter how inelegant you may find the attack.

Suggesting that DES is not broken is very silly because "not being broken" implies on some level that it is still acceptable to use.

• #### Re:Can someone explain this to me? (Score:4, Insightful)

<shawn-ds@willden.org> on Thursday January 07, 2010 @02:40PM (#30686406) Homepage Journal

That is like saying RSA-16 (if such a thing existed) is not broken because the fasted way of cracking it is factorization. Brute force is a legitimate form of cryptoanalysis, particularly when it is computationally feasible. Calling an encryption scheme "broken" when an attack such as this is demonstrated is quite reasonable, no matter how inelegant you may find the attack.

Suggesting that DES is not broken is very silly because "not being broken" implies on some level that it is still acceptable to use.

Not at all.

You're assuming there is only a single definition of "broken", which is absolutely not the case in cryptography. The definition you're using is what cryptographers would call a "practical break" and it is almost orthogonal to the definitions that cryptographers normally use. Many cryptographic breaks are not practical, for example, but they're still considered perfectly valid breaks. On the other hand many unbroken ciphers exist which are worthless in practical terms, such as RSA-16.

DES falls somewhere in between. It's not worthless in practical terms, since the effort required to break it is high enough for some purposes, but it has relatively little security value in general. However, the fact that DES is not cryptographically broken does have significant meaning -- because it enables us to have confidence that 3DES is secure. I mention this to make the point that cryptographers' definitions of "broken" (there are many) do have practical implications.

• #### Re: (Score:2)

I did not mean to imply that there is only a single valid definition of break in cryptography. It is general knowledge that not all cryptographic attacks are practical. However, that does not mean that practical breaks cannot also be cryptographic breaks.

As you indicated, there are many kinds of cryptographic attacks. Some of them are practical, others are not. Some of them only apply to ciphers when they are used in certain modes. Others only work if an often unreasonable amount of information is alre

• #### Re: (Score:2)

In short, there is an RSA break, as we have always known, but it is only practical for small keys. The definition of "small keys" has just been updated.

Agreed, with one small caveat regarding terminology.

In cryptographic circles, brute force (which factorization is, for RSA) is not considered a "break" of the algorithm. So it would be correct to say that RSA-768 has been shown to be weak, but if you say it's broken people will tend to think you mean some weakness other than practicality of brute force.

That nit aside, your characterization that we've just had the definition of "small keys" updated is spot on.

• #### Re: (Score:2)

This team cracked ONE key and it took them 3 supercomputers and 2.5yrs.

Factorization was possible before it was every actually done. Factorization of 1024bit keys is already possible even though it has not yet been.

768bit RSA is no more or less safe to use than it was yesterday. Considering the efforts it took to crack, I'd say 768bit RSA with key expiration of less than 2.5yrs is EXTREMELY safe to use.

• #### Re: (Score:2)

And Caesar Ciphers are EXTREMELY secure against elementary school children when the information you are protecting only has a useful lifespan of a few minutes.

You point, while correct, is irrelevant to my point.

• #### Re:Can someone explain this to me? (Score:5, Interesting)

on Thursday January 07, 2010 @01:20PM (#30685432) Homepage

Other people have explained factorization in this thread (finding the prime factors that make up a composite number), but I just wanted to point out why making a "nice big chart" won't work.

The "nice big chart" would have to be very big. If you wanted to factor all the numbers from 1 to 2^768, you'd need a chart with 2^768 entries on it. This chart would need to be made of something, or stored on a disk that was made of something. Made of something means it needs to be made of matter, which means it needs to be made of atoms. In the observable universe, there are about 2^84 atoms, so you'd need a universe around 8x10^205 times larger than ours to store the chart in.

• #### Re: (Score:2)

Not exactly true, though the conclusion is almost correct. The problem is that the domain is not 2^768 large. Not all numbers 768 bits long are products of two primes.
• #### Oblig. Futurama reference (Score:2)

Or you could just use tiny atoms...but have you priced those lately? I'm not made of money!
• #### Re: (Score:2)

Factorisation is just the process of splitting a number - say, 21 - into the numbers that multiply to produce it: 3*7=21. It is cryptographically useful because it doesn't have a short way of doing it: you have to simply try dividing by 2, 3, 4, 5, etc, till you get an answer. When you have a number that's several hundred digits long and only has two relatively large factors, this takes a very long time. There are some tricks you can use to speed it up, but that's essentially it.
• #### Re: (Score:2)

It is cryptographically useful because it doesn't have a short way of doing it: you have to simply try dividing by 2, 3, 4, 5, etc, till you get an answer. When you have a number that's several hundred digits long and only has two relatively large factors, this takes a very long time. There are some tricks you can use to speed it up, but that's essentially it.

This is very, very wrong. What you describe is the most naive possible way to factor a number, a.k.a. trial division (without an obvious "trick" to speed it up: not bothering dividing by composites). There are far more efficient ways to factor large numbers. The fastest, currently, for numbers over about 90 digits without any easily-found smaller factors, is the General Number Field Sieve.
http://en.wikipedia.org/wiki/Integer_factorization [wikipedia.org]
http://en.wikipedia.org/wiki/Trial_division [wikipedia.org]
http://en.wikipedia.org/ [wikipedia.org]

• #### Re: (Score:2)

In college I wrote a Python program capable of factoring primes up to 1024 bits long. It ran fairly quickly. I should dig out that program, and post it here for peer review. I think you'll find some cleverness in the algorithm used.

Oh here it is.

# Title: Circular Imaginary Number Prime Factorization Program.
# Released under the GPL
#
# Uses imaginary numbers, ratio of circumference to diameter in
# the calculation of the factors of a prime number.
#
# Able to factor prime numbers as large as 1024 bits and up

• #### Re: (Score:2)

Well, 768 was never a standard length for RSA. Everything smaler than 1024 bits was considered broken long ago (512 was broken a few years ago). What this really means is that we should stop using 1024 bits already, and standardize on 2048. By the way, 2048 bits RSA is expected to never be broken on Earth (if we ever go to space and start gathering the majority of the power released by a star, things change), but nobody is really certain.
• #### Re: (Score:2)

What about how does this RSA-768 refer to the common RSA-128 "strong encryption" used in SSL/HTTPS?

Does the 128-bit mean a 128-bit key that can be trivially factored? Or is it something different?

• #### New algorithms? (Score:3, Interesting)

on Thursday January 07, 2010 @12:45PM (#30684948)
1024 bit RSA keys are already considered insecure due to the possibility of finding more efficient algorithms. 2048 is considered secure enough.
• #### Re:New algorithms? (Score:5, Insightful)

on Thursday January 07, 2010 @12:57PM (#30685106)
And newly generated keys for PGP/GPG are suggested to be at least 4096 bits.
• #### The real scary part is 3 years to obsolecence (Score:3, Interesting)

I'd agree with that for government and it's true that the military should phase out 1024, but does the general public need to worry?

• #### Re:The real scary part is 3 years to obsolecence (Score:5, Insightful)

on Thursday January 07, 2010 @01:48PM (#30685810) Journal

In the security world, there's always a tradeoff between the cost of the security, the cost to an attacker to break the security, and the value of the thing being protected.

In the military world, there are many secrets which need to be (are seen as needing to be) kept for many years. For these, an encryption that takes a year and \$10M to break may not be good enough, because after a year and \$10M, an enemy might have information worth more than that. For my bank account, encryption that takes a year and \$10M to break is more than sufficient, because the value to an attacker is approximately \$47.32, plus the overdraft fees that they can stick me with.

There is no current concern for the average person, unless you're dealing in nuclear secrets or are protecting a politicians date book. Given a choice in the future, moving to a larger RSA key size is prudent change, but that's about it.

/frank

• #### Re: (Score:2)

Informative post. That's what I was thinking, just not so elaborately.

I guess that's what I was wondering. Is the key size doubling going to do much for "ME" in the next 5 years? What I don't know is what is the cost of the 2Mbit key in system resources to implement in an aplicable way?

Mind you I know nothing of these details, just typing out loud.

• #### Re: (Score:2)

At my bank \$47.32 + overdraft fees ~= \$10 M

• #### Re: (Score:2)

Those are two different values: The value of keeping your data secret (hidden from everyone else) versus the value of keeping your data available to you for your own use. Data backups satisfy the latter, encryption the former. For many people, most of their data needs to be available, but not necessarily hidden.
• #### Re: (Score:2)

Exactly. If a client loses their pics, they usually place a value of 0-Infinity on them.

\$0 if they are on face book, and available to the world.

If they are a hobby photographer, they usually are in the range of 100-500 usd.

If they lost nude pics of themselves to a malware infection, it could be infinate... 8')

I don't discriminate though, and help as many people as cheaply as possible.

The question is what is the cost to implement and use vs. the level of increased protection?

In reality, if someone wants to

• #### Not obsolete -- defunct (Score:2)

The number RSA-768 was taken from the now obsolete RSA Challenge list as a representative 768-bit RSA modulus.

In fact, the challenge list is defunct, the challenge having been canceled by RSA. The challenges are still scientifically interesting, so to call them obsolete is factually inaccurate.

• #### Re: (Score:2)

In fact, the challenge list is defunct, the challenge having been canceled by RSA. The challenges are still scientifically interesting, so to call them obsolete is factually inaccurate.

You need to address this to the authors of the paper itself, since dtmos didn't "write" a "summary" so much as directly cut & paste from the paper's first paragraph. Yeah, yeah I did RTFA, what was I thinking...

• #### why wait? (Score:2)

Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.

Or immediately if you are encrypting things now which you want to remain secret throughout the decade and beyond.

"Little prigs and three-quarter madmen may have the conceit that the laws of nature are constantly broken for their sakes." -- Friedrich Nietzsche

Working...