Assignment Overview:

Aim: To gain a basic familiarity with public-key cryptography and its applications.

Task 1. Simplified Hash Functions

SHA-1 (or SHA1) is a hash function that produces 160-bit digest (output). You can download the source code for SHA-1 from the web, but you need to state where you get the original code from. As an example, see this github: https://github.com/clibs/sha1

We learned in the lecture that a good hash function should be collision-resistant, meaning that it is difficult to find two messages, m, and m0 such that H(m) = H(m0). In this task, we want to see how easy it is to find a collision if we use a hash function whose output size is small. So, we assume a simplified version of SHA-1, named SSHA-1. SSHA-1 is simply a hash function that outputs the last 24 bits of SHA-1 when hashing a message.

Your task is to find a pair of integers (x, x0) such that x 6= x0 but the SSHA-1 hash values of the following two messages are the same.

m = The Cat-In-The-Hat owes [FIRSTNAME] x dollars
m0 = The Cat-In-The-Hat owes [FIRSTNAME] x0 dollars

Here, [FIRSTNAME] represents your first name. (In other words, you need to find two integers x and x0 that make SSH1(m) = SSH1(m0). Your program should output the two messages, their hash values (should be the same), and the number of trials your program has made before it finds the collision. You need to write a C++ or Java program for this, and you must also submit your program with a clear readme.txt file.

Task 2. Diffie-Hellman Key Exchange

In these questions, your task is to implement the Diffie-Hellman key exchange protocol based on the prime-order subgroup using Java or C++. To accomplish this task, you must generate two prime numbers p and q such that p = 2q + 1. (That is, p is a safe prime.) You also need to calculate a generator g such that g = h2 (mod p), where h is any number between 2 and p − 2. After you have generated p, q, and g, pick a random number between 1 and q − 1 and regard it as Alices private key. Then, calculate Alices public key yA = ga (mod p)
Similarly, pick another random number b between 1 and q − 1 and regard it as
Bobs private key. Then, calculate Bobs public key yB = gb(mod p).

After you have calculated Alice and Bobs public keys, show how Alice and Bob can calculate the common Diffie-Hellman key.

Specifically, your program MUST satisfy the following:

1. The size of q must be 100 bits.
2. The values of p, q, and g must be displayed on the screen.
3. Alice and Bobs public keys must be displayed on the screen.
4. The calculation of the Diffie-Hellman key by Alice and Bob must be displayed on the screen separately. For example, “Alice will calculate the Diffie-Hellman key as follows: y Bˆa =…” and “Bob will calculate the Diffie-Hellman key as follows: y Aˆb =…” 2

Your program should handle any possible errors. Write a readme.txt file to accompany this task.

Task 3. ElGamal Encryption

In this task, you are to implement an ElGamal algorithm with C++ or Java. The algorithm generates a random generator g, and then print all the parameters and the public key to the screen. Then the program asks if you want to encrypt or decrypt. For encryption, you need to enter a file to be encrypted, and then save the result in a cipher file, together with keyfile.txt that contains all the information about the key. For decryption, you need to enter the cipher file together with the key file and you will be able to output the original plaintext file. 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 file. Submit your report as report.txt together with your source code and readme.txt.

Task 4. RSA Algorithm

Consider the RSA encryption algorithm with p = 59, q = 47, e = 15.
1. What is the public key?
2. What is the private key?
3. Implement the RSA signature using C++ or Java. Below are components that need to be implemented.
1. KeyGen: The RSA key generations function.
2. Sign: The RSA signing function.
3. Verify The RSA verification function.

The key generation function (KeyGen) should take the bit-length (up to 32) of p and q as input, and output the public key (N, e) and the corresponding private key (N, p, q, d) into two separate files pk.txt and sk.txt respectively, where p, q are distinct primer numbers, N = p ∗ q (i.e., N is up to 64 bits), d ∗ e = 1mod((p − 1) ∗ (q − 1)).

The signing function (Sign) should take the private (secret) key from sk.txt and a message M (a positive integer smaller than N) from a file mssg.txt as input, and output the corresponding signature S = Md (mod N) into another file sig.txt.
The verification function (Verify) should take the public key from pk.txt and a signature S (a positive integer smaller than N) from sig.txt and the message M as input, and output (display) the verification result “True” or “False” on the screen (terminal). When your program is executed, a menu with these three functions should be displayed and a user can choose to invoke any of these functions multiple times.

Important: the key generation function should be probabilistic. That is, the output of the key generation function should be different even if the same bit-length for p and q is chosen.

For all the implemented functions, please do the necessary validation.

4. Encrypt the plaintext m = 10 with your program, and also do by hand. Compare the result.

5. Decrypt the resulting result with your program and compare it with your manual calculation.

Task 5. Implementation of Trapdoor Knapsack Encryption Scheme

In this section, you are to implement a trapdoor knapsack encryption scheme. When the program is run, it first asks for the size of the super-increasing knapsack, then the user is asked to enter the value of each ai in the private key, each separated with space. Then, the user is asked to enter a modulus, follows by a multiplier. You will need to check whether the condition of the multiplier is satisfied. Then, the public key will be generated and shown. Now, a set of messages is being asked, and the ciphertext will need to be displayed.

Finally, a ciphertext will need to be asked and the correct decryption of the ciphertext will need to be displayed. Implement this part as knapsack.cpp or knapsack.java

Task 6. Various Questions

Answer the following questions. 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 the message space (domain) for a given hash function is 250. 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 m = 5 using the RSA signature when p = 3, q = 11, e = 7.

3. Demonstrate that the RSA signature with the parameters given in Q2 is forge- able under chosen message attack with two messages m1 = 2 and m2 = 3.

4. Sign and verify the message m = 3 using the ElGamal signature when p = 23, g = 2 and x = 7.