Asymmetric Encryption & Key Exchange

calendarDec 12, 2024 · 5 min read · cryptography rsa ecc public-key crypto-knowhow mathematics  ·
Share on: linkedincopy

Asymmetric (public-key) cryptography with mathematical foundations, including RSA, ECC, and key exchange protocols.

Mathematical Foundation

Public-Key Cryptosystem

A public-key cryptosystem consists of:

$$ \begin{aligned} (pk, sk) &\leftarrow KeyGen() \ C &= Encrypt(pk, M) \ M &= Decrypt(sk, C) \end{aligned} $$

Where:

  • $pk$: Public key (can be shared)
  • $sk$: Private/secret key (must be kept secret)
  • $M$: Message
  • $C$: Ciphertext

Property: $Decrypt(sk, Encrypt(pk, M)) = M$

RSA (Rivest-Shamir-Adleman)

Key Generation

  1. Choose two large primes $p$ and $q$ (e.g., 1024 bits each)
  2. Compute $n = p \cdot q$ (modulus)
  3. Compute $\phi(n) = (p-1)(q-1)$ (Euler's totient)
  4. Choose $e$ such that $\gcd(e, \phi(n)) = 1$ (commonly $e = 65537$)
  5. Compute $d = e^{-1} \mod \phi(n)$ (private exponent)

$$ \begin{aligned} \text{Public key:} \quad & (n, e) \ \text{Private key:} \quad & (n, d) \end{aligned} $$

Encryption

$$ C = M^e \mod n $$

Decryption

$$ M = C^d \mod n $$

Why It Works

By Euler's theorem:

$$ M^{\phi(n)} \equiv 1 \pmod{n} \quad \text{if } \gcd(M, n) = 1 $$

Since $e \cdot d \equiv 1 \pmod{\phi(n)}$, we have $e \cdot d = k \cdot \phi(n) + 1$:

$$ \begin{aligned} C^d &= (M^e)^d = M^{ed} \ &= M^{k \cdot \phi(n) + 1} \ &= M \cdot (M^{\phi(n)})^k \ &\equiv M \cdot 1^k \equiv M \pmod{n} \end{aligned} $$

Security

Hard problem: Integer factorization

Given $n = p \cdot q$, finding $p$ and $q$ is computationally hard.

Best known algorithm: General Number Field Sieve (GNFS)

Complexity: $O(e^{(\ln n)^{1/3} (\ln \ln n)^{2/3}})$

Key sizes:

  • 2048 bits: ~112-bit security
  • 3072 bits: ~128-bit security
  • 4096 bits: ~140-bit security

Elliptic Curve Cryptography (ECC)

Elliptic Curve Definition

Curve over $\mathbb{F}_p$ (prime field):

$$ y^2 = x^3 + ax + b \pmod{p} $$

Example: secp256k1 (Bitcoin):

$$ y^2 = x^3 + 7 \pmod{p} $$

Where $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$

Point Addition

For points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$:

If $P \neq Q$ (point addition):

$$ \begin{aligned} \lambda &= \frac{y_2 - y_1}{x_2 - x_1} \mod p \ x_3 &= \lambda^2 - x_1 - x_2 \mod p \ y_3 &= \lambda(x_1 - x_3) - y_1 \mod p \end{aligned} $$

If $P = Q$ (point doubling):

$$ \begin{aligned} \lambda &= \frac{3x_1^2 + a}{2y_1} \mod p \ x_3 &= \lambda^2 - 2x_1 \mod p \ y_3 &= \lambda(x_1 - x_3) - y_1 \mod p \end{aligned} $$

Scalar Multiplication

$$ Q = k \cdot P = \underbrace{P + P + \cdots + P}_{k \text{ times}} $$

Computed efficiently using double-and-add algorithm: $O(\log k)$

ECDH (Elliptic Curve Diffie-Hellman)

  1. Agree on curve parameters $(p, a, b, G, n)$
  2. Alice: $a \leftarrow random$, $A = a \cdot G$
  3. Bob: $b \leftarrow random$, $B = b \cdot G$
  4. Alice computes: $S = a \cdot B = a \cdot (b \cdot G)$
  5. Bob computes: $S = b \cdot A = b \cdot (a \cdot G)$

$$ S = a \cdot b \cdot G \quad \text{(shared secret)} $$

Security

Hard problem: Elliptic Curve Discrete Logarithm Problem (ECDLP)

Given $Q = k \cdot P$, finding $k$ is computationally hard.

Best known algorithm: Pollard's rho

Complexity: $O(\sqrt{n})$ where $n$ is the order of the curve

Key sizes (equivalent security):

  • 256-bit ECC ≈ 3072-bit RSA ≈ 128-bit security
  • 384-bit ECC ≈ 7680-bit RSA ≈ 192-bit security

Advantage: Much smaller keys for same security!

Modern Curves

Curve25519 (X25519 for key exchange)

Montgomery curve:

$$ y^2 = x^3 + 486662x^2 + x \pmod{2^{255} - 19} $$

Advantages:

  • Fast (optimized for modern CPUs)
  • Side-channel resistant
  • Safe by design (no weak points)

Ed25519 (EdDSA for signatures)

Edwards curve (birationally equivalent to Curve25519):

$$ -x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2 \pmod{2^{255} - 19} $$

Python Implementation

RSA

 1from cryptography.hazmat.primitives.asymmetric import rsa, padding
 2from cryptography.hazmat.primitives import hashes
 3
 4# Generate key pair
 5private_key = rsa.generate_private_key(
 6    public_exponent=65537,
 7    key_size=2048
 8)
 9public_key = private_key.public_key()
10
11# Encrypt
12message = b"Secret message"
13ciphertext = public_key.encrypt(
14    message,
15    padding.OAEP(
16        mgf=padding.MGF1(algorithm=hashes.SHA256()),
17        algorithm=hashes.SHA256(),
18        label=None
19    )
20)
21
22# Decrypt
23plaintext = private_key.decrypt(
24    ciphertext,
25    padding.OAEP(
26        mgf=padding.MGF1(algorithm=hashes.SHA256()),
27        algorithm=hashes.SHA256(),
28        label=None
29    )
30)

X25519 (Key Exchange)

 1from cryptography.hazmat.primitives.asymmetric import x25519
 2
 3# Alice
 4alice_private = x25519.X25519PrivateKey.generate()
 5alice_public = alice_private.public_key()
 6
 7# Bob
 8bob_private = x25519.X25519PrivateKey.generate()
 9bob_public = bob_private.public_key()
10
11# Derive shared secret
12alice_shared = alice_private.exchange(bob_public)
13bob_shared = bob_private.exchange(alice_public)
14
15assert alice_shared == bob_shared  # Same secret!
16
17# Derive encryption key from shared secret
18from cryptography.hazmat.primitives.kdf.hkdf import HKDF
19from cryptography.hazmat.primitives import hashes
20
21key = HKDF(
22    algorithm=hashes.SHA256(),
23    length=32,
24    salt=None,
25    info=b'handshake data',
26).derive(alice_shared)

ECDH with secp256k1

 1from cryptography.hazmat.primitives.asymmetric import ec
 2
 3# Generate keys
 4private_key = ec.generate_private_key(ec.SECP256K1())
 5public_key = private_key.public_key()
 6
 7# Peer's public key
 8peer_public_key = ec.generate_private_key(ec.SECP256K1()).public_key()
 9
10# Derive shared secret
11shared_secret = private_key.exchange(ec.ECDH(), peer_public_key)

Hybrid Encryption

Problem: RSA/ECC are slow for large data

Solution: Combine symmetric + asymmetric

 1from cryptography.hazmat.primitives.ciphers.aead import AESGCM
 2import os
 3
 4def hybrid_encrypt(plaintext, recipient_public_key):
 5    # 1. Generate random symmetric key
 6    aes_key = AESGCM.generate_key(bit_length=256)
 7    
 8    # 2. Encrypt data with AES
 9    aesgcm = AESGCM(aes_key)
10    nonce = os.urandom(12)
11    ciphertext = aesgcm.encrypt(nonce, plaintext, None)
12    
13    # 3. Encrypt AES key with RSA
14    encrypted_key = recipient_public_key.encrypt(
15        aes_key,
16        padding.OAEP(
17            mgf=padding.MGF1(algorithm=hashes.SHA256()),
18            algorithm=hashes.SHA256(),
19            label=None
20        )
21    )
22    
23    return encrypted_key, nonce, ciphertext
24
25def hybrid_decrypt(encrypted_key, nonce, ciphertext, private_key):
26    # 1. Decrypt AES key with RSA
27    aes_key = private_key.decrypt(
28        encrypted_key,
29        padding.OAEP(
30            mgf=padding.MGF1(algorithm=hashes.SHA256()),
31            algorithm=hashes.SHA256(),
32            label=None
33        )
34    )
35    
36    # 2. Decrypt data with AES
37    aesgcm = AESGCM(aes_key)
38    plaintext = aesgcm.decrypt(nonce, ciphertext, None)
39    
40    return plaintext

Comparison

AlgorithmKey SizeSpeedSecurity BasisUse Case
RSA-20482048 bitsSlowFactorizationLegacy, TLS
RSA-40964096 bitsVery slowFactorizationHigh security
ECC-256256 bitsFastECDLPModern, mobile
X25519256 bitsVery fastECDLPKey exchange
Ed25519256 bitsVery fastECDLPSignatures

Related Snippets