Cryptography Reference
In-Depth Information
Analysis
First, we note that (
p
1) in Example 4.4 is just the Euler function
(see page 479) applied to
pq
, since
φ
(
n
)=
φ
(
pq
)=(
p
−
1)(
q
−
1), and the
application of
f
−
1
in Equation (4.3) is just Euler's generalization of Fermat's
Little Theorem (see Theorem A.14 on page 479). This little bit of elementary
number theory is really all that is behind the RSA cipher, so understanding this
is su8cient to understand the entire cryptosystem.
In order to show that the finding of the trapdoor
d
in Example 4.4 is based
upon the IFP, in this case factoring
n
, we need to show that computing
d
is
“as hard as” factoring
n
. Determining what
as hard as
means will involve some
discussion of probabilities.
If we can factor
n
, obviously we can compute (
p
−
1)(
q
−
1). Then we can
use the Euclidean algorithm to find
d
from
e
(in computationally feasible time),
since we need merely solve
ed
+
x
(
p
−
1)(
q
−
1) = 1 for
x
and
d
. A simple
example is
e
=7,
p
= 101 and
q
= 167. Then solving 7
d
+ 100
−
1)(
q
−
·
166
·
x
=1
is easily achieved, with
x
=
2, and
d
= 4743. In fact, it can be shown that
being able to compute
d
can be converted (with an arbitrarily high probability)
into an algorithm for factoring
n
(see [170, page 65] for instance). In other
words, knowledge of
d
can be converted into an algorithm for factoring
n
(with
an arbitrarily small probability of failure to do so). Thus, to say that finding
d
is as hard as factoring the modulus is not a proven fact, rather a conjecture
based upon some (rather solid) evidence. We will formalize this conjecture in
the next section.
Note, as well, that if we have
φ
(
n
) and
n
, then we can factor
n
. The reason
is that we can find
p
and
q
by successively computing
−
q
=
(
p
+
q
)
2
p
+
q
=
n
−
(
p
−
1)(
q
−
1) + 1 and
p
−
−
4
n,
(4.4)
so we get
p
=
1
q
)] and
q
=
1
−
−
−
2
[(
p
+
q
)+(
p
2
[(
p
+
q
)
(
p
q
)]
.
Hence, finding
d
or finding
φ
(
n
) means we can factor
n
.
The next topic is a mechanism for creating a digital “fingerprint” of data.
Hash Functions
A
hash function
is a computationally e8cient function that maps bitstrings
of arbitrary length to bitstrings of fixed length, called
hash values
.A
one-way
hash function
is a hash function that is a one-way function as described above.
The process of using a hash function on a message is called
hashing the message
.
In order for a hash function to be cryptographically viable, it must be a
one-way hash function to prevent easy unauthorized retrieval of the original bit-
string. Thus, one-way hash functions are called
cryptographic hash functions
.
Hash values produced by such functions are used as a concentrated represen-
tative of the original bitstring, so they can be used as a unique identifier of
it. Thus, this type of hash value is called a
message digest
,
imprint
,or
digital
Search WWH ::
Custom Search