Cryptography Reference
In-Depth Information
NON-MODULAR EXPONENTIATION
The discrete logarithm problem might look hard enough without the added
complication of modular arithmetic. However, there is a big difference between
computing normal logarithms (given
a
and
a
b
, find
b
) and computing discrete
logarithms (do the same thing, but working modulo
n
). Finding logarithms is in
fact much easier without modular arithmetic. To get a feeling for this, consider a
closely related problem: the taking of square roots.
We will try to find the square root of 1369. Here is a good strategy:
1. Start with a guess, say 40. The square of 40 (in other words 40
×
40) is easy
to compute. It is 1600, which is too big.
2. Try something smaller, such as 30. The square of 30 is 900, which is too small.
3. Now try an intermediate value, such as 35. The square of 35 is 1225. This
is still too small, but it is fairly close.
4. Now try something just a little bit bigger than 35, but smaller than 40, such
as 37. The square of 37 is 1369, which is our target. Thus the square root of
1369 is 37.
It is clear that the above 'strategy' is actually a simple algorithm that we could use
to find the square root of any number. This iterative algorithm essentially makes
educated guesses at the answer, modifying the next guess based on the result of
the previous one. It is efficient to run and thus computing square roots is clearly
easy.
But what about computing square roots modulo a number? We will try to find
the square root of 56 modulo 101. We might as well try the strategy that worked
so well last time.
1. Start with a guess, say 40. The square of 40 is 1600. Reducing 1600 modulo
101 we get the answer 85. So the square of 40 modulo 101 is 85, which is
too big.
2. Try something smaller, say 30. The square of 30 is 900, which is 92
modulo 101. This is even bigger, which is strange because 30 was smaller
than our first guess.
We have just observed that the square of 30 modulo 101 is 'bigger' than the square
of 40 modulo 101. Thus the algorithm that we designed for computing square
roots, which was based on an intuitive notion of numerical order, no longer
works. Generally, computing square roots modulo a number is regarded as being
much harder than for normal integers. Thus squaring a number is an easy function
to compute and to reverse for normal integers, but could be regarded as a one-way
function when computed using modular arithmetic. Modular exponentiation can
be regarded as a one-way function for similar reasons.
The moral of this short side discussion is that if we want to design one-way
functions then modular arithmetic is a good concept on which to base our design,
because it makes certain types of computation much harder than when it is
not used.
