18.4.4. Security Considerations of Discrete Log

And assuming that the key agreement has been achieved, the second problem that is addressed by the cryptography, the second core problem, I should stress here, it is not the case that secure communication is the only problem, the second core problem addressed by cryptography startup secure communication. So, the setting here is the following, we will assume that Sita and Ram has already executed the key agreement protocol over the internet, and they have agreed upon a common key. And now using this common key, we would require Sita and Ram to come, we would require some algorithms which are publicly known, according to which Sita can convert or encrypt her message into some garbled text into some garbage and communicate to Ram and Ram should be able to convert back those garbage or scrambled text back to the original contents using the same key, k which Sita has.

In this chunk, we introduce the concept of secure communication between two parties, Sita and Ram. They have already established a common key through a key agreement process. The main idea here is that they will use this common key to encrypt their messages, transforming plain text into an unreadable format (ciphertext) so that only Ram, who possesses the same key, can decrypt it back into its original form. The security consideration is crucial: if a third party (a malicious actor) is observing their communication and only has access to the encryption method (but not the key), they should not be able to decipher the messages being exchanged.

Think of Sita wanting to send a secret message to Ram. She writes a note, which represents plain text, and places it in a locked box (the encryption process) that only she and Ram have keys for. When she sends this locked box to Ram, nobody else can open it without the key, ensuring that the message remains confidential.

So, it turns out that there are two kinds of, two classes of cryptographic algorithms which we use. The first category is that of private key or symmetric key encryption. In the symmetric key encryption, the setting is the following. It will be ensured that a common key is already shared between Sita and Ram by some mechanism, say, by running a key agreement protocol and no one else apart from Sita and Ram knows the value of that key.

This chunk discusses the first type of encryption called symmetric key encryption. In this method, Sita and Ram share a common secret key which they will use for both encrypting and decrypting messages. The key must remain confidential, known only to these two parties. If any outsider knows the encryption algorithm yet lacks the key, they should not be able to access the encrypted message.

Imagine Sita and Ram have a diary with a lock requiring a key only they possess. When Sita writes a message in her diary and locks it, only Ram can unlock it with the same key. If someone else tries to read it without the key, it remains a secret.

How at the first place they can do that? Because everything will be now happening over a public channel because it is not the case that Sita and Ram knew beforehand in advance. It is like saying the following, if I want to do a transaction over the internet; Amazon may not be knowing well in advance that a person called Ashish Chowdhury, would like to do a transaction with Amazon. So, I will be doing my transaction at a runtime, how at the first place establishment of a secure key has taken place?

This chunk emphasizes the importance of establishing a common secret key without having prior contact, especially over public channels (like the internet). It addresses the challenge of secure key agreement and hints at solutions such as using key exchange protocols to accomplish this. Without a secure method to agree on a key, the encryption cannot be safely conducted.

Think of it as needing to set a private meeting with someone in a crowded area. You must find a way to signal each other without alerting bystanders about your plan, ensuring that only you both know where and when to meet.

So, it was a folklore belief that it is not possible to agree upon a common key by interacting over a public channel. But the Turing Award winner, Diffie and Hellman, proved this belief to be incorrect, by coming up with their seminal key exchange protocol. So, I would not be going into the full details of security proof and other details of the key exchange protocol, I will just try to give you the underlying idea.

Here, we refer to the breaking of the earlier belief about the impossibility of establishing a shared secret key over public channels. The Diffie-Hellman key exchange protocol demonstrated how this can be achieved using certain mathematical properties. It exploits asymmetrical problems where performing one operation is easy, but reversing it is computationally challenging, which forms the foundation of secure key exchange.

It’s like sharing a secret spice blend where you exchange ingredients without revealing the unique elements. Each person adds their own ingredients to the mix, allowing mutual agreement on a unique blend known only to them, while outsiders cannot replicate it.

So, the main idea used in their key exchange protocol is the following. They observed that there are plenty of tasks in this universe which are asymmetric, they are asymmetric in the sense, they are very easy to compute in one direction. That means, it is very easy to go from one state to another state but extremely difficult to reverse back the effect of that action.

This chunk highlights the key idea behind securing communications through asymmetric tasks. These tasks are straightforward to accomplish in one direction (like locking a box), but reversing them without the requisite knowledge (like having a key) is prohibitively difficult. This is utilized in the Diffie-Hellman method to securely create a common key.

Consider a puzzle that is easy to assemble (compute in one direction), but disassembling it back into its original parts requires considerable effort, akin to reassembling a puzzle you’ve already completed. This difficulty prevents unauthorized users from easily accessing what is locked away.

So, now we have to convert this whole process, this whole color exchanging idea into a concrete algorithm, mathematical algorithm and protocol.

In this final chunk, we describe how to formalize the previously discussed ideas into a concrete mathematical protocol that implements the key exchange algorithm. The key exchange between Sita and Ram must use specific mathematical steps to ensure security, which builds on the principles introduced earlier regarding secure communication over public channels.

This can be likened to developing a recipe based on a blend of ingredients (shared secret) where every step must be mapped out clearly to ensure that the final dish is safe for both tasters. It includes clear instructions that both parties can follow independently while maintaining the overall security.

--