Deep Dive into RSA: How It Works and Why It’s Secure

RSA Overview

RSA is a widely used public‑key encryption algorithm named after its inventors Ron Rivest, Adi Shamir and Leonard Adleman (1977). Its security relies on the difficulty of factoring large composite numbers and related mathematical problems.

Core Idea

The algorithm uses a key pair: a public key that anyone can use to encrypt data, and a private key that only the owner can use to decrypt, ensuring that only the private‑key holder can recover the original message.

Mathematical Foundations

Understanding RSA requires several concepts:

Prime numbers : integers greater than 1 divisible only by 1 and themselves.

Coprime : two integers whose greatest common divisor is 1.

Modular arithmetic : the remainder after division.

Euler’s totient function φ(n) : the count of integers less than n that are coprime to n.

Key Generation

The steps are:

Select two large, distinct primes p and q.

Compute the modulus n = p × q; n is part of both keys and is public.

Calculate φ(n) = (p‑1)·(q‑1); this value is kept secret.

Choose an encryption exponent e such that 1 < e < φ(n) and e is coprime to φ(n).

Find the decryption exponent d satisfying e·d ≡ 1 (mod φ(n)) (the modular inverse of e).

The resulting public key is (n, e) and the private key is (n, d).

Encryption Process

To encrypt a plaintext message M (where M < n), compute the ciphertext C = M^e mod n. Anyone can perform this operation using the public key.

Decryption Process

The private‑key holder recovers the plaintext by computing M = C^d mod n. Without the private key, the ciphertext cannot be feasibly decrypted.

Security Considerations

Key length : Modern practice recommends at least 2048‑bit keys to resist known attacks.

Random number generation : High‑quality randomness is essential during prime selection to avoid weak keys.

Parameter choice : Proper selection of primes p, q and exponent e is critical; secure generation methods help avoid common pitfalls.

Known attacks and defenses : Side‑channel attacks (timing, power analysis) can leak key material; countermeasures such as masking are recommended.

Typical Applications

Secure network communication (HTTPS, SSH).

Digital signatures for data integrity and authenticity.

Identity authentication in online banking and other services.

Email encryption (e.g., PGP).

VPN connections.

Digital certificates for website authentication.

Java Example

import java.security.*;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Base64;

public class RSAExample {

    // Generate a key pair
    public static KeyPair generateKeyPair() throws NoSuchAlgorithmException {
        KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");
        keyPairGenerator.initialize(2048);
        return keyPairGenerator.generateKeyPair();
    }

    // Convert private key to a Base64 string
    public static String privateKeyToString(PrivateKey privateKey) {
        byte[] encoded = privateKey.getEncoded();
        return Base64.getEncoder().encodeToString(encoded);
    }

    // Restore private key from a Base64 string
    public static PrivateKey stringToPrivateKey(String privateKeyStr) throws GeneralSecurityException {
        byte[] encoded = Base64.getDecoder().decode(privateKeyStr);
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(encoded);
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        return keyFactory.generatePrivate(keySpec);
    }

    // Convert public key to a Base64 string
    public static String publicKeyToString(PublicKey publicKey) {
        byte[] encoded = publicKey.getEncoded();
        return Base64.getEncoder().encodeToString(encoded);
    }

    // Restore public key from a Base64 string
    public static PublicKey stringToPublicKey(String publicKeyStr) throws GeneralSecurityException {
        byte[] encoded = Base64.getDecoder().decode(publicKeyStr);
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(encoded);
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        return keyFactory.generatePublic(keySpec);
    }

    // Encrypt data with the public key
    public static byte[] encrypt(PublicKey publicKey, byte[] data) throws GeneralSecurityException {
        Cipher cipher = Cipher.getInstance("RSA");
        cipher.init(Cipher.ENCRYPT_MODE, publicKey);
        return cipher.doFinal(data);
    }

    // Decrypt data with the private key
    public static byte[] decrypt(PrivateKey privateKey, byte[] encryptedData) throws GeneralSecurityException {
        Cipher cipher = Cipher.getInstance("RSA");
        cipher.init(Cipher.DECRYPT_MODE, privateKey);
        return cipher.doFinal(encryptedData);
    }

    public static void main(String[] args) {
        try {
            KeyPair keyPair = generateKeyPair();
            PublicKey publicKey = keyPair.getPublic();
            PrivateKey privateKey = keyPair.getPrivate();

            String publicKeyStr = publicKeyToString(publicKey);
            String privateKeyStr = privateKeyToString(privateKey);
            System.out.println("Public key: " + publicKeyStr);
            System.out.println("Private key: " + privateKeyStr);

            String originalMessage = "Message to encrypt";
            System.out.println("Original message: " + originalMessage);

            byte[] encryptedData = encrypt(publicKey, originalMessage.getBytes());
            System.out.println("Encrypted data: " + Base64.getEncoder().encodeToString(encryptedData));

            PrivateKey restoredPrivateKey = stringToPrivateKey(privateKeyStr);
            byte[] decryptedData = decrypt(restoredPrivateKey, encryptedData);
            System.out.println("Decrypted message: " + new String(decryptedData));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Conclusion

RSA remains one of the most widely deployed public‑key algorithms, suitable for digital signatures, authentication, and data encryption. Its strengths lie in straightforward implementation and strong security when proper key lengths, random number generation, and parameter choices are observed.