📂Number Theory

Encryption and Decryption in Cryptography

Buildup

Let’s imagine that Alice wants to convey a message to Bob. If there were only two people in the world, this message would be shared exclusively between them, with no reason to hide it. [ NOTE: In cryptography, Alice and Bob are names commonly used to represent $A$ and $B$, respectively. ] However, suppose there is a third person, Eve. Eve might not necessarily have bad intentions, but she is interested in the message Alice wants to convey to Bob. On the other hand, Alice wants only Bob to know the message she sends. [ NOTE: In cryptography, Eve refers to an ‘Eavesdropper’, represented by $E$, and plays the role of a passive attacker who only attempts to intercept messages. ] Therefore, Alice tries to send the message in a way that Eve cannot understand. This is a motif that anyone, as a human, can empathize with in ‘cryptography’.

When Alice transforms the message so only Bob can understand, it is called Encryption, and when Bob restores the transformed message to its original form, it is called Decryption. Moreover, the message before encryption is called the Plaintext, denoted by $\mathcal{M}$, and the collection of these messages is referred to as the set, whereas the message after encryption is called the Ciphertext, denoted by $\mathcal{C}$, and its collection is referred to as another set. Encryption and decryption are performed based on certain rules, and a Key is shared so that a third party, even if they know these rules, cannot decrypt the message. If the collection of such keys is called $\mathcal{K}$, then encryption and decryption can be mathematically represented as follows.

Definition ¹

1. The function $e : \mathcal{K} \times \mathcal{M} \to \mathcal{C}$ is called Encryption, and is also denoted as $e_{k} : \mathcal{M} \to \mathcal{C}$.
2. The function $d : \mathcal{K} \times \mathcal{C} \to \mathcal{M}$ is called Decryption, and is also denoted as $d_{k} : \mathcal{C} \to \mathcal{M}$.

However, $e_{k}$ and $d_{k}$ must be inverse functions of each other. In other words, for all $m \in \mathcal{M}$, $d_{k} \left( e_{k} ( m ) \right) = m$ must hold.

Yet, there are too many such corresponding relationships, and among them, a usable cipher must satisfy the following conditions.

A cryptographic system $( \mathcal{K} , \mathcal{M} , \mathcal{C} , e , d )$ is useful when it has the following properties:

• (i): For all $k \in \mathcal{K}$ and $m \in \mathcal{M}$, it must be easy to compute $e_{k} (m)$.
• (ii): For all $k \in \mathcal{K}$ and $c \in \mathcal{C}$, it must be easy to compute $d_{k} (c)$.
• (iii): Without knowing $k$, even if $c_{1} , \cdots , c_{n} \in \mathcal{C}$ is given, considering $d_{k} ( c_{1} ) , \cdots , d_{k} ( c_{n} )$ must be difficult to compute.

Explanation

In summary, a useful cryptographic system is one where only those qualified can easily see the message, and those who are not cannot see it. It would be best if there were no attackers intercepting the message, but even if there are, the content must not be revealed. Moreover, if encryption and decryption take too long even for the parties involved in communication, it might compromise too much of the functionality of communication despite having good security.