Cryptography Reference
In-Depth Information
10.2.2 Computational Aspects
First, we note that the signature is as long as the modulus
n
, i.e., roughly
bit. As discussed earlier,
n
is typically in the range from 1024 to 3072 bit. Even
though such a signature length is not a problem in most Internet applications, it can
be undesirable in systems that are bandwidth and/or energy constrained, e.g., mobile
phones.
The key generation process is identical to the one we used for RSA encryption,
which was discussed in detail in Chap. 7. To compute and verify the signature,
the square-and-multiply algorithm introduced in Sect. 7.4 is used. The acceleration
techniques for RSA introduced in Sect. 7.5 are also applicable to the digital signa-
ture scheme. Particularly interesting are short public keys
e
, for instance, the choice
e
= 2
16
+ 1. This makes verification a very fast operation. Since in many practical
scenarios a message is signed only once but verified many times, the fact that ver-
ification is very fast is helpful. This is, e.g., the case in public-key infrastructures
which use certificates. Certificates are signed only once but are verified over and
over again every time a user uses his asymmetric keys (cf. Sect. 13.3.3).
log
2
n
10.2.3 Security
Like in every other asymmetric scheme, it must be assured that the public keys
are authentic. This means that the verifying party in fact has the public key that
is associated with the private signature key. If an attacker succeeds in providing
the verifier with an incorrect public key that supposedly belongs to the signer, the
attacker can obviously sign messages. In order to prevent the attack, certificates can
be used, a topic which is discussed in Chap. 13.
Algorithmic Attacks
The first group of attacks attempts to break the underlying RSA scheme by comput-
ing the private key
d
. The most general of these attacks tries to factor the modulus
n
into the primes
p
and
q
. If an attacker succeeds with this, she can compute the private
key
d
from
e
. In order to prevent factoring attacks the modulus must be sufficiently
large, as discussed in Sect. 7.8. In practice, 1024 bit or more are recommended.
Existential Forgery
Another attack against the schoolbook RSA signature scheme allows an attacker to
generate a valid signature for a
random
message
x
. The attack works as follows:
