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!

Factorization of a 768-Bit RSA Modulus

CmdrTaco posted more than 4 years ago | from the that's-a-lotta-math dept.

Math 192

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

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

Meanwhile in Canada... (-1, Troll)

denis-The-menace (471988) | more than 4 years ago | (#30684616)

We are forced to use 128-bit encryption for online banking!

Re:Meanwhile in Canada... (1, Informative)

Anonymous Coward | more than 4 years ago | (#30684628)

Isnt it AES?

Re:Meanwhile in Canada... (1)

Icegryphon (715550) | more than 4 years ago | (#30684706)

Isnt it AES?

Ha, all my important documents are encrypted in Lucifer [wikipedia.org]
ALL HAIL SATAN!

Re:Meanwhile in Canada... (0)

Anonymous Coward | more than 4 years ago | (#30684792)

I was always a fan of twofish, My Niece on the other hand like the red and blue fishes better

Re:Meanwhile in Canada... (4, Funny)

Icegryphon (715550) | more than 4 years ago | (#30684950)

I was always a fan of twofish, My Niece on the other hand like the red and blue fishes better

Atleast she doesn't do blowfish.

Re:Meanwhile in Canada... (0)

Anonymous Coward | more than 4 years ago | (#30685656)

And you know this how?

Re:Meanwhile in Canada... (3, Informative)

Anonymous Coward | more than 4 years ago | (#30684828)

AES is a symmetric block cipher, meaning, you both need a shared key. While yes, the actual encryption on the data may be AES (I don't know this for sure), you still need to use a public key encryption method like RSA in order to handshake and transfer keys to each other before using AES.

Re:Meanwhile in Canada... (1)

tempest69 (572798) | more than 4 years ago | (#30685804)

My guess is that the block cipher is selectable (in a manner similar to SCP), and I'm betting that it defaults to AES.
The new Intel proc's rock at AES encrypt/decrypt. Which will likely make it the speed king over blowfish.

Storm

Re:Meanwhile in Canada... (0)

Anonymous Coward | more than 4 years ago | (#30684662)

I don't believe you. Post your account credentials so I can check for myself.

Re:Meanwhile in Canada... (5, Informative)

jasonwc (939262) | more than 4 years ago | (#30684666)

I hope this is a joke. If not, you are confusing the strength of symmetric key encryption and public key encryption. The latter requires larger key sizes because the public and private key pair are mathetmically related whereas in symmetric encryption, there is a single key, and it ought to be randomly generated, and have no mathematical relation to any other value.

The key sizes are given for RSA/DSA encryption. Elliptical curve crypto can use much smaller key sizes while maintaining equivalent security levels. Unfortunately, most ECC is patent encumbered.

Re:Meanwhile in Canada... (1)

Kolie (1012967) | more than 4 years ago | (#30684716)

Maybe they force him to use 128-bit RSA. He didn't really specify.

Re:Meanwhile in Canada... (2, Insightful)

jasonwc (939262) | more than 4 years ago | (#30684844)

Yes, but he's likely referring to the strength of the SSL connection to his bank. While authentication is done with public key crypto (probably 1024 or 2048 bit key), the actual data stream is encrypted with some symmetric cyrpto algo such as AES or RC4 at 128 or 256 bits.

Re:Meanwhile in Canada... (4, Informative)

Rich0 (548339) | more than 4 years ago | (#30685726)

Yes, but he's likely referring to the strength of the SSL connection to his bank. While authentication is done with public key crypto (probably 1024 or 2048 bit key), the actual data stream is encrypted with some symmetric cyrpto algo such as AES or RC4 at 128 or 256 bits.

That is only helpful if the person sniffing the SSL connection doesn't capture the initial handshake.

The problem with symmetric crypto is key exchange. With SSL the client generates a premaster key, encrypts it with the server's public key, and sends it to the server. Then the client and server use this to derive a session key (at least, that is my reading of the relevant docs - I think the specifics depend on the exact cipher used). So, if you can crack the RSA key, then you can obtain the session key, which makes the entire session obtainable.

To use symmetric crypto you either need a shared secret, or you need to use a key-exchange technique. I believe all the key-exchange techniques are vulnerable to factoring (or P=NP issues in general), although their details vary. If factoring becomes easy we'll never be able to encrypt communications between parties unless they have a secure channel to exchange keys (typically involving plane tickets).

Disclaimer, I'm not a cryptographer and if somebody has more to add I'm all ears.

Re:Meanwhile in Canada... (1)

jasonwc (939262) | more than 4 years ago | (#30685948)

Yeah, I'm aware. I'm just pointing out what the first post was likely referring to.

Re:Meanwhile in Canada... (1)

skylerweaver (997332) | more than 4 years ago | (#30686048)

I thought they share a key with the http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange [wikipedia.org]

So it doesn't matter if someone captures the initial handshake.

Re:Meanwhile in Canada... (1)

Chris Burke (6130) | more than 4 years ago | (#30686336)

So it doesn't matter if someone captures the initial handshake.

It matters if they can break the public key encryption, and thus discover the shared private key.

Re:Meanwhile in Canada... (3, Informative)

morgan_greywolf (835522) | more than 4 years ago | (#30685448)

Unfortunately, most ECC is patent encumbered.

Well, djb wrote a particular algorithm, Curve25519 [cr.yp.to] , that's in the public domain.

(Yeah, yeah, save your comments about djb's personality. Like it or not, the guy's a crypto and security genius.)

Re:Meanwhile in Canada... (3, Informative)

Anpheus (908711) | more than 4 years ago | (#30685888)

He said patent encumbered, not copyrighted.

Something can be open source and if it implements something protected by patent in the US or in other nations with laws that allow software patents or have agreements to make US patents enforceable, then it can still be illegal to distribute, and you'd probably be liable for damages if you built commercial software, but IANAL.

I think the patent encumbrances of ECC are the reason it's mysteriously absent from a lot of commercial software that deals with security and even a lot of Linux distros and software. I'd have to double-check, but for example, I don't think Windows Certificate Services supports ECC.

P.S.: Isn't it horrible that Error Correcting Codes and Elliptic Curve Cryptography have the same acronym? IMHO, we should rename one of the TLAs before it becomes a PITA.

Re:Meanwhile in Canada... (1)

corbettw (214229) | more than 4 years ago | (#30684744)

Don't worry, your money will be safe in my offshore account.

Re:Meanwhile in Canada... (0)

Anonymous Coward | more than 4 years ago | (#30684966)

Which is same as his onshore account?

Re:Meanwhile in Canada... (1)

havock (42287) | more than 4 years ago | (#30684956)

We are forced to use 128-bit encryption for online banking!

Maybe you need to get a better bank! I just logged into a top 5 Canadian bank and they are using AES-256 with a 1024-bit RSA cert.

Re:Meanwhile in Canada... (1)

Bert64 (520050) | more than 4 years ago | (#30685166)

A lot of banks here still only support 128-bit, most of them only support 128-bit RC4 and don't have support for any kind of AES, let alone 256-bit.
PayPal used to do AES256, but they also don't support it anymore, which seems quite ridiculous.

Re:Meanwhile in Canada... (1)

xZgf6xHx2uhoAj9D (1160707) | more than 4 years ago | (#30685316)

Keep in mind that AES-256 only uses a 128-bit key and has recently been broken (down to 118 bits of security or something like that?). AES-256 is currently less secure than AES-128.

Re:Meanwhile in Canada... (3, Informative)

profplump (309017) | more than 4 years ago | (#30685504)

AES-256 uses a 256-bit key. It has a fixed block size of 128 bits, but that's unrelated to the key length.

There is a related-key weakness in AES-256 and AES-192, bringing their effective strength down to 2^119 and 2^176 respectively. So AES-192 is your best bet right now, though 2^119 or 2^128 are not exactly feasible attack keyspaces either.

Re:Meanwhile in Canada... (1)

FrankSchwab (675585) | more than 4 years ago | (#30685630)

uhh, no.

AES-256 uses a 256 bit key. It may have a weaker than expected key schedule for using that key, as Schneier has opined (do I know what that means? Not a chance), but it's certainly 256 bits long.

Re:Meanwhile in Canada... (0)

Anonymous Coward | more than 4 years ago | (#30685998)

You're so wrong I'm not bothering to provide a correction. If your laziness and opinionated ignorance is that great, it's probably a waste of time. Google is your friend.

Re:Meanwhile in Canada... (1)

canajin56 (660655) | more than 4 years ago | (#30685722)

That would be RBC ;) BMO uses 3DES-196, TD also uses AES-256, but with a 2048 cert. Scotia Bank and CIBC use RC4-128 though. I guess the OP uses one of those two, and figured "if my bank does this, they all must!"

Re:Meanwhile in Canada... (1)

FrozenGeek (1219968) | more than 4 years ago | (#30685444)

128-bit keys for symmetric ciphers, such as we use for banking equate to much large key sizes for asymmetric ciphers such as RSA. You are comparing apples and volkswagens.

Bad math... (1, Funny)

Anonymous Coward | more than 4 years ago | (#30684708)

WTF? 2^1024 != 2^768*1000

Screw you slashdot for making me type more than my perfectly concise statement above that gets the effing point across just fine.

Re:Bad math... (3, Insightful)

pclminion (145572) | more than 4 years ago | (#30684772)

Everyone likes to show off how stupid they are, I guess. You don't measure public key keyspace like that. Not all possible bit patterns are valid keys. In fact, VERY FEW bit patterns are valid keys.

Re:Bad math... (4, Funny)

mikeee (137160) | more than 4 years ago | (#30685582)

That's why we need to be more proactive; instead of trying to eliminate all the invalid keys, we should just pick the strongest possible key and standardize on it.

Re:Bad math... (1)

marcosdumay (620877) | more than 4 years ago | (#30684784)

Yep, but factoration also isn't O(a^n) where a is constant. It is more like O(a^(n/b)) where b is quite bigger than 1.

Re:Bad math... (3, Insightful)

cperciva (102828) | more than 4 years ago | (#30685026)

It is more like O(a^(n/b))

No, factorization is more like O(a^(n^b)). For GNFS on RSA-sized inputs, 1000^(n^(1/3) - 2.5) is a good estimate of the number of operations required.

Re:Bad math... (1)

SoVeryTired (967875) | more than 4 years ago | (#30685700)

You need to brush up on your exponents.

If a is some constant, then a^(n/b) = (a^(1/b))^n.
Define c = a^(1/b)
then
a^(n/b) = c^n

You can't just say "where a is constant". You need to specify a.

Re:Bad math... (1)

marcosdumay (620877) | more than 4 years ago | (#30686670)

Yep, you are right. That was a mistake. And, as somebody already noticed, it is O(a^(n^(1/b))), where b > 1.

Re:Bad math... (0)

Anonymous Coward | more than 4 years ago | (#30684860)

They just took the line from the abstract in the paper.

Re:Bad math... (4, Informative)

jasonwc (939262) | more than 4 years ago | (#30684954)

They're comparing the relative strength of a 768 bit RSA key to a 1024 bit RSA key. Because of the mathematical correlation between the public and private keys, the strength is nowhere near 2^768 or 2^1024. RSA has created a comparison table for RSA -> symetric cipher strength.

1024 bit ----> 80 bit
2048 bit ----> 112 bit
3072 bit ----> 128 bit

However, "1000 times stronger" seems far too small, in any case.

Source: http://www.rsa.com/RSALABS/node.asp?id=2004 [rsa.com]

Re:Bad math... (4, Informative)

pow(b,2) (1715796) | more than 4 years ago | (#30686852)

Cryptographic strength, as applied to RSA keys, is measured by the time needed to factor the public modulus. The fastest way to do this is today is using the general number field sieve. The run time of the general number field sieve can be estimated as T(b) = exp(1.923 * ln(2^b)^(1/3) * (ln( ln(2^b)))^(2/3)), where b is the size of the input in bits. See Aoki's paper on a kilobit SNFS factorization for details. Chug through this estimate for b = 1024 and b = 768, and you'll find that the ratio is approximately 1000 (I got 1221.15). That's why 1024 bit RSA keys are approximately 1000 times stronger.

Can someone explain this to me? (2, Interesting)

Monkeedude1212 (1560403) | more than 4 years ago | (#30684814)

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? (5, Informative)

Arcquist (1100065) | more than 4 years ago | (#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:Can someone explain this to me? (1)

bytethese (1372715) | more than 4 years ago | (#30685006)

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? (4, Informative)

Rockoon (1252108) | more than 4 years ago | (#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? (0)

Anonymous Coward | more than 4 years ago | (#30686074)

That's an implementation choice, but the principle does call for p and q to be actual primes in order to be truly secure.

Re:Can someone explain this to me? (4, Informative)

swillden (191260) | more than 4 years ago | (#30686290)

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? (1, Funny)

Anonymous Coward | more than 4 years ago | (#30686508)

it's very reasonable to simply say "it's prime"

i guess Megatron will be pissed off

Re:Can someone explain this to me? (4, Informative)

Trepidity (597) | more than 4 years ago | (#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:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30686368)

What is it with Americans and writing psuedo instead of pseudo?

I know they sound the same in English, but that's hardly any excuse to have so many people making this mistake. Do your professors write psuedo as well?

Re:Can someone explain this to me? (1)

xaustinx (926033) | more than 4 years ago | (#30686692)

"unless something dramatic changes in factoring" Something like using ATI and NVIDIA GPU's to accelerate factoring? something dramatic like that? http://eecm.cr.yp.to/pc109-20090901.pdf [cr.yp.to] If you take the latest in CPU/Multi GPU configurations; and build around the idea of operating them for this purpose, i think RSA-1024 could be cracked in a similar amount of time. Far less than 10 or 5 years. Their paper doesn't make any references at all to GPU accelerated factoring, it's not even on their radar. http://fastra2.ua.ac.be/ [ua.ac.be]

Re:Can someone explain this to me? (1)

russotto (537200) | more than 4 years ago | (#30686818)

Last I saw, the GPU based processors had a serious problem when using for cryptanalysis; there was no fast parallel inverse calculation method. However, I was looking at elliptic curve encryption; I don't know if factoring requires inverse calculation.

Re:Can someone explain this to me? (1)

bytethese (1372715) | more than 4 years ago | (#30684988)

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:Can someone explain this to me? (1)

melted keyboard (798559) | more than 4 years ago | (#30685114)

An RSA public key consists of (e, n) and the private key consists of (d, n). If you can factor "n" into "p" and "q", then it is trivial to compute "d" from "e".

Re:Can someone explain this to me? (1, Informative)

Anonymous Coward | more than 4 years ago | (#30685188)

No, solving discrete logarithms allows you to break the El Gamal public key encryption system. Like prime factorization, the discrete logarithm problem is considered "hard".

Re:Can someone explain this to me? (1, Informative)

Anonymous Coward | more than 4 years ago | (#30685450)

Recovering an RSA secret key is no harder than the discrete logarithm problem. The RSA public key consists of the pair (e,n) and the associated secret key is (d,n) where any message 0<=m<n can be transformed into the ciphertext c=m^e mod n and the ciphertext can be decrypted as m=c^d mod n.

If one can solve the discrete logarithm problem over Z_n (integers modulo n), then one can recover the exponent d given the element m and a base c. One can simply encrypt arbitrary messages m to obtain a ciphertext c and apply the base c discrete logarithm in Z_n to obtain d.

Re:Can someone explain this to me? (1)

kalidasa (577403) | more than 4 years ago | (#30685394)

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 discrete log problem will be made trivial by Schor's algorithm.

Re:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30685702)

By the way, yes, "through multiplication mod (p-1)(q-1)" is a simplification for "using the extended Euclidean algorithm to find the multiplicative inverse of the public key in the cyclic group Z/(p-1)(q-1)."

Re:Can someone explain this to me? (1)

jonbryce (703250) | more than 4 years ago | (#30685004)

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

Re:Can someone explain this to me? (4, Informative)

Mini-Geek (915324) | more than 4 years ago | (#30685030)

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:Can someone explain this to me? (2, Insightful)

Hurricane78 (562437) | more than 4 years ago | (#30686828)

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 compromised? (After all, the programmer should be an expert in this area. ;)

Re:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30685060)

No. Factorization means that they split the product of two prime numbers into the constituent factors.
As you know now, the premise of RSA public key crypto lies in that it's hard to factorize "long" numbers
(768 bit long, in this case). They have shown that it's doable to factor a 768 bit long non-prime
number.

Keep in mind that proving non-primality and finding a factor are two separate issues. There are very
good primality tests that work in reasonable time on numbers tens of millions bit long (see GIMPS,
for example), yet (some/any) factors of those non-prime numbers are yet to be found, in most cases.

Re:Can someone explain this to me? (1)

Sir_Lewk (967686) | more than 4 years ago | (#30685064)

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:Can someone explain this to me? (1)

maxume (22995) | more than 4 years ago | (#30685082)

They factored a particular number named "RSA-768". They did this using a large but obtainable amount of computing power, meaning that RSA-768 probably shouldn't be used to protect secrets that are more valuable than the amount of computing power they expended (and given how easy it is to use bigger keys, they recommend doing that for everything).

Re:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30685228)

So, this is like the 1024 blade razor?

Wouldn't the expense of carrying around a large cipher become burdensome at some point? Or, are they expecting that Moore's law will continue indefinitely, and that they will always have gobs and gobs of memory and processing power to work with?

One would think that there is a theoretical crossroads (near the quantum bit level) where it will become impractical to have such large ciphers just to check your bank account, because increasing the size of the cipher would require Nth order more bits to be processed on a device architecture that cannot get any more dense without seriously increasing the complexity of the system. (It would become very prohibitive to just increase the bit depth at this point, since quantum entanglement devices become increasingly difficult to manufacture and reliably use as the number of bits increases.)

Granted, that is a long ways off, but this still looks like a virtual incarnation of the 1024 blade razor, where adding more blades "makes it better!"

Re:Can someone explain this to me? (2, Insightful)

maxume (22995) | more than 4 years ago | (#30685604)

Sort of, the key sizes are being increased because it is an effective way to offset the increases in computing power, not for marketing reasons.

If something convincingly better comes out, I'm sure people would use it.

Re:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30686382)

Maybe we can use Green's Theorem to process a random sieve field with a SixSigma eigenvalue partial differential equation to factorize the resultant RSA?

Re:Can someone explain this to me? (1)

ispeters (621097) | more than 4 years ago | (#30686396)

I think I get your point, but I also think you've missed a point: a 1024-blade razor is probably incrementally better than a 1023-blade razor (for some value of "better"). On the other hand, a 1024-bit key is twice as good as a 1023-bit key. Unless I've forgotten my 3rd-year CS courses, factorization difficulty is exponential in the number of bits, so things get harder really quickly. Of course, Moore's Law is also exponential so, in theory, the time from "use 256-bit keys" to "use 512-bit keys" is about the same as the the time from "use 512-bit keys" to "use 1024-bit keys", but that sort of rebuts your comment. If Moore's Law continues to hold, then the arms race continues, but it remains easier to compute and store a key of arbitrary size than to crack a key of the same size. If Moore's Law becomes a wistfully-remembered relic, then the arms race is over and there's a well-known key size that's easy to generate and store but hard to crack. The only way for the cracking side to win is to find an efficient way to factor large integers. Quantum computing is a potential option, finding a general solution to NP-complete problems is another. Neither seems imminent.

Re:Can someone explain this to me? (1)

shadow_slicer (607649) | more than 4 years ago | (#30685196)

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.

Factorization is simply finding the prime factors of a number:
For example, the factors of n=21 are p=3 and q=7.

In RSA, I would take these factors and use them to calculate some other things:
I choose e=11 to be my public key exponent (since it is less than and shares no common factors with (7-1)*(3-1)). Then I would calculate my private key exponent "d" such that d*e=1 mod n: for example, d=2 would work.

So you announce n and e publicly. Someone can break your key if they can find d, which is equivalent to finding the two factors of n: p and q. So if I were to tell you 21, you have basically broken my private key once you know 3 and 7 are p and q.
In the article, it's not much different. Basically they found p and q for a 768-bit n.

Re:Can someone explain this to me? (3, Interesting)

Sir_Lewk (967686) | more than 4 years ago | (#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? (3, Insightful)

swillden (191260) | more than 4 years ago | (#30686406)

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:Can someone explain this to me? (1)

shaitand (626655) | more than 4 years ago | (#30686884)

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:Can someone explain this to me? (1)

morgan_greywolf (835522) | more than 4 years ago | (#30685672)

Exactly. They found p and q for one 768-bit n, and it took them 2.5 years, 3 supercomputers and 5 terabytes of data. If your data is important enough for someone to spend these kind of resources, you simply choose a 1024-bit n, or, even better, a 2048-bit n.

If your data is not important enough for someone to spend those kind of resources, then you can continue with 768-bit RSA and suffer no ill effects. If Moore's law holds true, you may want to consider upgrading to 1024-bit. The truly paranoid will want to use 2048-bit n or larger.

To put it very briefly: nothing to see here, move along.

Re:Can someone explain this to me? (1)

Sir_Lewk (967686) | more than 4 years ago | (#30686202)

I find it weird that people keep on quoting the 5 TB stat as one of the reasons this isn't anything to be worried about. With a few hundered dollars, and a 5 minute drive, I can pick up 5TB of storage right now at Walmart.

Re:Can someone explain this to me? (1)

morgan_greywolf (835522) | more than 4 years ago | (#30686282)

Sure. But the 5 TB of storage you can buy from Walmart comes blank.

5 TB is a lot of data to generate when you're not using BitTorrent to do it. :->

Re:Can someone explain this to me? (1)

Sir_Lewk (967686) | more than 4 years ago | (#30686332)

Well yeah of course, that is where the supercomputers and several years of number crunching comes in.

On a semi-related note, I still haven't been able to fill my 320GB harddrive with all of my torrenting :o I honestly don't know how people do it.

Re:Can someone explain this to me? (1)

morgan_greywolf (835522) | more than 4 years ago | (#30686352)

Two words: high-def movies

Re:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30686446)

You would want to have most of that data in memory, not on disk as that would be very slow. That way you wouldn't get the result in 2.5 years but a very large multiple of that time.

Factorization is still hard. These things can't (yet) be done effectively on consumer hardware.

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

Digital_Quartz (75366) | more than 4 years ago | (#30685432)

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:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30685500)

What they did is considerably more involved than "testing all the possible values". I've got a PhD in maths (wrong sort for what they're doing), and it will still take me a couple of hours (at least) to understand what they did and why it works. Its all tied into number field theory and other such fun. The basics seem to be finding solutions of u^2 = v^2 mod n over some smoothed approximation to the integers. u and v then have a beter than even chance of being factors of n. The tricky part is how you find trial values for u and v...

So, the short answer to "can someone explain this to me?" is "not without a course in number theory first".

Re:Can someone explain this to me? (1)

u38cg (607297) | more than 4 years ago | (#30685560)

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:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30686086)

I don't really want to know how RSA and other encryption systems work as much as I want a simple table of settings/key sizes that will make me immune to advances in technology making them crackable without my having to learn the details of each cryptosystem.

What is the minimum key length for each style of encryption that will mean that cracking the key with a Beowulf cluster of today's best technology would take longer than the age of the universe?

I want to be able to encrypt my signed confession to assassinating President Oprah Winfrey, post it on usenet for posterity and be able to rest easy that not even the concerted effort of nations could uncover by secret by decrypting the file.

Often the author of an encryption package will put a 'recommended value' in the documentation, but it's always with respect to the day's current technology. I want confession goddamnit proof against anything short of discovering P=NP. Speed is nice, slow is OK. Absolutely reliable encryption from now and into the future for at least 100 years is a must.

Re:Can someone explain this to me? (0)

Anonymous Coward | more than 4 years ago | (#30686486)

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

I don't necessarily mean to pick on you, but this post is mostly in response to a number of the other posts below yours that seem to be confused on the subject, too. There seem to be a lot of other people posting here that clearly have some sort of CS and programming backgrounds that don't seem to understand factorization either. And yet somehow this is something that I learned about in high school (and it was covered in a few math classes in college, too). I've never taken a CS class in my life, but I am able to follow the general ideas of what the article is talking about. Why is it that people that specifically work in the field that this applies to don't seem to understand these concepts very well?

Re:Can someone explain this to me? (1)

Chapter80 (926879) | more than 4 years ago | (#30686542)

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
#
# Key in your input in either decimal or binary

# Runs in O() time.

import math

def exponentiate(num, exponent):
        """exponentiate function, starts at 1, and multiplies by num
              as many times as exponent tells you to.
              Needed as a function, since ^ operator doesn't work on
              complex numbers."""
        result = 1
        for x in range(exponent.real):
                result = result * num
        return result

primenum = int(raw_input("Please enter a really big prime number: "))
factors = []
i = complex(0,1)

for factor_candidate in range ((exponentiate(math.e,math.pi*i)),2):
        if primenum % factor_candidate == 0:
                factors.extend([factor_candidate, primenum/factor_candidate])
print factors

Re:Can someone explain this to me? (1)

marcosdumay (620877) | more than 4 years ago | (#30686586)

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:Can someone explain this to me? (1)

vxice (1690200) | more than 4 years ago | (#30686626)

Breaking RSA encryption will become much easier once quantum computing becomes realistic. When factoring large numbers the bottleneck is in data transfer if using multiple computers which is almost required due to processing requirements. Quantum computing allows for better data transfer rates and there are already algorithms that take advantage of this and have been proven in theory but until we get our hands on quantum computing rsa will remain secure.

New algorithms? (3, Interesting)

Jonas Buyl (1425319) | more than 4 years ago | (#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? (5, Insightful)

z4ns4stu (1607909) | more than 4 years ago | (#30685106)

And newly generated keys for PGP/GPG are suggested to be at least 4096 bits.

Re:New algorithms? (0)

broken_chaos (1188549) | more than 4 years ago | (#30685820)

Really? Can you cite that somewhere? Last I recall seeing (a few months ago, only) is that 2048-bit was the recommended number (likely secure to somewhere around 2030, I believe), and 4096-bit was the maximum without source modification, due to compatibility issues with some older GPG/PGP implementations for anything larger.

Re:New algorithms? (1)

z4ns4stu (1607909) | more than 4 years ago | (#30686868)

I just tried generating a new key using GPG and you appear to be correct. I'll have to go back and try to figure out what I was doing that it recommended I use a key no smaller than 4096-bits.

The real scary part is 3 years to obsolecence (2, Interesting)

DRAGONWEEZEL (125809) | more than 4 years ago | (#30685224)

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 (1)

z4ns4stu (1607909) | more than 4 years ago | (#30685400)

I'd say that depends on two things:

  1. How much you value your privacy vs. the difficulty of distributing new keys
  2. How much you like new toys

Re:The real scary part is 3 years to obsolecence (1)

DRAGONWEEZEL (125809) | more than 4 years ago | (#30685836)

hehe

1. I love new toys.

2. I don't keep anything private except pins,passwords,and underpants.

I guess I forgot though that there is this new fangled graphics card as a processor thing... I suppose some malware creator could create a distributed program taking advantage of the power of a graphics card to break these down. In which case, 2048 is a only a few years away (but by then graphics cards will be as big as a TV acording to the size of my 5870)

Re:The real scary part is 3 years to obsolecence (0)

Anonymous Coward | more than 4 years ago | (#30685580)

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?

Yes, what could the general public possibly fear from ubiquitous monitoring by the government or military?

Re:The real scary part is 3 years to obsolecence (1)

DRAGONWEEZEL (125809) | more than 4 years ago | (#30686024)

Ubiquitous monitoring encrypted at 2048...
why would they want to hear me fart, and then encrypt it at that rate?

Dude take off your tinfoil hat, their rays can penetrate that now. Please switch to a graphene and lead cap asap. I have one for sale for a measley 2.2 mil. Comes w/ bottle opener, and guiness logo. May only stop rays from one direction. Void when worn over a toupe or comb-over. Not effective on bare skin. Some side efects have been experienced. These include but are not limited to: spontaneous combustion, alien abduction, dreams of standing on a myan tempmle w/ thousands of naked ladies throwing pickles at you, itchy eyes, atraction to fat chicks, and sometimes in rare occurences death, resurection, then death again. Batteries not included. Not valid with any other offer. This coupon has No cash value.

Re:The real scary part is 3 years to obsolecence (4, Insightful)

FrankSchwab (675585) | more than 4 years ago | (#30685810)

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:The real scary part is 3 years to obsolecence (1)

DRAGONWEEZEL (125809) | more than 4 years ago | (#30685926)

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:The real scary part is 3 years to obsolecence (1)

JDeane (1402533) | more than 4 years ago | (#30686794)

Your post gave me a great idea...

Sure your account may be empty and cracking the encryption not worth it.

but I am sure that there would be more then 10 million dollars worth of accounts in the banking computer.

So why not try to crack them all at one time? What I mean is that if a key does not work for say your encrypted account or what ever try the same key on all the accounts. Probably faster that way then then to try all the keys on one account.

Of course this all assumes unfettered access to a banks computer, and at that point it may just be easier to rob the local Quicky Mart.

Now for downloaded .gov files thats a whole different mess. Pretty much the more secret something is they should encrypt the hell out of it pick some number of bits that makes it so hard to crack that by the time they do the information will be 50 years old.

I think for something to remain that secret the encryption should be measured in MB's not bits. I like the idea of a random location in a Mandelbrot sequence used as key but that might be too easy to crack (I am not a math person when it comes to stuff like this the hardest encryption I ever cracked in my entire life was the Captain Crunch hidden letter crap.. lol) So yeah it could be way too easy for all I know. but I think cracking it would look awesome lol

Re:The real scary part is 3 years to obsolecence (1)

EndlessNameless (673105) | more than 4 years ago | (#30686066)

Your sig makes your post exceptionally ironic.

Re:New algorithms? (1)

Dc0der (783811) | more than 4 years ago | (#30685668)

Due to the possibility of finding more efficient algorithms? Wouldn't that rule out RSA-any size? 1024 bit RSA keys are considered mildly secure because they are breakable with a large budget.

Not obsolete -- defunct (1)

rwade (131726) | more than 4 years ago | (#30685964)

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:Not obsolete -- defunct (1)

Vainglorious Coward (267452) | more than 4 years ago | (#30686550)

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? (1)

Jodka (520060) | more than 4 years ago | (#30686334)

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.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?