Complexities on faking one signature

[Wouter Verhelst]

On Sun, Apr 02, 2017 at 07:12:38PM -0400, Robert J. Hansen wrote:
> > 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.

No, but you can generate random numbers and verify whether they happen
to be a valid signature.

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.

With RSA, the signature is exactly the same length as the (public) key.
Therefore, naively, one could assume that the complexity would be
approximately the same too.

In practice, however, the work required to brute-force a signature is
probably worse than that to brute-force a private key, because the
public key must be the product of the private key's two prime numbers
(which limits their values to things that can reasonably be the public
key's divisors, and you can preselect for that), whereas a signature is
a modulus and can therefore be pretty much anything.

-- 
< ron> I mean, the main *practical* problem with C++, is there's like a dozen
       people in the world who think they really understand all of its rules,
       and pretty much all of them are just lying to themselves too.
 -- #debian-devel, OFTC, 2016-02-12