Public-Key Encryption - Everyday Cryptography - page 159

a factorisation algorithm that works by dividing the target number by every prime,
starting with the smallest ones. If the primes are very large then this algorithm
fails to find a factor in polynomial time, but if one of the primes is small then it
will find this factor very quickly.
Multiplication of two large primes is believed to be a one-way function. We say
'believed' because nobody has been able to prove that it is hard to factor. However,
enough experts have devoted sufficiently many years to studying the problem
without making significant progress that it seems a reasonable assumption.
Maybe one day someone will find a method of factoring efficiently. Apart from
becoming famous, and probably rich, a wider implication will be that any public-
key cryptosystem whose security relies on multiplication of two primes being a
one-way function will immediately be broken. One such public-key cryptosystem
is RSA, which we study in Section 5.2.

MODULAR EXPONENTIATION WITH A LARGE MODULUS
The second one-way function that we will look at is modular exponentiation .In
Section 1.6.1we noted that exponentiation justmeans raising a number to a power.
Hence modular exponentiation means raising a number to a power modulo some
other number (this latter number is the modulus ). Amore detailed explanation of
modular arithmetic is provided in the Mathematics Appendix.
Modular exponentiation thus involves raising a number a to the power b
and then calculating the result modulo n , for some number n . We tend to write
this as:

a b mod n .

For example, raising 3 to the power 5 modulo 7 involves first calculating:
3 5

= 3 × 3 × 3 × 3 × 3 = 243

and then computing:

243mod 7 = 5 .

We have already noted in Section 3.2.3 that exponentiation can be conducted in
polynomial time. Since this is also true for modular exponentiation, it is regarded
as an easy operation.
However, given the result of a modular exponentiation, and only the numbers
a and n (where n is a prime), calculating the number b that was used to compute
the modular exponentiation is believed to be a hard problem, assuming that
n is large. This difficult problem is often referred to as the discrete logarithm
problem .
In other words, given numbers a and n (where n is prime), the function

a b mod n f ( b ) = ,

is believed to be a one-way function, since computing f ( b ) is easy but, given f ( b ),
working out what b is appears to be hard.