Cryptography Reference
In-Depth Information
walks records every 10th point, for example, in the first sequence and then
checks whether the second sequence matches any of these points. In this case,
the first sequence is called a tame kangaroo, and the second is called a wild
kangaroo. The idea is to use the tame kangaroo to catch the wild kangaroo.
The λ method is expected to find a match in at most a constant times N
steps. If it is run in parallel with many starting points, the running time can
be improved significantly.
Finally, we should point out a difference between the baby step, giant step
method and the ρ and λ methods. The baby step, giant step method is de-
terministic , which means th at it is guaranteed to finish within the predicted
time of a constant times N . On the other hand, the ρ and λ methods are
probabilistic , which means that there is a very high probability that they
will finish within the predicted time, but this is not guaranteed.
5.2.3
The Pohlig-Hellman Method
As before, P, Q are elements in a group G and we want to find an integer
k with Q = kP . We also know the order N of P and we know the prime
factorization
N =
i
q e i
i
of N . The idea of Pohlig-Hellman is to find k (mod q e i )foreach i ,thenuse
the Chinese Remainder theorem to combine these and obtain k (mod N ).
Let q be a prime, and let q e
be the exact power of q dividing N .Write k
in its base q expansion as
k = k 0 + k 1 q + k 2 q 2 + ···
k i <q . We'll evaluate k (mod q e ) by successively determining
k 0 ,k 1 ,...,k e− 1 . The procedure is as follows.
1. Compute T = j q P
with 0
| 0 ≤ j ≤ q − 1 .
q Q . This will be an element k 0 q P of T .
N
2. Compute
3. If e = 1, stop. Otherwise, continue.
4. Let Q 1 = Q
k 0 P .
q 2 Q 1 . This will be an element k 1 q P of T .
N
5. Compute
6. If e = 2, stop. Otherwise, continue.
7. Suppose we have computed k 0 ,k 1 ,...,k r− 1 ,and Q 1 ,...,Q r− 1 .
 
Search WWH ::




Custom Search