Complexities on faking one signature

[Robert J. Hansen]

> I believe the OP is asking whether it'd be easier to brute-force a
> signature than it is to brute-force a private key.

Unimaginably harder to brute-force a sig.

Since RSA is deterministic (at least, naïve RSA is), a sig is done on a
digest (of let's say size 256 bits) and there are 2**256 different valid
outputs.  But the signature length itself is thousands of bits, for
2**thousands of possibilities.  So the per-attempt likelihood of finding
one of the 2**256 valid signatures out of a signature of 2**thousands of
bits is likelihood is 2**(256 - thousands).

2**-2000 is so close to zero as makes no difference whatsoever.