*This is a Cryptography question*

3.12 Hoffstein

Formulate a man-in-the-middle attack, similar to the attack described in Example 3.13 on page 126, for the following public key cryptosystems.

Example 3.13 (Woman-in-the-Middle Attack). Suppose that Eve is not simply an eavesdropper, but that she has full control over Alice and Bobs communication network. In this case, she can institute what is known as a man-inthe-middle attack. We describe this attack for DiffieHellman key exchange, but it exists for most public key constructions.

1. The Elgamal public key cryptosystem (Table 2.3 on page 72).

Public parameter creation
A trusted party chooses and publishes a large prime p and an element g modulo p of large (prime) order.
Alice	Bob
Key creation
Choose private key 1 a p 1. Compute A = ga (mod p). Publish the public key A.
Encryption
	Choose plaintext m. Choose random element k. Use Alices public key A to compute c1 = gk (mod p) and c2 = mAk (mod p). Send ciphertext (c1, c2) to Alice.
Decryption
Compute (ca 1)1 c2 (mod p). This quantity is equal to m.

Table 2.3: Elgamal key creation, encryption, and decryption

(b) The RSA public key cryptosystem (Table 3.1 on page 123).

Bob	Alice
Key creation
Choose secret primes p and q. Choose encryption exponent e with gcd(e,(p 1)(q 1)) = 1. Publish N = pq and e.
Encryption
	Choose plaintext m. Use Bobs public key (N,e) to compute c me (mod N). Send ciphertext c to Bob.
Decryption
Compute d satisfying ed 1 (mod (p 1)(q 1)). Compute m cd (mod N). Then m equals the plaintext m.

Table 3.1: RSA key creation, encryption, and decryption 3.2 The RSA Public Key C