Asymmetric Cryptography & Digital Signatures: RSA, ECC, DSS, and Real-World Use

Core Concepts: Symmetric vs. Asymmetric Cryptography

Asymmetric cryptography solves symmetric cryptography’s key distribution problem by using two mathematically linked keys:

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

Unlike symmetric keys (e.g., AES), asymmetric keys cannot be derived from each other—only via computational hardness assumptions (e.g., factoring, discrete logarithms).

Why asymmetric?

• Secure key exchange: Diffie-Hellman (not covered here) or RSA can share a symmetric key over an insecure channel.
• Digital signatures: Prove a message came from you (non-repudiation).
• Authentication: Verify identities (e.g., HTTPS certificates).

1. RSA: The Workhorse of Asymmetric Cryptography

RSA (Rivest-Shamir-Adleman) is the most widely used asymmetric algorithm, relying on the difficulty of factoring large primes.

sequenceDiagram
    participant Alice
    participant Bob
    participant eSewa
    Alice->>eSewa: Transaction Request (encrypted with eSewa's Public Key)
    eSewa-->>Alice: Signed Receipt (encrypted with eSewa's Private Key)
    Note right of eSewa: **RSA Encryption**: Only eSewa can decrypt
    Alice->>Bob: Payment Confirmation (digitally signed with eSewa's Private Key)
    Bob->>Alice: Verification (using eSewa's Public Key)
    Note right of Bob: **RSA Signature**: Proves authenticity

How RSA Works

1. Key Generation:

   • Choose two large primes p and q (e.g., 61 and 59 in examples, but real-world uses 1024+ bits).
   • Compute n = p × q (modulus) and φ(n) = (p–1)(q–1) (Euler’s totient).
   • Pick e (public exponent, usually 65537) such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.
   • Compute d (private exponent) as the modular inverse of e mod φ(n): $d\equiv e^{-1}\mathrm{mod}\varphi (n)$.

2. Encryption: For a message m (as an integer < n), ciphertext c is: $c\equiv m^e\mathrm{mod}n$.

3. Decryption: $m\equiv c^d\mathrm{mod}n$.

Worked Example: RSA with p=5, q=19, m=4

stateDiagram-v2
    [*] --> KeyGen: p=5, q=19
    KeyGen --> Compute: n = 5×19 = 95
    Compute --> Compute: φ(n) = 4×18 = 72
    Compute --> Choose: e=5 (since gcd(5,72)=1)
    Choose --> Compute: d = 5⁻¹ mod 72 = 29 (since 5×29 ≡ 1 mod 72)
    KeyGen --> PublicKey: (e=5, n=95)
    KeyGen --> PrivateKey: (d=29, n=95)
    PublicKey --> Encrypt: c = 4⁵ mod 95 = 1024 mod 95 = 34
    Encrypt --> Decrypt: m = 34²⁹ mod 95 = 4
    Decrypt --> [*]

Step-by-Step Calculation:

1. n = 5 × 19 = 95
2. φ(n) = (5–1)(19–1) = 4 × 18 = 72
3. Choose e = 5 (must be coprime with 72; gcd(5,72)=1).
4. Find d such that $5d\equiv 1\mathrm{mod}72$. Testing: $5\times 29=145\equiv 1\mathrm{mod}72$ ⇒ d = 29.
5. Encrypt m=4: $c=4^5\mathrm{mod}95=1024\mathrm{mod}95=34$.
6. Decrypt c=34: $m=34^{29}\mathrm{mod}95$. Use modular exponentiation (e.g., square-and-multiply):
   • Break 29 into binary: 11101.
   • Compute step-by-step: $34^1\mathrm{mod}95=34$ $34^2\mathrm{mod}95=1156\mathrm{mod}95=41$ $34^4\mathrm{mod}95=41^2\mathrm{mod}95=1681\mathrm{mod}95=1$ $34^8\mathrm{mod}95=1^2\mathrm{mod}95=1$ $34^{16}\mathrm{mod}95=1$ Combine: $34^{29}=34^{16}\times 34^2\times 34^1\mathrm{mod}95=1\times 41\times 34\mathrm{mod}95=1394\mathrm{mod}95=4$.

RSA in the Real World

1. eSewa Payments:

   • When you pay bills via eSewa, your public key (embedded in the app) encrypts your transaction details. The private key (held securely by eSewa’s servers) decrypts and verifies the payment.
   • Digital signatures ensure the transaction request is authentic (not spoofed).

2. Ncell’s SIM Card Authentication:

   • Your SIM card stores an RSA private key for authenticating to the Ncell network. The network holds your public key to verify your identity when you make calls/data requests.

3. NEPSE (Nepal Stock Exchange):

   • Investors use RSA-signed certificates to authenticate trades. The exchange’s servers verify signatures to prevent fraudulent orders.

2. Elliptic Curve Cryptography (ECC): Smaller Keys, Same Security

ECC provides equivalent security to RSA but with smaller key sizes (e.g., 256-bit ECC ≈ 3072-bit RSA). It uses elliptic curves over finite fields.

Key Concepts

• Elliptic Curve: Defined by $y^2=x^3+ax+b$ over a finite field ${\mathbb{F}}_p$.
• Discrete Logarithm Problem (ECDLP): Hard to compute $k$ given $Q=kG$, where $G$ is a base point.
• Key Generation:
  1. Choose a curve $E$ and base point $G$.
  2. Pick a private key $k$ (random integer).
  3. Public key $Q=kG$ (scalar multiplication).

ECC vs. RSA: Comparison

Why ECC?

• Mobile Devices: Pathao’s driver-app uses ECC for lightweight authentication.
• IoT: Smart meters in Kathmandu use ECC to secure communications with low power.
• Blockchain: Bitcoin’s secp256k1 curve is an ECC variant.

3. Digital Signatures: Proving Authenticity

Digital signatures bind a message to a signer’s identity using asymmetric cryptography. Two main approaches:

1. RSA-Based Signatures:
   • Sign: $s=m^d\mathrm{mod}n$ (private key).
   • Verify: $m^{\prime }=s^e\mathrm{mod}n$. If $m^{\prime }=m$, signature is valid.
2. DSS (Digital Signature Standard):
   • Uses DSA (Digital Signature Algorithm) or ECDSA (Elliptic Curve DSA).
   • More efficient for large messages.

How DSS Works (DSA)

1. Key Generation:
   • Choose a prime $p$, subgroup generator $g$, and hash function (e.g., SHA-256).
   • Pick private key $x$, compute public key $y=g^x\mathrm{mod}p$.
2. Signing:
   • Hash message $m$ to get $h=H(m)$.
   • Pick random $k$, compute: $r=(g^k\mathrm{mod}p)\mathrm{mod}q$, $s=(k^{-1}(h+xr))\mathrm{mod}q$.
3. Verification:
   • Compute $w=s^{-1}\mathrm{mod}q$, $u1=(h\cdot w)\mathrm{mod}q$, $u2=(r\cdot w)\mathrm{mod}q$, $v=(g^{u1}\cdot y^{u2}\mathrm{mod}p)\mathrm{mod}q$.
   • If $v=r$, signature is valid.

Real-World Example: WhatsApp Messages

• When you send a message on WhatsApp:
  1. Your device signs the message with your private key (ECDSA).
  2. The recipient’s device verifies the signature using your public key (from WhatsApp’s server).
  3. If verification fails, the message is flagged as tampered or spoofed.

4. Security Considerations

Exam Tip: Always mention key size and mathematical hardness when discussing security!

5. Playfair and Vernam Ciphers (Bonus: Symmetric Context)

While not asymmetric, these are often confused in exams:

• Playfair Cipher:

  • Uses a 5×5 matrix and digraphs (pairs of letters).
  • Confusion: Substitutes letters; Diffusion: Shuffles positions.
  • Example: Encrypt "TRIBHUVAN" with key "BES":
    1. Create matrix with key "BES" + fill remaining letters (skip 'J').
    2. Split message into digraphs: TR IB HU VA NN (pad with 'X' if odd).
    3. Encrypt each pair (e.g., "TR" → "BO", "IB" → "QM").

• Vernam Cipher:

  • One-time pad (perfect secrecy if key is truly random and never reused).
  • XOR message with key: $c=m\oplus k$, $m=c\oplus k$.

Exam Tip: How to Score Full Marks

1. For RSA/ECC Questions:

   • Always show all steps of key generation (p, q, n, φ(n), e, d).
   • Use modular arithmetic explicitly (e.g., $4^5\mathrm{mod}95$).
   • For decryption, explain modular exponentiation (square-and-multiply).

2. For Digital Signatures:

   • Draw a signature process diagram (signer → hash → sign → verify).
   • Compare RSA vs. DSS in a table (speed, key size, use cases).

3. Common Pitfalls:

   • Forgetting to reduce modulo n in RSA operations.
   • Miscomputing φ(n) as $n-1$ instead of $(p-1)(q-1)$.
   • Ignoring padding schemes (e.g., OAEP for RSA) in real-world use.

4. Past Exam Patterns:

   • 5-mark questions: Key generation + encryption/decryption (show all steps).
   • 2-mark questions: Define terms (e.g., "What is a digital signature?" → "A mathematical scheme to verify authenticity and integrity using private/public keys").
   • 3-mark questions: Compare algorithms (e.g., RSA vs. ECC) or explain a concept (e.g., "Why is ECDLP hard?").

Final Note: Asymmetric cryptography is the backbone of secure communications today. Master RSA’s math, understand ECC’s efficiency, and always relate digital signatures to real-world trust (e.g., eSewa, Ncell, or WhatsApp). Practice with small primes (like p=5, q=19) to grasp the mechanics before tackling larger keys.

In the real world

• eSewa/Khalti Payments: Uses RSA encryption to secure transaction data between user devices and servers, and RSA digital signatures to authenticate payment requests (preventing spoofing).
• Ncell SIM Authentication: Stores an RSA private key on the SIM card to authenticate calls/data requests; the network verifies using the public key stored in its database.
• WhatsApp End-to-End Encryption: Relies on ECDSA digital signatures to prove messages originate from the claimed sender (visible in the '✓ Verified' badge).