Chapter 15: Cryptographic Algorithms (RSA, Modular Arithmetic)

Introduction

Cryptography protects information through mathematical transformations. This chapter explores fundamental cryptographic algorithms including RSA encryption, Diffie-Hellman key exchange, and advanced modular arithmetic. Understanding these algorithms is essential for building secure systems, protecting data, and comprehending modern security protocols.

Why This Matters

Cryptography secures the digital world:

Online banking: Encrypting financial transactions
Messaging apps: End-to-end encryption (Signal, WhatsApp)
HTTPS: Secure web communication
Password storage: Hashing and salting
Digital signatures: Verifying authenticity
Blockchain: Cryptocurrencies and smart contracts
VPNs: Secure network communication

How to Study This Chapter

Understand mathematical foundations - Modular arithmetic, prime numbers
Learn key generation - How public/private keys are created
Trace encryption/decryption - Work through examples by hand
Implement basic algorithms - RSA, Diffie-Hellman
Study security considerations - Key sizes, attack vectors

Modular Arithmetic Review

Key Properties

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m
(a^b) mod m can be computed efficiently using binary exponentiation

Modular Exponentiation

Essential for RSA - computes (base^exp) mod m efficiently.

C Implementation

#include <stdio.h>

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;

    while (exp > 0) {
        // If exp is odd, multiply base with result
        if (exp & 1) {
            result = (result * base) % mod;
        }

        // Square the base and halve the exponent
        base = (base * base) % mod;
        exp >>= 1;
    }

    return result;
}

int main() {
    long long base = 3, exp = 13, mod = 7;
    printf("(%lld^%lld) mod %lld = %lld\n", base, exp, mod, modPow(base, exp, mod));
    return 0;
}

Complexity: O(log exp)

Modular Inverse

Find x such that (a × x) mod m = 1.

#include <iostream>
using namespace std;

// Extended Euclidean Algorithm
long long extendedGCD(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long x1, y1;
    long long gcd = extendedGCD(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return gcd;
}

long long modInverse(long long a, long long m) {
    long long x, y;
    long long gcd = extendedGCD(a, m, x, y);

    if (gcd != 1) {
        return -1;  // Inverse doesn't exist
    }

    return (x % m + m) % m;
}

int main() {
    long long a = 3, m = 11;
    long long inv = modInverse(a, m);

    cout << "Inverse of " << a << " mod " << m << " = " << inv << endl;
    cout << "Verification: (" << a << " × " << inv << ") mod " << m << " = "
         << (a * inv) % m << endl;

    return 0;
}

RSA Encryption

RSA (Rivest-Shamir-Adleman) is an asymmetric encryption algorithm using public/private key pairs.

RSA Algorithm

Key Generation

1. Choose two large prime numbers p and q
2. Compute n = p × q (modulus)
3. Compute φ(n) = (p - 1) × (q - 1) (Euler's totient)
4. Choose public exponent e (1 < e < φ(n), gcd(e, φ(n)) = 1)
   Common choice: e = 65537
5. Compute private exponent d = e^(-1) mod φ(n)

Public key: (e, n)
Private key: (d, n)

Encryption

ciphertext = (message^e) mod n

Decryption

message = (ciphertext^d) mod n

Visualization

Example with small primes (NOT secure in practice):

1. Choose p = 61, q = 53
2. n = 61 × 53 = 3233
3. φ(n) = (61-1) × (53-1) = 3120
4. Choose e = 17 (gcd(17, 3120) = 1)
5. Compute d = 17^(-1) mod 3120 = 2753

Public key: (17, 3233)
Private key: (2753, 3233)

Encrypt message m = 123:
  c = 123^17 mod 3233 = 855

Decrypt ciphertext c = 855:
  m = 855^2753 mod 3233 = 123 ✓

C++ Implementation

#include <iostream>
#include <cmath>
using namespace std;

class RSA {
private:
    long long p, q, n, phi, e, d;

    // Check if number is prime (simple version)
    bool isPrime(long long num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;

        for (long long i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    long long extendedGCD(long long a, long long b, long long& x, long long& y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }

        long long x1, y1;
        long long gcd = extendedGCD(b, a % b, x1, y1);

        x = y1;
        y = x1 - (a / b) * y1;

        return gcd;
    }

    long long modInverse(long long a, long long m) {
        long long x, y;
        long long g = extendedGCD(a, m, x, y);

        if (g != 1) return -1;

        return (x % m + m) % m;
    }

    long long modPow(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;

        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }

        return result;
    }

public:
    void generateKeys(long long prime1, long long prime2) {
        if (!isPrime(prime1) || !isPrime(prime2)) {
            cout << "Both numbers must be prime!" << endl;
            return;
        }

        p = prime1;
        q = prime2;
        n = p * q;
        phi = (p - 1) * (q - 1);

        // Choose e (commonly 65537, but using smaller for demo)
        e = 17;
        while (e < phi) {
            if (gcd(e, phi) == 1) {
                break;
            }
            e++;
        }

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

        cout << "RSA Keys Generated:" << endl;
        cout << "Public Key (e, n): (" << e << ", " << n << ")" << endl;
        cout << "Private Key (d, n): (" << d << ", " << n << ")" << endl;
        cout << "p = " << p << ", q = " << q << ", φ(n) = " << phi << endl;
    }

    long long encrypt(long long message) {
        return modPow(message, e, n);
    }

    long long decrypt(long long ciphertext) {
        return modPow(ciphertext, d, n);
    }

    void getPublicKey(long long& publicE, long long& publicN) {
        publicE = e;
        publicN = n;
    }

    void getPrivateKey(long long& privateD, long long& privateN) {
        privateD = d;
        privateN = n;
    }
};

int main() {
    RSA rsa;

    // Generate keys with small primes (NOT secure for real use)
    rsa.generateKeys(61, 53);

    long long message = 123;
    cout << "\nOriginal message: " << message << endl;

    // Encrypt
    long long ciphertext = rsa.encrypt(message);
    cout << "Encrypted: " << ciphertext << endl;

    // Decrypt
    long long decrypted = rsa.decrypt(ciphertext);
    cout << "Decrypted: " << decrypted << endl;

    return 0;
}

Java Implementation

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

public class RSA {
    private BigInteger n, d, e;
    private int bitLength = 1024;

    public RSA() {
        SecureRandom random = new SecureRandom();

        // Generate two large prime numbers
        BigInteger p = BigInteger.probablePrime(bitLength / 2, random);
        BigInteger q = BigInteger.probablePrime(bitLength / 2, random);

        // Compute n = p * q
        n = p.multiply(q);

        // Compute φ(n) = (p-1) * (q-1)
        BigInteger phi = p.subtract(BigInteger.ONE)
                          .multiply(q.subtract(BigInteger.ONE));

        // Choose e (commonly 65537)
        e = BigInteger.valueOf(65537);

        // Compute d = e^(-1) mod φ(n)
        d = e.modInverse(phi);

        System.out.println("RSA Keys Generated");
        System.out.println("Public Key (e, n):");
        System.out.println("e = " + e);
        System.out.println("n = " + n);
        System.out.println("\nPrivate Key (d, n):");
        System.out.println("d = " + d);
    }

    public BigInteger encrypt(BigInteger message) {
        return message.modPow(e, n);
    }

    public BigInteger decrypt(BigInteger ciphertext) {
        return ciphertext.modPow(d, n);
    }

    public static void main(String[] args) {
        RSA rsa = new RSA();

        String messageStr = "Hello RSA!";
        BigInteger message = new BigInteger(messageStr.getBytes());

        System.out.println("\nOriginal message: " + messageStr);

        BigInteger ciphertext = rsa.encrypt(message);
        System.out.println("Encrypted: " + ciphertext);

        BigInteger decrypted = rsa.decrypt(ciphertext);
        String decryptedStr = new String(decrypted.toByteArray());
        System.out.println("Decrypted: " + decryptedStr);
    }
}

Security Considerations

Key size: Minimum 2048 bits for security
Prime generation: Use cryptographically secure random primes
Padding: Use OAEP or PSS for security
Never reuse primes: Each key pair needs unique p and q
Protect private key: Must remain secret

Diffie-Hellman Key Exchange

Diffie-Hellman allows two parties to establish a shared secret over an insecure channel.

Algorithm

Public parameters: prime p, generator g

Alice:
1. Choose secret a (random)
2. Compute A = g^a mod p
3. Send A to Bob

Bob:
1. Choose secret b (random)
2. Compute B = g^b mod p
3. Send B to Alice

Alice computes: s = B^a mod p = (g^b)^a mod p = g^(ab) mod p
Bob computes: s = A^b mod p = (g^a)^b mod p = g^(ab) mod p

Shared secret: s = g^(ab) mod p

C++ Implementation

#include <iostream>
#include <random>
using namespace std;

class DiffieHellman {
private:
    long long p;  // Prime modulus
    long long g;  // Generator

    long long modPow(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;

        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }

        return result;
    }

public:
    DiffieHellman(long long prime, long long generator)
        : p(prime), g(generator) {}

    long long generatePublicKey(long long privateKey) {
        return modPow(g, privateKey, p);
    }

    long long computeSharedSecret(long long otherPublicKey, long long myPrivateKey) {
        return modPow(otherPublicKey, myPrivateKey, p);
    }

    void demonstrate() {
        cout << "Diffie-Hellman Key Exchange" << endl;
        cout << "Public parameters: p = " << p << ", g = " << g << endl << endl;

        // Alice's keys
        long long alicePrivate = 5;  // In practice, choose randomly
        long long alicePublic = generatePublicKey(alicePrivate);
        cout << "Alice's private key: " << alicePrivate << endl;
        cout << "Alice's public key: " << alicePublic << endl << endl;

        // Bob's keys
        long long bobPrivate = 7;
        long long bobPublic = generatePublicKey(bobPrivate);
        cout << "Bob's private key: " << bobPrivate << endl;
        cout << "Bob's public key: " << bobPublic << endl << endl;

        // Compute shared secrets
        long long aliceShared = computeSharedSecret(bobPublic, alicePrivate);
        long long bobShared = computeSharedSecret(alicePublic, bobPrivate);

        cout << "Alice's computed shared secret: " << aliceShared << endl;
        cout << "Bob's computed shared secret: " << bobShared << endl;

        if (aliceShared == bobShared) {
            cout << "\n✓ Shared secret established successfully!" << endl;
        }
    }
};

int main() {
    // Using small values for demonstration (NOT secure in practice)
    long long p = 23;  // Prime
    long long g = 5;   // Primitive root modulo p

    DiffieHellman dh(p, g);
    dh.demonstrate();

    return 0;
}

Hash Functions

Hash functions produce fixed-size outputs from variable-size inputs.

Properties

Deterministic: Same input always produces same output
One-way: Cannot reverse to find input
Collision-resistant: Hard to find two inputs with same hash
Avalanche effect: Small input change → large output change

Simple Hash (Educational)

#include <iostream>
#include <string>
using namespace std;

// Simple polynomial rolling hash (NOT cryptographically secure)
unsigned long long simpleHash(const string& str) {
    unsigned long long hash = 0;
    const unsigned long long p = 31;
    const unsigned long long m = 1e9 + 9;

    unsigned long long pPow = 1;

    for (char c : str) {
        hash = (hash + (c - 'a' + 1) * pPow) % m;
        pPow = (pPow * p) % m;
    }

    return hash;
}

int main() {
    string text1 = "hello";
    string text2 = "world";
    string text3 = "hello";

    cout << "Hash of '" << text1 << "': " << simpleHash(text1) << endl;
    cout << "Hash of '" << text2 << "': " << simpleHash(text2) << endl;
    cout << "Hash of '" << text3 << "': " << simpleHash(text3) << endl;

    return 0;
}

Caesar Cipher (Classical)

Simple substitution cipher (educational only, NOT secure).

#include <stdio.h>
#include <string.h>
#include <ctype.h>

void caesarEncrypt(char* text, int shift) {
    for (int i = 0; text[i] != '\0'; i++) {
        if (isalpha(text[i])) {
            char base = isupper(text[i]) ? 'A' : 'a';
            text[i] = (text[i] - base + shift) % 26 + base;
        }
    }
}

void caesarDecrypt(char* text, int shift) {
    caesarEncrypt(text, 26 - shift);
}

int main() {
    char message[] = "HELLO WORLD";
    int shift = 3;

    printf("Original: %s\n", message);

    caesarEncrypt(message, shift);
    printf("Encrypted: %s\n", message);

    caesarDecrypt(message, shift);
    printf("Decrypted: %s\n", message);

    return 0;
}

Common Mistakes

Using small primes in RSA - Insecure, easily factored
Not using padding - Vulnerable to attacks
Reusing random values - Breaks security guarantees
Integer overflow - In modular arithmetic
Weak random number generation - Predictable keys
Storing private keys insecurely - Plain text files
Rolling your own crypto - Use established libraries

Debugging Tips

Test with small values - Verify algorithm correctness
Verify mathematical properties - Encrypt then decrypt = original
Check key generation - Ensure gcd(e, φ(n)) = 1
Test edge cases - Message = 0, message > n
Validate modular inverse - (a × a^(-1)) mod m = 1
Use established libraries - For production code
Never log sensitive data - Private keys, messages

Mini Exercises

Implement Vigenère cipher
Compute discrete logarithm (small examples)
Implement ElGamal encryption
Create simple digital signature scheme
Implement XOR cipher
Compute cryptographic hash collision (birthday paradox)
Implement one-time pad
Create Shamir's Secret Sharing
Implement basic AES (educational)
Build password hashing with salt

Review Questions

Why does RSA use two large prime numbers?
How does Diffie-Hellman prevent man-in-the-middle attacks?
What's the difference between symmetric and asymmetric encryption?
Why is modular exponentiation crucial for RSA?
What properties make a good cryptographic hash function?

Reference Checklist

By the end of this chapter, you should be able to:

Implement modular exponentiation
Compute modular inverse
Generate RSA key pairs
Encrypt and decrypt with RSA
Implement Diffie-Hellman key exchange
Understand hash function properties
Explain public key cryptography
Identify security considerations

Next Steps

Chapter 16 explores compression algorithms—Run-Length Encoding (RLE), Huffman Coding, and data compression techniques used in file formats, network protocols, and storage systems.

Key Takeaway: Cryptographic algorithms protect digital information using mathematical transformations. RSA enables secure communication with public/private keys. Diffie-Hellman establishes shared secrets over insecure channels. Understanding these algorithms is fundamental to building secure systems, though production systems should always use well-tested cryptographic libraries.