Asymmetric Cryptography: RSA & Digital Signatures
Asymmetric (public-key) cryptography uses mathematically linked key pairs: a public key (shared openly with anyone) and a private key (kept secret by the owner). Data encrypted with the public key can only be decrypted with the corresponding private key, and vice versa. This elegantly solves the key distribution problem of symmetric cryptography.
---
RSA Algorithm — Step-by-Step
RSA (Rivest-Shamir-Adleman, 1977) is the most widely used asymmetric algorithm. Its security depends on the mathematical difficulty of integer factorization: it is easy to multiply two large primes, but computationally infeasible to factor the product.
RSA Key Generation (Simplified Example):
| Step | Operation | Numerical Example | Mathematical Basis |
|---|---|---|---|
| 1. Choose two primes | Select large primes p and q | p=61, q=53 | Must be large in practice (1024+ bits each) |
| 2. Compute n | n = p × q | n = 61 × 53 = 3233 | n is the modulus (public) |
| 3. Compute φ(n) | φ(n) = (p−1)(q−1) | φ(3233) = 60 × 52 = 3120 | Euler's totient function |
| 4. Choose e | e: 1 < e < φ(n), gcd(e, φ(n)) = 1 | e = 17 | e is public exponent (65537 in practice) |
| 5. Compute d | d × e ≡ 1 (mod φ(n)) | d = 2753 | d is private exponent (extended Euclidean) |
| 6. Public Key | (e, n) | (17, 3233) | Shared openly |
| 7. Private Key | (d, n) | (2753, 3233) | Never revealed |
RSA Encryption and Decryption:
- Encrypt: C = M^e mod n (where M is plaintext as integer)
- Decrypt: M = C^d mod n
Security of RSA:
- With real RSA, p and q are 1024-bit primes each; n is 2048 bits
- Current recommended minimum: 2048-bit RSA
- Factoring a 2048-bit number would take astronomical time with classical computers
- Quantum threat: Shor's algorithm on a quantum computer could break RSA
---
Symmetric vs Asymmetric Cryptography Comparison
| Property | Symmetric (AES) | Asymmetric (RSA) | Hybrid (TLS) |
|---|---|---|---|
| Keys | 1 shared key | 2 keys (public + private) | Both types |
| Speed | Very fast (GB/s) | Slow (KB/s) | Fast overall |
| Key distribution | Problem: must share securely | Solved: public key is public | Uses asymmetric for key exchange |
| Key management scale | n(n-1)/2 keys for n users | 2n keys for n users | Simple |
| Use case | Encrypting large data | Key exchange, signatures | Internet communications |
| Security basis | Key secrecy | Integer factorization / ECDLP | Combined |
| Examples | AES-256, ChaCha20 | RSA-2048, ECDSA, Ed25519 | TLS 1.3, HTTPS, S/MIME |
---
Digital Signatures
A digital signature is a cryptographic mechanism that provides:
- Authentication — Verifies the identity of the signer
- Integrity — Proves the message has not been altered
- Non-repudiation — Signer cannot deny having signed the document
How Digital Signatures Work:
- Signing (by Alice):
- Alice computes hash of message: h = SHA-256(message)
- Alice encrypts hash with her private key: signature = RSA_encrypt(private_key, h)
- Alice sends: [message + signature]
- Verification (by Bob):
- Bob receives [message + signature]
- Bob decrypts signature with Alice's public key: h' = RSA_decrypt(public_key, signature)
- Bob independently computes hash: h = SHA-256(message)
- If h == h': signature is valid; message is authentic and unaltered
| Signature Verification Result | Meaning | Possible Cause |
|---|---|---|
| Valid signature, hashes match | Message authentic, unaltered, from claimed sender | Legitimate document |
| Valid signature, hashes don't match | Message tampered after signing | Man-in-the-middle attack |
| Invalid signature | Not signed by claimed sender | Forgery, wrong key, or message corruption |
---
Message Authentication Codes (MAC)
A MAC (Message Authentication Code) provides integrity and authentication using a shared secret key (symmetric). Unlike digital signatures, MACs do not provide non-repudiation (since both parties have the same key, either could generate the MAC).
HMAC (Hash-based MAC):
- HMAC-SHA256(key, message) = SHA256((key XOR opad) || SHA256((key XOR ipad) || message))
- Uses nested hashing with the secret key to prevent length-extension attacks
- Widely used in: TLS MAC, JWT token signatures, TOTP (time-based OTP)
| Mechanism | Keys | Provides Integrity | Provides Authentication | Provides Non-repudiation | Performance |
|---|---|---|---|---|---|
| Hash (SHA-256) | None | ✅ | ❌ | ❌ | Fastest |
| MAC (HMAC) | Shared symmetric key | ✅ | ✅ (between parties) | ❌ | Fast |
| Digital Signature | Asymmetric key pair | ✅ | ✅ | ✅ | Slow |
---
Public Key Infrastructure (PKI)
PKI is the ecosystem of cryptographic certificates, certificate authorities, and protocols that makes large-scale public key cryptography practical. Without PKI, how would you know Bob's "public key" was really Bob's and not an attacker's?
PKI Components:
| Component | Role | Example | Trust Basis |
|---|---|---|---|
| Certificate Authority (CA) | Issues and signs digital certificates | DigiCert, Let's Encrypt | Root CA trusted by OS/browsers |
| Digital Certificate (X.509) | Binds public key to identity | HTTPS certificate for amazon.com | CA's digital signature on cert |
| Certificate Revocation List (CRL) | List of revoked certificates | CRL published by CA | Must be checked before trusting |
| OCSP | Online certificate validity check | Real-time revocation check | CA responds with valid/revoked |
| Registration Authority (RA) | Verifies identity before cert issuance | Domain validation, EV validation | Policy-based identity verification |
Exam Tip: Digital Signature = sign with PRIVATE key, verify with PUBLIC key. Encryption = encrypt with PUBLIC key, decrypt with PRIVATE key. This is the opposite direction and a common exam trick. RSA security = difficulty of factoring product of two large primes. Digital signatures provide authentication, integrity, AND non-repudiation.
---
Study Deep: Public-Key Cryptography
- Elliptic Curve Cryptography (ECC) is more efficient than RSA: ECC achieves equivalent security to RSA with much shorter keys: 256-bit ECC ≈ 3072-bit RSA in security strength. Shorter keys mean faster operations and lower power consumption — critical for IoT, mobile devices, and TLS performance. Most modern TLS connections use ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) for key exchange.
- Certificate Transparency prevents fraudulent certificates: Google's Certificate Transparency (CT) project requires all publicly trusted certificates to be logged in public, auditable CT logs. This allows detection of fraudulently issued certificates (mis-issuance) within hours. The 2011 DigiNotar hack (CA compromised, fraudulent Google certs issued) accelerated the adoption of CT.
- Perfect Forward Secrecy (PFS) protects past sessions: In classic RSA key exchange, if the server's private key is ever compromised, all past recorded sessions can be decrypted. PFS (using ephemeral Diffie-Hellman or ECDHE) generates fresh session keys for every connection, so compromising the server key today does not decrypt yesterday's sessions. TLS 1.3 mandates PFS.
- Blockchain uses asymmetric cryptography: Bitcoin and Ethereum use ECDSA (Elliptic Curve Digital Signature Algorithm) for transaction signing. Your private key signs transactions; the network verifies with your public key (Bitcoin address). Losing your private key means losing your funds permanently — there is no recovery mechanism.
- The RSA 768-bit factoring milestone: In 2009, researchers factored a 768-bit RSA modulus using distributed computing over 2.5 years (special number field sieve algorithm). This is why 1024-bit RSA is now considered deprecated and 2048-bit is the minimum. NIST recommends 3072-bit or 4096-bit for post-2030 security.