Project 3 (El Gamal Cryptosystem): The El Gamal cryptosystem, named after its inventor, Taher El Gamal, is a public-key cryptosystem that uses randomization, so that independent encryptions of the same plaintext are likely to produce different ciphertexts. It is based on viewing input blocks as numbers and applying arithmetic operations on these numbers to perform encryption and decryption. As a part of the setup, Bob chooses a random number x between 1 and p – 2, and computes y = g x mod p. The number x is Bob’s secret key. His public key is the triple (p, g, y). When Alice wants to encrypt a plaintext message M for Bob, she begins by getting his public key (p, g, y). She, then, generates a random number k between 1 and p – 2, and she then uses modular multiplication and exponentiation to compute two numbers: a = g k mod p b = My k mod p The encryption of M is the pair (a, b). Given an El Gamal ciphertext (a, b) created for Bob, he can decrypt this ciphertext by computing a x mod p, computing the inverse of this value modulo p, and multiplying the result by b, modulo p. This sequence of computations gives Bob the following: M = b(a x ) –1 mod p The reason this actually decrypts the ciphertext is as follows: b(a x ) –1 mod p = My k (g kx) –1 mod p = M(g x ) k g –kx mod p = Mg xk g –kx mod p = M mod p = M