Task 1. Cryptanalysis

Let 𝐸𝑛𝑐 be an encryption algorithm based on a one-way function 𝐹 , and 𝑟 a shared secret key between the sender and the receiver. 𝐸𝑛𝑐 works as follows:

1. Compute 𝐾 = 𝐹(𝑟)||𝐹(2𝑟)||𝐹(3𝑟)||𝐹(4𝑟)||.. ;

2. For a message 𝑀, the ciphertext is computed as 𝑀⨁𝐾 (i.e., one-time pad).

Assume that an eavesdropper knows the function 𝐹 but does not know the secret key 𝑟.

a) Suppose 𝐹 is defined as 𝐹(𝑥) = 𝑔 𝑥 𝑚𝑜𝑑 𝑝 where p is a 1024-bit prime number and 𝑔 is a generator of 𝑍𝑝∗ . Assume that the discrete logarithm problem cannot be solved in the group 𝑍𝑝 ∗ . The secret key 𝑟 is chosen randomly from 𝑍𝑝−1 . Show that the eavesdropper can decrypt the whole message easily once after obtaining 𝑔, 𝑝, and the first 1024 bits of the plaintext-ciphertext pair.

b) Suppose 𝐹 is an RSA function, that is 𝐹(𝑥) = 𝑥 𝑒 𝑚𝑜𝑑 𝑛 where n is 1024-bit long. Assume the RSA problem cannot be solved in the group 𝑍𝑛 ∗, and r is chosen randomly from 𝑍𝑛 ∗ . Show that the eavesdropper can decrypt the
message easily once after obtaining n, e, and the first 1024 bits of the plaintext-ciphertext pair.

Task 2. Shamir Secret Sharing

In this section, you are to design and implement (t, n) Shamir’s secret sharing scheme as described in the lecture in C++, Java or Python. Your program should be called SSS.cpp, SSS.java, or SSS.py and it comprises at least the following functionalities:

• Share Generation: to generate shares in the (t, n) Shamir’s secret sharing scheme. As a hint, you should at least accept the secret, t, n and the modulus in the parameter.

• Share Reconstruction: to reconstruct the secret from the given shares in the (t, n) Shamir’s secret sharing scheme.

In this part, you need to explain your design first in file Task2.pdf to explain the logic of your functions. As usual, you need to take the screen capture of the sample run of your program and put it in Task2.pdf as well.

Task 3. ElGamal Signature with SHA-1

In this section, you are to implement an ElGamal signature scheme, where the message will need to be first hashed with the SHA-1 algorithm. The algorithm for SHA-1 is available online, for example at:

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 file called 𝑘𝑒𝑦𝑓𝑖𝑙𝑒.𝑡𝑥𝑡.

• Sign: this part is to sign a text file given as an input. In this mode, the program will ask for the name of the text file, then read the private key from 𝑘𝑒𝑦𝑓𝑖𝑙𝑒.𝑡𝑥𝑡 for signing. Prior to signing the file, the program will compute the hash of the file using SHA-1, then sign it to produce 𝑠𝑖𝑔.𝑡𝑥𝑡.

• Verify: this part is used to verify the signature in 𝑠𝑖𝑔.𝑡𝑥𝑡 for the file, using the public key from 𝑘𝑒𝑦𝑓𝑖𝑙𝑒.𝑡𝑥𝑡.

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, C++, or Python. This part will need to be submitted with the filename ElGamalsign (with .cpp, or java, or py respectively), together with Task3.pdf containing your report detailing how to use the program.

Task 4. Design of One-Time Signature Schemes

A fail-stop signature scheme provides some extra protection to the system. An the unbounded adversary is an adversary who can solve a computationally hard problem, such as discrete logarithm problem and factorization problem.
Please refer to the following scheme:

Key Generation

Public Key:
𝑦1 = 𝑔 𝑎1𝑦 𝑎2 (𝑚𝑜𝑑 𝑝)
𝑦2 = 𝑔 𝑏1𝑦 𝑏2 (𝑚𝑜𝑑 𝑝)

𝑔 denotes a generator of 𝑍𝑝

∗ and 𝑦 is a random element from 𝑍𝑝
∗. The private key is (𝑎1,𝑎2, 𝑏1,𝑏2).

Signing

𝜎1 = 𝑎1𝑚 + 𝑏1  (𝑚𝑜𝑑 𝑞)
𝜎2 = 𝑎2𝑚 + 𝑏2 (𝑚𝑜𝑑 𝑞)
where 𝑞|𝑝 − 1. The signature on 𝑚 is (𝜎1,𝜎2).

The notation 𝑞|𝑝 − 1 means that 𝑞 is a multiple of 𝑝 − 1.

Verification

To verify (𝑚,𝜎1, 𝜎2 ), one does the following.
𝑦1 𝑚𝑦2 𝑔 𝜎1 =? 𝑦 𝜎2 (𝑚𝑜𝑑 𝑝).

If the equation holds, then the signature is accepted. Otherwise, the signature is rejected.

Write a C++, Java or Python program to accomplish the task. You need to take the screen capture of the sample run of your program and put it in a file named
Task4.pdf. You need to submit both your source code and the report (Task4.pdf).

5 Task 5. Implementing Ring Signature of 2 users

In this task, you are to implement a ring signature for 2 users, as described in the lecture notes. The input files are the following:
• publickey.txt
• message.txt
The file publickey.txt has four lines, which indicates: 𝑒1 ,𝑛1 ,𝑒2 ,𝑛2 from RSA algorithm. The message.txt contains a string of characters, which needs to be signed. You need to implement two programs: sign and verify. The sign program will sign the message (from message.txt) and read the public keys from publickey.txt. It will ask for one input, which is user 1 or user 2, who is the signer, and the program will ask for that user’s private key. Then, the sign program will output signature.txt.

The verify program will take an input of publickey.txt, message.txt and signature.txt and it will output True or False to show the verification of the ring signature.

The symmetric encryption should use the AES algorithm. You can import the AES algorithm from the existing library or use any implementation of AES algorithm (with 10 rounds) to do this.

You may implement you program using C++, Java, or Python. You need to take the screen capture of the sample run of your program and put it in a file named
Task5.pdf. You need to submit both your source code and the report (Task5.pdf).

6 Task 6. Various Questions

Answer the following questions. You do not need to implement any program for these tasks. These tasks are pen-and-paper exercises. Please show all your workings for Task 6.1 to 6.4. Answers without showing the workings, receive no mark.

1. Assume that the size of message space (domain) for a given hash function is 2 50. Also, assume that we want the chance of the adversary finding a collision to be at most 2 −30. What is the size of the hash (in bits) required?

2. Sign and verify the message 𝑚 = 11 using the RSA signature when 𝑝 = 59, 𝑞 = 47, and 𝑒 = 15.

3. Demonstrate that the RSA signature with the parameters given in Q2 is forgeable under chosen message attack with two messages 𝑚1 = 2 and 𝑚2 = 3.

4. Adam and Bob share the same modulus 𝑛 = 21 for RSA, and encryption exponents 𝑒𝑎 = 5 and 𝑒𝑏 = 4 with 𝑔𝑐𝑑(𝑒𝑎,𝑒𝑏 ) = 1 . Charlie sends them the same message 𝑚 encrypted with 𝑒𝑎 and 𝑒𝑏 respectively, resulting in the ciphertexts 𝑐𝑎 = 14 and 𝑐𝑏 = 7. Eve intercepts both 𝑐𝑎 and 𝑐𝑏 , and applies a common modulus attack to recover the message 𝑚. What is the message 𝑚?

Write your answer in a file called Task6.pdf. You need to show all the key steps in order to obtain full marks. Submit Task6.pdf together with the other tasks in this assignment to Moodle.