How RSA Works
Using RSA, an Asymmetric Cipher
Jump ahead to see how the RSA cipher works
Asymmetric ciphers like RSA
or Rivest Shamir Adelman,
and ECC or ellipticcurve cryptography
are intended for session key agreement and
for digital signature creation and verification.
They are not suited for encrypting the
data itself —
email messages or files or database contents or data
streams or archives — whatever the sensitive
data content may be.
Instead, asymmetric ciphers work on
keys and hash outputs.
Their plaintext and ciphertext are typically 256 bits long,
and no more than 512 bits long —
32 to 64 bytes, maximum.
A digital signature provides
Proof of Content
and Proof of Origin.
Proof of Content comes from the hash function.
Even a singlebit change in the content should lead to
approximately 50% of the hash output bits changing.
The receiver knows the message content did not change.
Proof of Origin comes from the asymmetric
encryption and decryption.
When the receiver decrypts the signature using the purported
sender's public key, and finds a match to the message hash,
this verifies that the signature must have been created
with the sender's private key.
The receiver knows who sent the message.
Either RSA or ECC could be used to encrypt and create the
digital signature, and then to decrypt and verify it.
Let's see how RSA is used in digital signatures,
and then we'll see how the cipher works.
Follow the steps in the below procedure.
How Digital Signatures Work
Alice has a message for Bob. Alice wants to make sure that Bob can verify that the message came from Alice and has not been modified.
 Alice creates the message. If confidentiality is also needed, the message should be encrypted before continuing.
 Alice calculates the hash of the message, typically using SHA2256.
 Alice then encrypts the hash, using RSA or another asymmetric cipher. The encryption key is Alice's private key. No one else knows that key, so only Alice can do this operation in that specific way. The ciphertext output is the digital signature.
 The message and digital signature are transmitted to Bob. They could be two components of an email message, two files combined into one archive, two separate files to download from a server, as long as Bob ends up with both pieces. Metadata added to the signature explains which hash function, which asymmetric cipher, and the identity of the creator.
 Bob verifies the digital signature. The first step is calculating the hash of the received message, which is suspected of being modified, or being sent by someone masquerading as Alice, or both.
 Bob then decrypts the digital signature. The decryption key is Alice's public key. Bob needs to be certain that what he is using is really Alice's public key.
 If Bob finds that the received message hash is identical to the signature decryption output, he concludes that the message was not changed (because of the hash being so sensitive to even a singlebit change), and it really came from Alice (because decrypting with what he knows to be Alice's public key implies encryption with Alice's private key, which no one else knows).
PublicKey Infrastructure and Digital Certificates
The practical difficulty is that you must be absolutely certain that what you have really is the other party's public key.
Bob and Alice could meet facetoface and exchange public keys. However, this doesn't scale beyond a few local acquaintances with plenty of free time.
Instead, everyone's public key should be in the form of a digital certificate. That's a data structure containing information about the owner or "subject" (name, address, email address, URL, etc), their public key, and the name of the certificate issuer. We call the issuer the Certificate Authority or CA. All of certificate data structure is wrapped in a digital signature created by the CA, so the content and the issuer identity can be verified.
Public CAFailures
Everyone must completely trust the CA as an issuer of credentials — a trusted introducer, if you will. The CA says things like "Alice exists" and "The following is Alice's public key", and everyone believes it. This is a completely nontechnical human trust issue, confidence that the CA will never makes errors or tells lies. Sometimes this goes wrong.
Everyone then needs a copy of the CA's public key, which will be in the form of a digital certificate that they issued to themselves. This is a completely technical issue, confidence in the mathematics and logic meaning that the cryptography is strong enough.
CA/BrowserForum
All this is built into web browsers and email tools. The makers of Chrome, Firefox, and other browsers have decided that everyone should trust a group of rootlevel CAs such as Comodo, DigiCert, VeriSign, and others, and so their certificates are included in the browsers. Similarly, the Mozilla organization's Thunderbird and other email tools contain certificates.
Any organization can create its own PKI or PublicKey Infrastructure. They would establish an inhouse CA, and install its certificates in all of the organization's browsers and email tools.
Supporting Encryption with RSA
Another possible use for asymmetric ciphers would be to agree on a shared secret session key. That key would be used with AES or another symmetric cipher to encrypt some data.
Consider the above situation and diagram, where Alice is sending a message to Bob. If the message is sensitive and should be encrypted:
 Alice obtains a copy of Bob's public key. If it's in the form of a certificate from a CA that Alice trusts, then Alice can verify that it really is Bob's.
 Alice generates a random 256bit key to be used only for this one message or transferred file.

Alice creates a short message containing that key,
saying something like "Let's encrypt the data
using the AES cipher in CBC mode using key
0x34a09cc1eff4832...
", and then encrypts that message using Bob's public key. And really, only the session key itself needs to be encrypted. If we think we have to hide our choice of cipher and mode, then apparently we think we're using a weak choice, and Kerchoff's principle tells us that we should instead use a cipher without a known or suspected flaw. Claude Shannon reached a similar conclusion in the 1940s.  Alice encrypts the data itself according to the message.
 Alice sends the asymmetricencrypted key message combined with the symmetricencrypted data to Bob. This is hybrid cryptography, combining symmetric and asymmetric. In the scenario of the above diagram, that hybridencrypted message would be accompanied by its digital signature.
 Only Bob has a copy of Bob's private key. And so only Bob can decrypt the short key message. That explains how to decrypt the data, and so Bob decrypts and reads the file or message.
Ephemeral Keys and Perfect Forward Secrecy
The above explains how you could use RSA to agree on a shared secret session key. However...
Utah Data CenterConsider that your adversary might be recording every ciphertext message transmitted, in the hopes of eventually decrypting something.
If your longterm private key is ever exposed, then every session key created using the above procedure is exposed, and all the messages can be decrypted.
You instead should insist on only using ephemeral session keys. An ephemeral key is used only once, and if your private key is exposed some day, that can't be used to figure out what the ephemeral key was.
Using nothing but ephemeral keys provides Forward Secrecy, also called Perfect Forward Secrecy or just PFS. The concept is: "A breach today does not expose secrets protected in the past."
DiffieHellman key agreement ECDHE, or EllipticCurve DiffieHellman Ephemeral key agreementThe DiffieHellman algorithm lets two parties securely agree on an ephemeral shared secret key, this is called DHE. Classic DiffieHellman calculates exponential powers of large integers followed by modulo operation. ECDHE or EllipticCurve DiffieHellman Ephemeral key agreement can run much faster.
TLS 1.3 requires PFS and ephemeral keys agreed upon by either DHE or ECDHE.
However, there is still use for RSA! You don't want to exchange secrets with strangers. The key agreement stage needs authentication to prevent ManintheMiddle or MitM attacks. So, you combine DHE or ECDHE for the key negotiation with RSA or an ellipticcurve method for authentication.
So, let's see how RSA works.
How RSA Works
Setting up RSA keys
 Randomly select two distinct large prime numbers \( p \) and \( q \). These should be large numbers, similar in magnitude but differing in length by a few digits to make factoring even more difficult. For example, in base 10, a 615digit prime \(p\) and a 617digit prime \(q\) for a 1232digit \(n\), approximately \( 2 ^ {4096} \) and thus a 4096bit modulus or key size. Yes, the numbers become very large.

Compute: \( n = p \cdot q \)
\( n \) will be used as the modulus for both the private and public keys.
Security comes from: The difficulty of factoring the product of two large prime numbers.
 The ambiguity introduced by the modulo function.

Compute \( \lambda (n) \),
Carmichael's totient function for \(n\).
That's equal to the least common multiple
of \( (p1) \) and \( (q1) \):
\( \lambda (n) = l.c.m.(p  1, q  1) \)
You can compute \( l.c.m.(a, b) \) by first computing the greatest common divisor:
\( l.c.m.(a, b) = \frac{  a \cdot b  }{ g.c.d.(a, b) } \)
and so:
\( l.c.m.(p1, q1) = \frac{  (p1) \cdot (q1)  }{ g.c.d.((p1), (q1)) } \)

Choose an integer \( e \) such that:
 \( 1 < e < \lambda (n) \)

\( e \) and \( \lambda (n) \)
are coprime,
they share no factors other than 1.
A popular choice is
\( e = 2^{16} + 1 = 65537 \)
Some applications choose smaller \( e \) such as \( 3 \), \( 5 \), or \( 17 \), to make encryption and signature verification faster on small devices like smart cards. However, small values of \(e\) are less secure in some settings.

Compute \( d \) to satisfy the
congruence relation:
\( ( d \cdot e )\mod{\lambda (n)} = 1 \)
or, put another way:
\( d \cdot e = 1 + k \cdot \lambda (n) \)
for some integer \( k \).
Also note that in computing \( d \) in steps 35 you could use the Euler totient function:
\( \varphi (n) = ( p  1 ) \cdot ( q  1) \)
in place of:
\( \lambda (n) = l.c.m. ( p  1, q  1) \)
as it would be a common multiple instead of the least common multiple.
The exponent \( e \) and modulus \( n \) make up the public key.
\( d \) is the private key.
The first few chapters of Number Theory by George Andrews can give you plenty of background on the mathematics.
For a trivial example with very small prime factors, let's use: $$ \begin{aligned} p &= 5 \\ q &= 11 \\ n &= p \cdot q = 55 \\ \varphi ( n ) &= (p  1) \cdot (q  1) \\ & = 4 \cdot 10 \\ & = 40 \\ \lambda ( n ) &= l.c.m. (p  1, q  1) \\ &= l.c.m. (4, 10) \\ &= 20 \end{aligned} $$
We need: $$ 1 < e < \lambda (n) $$ where \(e\) and \( \lambda (n) \) are coprime, and so: $$ e \in \{3, 7, 9, 11, 13, 17, 19\} $$
\( d \) is defined by: $$ ( d \cdot e )\mod{20} = 1 $$ So, the possible key pairs are:
public \( n, e \) 
private \( d \) 
55, 3  7 
55, 7  3 
55, 9  9 
55, 11  11 
55, 13  17 
55, 17  13 
55, 19  19 
Using the keys for RSA encryption and decryption
 Sender obtains receiver's public key \( (n,e) \).
 Sender converts message M into a number \( m < n \) with an agreedupon reversible padding scheme. Since the point is usually to agree on a 256bit symmetric session key, or to encrypt a SHA2256 hash value to create a digital signature, the typical message is a 256bit unsigned integer, a number in the range \( \{ 0, 1, 2, ..., 2^{256}  1 \} \)

Sender computes ciphertext \( c \) using the
receiver's public key \(e\)
and the modulus \(n\) by:
\( c = ( m^e )\mod{n} \)  Sender transmits ciphertext to receiver.

Receiver calculates cleartext by using
their private key \(d\) and the modulus \(n\):
\( m = ( c^d )\mod{n} \)  Receiver reverses padding function to recover message M from cleartext \( m \).
As an almost as trivial example:

Choose prime factors:
$$ \begin{aligned} p &= 61 \\ q &= 53 \end{aligned} $$ 
Calculate modulus \(n\):
$$ \begin{aligned} n &= p \cdot q \\ & = 61 \cdot 53 \\ & = 3233 \end{aligned} $$ 
Calculate \( \lambda (n) \):
$$ \begin{aligned} \lambda (n) &= l.c.m. (p  1, q  1)\\ &= l.c.m. ( 60, 53 )\\ &= \left( \frac{  60 \cdot 53  }{ g.c.d. ( 60, 53 ) } \right)\\ &= \left( \frac{ 3339 }{ 1 } \right) \\ &= 3339 \end{aligned} $$ 
Select \(e\) and calculate \(d\):
$$ \begin{aligned} e &= 17 \\ d &= 2753 \end{aligned} $$ 
For message \( m = 123 \),
sender calculates and sends:
$$ \begin{aligned} c & = (123^{17})\mod{3233} \\ & = 337587917446653715596592958817679803\mod{3233} \\ & = 855 \end{aligned} $$ 
Receiver then calculates:
$$ \begin{aligned} m &= (855^{2753})\mod{3233} \\ & = 123 \end{aligned} $$
The number \(855^{2753}\) is enormous,
approximately \( 5 \times 10^{8071} \),
but you can do these calculations with the
bc
command.
Leave off the common l
option so it will be
set up for large integer arithmetic rather than floatingpoint:
$ bc (123^17) % 3233 855 (855^2753) % 3233 123
PostQuantum Cryptography
Asymmetric ciphers rely on "trapdoor problems", math problems that are enormously more difficult to solve in one direction than the other. RSA uses the factoring problem, ellipticcurve cryptography relies on the difficulty of the discrete logarithm problem.
If an attacker could factor an RSA modulus \(n\) into its prime factors \( p \cdot q \), they could use the public key \(e\) to derive the private key \(d\). We are gambling on two assumptions to keep us safe.
First, that factoring is and will remain too difficult — factoring \( n = p \cdot q \) would always take too long. Either the attacker would get frustrated and give up, or if they did keep at it until they succeeded, it would have taken so long that we no longer care about those secrets. Factoring and prime numbers have fascinated mathematicians since Ancient Greece, so we aren't too worried about a sudden mathematical discovery.
Second, that no sidechannel attack will be discovered — no one will figure out an alternative method to find the private key \(d\) without having to factor \( n = p \cdot q \). RSA is intentionally simple enough that everyone feels reasonably comfortable about this assumption. But you can't prove the nonexistence of this type of attack.
Peter Shor's initial publication of his algorithm, 1994 An update to Shor's original paper, 1995 Increasing the speed of Shor's algorithm, 1998There is, however, a growing third worry. Algorithms have been devised to solve some enormously difficult problems when run on a generalpurpose quantum computer. One example is Shor's algorithm. It could solve the factoring problem in polynomial time, an enormous speedup. More recent work has shown that it could also be used to solve the discrete logarithm problem used by ECC. We don't yet have a generalpurpose quantum computer, one that has enough stable cubits to solve nontrivial problems and run Shor's algorithm. But advances continue.
In 2015 the NSA announced that ECC wasn't a backup for RSA when facing the threat of quantum computing cryptanalysis, to the point that government agencies and contractors considering a migration from RSA to ECC shouldn't bother. They later modified the page, and later yet they took it down, see the archived update here.
We need postquantum or quantumsafe or quantumresistant asymmetric ciphers. Several families of postquantum cipher algorithms are being explored: latticebased cryptography, codebase cryptography, multivariate polynomial cryptography, and others. See the PostQuantum Crypto conference series for details.
U.S. NIST started a project to standardize PostQuantum Cryptography algorithms in 2016. They hope to have draft standards out in 2022 to 2024.
The Open Quantum Safe project is an opensource project supporting the development and prototyping of quantumsafe or quantumresistant cryptographic algorithms. They have the opensource liboqs C library ready for download and use, along with prototype integrations into protocols and applications including OpenSSL. See the 2016/2017 paper for a detailed description of the project.
Postquantum asymmetric cryptography would be used only to encrypt a randomly generated session key that will be used with a symmetric cipher. Symmetric ciphers are thought to be relatively safe against quantum computing attacks. Grover's algorithm on a quantum computer would speed up the search for a symmetric key, but only to the point that keys would need to be doubled in length to preserve the same resistance to attack. See Daniel J. Bernstein's paper Grover vs. McEliece for applications of Grover's algorithm to other cryptosystems.
Quantum Key Distribution
The only alternative to a quantumsafe or quantumresistant asymmetric cipher requires physics.
Quantum Key Distribution or QKD is a physicsbased method to securely communicate a randomly selected symmetric key to the other party.
QKD uses singlephoton signaling between the legitimate users at either end of a fibre link. This involves either polarized single photons in the BB84 protocol, or entangled photon pairs in the E91 protocol. An intruder could tap the fibre and monitor the key exchange, but that would corrupt the signal and warn both ends that the key was compromised and must not be used.
For a discussion of its security, see "The security of practical quantum key distribution", Reviews of Modern Physics, 81, pg 1301, 29 Sep 2009 (also here). For a rebuttal of its supposed absolute security, see Dan Bernstein's paper: "Is the security of quantum cryptography guaranteed by the laws of physics?"
Many people think it sounds like science fiction or at least impractical, but it's been in use since 2004. In that year it was used to protect a transaction between the Vienna City Hall and the headquarters of Bank Austria Creditanstalt.
That seems to me to have been a proof of concept organized by the city to support development in a local university. But since 2007 the government of Geneva, Switzerland, has used QKD to protect election results.
In 2007, China began deploying a QKD network in Beijing. A larger network with over 45 nodes began operating in Hefei in 2010. Another large network began operating in Jinan in 2014, joining 28 organizations, including government agencies such as the China Banking Regulatory Commission plus commercial customers including the China Industrial and Commercial Bank, and the Xinhua News Agency. In 2016 China was planning to complete the world's longest QKD network with a 2000kilometer backbone joining Beijing, Jinan, Hefei, and Shanghai.
In 2010, Japan began operating a QKD network developed by NEC, Toshiba, NTT and others and joining several nodes in Tokyo.
In 2013, Battelle Memorial Institute deployed a QKD network joining its headquarters in Columbus, Ohio, to a manufacturing facility 20 miles away.
In 2015 ETSI, the European Telecommunications Standards Institute, published a number of quantum key distribution specifications.
In 2016, a South Korean QKD network began operating between Seoul, Bundang, and Suwon.
In 2016, China was working on QKD between satellites and ground stations. See "China's quantum space pioneer: We need to explore the unknown", Nature, 13 Jan 2016.
In 2017, China demonstrated QKD between orbit and the ground in their Liángzĭ kēxué shíyàn wèixīng or Quantum Experiments at Space Scale. The Chinese Academy of Sciences operates the Micius satellite and the Chinese ground stations, the University of Vienna and the Austrian Academy of Sciences run the European ground stations.
Wikipedia Science Nature BBC Reuters CNBC
By 2020, the range was extended to over 1,100 kilometers.
ID Quantique in Geneva, Switzerland, sells QKD systems plus randomnumber generators based on quantum physics.