This program uses more of a pseudo rainbow table approach since I am not asking you to incorporate a reducing function. Also, we will only consider passwords of exactly length 4 that use only lowercase letters (in reality, not a good hashing function at all!!). The relatively simple hashing algorithm is based on a power of 29. That is, for any given valid password, the algorithm is as follows:

hashValue = (16^3 * character at position 0) + (16^2 * character at position 1) + (16^1 * character at position 2) + (16^0 * character at position 3)

The key-value pair is then To incorporate this key-value pair, first compute every possible hash for each 4- letter character combination aaaa to zzzz.

Instructions: Step 1: Download the program 5 starting files and unzip. Open PasswordMap, which is a class that instantiates 1 key - value pair (i.e., ).

Step 2: Open the driver. This Java class is provided for you to test your HashMap class. Notice that the methods you are asked to implement in HashMap.java are invoked in this class. Although the driver does not catch these errors, be sure to check for invalid lengths, invalid characters, and hash codes not found in HashMap. In all cases, throw and InvalidPasswordException.

Step 3: Open HashMap. Scroll down until you find the TODO stub for the compute method. Within this method, compute all combinations (i.e., ). These values should be stored in rainbow.

Step 4: Implement hash by accepting a plaintext password and retrieving from rainbow, the corresponding hash. To get credit for these unit tests, you MUST retrieve from the rainbow table. You may NOT simply re-compute the hash value.

Step 5: Implement hack by accepting the hash value for the password and retrieving the corresponding plaintext password. Again, to get credit for these unit tests, you MUST retrieve from the rainbow table. You may NOT otherwise mathematically determine the password.

Step 6: Finally, say you get ahold of a file from a credit card company, creditCard Five.txt, containing usernames and hashed passwords from clientele. Open this file and, using your HashMap, crack the passwords (see Sample Outputthis gives the usernames, the plaintext password, and the hashed password).

Step 7: Verify that your files correctly run with the Junit tests. 9 tests are given but 20 tests will be used to verify your file.

Sample Output for Driver: Found hashed password: 3036062 Hash 2624641 is the password help aaaa: 2450220 Generated Passwords: tiodjksb,sbpc,2890500 lggho vsj,ckex,2507547 ufkixemd,qili,2847499 kurovpqo,xhla,3017373 liqwsxsi,fuiq,2589233

passwordMap.java: public class PasswordMap { private Long hash; private String password; public PasswordMap(Long hash, String password) { this.hash = hash; this.password = password; } public PasswordMap(String password) { this.hash = 0L; this.password = password; } public Long getHash() { return hash; } public void setHash(Long hash) { this.hash = hash; } public String getPassword() { return password; } public void setPassword(String password) { this.password = password; } }

InvalidPasswordException.java

public class InvalidPasswordException extends RuntimeException { /** * Sets up this exception with an appropriate message. * @param collection the name of the collection */ public InvalidPasswordException() { super("The entered password is invalid"); }

}

HashMapTest.java

import static org.junit.Assert.*;

import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;

import org.junit.Test;

public class HashMapTest { @Test public void testhashCode1() { HashMap evaluator = new HashMap(); Long result = evaluator.hashCode("aaaa"); assertTrue(result == 2450220); } @Test(expected=InvalidPasswordException.class) public void testhashCode6() { HashMap evaluator = new HashMap(""); fail("InvalidPasswordException not caught"); } @Test(expected=InvalidPasswordException.class) public void testhashCode7() { HashMap evaluator = new HashMap("aaa!"); fail("InvalidPasswordException not caught"); }

@Test public void testhash2() { HashMap evaluator = new HashMap("zzzz"); Long result = evaluator.hash("zzzz"); assertTrue(result == 3081720); }

@Test(expected=InvalidPasswordException.class) public void testhash5() { HashMap evaluator = new HashMap(); Long result = evaluator.hash("mmm"); fail("InvalidPasswordException not caught"); } @Test(expected=InvalidPasswordException.class) public void testhash6() { HashMap evaluator = new HashMap(); Long result = evaluator.hash("zzzzz"); fail("InvalidPasswordException not caught"); } @Test public void testhack2() { HashMap evaluator = new HashMap(); assertEquals("hard", evaluator.hack(2621439L)); }

@Test(expected=InvalidPasswordException.class) public void testhack4() { HashMap evaluator = new HashMap(); String result = evaluator.hack(30360622L); fail("InvalidPasswordException not caught");

} @Test public void testfile1() throws FileNotFoundException { HashMap evaluator = new HashMap(); String hashedPasswords = ""; String [] oneLine; Scanner in = new Scanner(new File("creditCardFive.txt")); while(in.hasNext()){ oneLine = in.next().split(","); hashedPasswords += evaluator.hack(Long.parseLong(oneLine[2])) + " "; } assertEquals("sbpc ckex qili xhla fuiq ", hashedPasswords); }

}

HashMapADT.java

public interface HashMapADT { public void compute(); public Long hash(String pwd); public String hack(Long pwdHash); }

HashMap.java

import java.util.*; public class HashMap implements HashMapADT{ private String password; private Long hash; private int key; private final int passwordLength = 4; ArrayList> rainbow; public HashMap() { password = ""; hash = -1L; key = -1; initializeHashMap(); } public HashMap(String str) { password = str; hash = hashCode(str); key = (int)(hash % 29); initializeHashMap(); } private void initializeHashMap() { //Initialize an ArrayList of 29 elements - when dividing by 29 only remainders 0 - 28 are possible rainbow = new ArrayList<>(); for(int i = 0; i < 29; i++) { rainbow.add(new ArrayList()); } compute(); } public Long hashCode(String str) throws InvalidPasswordException{ this.hash = 0L; //TODO: Calculate hashCode using hashing function based on powers of 29 return 0L; // temp - delete once hashCode method is implemented. } public void compute() { //TODO: Add code to compute all possible 4-letter passwords - store in rainbow // Begin your possible passwords with aaaa and end with zzzz // Use hashCode(pwd) % 29 to determine the key (index) of where this element should be added to rainbow's ArrayList of ArrayLists // You will need to cast as int, such as key = (int) hashCode(pwd)%29 - key is the index of where to add this element in the rainbow ArrayList of ArrayLists

} public Long hash(String pwd) { //TODO: Return the hashcode for a given password // First, hash the password: int key = (int)(hashCode(pwd) % 29); // Use this key to determine which element in the rainbow table you should be traversing to find the hash code // Recall rainbow is an ArrayList of ArrayLists!! return 0L; // temp - delete once hash method is implemented.

} public String hack(Long pwdHash) { String pwd=""; //TODO: Given a hashed password, pwdHash, determine the password // When identifying a correct hashed password, you will need to look at a difference RATHER THAN == // That is, //if (Math.abs(pwdHash - rainbow.get(key).get(i).getHash())<.001) - you've found your password!! // Note: key is the location of the rainbow list you should be traversing: key = (int)((pwdHash) % 29);

return pwd; } @Override public String toString() { return password + ": " + hash; } }

Driver.java

import java.util.ArrayList;

public class Driver {

public static void main(String[] args) { HashMap hash1 = new HashMap(); Long pwdHash = hash1.hash("yarn"); System.out.println("Found hashed password: " + pwdHash); String pwd = hash1.hack((long)2624641); System.out.println(" Hash 2624641 is the password " + pwd); HashMap hash2 = new HashMap("aaaa"); System.out.println(hash2);

}

}

creditCardFive.txt

tiodjksb,sbpc,2890500 lgghovsj,ckex,2507547 ufkixemd,qili,2847499 kurovpqo,xhla,3017373 liqwsxsi,fuiq,2589233

letter_frequency.txt

20.152 a 6.5336 b 1.1936 c 2.2256 d 3.4024 e 10.1616 f 1.7824 g 1.612 h 4.8752 i 5.5728 j 0.01224 k 0.576 l 3.22 m 1.9248 n 5.3992 o 6.0056 p 1.5432 q 0.076 r 4.7896 s 5.0616 t 7.2448 u 2.2064 v 0.7824 w 1.888 x 0.12 y 1.5792 z 0.0592