$ ./Rainbow Passwords.txt where the file Passwords.txt contains a list of possible passwords. The password file contains a password per line, as in the provided words file and consists of strings of printable characters. Any password used must be taken from this file, so the only stored hash information needs to relate to those entries in the file. The program is used to find pre-images for given hash values. Rainbow tables can be used to solve pre-image problems for hash functions. At the simplest level they can simply be a list of hash values and the corresponding pre-images, often from some dictionary. This can be expensive in terms of storage space however, and a more efficient way of identifying pre-images involves the use of the hash function and reduction functions. : Your program will do some initial computations to generate the rainbow table. First step The process is as follows: 1. Read in the list of possible passwords. Report on the number of words read in. 2. For each previously unused word W, first mark it as used and then carry out the following process (a) Apply the hash function H to the word W to produce a hash value H(W), which we refer to as the current hash. (b) Apply the reduction function R to the current hash, which will give a different possible password which should be marked as used and then hashed. The resulting hash value is recorded as the current hash. (c) Repeat the previous step four times. You can deal with collisions if you like but are not required to. (d) Store the original word W and the final current hash as an entry in your rainbow table. 3. To assist with the later identification of the pre-images you should sort the rainbow table based on the hash values 4. Output the list of words and corresponding "final current hashes" to a text file Rainbow.txt. Report to standard out the number of lines in your rainbow table Second Step : You are now ready to carry out the second part of the exercise, finding pre- images. Request a hash value from the user. There should be appropriate error checking as to the length of the input string etc. The process of identifying the pre-image for the provided hash value is sketched as follows: 1. Check if the hash value is in the rainbow table