Cryptography Reference
In-Depth Information
10.2.1 Schoolbook RSA Digital Signature
Suppose Bob wants to send a signed message
x
to Alice. He generates the same
RSA keys that were used for RSA encryption as shown in Chap. 7. At the end of the
set-up he has the following parameters:
RSA Keys
Bob's private key:
k
pr
=(
d
)
Bob's public key:
k
pub
=(
n
,
e
)
The actual signature protocol is shown in the following. The message
x
that is
being signed is in the range (1
,
2
,...,
n
−
1).
Basic RSA Digital Signature Protocol
Alice
Bob
k
pr
=
d
,
k
pub
=(
n
,
e
)
(
n
,
e
)
←−−−−−−−−−−−−
compute signature:
s
= sig
k
pr
(
x
)
x
d
≡
mod
n
(
x
,
s
)
←−−−−−−−−−−−−
verify: ver
k
pub
(
x
,
s
)
x
≡
s
e
mod
n
x
≡
x
mod
n
=
⇒
valid signature
≡
x
mod
n
=
⇒
invalid signature
As can be seen from the protocol, Bob computes the signature
s
for a message
x
by RSA-encrypting
x
with his private key
k
pr
. Bob is the only party who can
apply
k
pr
, and hence the ownership of
k
pr
authenticates him as the author of the
signed message. Bob appends the signature
s
to the message
x
and sends both to
Alice. Alice receives the signed message and RSA-decrypts
s
using Bob's public
key
k
pub
, yielding
x
.If
x
and
x
match, Alice knows two important things: First, the
author of the message was in possession of Bob's secret key, and if only Bob has
had access to the key, it was in fact Bob who signed the message. This is called
message authentication. Second, the message has not been changed in transit, so
that message integrity is given. We recall from the previous section that these are
two of the fundamental security services which are often needed in practice.
Proof.
We now prove that the scheme is correct, i.e., that the verification process
yields a “true” statement if the message and signature have not been altered during
transmission. We start from the verification operation
s
e
mod
n
:
s
e
=(
x
d
)
e
=
x
de
≡
x
mod
n
