Noë Flatreaud

Last update

• 10 Aug, 2025 A Thing or Two About RSA

  RSA (Rivest-Shamir-Adleman) is the first and still one of the most common asymmetric encryption scheme. While being used almost everywhere by almost everyone, not many seems to really understand what RSA stands really for. Obviously, it would be difficult for me to explain every bits in a one page article. So let me give you a thing or two, just enough to, I wish, motivate you to dig deeper.

  About Public Key Cryptography

  Public key cryptography, also known as asymmetric cryptography, is a cryptographic system that uses pairs of keys to identify, authenticate and encrypt data over and insecure channel. We may find it in many modern security protocols, including TLS and PGP.

  1. Each user generates a pair of keys, a public key Pk, shared openly, and a private key Sk kept secret.
  2. When Alice wants to send a message to Bob, she uses Bob's public key to encrypt it, so that only he can decrypt the ciphertext.
  3. Upon receiving it, Bob uses his private key to decrypt the ciphertext, revealing it’s original content.

  The Need for a Trapdoor

  The system relies on mathematical problems that are easy to solve in one direction but extremely difficult to solve in the reverse direction. In simple words, what we need is a Trapdoor function - very easy to compute in one way and nearly impossible the other that has a tiny piece of information (the "trapdoor") to easily reverse the process.

  Primer on RSA Encryption.

  Here, the whole security is based on the mathematical properties of large prime numbers and modular arithmetic. So yes, we might need to refresh some concepts beforehand. I'll assume you at least know about prime numbers and their properties.

  Two numbers are coprime if their greatest common divisor (gcd) is 1. In other words, they share no common factors other than 1. Example: 3 and 5 are coprime because gcd(3,5)=1.

  For a given integer n, Euler's totient function, denoted as ϕ(n), counts the number of integers up to n that are coprime with n. Example: ϕ(6)=2 because the numbers [1,5] are coprime with 6.

  Modular arithmetic is a system for integers, where numbers "wrap around" after reaching a certain value, known as the modulus. Example: Seconds, Minutes are modulo 60 and Hours modulo 24.

  RSA Key Creation

  Now that we’ve seen the building blocks, let's get our hands dirty. To build RSA keys, you first need to :

  1. Choose Two Large Prime Numbers (p and q): These primes should be large, random and distinct. Smaller primes can be easily factored and closer primes can be reduced.

  2. Compute n = p x q, n is used as the modulus for both the public and private keys.

  3. Compute ϕ(n)=(p−1)×(q−1), the Euler’s totient, used to determine the public exponent.

  4. Choose an Integer e such that 1 < e < ϕ(n) and gcd(e,ϕ(n)), It will later be known as the public exponent.

  5. Compute d = e−1 mod ϕ(n), the private exponent and modular multiplicative inverse of e modulo ϕ(n) (because e and ϕ(n) are coprimes).

  The tuple (e,n) are known as public parameters, and (d,n) private parameters, which forms, a public/private keypair.

  Sk = (d, n) <— Used for Decryption and Signing
  Pk = (e, n) <— Used for Encryption and Verification
  

  RSA Encryption

  To encrypt a message M, Bob uses Alice's public key ( Pk) :

  C = M^e mod n

  Where C is the ciphertext and (e, n) is Alice’s public parameters.

  To reverse it, Alice uses her private key to decrypt Bob’s message.

  M=C^d mod n

  Where M is Bob's original message, and (d, n) is Alice’s private parameters.

  Some security issues

  While robust, RSA is far from immune to attacks, in fact we have plenty to have some fun. Aside from brute force, you can use :

  A Factorization Attack : If an attacker can factor n into p and q, they can then re-compute the private key.
  

  A Chosen Ciphertext Attack : Attacker can choose ciphertexts to be decrypted and uses the results to gain information about private key
  

  A Small Exponent Attack : Using a small public exponent e can make the system vulnerable to certain types of attacks.
  

  You may also see some trickier but still juicy stuff with :

  Fermat's Attack - If the prime numbers p and q are close to each other, N can be factorized using Fermat's method, making RSA vulnerable.

  Pollard's p − 1 Algorithm factorizes values into their prime number roots when p−1 is powersmooth.

  Wiener's Attack (As like to call it peepee pewpew) involves a short decryption exponent and uses continued fractions.

  ROCA (Return of the Coppersmith Attack): Allows an RSA private key to be recovered kowing the public key.

  RSA has, again, a lot more to offer, from zero-knowledge proofs, hybrid systems, partial homomorphic encryption, blind signatures and stuff, but that’s unfortunately all I can explain to you, in one page, without making it too unbearable, hope you found it relevant or interesting, please have fun making your own implementation of this algorithm at home, but keep away crappy, unaudited libraries that reinvents the wheel for the thousandth time.

  Ref. Buchanan, William J (2025). RSA. Asecuritysite.com. https://asecuritysite.com/rsa/

↑ back to top