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

Adversary

Message
X X , σ X

σ

X σ X

d

Hashing Decryption Encryption Hashing

d d

Secret key
K s

Public key
K p K p

AUTHENTICATED

Compare

Generator

Figure 10.3. Encryption to signature.

In order to limit the size of the signature, we can use a cryptographic hash function
before signing. This hash function must however be collision-resistant (otherwise we
can have the same signature for two different messages, so a chosen message attack
with the first message makes a signature forgery on the second message).

Fig. 10.3 represents the generic transformation of public-key encryption into a
signature scheme. Note that it does not provide message recovery. In the following, we
however strongly discourage to talk about encryption instead of signature, since the
threat model is totally different.

10.2.2 On the Plain RSA Signature

Let K p = d ) be an RSA key pair for signature. The signature of

a message m by using the plain RSA algorithm is simply

( N , e ) and K s = ( N ,

m d mod N , as depicted
in Fig. 10.4. This suffers from several problems which are mainly due to the RSA
properties.

σ =

e

First of all, it is easy for anyone to pick a random σ and to construct m = σ mod N

,σ

which makes ( m ) a valid pair. This is an existential forgery : we can forge a valid

pair, but we have no control on the meaning of the forged message m .

) and ( m ,σ ), for instance

Second, we can easily modify two valid pairs ( m ,σ

by taking m = σ = σσ mod N .( m ,σ ) is then a new valid pair.

This comes from the property of malleability of the RSA algorithm.

mm mod N and

These security issues can be fixed by cryptographic hash functions. We must at
least adapt the plain RSA system in order to prevent these attacks.