In the world of cryptography, RSA (Rivest–Shamir–Adleman) is a popular public-key cryptosystem widely used for secure data transmission. It’s based on the principle that while multiplying large prime numbers is computationally easy, factoring their product is not — which ensures security.

This post will walk you through how RSA encryption and decryption work using a simple Java program. You’ll learn how the sender encrypts a message using the recipient’s public key, and how the receiver decrypts it using their private key.

What Happens Under the Hood?

The RSA algorithm follows these steps:

1. Key Generation
   • Choose two large prime numbers p and q.
   • Compute N = p * q.
   • Compute the totient function: phi = (p-1)(q-1).
   • Choose an integer e such that 1 < e < phi and gcd(e, phi) = 1.
   • Compute d, the modular inverse of e modulo phi.
2. Encryption
   • The sender uses the recipient’s public key (e, N) to compute ciphertext: c = m^e mod N.
3. Decryption
   • The recipient uses their private key (d, N) to decrypt: m = c^d mod N.

Java Implementation of RSA

import java.util.*;
import java.math.BigInteger;

public class rsa {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        // Declare variables for primes, keys, message, etc.
        BigInteger p, q, phi, p1, q1, e, m, m2, N, t, d = new BigInteger("0"), i = new BigInteger("1");

        // Get input primes p and q from user
        System.out.println("Enter values for p and q");
        p = in.nextBigInteger();
        q = in.nextBigInteger();

        // Step 1: Calculate modulus N = p * q
        N = p.multiply(q);

        // Step 2: Calculate totient phi = (p-1)*(q-1)
        p1 = p.subtract(BigInteger.ONE);
        q1 = q.subtract(BigInteger.ONE);
        phi = p1.multiply(q1);

        // Sender's side
        System.out.println("At sender's end");

        // Step 3: Input public key (e) of the recipient
        System.out.println("Enter public key of recipient");
        e = in.nextBigInteger();

        // Step 4: Input the message to encrypt
        System.out.println("Enter Message");
        m = in.nextBigInteger();

        // Step 5: Encrypt message -> ciphertext = m^e mod N
        t = m.modPow(e, N);

        // Receiver's side
        System.out.println("At Receiver's end");

        // Step 6: Output the received cipher text
        System.out.println("The received message is: " + t);

        // Step 7: Calculate private key d such that (d * e) mod phi = 1
        d = e.modInverse(phi);

        // Step 8: Decrypt ciphertext -> plaintext = t^d mod N
        m2 = t.modPow(d, N);

        // Step 9: Output the decrypted message
        System.out.println("The decrypted message is: " + m2);
    }
}

Sample Output and Explanation

Enter values for p and q
13
17

At sender's end
Enter public key of recipient
5
Enter Message
10

At Receiver's end
The received message is: 108
The decrypted message is: 10

Step-by-Step Explanation

• Step 1: N = 13 × 17 = 221
• Step 2: φ(N) = (13-1)(17-1) = 12 × 16 = 192
• Step 3: Public key e = 5
• Step 4: Plain message m = 10
• Step 5: Encrypted ciphertext = 10^5 mod 221 = 108
• Step 6: Ciphertext received: 108
• Step 7: Private key d = 5⁻¹ mod 192 = 77
• Step 8: Decrypted plaintext = 108^77 mod 221 = 10

As you can see, the original message is recovered, confirming the correctness of encryption and decryption!