Understanding RSA: A Simple Guide to Public-Key Math

Source: Dev.to

RSA Basics

RSA (Rivest–Shamir–Adleman) is a public‑key cryptographic algorithm. It uses a public key to encrypt data and a corresponding private key to decrypt it, enabling secure transmission and digital signatures.

Key Generation

1. Choose two large prime numbers p and q.

2. Compute n = p × q.

3. Find the totient of n:

   [ \phi(n) = (p-1)(q-1) ]

   The totient counts the integers less than n that are relatively prime to n.

   Example:

   • (\phi(11) = 10) because the numbers 1‑10 are all relatively prime to 11.
   • (\phi(12) = 4) because only 1, 5, 7, 11 are relatively prime to 12.

4. Choose an integer e (the public exponent) such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.

5. Compute the private exponent d as the modular inverse of e modulo φ(n):

   [ d \equiv e^{-1} \pmod{\phi(n)} ]

Encryption and Decryption

If the plaintext message is m and the ciphertext is c:

• Encryption:

  c = m^e mod n

• Decryption:

  m = c^d mod n

Example

Let p = 7 and q = 17, so n = 7 × 17 = 119.

[ \phi(n) = (7-1)(17-1) = 96 ]

Choose e = 53 (relatively prime to 96).

• Encrypt the message m = 7 (ASCII for “H”):

  c = 7^53 mod 119 = 28

• Decrypt:

  m = 28^29 mod 119 = 7

The decrypted value matches the original plaintext.

Why RSA Is Secure

In practice, the primes p and q are hundreds of bits long (e.g., 2048‑bit RSA). Knowing only e and n does not reveal φ(n) without factoring n into p and q, which is computationally infeasible for sufficiently large keys.

A “2048‑bit RSA” key means n is a 2048‑bit integer (maximum value ≈ (2^{2048} - 1)), making factorisation practically impossible with current technology.

Implementation

A simple Java implementation is available for experimentation. Below is a minimal example (the full source and README are provided in the original repository).

// RSAExample.java
import java.math.BigInteger;
import java.security.SecureRandom;

public class RSAExample {
    public static void main(String[] args) {
        // Generate two large prime numbers
        SecureRandom rnd = new SecureRandom();
        BigInteger p = BigInteger.probablePrime(1024, rnd);
        BigInteger q = BigInteger.probablePrime(1024, rnd);

        BigInteger n = p.multiply(q);
        BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

        // Choose public exponent e
        BigInteger e = BigInteger.valueOf(65537); // common choice
        while (!phi.gcd(e).equals(BigInteger.ONE)) {
            e = e.add(BigInteger.TWO);
        }

        // Compute private exponent d
        BigInteger d = e.modInverse(phi);

        // Example message
        BigInteger m = new BigInteger("123456789");
        BigInteger c = m.modPow(e, n); // encryption
        BigInteger decrypted = c.modPow(d, n); // decryption

        System.out.println("Original: " + m);
        System.out.println("Encrypted: " + c);
        System.out.println("Decrypted: " + decrypted);
    }
}

Common Risks and Mitigations

By following these best practices—choosing large primes, employing proper padding, and using adequate key lengths—RSA remains a robust foundation for secure communication.