How Difficult is it to Break Encryption?
Source: Veronica Jackson, Andrew Konia, Clare Le
Whether it’s in discussions of public policy or discussions of best practices, encryption is all the rage right now. In fact, it’s been all the rage for centuries, but with revelations about the extent of domestic and international surveillance, the increasing frequency of data breaches, and a wonderful film about Alan Turing [http://www.imdb.com/title/tt2084970/?ref_=nv_sr_1], it’s fresh on everyone’s mind. The real question, though, is just how difficult is it to crack encryption?
As a computer science student turned public affairs consultant, I thought I had successfully evaded math, but to no avail. To properly demonstrate just how effective encryption is, you have to do just a bit. For this discussion, I’ll use the RSA algorithm, first developed in 1971 and still widely used today. I’ll discuss RSA in the context of sending a message.
The entire scheme is built upon the premise that it’s easy to multiply two large numbers together, but difficult to factor the large number that results back into the original two numbers. To demonstrate, it’s easy to multiply 23,719 and 41,843. You grab a calculator (or a pencil and paper, if you’re into that) and have the resulting 992,474,117 in a short amount of time. On the other hand, if I give you the number 992,474,117 and ask what two numbers I used to get it (ask you to factor it), you’re going to be busy for quite a while.
RSA is an example of public key cryptography. There are two keys: the public key that I share with everyone, and the private key that I keep a secret. The public key consists of the result of multiplying two large prime numbers together (above we used 992,474,117) and of a coprime number resulting from a simple equation involving the two original prime numbers. The private key is the two original prime numbers (above, 23,719 and 41,843).
The sender uses the public key to encrypt the message. The recipient uses the private key to decrypt it back into the original plaintext. I’m leaving out a lot of the mathematical details, but suffice it to say you need the private key to efficiently decode a message even with full knowledge of the algorithm.
To figure out the private key, you could just factor the public key and try the various combinations. But how long would that take? For any size number, the number of factor combinations is in the order of the size of the square root of that number. The square root of 992,747,117 �C our 9 digit number above �C is about 31,000. It wouldn’t take a modern computer very long to try 31,000 combinations. But, if the number of digits in the public key is 200 digits, the number of combinations is a 100 digit number. Assuming a modern computer could try 1 million combinations a second, it would take 3.17 x 1086 years �C or 317,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000 years �C to try every combination.
Teams of computer scientists have factored 768 bit (roughly 200 digits) RSA keys, but they’ve used special factorization algorithms and parallel computer set ups. Even then, it’s taken specialized knowledge, a lot of computing power, and months or even years to crack the keys. The point of the illustration is that breaking encryption keys is a mathematically daunting task.
To be sure, there are methods for defeating encryption schemes other than factorization. These usually involve improper key generation, not using padding schemes, and poor key choice. Regardless, the use of encryption makes unauthorized access to sensitive data very difficult. So what are you waiting for?
| }
|