1426  Asymmetric Encryption and Public Key Cryptography

1426.1 Learning Objectives

By the end of this chapter, you will be able to:

  • Understand Public Key Cryptography: Explain how two related keys enable secure communication without pre-shared secrets
  • Apply RSA Encryption: Understand the mathematical foundation and proper use of RSA for key exchange and signatures
  • Implement Diffie-Hellman: Use DH key exchange to establish shared secrets over insecure channels
  • Create Digital Signatures: Sign and verify messages to ensure authenticity and non-repudiation
TipIn Plain English

Asymmetric encryption uses two mathematically related keys - a public key and a private key. Think of a mailbox: anyone can drop mail through the slot (public key = encrypt), but only you have the key to open it (private key = decrypt).

Why it matters for IoT: Asymmetric encryption solves the “key distribution problem” that plagues symmetric encryption. When you set up a new smart device, it can use the server’s public key to securely establish a connection - no need to pre-share secrets during manufacturing.

1426.2 How Asymmetric Encryption Works

Asymmetric encryption (public-key cryptography) uses two related keys: a public key for encryption and a private key for decryption.

%% fig-alt: "Asymmetric encryption flow showing sender encrypting with recipient's public key, and recipient decrypting with private key"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22'}}}%%
flowchart TB
    subgraph Alice["Alice (Sender)"]
        AlicePriv[Alice Private Key<br/>Keep Secret]
        AlicePub[Alice Public Key<br/>Share Freely]
        Message[Plaintext Message]
        Sign[Digital Signature]
    end

    subgraph Bob["Bob (Receiver)"]
        BobPriv[Bob Private Key<br/>Keep Secret]
        BobPub[Bob Public Key<br/>Share Freely]
        Decrypt[Decrypt Message]
        Verify[Verify Signature]
    end

    subgraph Operations["Cryptographic Operations"]
        Enc[Encrypt with<br/>Bob's Public Key]
        SignOp[Sign with<br/>Alice's Private Key]
    end

    Message --> Enc
    BobPub -.->|Public| Enc
    Enc --> Decrypt
    BobPriv -.->|Private| Decrypt

    Message --> SignOp
    AlicePriv -.->|Private| SignOp
    SignOp --> Sign
    Sign --> Verify
    AlicePub -.->|Public| Verify

    KeyDist[Solves Key<br/>Distribution Problem]
    BobPub -.-> KeyDist

    style Alice fill:#2C3E50,stroke:#16A085,stroke-width:2px,color:#fff
    style Bob fill:#2C3E50,stroke:#16A085,stroke-width:2px,color:#fff
    style Operations fill:#E67E22,stroke:#2C3E50,stroke-width:2px,color:#fff
    style KeyDist fill:#D4EDDA,stroke:#28A745,stroke-width:2px

Figure 1426.1: Asymmetric encryption: encrypt with public key, decrypt with private key

Mathematical Relationship:

  • Keys are mathematically related but computationally infeasible to derive one from the other
  • Encryption with public key -> decryption with private key
  • Signing with private key -> verification with public key

Advantages:

  • Solves key distribution problem
  • No secure channel needed for public key
  • Digital signatures enable authentication
  • Non-repudiation support

Disadvantages:

  • 100-1000x slower than symmetric encryption
  • Not suitable for bulk data
  • Public keys need authentication (certificates)
  • Key loss means permanent data loss

1426.3 RSA Cryptosystem

History: Developed by Rivest, Shamir, and Adleman (1977)

RSA relies on a mathematical “one-way door” - operations that are easy in one direction but nearly impossible to reverse:

Direction Difficulty Example
Forward (easy) Milliseconds Multiply 2 large primes: 61 x 53 = 3,233
Backward (hard) Years Factor 3,233 into primes: ? x ? = 3,233

For small numbers, factoring is trivial. But RSA uses 617-digit numbers (2048 bits). Factoring those would take all the world’s computers billions of years.

The Elegant Trick:

  1. You know a secret shortcut - If you chose the original primes (p and q), you can easily compute the private key
  2. Attackers see only the product - They would need to factor the huge number to find your primes
  3. Math guarantees it works - Euler’s theorem ensures that encrypting then decrypting returns the original message

The Catch: Quantum Computers

Future quantum computers could factor large numbers quickly using Shor’s algorithm. That’s why post-quantum cryptography is being developed. For now, RSA-2048+ remains secure against classical computers.

1426.3.1 RSA Key Generation

  1. Choose two large prime numbers \(p\) and \(q\)
  2. Compute \(n = p \times q\) (modulus)
  3. Compute \(\phi(n) = (p-1)(q-1)\) (Euler’s totient)
  4. Choose public exponent \(e\) (typically 65537)
  5. Compute private exponent \(d\) such that \(ed \equiv 1 \pmod{\phi(n)}\)

Public key: \((n, e)\) Private key: \((n, d)\)

Encryption: \(c = m^e \mod n\) Decryption: \(m = c^d \mod n\)

1426.3.2 RSA Key Size Recommendations

Key Size Security Level Use Case
RSA-2048 ~112-bit Minimum acceptable, sufficient until ~2030
RSA-3072 ~128-bit Recommended for new deployments (10+ year lifespan)
RSA-4096 ~152-bit Maximum security, rarely needed (very slow)
WarningNever Use RSA-1024

RSA-1024 has been deprecated since 2010 and is considered broken. Academic attacks have demonstrated factorization of 768-bit RSA. Always use RSA-2048 or higher.

1426.4 Digital Signatures

Digital signatures prove that a message came from a specific sender and hasn’t been modified.

%% fig-alt: "Digital signature process showing signing with private key and verification with public key"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22'}}}%%
sequenceDiagram
    participant Sender as Manufacturer
    participant Device as IoT Device

    Note over Sender: Has: Private Key (secret)<br/>Public Key (embedded in devices)

    Sender->>Sender: 1. Hash firmware: SHA-256(firmware)
    Sender->>Sender: 2. Sign hash with Private Key
    Sender->>Device: 3. Send: Firmware + Signature

    Device->>Device: 4. Hash received firmware
    Device->>Device: 5. Decrypt signature with Public Key
    Device->>Device: 6. Compare hashes

    alt Hashes Match
        Device->>Device: VERIFIED - Install firmware
    else Hashes Differ
        Device->>Device: REJECTED - Possible tampering
    end

Figure 1426.2: Digital signature verification for firmware updates

Signature Process:

  1. Hash the data - Create a fixed-size fingerprint with SHA-256
  2. Encrypt the hash - Use private key to create signature
  3. Send data + signature - Recipient receives both
  4. Verify - Decrypt signature with public key, compare to computed hash

IoT Use Cases:

  • Firmware update verification
  • Command authentication
  • Device attestation
  • Non-repudiation for transactions

1426.5 Diffie-Hellman Key Exchange

Allows two parties to establish a shared secret over an insecure channel without transmitting the secret itself.

%% fig-alt: "Diffie-Hellman key exchange showing Alice and Bob computing shared secret without transmitting it"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22'}}}%%
sequenceDiagram
    participant Alice as Alice
    participant Public as Public Channel<br/>(Insecure)
    participant Bob as Bob

    Note over Alice,Bob: Public: prime p, generator g

    Note over Alice: Choose secret a
    Alice->>Alice: Compute A = g^a mod p

    Note over Bob: Choose secret b
    Bob->>Bob: Compute B = g^b mod p

    Alice->>Public: Send A (public)
    Public->>Bob: Forward A

    Bob->>Public: Send B (public)
    Public->>Alice: Forward B

    Note over Alice: Compute s = B^a mod p
    Note over Bob: Compute s = A^b mod p

    Note over Alice,Bob: Both have same secret:<br/>s = g^ab mod p

    Note over Public: Eavesdropper sees:<br/>p, g, A, B<br/>Cannot compute s!

Figure 1426.3: Diffie-Hellman: establishing shared secrets over insecure channels

Mathematical Foundation:

Given public \(p\) (prime) and \(g\) (generator):

  1. Alice chooses secret \(a\), computes \(A = g^a \mod p\)
  2. Bob chooses secret \(b\), computes \(B = g^b \mod p\)
  3. They exchange \(A\) and \(B\) publicly
  4. Alice computes \(s = B^a \mod p = g^{ab} \mod p\)
  5. Bob computes \(s = A^b \mod p = g^{ab} \mod p\)

Both arrive at the same shared secret \(s = g^{ab} \mod p\).

Security: Even seeing p, g, A, and B, an attacker cannot compute s without solving the discrete logarithm problem (computationally infeasible for large primes).

1426.6 Algorithm Comparison

%% fig-alt: "Comparison of RSA, ECC, and Diffie-Hellman asymmetric algorithms"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22'}}}%%
graph TB
    subgraph Algorithms["Asymmetric Algorithms"]
        RSA[RSA<br/>Rivest-Shamir-Adleman]
        ECC[ECC<br/>Elliptic Curve Crypto]
        DH[Diffie-Hellman<br/>Key Exchange]
    end

    subgraph RSAProps["RSA Properties"]
        RSAMath[Prime Factorization<br/>Hard Problem]
        RSAKey[2048-4096 bit keys]
        RSAUse[Key exchange<br/>Digital signatures]
    end

    subgraph ECCProps["ECC Properties"]
        ECCMath[Elliptic Curve<br/>Discrete Log]
        ECCKey[256-384 bit keys<br/>10x smaller than RSA]
        ECCUse[IoT devices<br/>Low power]
    end

    subgraph DHProps["DH Properties"]
        DHMath[Discrete Logarithm<br/>Hard Problem]
        DHKey[Shared secret<br/>without transmission]
        DHUse[TLS handshake<br/>Perfect forward secrecy]
    end

    RSA --> RSAProps
    ECC --> ECCProps
    DH --> DHProps

    style RSA fill:#E67E22,stroke:#2C3E50,stroke-width:2px,color:#fff
    style ECC fill:#16A085,stroke:#2C3E50,stroke-width:2px,color:#fff
    style DH fill:#2C3E50,stroke:#16A085,stroke-width:2px,color:#fff

Figure 1426.4: Asymmetric algorithm comparison
Algorithm Key Size for 128-bit Security Speed Best For
RSA 3072 bits Slow Legacy systems, wide compatibility
ECDH 256 bits Fast IoT key exchange
ECDSA 256 bits Fast IoT digital signatures
Ed25519 256 bits Very Fast Modern signatures

1426.7 Knowledge Check

An IoT manufacturer wants to push signed firmware updates to 100,000 deployed devices. Which key should they use to SIGN the firmware, and which key should devices use to VERIFY it?

Options:

    1. Sign with public key, verify with private key
    1. Sign with manufacturer’s private key, verify with manufacturer’s public key embedded in devices
    1. Use symmetric encryption - same key for sign and verify
    1. Sign with each device’s private key, verify with device’s public key

Correct: B

The manufacturer signs firmware with their private key (kept secret). Each device has the manufacturer’s public key pre-installed and uses it to verify signatures. Since only the manufacturer has the private key, only they can create valid signatures. This is how secure boot and firmware verification work.

During a Diffie-Hellman key exchange, an attacker intercepts the public values A and B exchanged between Alice and Bob over an insecure channel. Can the attacker compute the shared secret?

Options:

    1. Yes, because A and B together reveal the shared secret
    1. No, computing the shared secret from A and B requires solving the discrete logarithm problem
    1. Yes, if they also know the public parameters p and g
    1. No, but only if the channel uses TLS encryption

Correct: B

This is the mathematical foundation of Diffie-Hellman security. The attacker sees p, g, A (g^a mod p), and B (g^b mod p), but computing a or b from these values is the discrete logarithm problem - computationally infeasible for sufficiently large primes. The parameters p and g are intentionally public (published in RFC 3526). Only Alice and Bob can compute s = g^ab mod p.

1426.8 Hybrid Encryption: Best of Both Worlds

In practice, IoT systems use both symmetric and asymmetric encryption together:

%% fig-alt: "Hybrid encryption combining asymmetric key exchange with symmetric bulk encryption"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22'}}}%%
flowchart LR
    subgraph Phase1["Phase 1: Key Exchange"]
        direction TB
        DH[ECDH/RSA]
        SessionKey[Derive AES<br/>Session Key]
        DH --> SessionKey
    end

    subgraph Phase2["Phase 2: Bulk Encryption"]
        direction TB
        AES[AES-128-GCM]
        Data[Sensor Data<br/>Encrypted Fast]
        AES --> Data
    end

    Phase1 -->|Session Key| Phase2

    style Phase1 fill:#E67E22,stroke:#2C3E50,stroke-width:2px,color:#fff
    style Phase2 fill:#16A085,stroke:#2C3E50,stroke-width:2px,color:#fff

Figure 1426.5: Hybrid encryption: asymmetric for key exchange, symmetric for data

Why Hybrid?

  1. Asymmetric (RSA/ECDH): Securely exchange session keys (slow, but only once)
  2. Symmetric (AES): Encrypt all data with session key (fast, continuous)

This is exactly how TLS/HTTPS works - and why it’s the standard for IoT security.

1426.9 Summary

  • Asymmetric encryption uses two keys: public (encrypt) and private (decrypt)
  • RSA is based on the difficulty of factoring large prime products - use RSA-2048 minimum
  • Diffie-Hellman enables shared secret establishment over insecure channels
  • Digital signatures prove authenticity: sign with private, verify with public
  • ECC provides equivalent security to RSA with 10x smaller keys (ideal for IoT)
  • Hybrid encryption combines both: asymmetric for key exchange, symmetric for bulk data

1426.10 What’s Next

Continue to Elliptic Curve Cryptography (ECC) to learn why ECC is the preferred choice for resource-constrained IoT devices, offering RSA-equivalent security with dramatically smaller keys and faster operations.