Cryptography Reference
In-Depth Information
of 1 when divided by the least common multiple of
p
− 1
and
q
− 1. With knowledge of
p
and
q
, the number
d
can
easily be calculated using the Euclidean algorithm. If one
does not know
p
and
q
, it is equally difficult to find either
e
or
d
given the other as to factor
n
, which is the basis for
the cryptosecurity of the RSA algorithm.
We will use the labels
d
and
e
to denote the function
to which a key is put, but as keys are completely inter-
changeable, this is only a convenience for exposition. To
implement a secrecy channel using the standard two-key
version of the RSA cryptosystem, user
A
would publish
e
and
n
in an authenticated public directory but keep
d
secret. Anyone wishing to send a private message to
A
would encode it into numbers less than
n
and then
encrypt it using a special formula based on
e
and
n
.
A
can
decrypt such a message based on knowing
d
, but the pre-
sumption—and evidence thus far—is that for almost all
ciphers no one else can decrypt the message unless he can
also factor
n
.
Similarly, to implement an authentication channel,
A
would publish
d
and
n
and keep
e
secret. In the simplest
use of this channel for identity verification,
B
can verify
that he is in communication with
A
by looking in the
directory to find
A
's decryption key
d
and sending him
a message to be encrypted. If he gets back a cipher that
decrypts to his challenge message using
d
to decrypt it, he
will know that it was in all probability created by some-
one knowing
e
and hence that the other communicant is
probably
A
. Digitally signing a message is a more complex
operation and requires a cryptosecure “hashing” function.
This is a publicly known function that maps any message
into a smaller message—called a digest—in which each bit
of the digest is dependent on every bit of the message in
such a way that changing even one bit in the message is
