How do other, non-RSA algorithms, compare to the PKCS #1 standard?

Question

Arguably the PKCS suite of standards have a profit-oriented bias as they are promoted by RSA and promote their algorithms over others in the form of RFCs and other means.

I'm considering the possibility that this information bias may include disinformation or omission regarding substitute algorithms that may be equally good if not better.

What are the other algorithms that could fill the space that that the PKCS#1 RSA algorithm is currently holding?

Answer 1

RSA is two algorithms, one for asymmetric encryption, the other for digital signatures.

For asymmetric encryption, the main competitors of RSA would be:

• The Rabin cryptosystem
• ElGamal
• NTRUEncrypt
• Diffie-Hellman key exchange (in practice, key exchange is almost as good as asymmetric encryption, since most usages of asymmetric encryption are for sending a key, followed by symmetric encryption).
• McEliece

For signatures, there are variants of the above; for ElGamal-like signatures, the most well-known variant is DSA.

The biggest advantage of RSA over almost any other competing algorithm is that it has a standard (PKCS#1) which unambiguously states where every byte should go. For wide industrial acceptance, such a standard is a must-have -- and it is even a free standard. This alone can explain the current dominant position of RSA. On that point, the only algorithms which can put up a fight with RSA are DSA, its elliptic-curve variant ECDSA, Diffie-Hellman, and elliptic-curve variant thereof. Only the DSA standard itself is free.

For performance, RSA public key operations are very fast, much faster than public key operations for discrete logarithm. On the other hand, elliptic-curve variants of DSA and DH are quite faster than RSA for private key operations. This can be seen by using OpenSSL with the openssl speed command-line tool. On a cheap and not-that-new 1.6 GHz AMD CPU (in 64-bit mode), I get this:

$ openssl speed rsa2048 dsa2048 ecdsap224 ecdhp224
Doing 2048 bit private rsa's for 10s: 1996 2048 bit private RSA's in 9.99s
Doing 2048 bit public rsa's for 10s: 70600 2048 bit public RSA's in 9.99s
Doing 2048 bit sign dsa's for 10s: 7311 2048 bit DSA signs in 9.99s
Doing 2048 bit verify dsa's for 10s: 6218 2048 bit DSA verify in 9.99s
Doing 224 bit sign ecdsa's for 10s: 43073 224 bit ECDSA signs in 10.00s 
Doing 224 bit verify ecdsa's for 10s: 9760 224 bit ECDSA verify in 9.99s
Doing 224 bit  ecdh's for 10s: 11474 224-bit ECDH ops in 9.99s
OpenSSL 0.9.8k 25 Mar 2009
built on: Thu Feb 10 01:45:33 UTC 2011
options:bn(64,64) md2(int) rc4(ptr,char) des(idx,cisc,16,int) aes(partial) blowfish(ptr2) 
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT
-DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -O3 -Wa,--noexecstack
-g -Wall -DMD32_REG_T=int -DOPENSSL_BN_ASM_MONT -DSHA1_ASM -DSHA256_ASM
-DSHA512_ASM -DMD5_ASM -DAES_ASM
available timing options: TIMES TIMEB HZ=100 [sysconf value]
timing function used: times
                              sign    verify    sign/s verify/s
rsa 2048 bits             0.005005s 0.000142s    199.8   7067.1
                              sign    verify    sign/s verify/s
dsa 2048 bits             0.001366s 0.001607s    731.8    622.4
                              sign    verify    sign/s verify/s
224 bit ecdsa (nistp224)  0.0002s   0.0010s     4307.3    977.0
                              op                 op/s
224 bit ecdh (nistp224)   0.0009s               1148.5

(I have slightly edited the output so that numbers are graphically aligned.)

This tests 2048-bit RSA vs 2048-bit DSA, and ECDSA and ECDH over a 224-bit curve, which should supposedly offer similar security. RSA is sorely beaten for private-key performance, but really shines for public-key operations.

Also (this is not apparent on this benchmark), DSA and ECDSA offer shorter signatures than RSA (56 bytes for ECDSA over P-224, vs 256 bytes for RSA-2048).

DSA and Diffie-Hellman got a lot of push from the US federal government in the last century, because at that time RSA was still patented. Otherwise, FIPS 186-3 would not have existed as a free standard. Nowadays, a lot of governmental organizations are pushing for the adoption of elliptic-curve cryptography, because it "feels unsafe" to rely on a single primitive: in case RSA gets spectacularly broken, there should be an alternate set of algorithms already developed.

For the figures above, we can see that ECDSA and ECDH are decent competitors for RSA, and have an edge over it in some specific cases. Yet support is not as widespread as for RSA, because the relevant standards are much more recent and involve higher-level mathematics (at some point, the implementer -- who writes the actual code -- must understand what is going on, and RSA is easier to understand).

In the future, NTRU may be a faster alternative, but right now it is aggressively patented, and still quite new (that's one of the benefits of a patent: it forces the rest of the world to wait a bit before deploying the algorithm, and this leaves time for cryptanalysts to do their job).