Mastering Algorithms

RSA (Rivest-Shamir-Adleman)

Overview

RSA is an asymmetric cryptographic algorithm named after its inventors: Ron Rivest, Adi Shamir, and Leonard Adleman. It's one of the first public-key cryptosystems and is widely used for secure data transmission, digital signatures, and key exchange.

RSA's security is based on the mathematical difficulty of factoring large composite numbers into their prime factors. The algorithm uses a public key for encryption and a private key for decryption, enabling secure communication without sharing secret keys.

How It Works

  1. 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) mod φ(n) = 1
    • Public key: (n, e), Private key: (n, d)
  2. Encryption: c = m^e mod n
  3. Decryption: m = c^d mod n

RSA Algorithm


RSA_KeyGeneration():
    p, q = generate_large_primes()
    n = p * q
    φ(n) = (p - 1) * (q - 1)
    e = choose_public_exponent(φ(n))
    d = modular_inverse(e, φ(n))
    return (n, e), (n, d)

RSA_Encrypt(message, public_key):
    (n, e) = public_key
    return message^e mod n

RSA_Decrypt(ciphertext, private_key):
    (n, d) = private_key
    return ciphertext^d mod n

Implementation


from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.backends import default_backend

def generate_rsa_keys(key_size=2048):
    """Generate RSA key pair"""
    private_key = rsa.generate_private_key(
        public_exponent=65537,
        key_size=key_size,
        backend=default_backend()
    )
    public_key = private_key.public_key()
    return private_key, public_key

def rsa_encrypt(message, public_key):
    """Encrypt message using RSA public key"""
    ciphertext = public_key.encrypt(
        message,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return ciphertext

def rsa_decrypt(ciphertext, private_key):
    """Decrypt message using RSA private key"""
    plaintext = private_key.decrypt(
        ciphertext,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA256()),
            algorithm=hashes.SHA256(),
            label=None
        )
    )
    return plaintext

# Example usage
private_key, public_key = generate_rsa_keys()
message = b"Hello, RSA Encryption!"
ciphertext = rsa_encrypt(message, public_key)
decrypted = rsa_decrypt(ciphertext, private_key)

Security

RSA security depends on:

  • Key Size: Larger keys provide more security but slower operations
  • Prime Generation: Primes must be truly random and large
  • Implementation: Proper padding (OAEP) is essential

Recommended key sizes:

  • 1024 bits: Minimum (deprecated)
  • 2048 bits: Standard (current recommendation)
  • 4096 bits: High security (future-proof)

Applications

  • SSL/TLS: Secure web communication
  • Digital Signatures: Document authentication
  • Key Exchange: Secure key distribution
  • Email Encryption: PGP, S/MIME
  • VPN: Secure remote access

Related Algorithms

Explore other encryption algorithms: