Cryptography Reference
In-Depth Information
Due to the mathematical relationship between the private and the public key, namely
that
de
≡
1mod
φ
(
n
)
,
raising any integer
x
∈
Z
n
to the (
de
)th power yields the integer itself again. The
proof for this was given in Sect. 7.3.
The role of the public and the private keys are swapped compared to the RSA
encryption scheme. Whereas RSA encryption applies the public key to the message
x
, the signature scheme applies the private key
k
pr
. On the other side of the commu-
nication channel, RSA encryption requires the use of the private key by the receiver,
while the digital signature scheme applies the public key for verification.
Let's look at an example with small numbers.
Example 10.1.
Suppose Bob wants to send a signed message (
x
= 4) to Alice. The
first steps are exactly the same as it is done for an RSA encryption: Bob computes
his RSA parameters and sends the public key to Alice. In contrast to the encryption
scheme, now the private key is used for signing while the public key is needed to
verify the signature.
Alice
Bob
1. choose
p
= 3and
q
= 11
2.
n
=
p
·
q
= 33
3.
Φ
(
n
)=(3
−
1)(11
−
1)=20
4. choose
e
= 3
5.
d
e
−
1
≡
≡
7 mod 20
(
n
,
e
)=(33
,
3)
←−−−−−−−−−−−−
compute
signature
for
message
x
= 4:
s
=
x
d
4
7
≡
≡
16 mod 33
(
x
,
s
)=(4
,
16)
←−−−−−−−−−−−−
verify:
x
=
s
e
≡
16
3
≡
4 mod 33
x
≡
x
mod 33 =
⇒
valid signature
Alice can conclude from the valid signature that Bob generated the message and
that it was not altered in transit, i.e., message authentication and message integrity
are given.
It should be noted that we introduced a digital signature scheme only. In par-
ticular, the message itself is not encrypted and, thus, there is not confidentiality. If
this security service is required, the message together with the signature should be
encrypted, e.g., using a symmetric algorithm like AES.
