RSA Algorithm: Interactive Public-Key Cryptography Implementation

Description

RSA (Rivest-Shamir-Adleman) is a public-key cryptosystem widely used for secure data transmission. It is based on the practical difficulty of factoring the product of two large prime numbers.

How It Works

Key Generation:
- Choose two large prime numbers p and q
- Calculate n = p × q
- Calculate φ(n) = (p-1) × (q-1)
- Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
- Calculate d such that d × e ≡ 1 (mod φ(n))
Encryption: c = m^e mod n
Decryption: m = c^d mod n

Complexity Analysis

Time Complexity

Key Generation: O(k³) where k is the number of bits in the key
- Prime number generation: O(k²) per primality test
- Modular exponentiation: O(k³)
Encryption: O(k²) for k-bit keys
- Modular exponentiation (m^e mod n): O(k²)
- Public exponent e is typically small (e.g., 65537)
Decryption: O(k³) for k-bit keys
- Modular exponentiation (c^d mod n): O(k³)
- Private exponent d is typically the same size as n

Space Complexity

Key Storage: O(k) where k is the number of bits
- Public key (e, n): O(k)
- Private key (d, n): O(k)
Message Processing: O(k)
- Input message blocks: O(k)
- Intermediate calculations: O(k)

Practical Considerations

Key size recommendations:
- 2048 bits: Current standard for general use
- 3072 bits: Recommended for high security after 2030
- 4096 bits: Maximum security for critical applications
Performance trade-offs:
- Larger keys provide better security but slower operations
- Public key operations (encryption) are faster than private key operations (decryption)
- Key generation is the most computationally intensive operation

Visualization

Enter a message and click Encrypt to begin

Implementation


from math import gcd
from random import randrange

class RSA:
    def __init__(self, key_size=1024):
        self.key_size = key_size
        self.public_key = None
        self.private_key = None
        self.n = None
        self.generate_keys()
    
    def is_prime(self, n, k=5):
        """Miller-Rabin primality test"""
        if n == 2 or n == 3:
            return True
        if n < 2 or n % 2 == 0:
            return False
        
        # Write n as 2^r * d + 1
        r, d = 0, n - 1
        while d % 2 == 0:
            r += 1
            d //= 2
        
        # Witness loop
        for _ in range(k):
            a = randrange(2, n-1)
            x = pow(a, d, n)
            if x == 1 or x == n-1:
                continue
            for _ in range(r-1):
                x = (x * x) % n
                if x == n-1:
                    break
            else:
                return False
        return True
    
    def generate_prime(self, bits):
        """Generate a prime number with specified bits"""
        while True:
            n = randrange(2**(bits-1), 2**bits)
            if self.is_prime(n):
                return n
    
    def generate_keys(self):
        """Generate public and private key pairs"""
        # Generate two prime numbers
        p = self.generate_prime(self.key_size // 2)
        q = self.generate_prime(self.key_size // 2)
        
        self.n = p * q
        phi = (p - 1) * (q - 1)
        
        # Choose public exponent e
        e = 65537  # Common choice for e
        while gcd(e, phi) != 1:
            e += 2
        
        # Calculate private exponent d
        d = pow(e, -1, phi)
        
        self.public_key = (e, self.n)
        self.private_key = (d, self.n)
    
    def encrypt(self, message):
        """Encrypt a message using public key"""
        e, n = self.public_key
        if isinstance(message, str):
            message = int.from_bytes(message.encode(), 'big')
        return pow(message, e, n)
    
    def decrypt(self, ciphertext):
        """Decrypt a message using private key"""
        d, n = self.private_key
        plaintext = pow(ciphertext, d, n)
        try:
            return plaintext.to_bytes((plaintext.bit_length() + 7) // 8, 'big').decode()
        except:
            return str(plaintext)

# Example usage
if __name__ == "__main__":
    # Create RSA instance with smaller key size for demonstration
    rsa = RSA(key_size=32)
    
    message = "Hello, RSA!"
    print(f"Original message: {message}")
    
    # Encrypt
    encrypted = rsa.encrypt(message)
    print(f"Encrypted: {encrypted}")
    
    # Decrypt
    decrypted = rsa.decrypt(encrypted)
    print(f"Decrypted: {decrypted}")


#include <iostream>
#include <cmath>
#include <random>
#include <string>

class RSA {
private:
    long long n, e, d;
    
    bool is_prime(long long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        
        for (long long i = 2; i <= sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    long long generate_prime(int min, int max) {
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<long long> dis(min, max);
        
        long long num;
        do {
            num = dis(gen);
        } while (!is_prime(num));
        
        return num;
    }
    
    long long mod_inverse(long long e, long long phi) {
        long long m0 = phi;
        long long y = 0, x = 1;
        
        if (phi == 1) return 0;
        
        while (e > 1) {
            long long q = e / phi;
            long long t = phi;
            
            phi = e % phi;
            e = t;
            t = y;
            
            y = x - q * y;
            x = t;
        }
        
        if (x < 0) x += m0;
        return x;
    }
    
    long long gcd(long long a, long long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

public:
    RSA() {
        // Generate two prime numbers
        long long p = generate_prime(100, 300);
        long long q = generate_prime(100, 300);
        
        n = p * q;
        long long phi = (p - 1) * (q - 1);
        
        // Choose e
        e = 2;
        while (e < phi) {
            if (gcd(e, phi) == 1) break;
            e++;
        }
        
        // Calculate d
        d = mod_inverse(e, phi);
    }
    
    long long encrypt(long long message) {
        long long result = 1;
        for (long long i = 0; i < e; i++) {
            result = (result * message) % n;
        }
        return result;
    }
    
    long long decrypt(long long ciphertext) {
        long long result = 1;
        for (long long i = 0; i < d; i++) {
            result = (result * ciphertext) % n;
        }
        return result;
    }
    
    void get_public_key(long long& out_e, long long& out_n) {
        out_e = e;
        out_n = n;
    }
};

int main() {
    RSA rsa;
    long long e, n;
    rsa.get_public_key(e, n);
    
    std::cout << "Public Key (e,n): (" << e << "," << n << ")\n";
    
    // Example message
    long long message = 12345;
    std::cout << "Original Message: " << message << "\n";
    
    // Encrypt
    long long encrypted = rsa.encrypt(message);
    std::cout << "Encrypted: " << encrypted << "\n";
    
    // Decrypt
    long long decrypted = rsa.decrypt(encrypted);
    std::cout << "Decrypted: " << decrypted << "\n";
    
    return 0;
}


using System;
using System.Numerics;
using System.Security.Cryptography;

public class RSA
{
    private BigInteger n, e, d;
    private readonly int keySize;
    
    public RSA(int keySize = 1024)
    {
        this.keySize = keySize;
        GenerateKeys();
    }
    
    private void GenerateKeys()
    {
        using (var rng = new RNGCryptoServiceProvider())
        {
            // Generate two prime numbers
            var p = GeneratePrime(keySize / 2);
            var q = GeneratePrime(keySize / 2);
            
            n = p * q;
            var phi = (p - 1) * (q - 1);
            
            // Choose public exponent
            e = new BigInteger(65537); // Common choice for e
            
            // Calculate private exponent
            d = ModInverse(e, phi);
        }
    }
    
    private BigInteger GeneratePrime(int bits)
    {
        using (var provider = new RNGCryptoServiceProvider())
        {
            var bytes = new byte[bits / 8];
            BigInteger prime;
            
            do
            {
                provider.GetBytes(bytes);
                bytes[bytes.Length - 1] &= 0x7F; // Ensure positive number
                prime = new BigInteger(bytes);
            }
            while (!IsProbablyPrime(prime, 10));
            
            return prime;
        }
    }
    
    private bool IsProbablyPrime(BigInteger n, int k)
    {
        if (n <= 1 || n == 4) return false;
        if (n <= 3) return true;
        
        BigInteger d = n - 1;
        while (d % 2 == 0)
            d /= 2;
        
        Random rand = new Random();
        byte[] bytes = new byte[n.ToByteArray().Length];
        
        for (int i = 0; i < k; i++)
        {
            rand.NextBytes(bytes);
            BigInteger a = new BigInteger(bytes) % (n - 4) + 2;
            BigInteger x = BigInteger.ModPow(a, d, n);
            
            if (x == 1 || x == n - 1)
                continue;
            
            while (d != n - 1)
            {
                x = (x * x) % n;
                d *= 2;
                
                if (x == 1) return false;
                if (x == n - 1) break;
            }
            
            if (x != n - 1) return false;
        }
        return true;
    }
    
    private BigInteger ModInverse(BigInteger a, BigInteger m)
    {
        BigInteger m0 = m;
        BigInteger y = 0, x = 1;
        
        if (m == 1)
            return 0;
        
        while (a > 1)
        {
            BigInteger q = a / m;
            BigInteger t = m;
            
            m = a % m;
            a = t;
            t = y;
            
            y = x - q * y;
            x = t;
        }
        
        if (x < 0)
            x += m0;
        
        return x;
    }
    
    public byte[] Encrypt(byte[] message)
    {
        var msg = new BigInteger(message);
        var encrypted = BigInteger.ModPow(msg, e, n);
        return encrypted.ToByteArray();
    }
    
    public byte[] Decrypt(byte[] ciphertext)
    {
        var msg = new BigInteger(ciphertext);
        var decrypted = BigInteger.ModPow(msg, d, n);
        return decrypted.ToByteArray();
    }
    
    public (BigInteger e, BigInteger n) GetPublicKey()
    {
        return (e, n);
    }
    
    // Example usage
    public static void Main()
    {
        var rsa = new RSA(512); // Smaller key size for demonstration
        var message = "Hello, RSA!";
        Console.WriteLine($"Original message: {message}");
        
        // Convert string to bytes
        var messageBytes = System.Text.Encoding.UTF8.GetBytes(message);
        
        // Encrypt
        var encrypted = rsa.Encrypt(messageBytes);
        Console.WriteLine($"Encrypted: {BitConverter.ToString(encrypted)}");
        
        // Decrypt
        var decrypted = rsa.Decrypt(encrypted);
        var decryptedMessage = System.Text.Encoding.UTF8.GetString(decrypted);
        Console.WriteLine($"Decrypted: {decryptedMessage}");
    }
}

Quick Info

RSA Algorithm