Cryptography Reference
In-Depth Information
•
In a
universal forgery
, the adversary must be able to find an efficient algorithm
that is functionally equivalent to the signatory's
Generate
algorithm (but does
not require the signatory's signing key).
1
A DSS that does not protect against
a universal forgery is sometimes also called
universally breakable
.
•
In a
selective forgery
, the adversary is able to forge a digital signature for a
particular message (that is chosen before the attack is mounted). A DSS that
does not protect against a selective forgery is sometimes also called
selectively
breakable
.
•
In an
existential forgery
, the adversary is able to forge a digital signature for at
least one (possibly random-looking and not necessarily meaningful) message.
A DSS that does not protect against an existential forgery is sometimes also
called
existentially breakable
.
The types of security breaks are itemized in order of decreasing severity,
meaning that a total break is the most severe break and an existential forgery is
the least severe break. Many DSSs used in practice are existentially breakable. If,
for example, a DSS is built from a family of trapdoor permutations (e.g., the RSA or
Rabin DSS), then every possible value represents a valid signature for a (probably
random-looking and not very meaningful) message. This problem and ways to solve
it are discussed later in this chapter.
The adversary's capabilities (i.e., types of attack) and the task an adversary
is required to solve can be combined to come up with different notions of security
for DSSs. For example, we can say that a DSS is totally breakable even if we allow
only key-only attacks. Such a DSS is not very useful in practice. When people talk
about (provably) secure DSSs, then they usually refer to DSSs that protect against
existential forgery, even if one assumes an adversary who is able to mount adaptive
chosen message attacks. This notion of security is further addressed in Section 15.3.
We first begin with some basic DSSs (that are not secure in this strong sense).
15.2
BASIC SYSTEMS
In this section, we overview and discuss some basic DSSs that are practically
relevant. More specifically, we elaborate on RSA, ElGamal, and the DSA. RSA
and ElGamal are fundamentally different DSSs, whereas the DSA can also be
understood as a variation of ElGamal. For each of these DSSs, we describe the
1
Note that the distinction between a total break and a universal forgery is somehow vague. It
would also be possible to say that a total break occurs if an adversary is either able to compute
the signatory's private (signing) key or find an efficient signature generation algorithm that is
functionally equivalent to the signatory's true signature generation algorithm.
