Public Key Cryptography
Explore the fascinating world of modern cryptographic systems
Introduction to Public Key Cryptography
Public key cryptography, also known as asymmetric cryptography, revolutionized secure communication by solving the key distribution problem. Unlike symmetric cryptography where the same key is used for encryption and decryption, public key systems use mathematically related key pairs.
Key Generation
Generate mathematically related public and private key pairs
Public Distribution
Share public key openly while keeping private key secret
Secure Communication
Encrypt with public key, decrypt with private key
Key Applications
- Digital Signatures: Verify authenticity and integrity of messages
- Key Exchange: Securely establish shared secrets over insecure channels
- Secure Communications: Enable encrypted email, messaging, and web traffic
- Authentication: Verify identity in digital certificates and PKI systems
Requirements for Public Key Systems
Mathematical Requirements
- Computationally easy to generate key pairs
- Easy to encrypt/decrypt with appropriate keys
- Computationally infeasible to derive private key from public key
- Computationally infeasible to decrypt without private key
RSA Algorithm
RSA (Rivest-Shamir-Adleman) is one of the most widely used public key cryptosystems, based on the computational difficulty of factoring large integers.
๐ง Interactive RSA Demo
Click "Generate Keys" to start the RSA demonstration
RSA Key Generation Algorithm
Choose Primes
Select two large prime numbers p and q
Calculate n
Compute n = p ร q (the modulus)
Calculate ฯ(n)
Compute ฯ(n) = (p-1) ร (q-1)
Choose e
Select e such that gcd(e, ฯ(n)) = 1
Calculate d
Find d such that d ร e โก 1 (mod ฯ(n))
Key Pair
Public: (n, e), Private: (n, d)
Computational Aspects
function rsaEncrypt(message, publicKey) {
const {n, e} = publicKey;
return modularExponentiation(message, e, n);
}
// RSA Decryption: M = C^d mod n
function rsaDecrypt(ciphertext, privateKey) {
const {n, d} = privateKey;
return modularExponentiation(ciphertext, d, n);
}
// Efficient modular exponentiation
function modularExponentiation(base, exponent, modulus) {
let result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 === 1) {
result = (result * base) % modulus;
}
exponent = Math.floor(exponent / 2);
base = (base * base) % modulus;
}
return result;
}
Security Analysis
RSA security depends on the difficulty of factoring large integers. Current recommendations suggest:
Key Size: Minimum 2048 bits (recommended 3072+ bits for future security)
โ ๏ธ RSA Vulnerabilities
- Factorization Attacks: Quantum computers threaten RSA security
- Timing Attacks: Side-channel attacks on implementation
- Chosen Ciphertext Attacks: Padding oracle attacks
- Small Exponent Attacks: When e is small and message is short
Diffie-Hellman Key Exchange
The Diffie-Hellman key exchange algorithm allows two parties to establish a shared secret key over an insecure channel without prior communication.
๐ค Interactive Diffie-Hellman Demo
Click "Initialize Parameters" to start the Diffie-Hellman demonstration
Alice
Generates private key 'a'
Computes A = g^a mod p
Public Channel
Exchanges public values
A and B are transmitted
Bob
Generates private key 'b'
Computes B = g^b mod p
Algorithm Steps
Public Parameters
Agree on prime p and generator g
Private Keys
Alice picks 'a', Bob picks 'b'
Public Keys
A = g^a mod p, B = g^b mod p
Exchange
Alice sends A, Bob sends B
Shared Secret
Both compute g^(ab) mod p
class DiffieHellman {
constructor(p, g) {
this.p = p; // Large prime
this.g = g; // Generator
}
generatePrivateKey() {
// Generate random private key
return Math.floor(Math.random() * (this.p - 2)) + 1;
}
generatePublicKey(privateKey) {
// Compute g^privateKey mod p
return this.modPow(this.g, privateKey, this.p);
}
computeSharedSecret(otherPublicKey, myPrivateKey) {
// Compute otherPublicKey^myPrivateKey mod p
return this.modPow(otherPublicKey, myPrivateKey, this.p);
}
modPow(base, exponent, modulus) {
let result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 === 1) {
result = (result * base) % modulus;
}
exponent = Math.floor(exponent / 2);
base = (base * base) % modulus;
}
return result;
}
}
Security Threats & Man-in-the-Middle Attacks
Understanding security vulnerabilities is crucial for implementing robust cryptographic systems. The Man-in-the-Middle (MITM) attack is a fundamental threat to key exchange protocols.
๐จ Man-in-the-Middle Attack Simulation
Click "Simulate MITM Attack" to see how an attacker can intercept communications
Alice
Believes she's talking to Bob
Actually talking to Eve
Eve (Attacker)
Intercepts all communications
Establishes separate keys with both
Bob
Believes he's talking to Alice
Actually talking to Eve
Attack Scenarios
Interception
Attacker intercepts initial key exchange
Impersonation
Establishes separate sessions with both parties
Relay
Decrypts, reads, and re-encrypts messages
Control
Can modify or inject malicious content
Countermeasures
๐ก๏ธ Protection Strategies
- Authentication: Use digital certificates and PKI
- Key Verification: Out-of-band verification of public keys
- Perfect Forward Secrecy: Use ephemeral keys for each session
- Certificate Transparency: Monitor certificate issuance
- Key Pinning: Pin expected public keys in applications
Other Cryptanalytic Attacks
Brute Force
Exhaustive key search attacks
Side Channel
Timing, power, and electromagnetic attacks
Mathematical
Factorization and discrete logarithm attacks
Quantum
Shor's algorithm threatens current systems