> ## Content Index > Fetch the complete content index at: https://sudosecurity.org/llms.txt > Use this file to discover other available public pages before exploring further. # A Small Introduction to RSA Encryption & the Mathematics - URL: https://sudosecurity.org/introduction-to-rsa-encryption/ - Published: 2021-11-01T04:00:00.000Z - Updated: 2026-07-17T10:55:01.000Z - Author: Traven - Tags: Cryptography RSA Encryption has always been amazing to me. It allows you to publish an encryption key – also known as *`e`* – without having to compromise your decryption key – known as *`d`*. One amazing feat that I find the most interesting is that generally in practice that *`e`* is usually always the same number as follows. ``` e = 65537 ``` I will do a small review of RSA, explain how this default e was chosen, and discuss why this may or may not be a problem. ## How does RSA Encryption Work? This is a very basic rundown of how RSA encryption works. 1. First, we need to select two very large prime numbers. They will become our *`p`* and *`q`*. 2. Then we need to compute `*n* = *pq*` and `φ(*n*) = (*p* − 1)(*q* − 1)`. 3. After that we now choose an encryption key `*e*` relatively prime to `φ(*n*)`. 4. Then the fun part is to calculate the decryption key *`d`* such that `*ed* = 1 (mod φ(*n*))`. 5. Finally, we can now publish *`e`* and *`n`*, and keep *`d`*, *`p`*, and *`q`* secret. Now you may be asking where the asymmetry in the encryption scheme comes from? It is from the fact that the person who knows *`p`* and *`q`* is able to compute `*n*, φ(*n*)`, and *`d`* easily – better yet knows the decryption key – while no one else can find *`d`* without knowing or being able to factor *`n`*. ## What is the Encryption Exponent of RSA? We are mainly going to focus on the third step of the RSA Encryption that I explained earlier above. In theory, the *`e`* could be extremely large – but it happens that most of the time that `*e* = 65537` instead. If this is the case, then we do not actually choose what `*e*` is going to a prime to `φ(*n*)`. However, we do pick the *`p`* and `*q*` and then in `φ(*n*)` will usually be the common prime `65537`. Here's the fun part, if the prime is not `65537` then we can choose the *`p`* and `*q*` again until `gcd(65537, φ(*n*)) = 1`. The general idea is as follows a small excerpt from [one of my college textbooks](https://www.amazon.com/Introduction-Number-Cryptography-Textbooks-Mathematics/dp/1138063479?ref=sudosecurity.org)... > … surprisingly, *`e`* does not have to be large. Sometimes `*e* = 3` has been used, although it is usually recommended that larger values be used. In practice, the most common value is `*e* = 65537`, The advantages are that `65537` is a relatively large prime, so it’s easier to arrange that `gcd(*e*, φ(*n*)) = 1`, and it is one more than a power of `2`, so raising a number to the 65537th power consists mostly of squarings … We do have to remember – then also never forget at the same time – value of *`e`* was chosen for mainly for the efficiency. Also, there aren’t many choices for similar values of `*e* [3]`. Heninger and Shacham go into[ more detail in their paper](https://eprint.iacr.org/2008/510.pdf?ref=sudosecurity.org). > The choice `*e* = 65537 = 216 + 1` is especially widespread. Of the certificates observed in the UCSD TLS 2 Corpus (which was obtained by surveying frequently-used TLS servers), 99.5% had `e = 65537`, and all had *`e`* at most 32 bits. So, this ends up with the *most common value* mentioned by Kraft and Washington appearing to be *used 99.5%* of the time in RSA Encryption. ## Why Do We Use `65537` as the Prime? It is technically fine to use a larger prime number as your `*e*`, but this one is chosen because it is just the right sized one. This means that a higher prime number would make the public RSA operation – such as encryption or signature verification – slower. Some of the lower primes like `e = 3` would make the operation appreciably faster – roughly just about eight times as fast. If using a proper padding scheme, the choice of *`e`* is not known to make a difference in security. A lot of people consider that security through obscurity. For the padding schemes that are using high values of *`e`* \-- compared to the number of bits in the public modulus of `n` – are generally a safer choice. `e = 65537` is chosen to be the common compromise between being high and increasing the cost of raising to the *`e`* power. If we choose any higher odd *`e`* cost at least one more multiplication – or squaring in case. Which does make it true for odd exponents of the form `2k+1`. Also, `e = 65537` is prime, which slightly simplify generating a prime `p` suitable as RSA modulus, implying `gcd(p−1,e)=1`, which reduce `p≢1(mode)` for prime *`e`* . Only the [Fermat primes](https://en.wikipedia.org/wiki/Fermat%5Fnumber?ref=sudosecurity.org) such as `3, 5, 17, 257, 65537` have both properties, and all are common choices of *`e`* . It is generally assumed that there are no other Fermat prime – and if there was any, it would we unusably higher compared to the ones which we do know of already. ## What Protections does `65537` offer? Using `e = 65537` in RSA is an ***extra*** precaution against a variety of attacks that are possible when bad message padding is used – these attacks tend to be more likely or devastating with much smaller `e`. Using `e = 3` would otherwise be attractive, since raising to the power `e = 3` cost 1 squaring and 1 multiplication, to be compared to 16 squaring and 1 multiplication when raising to the power `e = 65537 = 2^16 + 1`. For example, RSA with `e = 65537` has a security advantage over e=3e=3 when: 1. Sending a message naively encrypted as `ciphertext = plaintext^e mod n`. The greater `e` makes it more likely that `log 2 (plaintext) ≫ log 2 (n) /e` ends up being way better for security. 2. Sending the same message encrypted to `k` recipients using the same padding – including any deterministic padding independent of `n` – the greater `e` makes it less likely that `k ≥ e` – which allows a break. 3. Signing messages chosen by the adversary with a bad signature scheme. For example, with the scheme of the (withdrawn) ISO/IEC 9796 standard (described in [HAC section 11.3.5](https://cacr.uwaterloo.ca/hac/about/chap11.pdf?ref=sudosecurity.org#page=19)), the adversary could obtain a forged signature from only 1 legitimate signature if `e = 3`, but needs 3 legitimate signatures for `e = 65537`. The security advantage of `e = 65537` is wider for [attacks](https://eprint.iacr.org/2009/203.pdf?ref=sudosecurity.org) against scheme 1 of the [ISO/IEC 9796-2](https://webstore.iec.ch/preview/info%5Fisoiec9796-2%7Bed3.0%7Den.pdf?ref=sudosecurity.org). For more explanations and examples of the risk of the *combination* of questionable message padding and low `e`, see section 4 in Dan Boneh's [Twenty Years of Attacks on the RSA Cryptosystem](https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf?ref=sudosecurity.org). ## Could this be a Problem? Is `e` being the same number about 99.5% of the time be an issue with RSA Encryption? I am going to say no, because the `e` is a public knowledge part of the encryption standard. The idea is that it doesn't seem to be harmful since it is selected before you even choose what your *`p`* and *`q`* is ever going to be. There could possibly be a problem – only by my standards of the mathematical principles behind encryption – where the prime number is relatively small. Yet with it being smaller, it does give an algorithm for recovery of private RSA keys when some of the bits are known – this is also while the exponent `e` is small. How would some of the bits be known though? If a person had physical access to a computer, then they can recover some of the bits from the memory of the device. Yet, this is a story for another day or another article in the future.