Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 171

fingerprint . We will mean a cryptographic hash function when we use the term
hash function henceforth.
There is a special terminology for one-way hash functions. A hash function
h is called weakly collision resistant if it is computationally infeasible to find
for a given x 1 , a value x 2

= x 1 such that h ( x 1 )= h ( x 2 ). A hash function
h is called strongly collision resistant if it is computationally infeasible to find
any pair of values ( x 1 ,x 2 ) such that x 1

= x 2 and h ( x 1 )= h ( x 2 ). The reader is
cautioned that these collision-related terms are not used consistently throughout
the literature.
We will be looking at hash functions from numerous perspectives, some of
the most important of which are in message authentication, as one might expect
from a device that mimics a “fingerprint”. We study hash function in depth
later (see page 252).
We conclude this section with an important algorithm that is essential to
the e8ciency of many cryptosystems including RSA. It is our last example of
yet another kind of exponentiation algorithm, called basic exponentiation , which
can be used with any base b and any exponent r .
Our basic goal is to calculate the least positive residue of x d modulo n for
any given x, d . To do this with a single exponentiation would overflow the

memory of most computers for su8ciently large d . We could reduce memory
requirements by starting with x and multiplying by x, d

∈ N

1 times, reducing
modulo n at each step, but even here, for large d , the methodology is still
too slow. Fortunately, there is an e8cient algorithm of squaring and reducing
modulo n in successive steps, that is quite e8cient.

−

The Repeated Squaring Method

Given d, n ∈ N , d> 1, and

k

d j 2 j , d j ∈{

d = 0 , 1 } ,

j =0

the goal is to find x d (mod n ).
First, we initialize by setting c 0 = x if d 0 = 1, and set c 0 =1if d 0 = 0. Also,
set x 0 = x , j = 1, and execute the following steps:

x j − 1 (mod n ).
(2) If d j = 1, set c j = x j ·

(1) Compute x j ≡

c j − 1 (mod n ).

(3) If d j = 0, then set c j ≡ c j − 1 (mod n ).

x d (mod n ), and terminate

(3) Reset j to j +1. If j = k + 1, output c k ≡

the algorithm. Otherwise, go to step (1).