Check out the new USENIX Web site. next up previous
Next: mRSA Measurements Up: Experimental Results Previous: Communication Overhead

Standard RSA

As a point of comparison, we initially timed the standard RSA sign operation in OpenSSL (Version 0.9.6) with three different key sizes on each of our three test PCs. The results are shown in Tables 2 and 3. Each timing includes a message hash computation followed by an exponentiation. Table 2 reflects optimized RSA computation where the Chinese Remainder Theorem (CRT) is used to speed up exponentiation (essentially exponentiation is done modulo the prime factors rather than modulo N). Table 3 reflects standard RSA computation without the benefit of the CRT. Taking advantage of the CRT requires knowledge of the factors (p and q) of the modulus n. In mRSA, neither the SEM nor the user know the factorization of the modulus, hence, it is more appropriate to compare the efficiency of mRSA with the unoptimized RSA.

As evident from the two tables, the optimized RSA performs a factor of 3-3.5 faster for the 1024- and 2048-bit moduli than the unoptimized version. For 512-bit keys, the difference is slightly less marked.


Table 2: RSA results with CRT (in milliseconds).
Keysize 466 Mhz PII 800 Mhz PIII 930 Mhz PIII
(bits) (slow client) ( SEM) (fast client)
512 2.9 1.4 1.4
1024 14.3 7.7 7.2
2048 85.7 49.4 42.8


Table 3: Standard RSA results without CRT (in milliseconds).
Keysize 466 Mhz PII 800 Mhz PIII 930 Mhz PIII
(bits) (slow client) ( SEM) (fast client)
512 6.9 4.0 3.4
1024 43.1 24.8 21.2
2048 297.7 169.2 144.7


next up previous
Next: mRSA Measurements Up: Experimental Results Previous: Communication Overhead
Gene Tsudik
2001-05-10