# Asymmetric Key Ciphers and Public-Key Cryptography - Overview

**Asymmetric key cryptosystems / public-key cryptosystems **(like **RSA**, **elliptic curve cryptography (ECC)**, **Diffie-Hellman**, **ElGamal**, **McEliece**, **NTRU** and others) use a pair of mathematically linked keys: **public key** (encryption key) and **private key** (decryption key).

The asymmetric key cryptosystems provide **key-pair generation** (private + public key), **encryption algorithms** (asymmetric key ciphers and encryption schemes like **RSA-OAEP** and **ECIES**), **digital signature algorithms** (like **DSA**, **ECDSA** and **EdDSA**) and **key exchange algorithms** (like **DHKE** and **ECDH**).

A message **encrypted** by the **public key** is later **decrypted** by the **private key**. A message **signed** by the **private key** is later **verified** by the **public key**. The **public key** is typically shared with everyone, while the **private key** is kept secret. Calculating the private key from its corresponding public key is by design computationally infeasible.

## Public-Key Cryptosystems

Well-known **public-key cryptosystems** are: **RSA**, **ECC**, **ElGamal**, **DHKE**, **ECDH**, **DSA**, **ECDSA**, **EdDSA**, **Schnorr signatures**. Different public key cryptosystems may provide one or more of the following capabilities:

**Key-pair generation**: generate random pairs of private key + corresponding public key.**Encryption**/**decryption**: encrypt date by public key and decrypt data by private key (often using a hybrid encryption scheme).**Digital signatures**(message authentication): sign messages by private key and verify signatures by public key.**Key-exchange algorithms**: securely exchange cryptographic key between two parties over insecure channel.

The most important and most used public-key cryptosystems are **RSA** and **ECC**. Elliptic curve cryptography (ECC) is the recommended and most preferable modern public-key cryptosystem, especially with the modern highly optimized and secure curves (like Curve25519 and Curve448), because of smaller keys, shorter signatures and better performance.

The **RSA public-key cryptosystem** is based on the mathematical concept of **modular exponentiation** (numbers raised to a power by modulus), along with some mathematical constructions and the **integer factorization problem** (which is considered to be computationally infeasible for large enough keys).

The **elliptic-curve cryptography (ECC) cryptosystem** is based on the math of the on the algebraic structure of the **elliptic curves** over finite fields and the **elliptic curve discrete logarithm problem (ECDLP)**, which is considered to be computationally infeasible for large keys. **ECC** comes together with the **ECDSA** algorithm (elliptic-curve digital signature algorithm). ECC uses smaller keys and signatures than RSA and is prefered in most modern apps. We shall discuss ECC and ECDSA later in details, along with examples.

Most **public-key cryptosystems** (like RSA, ECC, DSA, ECDSA and EdDSA) are **quantum-breakable** (quantum-unsafe), which means that (at least on theory) a powerful enough quantum computer will be able to break their security and compute the private key from given public key in seconds.

## Asymmetric Encryption Schemes

**Asymmetric encryption** is more complicated than symmetric encryption, not only because it uses **public** and **private keys**, but because asymmetric encryption can encrypt / decrypt only small messages, which should be mapped to the underlying math of the public-key cryptosystem. Some cryptosystems (like ECC) do not provide directly encryption primitives, so more complex schemes should be used.

In the **RSA** system, the input message should be transformed to **big integer** (e.g. using OAEP padding), while in **ECC** the message cannot be directly encrypted and more complex encryption scheme is used, based on the elliptic-curve Diffie-Hellman Key Exchange (ECDH). It will be explained in details later in this chapter. Additionally, asymmetric ciphers are significantly slower than symmetric ciphers (e.g. the RSA encryption is 1000 times slower than AES).

To overcome the above limitations and to allow encrypting messages of any size, modern cryptography uses **asymmetric encryption schemes** (also known as **public key encryption schemes** / **asymmetric encryption constructions** / **hybrid encryption schemes**), like **key encapsulation mechanisms** (KEM) and **integrated encrypted schemes**, which combine asymmetric encryption with symmetric key ciphers.

This is how a large document or file can be **encrypted** by combining **public-key cryptography** and **symmetric crypto algorithm**:

In the above diagram the encrypted symmetric key is known as **KEM block** (encapsulated key, with public key encryption) and the encrypted data file is known as **DEM block** (encapsulated data, with symmetric encryption). The encrypted message consists of these two blocks together (encapsulated key + encapsulated data).

This is the corresponding **decryption** process (decrypt an encrypted large document using **public-key cryptography** and **symmetric crypto algorithm**):

Examples of such asymmetric encryption schemes are: **RSA-OAEP**, **RSA-KEM** and **ECIES-KEM**.

### Integrated Encryption Schemes

**Integrated encryption schemes (IES)** are modern public key encryption schemes, which combine symmetric ciphers, asymmetric ciphers and key-derivation algorithms to provide secure **public-key based encryption** (PKE). In EIS scheme asymmetric algorithms (like RSA or ECC) are used to encrypt or encapsulate a symmetric key, used later by symmetric ciphers (like AES or ChaCha20) to encrypt the input message. Some EIS schemes provide also message authentication. Examples of EIS schemes are **DLIES** (Discrete Logarithm Integrated Encryption Scheme) and **ECIES** (Elliptic Curve Integrated Encryption Scheme).

### Key Encapsulation Mechanisms (KEMs)

A **key encapsulation mechanisms (KEM)** are asymmetric cryptographic techniques used to encrypt and encapsulate a secret key (called "ephemeral symmetric key"), which is used to encrypt an input message using a symmetric cryptographic cipher. **KEM** encapsulates the ephemeral symmetric encryption key as part of the encrypted message, by encrypting it with the recipient's public key. In cryptography this process is known as "**key encapsulation**".

The output from a KEM-based hybrid encryption scheme consists of **KEM block**, holding the encapsulated encrypted symmetric key (or certain parameters used to derive it), and **DEM block** (data encapsulation mechanism), holding the encapsulated symmetrically-encrypted data (cipher parameters + ciphertext + optionally an authentication tag).

**Key encapsulation mechanisms** (KEMs) are used in the hybrid encryption schemes and in the integrated encryption schemes, where a random element is generated in the underlying public-key cryptosystem and a symmetric key is derived from this random element by hashing. This approach simplifies the process of combining asymmetric and symmetric encryption. Examples of modern key encapsulation mechanisms are: **RSA-KEM**, **ECIES-KEM** and **PSEC-KEM**.

**Key encapsulation** should not be confused with **key wrapping**.

**Key encapsulation**(KEM) refers to**public-key encryption of another key**(symmetric or asymmetric). It is used for creating provably secure**hybrid encryption schemes**, e.g. to encrypt an AES secret key by given ECC public key.**Key wrapping**refers to**symmetric-key encryption of another key**(which can be either a symmetric key or an asymmetric key). It is used to encrypt, integrity-protect and transport cryptographic keys. Key wrapping provides privacy and integrity protection for specialized data such as cryptographic keys, without the use of nonces. For details see RFC 3394.

## Digital Signatures

In cryptography **digital signatures** provide message **authentication**, **integrity** and **non-repudiation** for digital documents. Digital signatures work in the public-key cryptosystems and use a public / private key pairs. Message **signing** is performed by the **private key** and message **verification** is performed by the corresponding **public key**.

A **message signature** mathematically guarantees that certain message was signed by certain (secret) **private key**, which corresponds to certain (non-secret) **public key**. After a message is signed, the message and **the signature cannot be modified** and thus message **authentication** and **integrity** is provided. Anyone, who knows the **public key** of the message signer, can **verify the signature**. Аfter signing the signature author cannot reject the act of signing (this is known as **non-repudiation**).

**Digital signatures** are widely used today for signing digital contracts, for authorizing bank payments and signing transactions in the public blockchain systems for transferring digital assets.

Most public-key cryptosystems like **RSA** and **ECC** provide secure digital signature schemes like **DSA**, **ECDSA** and **EdDSA**. We shall discuss the digital signatures in greater detail later in this section.

## Key Exchange Algorithms

In cryptography **key exchange algorithms** (**key agreement protocols** / **key negotiation schemes**) allow cryptographic keys to be exchanged between two parties, allowing the use of a cryptographic algorithm, in most cases symmetric encryption cipher. For example, when a laptop connects to the home **WiFi router**, both parties agree on a **session key**, used to symmetrically encrypt the network traffic between them.

Most key-exchange algorithms are based on public-key cryptography and the math behind this system: discrete logarithms, elliptic curves or other.

**Anonymous key exchange**, like Diffie–Hellman (**DHKE** and **ECDH**), does not provide authentication of the parties, and is thus vulnerable to man-in-the-middle attacks, but is safe from traffic interception (sniffing) attacks.

**Authenticated key agreement** schemes authenticate the identities of parties involved in the key exchange and thus prevent man-in-the-middle attacks by use of **digitally signed keys** (e.g. PKI certificate), **password-authenticated key agreement** or other method.