RSA is an asymmetric cryptography algorithm based on the mathematical difficulty of factoring large integers.

What is RSA?

RSA uses a key pair (public and private) where the public key can be freely shared, while the private key must be kept secret.

Mathematical Foundations

Key Generation

  1. Choose primes: Select two large prime numbers p and q
  2. Calculate n: n = p × q (modulus)
  3. Calculate φ(n): φ(n) = (p-1) × (q-1) (Euler’s function)
  4. Choose e: e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
  5. Calculate d: d such that (e × d) mod φ(n) = 1

Resulting Keys

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

Operations

Encryption

C = M^e mod n

Where:

  • C = ciphertext
  • M = original message
  • e = public exponent
  • n = modulus

Decryption

M = C^d mod n

Where:

  • M = decrypted message
  • C = ciphertext
  • d = private exponent
  • n = modulus

Implementation

Key Generation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Example of RSA key generation
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization

# Generate 2048-bit RSA key pair
private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
)

# Get public key
public_key = private_key.public_key()

Encryption with Public Key

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Encrypt with public key
from cryptography.hazmat.primitives.asymmetric import padding

message = b"Hello, World!"
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

Decryption with Private Key

1
2
3
4
5
6
7
8
9

# Decrypt with private key
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

Digital Signatures

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# Sign with private key
from cryptography.hazmat.primitives import hashes

signature = private_key.sign(
    message,
    padding.PSS(
        mgf=padding.MGF1(hashes.SHA256()),
        salt_length=padding.PSS.MAX_LENGTH
    ),
    hashes.SHA256()
)

# Verify with public key
try:
    public_key.verify(
        signature,
        message,
        padding.PSS(
            mgf=padding.MGF1(hashes.SHA256()),
            salt_length=padding.PSS.MAX_LENGTH
        ),
        hashes.SHA256()
    )
    print("Valid signature")
except:
    print("Invalid signature")

Key Sizes

Current Recommendations

  • 1024 bits: Obsolete, not recommended
  • 2048 bits: Currently recommended minimum
  • 3072 bits: Recommended for critical applications
  • 4096 bits: For maximum security

Considerations

  • Performance: Larger keys = slower
  • Security: Larger keys = more secure
  • Compatibility: Verify system support

Applications

Data Encryption

  • Hybrid encryption: RSA + AES
  • Key exchange: Establish symmetric keys
  • File encryption: Sensitive files
  • Communications: Secure channels

Authentication

  • Digital signatures: Verify identity
  • Digital certificates: PKI infrastructure
  • Secure login: Passwordless authentication
  • Integrity: Verify no modification

Protocols

  • TLS/SSL: Handshake and authentication
  • SSH: Server authentication
  • PGP/GPG: Email encryption
  • S/MIME: Secure email

Security

Strengths

  • Factorization: Proven mathematical difficulty
  • Standard: Widely implemented
  • Flexible: Multiple applications
  • Mature: Years of analysis

Vulnerabilities

  • Factorization: Advances in algorithms
  • Implementation: Programming errors
  • Side-channel: Side-channel attacks
  • Timing attacks: Timing attacks

Best Practices

  • Key size: Use at least 2048 bits
  • Padding: Use OAEP for encryption
  • Generation: Use secure generators
  • Storage: Protect private keys

Comparison with Other Algorithms

RSA vs ECC

  • RSA: More mature, larger keys
  • ECC: More efficient, smaller keys
  • Performance: ECC generally faster
  • Security: Both are secure when correctly implemented

RSA vs AES

  • RSA: Asymmetric, key exchange
  • AES: Symmetric, data encryption
  • Combined use: RSA for keys, AES for data
  • Hybrid: Common combination in applications

Performance

Expensive Operations

  • Key generation: Very slow
  • Encryption/Decryption: Moderately slow
  • Signatures: Moderately slow
  • Verification: Relatively fast

Optimizations

  • Hardware: Cryptographic accelerators
  • Software: Optimized implementations
  • Cache: Reuse generated keys
  • Hybrid: RSA + AES for efficiency

Best Practices

Key Generation

  • Size: Use at least 2048 bits
  • Primes: Use secure generators
  • Validation: Verify mathematical properties
  • Storage: Protect private keys

Implementation

  • Padding: Use OAEP for encryption
  • Signatures: Use PSS for signatures
  • Libraries: Use proven libraries
  • Testing: Test implementations

Management

  • Rotation: Rotate keys regularly
  • Backup: Backup keys securely
  • Revocation: Revoke compromised keys
  • Audit: Log key usage

References