Introduction to Cryptography: The Proposal Story

Sarim-Katrina ring exchange

This is a story of two friends, Sarim and Katrina. Sarim lives near the river, and Katrina lives across the river. They send messages to each other by placing them inside a box and sending it across the river. Sarim loves Katrina and wants to propose to her by sending her the ring across the river. However, there is a problem. The pirates have attacked and are capturing all the boxes are unlocked. If a box is locked, they let it go.

Cryptograph

In a web-based online world, all messages or information we share over the internet are encrypted in some form, so that if anyone tries to hack them, they cannot be understood. Only we, the receiver of the messages, should be able to understand what they mean. Once these messages pass through the internet network (which is like a river), they reach their destination servers (just like the two ends of the river). Pirates are access points where anyone can connect (the internet providers with privileges) and can hook the network packets passing through their connections. All encryption versions of messages work in a similar fashion as in the above example about mailing a box.

For example, a very powerful encryption method called Encryption Protocol is used the giants of social world enterprise businesses, such as Facebook, Google, and so on. Encryption protocol (in the bigger picture) works in the following similar fashion.

• To establish secure communication with the end-user U, the server S creates and distributes a lock, $L_{s}$, which is similar to the padlocks used in the story between Sarim and Katrina. However, in this case, the end-user U already has the lock of the recipient, $L_{s}$ (the lock of Katrina), and can use it to lock the message before sending it to the server S. The lock, $L_{s}$, created by the server S is available to everyone, including the end-user U, and is used to secure the message during transmission between the two parties.
• The key, $K_{s}$, of the lock, $L_{s}$, is only there with the server S, which is hidden.
• In cryptography, $L_s$ is known as the public key and $K_s$ is called the private key of server S.
• The end-user U (in the above case, Sarim) uses $L_s$ to encrypt $M$ (Sarim’s ring) and make $M^*$ (ring in the box locked with $L_s$, as $L_s$ is available to him) using some mathematical operations (multiplications and divisions like arithmetic operations) which is quite easy to compute if you know $M$ and $L_{s}$ and send it over the internet. When the encrypted message $M^*$ reaches the server S (when the locked box containing the ring reaches Katrina), to decrypt $M$ from $M^*$, there is only one practical way to figure out what is M and that is by using $K_{s}$ (Katrina’s own key).
• It is possible to decrypt $M^*$ without using the private key, $K_{s}$, but the only way to do so is by trying all possible combinations of the key. This would be extremely impractical, as the number of possible combinations is exponential and would take, even for a supercomputer, millions of years to crack.

Exercise 1

A farmer wants to take a goat, a lion, and a bundle of grass across a river. The boat is small, so he can only carry one of them at a time. If he leaves the goat and grass alone together, the goat will eat the grass. If he leaves the lion and goat alone together, the lion will eat the goat. How can he bring all three safely across the river?

Exercise 2

We must carry four numbers $1$, $2$, $5$, and $10$ in a boat across a river. We can’t take more than two numbers, and the cost of traveling is equal to the larger of these two numbers. Once we’ve crossed the river, one number must be in our boat during the return trip, which defines the cost of this trip. What is the minimum price to carry all four digits from one river bank to the other?

Directions to look at the exercise

If we take $1$ and $2$ to cross the river first, then this one side trip will cost us $2$, and we can come back with $1$. Hence, this complete trip will cost us $3$. Further, we can take $5$ along with $1$ to cross the river and bring back $1$ with the current total cost of $6$. Then, we can take $1$ and $10$. This way, our total cost will be $3+6+10 = 19$.

But can we come up with an even better solution?

Exercise 3

Consider a scenario where we have two cubes (cube A and cube B). We can arrange them so that the front faces show the current day of the month. How can we use numbers on the front faces of the cubes so that they show the current date?

Note: We can’t represent day $7$ with a single cube with a side that says $7$ on it and the other cube hidden. We have to use both cubes all the time. So the $7^{th}$ day should be represented as $07$.