How long will it take to crack an RSA encrypted private key if each of the primes used are 50 digits, 100 digits long? How can an RSA 2048 encryption be broken? The Lenstra group estimated that factoring a 1024-bit RSA modulus would be about 1,000 times harder than their record effort with the 768-bit modulus, or in other words, on the same hardware, with the same conditions, it would take about 1,000 times as long. For a perfectly secure and correct RSA implementation, factoring the modulus is the best attack we know of. The largest RSA modulus factored (also the largest semi-prime factored) is RSA-768, of the RSA Challenge. If you can't attack the math, you can attack the implementation, like in the side-channel attack you mentioned.

In the indictment that led to the expulsion of 10 Russian spies from the U.S. last summer, the FBI said that it had gained access to their encrypted communications after surreptitiously entering one of the spies' homes, where agents found a piece of paper with a 27-character password.

In essence, the FBI found it more productive to burglarize a house than to crack a 216-bit code, despite having the computational resources of the U.S. government behind it. That's because modern cryptography, when used correctly, is very strong. Cracking an encrypted message can take an incredibly long time.

'The entire commercial world runs off the assumption that encryption is rock-solid and is not breakable,' says Joe Moorcones, a vice president at SafeNet, an information security vendor in Belcamp, Md.

That's the case today. But within the foreseeable future, cracking those same codes could become trivial, thanks to quantum computing.

Before learning about the threat of quantum computing, it helps to understand the current state of encryption. There are two kinds of encryption algorithms used in enterprise-level communications security: symmetric and asymmetric, Moorcones explains. Symmetric algorithms are typically used to send the actual information, whereas asymmetric algorithms are used to send both the information and the keys.

Symmetric encryption requires that the sender and receiver both use the same algorithm and the same encryption key. Decryption is simply the reverse of the encryption process -- hence the 'symmetric' label.

There are numerous symmetric algorithms, but most enterprises use the Advanced Encryption Standard (AES), published in 2001 by the National Institute of Standards and Technology after five years of testing. It replaced the Data Encryption Standard (DES), which debuted in 1976 and uses a 56-bit key.

AES, which typically uses keys that are either 128 or 256 bits long, has never been broken, while DES can now be broken in a matter of hours, Moorcones says. AES is approved for sensitive U.S. government information that is not classified, he adds.

As for classified information, the algorithms used to protect it are, of course, themselves classified. 'They're more of the same -- they put in more bells and whistles to make them harder to crack,' says IDC analyst Charles Kolodgy. And they use multiple algorithms, he says.

The genuine weakness of AES -- and any symmetric system -- is that the sender has to get the key to the receiver. If that key is intercepted, transmissions become an open book. That's where asymmetric algorithms come in.

Moorcones explains that asymmetric systems are also called public-key cryptography because they use a public key for encryption -- but they use a different, private key for decryption. 'You can post your public key in a directory with your name next to it, and I can use it to encrypt a message to you, but you are the only person with your private key, so you are the only person who can decrypt it.'

The most common asymmetric algorithm is RSA (named for inventors Ron Rivest, Adi Shamir and Len Adleman). It is based on the difficulty of factoring large numbers, from which the two keys are derived.

But RSA messages with keys as long as 768 bits have been broken, says Paul Kocher, head of security firm Cryptography Research in San Francisco. 'I would guess that in five years, even 1,024 bits will be broken,' he says.

Moorcones adds, 'You often see 2,048-bit RSA keys used to protect 256-bit AES keys.'

Besides creating longer RSA keys, users are also turning to elliptic curve (EC) algorithms, based on the math used to describe curves, with security again increasing with the size of the key. EC can offer the same security with one-fourth the computational complexity of RSA, Moorcones says. However, EC encryption up to 109 bits has been broken, Kocher notes.

RSA remains popular with developers because implementation requires only multiplication routines, leading to simpler programming and higher throughput, Kocher says. Also, all the applicable patents have expired. For its part, EC is better when there are bandwidth or memory constraints, he adds.

The Quantum Leap

But this tidy world of cryptography may be seriously disrupted by the arrival of quantum computers.

'There has been tremendous progress in quantum computer technology during the last few years,' says Michele Mosca, deputy director of the Institute for Quantum Computing at the University of Waterloo in Ontario. Mosca notes that in the past 15 years, we have moved from playing with quantum bits to building quantum logic gates. At that rate, he thinks it's likely we will have a quantum computer within 20 years.

'It's a game-changer,' Mosca says, explaining that the change comes not from improvements in the computer's clock speed, but from an astronomical reduction in the number of steps needed to perform certain computations.

Basically, Mosca explains, a quantum computer should be able to use the properties of quantum mechanics to probe for patterns within a huge number without having to examine every digit in that number. Cracking both RSA and EC ciphers involves that very task -- finding patterns in huge numbers.

Mosca explains that with a conventional computer, finding a pattern for an EC cipher with N number of bits in the key would take a number of steps equal to 2 raised to one-half N. As an example, for 100 bits (a modest number), it would take 250 (1.125 quadrillion) steps.

With a quantum computer, it should take about 50 steps, he says, which means code-breaking would then be no more computationally demanding than the original encryption process.

With RSA, determining the number of steps needed for a solution through conventional computation is more complicated than with EC encryption, but the scale of the reduction with quantum computation should be similar, Mosca says.

The situation is less dire with symmetric encryption, Mosca explains. Breaking a symmetric code like AES is a matter of searching all possible key combinations for the one that works. With a 128-bit key, there are 2128 possible combinations. But thanks to a quantum computer's ability to probe large numbers, only the square root of the number of combinations needs to be examined -- in this case, 264. This is still a huge number, and AES should remain secure with increased key sizes, Mosca says.

Timing Issues

2048 Bit Rsa Encryption

When will quantum computing threaten the status quo? 'We don't know,' says Mosca. To many people, 20 years seems a long way off, but in the world of cybersecurity, it's right around the corner. 'Is that an acceptable risk? I don't think so. So we need to start figuring out what alternatives to deploy, since it takes many years to change the infrastructure,' Mosca says.

Rsa 2048 Encryption Virus

SafeNet's Moorcones disagrees. 'DES lasted for 30 years, and AES is good for another 20 or 30 years,' he says. Increases in computing power can be countered by changing keys more often -- with each new message, if necessary -- since many enterprises currently change their key only once every 90 days, he notes. Every key, of course, requires a fresh cracking effort, as any success with one key isn't applicable to the next.

When it comes to encryption, the rule of thumb is that 'you want your messages to provide 20 years or more of security, so you want any encryption that you use to remain strong 20 years from

How Long To Crack Rsa 2048 Encryption