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

Core Concepts

What is Public Key Cryptography?

Public key cryptography (also called asymmetric cryptography) uses two mathematically linked keys:

• Public Key: Shared openly (e.g., on a website or server).
• Private Key: Kept secret by the owner.

Unlike symmetric cryptography (e.g., AES), different keys are used for encryption and decryption. This solves the key distribution problem—no need to securely share a single key beforehand.

Why is this revolutionary?

• No pre-shared secret: Alice can encrypt a message with Bob’s public key, and only Bob (with his private key) can decrypt it.
• Digital signatures: Bob can sign a message with his private key, and anyone can verify it with his public key.

---

Key Algorithms

1. RSA (Rivest-Shamir-Adleman)

How it works: RSA relies on the difficulty of factoring large primes. The steps are:

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

2. Encryption: For a message $m$, the ciphertext $c$ is: $$c\equiv m^e\mathrm{mod}n$$

3. Decryption: The original message $m$ is recovered as: $$m\equiv c^d\mathrm{mod}n$$

Worked Example: Encrypting "HELLO" (ASCII values) with RSA Assume:

• $p=61$, $q=53$, so $n=3233$.
• $\varphi (n)=3120$, $e=17$, $d=2753$.

Convert "HELLO" to ASCII: [72, 69, 76, 76, 79]. Encrypt the first letter (72): $$c\equiv 72^{17}\mathrm{mod}3233=2790$$ Decrypt: $$m\equiv 2790^{2753}\mathrm{mod}3233=72(\text{recovering "H"})$$

Real-World Tie-In: eSewa Transactions When you pay via eSewa, your public key is used to encrypt your transaction details (e.g., amount, recipient). Only eSewa’s server (holding the private key) can decrypt and process it. This ensures end-to-end encryption even if the network is compromised.

---

2. Diffie-Hellman Key Exchange

Problem: How to securely share a symmetric key over an insecure channel? Solution: Use exponential modular arithmetic to derive a shared secret.

Steps:

1. Agree on a prime $p$ and a 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: $$s=B^a\mathrm{mod}p=A^b\mathrm{mod}p$$

Why it’s secure:

• An eavesdropper sees $p,g,A,B$ but cannot compute $s$ without knowing $a$ or $b$ (assuming the Discrete Logarithm Problem is hard).

Worked Example: Shared Secret Calculation Let $p=23$, $g=5$.

• Alice picks $a=6$, computes $A=5^6\mathrm{mod}23=8$.
• Bob picks $b=15$, computes $B=5^{15}\mathrm{mod}23=19$.
• Shared secret: $$s=19^6\mathrm{mod}23=8\text{or}s=8^{15}\mathrm{mod}23=19$$ (Both compute $s=2$, the actual shared key.)

Real-World Tie-In: WhatsApp Calls WhatsApp uses Signal Protocol, which combines Diffie-Hellman with RSA to establish a secure session key for voice/video calls. Even if someone intercepts your messages, they can’t decrypt the call without the ephemeral keys exchanged during the handshake.

---

3. Digital Signatures

Purpose: Prove authenticity and integrity of a message. How it works:

1. The sender signs the message with their private key.
2. The receiver verifies the signature with the sender’s public key.

Steps for RSA Signatures:

1. Hash the message $m$ to get a fixed-size digest $h=\text{Hash}(m)$.
2. Sign the digest: $\sigma =h^d\mathrm{mod}n$ (using the sender’s private key).
3. Send $(m,\sigma )$ to the receiver.
4. The receiver computes $h^{\prime }={\sigma }^e\mathrm{mod}n$ and checks if $h^{\prime }=\text{Hash}(m)$.

Why it’s better than symmetric signatures:

• No need to securely share a secret key for verification.
• Tampering is detectable (hash mismatch).

Worked Example: Signing a Message Assume Bob’s RSA keys: $n=3233$, $d=2753$, $e=17$. Message: "PAY 1000 NRS". Hash (simplified): $h=1234$. Signature: $$\sigma =1234^{2753}\mathrm{mod}3233=1872$$ Verification: $$h^{\prime }=1872^{17}\mathrm{mod}3233=1234\text{(matches)}$$

Real-World Tie-In: NEPSE Stock Trades When you buy/sell shares on NEPSE, your trade order is digitally signed with your broker’s private key. The exchange verifies the signature using the broker’s public key to ensure the order is authentic and unaltered.

---

Comparison: Public vs. Symmetric Key Cryptography

---

Advantages and Disadvantages

Advantages of Public Key Cryptography

1. Secure Key Exchange: Solves the problem of distributing symmetric keys (e.g., Diffie-Hellman).
2. Non-Repudiation: Digital signatures prove the sender’s identity (e.g., e-contracts).
3. Scalability: Public keys can be freely distributed (e.g., HTTPS certificates).
4. Forward Secrecy: Ephemeral keys (e.g., in TLS) limit damage if a private key is compromised.

Disadvantages

1. Computational Overhead: Slower than symmetric encryption (e.g., RSA is 1000x slower than AES).
2. Key Management: Private keys must be protected (e.g., lost keys = lost access).
3. Implementation Complexity: Requires careful handling of large primes and modular arithmetic.

---

Real-World Applications

1. HTTPS (Secure Web Browsing)

• How it uses PKI: When you visit https://esewa.com.np, your browser:
  1. Verifies eSewa’s SSL/TLS certificate (signed by a trusted CA like Let’s Encrypt).
  2. Uses RSA or ECDHE (Elliptic Curve Diffie-Hellman) to establish a symmetric session key.
  3. Switches to AES-256 for fast encryption of your login details.
• Why it matters: Prevents man-in-the-middle attacks (e.g., fake login pages).

2. Khalti Payments

• Digital Signatures: When you authorize a payment, Khalti signs the transaction with its private key. The bank verifies this signature to confirm the payment is legitimate.
• Key Exchange: Khalti’s app uses ECDH to securely negotiate a session key with the bank’s server before encrypting your card details.

3. Ncell’s Secure SMS

• Public Key Encryption: Ncell uses asymmetric encryption to send OTPs. Your phone’s public key (embedded in the SIM) encrypts the OTP, and only your phone (with the private key) can decrypt it.
• Prevents SIM Swapping: Even if an attacker steals your SIM, they can’t decrypt the OTP without the private key.

---

Security Considerations

Threats to Public Key Cryptography

1. Brute Force Attacks: Factoring $n$ in RSA or solving the discrete logarithm in Diffie-Hellman.
   • Mitigation: Use large key sizes (e.g., RSA-4096, ECC-256).
2. Quantum Computing: Shor’s algorithm can break RSA and ECC.
   • Mitigation: Research post-quantum cryptography (e.g., lattice-based schemes).
3. Private Key Theft: If a private key is leaked (e.g., via malware), all past communications can be decrypted.
   • Mitigation: Use hardware security modules (HSMs) or key escrow.

Best Practices

• Key Storage: Use password-protected key containers (e.g., GPG, Bitwarden).
• Key Rotation: Regularly update private keys (e.g., every 1–2 years).
• Certificate Authorities (CAs): Always verify certificates (e.g., check the padlock icon in browsers).

---

Exam Tip

Public key cryptography is heavily tested in TU exams, especially:

1. RSA Workings: Expect questions on key generation, encryption/decryption formulas, and modular arithmetic.
   • Example: "Given $p=7$, $q=11$, $e=3$, compute $d$ and encrypt $m=5$."
2. Diffie-Hellman: Focus on shared secret calculation and security assumptions.
   • Example: "Alice and Bob agree on $p=23$, $g=5$. Alice sends $A=8$. If Bob’s private key is 15, what is the shared secret?"
3. Digital Signatures: Understand hashing + signing and verification steps.
   • Example: "Explain how RSA signatures prevent replay attacks."
4. Real-World Scenarios: Relate concepts to e-commerce (eSewa, Daraz), banking (NMB, Global IME), or government systems (e-Dak).
   • Example: "How does NTC use public key cryptography to secure online bill payments?"

Common Pitfalls:

• Forgetting to reduce modulo $n$ in RSA operations.
• Confusing public/private keys in encryption vs. signatures.
• Ignoring key size requirements (e.g., using RSA-1024 in 2024 is insecure).

---

A diagram showing hashing → signing → transmission → verification. (Image: FlippyFlink, CC BY-SA 4.0, via Wikimedia Commons)