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

Key Concepts and Definitions

What is Public Key Cryptography?

Public key cryptography (asymmetric cryptography) uses a pair of keys: a public key (shared openly) and a private key (kept secret). Data encrypted with the public key can only be decrypted with the private key, and vice versa. This solves the key distribution problem inherent in symmetric cryptography.

stateDiagram-v2
    [*] --> PublicKey: Shared openly
    [*] --> PrivateKey: Kept secret
    PublicKey --> Encrypt: Data
    PrivateKey --> Decrypt: Data
    PrivateKey --> Sign: Data
    PublicKey --> Verify: Signature

Why Use Public Key Cryptography?

• Key Distribution: No need to securely share a single key.
• Authentication: Digital signatures prove identity.
• Non-repudiation: The sender cannot deny sending a message.
• Confidentiality: Secure communication without pre-shared secrets.

RSA Algorithm: The Workhorse of Asymmetric Cryptography

How RSA Works

RSA relies on the mathematical difficulty of factoring large prime numbers. The steps are:

1. Key Generation:
   • Choose two large primes $p$ and $q$.
   • Compute $n=p\times q$ (modulus).
   • Compute Euler’s totient function $\varphi (n)=(p-1)(q-1)$.
   • Choose an integer $e$ (public exponent) such that $1<e<\varphi (n)$ and $\gcd (e,\varphi (n))=1$.
   • Compute $d$ (private exponent) as the modular inverse of $e$ modulo $\varphi (n)$.
2. Encryption: $C=M^e\mathrm{mod}n$.
3. Decryption: $M=C^d\mathrm{mod}n$.

Worked Example: RSA Encryption

Let’s encrypt the message $M=2$ using:

• $p=5$, $q=11$, so $n=55$.
• $\varphi (n)=40$.
• Choose $e=3$ (since $\gcd (3,40)=1$).
• Compute $d=27$ (since $3\times 27\mathrm{mod}40=1$).

Encryption: $C=2^3\mathrm{mod}55=8$.

Decryption: $M=8^{27}\mathrm{mod}55=2$.

Elliptic Curve Cryptography (ECC): Efficiency in Smaller Keys

Why ECC?

ECC provides equivalent security to RSA but with smaller key sizes. For example, a 256-bit ECC key offers security comparable to a 3072-bit RSA key. This makes ECC faster and more efficient for resource-constrained devices (e.g., smartphones, IoT).

How ECC Works

ECC relies on the algebraic structure of elliptic curves over finite fields. The security is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is computationally hard.

classDiagram
    class EllipticCurve {
        +Equation: y² = x³ + ax + b
        +PointAddition: P + Q = R
    }
    class ECC {
        +KeyGeneration: PrivateKey + BasePoint
        +Encryption: PublicKey + Plaintext
        +Decryption: PrivateKey + Ciphertext
    }
    EllipticCurve <|-- ECC

Comparison: RSA vs. ECC

Diffie-Hellman Key Exchange: Secure Key Agreement

Problem Solved

How can two parties securely agree on a shared secret over an insecure channel? Diffie-Hellman (DH) solves this using exponential modular arithmetic.

How DH Works

1. Both parties agree on a public prime $p$ and a generator $g$.
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. Alice computes the shared secret $s=B^a\mathrm{mod}p$.
5. Bob computes the shared secret $s=A^b\mathrm{mod}p$.

Worked Example: DH Key Exchange

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:
  • Alice: $19^6\mathrm{mod}23=2$.
  • Bob: $8^{15}\mathrm{mod}23=2$.

Digital Signatures: Proving Authenticity

How Digital Signatures Work

1. The sender signs a message using their private key.
2. The recipient verifies the signature using the sender’s public key.
3. Common algorithms: RSA, ECC, DSA (Digital Signature Algorithm).

Worked Example: RSA Digital Signature

1. Alice hashes the message $M$ to get $H(M)$.
2. She signs $H(M)$ with her private key $d$: $S=H(M{)}^d\mathrm{mod}n$.
3. Bob verifies by computing $H(M)=S^e\mathrm{mod}n$ and checking if it matches the hash of the received message.

In the Real World

1. eSewa and Khalti (Nepal):

   • Use ECC or RSA for secure transactions. When you pay via Khalti, your card details are encrypted with the merchant’s public key, ensuring confidentiality. The digital signature on the transaction proves you authorized it (non-repudiation).

2. WhatsApp End-to-End Encryption:

   • Uses the Signal Protocol, which combines Diffie-Hellman for key exchange and AES (symmetric) for message encryption. Your private key never leaves your device, and even WhatsApp cannot read your messages.

3. Nepal Stock Exchange (NEPSE):

   • Trades are authenticated using digital signatures (likely RSA or ECC) to prevent fraud. When you place an order, the exchange verifies your signature with your public key to confirm you are authorized.

4. Pathao Driver-Passenger Matching:

   • When a driver accepts a ride request, Diffie-Hellman is used to establish a secure session key for real-time location sharing and payment processing. This ensures no third party can intercept or alter the data.

Exam Tip

1. Understand the Math: Focus on the modular arithmetic in RSA and DH. Be able to compute small examples manually (e.g., $5^6\mathrm{mod}23$).
2. Key Differences: Memorize the trade-offs between RSA, ECC, and DH (key size, speed, use cases).
3. Digital Signatures: Know how hashing + private key signing + public key verification works. Practice a full trace.
4. Real-World Applications: Link algorithms to systems like TLS (uses RSA/ECC for key exchange), Bitcoin (ECDSA for signatures), and VPNs (IKE uses DH).
5. Security Assumptions: RSA relies on factoring hardness; ECC on ECDLP; DH on discrete log hardness. Examiners may ask which problem each algorithm resists.
6. Diagrams: Draw the RSA/ECC/DH workflows in exams. A well-labeled sequence diagram for DH or a state diagram for signature verification can earn easy marks.

How a recipient verifies an RSA digital signature. (Image: FlippyFlink, CC BY-SA 4.0, via Wikimedia Commons)