Factorization of a 768-Bit RSA Modulus 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.'"
Can someone explain this to me? (Score:3, Interesting)
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)
Re: (Score:2)
Re:Can someone explain this to me? (Score:5, Informative)
Re:Can someone explain this to me? (Score:5, Informative)
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)
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)
No real point to this post, just a memory from 1987.
Re: (Score:2)
Americans have a very low functional literacy rate. The problem is endemic, and is unlikely to go away as people care less about accuracy and more about expediency.
Re: (Score:2)
In your rush to respond, you forgot that you arent an expert in the subject so should
Re: (Score:2)
graph of runtime [wikipedia.org]
Re: (Score:2)
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: (Score:2)
Re: (Score:2)
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)
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: ...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 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)
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)
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: (Score:2)
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: (Score:2)
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: (Score:2)
Ah contraire!
Factoring 768-bit RSA keys can't (yet) be done effectively on comsumer hardware, but it is extremely practical for 512-bit keys. TI graphing calculator hackers did it with the donated CPU time of a handful of hobbists. And they did it 12 or so times in a matter of months.
That is a more accurate statement.
Re:Can someone explain this to me? (Score:5, Interesting)
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)
Oblig. Futurama reference (Score:2)
Re: (Score:2)
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)
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?
Re: (Score:2, Insightful)
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: (Score:2)
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
Re: (Score:2)
Don't forget that the computing time (big O) goes up by the cube of the size of the key when doing RSA. So something that takes 2 seconds at 1024 bits will take 8 seconds at 2048 bits.
Right now, RSA is still solid if you use at least 2048 bits for your key (which is the maximum size of a lot of smart cards). However, the key sizes that RSA needs are getting so large (some recommendations on keylength.com even go near 16384 bit keys), that it might be good to find another algorithm like ECC which only uses
New algorithms? (Score:3, Interesting)
Re:New algorithms? (Score:5, Insightful)
Re:New algorithms? (Score:4, Funny)
Here is the relevant wikipedia approved citation :
http://science.slashdot.org/comments.pl?sid=1501696&cid=30685106 [slashdot.org]
Re: (Score:2)
I, too, thought the 2048 was the default. However, in lieu of any reason not to choose 4096, I choose (and use) 4096.
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)
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: (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)
Lol whops ty for pointing that out.. I do that all the time, though I'm quite aware of the difference.
Re: (Score:2)
At my bank $47.32 + overdraft fees ~= $10 M
Re: (Score:2)
Your sig makes your post exceptionally ironic.
Re: (Score:2)
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
Re: (Score:2)
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: (Score:2)
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: spontane
Re: (Score:2)
That depends entirely on how much more efficient these new algorithms may be.
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)
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.
Re:Meanwhile in Canada... (Score:5, Informative)
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: (Score:3, Informative)
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... (Score:4, Informative)
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: (Score:2)
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.
http://blogs.technet.com/pki/archive/2008/01/23/how-to-set-up-a-ca-with-a-cng-ecc-certificate.aspx [technet.com]
Since Vista and Windows 2008 it does, but through CNG not through the more familiar CryptoAPI / CSP.
Even then it is limited to certain NIST curves - forget about doing any enhanced EC cryptography through that API.
Re: (Score:2)
What is funny is that in 1991, the NeXT had an implementation of ECC Fast Elliptic Encryption as part of the OS (think NeXTStep 2). However due to ITAR regs, it was removed from subsequent versions.
Re: (Score:3, Insightful)
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... (Score:5, Informative)
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: (Score:2)
Yeah, I'm aware. I'm just pointing out what the first post was likely referring to.
Re: (Score:2)
I'm unsure exactly what system is used but public keys may be used more thoroughly than you describe.
Example 1 : There are perhaps both presever and preclient keys that must be xored together, which are created separately on each side, and sent using the other's public key, thus ensuring that an eavesdropper must break both server and client public keys.
Example 2 : A sever could generate a session RSA key, digitally sign the session public key, and send both the session public and the server public key as
Re: (Score:2)
If symmetric key cryptography gets broken in general, what likely will happen is that the well heeled businesses would have a link between sites using quantum encryption. This link is extremely slow, so it would be used to set up session keys. Then the conventional Internet links would be used for the bulk data transfer.
People who don't have the cash for fiber optics would have to use lower tech means. One means would be have people generate a one time pad, and instead of PGP/gpg keysigning parties, peop
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
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: (Score:2)
If I am understanding correctly, the problem is that p is usually a pseudoprime, rather than a true prime. If you can factorize that, solving for a, b, and thus K becomes far easier.
The pseudoprime bit is because determining whether an arbitrary large number is prime is computationally expensive, but there are shortcuts that will detect most non-primes, but some numbers called pseudoprimes with very large factors slip through, which are usually good enough, as even though they aren't a true prime, there is
Re: (Score:2)
Public key and regular symmetric block ciphers differ completely in usage and attack.
Public key crypto is typically used to hide a random session key for a symmetric block cipher which is then used for the rest of the "conversation".
That is to say, your bank transactions are being encrypted with some block cipher like 3DES or AES whose random session keys are exchanged privately between your computer and the bank using public key crypto.
If your bank's public key were broken (this story), anyone could get th
Re: (Score:2)
The problem is that this is an oversimplification. See the WP entry on Diffie-Hellman.
The values sent between Alice and Bob are inter-related via the discrete log problem - so if you can (relatively) quickly calculate discrete logs you can obtain the session key.
This particular article is about factoring and not discrete logs. A magic way to quickly factor numbers wouldn't necessarily break D-H. However, this article wasn't about a magic way of breaking RSA, but brute-force factorization. If you can bru
Re: (Score:2)
The whole point of this story is that the math behind public keys can be broken after this amount of computation, given a 768 bit key. DH is not special in this regard.
Re: (Score:2)
Too bad it's already been cracked [schneier.com].
Re: (Score:2)
Re: (Score:2)
Don't worry, your money will be safe in my offshore account.
Re: (Score:2)
Re: (Score:2)
Eh, the one doesn't really have anything to do with the other. What you're talking about is 128 bit AES, which is symmetric encryption, which is shifting, xoring, and otherwise the making of chaotic of a block of data (16 bytes, in this case). RSA asymmetric encryption/decryption is more like a calculation that you miss certain parts of and therefore can really only be performed one way. To put it another way: symmetric encryption sees a block of data as a bits to be pushed around, while asymmetric encry
Re: (Score:2)
Isnt it AES?
Ha, all my important documents are encrypted in Lucifer [wikipedia.org]
ALL HAIL SATAN!
Re:Meanwhile in Canada... (Score:5, Funny)
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: (Score:3, Informative)
Re: (Score:2)
The new Intel proc's rock at AES encrypt/decrypt. Which will likely make it the speed king over blowfish.
Storm
Re: (Score:2)
Wait. There are intel chips now that do AES ? Like VIA's padlock ? 256 bit AES ?
Re: (Score:2)
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: (Score:2)
Yahoo Canada's sign-in is 1024-bit RSA using SHA-1 signatures, and a 128 bit RC4 session key.
Re: (Score:2)
Re:Meanwhile in Canada... (Score:4, Informative)
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: (Score:2)
There is a related-key weakness in AES-256 and AES-192, bringing their effective strength down to 2^119 and 2^176 respectively.
Only for related key attacks. Never ever leave out the context when talking about broken cryptographic algorithms.
Check it out, if you just generate a random key for each file you encrypt, then no such attack can take place.
AES-128 is certainly strong enough for the first couple of years anyway.
Re: (Score:2)
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: (Score:2)
Re:Bad math... (Score:4, Insightful)
Re:Bad math... (Score:5, Funny)
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: (Score:2)
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.
Um, no that's just for RSA and DSA. You can more or less measure ECC key spaces like this. AFAIK it is not a fundamental part of asymmetric cryptographic techniques. Since this IS about RSA, the GP is certainly incorrect though. So you make a very valid point but your explanation is slightly off.
Re: (Score:2)
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... (Score:4, Insightful)
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: (Score:2)
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: (Score:2)
Re:Bad math... (Score:5, Informative)
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... (Score:4, Informative)