Implementing RSA from Scratch: A Cryptography Deep Dive

There's a difference between using encryption and understanding encryption. For my UTPB-COSC-4380 Cryptography class, I had to cross that gap—implementing Diffie-Hellman, RSA, and AES from scratch in Java.

The project files tell the story: DHE.java, RSA.java, AES.java, and a primes.txt file I spent way too much time generating.

Project 3: Diffie-Hellman Key Exchange

Diffie-Hellman is elegant. Two parties can establish a shared secret over an insecure channel without ever transmitting the secret itself. The math is simple but the implications are profound:

// DHE.java - The core exchange
// Alice: g^a mod p -> sends to Bob
// Bob: g^b mod p -> sends to Alice
// Both compute: g^(ab) mod p = shared secret

public BigInteger computeSharedSecret(BigInteger otherPublic, 
                                       BigInteger myPrivate, 
                                       BigInteger p) {
    return otherPublic.modPow(myPrivate, p);
}

My implementation supports both two-party and three-party exchanges. The three-party version requires a circular exchange pattern where each party contributes to the final shared secret.

RSA: More Than Encryption

Most people think of RSA as encryption, but RSA.java implements two separate operations:

1. Encryption/Decryption: Hiding message content
2. Digital Signatures: Proving authenticity

// RSA.java - Key Generation
BigInteger p = generateLargePrime(1024);
BigInteger q = generateLargePrime(1024);
BigInteger n = p.multiply(q);
BigInteger phi = (p.subtract(ONE)).multiply(q.subtract(ONE));
BigInteger e = new BigInteger("65537");  // Common public exponent
BigInteger d = e.modInverse(phi);        // Private key

// Encryption: c = m^e mod n
// Decryption: m = c^d mod n

The hardest part wasn't the implementation—it was understanding why decryption works. It relies on Euler's theorem: m^(ed) ≡ m (mod n). I spent an entire weekend with a whiteboard proving it to myself.

Project 4: AES in ECB and CBC Modes

AES.java was brutal. Unlike RSA's mathematical elegance, AES is a sequence of byte manipulations—SubBytes, ShiftRows, MixColumns, AddRoundKey, repeated 10 times.

// AES.java - CBC mode encryption
byte[] previousBlock = iv;
for (byte[] block : blocks) {
    byte[] xored = xor(block, previousBlock);
    byte[] encrypted = aesEncryptBlock(xored, key);
    previousBlock = encrypted;
    output.add(encrypted);
}

The difference between ECB and CBC is crucial:

• ECB: Each block encrypted independently. Fast but reveals patterns.
• CBC: Each block XORed with previous ciphertext. Hides patterns.

The Debug Output That Saved Me

The smartest thing I did was add a debug flag that outputs state after each step. I kept an AES Debug.txt in the repo. When my output didn't match the reference, I could pinpoint exactly which step failed. The bug was always in MixColumns.

What I Learned

Building cryptography from scratch teaches you to respect the math. Every line has to be exactly right—there's no "close enough" in security. But more importantly, I now understand why we never roll our own crypto in production.