Let be the secret key to be discovered. We
suppose that exponentiations are achieved by the right-to-left
square-and-multiply algorithm (Fig. 3). The attack
supposes that the register containing the value of *y* has some
permanently damaged known bits, always `0' or `1'. Let and denote the subsets of correct and incorrect
(i.e. damaged) bits of register *y* , respectively. So, any value stored in register *y* can be written as

From Eq. (1), the faulty signature corresponding to message
*m* is given by

Let be the function that maps the
correct bits of to the correct bits of
. Since is finite, the sequence must
eventually cycle. The length of the tail and
the length of the cycle can efficiently be computed by the
Floyd's algorithm [9, exercise 6 on p. 7]. This algorithm is
also known as the *kangaroos' method* . It has the advantage of
minimizing the storage requirements.

Two kangaroos and cover the sequence generated by *f* .
Kangaroo progresses in bounds of 1 unit and kangaroo in
bounds of 2 units. Since the sequence cycles, the two kangaroos will
meet. If they meet after *k* bounds, then
. Once *k* has been found, it suffices
to generate and for .Then, is the smallest integer *j* such that
.

*Proof.*Since , it follows that (2*k*-*k*) is a
multiple of . Moreover since
, is the smallest
integer *j* such that .

length of the cycle is the smallest integer *j* such
that . Putting all together, we obtain
the Floyd's algorithm (see Fig. 5).

To recover the bits of the secret exponent *s* , the pirate Carol
proceeds as follows. She first chooses a random message *m* . Then, by
the kangaroos' method, she computes the tail's length and the
cycle's length of the sequence generated by the
. If the sequence does not cycle, she chooses another
message *m* and reiterates the process. The first bit of *s* is
since *s* must be odd. To find the next bits
, Carol asks to Alice to sign some
and successively evaluates

If then ;otherwise .

*Proof.*Assume that Carol already computed
and therefore knows
. Then, she computes

Suppose that . Then letting *i*=*k*+1+*j* with , we have

and

So,

There is no general recipe to find the remaining bits of *s* . If the
length of the tail is short, Carol may choose another
random message *m* to find the first bits of *s* . The next bits
have to be found by exhaustive search. However, this search can be
speeded up by noting that the unknown bits have to fulfill some
algebraic relations.
For example, the bits must satisfy
the following relations:

and

*Proof.*

Note that if , then Eq. (6) simplifies to

Similar relations can be exhibited if is a power of 2.