What’s the first thing that came to your mind when you read the title? How do you perceive the term ‘cryptography’? It has something to do with secrecy and hiding right! Anyway, cryptography is the art of protecting information by transforming it into an unreadable format. Only the people who have the secret key can decode this message. The process of transforming the information into something unreadable is called Encryption and the reverse process is called Decryption. Let’s say you have a message you want to send to your friend. The message to be encoded is called plaintext and the encrypted message is called ciphertext. The goal here is to find the most secure way of transforming the plaintext into ciphertext. How do we encrypt it? How do we make sure it remains safe even if someone happens to see it?
How does a crypto system work?
Let’s consider our friends Alice and Bob. They are geographically separated and Alice wants to send a secret message to Bob using mail because the phone might get intercepted. But she doesn’t trust the postal worker. The postal worker may be corrupt and he might read this message. How should Alice send a message to Bob without letting the postal worker read it? How would you do it? Just stop for a minute here and think about it before reading further! One way to do this would be that Bob should send an empty box to Alice. Alice would put her message inside that box and lock it. Now only Bob has a key to that box. So Alice would send this box via mail and nobody except Bob will be able to open it. This concept is called Public Key Cryptography. Bob’s open box is accessible to everyone. This is equivalent to public key. But once someone puts something inside the box, only Bob will be able to open it with his key. This is called private key.
It’s an ancient art.
The concept of cryptography is not new. It has been there for centuries and it has been evolving. Perhaps one of the oldest and simplest examples would be Caesar Cipher. It just takes each alphabet and shifts it by a certain amount. For example, let’s consider this sentence “OUR BASE IS UNDER ATTACK”. If you shift each alphabet by 3 to the right, then ‘O’ will become ‘R’, ‘U’ will become ‘X’ and so on. The ciphertext will be “RXU EDVH LV XQGHU DWWDFN”. This looks like jibberish right! You can transform it back to the original message by shifting each alphabet by 3 to the left.
Encryption using machines.
Caesar shift cipher is pretty straightforward and easy to break. Over time, newer techniques started coming in. People started using mechanical devices to achieve encryption. This made it hard for attackers to decode the information. A popular example would be Vigenère cipher. These machines gained huge popularity during World War II and people started developing complex electromechanical rotor machines to encrypt the data. One of the most popular crypto devices was the Enigma machine used by the German government. These devices were good but the drawback is that they were mechanical devices and the encryption algorithms were not inherently strong.
Earlier forms of cryptography were more dependent on the machines and the strength of an algorithm was not independent of them. Cryptographers started to look into mathematics for answers. It was in the beautiful world of numbers that they found the true answer! The strength of an encryption algorithm was completely controlled by the mathematical formulation and not by the limitations of any machine. Modern algorithms rely on the fact that factorizing a big number which is a product of two prime numbers is very difficult. A prime number is a number which is not divisible by any number other than 1 and itself. If you use numbers which are big enough, then factorizing it would take years.
Why do we need prime numbers? In fact, why do we need numbers at all?
Let’s consider the Alice-Bob example we discussed earlier. We had Bob’s open box, which is the public key, and the secret key to open the box, which is the private key. In modern crypto systems, public keys and private keys are large prime numbers. When we deal with text messages, the sender encrypts it using the receiver’s public key. This is equivalent to Alice putting the message in Bob’s box and locking it. Once it’s encrypted, only the receiver can decode it using his private key. Not even the sender can decode the message once it’s encrypted. This means that only Bob can open that box because he is the only one with the secret key.
If I ask you to factorize 15, you will quickly say 3×5=15. But if I ask you to factorize 143993, you will take a long time. The unique thing is that there is only one way to factorize a number which is a product of two primes. You can factorize 24 as 2×12 or 3×8 or 4×6. But there is only one way to factorize 15. Using composite numbers like 24 will be equivalent to having a lock to our house which can be opened by multiple keys. This is not exactly a good lock! The factors of 143993 are 311 and 463, both of which are prime numbers. In real life, very large prime numbers are used. If we use 128-bit key encryption, it would take several thousand trillion years to break it by brute force even if all the computers in the world were to work together in parallel.
Hackers are always looking for ways to break into a secure system and access the data. They try to decode encrypted data using Cryptanalysis. The realm of cryptography is too huge to be covered in a single blog post. I have tried to cover the essence of classical and modern cryptography here. I will continue this discussion in another post where I will delve deeper into number theory and the fundamental building blocks that determine the strength of a crypto system.