Search code examples
opensslcryptographyrsaverificationsigning

Why verify is quite faster than sign?

I tried to measure the performance of the rsa algorithm by running the following command :

$:openssl speed rsa

Output : 

                sign    verify    sign/s verify/s
rsa  512 bits 0.000048s 0.000003s  20923.5 355236.0
rsa 1024 bits 0.000102s 0.000007s   9757.6 152852.6
rsa 2048 bits 0.000676s 0.000022s   1479.2  46028.3
rsa 3072 bits 0.002385s 0.000041s    419.3  24407.0
rsa 4096 bits 0.005083s 0.000069s    196.7  14392.3
rsa 7680 bits 0.041772s 0.000234s     23.9   4281.9
rsa 15360 bits 0.231628s 0.000960s      4.3   1041.6

As we see from the output of this command the verify operation took less time than the sign one can anyone explain me why verify is much faster than sign? Thanks in advance !

Solution

  • I will only talk here about RSA signatures.

    First of all RSA public key is a pair (n,e) where the n is the modulus and e is called the public exponent.

    The common RSA public exponents are {3, 5, 17, 257 or 65537}. The reason is simple; the cost of verification can be controlled to be minimal. For example, if you select 3 then it will require 1 multiplication and 1 squaring with a fast moduluar squaring algorithm. If you select 65537 = 2^16+1 then that will require 16 squaring and 1 multiplication.

    Now, once you select your public key, the private exponent d is a random integer e *d = 1 mod φ(n) and we want it in this way due to the security. We don't want small d since it is insecure. Read more about the attacks in this paper Twenty Years of Attacks on the RSA Cryptosystem.

    Since d is random and if we use Euler's totient function φ then it will require φ(n)=(p-1)(q-1) squaring and φ(n)/2 multiplication on average. This is the core reason for the cost difference between the verification and signatures.

    The RSA must be never used without proper padding and for signature, it must be used with RSA-PSS ( and similarly for the encryption OAEP or PKCS#5v.5 paddings)

    Notes;

    1. We actually use Carmichael function instead of Euler's function since it always produces the smallest d.

    2. The RSA can use CRT to speed the private key operation up to 4 times and OpenSSL uses in this way.

    3. RSA signing is not decryption, as stated above secure RSA ( not the textbook RSA) must use proper paddings.

    4. Yes, first we select public key then make sure that GCD(φ(n), e ) =1, if not select new primes p and q where n=p * q