Complexities on faking one signature

[Robert J. Hansen]

> 1. Computing the private key from the public key of the target and
> then using the private key to sign the message;

The difficulty of this is dependent on the length of the asymmetric key.
 NIST's guidance is that cracking a 1024-bit key is about 2**80 work, a
2048-bit key is about 2**112 work, and a 3072-bit key is about 2**128 work.

> 2. Enumerating the possible signature of that certain message and
> using the target's public key to verify if one of the signatures is
> correct.

I'm not sure what you mean here; that's not how signatures work.
Signatures work by computing a digest over data and encrypting that with
the private key.  Since you lack the private key, you can't generate
signatures.

What you could do instead is look at an earlier message your target
signed, get the digest of that, and generate new messages until you
created one with an identical digest.  The difficulty of this will
depend on your target's signature:

DSA-1024: 2**159 work
DSA-2048: 2**223 work
DSA-3072: 2**255 work
RSA: varies by user prefs, but unlikely to be under 2**159

You'll notice the work to break the hash is almost exactly the square of
the work to break the key.  This is not an accident.  :)