Asymmetric Encryption

Public Key Cryptography

Two Keys, Enhanced Security

Asymmetric Encryption Definition

Asymmetric Encryption uses a pair of mathematically related keys: a public key for encryption and a private key for decryption. Also known as public key cryptography.

Key Characteristics:

Key Pair: Two different but related keys
Public Key: Shared openly, used for encryption
Private Key: Kept secret, used for decryption
Mathematical Relationship: Keys are mathematically linked

Asymmetric Encryption Process

Encryption Process:
Plaintext + Public Key → Encryption Algorithm → Ciphertext

Decryption Process:
Ciphertext + Private Key → Decryption Algorithm → Plaintext

Mathematical Representation:
E(Kpublic, P) = C (Encryption)
D(Kprivate, C) = P (Decryption)

Where:
Kpublic = Public Key
Kprivate = Private Key
P = Plaintext
C = Ciphertext

Understanding the Key Pair

Public Key:

Shared freely with everyone
Used for encryption
Can verify digital signatures
No confidentiality required
Often published in directories

Private Key:

Kept absolutely secret
Used for decryption
Creates digital signatures
Must be protected
Never shared with anyone

Mathematical Foundation

One-Way Functions: Easy to compute in one direction, computationally difficult to reverse

Common Mathematical Problems:

Integer Factorization: Easy to multiply, hard to factor (RSA)
Discrete Logarithm: Easy to exponentiate, hard to find logarithm (DH, ElGamal)
Elliptic Curve: Point multiplication easy, discrete log hard (ECC)

Example: 7 × 11 = 77 (Easy)
What two primes multiply to give 77? (Harder for large numbers)

RSA Algorithm

Most Famous Asymmetric Algorithm: Named after Rivest, Shamir, and Adleman (1977)

RSA Key Generation:

Choose two large prime numbers (p, q)
Calculate n = p × q
Calculate φ(n) = (p-1)(q-1)
Choose e such that gcd(e, φ(n)) = 1
Calculate d such that ed ≡ 1 (mod φ(n))
Public key: (n, e), Private key: (n, d)

RSA Simple Example

Key Generation (small numbers for illustration):
1. Choose p = 3, q = 11
2. n = 3 × 11 = 33
3. φ(n) = (3-1)(11-1) = 2 × 10 = 20
4. Choose e = 3 (gcd(3,20) = 1)
5. Find d: 3d ≡ 1 (mod 20), so d = 7

Keys:
Public Key: (33, 3)
Private Key: (33, 7)

Encryption of message m = 4:
c = 4³ mod 33 = 64 mod 33 = 31

Decryption:
m = 31⁷ mod 33 = 4 ✓

Other Asymmetric Algorithms

Algorithm	Mathematical Basis	Key Size	Performance	Use Case
RSA	Integer Factorization	1024-4096 bits	Slow	General Purpose
ECC	Elliptic Curves	160-521 bits	Faster	Mobile, IoT
Diffie-Hellman	Discrete Logarithm	1024-3072 bits	Moderate	Key Exchange
ElGamal	Discrete Logarithm	1024-3072 bits	Slow	Digital Signatures

Digital Signatures

Reverse Process: Sign with private key, verify with public key

Signing Process:
Document + Private Key → Digital Signature

Verification Process:
Document + Signature + Public Key → Valid/Invalid

Properties:
• Authentication: Proves who signed
• Non-repudiation: Signer can't deny
• Integrity: Detects tampering

Diffie-Hellman Key Exchange

Revolutionary Concept: Two parties can establish a shared secret over an insecure channel without prior shared information

Simplified Process:
1. Alice and Bob agree on public values (p, g)
2. Alice chooses private 'a', calculates A = g^a mod p
3. Bob chooses private 'b', calculates B = g^b mod p
4. Alice sends A to Bob, Bob sends B to Alice
5. Alice calculates B^a mod p = g^(ab) mod p
6. Bob calculates A^b mod p = g^(ab) mod p
7. Both have same shared secret: g^(ab) mod p

Advantages of Asymmetric Encryption

Key Management Benefits:

No Prior Shared Secret: No need for secure key exchange
Scalability: n users need only n key pairs
Public Distribution: Public keys can be shared openly
Digital Signatures: Provides authentication and non-repudiation

Security Benefits:

Forward Secrecy: Past communications remain secure
Identity Verification: Confirms sender identity
No Key Distribution Problem: Solves symmetric encryption's main weakness

Limitations of Asymmetric Encryption

Performance Issues:

Slow Speed: 100-1000x slower than symmetric
High Resource Usage: CPU and memory intensive
Large Key Sizes: Requires bigger keys for equivalent security
Power Consumption: Not ideal for battery-powered devices

Practical Challenges:

Key Authentication: How to verify public key ownership?
Key Management: Certificate authorities and PKI complexity
Implementation Complexity: More prone to implementation errors

Hybrid Cryptosystems

Best of Both Worlds: Combine asymmetric and symmetric encryption

Typical Hybrid Process:
1. Generate random symmetric key (AES key)
2. Encrypt data with symmetric key (fast)
3. Encrypt symmetric key with recipient's public key
4. Send encrypted data + encrypted key

Decryption:
1. Decrypt symmetric key with private key
2. Use symmetric key to decrypt data

Examples: HTTPS, PGP, S/MIME

Public Key Infrastructure (PKI)

PKI Purpose: Framework for managing public key certificates and ensuring trust

PKI Components:

Certificate Authority (CA): Issues and manages certificates
Registration Authority (RA): Verifies certificate requests
Digital Certificates: Bind public keys to identities
Certificate Repository: Stores and distributes certificates
Certificate Revocation Lists (CRL): Lists revoked certificates

Real-World Applications

Where Asymmetric Encryption is Used:

HTTPS/TLS: Secure web communications
Email Security: PGP, S/MIME encrypted email
Digital Signatures: Document signing, code signing
VPN Authentication: Identity verification
Cryptocurrency: Bitcoin, Ethereum transactions
Software Distribution: Verify software authenticity
IoT Device Authentication: Secure device identity

Security Best Practices

Use Adequate Key Sizes: RSA 2048+, ECC 256+
Protect Private Keys: Hardware security modules
Verify Public Keys: Use trusted certificate authorities
Regular Key Rotation: Update keys periodically
Secure Random Number Generation: Quality entropy sources
Implement Proper Padding: OAEP for RSA
Use Standard Libraries: Avoid custom implementations

Attacks on Asymmetric Encryption

Attack Categories:

Mathematical Attacks: Factor large integers, solve discrete logarithm
Side-Channel Attacks: Timing, power analysis
Implementation Attacks: Poor random number generation
Social Engineering: Fake certificates, CA compromise
Quantum Attacks: Shor's algorithm breaks RSA, ECC

Quantum Threat: Current asymmetric algorithms vulnerable to quantum computers

Post-Quantum Cryptography

Future Challenge: Quantum computers will break RSA, ECC, and Diffie-Hellman

Post-Quantum Candidates:

Lattice-based: CRYSTALS-Kyber, CRYSTALS-Dilithium
Hash-based: SPHINCS+
Code-based: Classic McEliece
Multivariate: Rainbow (broken), others under research

NIST Standards: CRYSTALS-Kyber (key exchange) and CRYSTALS-Dilithium (signatures) selected as primary standards

Performance Comparison

Operation	AES-256	RSA-2048	ECC P-256	Ratio
Key Generation	Instant	~100ms	~10ms	1:1000:100
Encryption (1KB)	~1μs	~1ms	~100μs	1:1000:100
Decryption (1KB)	~1μs	~10ms	~100μs	1:10000:100
Key Size	256 bits	2048 bits	256 bits	1:8:1

RSA Implementation Example

Python Example (using cryptography library):

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

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

# Encrypt
message = b"Secret message"
ciphertext = public_key.encrypt(message,
    padding.OAEP(mgf=padding.MGF1(hashes.SHA256()),
                    algorithm=hashes.SHA256(), label=None))

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

Key Takeaways

Asymmetric encryption uses two mathematically related keys
Solves the key distribution problem of symmetric encryption
Enables digital signatures and authentication
Much slower than symmetric encryption
Usually combined with symmetric encryption in practice
Foundation of modern secure communications
Quantum computers pose future threat to current algorithms

Remember: Public key can be shared, private key must remain absolutely secret

Thank You

Questions & Discussion

Next: Introduction to Account & Data Security