Cryptography Reference
In-Depth Information
The following three functions, which are conjectured to be one way, have
many applications in (public key) cryptography:
•
Discrete exponentiation function;
•
RSA function;
•
Modular square function.
The fact that these functions are conjectured to be one way means that we
don't know how to efficiently invert them. The best algorithms we have at hand are
super-polynomial—that is, they have an exponential or subexponential running time
behavior (some of the algorithms are briefly overviewed in Sections 7.3 and 7.4).
The three candidate one-way functions are addressed next.
7.2.1
Discrete Exponentiation Function
From the real numbers, we know that the exponentiation and logarithm functions
are inverse to each other and that they can both be computed efficiently. This makes
us believe that this must be the case in all algebraic structures. There are, however,
algebraic structures in which we can compute the exponentiation function efficiently,
but in which no known algorithm can be used to efficiently compute the logarithm
function. For example, let
p
be a prime number and
g
be a generator (or primitive
root) of
Z
p
. The function
−→
Z
p
Exp
p,g
:
Z
p−
1
g
x
x
−→
is then called
discrete exponentiation function
to the base
g
.Itdefinesanisomor-
phism from the additive group
Z
p
,
Z
p−
1
,
+
to the multiplicative group
·
—that
is, Exp
p,g
(
x
+
y
)=Exp
p,g
(
x
)
Exp
p,g
(
y
). Because Exp
p,g
is bijective, it has an
inverse function that is defined as follows:
·
Z
p
Log
p,g
:
−→
Z
p−
1
x
−→
log
g
x
∈
Z
p
, the discrete
logarithm function computes the
discrete logarithm
of
x
to the base
g
, denoted by
It is called the
discrete logarithm function
.Forany
x
