ńņš. 2 |

operations on the received message. In the sign-encrypt-sign, the recipient

also needs to check that both signatures were issued by the same person.

Ā© 2009 by Taylor and Francis Group, LLC

A birdā™s-eye view of modern cryptography 21

1.2.4 Abstracting cryptographic primitives

In order to construct secure cryptosystems, cryptographers often start from

small building blocks and put them together to assemble these cryptosystems.

Of course, it is essential for these building blocks to satisfy relevant security

properties. We now brieļ¬‚y describe how the security of two essential building

blocks, block ciphers and hash functions is often modelled.

1.2.4.1 Blockciphers

As said in Section 1.1.1.1, a block cipher is a keyed family of permutations

that operate on blocks of n bits. To select a permutation in the family,

one uses a k-bit key. To model the security of a block cipher, two models

are often used. The ļ¬rst approach considers pseudo-random permutation

families. It is based on distinguishers. In this approach, the adversary knows

the algorithmic description of a family of pseudo-random permutations and

its goal is to determine whether a permutation chosen by the environment

is a truly random permutation or a permutation selected from the family by

choosing a random key. A good block cipher aims at being a pseudo-random

permutation family. Another, much stronger, approach is the ideal cipher

model. In this model, mostly used in proofs, a block cipher is idealized as a

family of purely random permutations. Note that, while very convenient for

proofs, this cannot be achieved by any concrete block cipher. Indeed, every

block cipher has a short algorithmic description, which is not the case for a

family of purely random permutations.

In addition, some other properties of block ciphers are sometimes considered

in cryptanalysis. A typical example considers related key attacks. Here, the

adversary is no longer limited to querying the blockcipher with a ļ¬xed key.

Instead, he is allowed to make queries using several related keys, obtained,

for example, by xoring or adding ļ¬xed constants to an initial key. A formal

treatment of this notion is given in [BK03]. One diļ¬culty with this notion

of related key attacks is that, unless the allowed operations on keys are very

limited, these attacks are too strong. For example, if the attacker is allowed

both adding and xoring constants, any block cipher can easily be attacked.

Indeed, adding ā˜1ā™ and xoring ā˜1ā™ to the initial key yields the same new key,

if and only if the low order bit of the key is a ā˜0ā™. Adding and xoring other

powers of two permit the adversary to learn each bit of the key. Of course,

once the key is known, the adversary wins.

1.2.4.2 Hash functions

Cryptographic hash functions have two diļ¬erent ļ¬‚avors. For theoretical

purposes, one usually encounters keyed family of hash functions. This ļ¬‚avor

is very close to block ciphers, except for two noticeable diļ¬erences: hash func-

tions are modelled by random functions instead of permutations and their

inputs have variable length instead of ļ¬xed length. Where needed, hash func-

Ā© 2009 by Taylor and Francis Group, LLC

22 Algorithmic Cryptanalysis

tions are idealized by random oracles. It was recently proven that the random

oracle model and the ideal cipher model are equivalent [CPS08].

The other ļ¬‚avor of hash functions is used for practical purposes. In that con-

text, it is very useful to have access to an unkeyed hash function. This is, for

example, the case of signature schemes, as discussed in Section 1.1.1.4. With

unkeyed hash functions, speciļ¬c security properties need to be introduced.

Three very useful properties are collision resistance, preimage resistance and

second preimage resistance. Preimage and second preimage resistance can

easily be deļ¬ned. For preimage resistance, we simply say that H is preim-

age resistant if there exists no eļ¬cient adversary that given a value h can

output a message M such that H(M ) = h. Similarly, H is second preimage

resistant if no eļ¬cient adversary can, given a message M , ļ¬nd a diļ¬erent

message M such that M = M and H(M ) = H(M ). These two deļ¬nitions

are straightforward to formalize, even with unkeyed hash functions.

However, collision resistance is a trickier property. For any unkeyed hash

function H, there exists an eļ¬cient adversary which simply prints out two

messages M and M contained in its code, such that H(M ) = H(M ). For

keyed family, the problem vanishes, which explains why they are preferred for

theoretical purposes. Of course, the existence of the above eļ¬cient adversary

does not help to ļ¬nd collision in practice. Thus, the common answer is to

overlook the above problem and to simply keep the deļ¬nition informal: a hash

function is then said to be collision resistant when no practical method can

eļ¬ciently yield collisions.

Ā© 2009 by Taylor and Francis Group, LLC

Chapter 2

Elementary number theory and

algebra background

Number theory is at the core of many cryptographic systems, as a conse-

quence, it is routinely used in many cryptanalysis. In this chapter, we discuss

some elementary but crucial aspects of number theory for cryptographers,

including a basic description of the RSA and Diļ¬e-Hellman public key cryp-

tosystems.

2.1 Integers and rational numbers

The construction of the ring of integers Z is out of the scope of this book

and we simply take it for granted. We recall a few elementary facts:

1. Z possesses two commutative laws called addition and multiplication,

respectively, denoted by ā+ā and āĆ—ā (the symbol Ć— is often removed

from equations or replaced by āĀ·ā or even by nothing as in xy). Com-

mutativity means that for any x and y, x + y = y + x and xy = yx. In

addition the operations are associative, i.e., (x + y) + z = x + (y + z)

and (xy)z = x(yz).

2. The neutral element of addition is 0.

3. For all x in Z : 0 Ā· x = 0.

4. The neutral element of multiplication is 1.

5. For any element x in Z, we can construct an element denoted by ā’x

and called the opposite of x, such that x + (ā’x) = 0. The subtraction

of two elements x ā’ y is deļ¬ned as the sum x + (ā’y).

6. The notation Zā— denotes the set of non-zero elements of Z.

7. For any element x in Zā— and any pair (y, z) of elements of Z, xy = xz if

and only if y = z.

23

Ā© 2009 by Taylor and Francis Group, LLC

24 Algorithmic Cryptanalysis

8. The multiplication distributes with respect to addition, i.e., for all x, y

and z:

(x + y)z = xz + yz.

9. Z is totally ordered by an order ā„ compatible with the ring operations,

i.e.:

(a) For all x : x ā„ x.

(b) For all x and y, if x ā„ y and y ā„ x then x = y.

(c) For all x, y and z, if x ā„ y and y ā„ z then x ā„ z.

(d) For all x and y, either x ā„ y or y ā„ x hold.

(e) For all x, y and z, x ā„ y if and only if x + z ā„ y + z.

(f) The notation x > y indicates that x ā„ y and x = y.

(g) For all x, y and for all z > 0, x ā„ y if and only if xz ā„ yz.

(h) For all x, y and for all z < 0, x ā„ y if and only if xz ā¤ yz.

10. The absolute value of x, denoted by |x| is deļ¬ned as x when x ā„ 0 and

as ā’x otherwise.

11. For all x = 0 and y, there exist two integers q and r, called the quotient

and remainder of the (Euclidean) division of y by x such that 0 ā¤ r < |x|

and:

y = qx + r.

12. When the remainder of the division of y by x is 0, i.e., when y = qx, we

say that x divides y, that x is a divisor of y or that y is a multiple of x.

Note that when x divides y, ā’x also divides y. Thus, it is convenient to

consider positive divisors only.

13. 1 (and ā’1) divides all integers.

14. For all x = 0, x divides itself, since x = 1 Ā· x.

15. A prime is an integer x > 1 with no non-trivial divisor, i.e., with no

positive divisor except 1 and x.

16. A positive integer x > 1 which is not a prime is said to be composite.

17. Any composite number N > 1 can be written as

t

pei ,

N= (2.1)

i

i=1

where each pi is a prime and ei > 0 is called the multiplicity of pi in N

and where no two pi s are equal. Moreover, up to the order of factors,

this decomposition is unique. This statement is called the fundamental

theorem of arithmetic.

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 25

Among the above notions, primes and the Euclidean division both play an

essential role in cryptography.

From the integers in Z, constructing the set Q of rational numbers (or

simply rationals) is quite easy and uses a classical construction of quotienting

a set by an equivalence relation. We describe this process in detail here since

we use it again in a more complicated case in Chapter 14. Let us consider

the set Z Ć— Zā— containing pairs of integers, with a non-zero second member.

We ļ¬rst deļ¬ne an equivalence relation ā” on this set. For all pairs (x1 , x2 )

and (y1 , y2 ), we say that (x1 , x2 ) ā” (y1 , y2 ) if and only if x1 y2 = y1 x2 . This

clearly is an equivalence relation, i.e., a relation which is reļ¬‚exive, symmetric

and transitive:

ā¢ Reļ¬‚exivity For all pairs (x1 , x2 ), we have (x1 , x2 ) ā” (x1 , x2 ) since

x1 x2 = x1 x2 .

ā¢ Symmetry For all pairs (x1 , x2 ) and (y1 , y2 ), the equivalence (x1 , x2 ) ā”

(y1 , y2 ) implies (y1 , y2 ) ā” (x1 , x2 ).

ā¢ Transitivity For all pairs (x1 , x2 ), (y1 , y2 ) and (z1 , z2 ), if (x1 , x2 ) ā”

(y1 , y2 ) and (y1 , y2 ) ā” (z1 , z2 ) then (x1 , x2 ) ā” (z1 , z2 ). Indeed, x1 y2 =

y1 x2 implies x1 z2 y2 = y1 x2 z2 and y1 z2 = z1 y2 implies x2 z2 y1 = x2 z1 y2 .

Thus, x1 z2 y2 = x2 z1 y2 and since y2 = 0, we ļ¬nd x1 z2 = x2 z1 .

The set Q is deļ¬ned as the set of equivalence classes of Z Ć— Zā— under the

equivalence relation ā”. The equivalence class of (x1 , x2 ) is denoted by x1 /x2

x1

or x2 . Since (x1 , x2 ) ā” (ā’x1 , ā’x2 ), it is possible to assume that x2 > 0.

Elements of Q written as x1 /x2 with x2 > 0 are called fractions.

It is clear that for any integer Ī» > 0, (x1 , x2 ) ā” (Ī»x1 , Ī»x2 ) or equivalently:

x1 Ī»x1

= .

x2 Ī»x2

When a fraction x1 /x2 cannot be written as y1 /y2 with 0 < y2 < x2 , we say

that the fraction is in irreducible form. In that case, there exists no integer

Ī» > 1 that divides both x1 and x2 . Every fraction has a unique representation

in irreducible form.

The set of integers Z is naturally embedded into Q by sending the integer x

to the fraction x/1. In the sequel, we simply use the symbol x when referring

to the fraction x/1. The set Q inherits, the addition, the multiplication and

the order from Z as follows:

ā¢ Deļ¬ne addition by saying that the sum of the equivalence classes of

(x1 , x2 ) and (y1 , y2 ) is the equivalence class of (x1 y2 + y1 x2 , x2 y2 ). This

deļ¬nition is compatible with the equivalence relation and identical to

the integer addition on the image of Z by the natural embedding.

ā¢ Deļ¬ne multiplication by saying that the product of the equivalence

classes of (x1 , x2 ) and (y1 , y2 ) is the equivalence class of (x1 y1 , x2 y2 ).

Ā© 2009 by Taylor and Francis Group, LLC

26 Algorithmic Cryptanalysis

This deļ¬nition is compatible with the equivalence relation and identical

to the integer multiplication on the image of Z by the natural embed-

ding.

ā¢ Deļ¬ne the order for equivalence classes (x1 , x2 ) and (y1 , y2 ), with x2 > 0

and y2 > 0 as follows: (x1 , x2 ) ā„ (y1 , y2 ) if and only if x1 y2 ā„ y1 x2 .

Once again, this is compatible with the equivalence relation and gives

the same order as in Z after the natural embedding.

We now recall the basic properties of these operations in Q:

1. Addition and multiplication in Q are commutative and associative.

2. The neutral element of addition is 0 = 0/1.

3. For all x in Q : 0 Ā· x = 0.

4. The neutral element of multiplication is 1 = 1/1.

5. For any element x/y in Q, its opposite is (ā’x)/y, denoted by ā’x/y.

6. The notation Qā— denotes the set of non-zero elements of Q.

7. Any element x/y of Qā— has a multiplicative inverse y/x that satisļ¬es

(x/y) Ć— (y/x) = 1.

8. The multiplication distributes with respect to addition in Q.

9. Q is totally ordered by the order ā„, and ā„ is compatible with the ring

operations.

10. The absolute value of x/y, denoted by |x/y| is deļ¬ned as |x|/|y|.

Since every non-zero element has an inverse, Q is not only a ring but also a

ļ¬eld. Note that the above construction can be applied not only to Z but to

any entire ring. In general, the resulting ļ¬eld is called the ļ¬eld of fractions of

the entire ring.

2.2 Greatest common divisors in Z

Given two integers x and y, we say that an integer z is a common divisor

of x and y if z divides both x and y. The set of common divisors of x

and y is a ļ¬nite set and thus contains a largest element, called the greatest

common divisor or GCD of x and y. The computation of GCDs is one of the

most frequent algorithmic tasks encountered in cryptography. One of its most

basic application is the rewriting of fractions in irreducible form. Indeed, for

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 27

any fraction x/y, if Ī» is a common divisor of x and y, we can write x = Ī»x

and y = Ī»y and remark that x/y = x /y . If Ī» is the greatest common divisor

of x and y, then x /y is in irreducible form.

To compute the greatest common divisor of x and y, it would, of course, be

possible to consider each number between 1 and the minimum of |x| and |y|

and to test whether it divides x and y. The largest of these numbers is then

the required GCD. However, when x and y become large in absolute value,

this algorithm requires a very large number of division and becomes extremely

ineļ¬cient. A much more eļ¬cient method, called Euclidā™s algorithm, is based

on Euclidean division. This algorithm is based on the following fact. If Ī»

is a common divisor of x and y; if, q and r are the quotient and remainder

in the Euclidean division of y by x, then Ī» is a common divisor of x and r.

Conversely, any common divisor of x and r is a common divisor of x and y.

Indeed, writing x = Ī»x , we have the equality:

y = (qx )Ī» + r. (2.2)

Thus, y is a multiple of Ī» if and only if r is a multiple of Ī». Since this is true

for all divisors, it is true in particular for the greatest. Thus, the GCD of

x and y is equal to the GCD of x and r. Applying this idea repeatedly and

assuming, without loss of generality, that y ā„ x ā„ 0 we can deļ¬ne a sequence

of integers z, starting with z0 = y, z1 = x and letting zi+1 be the remainder of

the Euclidean division of ziā’1 by zi . This sequence of integers is decreasing,

thus at some point we ļ¬nd zk = 0 and stop the sequence. Thanks to the above

remark, we know that the greatest common divisor of ziā’1 and zi is identical

to the greatest common divisor of zi and zi+1 . Thus, by induction, the GCD

of x and y is equal to the GCD of zkā’1 and zk . Since zk = 0, this GCD is

zkā’1 . The deļ¬nition of this sequence can be rewritten in algorithmic form as

Algorithm 2.1. In this algorithm, we express the quotient in the Euclidean

division of y by x as the fraction y/x rounding down to the nearest integer.

The fact that the sequence z is decreasing shows that algorithm terminates

and that it stops after at most |x| steps. However, it is much more eļ¬cient

than that. Indeed, the number of steps can be bounded by O(log |x|). A simple

way to prove this fact is to show that for all values of i we have zi+2 ā¤ zi /2,

when both values of the sequence are deļ¬ned. Indeed, either zi+1 ā¤ zi /2 and

we are done because the sequence is decreasing, or zi+1 > zi /2 in which case

zi+2 = zi ā’zi+1 < zi /2. Since z is a sequence of integers, we cannot have more

than log2 |x| divisions by two. Studying the complexity of GCD algorithms is

a research topic in its own right.

In addition to the GCD of x and y, Euclidā™s algorithm can also be used

to recover additional information by keeping track of the transformation used

from an element of the sequence z to the next. From a mathematical point-

of-view, let us deļ¬ne two additional sequences Ī± and Ī² in parallel to z. First,

we explicitly write:

zi+2 = zi ā’ qi zi+1 , (2.3)

Ā© 2009 by Taylor and Francis Group, LLC

28 Algorithmic Cryptanalysis

Algorithm 2.1 Euclidā™s greatest common divisor algorithm

Require: Input two integers X and Y

Let x āā’ |X|

Let y āā’ |Y |

if x > y then

Exchange x and y

end if

while x > 0 do

Let q āā’ y/x (Quotient of Euclidean division)

Let r āā’ y ā’ qx (Remainder of Euclidean division)

Let y āā’ x

Let x āā’ r

end while

Output y (GCD of X and Y )

where qi is the quotient in the Euclidean division of zi by zi+1 . Using this

quotient, we now deļ¬ne Ī± by the equations:

Ī±0 = 1

Ī±1 = 0 (2.4)

Ī±i+2 = Ī±i ā’ qi Ī±i+1 ,

and Ī² by the equations:

Ī²0 = 0

Ī²1 = 1 (2.5)

Ī²i+2 = Ī²i ā’ qi Ī²i+1 .

These two sequences have the property that for all 0 ā¤ i ā¤ k :

zi = Ī±i z0 + Ī²i z1 . (2.6)

This is true for i = 0 and i = 1 and readily follows by recurrence for greater

values of i. We can also show that for all values 0 ā¤ i ā¤ k ā’ 1 :

Ī±i Ī²i

= Ī±i Ī²i+1 ā’ Ī±i+1 Ī²i = (ā’1)i .

det

Ī±i+1 Ī²i+1

Indeed, this is clear when i = 0 and follow by induction when remarking that:

Ī±i+1 Ī²i+1 01 Ī±i Ī²i

Ā·

= .

1 ā’qi

Ī±i+2 Ī²i+2 Ī±i+1 Ī²i+1

Indeed, the transition from one step to the next is a multiplication by a matrix

of determinant ā’1.

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 29

In particular, the GCD of Ī±i and Ī²i is 1. Looking at Equation (2.6) for i = k

and using the fact that zk = 0 we see ā’Ī²k /Ī±k is an irreducible expression for

z0 /z1 . Note that it might be necessary to change the signs of both Ī±k and Ī²k

in order to enforce a positive denominator. The values Ī±kā’1 and Ī²kā’1 are also

very useful, they are called BĀ“zoutā™s coeļ¬cients and they allow us to express

e

the GCD zkā’1 of z0 and z1 as Ī±kā’1 z0 + Ī²kā’1 z1 . Euclidā™s extended algorithm

is a variation of Algorithm 2.1 that in addition to the GCD computes the

coeļ¬cients Ī±kā’1 and Ī²kā’1 . We give a description as Algorithm 2.2.

Algorithm 2.2 Euclidā™s extended algorithm

Require: Input two integers X and Y

Let Ī±y āā’ 0 and Ī²x āā’ 0.

if X ā„ 0 then

Let x āā’ X and Ī±x āā’ 1.

else

Let x āā’ ā’X and Ī±x āā’ ā’1.

end if

if Y ā„ 0 then

Let y āā’ Y and Ī²y āā’ 1.

else

Let y āā’ ā’Y and Ī²y āā’ ā’1.

end if

if x > y then

Exchange x and y

Exchange Ī±x and Ī±y

Exchange Ī²x and Ī²y

end if

while x > 0 do

Let q āā’ y/x (Quotient of Euclidean division)

Let r āā’ y ā’ qx (Remainder of Euclidean division)

Let Ī±r āā’ Ī±y ā’ qĪ±x

Let Ī²r āā’ Ī²y ā’ qĪ²x

Let y āā’ x, Ī±y āā’ Ī±x and Ī²y āā’ Ī²x

Let x āā’ r, Ī±x āā’ Ī±r and Ī²x āā’ Ī²r

end while

Output y and (Ī±y , Ī²y )

Optionally output (Ī±x , Ī²x )

The notion of greatest common divisor can be generalized to sets of integers.

It is the largest positive integer that divides all the elements of the state. It

is easy to compute it iteratively once we remark that given a set S containing

more than 2 elements, the GCD of S can be obtained as follows: Let a be

Ā© 2009 by Taylor and Francis Group, LLC

30 Algorithmic Cryptanalysis

any element of S, let b be the GCD of the set S ā’ {a}, then the GCD of S is

equal to the GCD of a and b. As a consequence, we can write Algorithm 2.3

to compute the GCD of a set or list of numbers.

Algorithm 2.3 GCD of a list of numbers

Require: Input a list of integers X1 , . . . , Xt

Let g āā’ X1

for i from 2 to t do

Let g āā’ GCD(g, Xi ) (using Euclidā™s GCD algorithm)

end for

Output g

2.2.1 Binary GCD algorithm

One drawback of Euclidā™s algorithm to compute GCDs is the need to per-

form Euclidean divisions. When faced with large integers, this can be a worry,

especially if one wants to avoid using a preexisting library for manipulating

large integers. In that case, Steinā™s binary GCD algorithm is a nice alterna-

tive solution. This algorithm computes GCDs without any Euclidean division,

using a few simple properties, that holds for all integers a ā„ 0 and b ā„ 0:

ā¢ If a = 0 and b = 0 then GCD(a, b) = b;

ā¢ If a = 0 and b = 0 then GCD(a, b) = a;

ā¢ If a and b are both even then GCD(a, b) = 2 GCD(a/2, b/2);

ā¢ If a is odd and b is even then GCD(a, b) = GCD(a, b/2);

ā¢ If a is even and b is odd then GCD(a, b) = GCD(a/2, b);

ā¢ If a and b are both odd, with a ā„ b then GCD(a, b) = GCD((aā’b)/2, b);

ā¢ If a and b are both odd, with a ā¤ b then GCD(a, b) = GCD(a, (bā’a)/2).

Using all of these properties in a proper sequence yields an algorithm whose

eļ¬ciency is similar to Euclid GCD. Depending on the exact architecture of

the computer running the algorithms, it might be somewhat faster or slightly

slower. An algorithmic description is given in Algorithm 2.4.

It is also useful to know how an extended version of Steinā™s algorithm can

also compute BĀ“zoutā™s coeļ¬cients. Since Steinā™s algorithm uses subtractions

e

and divisions by two, by following the same approach as in the extended

Euclidean Algorithm 2.2, it is easy, given two integers A and B to obtain

three integers Ī±, Ī² and e such that:

Ī±A ā’ Ī²B = 2e GCD(A, B). (2.7)

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 31

In order to obtain BĀ“zoutā™s coeļ¬cients, it suļ¬ces to modify the above coeļ¬-

e

cients in order to get rid of the unwanted factor 2e . After possibly exchanging

the role of A and B, we may assume that Ī± ā„ 0 and Ī² ā„ 0. Without loss of

generality, we may also assume that A and B are not both even. Indeed, the

BĀ“zoutā™s coeļ¬cients of 2A and 2B are the same as the BĀ“zoutā™s coeļ¬cients

e e

of A and B. Let us start with the simple case where A and B are both odd.

In that case, let us deļ¬ne:

e

B+1

Ī± =Ī± mod B and (2.8)

2

e

A+1

Ī² =Ī² mod A.

2

It is clear that Ī± A ā’ Ī² B = GCD(A, B) (mod AB). Moreover, since Ī± is

reduced modulo B and Ī² modulo A, Ī± A ā’ Ī² B lies in ] ā’ AB, AB[. As a

consequence, Ī± A ā’ Ī² B = GCD(A, B), not only modulo AB but also in the

ring of integers, and (Ī± , Ī² ) are BĀ“zoutā™s coeļ¬cients.

e

To treat the general case, it suļ¬ces to show how to obtain the coeļ¬cients

for the pair (A, 2B) from the coeļ¬cients (Ī± , Ī² ) for (A, B), when A is odd.

Remember that in that case, GCD(A, 2B) = GCD(A, B). If Ī² is even,

the coeļ¬cients are simply (Ī± , Ī² /2). If Ī² is odd, they are (Ī± + B, (Ī² +

A)/2). Note that there exist algorithms for computing GCDs with a better

asymptotic complexity than Euclidā™s or Steinā™s algorithm.

2.2.2 Approximations using partial GCD computations

The extended Euclidean Algorithm 2.1 yields more information about the

relation between its inputs X and Y than simply its outputs GCD(X, Y ),

(Ī±y , Ī²y ) and (Ī±x , Ī²x ). Going back to the mathematical representation by

sequences, we see that all intermediate values of the sequence (Ī±, Ī²) are inter-

esting; more precisely, at each step i ā„ 2 at the sequence, the fraction ā’Ī²i /Ī±i

is a good approximation of z0 /z1 , i.e. X/Y in Algorithm 2.1. More precisely,

we have:

z0 Ī²i zi 1

ā¤

+ = . (2.9)

|Ī±i Ī±i+1 |

z1 Ī±i Ī±i z1

As a consequence, it can be very useful to use intermediate values of Ī±i ,

Ī²i and zi to obtain a small linear combination of z0 and z1 whose coeļ¬cients

are also small. Roughly, one can expect to achieve values of all coeļ¬cients

around the square root of the initial numbers.

2.2.2.1 Application to real numbers

It is also possible to run the Euclidean algorithm on inputs which are ra-

tional of even real numbers instead of integers. When the inputs are two

rational numbers, say a and b, the output is the smallest positive rational

Ā© 2009 by Taylor and Francis Group, LLC

32 Algorithmic Cryptanalysis

Algorithm 2.4 Steinā™s binary greatest common divisor algorithm

Require: Input two integers X and Y

Let x āā’ |X|

Let y āā’ |Y |

if x = 0 then

Output y

end if

if y = 0 then

Output x

end if

Let p āā’ 1

while x is even and y is even do

Let x āā’ x/2

Let y āā’ y/2

Let p āā’ 2p

end while

while x is even do

x āā’ x/2

end while

while y is even do

y āā’ y/2

end while

if x > y then

Exchange x and y

end if

while x > 0 do

Let r āā’ (y ā’ x)/2

while r is even do

r āā’ r/2

end while

if r ā„ x then

Let y āā’ r

else

Let y āā’ x

Let x āā’ r

end if

end while

Output py (GCD of X and Y )

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 33

c such that aZ + bZ = cZ. If a = na /da and b = nb /db , we ļ¬nd that

c = GCD(na db , nb da )/da db . Thus, using the GCD algorithm with rationals

is essentially the same as using it with integers.

When the inputs are real numbers x and y, matters are more complicated.

Assuming temporarily that computations are performed with inļ¬nite preci-

sion, two cases arise, either x/y is a rational, in which case there exists a

smallest positive real z such that xZ + yZ = zZ, or x/y is irrational, in which

case xZ + yZ contains arbitrarily small positive numbers. In this second case,

the extended Euclidean algorithm never terminates and can be used to pro-

duce good rational approximation of x/y. Note that running the algorithm

on the pair of inputs (x/y, 1) yields the same result as on the pair (x, y).

2.2.2.2 Alternative approaches for approximations

Approximations of fractions or of irrationals can also be obtained using

diļ¬erent approaches. We brieļ¬‚y present these alternatives here.

A ļ¬rst possibility is the continued fraction algorithm, which can be seen as

a rewriting of the extended Euclidean algorithm for inputs of the form (x, 1).

Given an arbitrary real x, we deļ¬ne two sequences, one formed of reals r and

one formed of integers c. The two sequences are obtained from the following

rules:

ā¢ The sequence r is initialized by setting r0 = x.

ā¢ The two sequences are computed recursively, for all i:

ci = ri and (2.10)

1

ri+1 = . (2.11)

ri ā’ ci

Note that, if ri = ci for some value of i, we cannot deļ¬ne ri+1 and the

two sequences have a ļ¬nite number of terms.

The sequence c is called the continued fraction expansion of x. This se-

quence is ļ¬nite if and only if x is rational.

The second possibility to obtain an approximation of a real by a rational

fraction with small coeļ¬cients is to use lattice reduction in dimension two

(see Chapter 10, Exercise 1).

2.3 Modular arithmetic

Modular arithmetic is a very important tool in cryptography. In particular,

it is the keystone of RSA, Diļ¬e-Hellman and elliptic curve cryptosystem.

We ļ¬rst look at it from a mathematical perspective, before addressing the

Ā© 2009 by Taylor and Francis Group, LLC

34 Algorithmic Cryptanalysis

computational aspects. Choose an integer N > 1 and consider the set N Z

obtained by multiplying all integers by N . This set is an ideal of Z, i.e., it

satisļ¬es the following properties:

ā¢ For any x and y in N Z, x + y is in N Z.

ā¢ For any x in N Z and any Ī± in Z, Ī±x is in N Z.

Thanks to these properties, it is possible to construct the quotient of Z by

N Z, denoted by Z/N Z. More precisely, this quotient is obtained by consider-

ing equivalence classes for the equivalence relation ā”, deļ¬ned by x ā” y if and

only if x ā’ y ā N Z. As usual, the quotient Z/N Z inherits the addition and

multiplication from Z. In order to represent Z/N Z, it is often convenient to

choose a representative element in the interval [0, N ā’ 1]. In some cases, an

interval with positive and negative numbers such as ] ā’ N/2, N/2] might be

used instead of [0, N ā’ 1]. Most of the time, equivalence classes of Z/N Z are

identiļ¬ed with their representative. For example, we speak of the element 2

in Z/7Z instead of using the precise but cumbersome expression āthe class of

the integer 2 in Z/7Z.ā

In Z/N Z, any element has an opposite. For example, the opposite of the

class represented by x can be represented by N ā’x. When considering inverses,

the situation is more complicated; of course, 0 does not have an inverse, but

neither does an element x of Z/N Z when x and N are not coprime. Because

of this, we need to make a clear distinction between Z/N Z with N composite

and Z/pZ with p prime. Indeed, when p is prime, all non-zero elements have

inverses and Z/p is a ļ¬eld. On the contrary, when N is composite Z/N Z is a

ring with non-trivial divisors of 0. For some basic operations, this diļ¬erence is

not too signiļ¬cant and the same algorithms are used in both cases. However,

for some more advanced operations, eļ¬cient algorithms are only available for

the Z/pZ case. Conversely, the problem of ļ¬nding alternate representations

only arises for the composite case Z/N Z.

2.3.1 Basic algorithms for modular arithmetic

Most basic algorithms for modular arithmetic are extremely simple, this is

in particular the case of modular addition, modular subtraction and modu-

lar multiplication. The only real diļ¬culty is that these algorithms need to

perform Euclidean divisions, which are not easy to implement for large inte-

gers. However, this diļ¬culty is usually hidden. Indeed, for small integers,

Euclidean division is directly available at the hardware level in most proces-

sors and can be accessed in C using the operators / and %. For large integers,

the usual approach is to use one of the numerous existing libraries for manip-

ulation of large integers, which include Euclidean division. The computation

of modular inverses is more complicated than the above elementary opera-

tions; however, it entirely relies on the extended Euclidean algorithm which

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 35

Algorithm 2.5 Addition modulo N

Require: Input x and y in the range [0, N ā’ 1]

Let s āā’ x + y

if s ā„ N then

Let s āā’ s ā’ N

end if

Output s

Algorithm 2.6 Subtraction modulo N

Require: Input x and y in the range [0, N ā’ 1]

if y > x then

Let x āā’ x + N

end if

Let s āā’ x ā’ y

Output s

we already addressed. For reference, we describe the modular operations as

Algorithms 2.5, 2.6, 2.7 and 2.8.

Another computation is frequently encountered in modular arithmetic: ex-

ponentiation. Given an element x of Z/N Z and an integer n we need to

deļ¬ne and compute xn . The mathematical deļ¬nition is easily obtained by

considering three cases:

ā¢ for n = 0, we deļ¬ne x0 = 1;

ā¢ for n > 0, we deļ¬ne xn = x Ā· x Ā· Ā· Ā· x, with n occurrences of x;

ā¢ for n < 0, we deļ¬ne xn = y Ā· y Ā· Ā· Ā· y, with ā’n occurrences of the inverse

y of x.

To compute xn eļ¬ciently, some care needs to be taken. In particular, the

elementary approach that consists in computing xn over the integer ring Z

followed by a reduction modulo N does not work in the general case. Indeed,

when n is even moderately large, xn is a huge number which cannot even be

stored, let alone computed on any existing computer. Since xn in Z/N Z is

routinely computed in all implementations of the RSA cryptosystem, another

approach is required.

This approach needs to reduce the number of multiplications that are per-

formed (|n| in the deļ¬nition) and at the same time to prevent the growth of

the intermediate values that appear in the computation. Since, xā’n = (1/x)n ,

it suļ¬ces to deal with positive values of n. The most frequently encountered

algorithm is the āsquare and multiplyā method, it is based on the following

equation:

xn = ((((xn )2 xn ā’1 )2 Ā· Ā· Ā· )2 xn1 )2 xn0 , (2.12)

Ā© 2009 by Taylor and Francis Group, LLC

36 Algorithmic Cryptanalysis

Algorithm 2.7 Multiplication modulo N

Require: Input x and y

Let p āā’ xy

Using Euclidean division, write p = qN + r

Output r

Algorithm 2.8 Multiplicative inverse modulo N

Require: Input x

Compute extended GCD g of x and N (g = ax + bN )

if g = 1 then

Output āx is non-invertible modulo N ā

else

Output a

end if

where n = i=0 ni 2i is the binary expansion of n. Taking care to perform

modular reduction after each operation to avoid an uncontrolled growth of

representative, this equation can be used as a basis for an eļ¬cient exponen-

tiation algorithm in two diļ¬erent ways, reading it either from left to right or

from right to left. This yields Algorithms 2.9 and 2.10.

Algorithm 2.9 Exponentiation in Z/N Z, left-to-right version

Require: Input N , x ā Z/N Z and integer n on bits

if n < 0 then

Let n āā’ ā’n

Let x āā’ (1/x) (mod N )

end if

ā’1

Write n in binary n = i=0 ni 2i

Let y āā’ 1

for i from ā’ 1 downto 0 do

Let y āā’ y 2 (mod N )

if ni = 1 then

Let y āā’ xy (mod N )

end if

end for

Output y

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 37

Algorithm 2.10 Exponentiation in Z/N Z, right-to-left version

Require: Input N , x ā Z/N Z and integer n on bits

if n < 0 then

Let n āā’ ā’n

Let x āā’ (1/x) (mod N )

end if

ā’1

Write n in binary n = i=0 ni 2i

Let y āā’ 1

for i from 0 to ā’ 1 do

if ni = 1 then

Let y āā’ xy (mod N )

end if

Let x āā’ x2 (mod N )

end for

Output y

2.3.1.1 Invertible elements in Z/N Z

Another aspect of modular arithmetic is the set of elements in Z/N Z that

are invertible, i.e., coprime to N . This set forms a multiplicative group de-

noted by (Z/N Z)ā— . The cardinality of this multiplicative group is called the

Eulerā™s totient function or Eulerā™s phi function and usually denoted by Ļ(N ).

If N is decomposed into primes as:

n

p ei ,

N= (2.13)

i

i=1

then

n

(pi ā’ 1)pi i ā’1 .

e

Ļ(N ) = (2.14)

i=1

A well-known theorem from group theory is the following:

THEOREM 2.1

Let G be a multiplicative group, e the neutral element in G and |G| the cardi-

nality of G, then for any element x in G we have x|G| = e.

PROOF See [Lan05, Chapter I, Proposition 4.1].

Applying this theorem to (Z/N Z)ā— , we ļ¬nd that for any x such that 0 <

x < N and GCD(x, N ) = 1, we have:

xĻ(N ) = 1 (mod N ). (2.15)

Ā© 2009 by Taylor and Francis Group, LLC

38 Algorithmic Cryptanalysis

2.3.2 Primality testing

Since primes are used in many cryptosystems, the ability to eļ¬ciently detect

that numbers are primes is an essential task in cryptography. Note that, since

the density of primes is quite high1 , knowing how to test primality is enough

to generate prime numbers: it suļ¬ces to pick numbers at random and test

their primality. After testing about ln(N ) candidates in the range [N/2, N ],

we obtain a prime number of the prescribed size.

Known primality tests are of two kinds: pseudo-primality tests and true

primality tests. Pseudo-primality tests rely on a basic randomized subroutine

which always returns true when its input is a prime and which returns false

with noticeable probability when its input is a composite. After calling the

basic subroutine a large enough number of times and obtaining true each

time, we know that either the input is a prime or we have been unlucky to

an unbelievable extreme. Note that we never know for sure when the input is

prime. However, a single false output guarantees that the input is composite.

The most frequently used pseudo-primality test is the Miller-Rabin primality

test, it is based on the fact that for any prime p, if we write p ā’ 1 = 2e q, with

q odd, and deļ¬ne for any integer 0 < z < p, the sequence (zi ) for 0 ā¤ i ā¤ e

by:

z0 = z q (mod p) and (2.16)

2

zi+1 = zi (mod p).

Then, we either have z0 = 1 or there exists an integer i < e such that zi = ā’1.

Moreover, if N is an odd composite, deļ¬ning N ā’ 1 = 2e q and proceeding as

above yields a negative result for at least 3/4 of the integers 0 < z < N .

From a practical point-of-view and especially for cryptography, pseudo-

primality tests are enough. However, a true polynomial time algorithm for de-

ciding primality was discovered in 2002 by Agrawal, Kayal and Saxena [AKS02].

It is known as the AKS primality test.

2.3.2.1 Computing square roots modulo primes

Computing modular square roots or, more generally, ļ¬nding roots of modu-

lar polynomials (see Section 2.5.3) is one speciļ¬c task which is easy to perform

modulo primes and, in general, hard to perform modulo composites, unless

their factorization is known. Depending on the value of the prime p, the

available algorithms for computing square roots vary. The simplest case oc-

curs with primes p such that p = 3 (mod 4). Indeed, for such primes, if z is

a quadratic residue (i.e., a square), then z (p+1)/4 is a square root for z. This

is easily seen by writing z = u2 and remarking that:

z (p+1)/4 = u(p+1)/2 = u Ā· u(pā’1)/2 = Ā±u. (2.17)

1 For numbers around N , the fraction of primes is essentially 1/ ln(N ).

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 39

Indeed, u(pā’1) = 1 and consequently u(pā’1)/2 = Ā±1. Note that, when p = 3

(mod 4), then ā’1 is a quadratic non-residue. Thus, exactly one of u and ā’u

is a square. In addition, z (p+1)/4 is the only square root of z which is itself a

square.

When p = 1 (mod 4), matters become more complicated, especially if a

large power of 2 divides p ā’ 1. In that case, we need to write p ā’ 1 = 2e q

with q odd. The method of choice to compute square roots in this case is

Shanks-Tonelli algorithm. This method is based on the remark that for any

quadratic residue z = u2 (mod p), the value z (q+1)/2 is āalmostā a square

e

root for z. More precisely, if we let Īø = z (q+1)/2 /u, then Īø2 = 1. Indeed:

2e

uq+1

e e

Īø2 = = u2 q

= upā’1 = 1 (mod p). (2.18)

u

As a consequence, to obtain a correct square root, it suļ¬ces to multiply

z (q+1)/2 by an adequate 2e -th root of unity in Fp . If we are given a primitive

2e -th root of unity, this can be done eļ¬ciently using a special case of Pohlig-

Hellman method for discrete logarithm that is described in Chapter 6. This

is precisely described as Algorithm 2.11.

2.3.2.2 Jacobi symbols

In Shanks-Tonelli square root algorithm, we simply assumed that the input

is a quadratic residue. However, it is useful to have an algorithm for testing

this property. Modulo a prime p, testing whether an element z is a quadratic

residue is easy, it suļ¬ces to check that z (pā’1)/2 is equal to 1 modulo p. How-

ever, there exists a more eļ¬cient way to compute this information. Given a

z

prime p and an integer z, we deļ¬ne the Legendre symbol p to be 0 if z = 0

(mod p), 1 if z is a quadratic residue and ā’1 if z is a quadratic non-residue.

q p

Given two odd primes p and q, the values p and are related by the

q

law of quadratic reciprocity which asserts that:

q p

= (ā’1)(pā’1)(qā’1)/4 .

Ā· (2.19)

p q

Another noteworthy property of the Legendre symbol is its multiplicativity:

ab a b

Ā·

= . (2.20)

p p p

In order to compute the Legendre symbol, it is ļ¬rst generalized into the

Jacobi symbol a , deļ¬ned for arbitrary non-negative integers a and b as:

b

ei

a a

= , (2.21)

b pi

i

Ā© 2009 by Taylor and Francis Group, LLC

40 Algorithmic Cryptanalysis

Algorithm 2.11 Shanks-Tonelli algorithm for square roots in Fp

Require: Input p = 2e q + 1, p prime, q odd, z a quadratic residue in Fp

repeat

Pick a random g in Fā— p

Let g āā’ g q

Let h āā’ g, i āā’ 0

while h = 1 do

Let h āā’ h2 , i āā’ i + 1

end while

until i = e {Here g is a primitive 2e -th root of unity}

Let h āā’ z (q+1)/2

Let Īø āā’ h2 /z

while Īø = 1 do

Let k āā’ Īø2 , i āā’ 1

while k = 1 do

Let k āā’ k 2 , i āā’ i + 1

end while

Let k āā’ g

for j from 1 to e ā’ i ā’ 1 do

Let k āā’ k 2

end for

Let h āā’ hk

Let Īø āā’ Īøk 2

end while

Output h

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 41

where i pi ei is the decomposition of b into primes. With this generalized

deļ¬nition, the law of quadratic reciprocity still holds for arbitrary odd integers

a and b. Using this generalization, it is possible to write down Algorithm 2.12

in order to compute Jacobi symbols.

2.3.3 Speciļ¬c aspects of the composite case

In the composite case, using knowledge of the factorization of N , it is possi-

ble to represent Z/N Z in several diļ¬erent ways. The ļ¬rst available represen-

tation simply uses a representative in the interval [0, N ā’ 1] (or ] ā’ N/2, N/2]).

The other representations correspond to factorizations of N in a product of

pairwise coprime factors. Mathematically, they come from the Chinese re-

mainder theorem:

THEOREM 2.2

Let N be a composite integer and let N = N1 N2 Ā· Ā· Ā· N , be a factorization

of N into factors such that all pairs (Ni , Nj ) are coprime. Then the two

rings Z/N Z and Z/N1 Z Ć— Z/N2 Z Ć— Ā· Ā· Ā· Z/N Z are isomorphic. Moreover, this

isomorphism can be explicitly and eļ¬ciently computed.

PROOF Working by induction on the number of factors, it suļ¬ces to

address the basic case of a two-factor decomposition N = N1 N2 with N1 and

N2 coprime.

In one direction, going from Z/N Z to Z/N1 Z Ć— Z/N2 Z is easy, it suļ¬ces

to send x to (x mod N1 , x mod N2 ). Clearly, two diļ¬erent representatives for

the same equivalence class in Z/N Z are sent to the same element in Z/N1 Z Ć—

Z/N2 Z, since N = 0 (mod N1 ) and N = 0 (mod N2 ). Moreover, it is clear

that mapping elements in this way is compatible with the ring operations. In

the reverse direction, since N1 and N2 are coprime, we ļ¬rst use the extended

Euclidean algorithm and write:

Ī±1 N1 + Ī±2 N2 = 1. (2.22)

We can remark that Ī±1 N1 is congruent to 0 modulo N1 and congruent to 1

modulo N2 . Conversely, Ī±2 N2 is congruent to 1 modulo N1 and to 0 modulo

N2 . As a consequence, to any pair (x1 , x2 ) in Z/N1 ZĆ—Z/N2 Z, we can associate

the element x = x1 Ī±2 N2 + x2 Ī±1 N1 in Z/N Z; this element x satisļ¬es:

x ā” x1 (mod N1 ) and (2.23)

x ā” x2 (mod N2 ).

Instead of using induction, it is also possible to derive direct coeļ¬cients

to make the isomorphism between Z/N Z and Z/N1 Z Ć— Z/N2 Z Ć— Ā· Ā· Ā· Z/N Z

explicit. For any i in [1, ], let Mi = j=i Nj and remarking that Ni and Mi

Ā© 2009 by Taylor and Francis Group, LLC

42 Algorithmic Cryptanalysis

Algorithm 2.12 Computation of Jacobi symbols

Require: Input a ā„ 0 and b ā„ 0

if b = 0 then

if a = 1 then

Output 1

else

Output 0

end if

end if

if a and b are even then

Output 0

end if

Let i āā’ 0

while b is even do

Let b āā’ b/2 and i āā’ i + 1

end while

if i is even then

Let S āā’ 1

else

Let S āā’ 1 if a is either 1 or 7 modulo 8

Let S āā’ ā’1 if a is either 3 or 5 modulo 8

end if

while a = 0 do

Let i āā’ 0

while a is even do

Let a āā’ a/2 and i āā’ i + 1

end while

if i is odd then

Let S āā’ ā’S if b is either 3 or 5 modulo 8

end if

if (a ā’ 1)/2 and (b ā’ 1)/2 are both odd then

Let S āā’ ā’S

end if

Let c āā’ a

Let a āā’ b mod c

Let b āā’ c

end while

if b = 1 then

Output S

else

Output 0

end if

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 43

are coprime write:

Ī²i Mi + Ī³i Ni = 1. (2.24)

Since Ī²i Mi is congruent to 1 modulo Ni and to 0 modulo each Nj for j = i,

the isomorphism between x and (x1 , Ā·, x ) is given by reduction modulo each

Ni in the forward direction and by:

x= x i Ī²i M i (mod N ) (2.25)

i=1

in the reverse direction.

We leave it to the reader to express the Chinese remainder theorem in

eļ¬ective algorithmic form.

2.3.3.1 Square roots and factoring from Ļ(N )

Let N be a composite number and, for simplicity, assume that N = pq

is a product of two primes2 . One key observation is that, modulo N , 1 has

four square roots, 1, ā’1 and the two numbers obtained using the Chinese

remainder theorem on 1 mod p and ā’1 mod q or on ā’1 mod p and 1 mod q.

We call 1 and ā’1 the trivial square roots of 1. Let z be a non-trivial square

root of 1, then z can be used to factor N . Indeed, z ā’ 1 is a multiple of p or

q, but not both. Thus, the GCD of N and z ā’ 1 is a proper divisor of N .

This observation can be used in several ways. A ļ¬rst application is to show

that any algorithm for computing square roots modulo N can be used to

factor N . Note that it does not suļ¬ce to call this algorithm on the value 1

because it may then return 1. Instead, we use a self-randomizing property of

modular square roots, choose a random value r and ask for a square root s

of r2 (mod N ), while keeping r secret. After this operation, r/s is a random

square root of 1. Thus, it is non-trivial with probability 1/2 (or more, if N

has more factors) and leaks the factorization of N .

Another application is to show that the knowledge of Ļ(N ) is also enough

to factor N . Indeed, writing Ļ(N ) = 2e I, we may see that for any number

x in Z/N Z, letting y = xI and squaring y repeatedly, we obtain 1. Thus,

somewhere in the path between y and 1, we encounter a square root of 1. If

this square root is trivial or in the rare case where y = 1, we simply choose

another value for x. In truth, the knowledge of Ļ(N ) is not really needed to

use this argument: it is also possible to factor N using the same method when

a multiple of Ļ(N ) is known. Also note that in the two-factor case, there is an

easy deterministic method to factor N when Ļ(N ) is known. Indeed, in that

case, we know that pq = N and p + q = N + 1 ā’ Ļ(N ). As a consequence, p

and q are the roots of the quadratic equation x2 ā’ (N + 1 ā’ Ļ(N ))x + N = 0.

2 If

N has more factors, the same kind of argument applies. The only diļ¬erence is that there

are more non-trivial square roots of 1.

Ā© 2009 by Taylor and Francis Group, LLC

44 Algorithmic Cryptanalysis

2.4 Univariate polynomials and rational fractions

Polynomials in a single variable are also very frequently encountered in

cryptography. Given a ring R, we deļ¬ne the ring R[X] of polynomials in the

variable X as follows:

N

i

p

ā¢ A polynomial P is a formal sum P (X) = i=0 pi X , where pi is a

sequence of elements of R. The value pi is called the coeļ¬cient of X i in

P . For convenience, it is useful to deļ¬ne pi = 0 for all i > Np , to omit

ā

Np and write P (X) = i=0 pi X i . However, the reader should keep in

mind that P only contains ļ¬nitely many non-zero coeļ¬cients.

ā¢ The degree of a polynomial P is the largest integer d(P ) such that the

coeļ¬cient of X d(P ) is non-zero. For the zero polynomial 0 corresponding

to the null sequence, we deļ¬ne d(P ) = ā’ā.

ā ā

ā¢ The sum of two polynomials P (X) = i=0 pi X i and Q(X) = i=0 qi X i

ā

is deļ¬ned as (P + Q)(X) = i=0 (pi + qi )X i . Each polynomial has an

ā

opposite, (ā’P )(X) = i=0 (ā’pi )X i .

ā¢ The degree of a sum is at most the largest among the degrees of the sum-

mands P and Q, i.e., d(P + Q) ā¤ max((d(P ), d(Q)). When, the degrees

of P and Q are diļ¬erent, equality holds: d(P + Q) = max((d(P ), d(Q)).

ā

pi X i and Q(X) =

ā¢ The product of two polynomials P (X) = i=0

ā i

i=0 qi X is deļ¬ned as:

ļ£« ļ£¶

ā i

pj qiā’j ļ£ø X i .

(P Q)(X) = (2.26)

ļ£

i=0 j=0

We leave it to the reader to check that the sum in the above equation

is indeed ļ¬nite and that R[X] is a ring. Note that no non-constant

polynomial has an inverse.

ā¢ The degree of a product is the sum of the degrees d(P Q) = d(P ) + d(Q)

under the convention that addition with ā’ā yields ā’ā.

ā¢ A polynomial is called unitary when its coeļ¬cient of highest degree

dā’1

is 1. In other words, P is unitary when P (X) = X d + i=0 pi X i .

When R is a ļ¬eld, any non-zero polynomial can be transformed into a

unitary polynomial by multiplication by the inverse of its highest degree

coeļ¬cient.

ā¢ Given a polynomial P and a unitary polynomial Q, it is possible to

write P = AQ + R, with R a polynomial of smaller degree than Q:

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 45

d(R) < d(Q). As in the integer case, A and R are called the quotient

and remainder of the (Euclidean) division of P by Q. When R = 0, we

say that Q divides P .

ā¢ When R is an entire ring, a unitary polynomial P is called reducible

when there exists two non-constant polynomials Q and R, i.e., d(Q) = 0

and d(R) = 0 such that P = QR. Otherwise, P is called irreducible.

When P is reducible, it is possible to choose Q and R unitary in the

expression P = QR.

ā¢ Over an entire ring, any unitary polynomial P can be written as a

product of irreducible polynomials, i.e.:

t

Piei .

P= (2.27)

i=1

Moreover, up to the order of factors, this decomposition is unique.

Note that when non-entire rings are involved, polynomials may factor in

very strange ways. To take a simple example, over Z/15Z, one may see that

(3x2 ā’ 1) Ā· (5x2 + 2) = x2 ā’ 2 mod 15. Furthermore, x2 ā’ 2 is irreducible both

modulo 3 and modulo 5.

2.4.1 Greatest common divisors and modular arithmetic

Thanks to the existence of a Euclidean division process for polynomials, it

is possible to use Euclidā™s algorithm to compute the greatest common divisor

of two polynomials over a ļ¬eld (or an entire ring). It is possible to directly use

Algorithm 2.1 without any change, simply replacing numbers by polynomials

where appropriate. Similarly, the extended Algorithm 2.2 can also be used

directly for polynomials. However, it is interesting to consider the analog of

the results of Section 2.2.2 and look at the degrees of intermediate polyno-

mials that appear during the extended GCD algorithm. Instead of having

a multiplicative relation relating the product of the current coeļ¬cients and

of the current reduced value to the initial values of the algorithm as in the

integer case, we obtain a similar additive relation involving the degrees of the

corresponding polynomials. In particular, we can expect along the GCD com-

putation a partial relation where all the polynomials have half degree, when

compared to the algorithmā™s input.

A variation of Steinā™s binary GCD algorithm can also be used for polyno-

mials. Instead of giving a special role to the prime 2, this variation gives this

role to the irreducible polynomial x. It is described as Algorithm 2.13. An

extended version can also be obtained.

Ā© 2009 by Taylor and Francis Group, LLC

46 Algorithmic Cryptanalysis

Algorithm 2.13 Steinā™s greatest common divisor algorithm for polynomials

Require: Input two polynomials A(x) and B(x)

Let a(x) āā’ A(x)

Let b(x) āā’ B(x)

if a(x) = 0 then

Output b(x)

end if

if b(x) = 0 then

Output a(x)

end if

Let p āā’ 0

while a(0) = 0 and b(0) = 0 do

Let a(x) āā’ a(x)/x

Let b(x) āā’ b(x)/2

Let p āā’ p + 1

end while

while a(0) = 0 do

a(x) āā’ a(x)/x

end while

while b(0) = 0 do

b(x) āā’ b(x)/x

end while

if deg a > deg b then

Exchange a(x) and b(x)

end if

while a(x) = 0 do

Let c(x) āā’ (b(0)a(x) ā’ a(0)b(x))/x

while c(0) = 0 do

c(x) āā’ c(x)/x

end while

if deg c ā„ deg a then

Let b(x) āā’ c(x)

else

Let b(x) āā’ a(x)

Let a(x) āā’ c(x)

end if

end while

Output xp b(x) (GCD of A(x) and B(x))

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 47

2.4.2 Derivative of polynomials

A very useful operation when working with polynomials is the computation

of derivatives. We quickly recall the basic deļ¬nition and properties of deriva-

tives. To any polynomial f in a polynomial ring R[X] we associate the poly-

ā

nomial D(f ) or D(f ), also denoted f , deļ¬ned as follows: If f (x) = i=0 fi xi ,

we let:

ā

ifi xiā’1 .

D(f )(x) = (2.28)

i=1

Note that since f only has ļ¬nitely many non-zero coeļ¬cients, so does D(f ).

Thus D(f ) is a polynomial. Moreover, for any pair of polynomials f and g,

we have the following properties:

D(f + g) = D(f ) + D(g) and (2.29)

D(f g) = D(f )g + f D(g). (2.30)

The Property (2.29) is clear from the deļ¬nition. Moreover, thanks to this

property, it suļ¬ces to prove Property (2.30) in the special case where f is a

monomial, say f (x) = axk . In this special case, we see that:

deg(g)+k

k

aigiā’k xiā’1

D(f g) = D(ax g(x)) = (2.31)

i=k

deg(g)

a(i + k)gi xi+kā’1

=

i=0

deg(g) deg(g)

= axk igi xiā’1 + kaxkā’1 gi xi

i=1 i=0

k kā’1

= ax D(g)(x) + kax g

= f D(g) + D(f )g.

By deļ¬nition, the derivative of any constant polynomial is zero. The con-

verse is almost true. More precisely, see [Lan05, Chapter IV, Proposition

1.12], for any polynomial f of degree at least 1 over a ļ¬nite ļ¬eld Fq of char-

acteristic p, i.e., q = pn (see below), either Df = 0 or there exists another

polynomial g such that f (x) = g(xp ) = g(x)p over Fq [x].

2.5 Finite ļ¬elds

Finite ļ¬elds are often considered in cryptography and it is useful to see how

they can be constructed. We have already seen, in the context of modular

Ā© 2009 by Taylor and Francis Group, LLC

48 Algorithmic Cryptanalysis

arithmetic, that Z/pZ is a ļ¬eld, if and only if, p is prime. Using a construction

similar to modular arithmetic and based on polynomials, we are now going to

construct some additional examples of ļ¬nite ļ¬elds.

2.5.1 The general case

In this section, we let p be a prime and consider polynomials over Z/pZ. We

also choose an irreducible polynomial I(x) of degree n in this polynomial ring.

Using I(x), we can deļ¬ne an equivalence relation between polynomials that

says that f ā” g if and only if f (x) ā’ g(x) is a multiple of I(x). Equivalently,

this means that f and g have the same remainder in the Euclidean division

by I(x). Taking the quotient of the ring of polynomials by this equivalence

relation, we obtain a ring containing pn elements. Indeed, in the equivalence

class of an arbitrary polynomial f , there is a polynomial of degree < n: the

remainder in the Euclidean division of f by I. Moreover, no two polynomials

of degree < n may belong to the same class. Since a polynomial of degree < n

is completely described by n coeļ¬cients in Z/pZ, the quotient ring contains pn

classes. To prove that this ring is a ļ¬eld, we need to show that any polynomial

f in Z/pZ[x] is either a multiple of I or prime to I. Since I is irreducible, this

holds by deļ¬nition.

An important theorem stated in [Lan05, Chapter V, Theorem 5.1] says

that all ļ¬nite ļ¬elds are either of the form Z/pZ or obtained by the above

construction. Moreover, for each possible value of pn there is a unique ļ¬eld

with pn elements. A ļ¬eld with pn elements, where p is a prime, is said to be of

characteristic p. Alternatively, the characteristic can be deļ¬ned as the order

of the unit element 1 in the ļ¬eld Fpn viewed as an additive group. Note that,

two diļ¬erent irreducible polynomials of degree n over Z/pZ give two diļ¬erent

representations of the same ļ¬nite ļ¬eld. Thanks to this remark, when using

this construction directly to represent elements in ļ¬nite ļ¬elds and compute

with them, it is possible to make a convenient choice for I in order to speed

up the computations. One frequent option is to use I(x) = xn + i(x), where

i(x) is a polynomial of low degree containing a small number of coeļ¬cients.

This speciļ¬c choice allows to speed-up reduction modulo I. It also permits to

multiply ļ¬nite ļ¬eld elements faster.

The representation of a ļ¬nite ļ¬eld Fq by a quotient of Fp [x] by an irreducible

I(x), is usually called a polynomial or a power basis for Fq .

The Frobenius map In a ļ¬nite ļ¬eld Fpn , the Frobenius map is the func-

tion Ļ which sends any element x to xp . This map satisļ¬es some essential

properties:

ā¢ For all x and y in Fpn , Ļ(xy) = Ļ(x)Ļ(y).

ā¢ For all x and y in Fpn , Ļ(x + y) = Ļ(x) + Ļ(y).

Ā© 2009 by Taylor and Francis Group, LLC

Elementary number theory and algebra background 49

The ļ¬rst property is a simple consequence of the commutativity of multiplica-

tion. The second property comes from the fact that p divides all coeļ¬cients

in the expansion of (x + y)p , except the coeļ¬cients of xp and y p .

The Frobenius map is a very useful tool when working with ļ¬nite ļ¬elds. We

discuss it a bit further in Chapter 14, showing that it is also very important

for elliptic curves. For now, let us give a simple example of its power. For any

df

polynomial f (X) = i=0 fi X i , we deļ¬ne the Frobenius of f as the polynomial

df

Ļ(f )(X) = i=0 Ļ(fi )X i . The reader can easily check that for any element

x in Fpn we have Ļ(f (x)) = Ļ(f )(Ļ(x)).

The Frobenius map can also be used to characterize the subļ¬elds of Fpn .

For any divisor m of n, let us denote by Ļm the composition of the Frobenius

map with itself m times. Then, the subset of elements x in Fpn such that

Ļm (x) = x is the ļ¬nite ļ¬eld Fpm . When n is prime, the only proper subļ¬eld

of Fpn is Fp itself.

Multiple extensions. In some cases, it can be useful to represent Fpn1 n2

as an extension of degree n2 of Fpn1 . This can be done using an irreducible

polynomial I of degree n2 with coeļ¬cients in Fpn1 . In the special case where

n1 and n2 are coprime, this can even be done with an irreducible polynomial

I with coeļ¬cients in Fp .

Normal bases. We saw that by choosing sparse irreducible polynomials, it

is possible to obtain eļ¬cient representations of ļ¬nite ļ¬elds by a polynomial

basis that allows faster multiplication. Another frequent representation is the

use of normal bases which represent elements of F2n as sums of Ī±, Ī±2 , Ī±4 ,

nā’1

. . . , Ī±2 , for a well-chosen value of Ī±. With normal bases, the Frobenius

map can be applied very easily, by simply rotating the coeļ¬cients. However,

multiplications become more costly. For special ļ¬nite ļ¬elds, it is even possible

to use optimal normal bases that allow faster computation of multiplication

and Frobenius.

Recently, a new representation was proposed in [CL09] by Couveignes and

Lercier that allows these fast operations for all ļ¬nite ļ¬elds. This representa-

tion is more complex that normal bases and makes use of elliptic curves over

the base ļ¬eld to represent extension ļ¬elds.

2.5.2 The special case of F2n

Finite ļ¬elds of characteristic 2 are frequently encountered in cryptographic

algorithms. As a consequence, fast implementations of arithmetic operations

in F2n have been developed for this special case, both in software and in

hardware. One frequently encountered method makes use of linear feedback

shift registers (LFSR). Since LFSR are also used as a basis for many stream

ciphers, we now describe them in more details.

ńņš. 2 |