Public Key Cryptography: RSA, ECC, Diffie-Hellman, Digital Signatures

TAKEAWAYS:

• Public key cryptography uses asymmetric keys (public/private pairs) to enable secure communication without pre-shared secrets.
• RSA and Elliptic Curve Cryptography (ECC) are widely used algorithms for encryption, digital signatures, and key exchange.
• Diffie-Hellman (DH) and its variants (ECDH) enable secure key exchange over insecure channels.
• Digital signatures provide non-repudiation and authentication using private keys and public key verification.
• Public key infrastructure (PKI) manages certificates to bind public keys to identities.
• Real-world applications include HTTPS (TLS/SSL), eSewa transactions, and Ncell digital signatures.

Core Concepts: Asymmetric Keys and Mathematical Foundations

Public key cryptography relies on mathematical problems that are easy to compute in one direction but hard to reverse. Unlike symmetric cryptography (Unit 4), it uses two keys:

• Public key: Shared openly (e.g., posted on a website or embedded in software).
• Private key: Kept secret by the owner.

Why Asymmetric Keys?

• No need to share secrets beforehand (unlike symmetric keys).
• Supports digital signatures (proof of identity and integrity).
• Scalability: One public key can encrypt messages for many recipients.

Mathematical Hard Problems

Public key cryptography is based on these one-way functions:

1. Integer Factorization (used in RSA):
   • Easy to multiply two large primes, but hard to factor their product.
   • Example: $n=p\times q$, where $p$ and $q$ are large primes.
2. Discrete Logarithm Problem (DLP) (used in Diffie-Hellman and ECC):
   • Given $g^x\mathrm{mod}p$, finding $x$ is computationally hard.
3. Elliptic Curve Discrete Logarithm Problem (ECDLP) (used in ECC):
   • Harder than DLP for the same security level, enabling smaller key sizes.

RSA: The Workhorse of Public Key Cryptography

RSA (Rivest-Shamir-Adleman) is the most widely used public key algorithm. It works as follows:

Key Generation

1. Choose two large primes $p$ and $q$ (e.g., 1024+ bits).
2. Compute $n=p\times q$ (modulus).
3. Compute Euler’s totient function $\varphi (n)=(p-1)(q-1)$.
4. Choose a public exponent $e$ (typically 65537) such that $1<e<\varphi (n)$ and $\gcd (e,\varphi (n))=1$.
5. Compute the private exponent $d$ as the modular inverse of $e\mathrm{mod}\varphi (n)$: $$d\equiv e^{-1}\mathrm{mod}\varphi (n)$$
6. The public key is $(e,n)$, and the private key is $(d,n)$.

Encryption and Decryption

• Encryption: $C=M^e\mathrm{mod}n$ (where $M$ is the plaintext message).
• Decryption: $M=C^d\mathrm{mod}n$.

Worked Example: RSA Encryption

Scenario: Ncell wants to securely send a message to a user. The user’s public key is $(e=5,n=323)$. The message $M=2$ (represented as an integer).

1. Encrypt $M$: $$C=2^5\mathrm{mod}323=32\mathrm{mod}323=32$$
2. Decrypt $C$ using the private key $(d=271,n=323)$: $$M=32^{271}\mathrm{mod}323$$ (In practice, this is computed using efficient algorithms like the square-and-multiply method.)

Real-World Tie-In: Ncell uses RSA to encrypt OTP (One-Time Password) tokens sent to users for authentication. The OTP is encrypted with Ncell’s public key, ensuring only the authorized server (with the private key) can decrypt it.

stateDiagram-v2
    [*] --> RSA_KeyGen: Start
    RSA_KeyGen --> ChoosePrimes: Pick p, q
    ChoosePrimes --> ComputeN: n = p × q
    ComputeN --> ComputePhi: φ(n) = (p-1)(q-1)
    ComputePhi --> ChooseE: Pick e (gcd(e, φ(n)) = 1)
    ChooseE --> ComputeD: d = e⁻¹ mod φ(n)
    ComputeD --> PublicKey: (e, n)
    ComputeD --> PrivateKey: (d, n)
    PublicKey --> [*]
    PrivateKey --> [*]

Figure 1: RSA Key Generation Process

Elliptic Curve Cryptography (ECC): Smaller Keys, Stronger Security

ECC provides equivalent security to RSA but with smaller key sizes, making it efficient for mobile and IoT devices.

Why ECC?

• 160-bit ECC ≈ 1024-bit RSA in security.
• Faster computations and lower power consumption (critical for Pathao’s ride-hailing app or eSewa’s mobile payments).
• Used in Bitcoin, Signal, and TLS 1.3.

Mathematical Foundation

ECC relies on elliptic curves over finite fields. An elliptic curve is defined by: $$y^2=x^3+ax+b(\text{mod }p)$$ where $4a^3+27b^2\ne 0\mathrm{mod}p$.

Key Generation in ECC

1. Choose a curve $E$ over a finite field ${\mathbb{F}}_p$.
2. Select a base point $G$ on $E$ with large prime order $n$.
3. Choose a private key $d$ (a random integer $1\le d<n$).
4. Compute the public key $Q=d\times G$ (scalar multiplication).

Encryption (ElGamal-like)

1. Encrypt a message $M$ with public key $Q$:
   • Choose a random $k$.
   • Compute $C_1=k\times G$.
   • Compute $C_2=M\oplus x(Q_k)$, where $Q_k=k\times Q$.
   • Ciphertext: $(C_1,C_2)$.

Digital Signatures (ECDSA)

ECC Digital Signature Algorithm (ECDSA) works similarly to RSA signatures but uses elliptic curve math.

classDiagram
    class EllipticCurve {
        +y² = x³ + ax + b (mod p)
        +Point: (x, y)
    }
    class PrivateKey {
        -d: integer
    }
    class PublicKey {
        -Q = d × G
    }
    EllipticCurve "1" --> "1" PrivateKey : Defines field
    PrivateKey --> PublicKey : Generates
    PublicKey --> EllipticCurve : Lies on curve

Figure 2: ECC Key Structure

Key Exchange: Diffie-Hellman and ECDH

Diffie-Hellman (DH) enables two parties to establish a shared secret over an insecure channel (e.g., the internet). It is the foundation of TLS/SSL (used in HTTPS) and VPNs.

How DH Works

1. Agree on a prime $p$ and generator $g$ (public parameters).
2. Alice picks a private key $a$, computes $A=g^a\mathrm{mod}p$, and sends $A$ to Bob.
3. Bob picks a private key $b$, computes $B=g^b\mathrm{mod}p$, and sends $B$ to Alice.
4. Both compute the shared secret:
   • Alice: $s=B^a\mathrm{mod}p=(g^b{)}^a\mathrm{mod}p=g^{ab}\mathrm{mod}p$.
   • Bob: $s=A^b\mathrm{mod}p=(g^a{)}^b\mathrm{mod}p=g^{ab}\mathrm{mod}p$.

Worked Example: DH Key Exchange

Scenario: Daraz wants to securely exchange a session key with a customer over an untrusted network.

1. Public parameters: $p=23$, $g=5$.
2. Alice (Daraz) picks $a=6$, computes $A=5^6\mathrm{mod}23=8$.
3. Bob (Customer) picks $b=15$, computes $B=5^{15}\mathrm{mod}23=19$.
4. Shared secret:
   • Alice: $s=19^6\mathrm{mod}23=2$.
   • Bob: $s=8^{15}\mathrm{mod}23=2$.

Real-World Tie-In: When you log into eSewa via HTTPS, your browser and eSewa’s server perform an ECDH (Elliptic Curve Diffie-Hellman) handshake to establish a symmetric session key for encrypting your transaction data. This prevents eavesdroppers from reading your payment details.

sequenceDiagram
    participant Alice
    participant Bob
    participant Eavesdropper
    Alice->>Bob: p, g (public)
    Alice->>Bob: A = g^a mod p
    Bob->>Alice: B = g^b mod p
    Alice->>Alice: s = B^a mod p
    Bob->>Bob: s = A^b mod p
    Note over Alice,Bob: Shared secret s = g^(ab) mod p
    Eavesdropper--)Alice: Sees A, B, p, g
    Eavesdropper--)Bob: Cannot compute s (DLP hard)

Figure 3: Diffie-Hellman Key Exchange

Digital Signatures: Non-Repudiation and Authentication

Digital signatures use public key cryptography to verify the authenticity and integrity of a message. They are used in:

• eSewa receipts (proving you made a payment).
• Ncell SIM registration (proving your identity).
• NEPSE stock trades (preventing fraud).

How Digital Signatures Work (RSA Example)

1. Signing:
   • Hash the message: $h=\text{Hash}(M)$.
   • Encrypt the hash with the private key: $\sigma =h^d\mathrm{mod}n$.
   • Signature: $(M,\sigma )$.
2. Verification:
   • Decrypt the signature with the public key: $h^{\prime }={\sigma }^e\mathrm{mod}n$.
   • Hash the received message: $h^{\prime \prime }=\text{Hash}(M)$.
   • If $h^{\prime }=h^{\prime \prime }$, the signature is valid.

Worked Example: Signing a NEPSE Trade Order

Scenario: You sign a stock trade order for NEPSE using your private key.

1. Message $M=$ "Buy 100 shares of NEPSE at 1000 NPR".
2. Hash $M$: $h=\text{SHA-256}(M)$.
3. Sign with private key $(d,n)$: $\sigma =h^d\mathrm{mod}n$.
4. Send $(M,\sigma )$ to NEPSE.
5. NEPSE verifies using your public key $(e,n)$:
   • Compute $h^{\prime }={\sigma }^e\mathrm{mod}n$.
   • Check if $h^{\prime }=\text{SHA-256}(M)$.

Real-World Tie-In: When you submit a Khalti payment request, the merchant’s server verifies your digital signature to ensure the request hasn’t been tampered with and that it truly came from you.

sequenceDiagram
    participant Sender
    participant Receiver
    Sender->>Sender: M = "Trade Order"
    Sender->>Sender: h = Hash(M)
    Sender->>Sender: σ = h^d mod n (sign)
    Sender->>Receiver: (M, σ)
    Receiver->>Receiver: h' = σ^e mod n
    Receiver->>Receiver: h'' = Hash(M)
    alt h' == h'' then
        Receiver->>Receiver: Valid signature!
    else
        Receiver->>Receiver: Invalid or tampered!
    end

Figure 4: Digital Signature Process

Public Key Infrastructure (PKI): Managing Certificates

PKI is the system that binds public keys to identities using digital certificates. It includes:

• Certificate Authorities (CAs): Trusted entities that issue certificates (e.g., GlobalSign, DigiCert).
• Certificate Revocation Lists (CRL): Lists of invalidated certificates.
• Online Certificate Status Protocol (OCSP): Real-time certificate validation.

How PKI Works

1. Certificate Request: A user generates a key pair and sends a Certificate Signing Request (CSR) to a CA.
2. Certificate Issuance: The CA verifies the user’s identity and signs the certificate with its private key.
3. Certificate Distribution: The CA issues the certificate to the user.
4. Validation: Recipients verify the certificate using the CA’s public key.

Example: HTTPS Certificate for Daraz

When you visit Daraz.com, your browser:

1. Checks if Daraz’s certificate is valid (not expired, not revoked).
2. Verifies the certificate’s signature using the CA’s public key (e.g., Let’s Encrypt).
3. Establishes a secure TLS connection using the public key.

erDiagram
    CERTIFICATE ||--o{ USER : "Issued to"
    CERTIFICATE ||--|| CA : "Issued by"
    CA }|--|| TRUST_STORE : "Public key in"
    USER ||--|| PUBLIC_KEY : "Owns"
    USER ||--|| PRIVATE_KEY : "Owns"
    CERTIFICATE {
        string serialNumber
        string subject
        string issuer
        date validityPeriod
        string publicKey
        string signature
    }

Figure 5: PKI Entity-Relationship Diagram

In the Real World

Public key cryptography is everywhere in Nepal’s digital economy. Here’s how it’s used:

1. eSewa and Khalti Payments:

   • What it uses: RSA for encrypting payment details and ECDSA for digital signatures.
   • How it works: When you pay via eSewa, your device generates an ephemeral ECDH key pair to establish a secure session with eSewa’s server. Your payment request is signed with your private key, and eSewa verifies it using your public key (stored in their PKI).

2. Ncell Digital Identity:

   • What it uses: X.509 certificates (PKI) for authenticating SIM registrations.
   • How it works: When you register a SIM, Ncell’s server issues you a digital certificate binding your identity to a public key. This certificate is used to sign all subsequent transactions (e.g., mobile money transfers).

3. NEPSE Secure Trading:

   • What it uses: RSA and ECC for encrypting trade orders and digital signatures.
   • How it works: Before you can trade stocks, you must register with NEPSE using a digital signature. Your trade orders are signed with your private key, and NEPSE verifies them using your public key to prevent fraud.

4. Pathao Driver-Verification:

   • What it uses: TLS (which relies on DH/ECDH for key exchange and RSA/ECC for signatures).
   • How it works: When a Pathao driver’s app connects to the server, they perform an ECDH handshake to establish a secure channel. The app’s identity is verified using a certificate issued by a CA.

5. Bank Internet Banking (e.g., NMB, Global IME):

   • What it uses: PKI for user authentication and TLS for secure communication.
   • How it works: When you log into your bank’s website, your browser presents a client certificate (stored on your token or smartphone) to prove your identity. The bank’s server verifies this certificate before allowing access.

Advantages and Disadvantages of Public Key Cryptography

Common Attacks on Public Key Cryptography

Understanding attacks helps in securing implementations:

1. Man-in-the-Middle (MITM) Attacks:

   • Eavesdropper intercepts key exchange (e.g., DH) and impersonates both parties.
   • Mitigation: Use authenticated DH (e.g., Signal Protocol) or certificates.

2. Brute Force Attacks:

   • Trying all possible private keys (e.g., guessing $d$ in RSA).
   • Mitigation: Use sufficiently large keys (e.g., 2048-bit RSA or 256-bit ECC).

3. Side-Channel Attacks:

   • Exploiting implementation flaws (e.g., timing attacks on RSA decryption).
   • Mitigation: Use constant-time algorithms and blinding techniques.

4. Quantum Attacks:

   • Shor’s algorithm can break RSA and ECDH in polynomial time on a quantum computer.
   • Mitigation: Research post-quantum cryptography (e.g., lattice-based schemes).

Exam Tip

This unit is heavily tested in TU exams, especially on:

1. RSA/ECC Math: Be able to derive keys, encrypt/decrypt small messages, and explain the math behind them.

   • Example Question: "Given $p=5,q=11,e=3$, compute the private key $d$."
   • Solution: Compute $n=55$, $\varphi (n)=40$, then find $d$ such that $3d\equiv 1\mathrm{mod}40$. Use the Extended Euclidean Algorithm.

2. Diffie-Hellman Workings: Trace the key exchange step-by-step and compute shared secrets.

   • Example Question: "Alice and Bob use $p=23,g=5$. Alice picks $a=4$, Bob picks $b=3$. What is their shared secret?"
   • Solution: $A=5^4\mathrm{mod}23=10$, $B=5^3\mathrm{mod}23=10$. Shared secret $s=10^4\mathrm{mod}23=10^3\mathrm{mod}23=10$.

3. Digital Signatures: Explain how hashing + private key signing works, and how verification uses the public key.

   • Example Question: "How does ECDSA prevent repudiation?"
   • Answer: Only the private key holder can create a valid signature. The public key can verify it, proving the signer’s identity.

4. PKI and Certificates: Know the roles of CAs, CSRs, and how certificates are validated.

   • Example Question: "What is the purpose of a Certificate Revocation List (CRL)?"
   • Answer: To list certificates that should no longer be trusted (e.g., compromised or expired keys).

5. Real-World Applications: Relate concepts to eSewa, Ncell, NEPSE, or Pathao.

   • Example Question: "How does Khalti use public key cryptography to secure payments?"
   • Answer: Khalti uses TLS (with ECDH for key exchange and ECDSA for signatures) to encrypt transactions and authenticate users.

Final Checklist for Full Marks

• Explain the mathematical hardness behind RSA and ECC.
• Derive RSA keys from primes and compute encryption/decryption.
• Trace a Diffie-Hellman key exchange and compute shared secrets.
• Describe digital signatures and their role in non-repudiation.
• Draw a PKI diagram showing CAs, users, and certificates.
• Link concepts to Nepali examples (eSewa, Ncell, NEPSE, Pathao).
• Discuss attacks (MITM, brute force, quantum) and mitigations.