Cryptography Reference
In-Depth Information
Figure 3.2
Public-key (asymmetric) cryptography. Image courtesy of Dr. Warwick Ford.
Diffie and Hellman suggested that the
one-way functions
used in login
procedures provided a useful example of the mathematical basis of public
key cryptography. When a user enters her password
pw
for the first time
on the system, a function
f
(
pw
) is calculated, Rather than the actual pass-
word, it is the result of this function that is stored in the system. When
the user logs in again, the same function is applied to the typed password,
and the result is compared with that stored in the system. For the system
to be secure, it must be hard to
invert f.
That is, given the stored informa-
tion
f
(
pw
), it must be difficult to find
pw.
Such functions are called one-way
functions “if for any argument
x
in the domain
f
, it is easy to compute the
corresponding value
f
(
x
), yet, for almost all
y
in the range of
f
, it is com-
putationally infeasible to solve the equation
y = f
(
x
) for any suitable argu-
ment
x
.”
9
Diffie and Hellman characterized public key cryptosystems as
trapdoor one-way functions
:
“These are functions that are not really one-way
in that simply computed inverses exist. But given an algorithm for the
forward function, it is computationally infeasible to find a simply com-
puted inverse. Only through knowledge of certain trapdoor information
can one easily find the easily computed inverse.”
10
