Assignment 2

Task One. Shamir Secret Sharing (2 marks) In this section, you are to design and implement (t,n) Shamirs secret sharing scheme as described in the lecture in C, C++ or Java. Your program should comprise at least the following functions (via parameters or an interactive menu): help: to display the functions available and the format of the functions (i.e., how to use them). ShareGen: to generate shares in the (t,n) Shamirs secret sharing scheme. As a hint, you should at least accept the secret, t, n and the modulus in the parameter. ShareReconstruction: to reconstruct the secret from the given shares in the (t,n) Shamirs secret sharing scheme. In this part, you need to explain your design rst in le ReportA2 SSS.pdf to explain the logic of your functions. Then, you need to implement it in SSS.cpp or SSS.java. As usual, you need to take the screen capture of the sample run of your program and put it in ReportA2 SSS.pdf as well Task Two. ElGamal Signature with SHA-1 (2 marks) In this section, you are to implement an ElGamal signature scheme, where the message will need to be rst hashed with the SHA-1 algorithm. The algorithm for SHA-1 is avaiable online, for example at: https://github.com/vog/sha1 In your report for this section, you will need to quote any algorithm where you download online and cite it accordingly, instead of stating that it is written by you. The program is divided into three parts: keygen: this part is to generate the private and public key for ElGamal algorithm and store it in a le called keyle.txt. sign: this part is to sign a text le given as an input. In this mode, the program will ask for the name of the text le, then read the private key from keyle.txt for signing. Prior to signing the le, the program will compute the hash of the le using SHA-1, then sign it to produce sig.txt. verify: this part is used to verify the signature in sig.txt for the le, using the public key from keyle.txt You need to structure your program using the possible inputs given as the parameter of the program. This part needs to be written in Java or C++. This part will need to be submitted with the le name ElGamalsign (with .cpp or .java, respectively), together with Task-2.pdf containing your report detailing how to use the program Task Five. ElGamal Algorithm and Subverted algorithm (5 marks) This task comprises four subtasks. In this task, you are to implement using C++ or Java, and you need to write your report as A2Task5.pdf 1. In the rst part of this task, you are to implement an ElGamal algorithm. The algorithm generates a random generator g, and then print all the parameters and the public key to screen. Then the program asks if you want to encrypt or decrypt. For an encryption, you need to enter a le to be encrypted, and then save the result in a cipher le, together with keyle.txt that contains all the information about the key. For a decryption, you need to enter the cipher le togehter with the keyle and you will be able to output the original plantext le. You need to also output how long does it take to conduct the process of encryption and decryption. As part of the report, report the time to encrypt/decrypt 1MB, 10MB, 100MB, 200MB, and 1GB le. (1.5 marks) 2. In the second part of this task, you are to implement a subverted version of ElGamal. In this version, the encryption algorithm does not generate a random k as part of the ciphertext generation, but rather, it will make such that some of the bits of gk (mod p) is the same as bits of the private key. To make it more explicit, let the private key of the user be u (from the rst question above). Let u[i] denote the bit i of the private key u. The subverted algorithm will output gk (mod p)[i] = u[i] where i is the output value of H(secret||m), where m is the plaintext,||denotes concatenation of the string and H denotes an MD5 hash function. You can download an implementation of MD5 algorithm from the internet and just use it directly (you will need to quote the source of the MD5 code). As per the rst task, you need to report the time encrypt/decrypt 1MB, 10MB, 100MB, 200MB, and 1GB le. (1.5 marks) 3. Conduct an experiment to show how many times we need to encrypt messages to that the whole secret key will be revealed to the attacker in step (2) above. Present your ndings in the report and show exactly the sequence of messages that have been used. (1 mark) 4. Suppose you receive the program either from task 1 or task 2 as a blackbox, is there a way to add another program that reads the output of the resulting ciphertext and produce a new ciphertext which will still be decryptable by the original program? Justify your answer.