CSCI361: Implement the RSA Signature Using C++, Java, or Python Below are the Components that Need to be Implemented: Cryptography and Secure Applications Assignment, SIM, Singapore

Task One. 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++, Java, or Python. Below are the components that need to be implemented.

i. KeyGen: The RSA key generations function.
ii. Sign: The RSA signing function.
iii. 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), de = 1 mod ((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.

1. Encrypt the plaintext m = 13 with your program, and also do it by hand. Compare the result.

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

Task Two. 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 𝑎𝑖 in the private key. 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 a knapsack.CPP, knapsack.java or knapsack.py

3 Task Three. Collision Finding of Hash Functions

SHA-1 is a commonly used hash function. It produces a 160-bit hash value. 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 learnt in the lecture that a good hash function should be collision-resistant, meaning that it is difficult to find two messages, 𝑚 and 𝑚’, where 𝑚 ≠ 𝑚′, such that 𝐻(𝑚) = 𝐻(𝑚′).

In this task, we assume a simplified version of SHA-1, named SSHA1, is used for hashing. SSHA-1 only outputs the first 36 bits of SHA-1 when hashing a message. Your task is to find a pair of integers (x, xI ) such that 𝑥 ≠ 𝑥′ but the SSHA-1 hash values of the following two messages are the same. That is, H(The Cat-In-The-Hat owes [FIRSTNAME] x dollars) = H(The Cat-In-The-Hat owes [FIRSTNAME] X dollars).

You should replace [FIRSTNAME] with your first name. Write a C++, Java or Python program to accomplish the task. 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.

4 Task Four. Digital Signatures

In this assignment, you are to implement the Digital Signature Algorithm (DSA) as described in the lecture notes. Your program needs to accept a file as an input, and it should produce sig.txt, which is a signature on the input file. You should be able to verify the input file and the signature in sig.txt and this should return True. Otherwise, return False.

Write a C++, Java or Python program to accomplish the task.

5 Task Five. Simplified Blockchain: Simulating Proof of work

In this assignment, your task is to write a simple program for simulating Proof-of-work. The assumptions on the simulation program are as follows:
1. A blockchain node wants to compute a new block using proof-of-work.
2. Hash function is obtained from an AES or TEA encryption in CBC mode, where the key is obtained from the first 128 bits of the message (which is the contents of the block). You can download the implementation of AES online, but you need to state where the source is from. The output of the hash is 128 bit, which is obtained from the final ciphertext.

3. The program simulates the Proof-of-Work is described below. below. The program for proof-of-work should perform the following:

1. The program takes at least two parameters as follows:
(a) The condition of the hash value of a new valid block (The number of leading zeros).
(b) The data newly added to the current block.

2. The program outputs a random nonce value for a new block and hashed value for the new block.