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