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

Elements of Number Theory

21

Modulus

Reduced set

'(N)

N = p

(p prime)

f1; 2; : : : ; p 1 g

p 1

N = p2

(p prime)

f1; 2; : : : ; p 1; p + 1; : : :,

p(p 1)

2p 1; 2p + 1; : : : ; p2 1 g

.

.

.

.

.

.

.

.

.

N = pr

(p prime)

f1; 2; : : : ; pr

1 g

(pr

1)

(pr 1

1)

{ multiples of p < pr

= pr 1(p 1)

6

f

g

N = pq

(p, q prime, p = q)

1; 2; : : : ; pq

1

(pq

1)

(q

1)

(p

1)

{ multiples of p

= (p 1)(q 1)

{ multiples of q

.

.

.

.

.

.

.

.

.

t ei

t

ei 1

N =

i=1 pi

; (pi prime)

i=1 pi

(pi

1)

Q

Q

Table 2.1. Euler's totient function

The reduced set of residues modulo 27 = 33 is:

f1; 2; 4; 5; 7; 8; 10; 11; 13; 14; 16; 17; 19; 20; 22; 23;25; 26g

which has 18 elements. The number 18 is obtained from the observation that the reduced set of residues modulo 3 has 2 elements, 1 and 2, and all the elements are either 3i + 1 or 3i + 2 for i = 0; 1; : : : ; 8. In general for a prime power Nr, the reduced set of residues has (N 1) Nr 1 elements.

The Euler totient function '(N) is the number of elements in the reduced set of residues. This is tabulated in Table 2.1.

Theorem 4. (Euler's Theorem) Let gcd(a; N) = 1 then
a'(N) (mod N) = 1:	(2.7)

Proof. Let R = fr1; : : : ; r'(N)g be a reduced set of residues modulo N. Then far1; ar2; : : : ; ar'(N)g is a permutation of R for any a = 1; 2; : : : ; N 1. Thus,

'(N)		'(N)		'(N)
Y	ri =	Y	ari a'(N)	Y	ri	(mod N):
i=1		i=1		i=1

22 2 BACKGROUND THEORY

Hence a'(N) 1 (mod N). tu

Euler's Theorem is also called the generalization of Fermat's theorem.

Theorem 5. (Fermat's	Little Theorem) Let p be a prime and suppose the
gcd(a; p) = 1 then
ap 1 1 (mod p)	(2.8)

To understand the security of many public-key algorithms, we need to study how eÆciently we can nd inverses in modular arithmetic. Algorithms for nding inverses a 1 mod N:

{Search through 1; : : : ; N 1 until an a 1 is found such that a a 1 mod N = 1. This algorithm is not feasible when N is large.

{Compute

a 1 a'(N) 1 (mod N)

if '(N) is known.

{ Use the Euclid algorithm if '(N) is not known; see Formula (2.5).

Consider the third algorithm from the above list. Recall Formula (2.5), which describes the Euclid algorithm. We are going to show how to adjust it to nd inverses. It starts with the following substitution: r0 = N and r1 = a where N is the modulus and a is the number for which the inverse is sought. The rst step is r0 = q1r1 + r2. The equation can be rewritten as

r2 = r0 q1r1:

As r0 = N so r2 q1r1 mod N. We store the coeÆcient against r1 in x1 = q1 so r2 = x1r1. The second step r1 = q2r2 + r3 can be presented as

r3 = r1 q2r2 = r1 q2x1r1 = (1 q2x1)r1 = x2r1 where x2 = (1 q2x1). The third step proceeds as

r4 = r2 q3r3 = x1r1 q3x2r1 = x3r1

and x3 = (x1 q3x2). In general, the ith step is ri+1 = ri 1 qiri = xir1

where xi = (xi 2 qixi 1). The computations end when there is a step n 1 for which rn = 0 and rn 1 = 1. The equation for the previous step is

Elements of Number Theory

23

rn 1 = rn 3 qn 2rn 2 = xn 2r1 = 1:

The value of xn 2 is the inverse of a = r1.

To illustrate the algorithm, consider the following example in which we nd

the inverse of 5 modulo 23.
3	= 23 4		5 4 5		(mod 23)
2 = 5		1	3 = 5	1( 4	5) = 5 5
1	= 3	1	2 = ( 4	5) 1(5 5) = 9 5:

So 1 9 5 (mod 23) and 9 14 (mod 23) is the inverse.

C implementation of the Euclid algorithm for nding inverses

/* inverse returns an element x such that */ /* a*x=1 mod N */

long inverse(long N, long a)

f

long r0,r1,r2,q1,q2,x0,x1,x2;

r0=N; r1=a;

x0=1; /* initialisation */ q1=r0/r1; r2=r0 % r1; x1=-q1;

while(r2)f

r0=r1; r1=r2; q1=r0/r1; r2=r0 % r1; x2=x0-q1*x1;

x0=x1; x1=x2;

g

if(r1!=1)f

printf("NO INVERSE \n"); exit(1);

g

if(x0>0) return(x0); return(N+x0);

g

Algorithms for nding inverses can be used to solve congruences	(2.9)
ax b (mod N):

24 2 BACKGROUND THEORY

To nd an integer x which satis es Congruence (2.9), rst compute the inverse of a, i.e.

ay 1	(mod N)
and x yb	(mod N). For instance, to solve 5x 9 (mod 23), we rst solve
5y 1 (mod 23) getting y = 14 and thus x = 14			9 11 (mod 23).
Theorem 6. If d = gcd(a; N ) and d j b, then the congruence ax b				(mod N)
has d solutions
	b	N
xi+1 d x0		+ i d (mod N)		(2.10)
for i = 0; 1; : : : ; d 1 and x0 is the solution to
a		N
dx 1	(mod	d )
otherwise it has no solution.

Proof. If ax b mod N has a solution in [1; N 1], then N j (ax b). The fact
that d j N and d j	a implies that d j b. Hence the congruence
a	N
dx 1 (mod	d )

has a unique solution x0 in [1; Nd 1]. Thus x1 db x0 mod Nd is a solution of

a b		N
dx d	(mod	d )

therefore			a	x1			b	= k	N	for some k. Multiplication by d gives
			d				d		d
	ax1 b = kN
so x1 is a solution of ax										b mod N. But any x 2 f1; : : : ; N 1g such that
x		x1 mod			N	is also a solution. So all solutions are:
					d
	xi+1 = db x0 + iNd for i = 1; : : : ; d 1:
	ut
	Suppose we wish to solve 9x 6 mod 12. We denote d = gcd(9;12) = 3 and
3 divides 6 so there are three solutions. We rst solve:
	3x1 = 2				(mod 4)

by nding the solution to :

Elements of Number Theory

25

3x0 = 1 (mod 4)

Now x0 = 3 and so x1 = 3 2 = 6 2 mod 4. Thus the three solutions are: xi+1 = 2 + i 4; i = 0; 1; and 2

That is, x = 2, 6 and 10.

Diophantine equations are equations with solutions in the set of integers or natural numbers. Congruences have an intimate relation with Diophantine equations. The congruence a x b mod N has its Diophantine counterpart

a x = k N + b:

To solve it, it is enough to show pairs (x; k) which satisfy the equation for the given (a; b).

2.1.5 Legendre and Jacobi Symbols
Consider the following quadratic congruence
x2 a (mod p)	(2.11)

where p is a prime integer. Note that squaring takes two values x and x and produces the same result x2. Therefore the quadratic congruence (2.11) may have one, two or no solutions. More precisely, the quadratic congruence may have

0 (mod p),

2.two solutions if a is a quadratic residue modulo p,

3.no solution if a is a quadratic nonresidue modulo p.1. one solution if a

The Legendre symbol is de ned as follows:

p		>	0	if a = 0;
a		= 8	1	if a quadratic residue modulo p;	(2.12)
		>
		:
		< 1 if a quadratic nonresidue modulo p:
Below we list some properties of the Legendre symbol.

{ The value of the Legendre symbol can be computed from the congruence

a		1
p	a2 (p 1) (mod p):
It is easy to check that the congruence holds for a = 0 (or p						j a). Note
	6
that for a = 0 Fermat's Little Theorem says that a(p 1)					1	(mod p) so

	26	2 BACKGROUND THEORY
		a(p 1)=2 (mod p) is 1. Now we show that a is a quadratic residue modulo
		p if and only if a(p 1)=2 = 1. ()) Clearly if a is a quadratic residue, then
		there is a number x such that x2 = a. According to Fermat's Little Theorem,
		we have a(p 1)=2 = x(p 1) = 1. (() Assume that there is a number a for
		which a(p 1)=2 = 1. This means that a(p 1)=4 = 1 or in other words there
		is a number x = a1=2 such that x(p 1)=2 = 1. The case when the Legendre
		symbol is equal to 1 follows as there are three possible values it can take.
	{ The Legendre symbol is multiplicative or		ab		=		a		b		. To see that this
			p				p		p
		holds, consider the following sequence of congruences:
		ab	a			b
		p = (ab)(p 1)=2 = a(p 1)=2b(p 1)=2 = p			p :

{If a b (mod p), then ap = pb .

{The sets of nonresidues and residues modulo p are of the same cardinality.

The Jacobi symbol is a generalization of the Legendre symbol for the case when the quadratic congruence is considered for an arbitrary modulus N (N need not be a prime). The Jacobi symbol for a given quadratic congruence x2 = a

(mod N), where N = p1

pr, is de ned as

a

r

a

=

N

i=1

pi

Y

a

where N is a composite integer, pi are factors of N and

pi

are Legendre

symbols primes pi.

Jacobi symbols are easy to compute using exponentiation when the factors of N are known. If factors of N are not known, then Jacobi symbols can still be computed eÆciently using the Euclid algorithm with O(log22 N) steps (for details see [102]).

2.1.6 Chinese Remainder Theorem

Solving congruences for moduli which are composite is equivalent to the solution of systems of congruences. If the congruence is ax b mod p q, then we solve two congruences ax b mod p, ax b mod q and combine the results. The Chinese Remainder Theorem (CRT) states how we can solve a single congruence modulo N by solving the system of congruences for factors of N.

Elements of Number Theory

27

Theorem 7. Let p1; : : : ; pr be pairwise coprime and f(x) an arbitrary congruence. Further let N = p1 : : : pr. Then,

f (x) (mod N) 0 i f (x) (mod pi) 0 for i = 1; : : : ; r.

Proof. The pi are pairwise coprime so if f (x) = kN = k p1 : : : pr ) pi j f (x)

for any i. tu

Theorem 8. (Chinese Remainder Theorem) Let p1; : : : ; pr be pairwise coprime, where N = p1 : : : pr. Then the system of congruences

x xi (mod pi); i = 1; : : : ; r

has a common solution x in f0; : : : ; N 1g.

Proof. For each i, gcd(pi; Npi ) = 1. Therefore there exists a yi such that:

N
pi yi 1	(mod pi)
and
N
pi yi 0	(mod pj )

for all j = i and pj

N

. Let x

r

N

xiyi mod N. Then x is a solution of

j pi

i=1 pi

6

N

xi = x mod pi because, x =

P

xi mod pi.

tu

pi

xiyi

For example, suppose we wish to solve two congruences x

1 mod 5 and

x 10 mod 11 to nd a solution modulo 55. First nd the inverse of 11 modulo

5

55

1

(mod 5) ) y1 = 1:

5 y1 1

(mod 5) or 11y1

Next, nd the inverse of 5 modulo 11

55

1

(mod 11) ) y2 = 9;

11 y2 1

(mod 11) or 5y2

Thus x =

55

x1y1 +

55

x2y2 11 1 1 + 5 10 9 21 mod 55.

5

11

CRT algorithm { generates the solution for x mod N from xi mod pi where

N = p1 : : : pr ; i = 1; : : : ; r.

28 2 BACKGROUND THEORY

1.Precomputation: For all i = 1; : : : ; r, nd all inverses yi of Npi modulo pi and store them as the vector (y1; : : : ; yr).

2.Composition: For the given vector of residues x1; : : : ; xr, create the solution

x Pi=1 pi xiyi mod N.

r N

The CRT asserts the equivalence of the representation of integers in modular arithmetic,i.e. x mod N is equivalent to the vector representation (x1; : : : ; xr). From a cryptographic point of view, both the recovery procedure of x from its vector (x1; : : : ; xr) and the reverse operation (i.e. nding the vector from the integer x) are very eÆcient only if the factors of N are known (see Knuth [283]).

2.2 Algebraic Structures in Computing

Cryptography exploits a variety of algebraic structures. Most computations are done in nite groups, rings, and elds. In this section, we introduce basic algebraic concepts and explore properties of basic algebraic structures.

2.2.1 Sets and Operations

Computing always involves passive entities (numbers) and active entities (operations). Algebra provides a well-developed theory that deals with such objects. An algebraic structure is de ned as the collection of a set with one or more

operations which can be performed on elements of the set. Let S be a set of
elements and be an operation. The operation acts on a pair of elements
a; b	2 S and assigns an element c = a				b 2 S. Note that in general, the order
of elements is important as a			b = b		a.
			6
A group G = hS; i is an algebraic structure that satis es the following
conditions:
G1.	For any two elements a; b	2 S, c = a b 2 S. This property is called closure.
G2.	For any three elements a; b; c 2 S, the group operation is associative, i.e.
	(a b) c = a (b c):
G3.	There is a neutral (identity) element e 2 S such that
	8a2S a e = e a = a:

has its inverse, i.e.

Algebraic Structures in Computing

29

G4. Each element a 2 S

8a2S 9a 12S a a 1 = a 1 a = e:

An Abelian group is a group whose group operation is commutative: G5. For any two a; b 2 S

a b = b a:

The following structures are examples of groups.

{The set of integers with the addition as the group operation hZ; +i is a group. The identity element is zero and the inverse element of a 2 Z is a 2 Z. The group is Abelian as 8a;b2Z a + b = b + a. The group is in nite.

{The set of nonzero rationals R under multiplication creates an Abelian group hR n f0g; i. The identity element is 1 and the inverse of a is 1a. The group is in nite.

{The set ZN = f0; 1; : : : ; N 1g with addition modulo N is an Abelian group ZN = hZN ; +i. The identity element is 0. The inverse of a is (N a). The group is nite.

{The group Z2 = hZ2; +i has a special practical signi cance. It has two elements only. The group addition is equivalent to the binary Exclusive-Or operation .

{The set ZN = f1; 2; : : : ; N 1g with multiplication, i.e. ZN = hZN ; i is an Abelian group if N is prime. The identity element is 1. The inverse element

of a is a 1 such that a a 1 1 (mod N). The group is nite.

The order of a nite group is the number of elements in the group. A group G1 = hS1; i is a subgroup of the group G = hS; i if S1 S.

Theorem 9. (Lagrange theorem) The order of a subgroup H of a nite group G divides the order of G.

Proof. The idea of the proof is to show that there is an equivalence relation that partitions the elements of G into disjoint subsets (cosets). The relation is

de ned as a b if and only if a 1 b 2 H. We now verify that the relation is re exive, symmetric, and transitive. The relation is clearly re exive as a a means that a 1 a = e 2 H. The relation is symmetric as a b implies b a.

This is true as the following sequence of implications holds: a b is equivalent to a 1 b 2 H. This implies that (a 1 b) 1 2 H and b 1 a 2 H that is

30 2 BACKGROUND THEORY

equivalent to b a. The relation is also transitive (we need to check that a b

1

1

1

2

2

and b

c implies a

c). This means that a 1

b

H and b 1

c

H. So

(a

b)

(b

c) = a

c 2

H that is equivalent to a c.

As

is an equivalence relation, it partitions elements of G into disjoint

cosets each having the number of elements equal to the order of H. Since each

element of G is in some coset, so the order of H divides the order of G. tu

A cyclic group is a group whose elements are generated by a single element

g (also called the generator of the group).

Consider the multiplicative group Z7 . Note that the identity element 1 2 Z7

generates the trivial group hf1g; i. The element 6 1

(mod 7) generates

1

2

hf

g

i 3

a bigger subgroup namely

1; 6 ;

. The element 2 generates the following

subgroup: 2

= 2, 2

= 2

2 = 4, 2 = 2 2

2 = 8

1

(mod 7) of Z7 .

Obviously we can rewrite 23

20

(mod 7). The subgroup generated by 2 is

hf1; 2; 4g;i. The element 3 yields the following:

31

= 3

32

= 3

3

2

(mod 7)

33

= 3

3

3

6

(mod 7)

34

= 3

3

3

3

4

(mod 7)

35

= 3

3

3

3

3

5

(mod 7)

36

= 3 3 3 3 3

3 1

(mod 7)

The element 3 generates the whole group Z7 . Powers, of 4 are: 41

= 4, 42

2

(mod 7) and 43

1

2

hf

g i

3

1

(mod 7). The subgroup

1; 2; 4 ;

is generated by 4.

Finally, the element 5 produces 5

= 5, 5

4

(mod 7), 5

6

(mod 7),

54 2

(mod 7), 55 3

(mod 7) and 56

1

(mod 7), i.e. the whole group

Z7 . The number of elements in each subgroup is directly related to the factorization of '(N) = 6. All the trivial and nontrivial factors are: 1,2,3,6. If we deal with larger N and the factorization of '(N) has n nontrivial factors, then

the probability that a randomly selected element from ZN			generates the whole
group is	1	.
	n+1
Mapping f : X ! Y is a generalization of a function, i.e. for every element
of the set X, it assigns an element from the set Y. Let hG;			i and hH; Æi be two
groups, then the mapping f : G ! H is a group homomorphism if
8a;b2G f(a b) = f(a) Æ f(b):			(2.13)