A Small Introduction to RSA Encryption & the Mathematics

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...

… 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.

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 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), 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 against scheme 1 of the ISO/IEC 9796-2.

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.

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.