Complexities on faking one signature
Robert J. Hansen
rjh at sixdemonbag.org
Tue Apr 4 03:32:59 CEST 2017
> 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.
More information about the Gnupg-users