Cryptography Reference
In-Depth Information
in the discovery of the notion of PKC, he was awarded a Doctorate in Techni-
cal Sciences (
Honoris Causa
) by the Swiss Federal Institute of Technology in
1992. His current position is Chief Security O8cer at Sun Microsystems, in Palo
Alto, California, where he has been since 1991. He has numerous awards from
the Association of Computing Machinery (ACM), IEEE, NIST, NSA, and the
Franklin Institute. The reader wanting more details of his involvement in public
policy concerning cryptography, and his opposition to limitations on the use of
cryptography by individuals and corporations, should consult Levy's topic [151],
wherein Di8e is a central character.
There are two more ingredients for the RSA recipe that we need before we
close this section. The first we encountered briefly on page 99, and we now
formalize the notion.
One-Way Functions
A one-to-one function
f
from a set
M
to a set
C
is called
one-way
if
f
(
m
)is
“easy” to compute for all
m
∈
M
, but for a randomly selected
c
in the image of
f
, finding an
m
such that
c
=
f
(
m
) is computationally infeasible. In other
words, we can easily compute
f
, but it is computationally infeasible to compute
f
−
1
.
∈
M
Diagram 4.2 One-Way Function
f
: computationally easy
−−−−−−−−−−−−−−−−−−→
←−−−−−−−−−−−−−−−−−−−−−−−−
f
−
1
: computationally infeasible
☛
✟
✞
m
∈
M
f
(
m
)
∈
C
✝
✆
✡
✠
One-way functions have a plethora of cryptographic uses. For instance, we
talked about PRNG earlier and mechanisms for making CSPRNGs (see page
151). One means of creating a CSPRNG using a one-way function is as follows.
Let
f
be a one-way function and assume a nonce
n
is known to us. Then define
f
(
n
+
j
)=
r
j
for
j
=1
,
2
,....
If
b
j
is the least significant bit
4.2
of
r
j
, then the sequence
b
0
b
1
...
will be a
CSPRNG.
Another use of one-way functions, about which we will see more later, is
password security
. Suppose that Alice has a password
p
and
f
is a one-way
function. Then
p
can be stored as
f
(
p
) on a computer. When Alice logs in to
her account, the computer takes
p
, calculates
f
(
p
), and checks that it matches
the stored value. A cryptanalyst who gets hold of the password file will have
only the
f
(
p
) value for each user, and obtaining
p
is computationally infeasible.
The above being said, there is no rigorous mathematical proof that one-way
functions actually exist. Yet, as we saw on page 99, we have working definitions,
4.2
In a given base-
b
representation of
a
∈
N
,
a
=(
a
n
,a
n
−
1
,...,a
1
,a
0
)
b
, the digit
a
0
is called
the
least significant digit
, and
a
n
is called the
most significant digit
.
Search WWH ::
Custom Search