RSA PKCS#1 v.15 Signature verification computational complexity explanation?
Apparently the _sign is much more computationally complex than the _verify.


For RSA, this is typically the case.

For the signature verification operation, the computationally expensive part is the computation of $M^e \bmod N$ (for some $M$); where $e$ is a public value, which is typically fairly small (65537 is the most common value).

For the signature genearation operation, the computationally expensive part is the computation of $M^d \bmod N$ (for some $M$); where $d$ is a private value that's close to the size of $N$.

The computation of $M^x \bmod N$ takes time roughly proportional to the log of $x$; and so we're talking about of log2 of 16 (for signature verification) versus a log2 of 2048 (for signature generation), and so by this simple-minded analysis, we'd expect that verification be about a 100 times faster.

Now, during signature generation, an implementation can use the "Chinese Remainder Theorem" to cut this time by maybe a factor of 4 (this optimization cannot be used during the signature verification, as it requires knowledge of the factorization of $N$); this would reduce the expected ratio to about 25, which is roughly what you see.

For RSA, $d$ must be large (small values of $d$ are known to cause weaknesses); on the other hand, we don't mind if the attacker can guess $e$ (we'll publish it in the public key, hence he doesn't have to guess), and so there is no drawback in making is small.  Actually, an $e=3$ can actually be secure; however some people don't like it as it can be fragile if you don't get the padding right.