The Equivalent of a Written Signature - Burdens of Proof - page 77

adversary can compute the signer's private key and thus sign any messages
he wishes to.
At a minimum, any public-key signature scheme should be resistant
against total break under a key-only attack (that is, an adversary shouldn't
be able to compute the private key, given only access to the public key).
At the other end of the spectrum, signature schemes aim to resist against
existential forgery under an adaptively chosen message attack (that is, an
adversary shouldn't be able to create a single signature, even with access
to signatures on any document of his choice). 34 Proof of a cryptographic
signature scheme thus entails two distinct elements: on the one hand, the
specific computational assumptions on which the scheme is based (e.g.,
integer factorization is difficult); on the other hand, the attacks and
resources against which it is resistant.
The Threat of Repudiation
Both substitution and forgery are concerned with an adversary seeking to
abuse Alice's signing instrument, trying to produce valid signatures on
messages not of her own. But given signature schemes aim to produce
“undeniable” evidence that is binding on Alice, the threat model must also
consider that she herself might try to subvert the signature process and
produce valid signatures while somehow undermining their evidential
value. Throughout the 1980s and 1990s, cryptographers debated whether
Alice might be able to use the key generation process for such a purpose. By
deliberately creating a public key from which the private key could easily
be deduced, Alice could cast doubt on the strength of the evidence gener-
ated by the signature mechanism and consequently provide herself with
an opportunity to renegade on her commitments.
The attack would rely on a special-purpose “ P - 1 ” method, an algorithm
that can rapidly factor the public key n if its prime factors p and q possess
a certain “weak” structure. 35 In order to prevent against such attacks, p and
q can be specially chosen to be “strong” and thus resistant to the P - 1
method. But given that users may generate public key pairs themselves
(e.g., using software on their computers), what if they deliberately generated
a “weak” prime?
The user could do so by repeatedly generating RSA key pairs until one of the primes
output as part of the RSA private keys was obviously weak (to detect the weakness,
the user need only try to factor p - 1 or q - 1, perhaps by the Elliptic Curve Method).