Description

5/5 - (2 votes)

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]

–  Choose a g ∈ Z∗   such that  < g >= QR .

 

q

–  Choose a number

q

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

 

–  Compute

h = ga mod q. [See Note 2]

 

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

 

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

 

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

–  Compute  C1  = gr  mod q

–  Compute  C2  = (hr × m) mod q

–  Output, ciphertext  C = (C1, C2)

  • Decrypt: To decryt  a ciphertext  C = (C1, C2 ) under the secret SK = a, this algorithm  proceeds as follows:

–  Compute  t1 = (C1)a mod q.

1

–  Compute  t2 = (C2  × t−1) mod q [See Note 3]

 

–  Output decrypted  message as

t2 .

 

 

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.

  1. 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.

 

  1. 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.
  2. 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)
  3. Efficiency check will include measuring KeyGen, Encrypt and Decryption

time.

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