Skip to main content
Engineering LibreTexts

8.11: RSA Public Key Encryption

  • Page ID
    48341
    • Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
    • Google and Massachusetts Institute of Technology via MIT OpenCourseWare
    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Turing’s code did not work as he hoped. However, his essential idea—using number theory as the basis for cryptography—succeeded spectacularly in the decades after his death.

    In 1977, Ronald Rivest, Adi Shamir, and Leonard Adleman at MIT proposed a highly secure cryptosystem, called RSA, based on number theory. The purpose of the RSA scheme is to transmit secret messages over public communication channels. As with Turing’s codes, the messages transmitted are nonnegative integers of some fixed size.

    Moreover, RSA has a major advantage over traditional codes: the sender and receiver of an encrypted message need not meet beforehand to agree on a secret key. Rather, the receiver has both a private key, which they guard closely, and a public key, which they distribute as widely as possible. A sender wishing to transmit a secret message to the receiver encrypts their message using the receiver’s widelydistributed public key. The receiver can then decrypt the received message using their closely held private key. The use of such a public key cryptography system allows you and Amazon, for example, to engage in a secure transaction without meeting up beforehand in a dark alley to exchange a key.

    Interestingly, RSA does not operate modulo a prime, as Turing’s hypothetical Version 2.0 may have, but rather modulo the product of two large primes—typically primes that are hundreds of digits long. Also, instead of encrypting by multiplication with a secret key, RSA exponentiates to a secret power—which is why Euler’s Theorem is central to understanding RSA.

    The scheme for RSA public key encryption appears in the box.

    If the message \(m\) is relatively prime to \(n\), then a simple application of Euler’s Theorem implies that this way of decoding the encrypted message indeed reproduces the original unencrypted message. In fact, the decoding always works—even in (the highly unlikely) case that \(m\) is not relatively prime to \(n\). The details are worked out in Problem 8.81.

    RSA Cryptosystem

    A Receiver who wants to be able to receive secret numerical messages creates a private key, which they keep secret, and a public key, which they make publicly available. Anyone with the public key can then be a Sender who can publicly send secret messages to the Receiver—even if they have never communicated or shared any information besides the public key.

    Here is how they do it:

    Beforehand The Receiver creates a public key and a private key as follows.

    1. Generate two distinct primes, \(p\) and \(q\). These are used to generate the private key, and they must be kept hidden. (In current practice, \(p\) and \(q\) are chosen to be hundreds of digits long.)
    2. Let \(n ::= pq\).
    3. Select an integer \(e \in [0..n)\) such that \(\text{gcd}(e, (p - 1)(q - 1)) = 1\). The public key is the pair \((e, n)\). This should be distributed widely.
    4. Let the private key \(d \in [0..n)\) be the inverse of \(e\) in the ring \(\mathbb{Z}_{(p - 1)(q - 1)}\). This private key can be found using the Pulverizer. The private key \(d\) should be kept hidden!

    Encoding To transmit a message \(m \in [0..n)\) to Receiver, a Sender uses the public key to encrypt \(m\) into a numerical message

    \[\nonumber \hat{m} ::= m^e (\mathbb{Z}_n).\]

    The Sender can then publicly transmit \(\hat{m}\) to the Receiver.

    Decoding The Receiver decrypts message \(\hat{m}\) back to message \(m\) using the private key:

    \[\nonumber m = \hat{m}^d (\mathbb{Z}_n).\]

    Why is RSA thought to be secure? It would be easy to figure out the private key \(d\) if you knew \(p\) and \(q\)—you could do it the same way the Receiver does using the Pulverizer. But assuming the conjecture that it is hopelessly hard to factor a number that is the product of two primes with hundreds of digits, an effort to factor n is not going to break RSA.

    Could there be another approach to reverse engineer the private key \(d\) from the public key that did not involve factoring \(n\)? Not really. It turns out that given just the private and the public keys, it is easy to factor \(n\) 15 (a proof of this is sketched in Problem 8.83). So if we are confident that factoring is hopelessly hard, then we can be equally confident that finding the private key just from the public key will be hopeless.

    But even if we are confident that an RSA private key won’t be found, this doesn’t rule out the possibility of decoding RSA messages in a way that sidesteps the private key. It is an important unproven conjecture in cryptography that any way of cracking RSA—not just by finding the secret key—would imply the ability to factor. This would be a much stronger theoretical assurance of RSA security than is presently known.

    But the real reason for confidence is that RSA has withstood all attacks by the world’s most sophisticated cryptographers for nearly 40 years. Despite decades of these attacks, no significant weakness has been found. That’s why the mathematical, financial, and intelligence communities are betting the family jewels on the security of RSA encryption.

    You can hope that with more studying of number theory, you will be the first to figure out how to do factoring quickly and, among other things, break RSA. But be further warned that even Gauss worked on factoring for years without a lot to show for his efforts—and if you do figure it out, you might wind up meeting some humorless fellows working for a Federal agency in charge of security. . . .

    15In practice, for this reason, the public and private keys should be randomly chosen so that neither is "too small".


    This page titled 8.11: RSA Public Key Encryption is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .