Crypto Comics - What is 65537
I tried to explain what 65537 is in comic strips.
TL;DR
I explained what 65537 is and how it will be used in a particular situation.
Some Takeaway
65537 is a starting point of the RSA public-key encryption value. RAS refers to Ron Rivet, Adi Shamir, and Lenord Adleman who described the algorithm in 1977. 65537 is a large enough number to start with yet provides security of such encryption. 65537 or F4 is a prime number of form 2^(2^n)+1 when n=4. The number is large enough without being computationally expensive with no advantage to security.
How RSA works
To set up RSA you need to do the following steps:
Select two very large prime numbers p and q
Compute n = pq and f(n) = (p-1)(q-1)
Choose an encryption key e relatively prime to f(n)
Calculate the decryption key d so that ed=1(mod(f(n)))
Publish e and n and keep d, p, and q in secrete
Since e = 65537 and it is revealed to the public, there is no problem to compromise security. Also, e and n are components of the public key anyway. And d, p, and q are components of the private key.
How to Break RSA
Cracking an RSA below 128-bit prime numbers is pretty easy. The iteration of the guess prime number is fairly quick depending on your computational power. Nonetheless, modern RSA is likely to use 1024-bit or 2084-bit prime numbers to gear up its security. The method is called a chosen-plaintext attack or (CPA).
The process of such attack may involve:
The attacker chooses n plaintexts
The attacker sends n plaintexts to the encryption oracle
The encryption oracle encrypt plaintexts
The attacker receive response encrypt plaintexts and corresponds to each plaintext
The attacker then attempts to extract the key between oracle encode
You can see that it is an iterative process and time-consuming but doable when prime numbers are lower value.
65537 is Too Small
The largest prime number yet to be discovered is 2^82,589,933-1 which has 24,862,048 digits. However, it does not make RSA more secure but less efficient. 65537 is good enough even though it is the largest number that seems small. But the algorithm depends on p, q large prime numbers rather than solely on the number e.
In conclusion
65537 is a magic number for RSA encryption. It is a common practice to use it as it is and it does not matter to reveal to the public as part of the public key component.
