# Factorization of a 768-Bit RSA Modulus

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

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

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

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

## Re:Meanwhile in Canada... (1)

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

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)

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

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)

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)

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

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

## Re:Meanwhile in Canada... (1)

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

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

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

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

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

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

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

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

## Rockoon (1252108) | more than 4 years ago | (#30685422)

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

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

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

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

## 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 message0<=m<ncan be transformed into the ciphertextc=m^e mod nand the ciphertext can be decrypted asm=c^d mod n.If one can solve the discrete logarithm problem over

Z_n(integers modulon), then one can recover the exponentdgiven the elementmand a basec. One can simply encrypt arbitrary messagesmto obtain a ciphertextcand apply the basecdiscrete logarithm inZ_nto obtaind.## Re:Can someone explain this to me? (1)

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

## 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: ...a third of a day. (hundrets of years * 365 / hundrets of thousands of sytems)

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

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

twiceas 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 harderreally 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

notcryptographically 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

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

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

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

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

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

## New algorithms? (3, Interesting)

## Jonas Buyl (1425319) | more than 4 years ago | (#30684948)

## Re:New algorithms? (5, Insightful)

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

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

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

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

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

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

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

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.