4.1 Preliminaries

In this chapter, we are going to talk about how to achieve confidentiality, the first of the three security goals in the CIA triad. For this, we need encryption (and also decryption) functions. In order to be able to describe these functions precisely and to put them into the right context, we need some mathematical jargon.

Figure 4.1: A function f can be seen as a table in which every element in set X is assigned to precisely one element in set Y

First of all, the term function has a precise mathematical meaning. A function f is a mapping from a set X (called the domain of f) to some other set Y (called f’s co-domain) such that each element in X is mapped to precisely one element in Y , as illustrated in Figure 4.1. Symbolically, ones writes f : X → Y .

If x is an element of the set X, formally written as x ∈ X, and the function f maps x to an element y ∈ Y , then y is said to be the image of x, and x is said to be a preimage of y. Formally, we write y = f(x) in this situation.

Figure 4.2: Function f is a one-to-one function if each element in its co-domain Y is the image of at most one element of its domain X. In other words, each element in Y has at most one preimage in X

A function f : X → Y is called one-to-one if each element in the co-domain Y is the image of at most one element in the domain X, as shown in Figure 4.2. If a function is one-to-one and the images of all elements in X, the function’s domain, make up the entire set Y , then such a function is called a bijection. Note that the function shown in Figure 4.2 is not bijective, because there is an element in Y without a preimage in X. A bijective function is illustrated in Figure 4.3. In this case, an inverse function f−1 : Y → X can be formed which basically reverses the action of f.

Figure 4.3: Function f is a bijection when it is one-to-one and the images of all elements in X, the function’s domain, make up the entire set Y

The inverse function f−1 : Y → X maps each image y = f(x) ∈ Y onto its preimage x ∈ X. This works because, for a bijective function, preimages always exist and are unique in X.

Figure 4.4: An inverse function of f, written as f−1, reverses the action of f by mapping each element in Y to its preimage in X

In symmetric cryptography, we use certain functions f to encrypt things, and the inverse functions f−1 to decrypt things, that is, to reverse the encryption operation.