Hello readers,
Michael here, and in today’s post, we’re exploring a special topic-the mathematics behind encryption algorithms. More specifically, we’ll explore the mathematics behind the RSA asymmetric-key encryption algorithm that we discussed in the post 6 (honestly wanted to write this post because I love math and think the mathematics behind encryption algorithms are interesting).
The mathematical public exponent
Before we dive into the mathematics of encryption, let’s review what the public exponent does! As I mentioned in 6, the public exponent is a crucial part of the RSA algorithm’s public key that is utilized to verify both data encryption and access signatures for anyone trying to access the data.
I also mentioned the use of the number 65537 as a public exponent. Why is that such a common value for the public exponent? Well, 65537 is what’s known as a Fermat number.
The fun Fermat numbers
What exactly is a Fermat number? A simple explanation would be that a Fermat number is an integer that can be derived from the following expression:
The x in this case represents any positive integer, including 0. In simple terms, a Fermat number can be derived from 2 to the power of 2^x plus 1. The first five Fermat numbers are 3, 5, 17, 257 and 65537-pretty impressive range if I do say so myself.
Now, fun historical nerdy fact for this post-Fermat numbers were named after 17th century French mathematician Pierre de Fermat who first discovered these numbers. He’s also known for his early contributions to calculus, number theory, and probability, among other fields.
One of his more notable mathematical contributions is Fermat’s last theorem, which can be best described with this equation:
de Fermat stated that there are no three positive integers for a, b, and c that can satisfy this equation if n is greater than 2 (quite the opposite of the Pythagorean theorem where a^2+b^2=c^2).
- Fermat numbers aren’t required as public exponents for RSA keys but they are quite practical. They allow for efficient encryption and decryption and are more secure than non-Fermat numbers.
Now, how does this relate to RSA?
Good question. The magic number 65,537 (the default public exponent for RSA keys) is the perfect public exponent for RSA public keys because for one, it’s a prime number (and prime numbers usually make better public exponents), and for two, its neither too small nor too large of a public exponent.
Smaller public exponents like 3, 5 and 17 would make the data more vulnerable to attacks since hackers could use these low public exponents to decrypt the data without knowing the private key. On the other hand, a larger public exponent like 4,294,967,297 utilizes a lot of computing power while providing no significant security advantage. The public exponent 65,537 strikes the perfect balance between secure encryption and computational overhead.
Another thing worth noting about public exponents is that if you’re trying to figure out a good public exponent to use for your RSA encryption algorithm, prime numbers will do the trick (more so if they are Fermat prime numbers), as they provide mathematical efficiency (after all, prime numbers are only divisible by 1 and themselves) and more security during the encryption/decryption process since they make it much harder for hackers to figure out the public exponent and in turn, the RSA keys.
Thanks for reading,
Michael