<<

. 2
( 18)



>>

signing with his own private key. The recipient performs the complementary
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
( 18)



>>