In today’s interconnected world, data encryption is the only thing that keeps us from spinning into complete and utter chaos. Born out of cryptography, encryption functions like the codes you used to pass notes with in elementary school. But there’s a difference—technically, codes are made up of letter, word, or phrase substitutions while ciphers use mathematical procedures (also known as algorithms) to transform messages.
Just like if you wrote a note with a cipher and only someone with the same cipher could decode it, encryption requires a key. Quality encryption always has one common feature: the algorithm (the process to encrypting something) can be public, but the key will always be private. Even the smartest hacker in the world can’t break into encrypted data if he or she doesn’t know the key.
In the simplest terms, keys are just numbers that plug into a certain algorithm, which can be analogous to an equation. For example, the algorithm can say to replace each letter with a certain number, then multiply each number by X. In this case, X would be the key in the algorithm. However, this would be an easily breakable cipher because all the resulting numbers would be divisible by the key. In this way, it’s possible for a huge number of people to use the same encryption algorithm but still keep their data safe due to different keys. This type of encryption—where the same algorithm and key is used both to encrypt and decrypt data—is known as private-key or symmetric key, and example implementations include Blowfish, IDEA, and AES. For thousands of years, all encryption algorithms were private-key.
For companies that use the private-key encryptions though, keeping keys secret is a constant source of heartache. According to the Atlantic, U.S. Navy ships had to store so many keys to communicate with other ships that paper records had to be loaded with forklifts in the 1980s.
In 1976, this burden led to the invention of a second type of encryption to rival private-key: public-key ciphers. By making the process “asymmetric,” the encrypting key can be different than the decrypting key. It took a year for the theory of public-key encryption to enter the real world, thanks to the efforts of three MIT mathematicians. The system they came up with, named RSA for the three inventors’ initials, was based in factoring.
Factoring, if you need a refresher from grade school, means breaking down a number into its prime factors. For example, the number 534,320 has a prime factorization of 2*2*2*2*5*6679. But the funny thing about factoring is how difficult it can be—even to mathematicians. A paper from IJRASET, a journal for applied science and engineering, says that the largest number ever factored is 155-digits long, and that even that took over 250 computers a total of 7 months. As Tom Davis, a math educator, points out, “If I ask you to multiply together 34,537 and 99,991 [both primes], it is a simple matter to punch those numbers into a calculator and 3,453,389,167. But the reverse problem is much harder.”
This is the mathematical equivalent of a check valve, and what RSA encryption is built on. You can easily multiply two prime numbers together, but to take the non-prime product and split it back up into the original two primes? Near impossible. In fact, it would take a computer 10176 times the lifetime of the universe to factor a 400 digit number.
In a nutshell, RSA encryption works when the private key is made up of two large prime numbers, 100 to 200 digits each—call them a and b. Multiplying those two numbers gets you a product, call that product N. N is half of your public key that you can share with anyone who wants to send you an encrypted message; it’s easy for you to calculate, but near impossible for anyone else. The other half of your public key is a number we’ll call M, which has to be relatively prime to both (a-1) and (b-1).
The encryption and decryption process for RSA is a little tedious, but easy for a computer to implement. The computer first converts data (emails, cell phone signals, anything) into numbers—0s and 1s, called bits. Then the data is converted according to this formula: [data]^M(mod N), where mod means the remainder when data^M is divided by N. The result of the mathematical formula is what gets sent to you, the holder of the private key. To decode the encrypted message, you have to calculate [encrypted message] ^[1(mod(a-1)(b-1))/M](mod N). With the aid of a computer for computation, you can easily decode the message and get to the original data.
As the world becomes ever more connected, data encryption–once a topic so unsexy it almost seemed taboo–has slowly turned into a hot subject that we’ve come to rely on more and more. With your phone spouting off your credit card number and with people logging into Facebook at every public computer they can find, data on us is everywhere and it’s valuable. Data encryption is how programmers can make sure that our data doesn’t fall into places where it wasn’t intended to go.