$30.00

## Description

Write a python program to implement the following variant of the ElGamal public key encryption scheme.

• KeyGen: This algorithm proceed as follows,

– Choose two primes p and q such that q = 2p + 1, and p is a 300-bit prime. [See Note 1]

_{– } _{Ch}_{o}_{ose} _{a} _{g} _{∈} _{Z}_{∗ } _{su}_{c}_{h} _{that } _{<} _{g} _{>=} _{QR} _{.}

q

– Choose a number

q

a uniformly at random from the set {2, 3, o(g) − 1}.

– Compute

_{h} _{=} _{g}^{a} _{m}_{o}_{d} _{q}_{.} _{[}_{See} _{Note} _{2}_{]}

– Set, PK = (q, g, h); SK = a.

• Encrypt: To encrypt a message m ∈ QR_{q } under the public key PK = (q, g, h), this algorithm proceeds as follows:

– Choose a random element r ∈ {2, . . . , q − 1}

^{– } ^{Compute } ^{C}_{1 } ^{=} ^{g}^{r} ^{m}^{o}^{d} ^{q}

^{– } ^{Compute } ^{C}_{2 } ^{=} ^{(h}^{r} ^{×} ^{m)} ^{m}^{o}^{d} ^{q}

^{– } ^{Output,} ^{ciphertext } ^{C} ^{=} ^{(C}_{1}^{,} ^{C}_{2}^{)}

• Decrypt: To decryt a ciphertext C = (C_{1}, C_{2} ) under the secret SK = a, this algorithm proceeds as follows:

^{– } ^{Compute } ^{t}_{1} ^{=} ^{(C}_{1}^{)}^{a} ^{m}^{o}^{d} ^{q}^{.}

1

^{– } ^{Compute } ^{t}_{2} ^{=} ^{(C}_{2 } ^{×} ^{t}^{−}^{1}^{)} ^{m}^{o}^{d} ^{q} ^{[}^{See} ^{Note} ^{3}^{]}

– Output decrypted message as

^{t}_{2} ^{.}

Some important instructions:

1. Note1: For prime generation, you must use Miller-Rabin Algorithm as described in Algorithm 5.7 of the reference book. [School book algorithm will take million of years to generate a 300-bit prime!!]

2. Note2: Use square-and-multiply algorithm given in Algorithm 5.5 of the reference book.

3. Note3: For modular inverse computation, use extended Euclidean algorithm given in Algorithm 5.2 of the reference book.

4. You must write and submit three independent programs – KeyGen, Encrypt, and

Decrypt.

5. You might like to write this program in a way such that it is easily adaptable to the change of underlying group. After the submission of this program, you might be asked to write another variant where the underlying group is a multiplication subgroup of a Galois Field.

6. This program is also important in the sense that you will later be given to implement state-of-the-art digital signature scheme where you can call many built-in functions from this program.

7. Proficiency of the program include representation of the public key using standard encoding scheme such as ASN.1 (See https://en.wikipedia.org/wiki/Abstract_ Syntax_Notation_One)

8. Efficiency check will include measuring KeyGen, Encrypt and Decryption

time.

9. 35 marks, out of 40, are for correctness and efficiency. The rest 5 will account for programming proficiency.