Digital Signature - A Classical Introduction to Cryptography: Applications for Communications Security - page 249

someone else but the secret key holder. Note that this implies that the key
holder is restricted to a single person, which is a critical legal issue in the case
of signatures. (Encryption does not have the same legal problem.)
Here nonrepudiation relies on the security assumption, and on the hypoth-
esis that no attack is feasible. In most cases we cannot prove that no attack
is feasible but only reduce the forgery problem to some other problem we do
not know how to solve (yet). In some special signature schemes which can be
used in paranoid cases where we do not want to rely on this unstable assump-
tion, an additional protocol makes it feasible for a signer to formally prove
that a signature was forged when it happens to be the case. The denial proto-
col must be such that it is infeasible for the signer to repudiate a signature he
created. Most of the time we cannot prove that it is infeasible. We can only
argue that it must be hard. But here the debatable assumption is in favor of the
signer and not on the verifier, which may be more suitable depending on legal
constraints.

10.2 RSA Signature

The original RSA paper (Ref. [158]) proposed a way to use the RSA algorithm as
a digital signature scheme. The relationship between public-key cryptosystems and
digital signatures is however quite general and not specific to RSA.

10.2.1 From Public-Key Cryptosystem to Digital Signature

Assuming that we have a public-key cryptosystem with a key generator, an encryption
algorithm which is deterministic, and a decryption algorithm, we can sign a message
by decrypting it. Verification simply consists of encrypting it. Note that here we have
a signature with message recovery : we do not need to send X together with σ since X

can be extracted from . So we can replace the verification algorithm by an extraction

algorithm. This case is depicted in Fig. 10.2.

σ

Adversary

Message
X

Signature
σ

Sign

Extraction

σ

X

Secret key Public key

K s K p AUTHENTICATED K p

Generator

Figure 10.2. Digital signature with message recovery.