Asymmetric Encryption

Asymmetric Encryption: Core Concepts

Symmetric encryption has a fundamental problem: both parties need the same key, and sharing that key securely is difficult. Asymmetric encryption solves this by using a mathematically related key pair — a public key that can be shared openly and a private key that must be kept secret. Data encrypted with the public key can only be decrypted with the private key.

How Key Pairs Work

The security of asymmetric encryption relies on mathematical problems that are easy to compute in one direction but computationally infeasible to reverse:

• RSA — Based on the difficulty of factoring large composite numbers. Given two large primes p and q, computing n = p × q is easy, but factoring n back into p and q is infeasible for sufficiently large n.
• ECC (Elliptic Curve Cryptography) — Based on the difficulty of the elliptic curve discrete logarithm problem. Given points P and Q = kP on an elliptic curve, finding k is computationally infeasible.
• Diffie-Hellman — Based on the difficulty of the discrete logarithm problem in finite fields. Enables two parties to establish a shared secret over an insecure channel.

RSA in Detail

RSA key generation:

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

The public key is (n, e). The private key is (n, d).

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

The security relies on the fact that computing d from e and n requires knowing φ(n), which requires factoring n. For RSA-2048, n is a 2048-bit number — factoring it would take classical computers millions of years.

ECC: Smaller Keys, Equivalent Security

ECC provides the same security as RSA with much smaller keys:

A 256-bit ECC key provides equivalent security to a 3072-bit RSA key. This makes ECC ideal for mobile devices, IoT, and any environment where bandwidth, storage, or processing power is limited.

Digital Signatures

Asymmetric encryption also enables digital signatures, which provide authentication, integrity, and non-repudiation:

1. The sender hashes the message
2. The sender encrypts the hash with their private key (this is the signature)
3. The recipient decrypts the signature with the sender's public key to recover the hash
4. The recipient hashes the received message and compares it to the decrypted hash

If the hashes match, the message is authentic (came from the holder of the private key), intact (was not modified), and non-repudiable (the sender cannot deny sending it).

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

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

# Sign a message
message = b"This is a message to sign."
signature = private_key.sign(
    message,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    hashes.SHA256()
)

# Verify the signature
try:
    public_key.verify(signature, message,
        padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
        hashes.SHA256()
    )
    print("Signature valid.")
except:
    print("Signature invalid.")

Where It Fits

Asymmetric encryption solves the key distribution problem that makes symmetric encryption impractical for large-scale communication. It is the foundation of TLS, SSH, PGP, and blockchain. Study Symmetric Encryption first to understand what asymmetric encryption complements, then move to PKI and Certificates to see how public keys are distributed and trusted.

Asymmetric Encryption: Practice

Asymmetric encryption is mathematically complex but operationally straightforward. The exercises below cover key generation, encryption/decryption, and digital signatures.

Exercise 1: Generate RSA Keys with OpenSSL

# Generate a 2048-bit RSA private key
openssl genrsa -out private.pem 2048

# Extract the public key
openssl rsa -in private.pem -pubout -out public.pem

# Encrypt a file with the public key
openssl pkeyutl -encrypt -in secret.txt -out secret.enc \
  -pubin -inkey public.pem

# Decrypt with the private key
openssl pkeyutl -decrypt -in secret.enc -out secret_decrypted.txt \
  -inkey private.pem

Exercise 2: Sign and Verify a Document

# Sign a document (creates a detached signature)
openssl dgst -sha256 -sign private.pem -out document.sig document.pdf

# Verify the signature
openssl dgst -sha256 -verify public.pem -signature document.sig document.pdf
# Output: Verified OK

If the document is modified after signing, the verification fails:

echo "tampered" >> document.pdf
openssl dgst -sha256 -verify public.pem -signature document.sig document.pdf
# Output: Verification Failure

Exercise 3: Generate an ECC Key Pair

# Generate an ECC private key using the P-256 curve
openssl ecparam -name prime256v1 -genkey -noout -out ecc_private.pem

# Extract the public key
openssl ec -in ecc_private.pem -pubout -out ecc_public.pem

# Sign with ECC
openssl dgst -sha256 -sign ecc_private.pem -out ecc_document.sig document.pdf

# Verify with ECC
openssl dgst -sha256 -verify ecc_public.pem -signature ecc_document.sig document.pdf

ECC keys are much smaller than RSA keys for equivalent security. A P-256 key is 256 bits, compared to 3072 bits for equivalent RSA security.

Exercise 4: Diffie-Hellman Key Exchange

Simulate two parties establishing a shared secret:

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
import os

# Alice generates her key pair
alice_private = ec.generate_private_key(ec.SECP256R1())
alice_public = alice_private.public_key()

# Bob generates his key pair
bob_private = ec.generate_private_key(ec.SECP256R1())
bob_public = bob_private.public_key()

# Alice computes the shared secret using Bob's public key
alice_shared = alice_private.exchange(ec.ECDH(), bob_public)

# Bob computes the shared secret using Alice's public key
bob_shared = bob_private.exchange(ec.ECDH(), alice_public)

# Both derive the same symmetric key
alice_key = HKDF(algorithm=hashes.SHA256(), length=32, salt=None, info=b'handshake').derive(alice_shared)
bob_key = HKDF(algorithm=hashes.SHA256(), length=32, salt=None, info=b'handshake').derive(bob_shared)

assert alice_key == bob_key  # Both parties now share the same symmetric key

Check Your Understanding

• Why can't an attacker derive the private key from the public key in RSA?
• What is the advantage of ECC over RSA?
• How does a digital signature provide non-repudiation?

Asymmetric Encryption: Trade-offs and Interviews

Asymmetric encryption solves the key distribution problem but introduces its own challenges. Understanding these trade-offs is essential for choosing the right tool for each security problem.

When Asymmetric Encryption Is the Wrong Tool

• Bulk data encryption: Asymmetric encryption is orders of magnitude slower than symmetric encryption. Never use RSA or ECC to encrypt large files or streams. Use asymmetric encryption to exchange a symmetric key, then use symmetric encryption for the data.
• Password storage: Asymmetric encryption is not used for password storage. Passwords are hashed (with salt) using slow hash functions like bcrypt or Argon2.
• Real-time communication: The computational overhead of asymmetric encryption makes it unsuitable for real-time encryption of voice or video. Use it for the initial key exchange, then switch to symmetric encryption.

The Quantum Computing Threat

Shor's algorithm, running on a sufficiently powerful quantum computer, can factor large numbers and solve the discrete logarithm problem in polynomial time. This would break RSA and ECC completely.

Current quantum computers are not powerful enough to break RSA-2048 (they would need thousands of stable qubits; current machines have hundreds of noisy ones). However, the threat is real enough that NIST has been running a post-quantum cryptography standardization process. The selected algorithms (CRYSTALS-Kyber for key exchange, CRYSTALS-Dilithium for signatures) are based on lattice problems that are believed to be resistant to quantum attacks.

Key Size and Security

As key sizes increase, security improves but performance decreases:

RSA-1024 is no longer considered secure. RSA-2048 is the minimum for new deployments, with RSA-3072 recommended for long-term security. ECC-256 provides equivalent security to RSA-3072 with much better performance.

How This Comes Up in Interviews

• "What is the difference between RSA and ECC?" RSA is based on the difficulty of factoring large numbers. ECC is based on the elliptic curve discrete logarithm problem. ECC provides equivalent security with much smaller keys, making it faster and more efficient for mobile and IoT devices.
• "How does a digital signature work?" The sender hashes the message and encrypts the hash with their private key. The recipient decrypts the signature with the sender's public key and compares the result to their own hash of the message. If they match, the message is authentic and intact.
• "What happens when quantum computers become practical?" Shor's algorithm would break RSA and ECC. NIST has selected post-quantum algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium) based on lattice problems. Organizations should plan for crypto-agility — the ability to swap algorithms when needed.