Sebery J.Cryptography.An introduction to computer security.1989

2 BACKGROUND THEORY

This chapter covers main concepts and notions from Number Theory, Information Theory, and Complexity Theory that are frequently used in cryptology. Those readers with a strong mathematical background may wish to browse through this chapter or skip it completely.

2.1 Elements of Number Theory

Denote the set of natural numbers as N = f1;2; : : :g, the set of integers as Z = f: : : ; 1; 0; +1; : : :g, the set of rational numbers as Q, the set of irrational numbers as I and the set of real numbers as R.

2.1.1 Divisibility and the Euclid Algorithm

Let a be a nonzero integer. We can create the set f: : : ; 3a; 2a; 0; a; 2a; 3a; : : :g of all integers that are multiples of a. Any integer b from the set f: : : ; 3a;2a; 0; a; 2a; 3a; : : :g is divisible by a or a divides b without a remainder. This fact can be expressed in short as a j b. All integers which are divisible by other integers with no remainder are called composites. Divisibility has the following properties [367]:

1.If n j a and n j b, then n divides both (a+b) and (a b) (the set of multiples of n is closed under addition).

2.If a j b and b j c, then a divides c (transitivity).

3.For any nonzero b 2 Z, if n j a, then n divides ab.

4.For any nonzero b 2 Z, j a j j b j if a j b.

5.If a j b and b j a, then j a j=j b j (antisymmetry).

Integers di erent from 1, which are divisible by themselves and 1 only are called prime numbers or simply primes. The set of all primes is denoted by P.

12 2 BACKGROUND THEORY

The fundamental theorem of arithmetic states that any natural number can be uniquely factored into the product of primes, i.e. any n 2 N can be written as

n =	Y	pep	(2.1)

p2P

where ep is the exponent of the prime p (p 6= 1). The representation of n on the right side of Equation (2.1) is called its factorization and the primes p its factors.

Let a and b be two natural numbers. The least common multiple (lcm) of a and b is the smallest integer which is divisible by both a and b. How can we nd lcm(a; b)? Clearly, both a and b have their unique factorizations so a = Qi piai and b = Qi pibi . So if the factorizations of a and b are given, then their least common multiple can be computed as

lcm(a; b) =	Y	pimax (ai;bi)	(2.2)

i

where max (ai; bi) selects the maximum exponent for the given factor and i in-

dexes all factors of the integer. Consider a = 882 and b = 3465. Their factorizations are: a = 2 32 72 and b = 33 5 7 11. Thus lcm(a; b) = 2 33 5 72 11 = 145530.

The greatest common divisor (gcd) is another integer that expresses relation between two natural numbers a and b. The greatest common divisor of a and b is the largest integer which divides with no remainder both a and b. Therefore

The function min (ai; bi) produces the smallest exponent for the given factor.

gcd (a; b) = pimin (ai;bi)		(2.3)
i
Y
where a = Qi piai and b =	Qi pibi	and i indexes all factors of the integer.

For our two integers a = 882 and b = 3465, their greatest common divisor is

gcd (a; b) = 32 7 = 63. Both lcm and gcd work with an arbitrary number of
arguments and can be de ned recursively as follows:
lcm(a; b; c) = lcm(lcm(a; b); c) and gcd (a; b; c) = gcd (gcd (a; b); c)	(2.4)
Some of the properties of lcm and gcd are:

1.If there is an integer d 2 Z such that d j ni for all ni 2 N (i = 1; : : : ; k), then d j gcd (n1; : : : ; nk).

2.If n1 j m; : : : ; nk j m (m 2 Z), then lcm(n1; : : : ; nk) j m.

3.If d = gcd (n1; : : : ; nk) and bi = ndi , then gcd (b1; : : : ; bk) = 1.

Elements of Number Theory	13
4. lcm(a; b) gcd (a; b) = a b.
Two integers a and b are said to be coprime or relatively prime if	their
gcd (a; b) = 1. For example, a = 15 and b = 77 are coprime as	their

gcd (15; 77) = 1. Their lcm(15; 77) = 15 77.

How can we compute the greatest common divisor? Clearly, the gcd can be computed from factorizations of the integers. However, no one knows of an eÆcient factoring algorithm for large numbers. An excellent alternative not based on factoring is the well-known Euclid algorithm which is very eÆcient even for very large numbers.

Euclid algorithm { nds the greatest common divisor of two numbers

N .

E1. Initialize r0 = a and r1 = b.

E2. Compute the following sequence of equations:

r0 = q1r1 + r2 r1 = q2r2 + r3

.

.

.

a; b 2

(2.5)

rn 3 = qn 2rn 2 + rn 1 rn 2 = qn 1rn 1 + rn

until there is a step for which rn = 0 while rn 1 6= 0. E3. The greatest common divisor is equal to rn 1.

Theorem 1. Let the sequence rk be de ned as in (2.5), then rn 1 = gcd (a; b) when n is the rst index for which rn = 0.

Proof. Using induction, we will show that both rn 1 j gcd (a; b) and gcd (a; b) j rn 1, which implies that gcd (a; b) = rn 1.

Note that rn 1 j rn 2 as rn 2 = qn 1rn 1. Further, rn 1 j rn 3 as rn 3 = qn 2qn 1rn 1 + rn 1, and so forth. Finally, rn 1 j a and rn 1 j b. This implies that rn 1 j gcd (a; b) By de nition, gcd (a; b) divides both a and b and we conclude that gcd (a; b) j rn 1. ut

For example, assume we have two integers a = 882 and b = 3465. The Euclid algorithm will give the following equations:

14 2 BACKGROUND THEORY

3465 = 3 882 + 819

882 = 1 819 + 63

819 = 13 63 + 0

The remainder in the last equation is zero so the algorithm terminates and gcd (882; 3465) = 63.

The Euclid algorithm can be implemented as a computer program. A C language implementation of the algorithm is given below.

C implementation of Euclid algorithm

/* gcd finds the greatest common divisor for a and b */ long gcd(long a, long b)

f

long r0,r1,r2;

if(a==0 || b==0) return(0);

/* if one is zero output zero */

r0=a;

r1=b; /* initialisation */ r2=r0 % r1;

while(r2) f r0=r1; r1=r2;

r2=r0 % r1;

g

if(r1>0)

return(r1);

else

return(-r1);

g

Observe that we do not need to compute qi in the Euclid algorithm as we are looking for the last nonzero remainder.

The number of iterations n in the Euclid algorithm is proportional to log2 a where a is the larger integer from the pair. To justify this, it is enough to observe that the divisor in each iteration is bigger than or equal to 2. If the divisor were always 2, then the number of iterations would be exactly equal to log2 a. In other words, every iteration reduces the length of the remainder by at least one bit. How many steps are consumed by a single iteration ? Let our two integers

Elements of Number Theory

15

be a and b (a > b). To produce two integers q and r such that a = q b + r, we will need at most log2 a subtractions. This can be seen if we represent a and b in binary and carry out the division. A single subtraction takes at most log2 a bit operations. All together the Euclid algorithm needs O(log32 a) steps. This upper bound can be re ned to O(log22 a) after a more detailed analysis.

2.1.2 Primes and the Sieve of Eratosthenes

The fact that any integer can be uniquely represented by its prime factors emphasizes the importance of primes. Primes are \building blocks" for construction of all other integers. In cryptography most primes that are used are relatively large (typically more than a hundred decimal digits). One could ask whether it is possible to generate large primes and to decide whether an integer is prime. Another question could relate to the distribution of primes or how often they occur. The answer to the rst question was given by Euclid who showed that there are in nitely many primes. His proof is one of the gems of Number Theory [456].

Theorem 2. There are in nitely many primes.

Proof. (By contradiction) Assume that the number of primes is nite. Then there is the largest prime pmax. Consider the number N that is the product of all primes plus \1", i.e.

N = p1 pmax + 1:

The number N is bigger than pmax so it cannot be prime. Therefore N has to be composite. But this is impossible as any of the known primes p1; : : : ; pmax divides N leaving the remainder 1. Thus, there is a prime N larger then pmax. This is a contradiction which leads us to the conclusion that there are in nitely many primes. ut

Eratosthenes gave a method which generates all primes smaller than a given number N. His method is referred to as the sieve of Eratosthenes.

Sieve of Eratosthenes { determines all primes smaller than N.

S1. Create an initial set of all numbers NN = f2;3; 4; : : : ; N 1g smaller than

N.

16 2 BACKGROUND THEORY

S2. For all integers n < pN (that are still in the set NN ), remove all multiples of n from the set NN (leaving n itself in the set).

S3. The nal reduced set NN contains all primes smaller than N.

Let the upper limit N be 20. The set N20 = f2; 3; : : : ; 19g. We need to remove all multiples of 2,3,4 (n < p20). After removing all multiples of 2, the set is

f2; 3; 5; 7; 9; 11; 13; 15; 17;19g:

After removing all multiples of 3, the set reduces itself to f2; 3; 5; 7; 11; 13; 17; 19g:

The number 4 is not in the set so our sieving is completed. The set contains all primes smaller than 20.

Denote by (x) a function that gives the number of all primes contained in

the interval h1; xi. Alternatively, (x) is named the prime-counting function.
		x		x
Gauss claimed that (x) ln x . A better approximation of (x) ln x 1:08366
was given by Legendre. Hadamard and de la Vallee proved the prime number
theorem which says that
lim	(x) ln(x) = 1:		(2.6)
x!1	x

For more details, readers are referred to [367, 456].

A Mersenne number is an integer of the form Mp = 2p 1 where p is a prime. If a Mersenne number is itself prime then it is called a Mersenne prime. The number M3 = 23 1 = 7 is a Mersenne prime. Two consecutive primes separated by a single even number are called twin primes. Numbers 5 and 7 are twin primes.

2.1.3 Congruences

Modular arithmetic is often introduced in school as clock arithmetic. Fourteen hours after 3 p.m. is 5 a.m. the next morning. Simply,

14 + 3 5 (mod 12) or 14 + 3 = 1 12 + 5:

The formula a b mod N is a congruence and can be read as \a is congruent to b modulo N." It holds for integers a; b and N 6= 0 if and only if

a = b + kN for some integer k

Elements of Number Theory

17

or N j (a b).

If a b mod N, b is called a residue of a modulo N. In our example, 17 5 mod 12 or 5 is a residue of 17 modulo 12. A set fr1; r2; : : : ; rng is called a complete set of residues modulo N if for every integer a exactly one ri in the set satis es that a ri mod N. For any modulus N, f0; 1; : : : ; N 1g forms a complete set of residues modulo N. For N = 12 the set of complete residues is f0; 1; : : : ; 11g. We usually prefer to use integers from f0; : : : ; N 1g but sometimes integers in the set f12 (N 1); : : : ; 12 (N 1)g may be more useful (N is odd). Note that

	: : : 12 (mod 7) 5 (mod 7) 2 (mod 7) 9 (mod 7) : : :
Congruences have the following properties:
1.	If a A mod N and b B mod N, then a + b A + B mod N and
	a b A B mod N.
2.	a b mod N if and only if N j (a b).
3.	If ab ac mod N and gcd(a; N ) = 1, then b c mod N.

For example, the rule of \casting out nines" relies on adding all the digits of a number. If you add to 9, then ultimately the original number is divisible by 9. For instance, in order to determine whether 46909818 is divisible by 9 we sum the digits 4 + 6 + 9 + 9 + 8 + 1 + 8 = 45 and repeat this by summing 4 + 5 = 9 that indicates that the number is divisible by 9. The method relies on the fact that:

10	1	(mod 9)
102	10	(mod 9)	10	(mod 9) 1	(mod 9)
103	102	(mod 9) 10		(mod 9) 1	(mod 9)
	.
	.
	.

Any integer a is represented by the sequence of their successive decimal digits a = (am : : : a2a1a0)10 and a = am 10m + : : : + a2 102 + a1 10 + a0. So the integer,

a (am : : : a2a1a0)10 (mod 9)

am 10m + + a2 102 + a1 10 + a0 (mod 9)am + + a2 + a1 + a0 (mod 9):

18 2 BACKGROUND THEORY

The casting out nines rule illustrates the fact that the calculation of powers of an integer in congruences can be done very eÆciently.

Algorithm for fast exponentiation { computes ae mod N.

1.Find the binary representation of the exponent e. Let it be e = ek 2k + : : :+ e1 2 + e0 where ei are bits (ei 2 f0; 1g) for all i and ek = 1.

2.Initiate an accumulator accum (which will be used to store partial results)

to 1.

3.For i = 0; : : : ; k, multiply modulo N the contents of accum by aei and save a2 in a.

4.The result is stored in accum.

Observe that all the computations can be done \on the y." For every i, it is enough to square the power of a and modify the accumulator only if ei = 1. The modulus N can be represented as a string of ` = blog2 Nc + 1 bits. Exponentiation can be done using at most log2 e modular multiplications.

An example of the algorithm implementation in C is given below.

C implementation of fast exponentiation

/* fastexp returns a to the power of e modulo N */ long fastexp(long a, long e, long N)

f

long accum=1;

while(e) f

while(!(e%2)) f e/=2;

a=((a % N)*(a % N)) % N;

g

e--;

accum=((accum % N)*(a % N)) % N;

g

return(accum);

g

Suppose we wish to nd 75 mod 9. We rst note that 5 is e = 1 22 + 0 2 + 1 or e = (101)2 in binary. We start from the less signi cant (the rightmost) bit e0 of the exponent. As e0 = 1 so a = 7 and accum = 7. Since the second rightmost digit is zero, we square a but do not multiply it onto accum:

Elements of Number Theory

19

a = 72 = 49 4 (mod 9); and accum = 7:

Now, the left most digit of e is 1, so we square a and multiply it onto accum to get the result

a = 74 42 = 16 7 (mod 9); and accum = 72 = 4:

Note that if the fast exponential is used for very long integers (i.e. longer than the length of the long integer type in your C compiler), then special care must be taken to prevent over ow. Software packages such as MATHEMATICA and MAPLE provide multiprecision arithmetic that handles arbitrary long integers.

The inverse problem to that of nding powers of numbers in modular arithmetic is that of nding the discrete logarithm loga b (mod N). It means that we are looking for an integer e such that

ae b (mod N):

Unlike exponentiation, nding discrete logarithms is generally not an easy problem.

Consider an example in which we show how discrete logarithms may be

solved by applying exponentiation. Find two exponents e; f

such that the two

1

2

3

4

following congruences are satis ed: 3e

4 mod 13 and 2f

3 mod 13. Let

us compute 3

3, 3

9, 3

1, 3 3; : : : mod 13 which clearly has no

solution. On the other hand, for the congruence 2f 3 mod 13, we have the

following sequence:

21

2; 22 4; 23

8; 24

3;

25

6; 26 12; 27

11; 28

9;

29 5; 210 10; 211 7; 212

1

(mod 13):

So f = 4.

2.1.4 Computing Inverses in Congruences

Unlike ordinary integers, sometimes residues do have multiplicative inverses. So given a 2 f0; : : : ; N 1g there may be a unique x 2 f0; : : : ; N 1g such that,

ax 1 (mod N):

For example, 3 7 1 mod 10. Consider the following lemma.

20		2 BACKGROUND THEORY
Lemma 1. If gcd(a; N) = 1 then,
		6
a		i = a		j (mod N)
						6
for all numbers 0						i < j < N (i = j).

Proof. We proceed by contradiction. Assume a i a j mod N. This means that N j a(i j). This implies that i j 0 mod N as gcd(a; N ) = 1. Since i; j < N, we conclude that i = j which is a contradiction. tu

Corollary 1. If gcd(a; N ) = 1, then the collection of numbers a i mod N for i = 0; 1; : : : ; N 1 is a permutation of the numbers from 0 to N 1.

For example, if a = 3 and N = 7 then the congruence 3 i (mod 7) yields the
following sequence of numbers f0; 3; 6; 2; 5; 1; 4g for all successive i = 0; 1; : : : ; 6.
The sequence is just a permutation of the set f0; 1; 2; 3; 4; 5; 6g. This is not true
when gcd(a; N) = 1. For example, if a = 2 and N = 6 then for i = 0; 1; : : : ; 5
the congruence 26 i mod 6 generates all multiples of 2 smaller than 6.
Theorem 3. If	gcd(a; N) = 1, then the inverse element a 1, 0 < a 1 < N,
exists and
a a 1 1	(mod N):
Proof. From Corollary (1) we know that a i mod N is a		permutation of
0; 1; : : : ; N 1. Thus there must be an integer i such that a		i 1 mod N.
tu

A reduced set of residues is a subset of the complete set of residues that are relatively prime to N. For example, the complete set of residues modulo 10 is f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g, but of these only 1, 3, 7, 9 do not have a factor in common with 10. So the reduced set of residues modulo 10 is f1; 3;7; 9g. The elements that have been excluded to form the reduced set are the multiples of 2 and the multiples of 5. It is easy to see that for the modulus N = p q (p; q are di erent primes), the number of elements in the reduced set of residues is (p 1)(q 1).

The complete set of residues modulo 11 is f0; 1; 2; 3;. . . ;10g. Of these, only one element, 0, is removed to form the reduced set of residues, which has 10 elements. In general, for a prime modulus, the reduced set of residues contains (N 1) elements.