Home Computer Science



Table of Contents:
Background on functionsWhile 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 (11, oneway, trapdoor oneway)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}.
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 /. □
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) Oneway functions There are certain types of functions which play significant roles in cryptography. At the expense of rigor, an intuitive definition of a oneway function is given.
The concept of a oneway function is illustrated through the following examples. 1.14 Example {oneway 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,
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 squareandmultiply algorithm (Algorithm 2.143), whereas the process of finding x from f{x) is much harder. 1.15 Example (oneway 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.
Example 1.15 illustrates the concept of a trapdoor oneway 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 oneway functions. It remains to be rigorously established whether there actually are any (true) oneway 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 oneway functions is still unknown, the existence of trapdoor oneway functions is also unknown. However, there are a number of good candidates for oneway and trapdoor oneway functions. Many of these are discussed in this book, with emphasis given to those which are practical. Oneway and trapdoor oneway functions are the basis for publickey 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. PermutationsPermutations are functions which are often used in various cryptographic constructs.
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 ’ ) .
InvolutionsAnother 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. 
<<  CONTENTS  >> 

Related topics 