[166] | 1 | package ro.pub.cs.pp.a51hadoop.algorithm.testing; |
---|
| 2 | |
---|
| 3 | import ro.pub.cs.pp.a51hadoop.algorithm.HashReducer; |
---|
| 4 | |
---|
| 5 | |
---|
| 6 | /* A reduction function R that maps hash values back into secret values. |
---|
| 7 | * |
---|
| 8 | * There are many possible implementations for this function, and it's only |
---|
| 9 | * important that it behaves pseudorandomly. |
---|
| 10 | * |
---|
| 11 | * By alternating the hash function with the reduction function, |
---|
| 12 | * chains of alternating passwords and hash values are formed. |
---|
| 13 | * |
---|
| 14 | * |
---|
| 15 | * This reducer only changes one digit of the given string |
---|
| 16 | * (represented as a number). |
---|
| 17 | */ |
---|
| 18 | public class DigitReducer implements HashReducer |
---|
| 19 | { |
---|
| 20 | private int i; |
---|
| 21 | private int k; |
---|
| 22 | public DigitReducer(int i, int k) |
---|
| 23 | { |
---|
| 24 | this.i = i; |
---|
| 25 | this.k = k; |
---|
| 26 | } |
---|
| 27 | |
---|
| 28 | /* |
---|
| 29 | * Apply the current Reducer on the given hash. |
---|
| 30 | * |
---|
| 31 | * @return a new secret value |
---|
| 32 | */ |
---|
| 33 | public String apply(String strX) |
---|
| 34 | { |
---|
| 35 | try |
---|
| 36 | { |
---|
| 37 | int last_digit = 0; |
---|
| 38 | int x = Integer.parseInt(strX); |
---|
| 39 | |
---|
| 40 | |
---|
| 41 | /* |
---|
| 42 | * This is a limmited implementation. |
---|
| 43 | * |
---|
| 44 | * It will not give us pseudorandom strings, |
---|
| 45 | * but this will do for testing pourposes. |
---|
| 46 | */ |
---|
| 47 | switch (i) |
---|
| 48 | { |
---|
| 49 | case 0: |
---|
| 50 | last_digit = i % 3; |
---|
| 51 | break; |
---|
| 52 | case 1: |
---|
| 53 | last_digit = i % 3 + 3; |
---|
| 54 | break; |
---|
| 55 | case 2: |
---|
| 56 | last_digit = i % 3 + 6; |
---|
| 57 | break; |
---|
| 58 | default: |
---|
| 59 | last_digit = 9; |
---|
| 60 | break; |
---|
| 61 | } |
---|
| 62 | |
---|
| 63 | /* |
---|
| 64 | * Change the last digit |
---|
| 65 | */ |
---|
| 66 | x = x / 10 * 10 + last_digit; |
---|
| 67 | |
---|
| 68 | |
---|
| 69 | /* |
---|
| 70 | * This is done to look like we have many |
---|
| 71 | * distinct reducer functions. |
---|
| 72 | * |
---|
| 73 | * This is required to solve the problem of |
---|
| 74 | * collisions with ordinary hash chains by |
---|
| 75 | * replacing the single reduction function R |
---|
| 76 | * with a sequence of related reduction |
---|
| 77 | * functions R1 through Rk. |
---|
| 78 | * |
---|
| 79 | * This way, in order for two chains to |
---|
| 80 | * collide and merge, they must hit the same |
---|
| 81 | * value on the same iteration. Consequently, |
---|
| 82 | * the final values in each chain will be |
---|
| 83 | * identical. A final postprocessing pass can |
---|
| 84 | * sort the chains in the table and remove any |
---|
| 85 | * "duplicate" chains that have the same final |
---|
| 86 | * value as other chains. New chains are then |
---|
| 87 | * generated to fill out the table. These |
---|
| 88 | * chains are not collision-free (they may |
---|
| 89 | * overlap briefly) but they will not merge, |
---|
| 90 | * drastically reducing the overall number of |
---|
| 91 | * collisions |
---|
| 92 | */ |
---|
| 93 | x = x ^ k; |
---|
| 94 | |
---|
| 95 | String ret = "" + x; |
---|
| 96 | while(ret.length() < strX.length()) |
---|
| 97 | ret = "0" + ret; |
---|
| 98 | if (ret.length() > strX.length()) |
---|
| 99 | ret = ret.substring(0, strX.length()); |
---|
| 100 | return ret; |
---|
| 101 | } |
---|
| 102 | catch (Exception e) |
---|
| 103 | { |
---|
| 104 | /* |
---|
| 105 | * On error return the original unmodified |
---|
| 106 | * string. |
---|
| 107 | */ |
---|
| 108 | return strX; |
---|
| 109 | } |
---|
| 110 | } |
---|
| 111 | } |
---|