π Public-Key Infrastructure, Trapdoor Functions & Intractable Hard Problems
Symmetric encryption solves bulk data privacy with remarkable speed, but it suffers from a fundamental logistical barrier known as the Key Distribution Problem: before two communicating entities can exchange ciphertext, they must securely agree upon a secret key over an unmonitored channel. Asymmetric Cryptography (Public-Key Cryptography), pioneered by Whitfield Diffie, Martin Hellman, Ralph Merkle, Ronald Rivest, Adi Shamir, and Leonard Adleman, eliminates this requirement using mathematically matched key pairs: an openly publishable Public Key for encryption or signature verification, and a closely held Private Key for decryption or signing. These systems rely on Trapdoor One-Way Functionsβmathematical operations that are computationally trivial to calculate in the forward direction, yet physically impossible to invert without specialized side information ("the trapdoor"). The security of modern asymmetric protocols rests on three computationally intractable problems: the Integer Factorization Problem (IFP) in RSA, the Discrete Logarithm Problem (DLP) in Diffie-Hellman and DSA, and the Elliptic Curve Discrete Logarithm Problem (ECDLP) in ECC.
ASYMMETRIC CRYPTOGRAPHIC FAMILIES & UNDERLYING MATHEMATICAL TRAPDOORS:
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β TRAPDOOR ONE-WAY FUNCTION CONCEPT: β
β Forward Direction : y = f(x) βββΊ Computationally trivial (e.g., O(log n)) β
β Reverse Direction : x = f^(-1)(y) βββΊ Infeasible (Sub-exponential / Exponential) β
β Trapdoor Inversion: x = f^(-1)(y, Trapdoor)βββΊ Trivial when secret mathematical key is known β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β
ββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββ
βΌ βΌ βΌ
ββββββββββββββββββββββββββββββββ ββββββββββββββββββββββββββββββββ ββββββββββββββββββββββββββββββββ
β RSA (Rivest-Shamir-Adleman) β β DIFFIE-HELLMAN (DH / DHE) β β ELLIPTIC CURVE CRYPTO (ECC) β
ββββββββββββββββββββββββββββββββ€ ββββββββββββββββββββββββββββββββ€ ββββββββββββββββββββββββββββββββ€
β Hard Problem: β β Hard Problem: β β Hard Problem: β
β Integer Factorization (IFP) β β Discrete Logarithm (DLP) β β EC Discrete Logarithm (ECDLP)β
β Given n = p * q, find p & q. β β Given g^a mod p, recover a. β β Given Q = d * G, recover d. β
β β β β β β
β Trapdoor: β β Trapdoor: β β Trapdoor: β
β Euler Totient phi(n)=(p-1)(q-1)β Private exponent a or b β Scalar multiplier integer d β
β β β β β β
β Current Secure Key Size: β β Current Secure Key Size: β β Current Secure Key Size: β
β 2048 to 4096 bits β β 2048 to 4096 bits (MODP) β β 256 to 384 bits (secp256r1) β
β β β β β β
β Primary Applications: β β Primary Applications: β β Primary Applications: β
β Legacy TLS, S/MIME, PGP β β Ephemeral Key Exchange (DHE) β β TLS 1.3 (ECDHE), Ed25519 β
ββββββββββββββββββββββββββββββββ ββββββββββββββββββββββββββββββββ ββββββββββββββββββββββββββββββββ
import math
def egcd(a: int, b: int):
"""Extended Euclidean Algorithm: returns (gcd, x, y) such that a*x + b*y = gcd"""
if a == 0:
return b, 0, 1
g, x1, y1 = egcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return g, x, y
def modular_inverse(e: int, phi: int) -> int:
"""Computes private exponent d = e^(-1) mod phi(n)"""
g, x, _ = egcd(e, phi)
if g != 1:
raise ValueError(f"e={e} and phi={phi} are not coprime!")
return (x % phi + phi) % phi
class RsaCryptosystem:
def __init__(self, p: int, q: int, e: int = 65537):
if p == q:
raise ValueError("Primes p and q must be distinct!")
self.p = p
self.q = q
# Modulus n
self.n = p * q
# Euler's Totient Function phi(n)
self.phi = (p - 1) * (q - 1)
self.e = e
if math.gcd(self.e, self.phi) != 1:
raise ValueError(f"Exponent e={e} not coprime to phi={self.phi}")
# Compute private exponent d
self.d = modular_inverse(self.e, self.phi)
def encrypt(self, plaintext_int: int) -> int:
"""Ciphertext C = M^e mod n"""
if plaintext_int >= self.n:
raise ValueError("Message representative cannot exceed modulus n!")
return pow(plaintext_int, self.e, self.n)
def decrypt(self, ciphertext_int: int) -> int:
"""Plaintext M = C^d mod n"""
return pow(ciphertext_int, self.d, self.n)
if __name__ == "__main__":
# Academic primes (Small demonstration primes; production requires 1024-bit primes)
prime_p = 61
prime_q = 53
# Use smaller exponent e=17 for small modulus demo
rsa = RsaCryptosystem(p=prime_p, q=prime_q, e=17)
message = 65 # Numerical encoding of character 'A'
ciphertext = rsa.encrypt(message)
decrypted = rsa.decrypt(ciphertext)
print(f"[*] Selected Primes : p={rsa.p}, q={rsa.q}")
print(f"[*] Modulus n (p * q) : {rsa.n}")
print(f"[*] Euler's phi(n) : {rsa.phi}")
print(f"[*] Public Key (e, n) : ({rsa.e}, {rsa.n})")
print(f"[*] Private Key (d, n): ({rsa.d}, {rsa.n})")
print(f"[*] Original Message : {message}")
print(f"[+] RSA Ciphertext : {ciphertext} (via {message}^{rsa.e} mod {rsa.n})")
print(f"[β] Recovered Message : {decrypted} (via {ciphertext}^{rsa.d} mod {rsa.n})")
assert decrypted == message, "RSA verification failed!"
import random
class DiffieHellmanParticipant:
def __init__(self, name: str, p: int, g: int):
self.name = name
self.p = p
self.g = g
# Ephemeral private exponent chosen at random
self.private_key = random.randint(2, p - 2)
# Public key: A = g^a mod p
self.public_key = pow(self.g, self.private_key, self.p)
def compute_shared_secret(self, peer_public_key: int) -> int:
"""K = (B)^a mod p = (g^b)^a mod p = g^(ab) mod p"""
return pow(peer_public_key, self.private_key, self.p)
if __name__ == "__main__":
# Domain parameters: Public prime p, generator g (primitive root modulo p)
PRIME_P = 2357
GENERATOR_G = 2
print("--- SCENARIO 1: NORMAL DIFFIE-HELLMAN KEY EXCHANGE ---")
alice = DiffieHellmanParticipant("Alice", PRIME_P, GENERATOR_G)
bob = DiffieHellmanParticipant("Bob", PRIME_P, GENERATOR_G)
# Public exchange over wire
k_alice = alice.compute_shared_secret(bob.public_key)
k_bob = bob.compute_shared_secret(alice.public_key)
print(f"[*] Public Wire: Alice PubKey={alice.public_key} | Bob PubKey={bob.public_key}")
print(f"[β] Alice Computed Secret: {k_alice}")
print(f"[β] Bob Computed Secret : {k_bob}")
assert k_alice == k_bob, "Normal DH calculation failed!"
print("\n--- SCENARIO 2: UNAUTHENTICATED MAN-IN-THE-MIDDLE (MitM) ATTACK ---")
# Eve intercepts wire traffic between Alice and Bob
eve = DiffieHellmanParticipant("Eve (Attacker)", PRIME_P, GENERATOR_G)
# Alice transmits her public key to Bob, but Eve intercepts it
# Eve sends her own public key to Bob, impersonating Alice
k_eve_to_bob = eve.compute_shared_secret(bob.public_key)
k_bob_compromised = bob.compute_shared_secret(eve.public_key)
# Bob transmits his public key to Alice, but Eve intercepts it
# Eve sends her own public key to Alice, impersonating Bob
k_eve_to_alice = eve.compute_shared_secret(alice.public_key)
k_alice_compromised = alice.compute_shared_secret(eve.public_key)
print(f"[!] Eve splits key exchange into two independent cryptographic legs:")
print(f" Alice βββ [Shared Key: {k_alice_compromised}] βββΊ Eve βββ [Shared Key: {k_bob_compromised}] βββΊ Bob")
print(f"[!] Alice encrypts for Eve; Eve decrypts, modifies payload, and re-encrypts for Bob!")
print("[β] Architectural Defense: Classic Diffie-Hellman lacks identity authentication;")
print(" MitM is stopped by signing public keys via X.509 certificates (mTLS / ECDHE-RSA).")
from dataclasses import dataclass
from typing import Optional
def mod_inv(a: int, m: int) -> int:
return pow(a, -1, m)
@dataclass
class Point:
x: Optional[int]
y: Optional[int]
is_infinity: bool = False
class EllipticCurveFp:
"""
Short Weierstrass Equation: y^2 = x^3 + ax + b (mod p)
Singular Discriminant Condition: 4a^3 + 27b^2 != 0 (mod p)
"""
def __init__(self, a: int, b: int, p: int):
self.a = a
self.b = b
self.p = p
# Verify non-singularity
disc = (4 * pow(a, 3, p) + 27 * pow(b, 2, p)) % p
if disc == 0:
raise ValueError("Singular curve! 4a^3 + 27b^2 == 0 (mod p)")
def point_at_infinity(self) -> Point:
return Point(None, None, is_infinity=True)
def is_on_curve(self, pt: Point) -> bool:
if pt.is_infinity:
return True
lhs = pow(pt.y, 2, self.p)
rhs = (pow(pt.x, 3, self.p) + self.a * pt.x + self.b) % self.p
return lhs == rhs
def add_points(self, p1: Point, p2: Point) -> Point:
"""Computes P1 + P2 on the elliptic curve group."""
if p1.is_infinity:
return p2
if p2.is_infinity:
return p1
# Case 1: P1 == -P2 (Vertical line: slope is infinite -> Point at Infinity)
if p1.x == p2.x and (p1.y != p2.y or p1.y == 0):
return self.point_at_infinity()
# Case 2: Point Doubling (P1 == P2)
if p1.x == p2.x and p1.y == p2.y:
# Slope lambda = (3*x1^2 + a) / (2*y1) mod p
numerator = (3 * pow(p1.x, 2, self.p) + self.a) % self.p
denominator = (2 * p1.y) % self.p
slope = (numerator * mod_inv(denominator, self.p)) % self.p
# Case 3: Distinct Points (P1 != P2)
else:
# Slope lambda = (y2 - y1) / (x2 - x1) mod p
numerator = (p2.y - p1.y) % self.p
denominator = (p2.x - p1.x) % self.p
slope = (numerator * mod_inv(denominator, self.p)) % self.p
# Resulting coordinates
x3 = (pow(slope, 2, self.p) - p1.x - p2.x) % self.p
y3 = (slope * (p1.x - x3) - p1.y) % self.p
return Point(x3, y3)
def scalar_multiply(self, k: int, pt: Point) -> Point:
"""Computes k * P via Double-and-Add algorithm (Binary Exponentiation)."""
result = self.point_at_infinity()
addend = pt
while k > 0:
if k & 1:
result = self.add_points(result, addend)
addend = self.add_points(addend, addend)
k >>= 1
return result
if __name__ == "__main__":
# Academic Prime Curve: y^2 = x^3 + 2x + 2 (mod 17)
curve = EllipticCurveFp(a=2, b=2, p=17)
base_generator = Point(5, 1)
print(f"[*] Base Point G is on curve? {curve.is_on_curve(base_generator)}")
# Point Doubling: 2 * G
pt_2g = curve.add_points(base_generator, base_generator)
print(f"[+] 2 * G Coordinates: ({pt_2g.x}, {pt_2g.y})")
# Scalar multiplication via Double-and-Add: 3 * G
pt_3g = curve.scalar_multiply(3, base_generator)
print(f"[+] 3 * G Coordinates: ({pt_3g.x}, {pt_3g.y})")
assert curve.is_on_curve(pt_3g)
# Utilizing the EllipticCurveFp engine defined in Example 3
class EcdhParticipant:
def __init__(self, name: str, curve: EllipticCurveFp, generator: Point, private_scalar: int):
self.name = name
self.curve = curve
self.g = generator
# Private key d (Scalar integer)
self.d = private_scalar
# Public key Q = d * G (Point on curve)
self.public_key = self.curve.scalar_multiply(self.d, self.g)
def compute_shared_secret_point(self, peer_public_point: Point) -> Point:
"""Shared Secret Point S = d_mine * Q_peer"""
return self.curve.scalar_multiply(self.d, peer_public_point)
if __name__ == "__main__":
from __main__ import EllipticCurveFp, Point
# Curve: y^2 = x^3 + 2x + 2 (mod 17)
ec_curve = EllipticCurveFp(a=2, b=2, p=17)
g_point = Point(5, 1)
# 1. Alice selects private scalar d_A = 3
alice_ecdh = EcdhParticipant("Alice", ec_curve, g_point, private_scalar=3)
# 2. Bob selects private scalar d_B = 7
bob_ecdh = EcdhParticipant("Bob", ec_curve, g_point, private_scalar=7)
print(f"[*] Alice Public Key Q_A (3 * G) : ({alice_ecdh.public_key.x}, {alice_ecdh.public_key.y})")
print(f"[*] Bob Public Key Q_B (7 * G) : ({bob_ecdh.public_key.x}, {bob_ecdh.public_key.y})")
# 3. Transmit public keys over wire and compute shared point
shared_alice = alice_ecdh.compute_shared_secret_point(bob_ecdh.public_key)
shared_bob = bob_ecdh.compute_shared_secret_point(alice_ecdh.public_key)
print(f"[β] Alice Computed Shared Point S: ({shared_alice.x}, {shared_alice.y})")
print(f"[β] Bob Computed Shared Point S : ({shared_bob.x}, {shared_bob.y})")
assert (shared_alice.x, shared_alice.y) == (shared_bob.x, shared_bob.y), "ECDH failed!"
print("[β] ECDH Invariant Holds: S = 3 * (7 * G) = 7 * (3 * G) = 21 * G")
FORWARD SECRECY THREAT DYNAMICS: STATIC RSA VS. EPHEMERAL ECDHE:
1. STATIC RSA KEY EXCHANGE (LEGACY TLS 1.2 - DEPRECATED & FORBIDDEN IN TLS 1.3):
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Adversary taps fiber-optic cable and records 10 Terabytes of encrypted TLS wire traffic. β
β 1. Client generates Pre-Master Secret (PMS). β
β 2. Client encrypts PMS with Server's Long-Term Static RSA Public Key: C_pms = Enc(K_pub, PMS) β
β 3. Two years later: Adversary steals Server's Long-Term RSA Private Key (K_priv). β
β CATASTROPHE: Adversary decrypts C_pms for all recorded historical sessions! β
β ALL 10 TERABYTES OF RECORDED HISTORICAL SESSIONS ARE RETROACTIVELY EXPOSED IN PLAINTEXT! β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
2. EPHEMERAL ELLIPTIC CURVE DIFFIE-HELLMAN - ECDHE (MANDATORY IN TLS 1.3):
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Perfect Forward Secrecy (PFS) Guaranteed: β
β 1. Server generates ephemeral private scalar d_s (Used for exactly 1 session, then erased). β
β 2. Client generates ephemeral private scalar d_c (Used for exactly 1 session, then erased). β
β 3. Server signs its ephemeral ECDH public key using its long-term certificate (Authentication) β
β 4. Client and Server compute shared secret: S = d_s * Q_c = d_c * Q_s. β
β 5. Session keys derived via HKDF; ephemeral scalars d_s and d_c are securely wiped from RAM. β
β RESILIENCE: Even if an attacker steals the Server's long-term private signing key later, β
β the historical session keys CANNOT BE RECONSTRUCTED because the ephemeral keys no longer exist!β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
cryptography library. Implements high-speed Curve25519 key exchange (RFC 7748) and RSA-2048 encryption with Optimal Asymmetric Encryption Padding (OAEP) to protect against chosen-ciphertext and Bleichenbacher padding attacks.
from cryptography.hazmat.primitives.asymmetric import x25519, rsa, padding
from cryptography.hazmat.primitives import hashes
# ==============================================================================
# PIPELINE 1: HIGH-SPEED X25519 (CURVE25519) KEY EXCHANGE (TLS 1.3 STANDARD)
# ==============================================================================
def execute_x25519_key_agreement():
# Alice generates ephemeral private key
alice_private = x25519.X25519PrivateKey.generate()
alice_public = alice_private.public_key()
# Bob generates ephemeral private key
bob_private = x25519.X25519PrivateKey.generate()
bob_public = bob_private.public_key()
# Shared secret exchange
alice_shared = alice_private.exchange(bob_public)
bob_shared = bob_private.exchange(alice_public)
assert alice_shared == bob_shared, "X25519 key exchange divergence!"
return alice_shared
# ==============================================================================
# PIPELINE 2: SECURE RSA-OAEP ENCRYPTION (PREVENTS BLEICHENBACHER ATTACKS)
# ==============================================================================
def execute_rsa_oaep_pipeline(secret_data: bytes):
# Generate 2048-bit RSA key pair with standard F4 exponent 65537
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()
# Encrypt using OAEP with SHA-256 hashing and MGF1 mask generation function
ciphertext = public_key.encrypt(
secret_data,
padding.OAEP(
mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(),
label=None
)
)
# Decrypt
recovered_plaintext = private_key.decrypt(
ciphertext,
padding.OAEP(
mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(),
label=None
)
)
return ciphertext, recovered_plaintext
if __name__ == "__main__":
# Test X25519
shared_key_bytes = execute_x25519_key_agreement()
print(f"[*] X25519 Shared Key Derived : {shared_key_bytes.hex()[:32]}... (32 raw bytes)")
# Test RSA-OAEP
payload = b"EXAM_PAPER_CONFIDENTIAL_KEY_AES256"
ct_bytes, pt_bytes = execute_rsa_oaep_pipeline(payload)
print(f"[*] RSA-2048 OAEP Ciphertext : {ct_bytes.hex()[:48]}... (256 bytes output)")
print(f"[β] RSA-OAEP Recovered : {pt_bytes.decode('utf-8')}")
ASYMMETRIC KEY SIZE EQUIVALENCE & ASYMPTOTIC COMPLEXITY (NIST SP 800-57):
ββββββββββββββββββββ¬βββββββββββββββββββ¬βββββββββββββββββββ¬βββββββββββββββββββββββββββββββββββββββββ
β SYMMETRIC BITS β RSA / DH MODULUS β ECC CURVE SIZE β ASYMPTOTIC ATTACK COMPLEXITY β
ββββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β 80 bits (Legacy) β 1024 bits β 160 bits β GNFS Sub-exponential vs. Pollard-Rho β
β β (BROKEN) β (INSECURE) β Factored by distributed academic rigs β
ββββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β 112 bits β 2048 bits β 224 bits β Minimum allowed for legacy systems; β
β β β β Phased out of high-security standards β
ββββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β 128 bits β 3072 bits β 256 bits β Current baseline for commercial web: β
β (Standard Base) β (High CPU Cost) β (secp256r1/X25519β Equal strength; ECC key is 12x smaller β
ββββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β 192 bits β 7680 bits β 384 bits β High-security government / military β
β (NSA Suite B) β (Impractical) β (secp384r1) β RSA modulus too large for mobile/IoT β
ββββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββ€
β 256 bits β 15360 bits β 521 bits β Top Secret security posture β
β (Maximum Defense)β (Prohibitive) β (secp521r1) β RSA key generation requires seconds β
ββββββββββββββββββββ΄βββββββββββββββββββ΄βββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββββββ
ASYMPTOTIC ATTACK ALGORITHM FORMULATIONS:
1. RSA & Finite Field DH: General Number Field Sieve (GNFS)
Complexity: L_n [1/3, c] = exp( (c + o(1)) * (ln n)^(1/3) * (ln ln n)^(2/3) ) [Sub-exponential]
Growth is sub-exponential, so doubling the modulus provides far less than double the security!
2. Elliptic Curve Cryptography: Pollard's Rho Algorithm for ECDLP
Complexity: O( sqrt(n) ) = O( 2^(k/2) ) [Fully Exponential]
No general sub-exponential algorithm exists for standard prime curves. Every bit added directly
doubles the workload required to solve the ECDLP!
ASYMMETRIC CRYPTOGRAPHIC DEFECTS & ARCHITECTURAL REMEDIATION:
// ==============================================================================
// PITFALL 1: BLEICHENBACHER'S PADDING ORACLE ON PKCS#1 v1.5 (ROBOT ATTACK)
// DEFECT: When decrypting RSA ciphertext, the server responds differently depending
// on whether the decrypted plaintext begins with the valid block header "0x00 0x02":
// "HTTP 500: Invalid RSA Padding" vs "HTTP 400: Malformed Application Payload".
// ATTACK: An active adversary sends thousands of chosen ciphertexts, observing the
// oracle response to completely recover the plaintext without knowing private key d!
// FIX: Replace PKCS#1 v1.5 with RSA-OAEP (Optimal Asymmetric Encryption Padding)
// or use constant-time decryption routines that never report padding errors externally!
// ==============================================================================
// ==============================================================================
// PITFALL 2: SMALL PUBLIC EXPONENT e=3 BROADCAST ATTACK (HASTAD'S ATTACK)
// DEFECT: Developer chooses e=3 to speed up encryption calculations.
// ATTACK: If the exact same message M is encrypted and sent to 3 distinct recipients
// having moduli n1, n2, n3:
// C1 = M^3 mod n1, C2 = M^3 mod n2, C3 = M^3 mod n3
// By Chinese Remainder Theorem (CRT), an attacker computes C' = M^3 mod (n1*n2*n3).
// Since M < n_i, M^3 < n1*n2*n3, meaning C' is the exact integer cube over the real numbers!
// The attacker simply calculates the real-number cube root of C' to recover M instantly!
// FIX: Always use standard public exponent e = 65537 (2^16 + 1 = 0x10001)!
// ==============================================================================
// ==============================================================================
// PITFALL 3: INVALID CURVE ATTACK IN ECC (MISSING is_on_curve() CHECK)
// DEFECT: An ECDH implementation accepts an unvalidated public point Q = (x, y) from
// an external client and computes S = d * Q without checking if Q satisfies y^2 = x^3 + ax + b.
// ATTACK: The adversary crafts an invalid point lying on a weak curve with a small
// order. By analyzing the returned shared secret across multiple sessions, the adversary
// solves small discrete logs to reconstruct the server's private key d (Pohlig-Hellman)!
// FIX: Always validate that incoming public points lie on the specified curve and
// are not the point at infinity: assert curve.is_on_curve(peer_point)!
// ==============================================================================
ASYMMETRIC CRYPTOGRAPHY SPECIFICATION MATRIX:
βββββββββββββββββββββββββββ¬βββββββββββββββββββββββββββββββ¬βββββββββββββββββββ¬ββββββββββββββββββββββββββββββββ
β CRYPTOSYSTEM β MATHEMATICAL HARD PROBLEM β SECURE KEY SIZES β PRIMARY PROTOCOL APPLICATION β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β RSA-OAEP β Integer Factorization (IFP) β 2048 to 4096 bitsβ Secure key encapsulation, β
β (Encryption) β Given n = p*q, find factors β e = 65537 β S/MIME email, legacy TLS β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β RSA-PSS β Integer Factorization (IFP) β 2048 to 4096 bitsβ Modern digital signatures β
β (Digital Signatures) β Probabilistic Signature Sch. β e = 65537 β X.509 certs, code signing β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β Diffie-Hellman (DHE) β Discrete Logarithm (DLP) β 2048 to 4096 bitsβ Ephemeral session key β
β (Finite Field MODP) β Given g^a mod p, find a β RFC 3526 groups β agreement with Forward Secrecyβ
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β ECDH / ECDHE β Elliptic Curve Discrete Log β 256 to 384 bits β TLS 1.3 Key Exchange, β
β (Weierstrass Curves) β Given Q = d*G, find d β (P-256 / P-384) β SSHv2, IPsec VPN tunnels β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β X25519 (RFC 7748) β Montgomery Curve25519 ECDLP β 256 bits β High-performance modern web, β
β (Diffie-Hellman) β Curve: y^2 = x^3 + 486662x^2 β (Fastest ECDH) β WireGuard, Signal Protocol β
βββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββΌββββββββββββββββββββββββββββββββ€
β Ed25519 (RFC 8032) β Twisted Edwards Curve ECDLP β 256 bits β Modern high-security digital β
β (Digital Signatures) β Fast, side-channel immune β (Fastest Sign) β signatures, Git commit signingβ
βββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββ΄βββββββββββββββββββ΄ββββββββββββββββββββββββββββββββ€
β TOP 5 ASYMMETRIC CRYPTOGRAPHY AXIOMS: β
β 1. Asymmetric is for Key Exchange & Signatures: Never use asymmetric ciphers to encrypt bulk data; β
β use hybrid cryptography (asymmetric key encapsulation + symmetric AES-256-GCM data encryption). β
β 2. Mandate Perfect Forward Secrecy (PFS): Always use ephemeral key exchanges (ECDHE / X25519). β
β 3. Never use Textbook RSA: Always apply provably secure padding (RSA-OAEP for encryption, PSS for sig) β
β 4. Validate Elliptic Curve Points: Always check is_on_curve() to prevent invalid curve sub-group leak. β
β 5. Choose ECC over RSA for new designs: 256-bit ECC matches 3072-bit RSA with a fraction of the cost. β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ