RSA Algorithm Explained: Key Generation, Encryption, and Signatures (2026)

The RSA algorithm is fundamentally a mathematical trick, not a cryptographic one, leveraging the difficulty of factoring large numbers to secure communications.

Imagine you want to send a secret message to your friend Alice. RSA allows you to do this securely, even if an eavesdropper, Eve, is listening to your conversation. It’s built on two main ideas: public-key cryptography and the difficulty of factoring.

Public-Key Cryptography

Unlike traditional symmetric encryption where both parties share a secret key (like a lock and its single key), public-key cryptography uses a pair of keys: a public key and a private key.

• Public Key: This is like an open mailbox. Anyone can drop a letter (encrypted message) into it. You can share this key freely.
• Private Key: This is like the key to your mailbox. Only you have it, and it’s used to retrieve the letters (decrypt messages). You must keep this secret.

So, if Alice wants to receive secret messages, she generates a public/private key pair. She gives her public key to everyone, including you. You then use her public key to encrypt your message. Only Alice, with her corresponding private key, can decrypt and read it.

The Math Behind RSA: Prime Numbers and Factoring

RSA’s security hinges on the mathematical relationship between large prime numbers and the difficulty of their factorization.

1. Key Generation:

   • Choose Two Large Prime Numbers: Let’s call them p and q. For real-world RSA, these are hundreds of digits long. For our example, let’s pick small primes: p = 61 and q = 53.
   • Calculate n: This is the modulus, and it’s the product of p and q. n = p * q = 61 * 53 = 3233. This n will be part of both your public and private keys.
   • Calculate Euler’s Totient Function (φ(n)): This is φ(n) = (p-1) * (q-1). For our primes, φ(n) = (61-1) * (53-1) = 60 * 52 = 3120. This value is crucial but kept secret.
   • Choose Public Exponent e: This is a number that is greater than 1, less than φ(n), and is coprime to φ(n) (meaning their greatest common divisor is 1). A common choice for e is 65537, but for our small example, let’s pick e = 17. (GCD(17, 3120) = 1).
   • Calculate Private Exponent d: This is the modular multiplicative inverse of e modulo φ(n). In simpler terms, d is a number such that (d * e) mod φ(n) = 1. We need to find d such that (d * 17) mod 3120 = 1. Using the Extended Euclidean Algorithm (or by trial and error for small numbers), we find d = 2753.

   Now we have our keys:

   • Public Key: (n, e) = (3233, 17)
   • Private Key: (n, d) = (3233, 2753)

   Alice would publish (3233, 17) and keep (3233, 2753) secret.

2. Encryption: Suppose you want to send a message, represented by a number M, to Alice. The message M must be less than n (so M < 3233). Let’s say your message is M = 123. You use Alice’s public key (n, e) to encrypt M: Ciphertext (C) = M^e mod n C = 123^17 mod 3233 Calculating this (often done with specialized libraries for efficiency): C = 855

   You send the ciphertext 855 to Alice.

3. Decryption: Alice receives the ciphertext C = 855. She uses her private key (n, d) to decrypt it: Original Message (M) = C^d mod n M = 855^2753 mod 3233 Calculating this: M = 123

   Alice successfully recovers your original message!

Why is it Secure?

Eve, the eavesdropper, sees your public key (3233, 17) and the ciphertext 855. To decrypt, she would need Alice’s private key d. To find d, she needs φ(n), which is 3120. To find φ(n), she needs the prime factors p and q of n = 3233.

The security of RSA relies on the fact that it is computationally infeasible to find the prime factors p and q of a very large number n. If n is, say, 2048 bits long, factoring it would take an astronomical amount of time and computational power, far beyond current capabilities.

Digital Signatures

RSA can also be used for digital signatures, providing authentication and integrity. Instead of encrypting with the public key and decrypting with the private key, you do the opposite:

1. Signing: You take a hash of your message (a fixed-size digest) and "encrypt" it with your own private key. This encrypted hash is your signature. Signature (S) = hash(M)^d mod n
2. Verification: Anyone can verify your signature. They take the original message M, compute its hash, and then "decrypt" your signature S using your public key. If the decrypted hash matches the computed hash of the message, the signature is valid. hash(M) == hash(S^e mod n)

This proves two things:

• Authentication: Only the holder of the private key d could have created that signature.
• Integrity: If the message M was altered after signing, the computed hash would not match the decrypted hash from the signature.

The most surprising true thing about RSA is that the "encryption" step for signatures is mathematically identical to the decryption step for messages, just with the roles of public and private exponents reversed.

The next frontier after understanding RSA is exploring its vulnerabilities, such as the timing attacks that can reveal the private key if not implemented carefully.