Unit 5: Public Key Cryptography - Subjective Questions

Public-key cryptography (also called asymmetric cryptography) is a cryptographic system that uses a pair of mathematically related keys: a public key (shared openly) and a private key (kept secret).

Key differences from symmetric cryptography:

• Key usage:
  • Symmetric: a single shared secret key is used for both encryption and decryption.
  • Asymmetric: uses two different keys — one to encrypt, another to decrypt.
• Key distribution:
  • Symmetric: suffers from the key distribution problem (secure channel needed to share the key).
  • Asymmetric: the public key can be distributed freely; no secure channel needed.
• Speed:
  • Symmetric algorithms (e.g., AES) are faster.
  • Asymmetric algorithms (e.g., RSA) are slower due to heavy mathematical operations.
• Security basis: Public-key schemes rely on hard mathematical problems such as integer factorization or the discrete logarithm problem.

Common uses: key exchange, digital signatures, and secure communication over insecure channels.

Motivation for Public-Key Cryptography:

Classical (symmetric) cryptography requires both parties to share a common secret key before communication. This creates several problems:

• Key distribution problem: How do two parties securely agree on a secret key over an insecure channel without a prior meeting?
• Key management scalability: For users, a symmetric system requires keys, which grows quadratically.
• No digital signatures: Symmetric keys cannot easily provide non-repudiation or authentication of a sender.

How public-key cryptography solves these:

• Each user has a public/private key pair. The public key is published openly; the private key is kept secret.
• No secret channel is needed to exchange keys.
• Only keys are needed for users.
• Enables digital signatures (sign with private key, verify with public key), providing authentication and non-repudiation.

The concept was introduced by Diffie and Hellman (1976), laying the foundation for modern secure communication.

The Diffie-Hellman (DH) key exchange allows two parties to establish a shared secret key over an insecure channel.

Setup (public parameters):

• A large prime .
• A primitive root (generator) modulo .

Steps:

1. Alice chooses a private secret and computes:
   
   She sends to Bob.

2. Bob chooses a private secret and computes:
   
   He sends to Alice.

3. Alice computes the shared key:
   

4. Bob computes the shared key:
   

Both arrive at the same value .

Security: Relies on the Discrete Logarithm Problem (DLP) — given , , and , it is computationally infeasible to recover .

Note: Basic DH is vulnerable to man-in-the-middle attacks and needs authentication.

Given: , , , .

Step 1 — Alice computes her public value:

, and .
So .

Step 2 — Bob computes his public value:

Computing stepwise: , , .
.
.
So .

Step 3 — Alice computes shared key:

, so .
.
So .

Step 4 — Bob computes shared key:

, so . Since (order of 2 is 11), .
So .

Shared secret key = . Both parties agree. ✓

Discrete Logarithm Problem (DLP):

Given a cyclic group (e.g., ), a generator , and an element such that:

the DLP is the problem of finding the exponent (the discrete logarithm of to base ).

Why it is hard:

• While computing (modular exponentiation) is fast, reversing it to find is computationally infeasible for large primes.
• No known efficient (polynomial-time) classical algorithm exists for large .

Centrality to security:

• Diffie-Hellman: An eavesdropper sees and but cannot compute without solving the DLP (specifically the Computational Diffie-Hellman problem).
• ElGamal: Encryption security depends on the difficulty of recovering the private key from the public key .

Thus, the infeasibility of DLP guarantees that private keys cannot be recovered from public information, keeping the systems secure.

The RSA cryptosystem (Rivest, Shamir, Adleman, 1977) is a public-key algorithm based on the difficulty of factoring large integers.

1. Key Generation:

• Choose two large distinct primes and .

• Compute the modulus: .

• Compute Euler's totient: .

• Choose a public exponent such that and .

• Compute the private exponent such that:
  

• Public key: ; Private key: .

2. Encryption: For a plaintext message (with ):

3. Decryption: For ciphertext :

Correctness follows from Euler's theorem: .

Security: Rests on the difficulty of factoring into and .

Step 1 — Compute :

Step 2 — Compute :

Step 3 — Verify : ✓, so is valid.

Step 4 — Compute :
We need .
Using the extended Euclidean algorithm:

• , and . ✓

So .

Step 5 — Encrypt :

Compute stepwise:

Ciphertext .

Public key: ; Private key: .

Claim: For RSA, decryption recovers the plaintext: .

Given: , , and .

This means for some integer .

We must show: .

Using the Chinese Remainder Theorem, it suffices to show the congruence holds modulo and modulo separately.

Modulo :

• Case 1: If , then by Fermat's Little Theorem, .
  
• Case 2: If , then , so .

Either way: .

Modulo : By identical reasoning, .

Combining: Since and , and are distinct primes, by CRT:

Hence RSA decryption is correct.

The ElGamal cryptosystem (1985) is a public-key scheme based on the Discrete Logarithm Problem.

1. Key Generation:

• Choose a large prime and a generator of .
• Choose a private key where .
• Compute the public value: .
• Public key: ; Private key: .

2. Encryption: To encrypt message ():

• Choose a random ephemeral key with .
• Compute:
  
  
• Ciphertext: .

3. Decryption: Given :

Why it works:

Key features:

• Probabilistic encryption — same plaintext gives different ciphertexts (due to random ).
• Ciphertext expansion — ciphertext is twice the size of plaintext.

Step 1 — Compute public key :

, , .
So . Public key: .

Step 2 — Encryption with :

. . So .
So .

, so .
.
So . Ciphertext: .

Step 3 — Decryption:

. , , .
Inverse of : , so .
. ✓

Decrypted message = 13, matching the original.

Comparison of RSA and ElGamal:

Key observations:

• ElGamal provides semantic security naturally due to randomization, whereas basic RSA does not (requires padding schemes like OAEP).
• RSA suffers ciphertext expansion only when compared to ElGamal's doubling.
• Both are considered secure with sufficiently large key sizes but rely on different mathematical hardness assumptions.

Modular exponentiation is the computation of:

where is the base, the exponent, and the modulus. It is the core operation in RSA, Diffie-Hellman, and ElGamal.

Problem with naive computation:

• Computing directly produces an enormous number before reduction (e.g., ), which is infeasible.

Square-and-Multiply (fast exponentiation):

This algorithm computes efficiently using the binary representation of the exponent .

Steps:

1. Write in binary: .
2. Initialize result .
3. Scan bits from most significant to least:
   • Square the result modulo .
   • If the current bit is , multiply by modulo .

Example: , where :

Importance:

• Reduces complexity from multiplications to .
• Keeps intermediate values small by reducing mod at each step.
• Makes public-key operations practical for large exponents and moduli.

Man-in-the-Middle (MITM) Attack on Diffie-Hellman:

Basic Diffie-Hellman provides no authentication of the communicating parties, making it vulnerable to a MITM attack.

How the attack works:

1. Alice sends intended for Bob.
2. The attacker Mallory intercepts it and sends her own value to Bob.
3. Bob sends ; Mallory intercepts and sends to Alice.
4. Now:
   • Alice and Mallory share a key .
   • Bob and Mallory share a key .
5. Mallory sits in the middle, decrypting and re-encrypting all messages, reading and possibly altering them, while Alice and Bob believe they share a secure key.

Prevention methods:

• Authenticated Diffie-Hellman: Combine DH with digital signatures or certificates (e.g., Station-to-Station protocol).
• Public Key Infrastructure (PKI): Certificates from trusted Certificate Authorities validate identities.
• Pre-shared authentication data or password-authenticated key exchange (PAKE).

The root cause is the lack of identity verification, so any fix must authenticate the exchanged public values.

Security of RSA rests on the difficulty of factoring . However, several attacks exist if RSA is used improperly.

1. Factorization attack:

• If an attacker factors , they compute and hence . Prevented by using large primes (2048+ bit ).

2. Small exponent attacks:

• Small (e.g., ): If the same message is sent to multiple recipients, Håstad's broadcast attack can recover it.
• Small : Wiener's attack recovers if .

3. Common modulus attack:

• Sharing the same among users with different exponents leaks information.

4. Chosen-ciphertext attacks:

• RSA's multiplicative (homomorphic) property allows attackers to manipulate ciphertexts. Mitigated with OAEP padding.

5. Timing / side-channel attacks:

• Measuring decryption time can reveal . Prevented via blinding.

Best practices:

• Use large key sizes, random padding (OAEP), distinct primes of similar size, and secure implementations.
• Never reuse primes or use predictable random number generation.

Euler's Totient Function :

counts the number of integers in that are coprime to .

• For a prime : .
• For (product of two distinct primes): .

Role in RSA:

• Used to select the public exponent such that .
• Used to compute the private exponent: .

Euler's Theorem:

If , then:

Role in RSA correctness:

Since , we can write . Then:

Thus Euler's theorem guarantees that decryption recovers the original message. It is the mathematical foundation ensuring RSA works correctly (with Fermat's Little Theorem covering the case ).

Both problems relate to the security of DLP-based cryptosystems but are distinct.

Discrete Logarithm Problem (DLP):

• Given: , , and .
• Find: the exponent .
• This is the more general/fundamental problem.

Computational Diffie-Hellman (CDH) Problem:

• Given: , , , and (but not or ).
• Find: .
• This is exactly the value Diffie-Hellman relies on staying secret.

Relationship:

• If you can solve DLP, you can solve CDH: recover from , then compute .
• Therefore DLP hard CDH at least as easy, and solving CDH is no harder than DLP.
• Whether CDH is strictly easier than DLP is an open question in general; for practical secure groups, both are assumed hard.

Summary:

Step 1 — Compute and :

Step 2 — Verify : ✓.

Step 3 — Compute private key :
We need .
Try : , and . ✓
So .

Step 4 — Decrypt :

Compute using square-and-multiply ():

, so:

Plaintext .

Digital signatures provide authentication, integrity, and non-repudiation — proving a message came from a specific sender and was not altered.

General principle:

• Signing uses the sender's private key.
• Verification uses the sender's public key.
• This is the reverse of encryption (where the receiver's public key encrypts).

RSA Digital Signature Scheme:

Setup: Alice has public key and private key .

1. Signing (by Alice):

• Compute a hash of the message: .
• Sign by raising to the private exponent:
  
• Send .

2. Verification (by Bob):

• Compute from the received message.
• Recover the signed hash using Alice's public exponent:
  
• Accept the signature if .

Why it works:

Security properties:

• Only Alice (who holds ) can produce a valid → authentication & non-repudiation.
• Any change to changes → integrity.

Hashing before signing ensures efficiency and prevents forgery attacks based on RSA's multiplicative property.

Deterministic nature of textbook RSA:

In basic RSA, encryption is simply:

For a fixed public key , the same plaintext always yields the same ciphertext . There is no randomness involved.

Why this is a weakness:

• Lack of semantic security: An attacker who sees a ciphertext can compare it to encryptions of guessed plaintexts.
• Chosen-plaintext / dictionary attacks: If the message space is small (e.g., 'yes'/'no', or a PIN), the attacker simply encrypts all possibilities and matches the ciphertext.
• Pattern leakage: Repeated identical messages produce identical ciphertexts, revealing patterns in communication.
• Multiplicative (homomorphic) property: , enabling ciphertext manipulation and chosen-ciphertext attacks.

How it is addressed — Randomized Padding:

• OAEP (Optimal Asymmetric Encryption Padding): Adds structured randomness to the plaintext before encryption, so the same message encrypts to different ciphertexts each time.
• Padding also destroys the multiplicative structure, defeating malleability attacks.

Conclusion: Real-world RSA (RSA-OAEP) is probabilistic and provides semantic security, unlike vulnerable textbook RSA.

Key relationship in RSA:

The public exponent and private exponent must satisfy:

This means is the modular multiplicative inverse of modulo . Equivalently:

This inverse exists if and only if , which is why is chosen coprime to .

Using the Extended Euclidean Algorithm (EEA):

The EEA finds integers such that:

Taking this equation modulo :

Thus is the inverse of , i.e., (adjusted to be positive).

Worked example: Let , .

Apply EEA to :

Back-substitute:

So , giving .

Check: ✓.

Thus the EEA efficiently computes , completing key generation.