Asymmetric Ciphers—RSA and Others

The notion of an asymmetric encryption system dates to the 1970s, with the first and still primary version of asymmetric encryption being the RSA algorithm of Rivest, Shamir, and Adleman. In asymmetric encryption, an encryption key that is made public is used to encrypt a message that is sent to the owner of the public key. That owner then uses a privately held key to decrypt. The RSA algorithm relies on a choice of two large primes p and q, multiplied together to produce a modulus \(N = pq\). The public encryption key e and private decryption key d are chosen so that \(e d \equiv 1 \pmod {\phi (N)}\). Current knowledge of the mathematics is that if N and e are public, but p, q, and d are kept private, then decrypting a message requires factoring N into p times q, and that is computationally hard. In this chapter we lay out the foundation of the RSA process, with an example, and we comment on the current records in factoring as a estimate of the security of RSA.