How Encryption Works – The history and the Future- Part:1
Encryption pervades all aspects of our lives today. We utilize it as a matter of course without even giving it a second thought. That book you ordered for your Kindle library last night, the message you sent your friend on WhatsApp this morning, the agreement you digitally signed just now – all these acts used encryption, or the science of Cryptography.
The desire to keep and hold secrets is ageless. Cryptography in the form of basic ciphers, has existed from the times of the Greek and Roman civilizations. These were rudimentary in nature and mainly designed to obfuscate messages so they didn’t make sense if they fell into the wrong hands. An early example called the Caesar Cipher basically shifted characters by 3 places (e.g. A = D, B = E, C = F, and so on). Such a cipher is called a substitution cipher. A modern example, called ROT13 is a modified version of the Caesar cipher that simply shifts characters by 13 places (instead of 3). ROT13 is interesting because there are 26 letters in the alphabet – and as a result, it is its own inverse. Basically, the same algorithm (shifting 13 places) can be used for both decryption and encryption ?
As ciphers go, however – ROT13 is an example of weak encryption and is rarely used where secrecy is valued.
An historically more recent example where encryption was used was when the German military used the Enigma machine to transmit and receive coded messages. The Enigma’s encryption key changed every day, making the messages hard to crack. The story of how Alan Turing famously cracked the code and helped the Allies win the 2nd world war is memorably captured in the Hollywood movie – “The Imitation Game”.
In more recent times, IBM created a block cipher back in 1973 to protect their customer data. It was later adopted by the United States as a national standard called DES (Data Encryption Standard). It was in wide use until 1997 when it was cracked and later replaced by AES (Advanced Encryption Standard). AES is still extant and widely used in all modern applications.
You can understand encryption in the simple form of multiplication. If you think of the message you are trying to encode as a string of digits, which you multiply using another long string of digits (think of this second number as your encryption key), their product is your encrypted message. Easy, right? In order to decrypt, you simply need to divide the encrypted product with the same encryption key, and voila! Your original message is back.
What we’ve described above is an example of Symmetric Key Encryption and so long as you have a long enough key, it actually works quite well. Both DES and AES are examples of Symmetric Key ciphers, although their algorithms are substantially more complex than the simple multiplication example I’ve used above. The reason the encryption key needs to be long is to make the decryption computationally expensive enough for an unauthorized actor who may use computing techniques to decipher the key.
AES-256 is arguably the most secure, practical implementation of a symmetric key cipher available today. The 256 denotes the length in bits of the key used. Longer keys obviously will make AES more secure, but they also make the task of encryption computationally more intensive. To crack a 256-bit key, an attacker would need to try 2256 different combinations. This number is 78 digits long and is several orders of magnitude greater than the number of atoms in the observable universe. So, for all practical purposes, AES-256 is virtually impenetrable. The 56-bit DES key which was cracked in 1997 can be cracked in less than a day using today’s computers. In comparison, AES would take billions of years to break (using current computing technology – but more on that later).
Types of Encryption
Ciphers like DES and AES are Symmetric key ciphers. This means that the key used to encrypt and decrypt are the same. This is fine for scenarios where the same system needs to decrypt at a later date, something it had encrypted earlier. In such a case, the key is kept a secret and is known only to the system.
However, what if a system needs to send an encrypted message to someone else? How would the other side decrypt it? Well, the other party would need the same key to decrypt the message, obviously. But therein lies the problem. How do you communicate the key securely to the other party? What would you do? Encrypt the key? And then how to you protect the key you encrypted the key with? We could go on forever.
In 1976, Stanford researchers Diffie and Hellman proposed a way which used 2 separate keys for the encryption and decryption operations. One key could be used only for encryption whereas the other could be used to decrypt what the former encrypted. Or vice versa. It was a revolutionary* concept and completely changed the encryption landscape.
We won’t get into the math of this right now – but in this model, 2 keys are assigned to each user. One is a private key and another a public key. The public key can be shared freely with the world, whereas the private key is held secret by the user.
When A wants to send a secure message to user B, she uses B’s public key to encrypt it. B in turn uses his private key to decrypt it. The message is secure because nobody other than B knows how to decrypt the package.
The public-private key pair can also be used for digital signing – i.e. to validate a sender. If B receives a message from A and he needs to be sure it is from A and nobody else, A uses her private key to sign the message. When B receives it, and is able to decode the signature using A’s public key, he can be a 100% sure the message is from A.
*In 1997, it was revealed that the British signals intelligence agency, had shown as early as 1969, how public-key cryptography could be achieved – but they did nothing about it.
So, in short, Symmetric encryption is useful when you have a single entity doing
both encryption and decryption. As an example, if you were to maintain a diary which you wished to keep private to yourself – you could make all your entries in a cipher that only you understood. That would be symmetric encryption. Symmetric key encryption is relatively fast computationally and doesn’t require very long keys to make it computationally defensible. As stated earlier, a 256 length key used with AES would take billions of years to break with currently extant computing power.
Asymmetric encryption is something you would use when you have at least 2 entities that need to exchange messages. In such a case transmitting a single “symmetric key” to the other party would be risk-prone because somebody might eavesdrop. Going back to the diary analogy, it would be like writing down instructions on how to decode your cipher. You would have to worry about the instructions falling in the wrong hands. Asymmetric key encryption therefore has 2 keys – one with which you encrypt; and another with which your recipient decrypts. Asymmetric key computation is also more intensive computationally and requires much longer keys to make it defensible. As an example a 1024 bit RSA key is only reasonably secure and can be cracked by a fairly determined hacker with sufficient computing power. A 2048 bit RSA key is predicted to be secure until 2030. The problem with making these keys longer is that the computation complexity increases, and the speed of encryption slows down drastically.
In our next blog, we discuss what kind of encryptions work for what purposes. You can access it here.