Author: Vincent Bevia, MSc Computer Science — University of Liverpool

Introduction

RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. It was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT.

RSA is an asymmetric encryption algorithm, meaning it uses two different keys:

• A public key for encryption (can be shared openly)
• A private key for decryption (must be kept secret)

Mathematical Foundation

Prime Numbers

RSA’s security relies on the mathematical difficulty of factoring large composite numbers that are products of two large prime numbers.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself (e.g., 2, 3, 5, 7, 11, 13…).

Euler’s Totient Function $\varphi(n)$

Euler’s totient function, denoted $\varphi(n)$, counts the number of integers from 1 to n that are coprime (share no common factors other than 1) with n.

For two prime numbers p and q:

$$\varphi(n) = (p - 1) \times (q - 1)$$

Modular Arithmetic

RSA heavily uses modular arithmetic. The expression $a \mod n$ gives the remainder when a is divided by n.

For example:

• $17 \mod 5 = 2$ (because $17 = 3 \times 5 + 2$)

Greatest Common Divisor (GCD)

Two numbers are coprime if their GCD equals 1. The code implements GCD using the Euclidean algorithm:

static int gcd(int e, int z) {
    if (e == 0)
        return z;
    else
        return gcd(z % e, e);
}

RSA Algorithm Steps

Step 1: Key Generation

1.1 Select Two Prime Numbers (p and q)

Choose two distinct prime numbers. In the code:

p = 2;  // 1st prime number
q = 7;  // 2nd prime number

Security Note: In real-world applications, p and q should be very large primes (typically 1024+ bits each) to ensure security.

1.2 Compute n (Modulus)

Calculate the product of the two primes:

$$n = p \times q$$

In the code:

n = p * q;  // n = 2 × 7 = 14

The value n is used as the modulus for both the public and private keys.

1.3 Compute $\varphi(n)$ (Euler’s Totient)

Calculate Euler’s totient function:

$$\varphi(n) = (p - 1) \times (q - 1)$$

In the code:

phi = (p - 1) * (q - 1);  // phi = (2-1) × (7-1) = 1 × 6 = 6

1.4 Choose Public Exponent (e)

Select an integer e such that:

1. $1 < e < \varphi(n)$
2. $\gcd(e, \varphi(n)) = 1$ (e and $\varphi(n)$ are coprime)

In the code:

for (e = 2; e < phi; e++) {
    if (gcd(e, phi) == 1) {
        break;
    }
}

This finds the smallest valid e. Common choices in practice are 3, 17, or 65537.

1.5 Calculate Private Exponent (d)

Find d such that:

$$d \times e \equiv 1 \pmod{\varphi(n)}$$

This means d is the modular multiplicative inverse of e modulo $\varphi(n)$.

Equivalently: $d = \frac{k \times \varphi(n) + 1}{e}$ for some integer k that makes the division exact.

In the code:

for (i = 0; i <= 9; i++) {
    int x = 1 + (i * phi);
    if (x % e == 0 && d != e) {
        d = x / e;
        break;
    }
}

Step 2: Key Distribution

After key generation:

Encryption Process

To encrypt a message m:

$$C = m^e \mod n$$

Where:

• $m$ = plaintext message (must be less than n)
• $e$ = public exponent
• $n$ = modulus
• $C$ = ciphertext

In the code:

int msg = 2;  // Original message
c = (Math.pow(msg, e)) % n;  // C = 2^e mod 14

Decryption Process

To decrypt ciphertext C:

$$m = C^d \mod n$$

Where:

• $C$ = ciphertext
• $d$ = private exponent
• $n$ = modulus
• $m$ = recovered plaintext

In the code:

BigInteger N = BigInteger.valueOf(n);
BigInteger C = BigDecimal.valueOf(c).toBigInteger();
msgback = (C.pow(d)).mod(N);

Note: BigInteger is used because d can be large, and Math.pow() would overflow.

Why RSA Works

The mathematical proof relies on Euler’s theorem, which states:

$$m^{\varphi(n)} \equiv 1 \pmod{n}$$

Since we chose d such that $d \times e \equiv 1 \pmod{\varphi(n)}$, we can write:

$$d \times e = 1 + k \times \varphi(n) \quad \text{for some integer } k$$

Therefore:

$$ \begin{aligned} C^d \mod n &= (m^e)^d \mod n \\ &= m^{e \times d} \mod n \\ &= m^{1 + k \cdot \varphi(n)} \mod n \\ &= m \cdot (m^{\varphi(n)})^k \mod n \\ &= m \cdot 1^k \mod n \quad \text{(by Euler’s theorem)} \\ &= m \mod n \\ &= m \quad \text{(since } m < n \text{)} \end{aligned} $$

Example Walkthrough

Using the values from the code with $p=2$, $q=7$:

Encrypting message $m = 2$:

$$C = 2^5 \mod 14 = 32 \mod 14 = 4$$

Decrypting ciphertext $C = 4$:

$$m = 4^{11} \mod 14 = 4194304 \mod 14 = 2 \checkmark$$

Security Considerations

Why is RSA Secure?

1. Factoring Problem: Given n, finding p and q is computationally infeasible for large primes
2. One-Way Function: Computing C from m is easy; reversing it without d is hard
3. Key Size: Modern RSA uses 2048-bit or 4096-bit keys

Vulnerabilities to Avoid

Comparison: Code vs. Real-World Implementation

Summary

The RSA algorithm demonstrates the elegant application of number theory to cryptography:

1. Generate two large primes $p$ and $q$
2. Compute $n = p \times q$ and $\varphi(n) = (p-1)(q-1)$
3. Choose public exponent $e$ coprime to $\varphi(n)$
4. Calculate private exponent $d$ as modular inverse of $e$
5. Encrypt: $C = m^e \mod n$
6. Decrypt: $m = C^d \mod n$

The security of RSA rests on the mathematical difficulty of factoring large numbers, making it one of the foundational algorithms in modern cryptography.

Complete Java Implementation

Here’s the full working Java implementation that demonstrates all the concepts covered above:

// Java Program to Implement the RSA Algorithm

import java.math.*;

class RSA {
    public static void main(String args[]) {
        int p, q, n, phi, d = 0, e, i;

        // The number to be encrypted and decrypted
        int msg = 2;
        double c;
        BigInteger msgback;

        // 1st prime number p
        p = 2;

        // 2nd prime number q
        q = 7;

        // Value of N
        n = p * q;
        System.out.println("the value of N = " + n);

        // value of phi
        phi = (p - 1) * (q - 1);
        System.out.println("the value of phi = " + phi);

        for (e = 2; e < phi; e++) {

            // e is for public key exponent
            if (gcd(e, phi) == 1) {
                break;
            }
        }

        System.out.println("the value of e = " + e);
        for (i = 0; i <= 9; i++) {
            int x = 1 + (i * phi);

            // d is for private key exponent
            if (x % e == 0 && d != e ) {
                d = x / e;
                break;
            }
        }
        System.out.println("the value of d = " + d);
        System.out.println("the message in clear= " + msg);
        /*
            C = me mod n
            Here, m must be less than n.
         */

        c = (Math.pow(msg, e)) % n;
        System.out.println("Encrypted message is : " + c);

        // converting int value of n to BigInteger
        BigInteger N = BigInteger.valueOf(n);

        // converting float value of c to BigInteger
        BigInteger C = BigDecimal.valueOf(c).toBigInteger();
        msgback = (C.pow(d)).mod(N);
        System.out.println("Decrypted message is : "
                + msgback);
    }

    static int gcd(int e, int z) {
        if (e == 0)
            return z;
        else
            return gcd(z % e, e);
    }
}

Expected Output

the value of N = 14
the value of phi = 6
the value of e = 5
the value of d = 11
the message in clear= 2
Encrypted message is : 4.0
Decrypted message is : 2

References

• RSA on Wikipedia
• JavaTPoint RSA Tutorial
• Original Paper: Rivest, R.; Shamir, A.; Adleman, L. (1978). “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”