Asymmetric Keys, PKI, RSA, Diffie-Hellman & Digital Signatures

TAKEAWAYS:

• Asymmetric ≠ Symmetric: Asymmetric uses two keys (public/private) while symmetric uses one shared key—RSA and ECC rely on hard math problems (factoring, DLP) to secure this.
• RSA’s Workflow: Encrypt with public key $e$, decrypt with private key $d$ (where $e\cdot d\equiv 1\mathrm{mod}\varphi (n)$), using modular exponentiation $M^e\mathrm{mod}n$.
• Diffie-Hellman’s Magic: Two parties compute a shared secret $s=g^x\mathrm{mod}p$ and $g^y\mathrm{mod}p$ without ever transmitting $x$ or $y$.
• PKI’s Role: Certificates (signed by CAs like GlobalSign) bind identities to public keys, enabling secure web (HTTPS) and email (S/MIME) via chains of trust.
• Digital Signatures: Sign with private key, verify with public key—like a tamper-proof receipt for messages (used in NEPSE’s trade confirmations).
• Trade-offs: Asymmetric is slower but scalable; symmetric is fast but needs key distribution—hybrid systems (TLS) combine both.

1. Asymmetric Cryptography: The Core Idea

Asymmetric cryptography solves symmetric key’s biggest flaw: how to securely share the key. Instead of one key, it uses two mathematically linked keys:

• Public Key (PK): Shared openly (e.g., posted on a website).
• Private Key (SK): Kept secret (e.g., stored on your device).

How it works:

1. Alice encrypts a message with Bob’s public key.
2. Bob decrypts it with his private key (only he has it).
3. Or: Alice signs a message with her private key; Bob verifies it with her public key.

Why it’s revolutionary:

• No pre-shared secret needed.
• Enables non-repudiation (you can’t deny sending a signed message).
• Used in SSL/TLS (HTTPS), PGP email, and blockchain.

stateDiagram-v2
    [*] --> Alice: Generates PK/SK pair
    Alice --> Bob: Sends PK to Bob
    Bob --> Alice: Encrypts message M with Alice's PK
    Alice --> Bob: Decrypts M with her SK
    [*]

2. RSA: The Workhorse of Asymmetric Crypto

RSA (Rivest-Shamir-Adleman) is the most widely used asymmetric algorithm, securing eSewa payments, Ncell’s SIM cards, and NEPSE’s trading systems.

How RSA Works

1. Key Generation:

   • Choose two large primes $p$ and $q$ (e.g., $p=61$, $q=53$).
   • Compute $n=p\times q$ (modulus) and $\varphi (n)=(p-1)(q-1)$ (Euler’s totient).
   • Pick $e$ (public exponent, usually 65537) such that $1<e<\varphi (n)$ and $\gcd (e,\varphi (n))=1$.
   • Compute $d$ (private exponent) as the modular inverse of $e$: $d\equiv e^{-1}\mathrm{mod}\varphi (n)$.

2. Encryption:

   • Convert plaintext $M$ to an integer $m<n$.
   • Ciphertext $c=m^e\mathrm{mod}n$.

3. Decryption:

   • Plaintext $m=c^d\mathrm{mod}n$.

Why RSA is secure:

• Relies on the hardness of factoring $n$ into $p$ and $q$.
• Even if $n$ is known, breaking RSA requires solving a 2048-bit+ factorization problem (infeasible today).

Worked Example: RSA with $p=61$, $q=53$

1. Compute $n=61\times 53=3233$.
2. $\varphi (n)=50\times 52=2600$.
3. Choose $e=17$ (since $\gcd (17,2600)=1$).
4. Compute $d$:
   • Find $d$ such that $17d\equiv 1\mathrm{mod}2600$.
   • Using the Extended Euclidean Algorithm: $d=2311$.
5. Encrypt $M=42$:
   • $c=42^{17}\mathrm{mod}3233=2790$.
6. Decrypt $c=2790$:
   • $m=2790^{2311}\mathrm{mod}3233=42$.

sequenceDiagram
    Alice->>Bob: Sends PK (n=3233, e=17)
    Bob->>Alice: Encrypts M=42 → c=2790
    Alice->>Bob: Decrypts c=2790 → M=42

3. Diffie-Hellman: Secure Key Exchange

Diffie-Hellman (DH) solves the "key distribution problem"—how Alice and Bob agree on a shared secret over an insecure channel (e.g., public Wi-Fi).

How DH Works

1. Agree on:
   • A prime $p$ (e.g., 23).
   • A generator $g$ (e.g., 5).
2. Alice:
   • Picks private key $a=4$, computes $A=g^a\mathrm{mod}p=5^4\mathrm{mod}23=4$.
3. Bob:
   • Picks private key $b=3$, computes $B=g^b\mathrm{mod}p=5^3\mathrm{mod}23=10$.
4. Exchange:
   • Alice sends $A=4$ to Bob.
   • Bob sends $B=10$ to Alice.
5. Shared Secret:
   • Alice computes $s=B^a\mathrm{mod}p=10^4\mathrm{mod}23=18$.
   • Bob computes $s=A^b\mathrm{mod}p=4^3\mathrm{mod}23=18$.

Why it’s secure:

• Eavesdropper sees $A$ and $B$ but cannot compute $s$ without solving the Discrete Logarithm Problem (DLP).

Real-World Use: WhatsApp Calls

WhatsApp uses Signal Protocol, which combines DH with ECDH (Elliptic Curve DH) to securely exchange keys for voice/video calls. Even if Ncell’s network is compromised, attackers can’t decrypt your call.

4. Public Key Infrastructure (PKI)

PKI is the "trust system" behind HTTPS, digital signatures, and secure emails. It uses certificates to bind identities to public keys.

How PKI Works

1. Certificate Authority (CA):
   • A trusted third party (e.g., GlobalSign, DigiCert) issues digital certificates.
   • Example: When you visit https://esewa.com.np, your browser checks eSewa’s certificate chain up to a root CA like Let’s Encrypt.
2. Certificate Format:
   • Contains: Subject (e.g., esewa.com.np), Public Key, Issuer (CA), Expiry Date, and a digital signature by the CA.
3. Certificate Chain:
   • Your browser trusts root CAs pre-installed in its trust store.
   • For a website, it follows the chain: Website → Intermediate CA → Root CA.

erDiagram
    RootCA ||--o{ IntermediateCA : "issues"
    IntermediateCA ||--o{ Website : "issues"
    Website {
        string domain
        string publicKey
        date expiry
    }

Real-World Example: NEPSE’s Secure Trading

NEPSE uses PKI to:

• Sign trade confirmations digitally (preventing repudiation).
• Encrypt sensitive investor data (using certificates from Nepal Rastra Bank’s CA).

5. Digital Signatures: Proving Authenticity

Digital signatures prove that:

1. A message was sent by the claimed sender (authentication).
2. The message was not altered (integrity).

How Digital Signatures Work (RSA Example)

1. Signing:
   • Alice hashes the message $M$ → $h=\text{SHA-256}(M)$.
   • She signs with her private key: $s=h^d\mathrm{mod}n$.
2. Verification:
   • Bob computes $h^{\prime }=s^e\mathrm{mod}n$.
   • If $h^{\prime }=\text{SHA-256}(M)$, the signature is valid.

Real-World Use: eSewa’s Payment Receipts

When you pay via eSewa, the receipt is digitally signed by eSewa’s private key. You (or a bank) can verify it using eSewa’s public key to ensure:

• The amount is correct.
• The transaction wasn’t altered.

6. Comparison: Symmetric vs. Asymmetric

Hybrid Approach (TLS/SSL):

• Uses asymmetric crypto to exchange a symmetric key (e.g., AES).
• Example: When you visit https://daraz.com.np, RSA exchanges a session key for fast AES encryption.

7. Weaknesses and Attacks

Real-World Example: Heartbleed Bug (2014)

• Exploited a flaw in OpenSSL’s heartbeat extension (used in HTTPS).
• Allowed attackers to steal private keys from memory.
• Affected Ncell’s old servers and global sites like Yahoo.

## In the Real World

1. eSewa’s Secure Payments

   • Uses RSA-2048 to encrypt transactions between your phone and eSewa’s servers.
   • Your private key (stored in your phone’s secure enclave) signs payments, while eSewa’s public key verifies them.
   • Why it matters: Without RSA, hackers could intercept and modify your payment details.

2. Ncell’s SIM Card Authentication

   • Your SIM card stores a private key for GSM authentication (A5/1 cipher).
   • When you call, your phone and Ncell’s tower perform a DH-like key exchange to encrypt your voice data.
   • Why it matters: Prevents eavesdropping on your calls (though older 2G networks are still vulnerable).

3. NEPSE’s Digital Signatures for Trading

   • Brokers use PKCS#7 (a digital signature standard) to sign trade orders.
   • Example: If you buy shares of Nabil Bank, the trade confirmation is signed with the broker’s private key. NEPSE’s system verifies it using the broker’s public key to ensure no tampering.
   • Why it matters: Prevents fraudulent trades and disputes.

4. Pathao’s Driver-Verification System

   • Pathao uses PKI certificates to verify driver identities.
   • When you book a ride, Pathao’s app checks the driver’s digital certificate (issued by a trusted CA) to confirm their real name and vehicle details.
   • Why it matters: Reduces fake driver scams.

## Exam Tip

1. RSA Questions:

   • Always show all steps: $n=p\times q$, $\varphi (n)$, choosing $e$, computing $d$ via modular inverse.
   • For decryption, use modular exponentiation (e.g., $c^d\mathrm{mod}n$).
   • Common pitfall: Forgetting to reduce modulo $n$ at each step (leads to huge numbers).

2. Diffie-Hellman:

   • Memorize the four steps: agree $p,g$, compute $A=g^a$, $B=g^b$, then $s=B^a=A^b$.
   • Exam trick: If given $p=23$, $g=5$, $a=4$, $b=3$, compute $s=18$ (as in the example).

3. PKI and Digital Signatures:

   • Draw the certificate chain (Root → Intermediate → End-entity).
   • For signatures, explain hashing first, then signing with the private key.
   • Key point: A valid signature proves authenticity and integrity, not confidentiality.

4. Comparisons:

   • Always compare speed, key size, and use cases (e.g., "AES is faster but needs key exchange; RSA is slower but enables secure key exchange").
   • Example answer:

     "Symmetric ciphers like AES use a single key for encryption/decryption, making them 1000x faster than RSA. However, distributing the key securely is problematic, which is why hybrid systems like TLS use RSA to exchange an AES key."

5. Weak Keys:

   • For DES, weak keys are those where all subkeys are identical (e.g., key = 0x0101010101010101).
   • For RSA, weak keys occur if $p$ and $q$ are too close (e.g., $p=q+2$), making factoring easier.

6. Diagrams:

   • Always draw:
     • RSA’s modular arithmetic steps.
     • DH’s key exchange sequence.
     • PKI’s certificate hierarchy.
   • Pro tip: Label every arrow and box in your diagram—examiners reward clarity.