Gentle Introduction To Cryptography
Part I — Welcome to the world of Alice, Bob and the incorrigible Oscar
What is Cryptography?
Cryptography, in spite of sounding so grandiloquent, tries to solve a very fundamental problem. How do you send a message from one point to another in a very public setting, with a confidence that the message will not be understood by anyone else.
It is important to note the public channel here. This implies that anybody listening can intercept the same message that is being sent. For example, in the figure above, Alice wants to send a message that she hopes only Bob will be able to understand. However since she is using a public channel(Email, Internet) there is a chance that anyone(Oscar in this case) can also get a copy of the same message and read it.
The goal of cryptography is to come up with methods of sending the message in such a way that even if it is intercepted by a third party, they will probably not be able to decipher the true meaning of the message.
Let us take an example. Consider the fact that Alice wants to send her age to Bob across the public domain.
She comes up with a strategy of concealing her real age by adding a value to it. Let us say Alice and Bob had met in private a week before and they had mutually decided that they were going to use a value 26 to add to any data they send across the public domain.
This value added to the original message is called a key(k). k is added to the original message(m) and the value actually sent across the public channel is the cipher(c)
Some Terminologies
message(m): Before the concealment process has begun, the data in plain text that Alice wants to send to Bob is called the message, denoted by m. In this case m is 24.
key(k): The value using which the message is concealed is known as the key, denoted by k. In this scenario k is 26.
encryption(e): The process by which the message(m)is concealed with the help of the key(k) is called encryption. In this example the process of encryption is addition.
cipher(c): This is the value obtained after the encryption is applied. For Alice, the cipher is 50.
Bob receives this encrypted message or the cipher. Now he knows that Alice has used the key to transform the value of the original message. So he applies an inverse logic to get the original message back from the cipher.
decryption(d): The process by which the receiver transforms the encrypted value or the cipher into the original plaintext message is decryption. For Bob, the decryption process is subtracting the key(26) from the cipher(50) and he gets the plaintext original message(24).
Oscar, the eavesdropper has been able to obtain the same message as Bob. He intercepts the value 50. Now he knows that this is not the original message. He also knows that something has been added to it, but he just does not know how much.
This is a very fundamental principle of cryptography. The encryption algorithm is made public. The fact that Alice has performed addition is known to all. However what stays secret is the key - how much did Alice add to her message? The job of the cryptanalysts(people who see how strong the encryption algorithms are) is to try and figure out the key, given that they know exactly how the encryption algorithm works.
So if you are ever designing an encryption-decryption algorithm, note that you will have to make your logic public. Your algorithm will be tested by cryptanalysts who will see if they can retrieve the key given that they know the ins and outs of your algorithm.
Encryption can thus be denoted as a function
e subscript k is the encryption function. It takes the plain text message as input and generates the ciphertext.
d subscript k is the decryption function which takes the ciphertext as input and divulges the message as output.
Finally lets talk about the formal definition of Cryptography. Mathematically Cryptography is defined by the 5-tuples —
(P,C,K,E,D)
- P = set of all possible plain texts(plain text space)
- C = set of all possible cipher texts(cipher text space)
- K = set of all possible keys
- E = set of all possible encryption algorithms. Its function form is the following, eᵏ : P X K → C where eᵏ belongs to E
- D = set of all possible decryption algorithms. Its function form can be expressed as dᵏ : C X K → P where dᵏ belongs to D
However this 5-tuple cryptosystem definition comes with a condition.
Any encryption algorithm must be coupled with a decryption algorithm such that they complement each other.
More formally, for any key k belonging to the key space K there exists an encryption algorithm eᵏ(which belongs to E) and a decryption algorithm dᵏ(belonging to D) such that
the decryption algorithm when applied on the encrypted message must bring back the same plain text message for all plain text messages in the plain text space.
Credits: IIT KGP Lectures Youtube
In the next part we will discuss some classic encryption techniques.
