Cryptography Reference
In-Depth Information
16.5
SIGNING MESSAGES
Signing messages is a concept which arose with public key cryptography. When you receive
a message encrypted with your public key, how do you know the message is from whom
claims to have sent it? After all, your encryption keys are public, and so anyone can encrypt
messages to you. Signing is a way for the sender to modify the message in a way that could
only be done by her.
Each public key scheme usually defines a method to perform signing. Sometimes the
signing closely resembles the enciphering mechanism, but often it does not. We will first
cover signing with RSA, the first system to propose this concept.
Signing with RSA
Suppose individual A wants to send a message
P
to individual B
using RSA in such a way so that B knows the message could only have come from individual
A. Suppose A uses the RSA modulus
n
=
pq
, and the exponents
e
and
d
, while individual B
uses
n
*
=
p
*
q
*
, and the exponents
e
*
and
d
*
. Of course, neither party knows the other's pri-
vate key. Individual A does the following:
1.
Individual A computes
C
1
P
d
(mod
n
)
using her decryption exponent. (No one else can do this if A is protecting her private
key.)
If
C
1
≥
n
*
, it is necessary for A to separate
C
1
into blocks before applying the transfor-
mation
2.
C
C
1
e
*
(mod
n
*
)
and form the final ciphertext to send to B.
To decrypt the message sent by A, B does the following:
1.
B decrypts the message
C
by applying
C
1
C
d
*
(mod
n
*
)
to regain
C
1
.
2.
B then computes
P
C
1
e
(mod
n
)
using A's public information to recover the plaintext.
Actually, it isn't necessary for A to encrypt the message a second time using B's public
information if she isn't concerned with who reads the message. B could simply decrypt
with A's public key to retrieve the plaintext. However, anyone else could do the same thing.
If privacy (in addition to integrity) is an issue (and it usually is), both transformations are
involved.
Is this all there is to it? No. Establishing one's identity couldn't possibly be this easy. For
example, is it possible someone could publish his or her public key values using someone
else's identity? If this is not regulated in some way, the answer is yes. Most public key
Search WWH ::
Custom Search