Background on functions
While this book is not a treatise on abstract mathematics, a familiarity with basic mathematical concepts will prove to be useful. One concept which is absolutely fundamental to cryptography is that of a function in the mathematical sense. A function is alternately referred to as a mapping or a transformation.
Functions (1-1, one-way, trapdoor one-way)
A set consists of distinct objects which are called elements of the set. For example, a set X might consist of the elements a, b, c, and this is denoted X = {a, b, c}.
- 1.2 Definition A function is defined by two sets X and Y and a rule f which assigns to each element in X precisely one element in Y. The set X is called the domain of the function and Y the codomain. If x is an element of X (usually written x e X) the image of x is the element in Y which the rule / associates with x; the image у of ж is denoted by у = f(x). Standard notation for a function / from set X to set У is /: X —> Y. If у e Y, then a preimage of у is an element x e X for which f(x) = y. The set of all elements in У which have at least one preimage is called the image of /, denoted Im(/).
- 1.3 Example (function) Consider the sets X = (a, b. c}, Y = {1,2,3,4}, and the rule /
from A to У defined as f(a) = 2, f(b) = 4, /(c) = 1. Figure 1.2 shows a schematic of the sets X, Y and the function /. The preimage of the element 2 is a. The image of / is {1,2,4}. □
Thinking of a function in terms of the schematic (sometimes called a functional diagram) given in Figure 1.2, each element in the domain X has precisely one arrowed line originating from it. Each element in the codomain У can have any number of arrowed lines incident to it (including zero lines).
Figure 1.2: A function f from a set X of three elements to a set Y of four elements.
Often only the domain X and the rule / are given and the codomain is assumed to be the image of /. This point is illustrated with two examples.
1.4 Example (function) Take X = {1,2,3,... ,10} and let f be the rule that for each x e X, f(x) = r_{x}, where r_{x} is the remainder when x^{2} is divided by 11. Explicitly then
The image of / is the set У = {1,3,4,5,9}. □
1.5 Example (function) Take X = (1,2,3,... , Ю^{50}} and let / be the rule f(x) = r_{x}, where
r_{x} is the remainder when x^{2} is divided by Ю^{50} + 1 for all a: e X. Here it is not feasible to write down / explicitly as in Example 1.4, but nonetheless the function is completely specified by the domain and the mathematical description of the rule /. □
- (i) 1-1 functions
- 1.6 Definition A function (or transformation) is 1 - 1 (one-to-one) if each element in the codomain Y is the image of at most one element in the domain X.
- 1.7 Definition A function (or transformation) is onto if each element in the codomain У is the image of at least one element in the domain. Equivalently, a function /: X —» Y is onto if Im(/) = Y.
- 1.8 Definition If a function /: X —» Y is 1 -1 and Im(/) = Y, then / is called a bijection.
- 1.9 Fact If /: X —> Y is 1 - 1 then /: X —» Inr(/) is a bijection. In particular, if /: X —» Y is 1 - 1, and X and Y are finite sets of the same size, then / is a bijection.
In terms of the schematic representation, if / is a bijection, then each element in Y has exactly one arrowed line incident with it. The functions described in Examples 1.3 and 1.4 are not bijections. In Example 1.3 the element 3 is not the image of any element in the domain. In Example 1.4 each element in the codomain has two preimages.
1.10 Definition If / is a bijection from X to Y then it is a simple matter to define a bijection g from У to A as follows: for each у € Y define g(y) = x where x € X and f(x) = y. This function g obtained from / is called the inverse function of / and is denoted by g = / ^{L}.
Figure 1.3: A bijection f and its inverse g = f ^{1} ■
1.11 Example (inverse function) Let X = {a, b. c, d, e}, and Y = {1,2,3,4,5}, and consider
the rule / given by the arrowed edges in Figure 1.3. / is a bijection and its inverse g is formed simply by reversing the arrows on the edges. The domain of g is Y and the codomain is*. □
Note that if / is a bijection, then so is /^{-1}. In cryptography bijections are used as the tool for encrypting messages and the inverse transformations are used to decrypt. This will be made clearer in §1.4 when some basic terminology is introduced. Notice that if the transformations were not bijections then it would not be possible to always decrypt to a unique message.
(ii) One-way functions
There are certain types of functions which play significant roles in cryptography. At the expense of rigor, an intuitive definition of a one-way function is given.
- 1.12 Definition A function / from a set A to a set У is called a one-way function if f(x) is “easy” to compute for all x e A but for “essentially all” elements у e Im(/) it is “computationally infeasible” to find any x e X such that f(x) = y.
- 1.13 Note (clarification of terms in Definition 1.12)
- (i) A rigorous definition of the terms “easy” and “computationally infeasible” is necessary but would detract from the simple idea that is being conveyed. For the purpose of this chapter, the intuitive meaning will suffice.
- (ii) The phrase “for essentially all elements in У” refers to the fact that there are a few values у € У for which it is easy to find an.г e A such that у = fix). For example, one may compute у = f{x) for a small number of x values and then for these, the inverse is known by table look-up. An alternate way to describe this property of a one-way function is the following: for a random у e Im(/) it is computationally infeasible to find any x e X such that f{x) = y.
The concept of a one-way function is illustrated through the following examples.
1.14 Example {one-way function) Таке X = {1,2.3,... , 16} and define/(x) = r_{x} for all x e X where r_{x} is the remainder when 3* is divided by 17. Explicitly,
X |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
fix) |
3 |
9 |
10 |
13 |
5 |
15 |
11 |
16 |
14 |
8 |
7 |
4 |
12 |
2 |
6 |
1 |
Given a number between 1 and 16, it is relatively easy to find the image of it under /. However, given a number such as 7, without having the table in front of you, it is harder to find
x given that f(x) = 7. Of course, if the number you are given is 3 then it is clear that x = 1 is what you need; but for most of the elements in the codomain it is not that easy. □
One must keep in mind that this is an example which uses very small numbers; the important point here is that there is a difference in the amount of work to compute f(x) and the amount of work to find x given fix). Even for very large numbers, f{x) can be computed efficiently using the repeated square-and-multiply algorithm (Algorithm 2.143), whereas the process of finding x from f{x) is much harder.
1.15 Example (one-way function) A prime number is a positive integer greater than 1 whose
only positive integer divisors are 1 and itself. Select primes p = 48611, q = 53993, form n = pq = 2624653723, and let X = {1,2,3,... , n — 1}. Define a function / on X by f(x) = r_{x} for each x e X, where r_{x} is the remainder when x^{3} is divided by n. For instance, /(2489991) = 1981394214 since 2489991^{3} = 5881949859 • n + 1981394214. Computing f{x) is a relatively simple thing to do, but to reverse the procedure is much more difficult; that is, given a remainder to find the value x which was originally cubed (raised to the thud power). This procedure is referred to as the computation of a modular cube root with modulus n. If the factors of n are unknown and large, this is a difficult problem; however, if the factors p and q of n are known then there is an efficient algorithm for computing modular cube roots. (See §8.2.2(i) for details.) □
Example 1.15 leads one to consider another type of function which will prove to be fundamental in later developments.
- (iii) Trapdoor one-way functions
- 1.16 Definition A trapdoor one-way function is a one-way function /: X —> Y with the additional property that given some extra information (called the trapdoor information) it becomes feasible to find for any given у e Im(/), an x e X such that f(x) = y.
Example 1.15 illustrates the concept of a trapdoor one-way function. With the additional information of the factors of n = 2624653723 (namely, p = 48611 and q = 53993, each of which is five decimal digits long) it becomes much easier to invert the function. The factors of 2624653723 are large enough that finding them by hand computation would be difficult. Of course, any reasonable computer program could find the factors relatively quickly. If, on the other hand, one selects p and q to be very large distinct prime numbers (each having about 100 decimal digits) then, by today’s standards, it is a difficult problem, even with the most powerful computers, to deduce p and q simply from n. This is the well- known integer factorization problem (see §3.2) and a source of many trapdoor one-way functions.
It remains to be rigorously established whether there actually are any (true) one-way functions. That is to say, no one has yet definitively proved the existence of such functions under reasonable (and rigorous) definitions of “easy” and “computationally infeasible”. Since the existence of one-way functions is still unknown, the existence of trapdoor one-way functions is also unknown. However, there are a number of good candidates for one-way and trapdoor one-way functions. Many of these are discussed in this book, with emphasis given to those which are practical.
One-way and trapdoor one-way functions are the basis for public-key cryptography (discussed in §1.8). The importance of these concepts will become clearer when their application to cryptographic techniques is considered. It will be worthwhile to keep the abstract concepts of this section in mind as concrete methods are presented.
Permutations
Permutations are functions which are often used in various cryptographic constructs.
- 1.17 Definition Let S be a finite set of elements. A permutation p on S is a Injection (Definition 1.8) from S to itself (i.e., p: S —> S).
- 1.18 Example (permutation) Let S = {1,2,3,4,5}. A permutation p: S —> S is defined as follows:
A permutation can be described in various ways. It can be displayed as above or as an array:
where the top row in the array is the domain and the bottom row is the image under the mapping p. Of course, other representations are possible. □
Since permutations are bijections, they have inverses. If a permutation is written as an array (see 1.1), its diverse is easily found by interchanging the rows in the array and reordering the elements in the new top row if desired (the bottom row would have to be reordered
( 1 2 3 4 5
’ ) .
- o 4 1 о 2. J
- 1.19 Example (permutation) Let X be the set of integers {0,1,2,... , pq - 1} where p and q are distinct large primes (for example, p and q are each about 100 decimal digits long), and suppose that neitherp-1 nor q-1 is divisible by 3. Then the function p(x) = r_{x}, where r_{x }is the remainder when a;^{3} is divided by pq, can be shown to be a permutation. Determining the inverse permutation is computationally infeasible by today’s standards unless p and q are known (cf. Example 1.15). □
Involutions
Another type of function which will be referred to in §1.5.3 is an involution. Involutions have the property that they are their own inverses.
1.20 Definition Let S be a finite set and let / be a bijection from S to S (i.e., /: S —> 5). The function / is called an involution if / = f~^{l}. An equivalent way of stating this is
f{f(x)) = x for all x € S.
1.21 Example (involution) Figure 1.4 is an example of an involution. In the diagram of an
involution, note that if j is the image of i then i is the image of j. □
Figure 1.4: An involution on a set S of 5 elements.