先说几个概念
1、Hash。
一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。也就是hash是一种（可能）多对一的关系。
哈希（Hash）算法就是单向散列算法，它把某个较大的集合P映射到另一个较小的集合Q中，假如这个算法叫H，那么就有Q = H（P）。对于P中任何一个值p都有唯一确定的q与之对应，但是一个q可以对应多个p。作为一个有用的Hash算法，H还应该满足：H(p)速度比较快；给出一个q，很难算出一个p满足q = H(p)；给出一个p1，很难算出一个不等于p1的p2使得
H(p1)=H(p2)。正因为有这样的特性，Hash算法经常被用来保存密码————这样不会泄露密码明文，又可以校验输入的密码是否正确。常用的Hash算法有MD5、SHA1等。
2、MD5。
Message Digest Algorithm MD5（中文名为消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。MD5是hash算法的一种，是一种哈希函数。
MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。例如：我们常常在某些软件下载站点的某软件信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用专门的软件（如Windows MD5 Check等）做一次MD5校验，以确保我们获得的文件与该站点提供的文件为同一文件。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。
3、彩虹表
彩虹表就是一个庞大的、针对各种可能的字母组合预先计算好的哈希值的集合，不一定是针对MD5算法的，各种算法的都有，有了它可以快速的破解各类密码。越是复杂的密码，需要的彩虹表就越大，现在主流的彩虹表都是100G以上。
简单的说就是针对特定算法，尤其是不对称算法进行有效破解的一种方法（如 md5算法）。他的过程 就是建立一个 源数据与加密数据之间对应的hash表。这样在获得加密数据后 通过比较，查询或者一定的运算，可以快速定位源数据。理论上，如果不考虑查询所需要的时间的话，hash 表越大，破解也就越有效越迅速。当然对于其它破解方法（如碰撞）此方法比较笨拙，对于可变长密钥等现代高级算法，效果会大打折扣。但是无论怎样， 彩虹表（hash）永远是在数据加解密中是无奈但十分有效的方法。
以上的知识建议大家去网上搜一下，比这里详细得多。工欲善其事，必先利其器～
好了，现在进入正题。
之所以接触这个问题，是由于一个朋友，他提供了一个题目，如下：
The following hashes correspond to 3 character plain text words generated by the hash function hash.java
attached to this program. Implement any method you want to decode the following hashes, in a single class
called Decoder.java. Please submit the hash and the decoded 3 character string as your answer, and submit
your Decoder.java le on the learn.bu.edu HW 4 folder.
b*4&r<:b*|(24x26
66 ,8n<." fpfnj>
<pf"|r x("8f|>ld
dnf (x:rt8( ,f6t
:f*n&>~2z 8zl> 6
`<z6">:tb~vfx*v
x&*>t:.r<<:<d$2n
z|j*r4*&xhfpjndb
x&rj&4r~f,*x~xht
"~0"rvx~xjlx ldh
我拿到后到网上搜索了一下，看完相关的知识之后我的思路就被网上的思路局限了。也就是：下载一个彩虹表，然后用破解工具破解。但是这么一来就不是java的事情了。昨天晚上想了很久，也搜索了很多相关资料。但是还是没有头绪。
结果今天上课，讨论课，我就开小差了。由于相关的东西已经比较多了，再看下去也是没有用的。于是我回到题目本身。突然有了想法。既然是三个字符的纯文本，那么何不自己生成一个彩虹表。一想好像可行，因为英文字母就52（大小写）个，三个字符的话是52*52*52=174928个，不是很大，可以实现。思路如下：
先生成所有三个字符的字母组合，共174928个。然后用MD5算法生成hash码，并按给出的协议进行那个转换；转换完之后与给出的hash码进行比较。如果相同就输出对应的源码。思路非常简单，下面来实现。
先生成彩虹表，然后写出解码成功后的输出函数。代码如下：
public class HashDecode {
/**
* get rainbow table of 3 character plain text words
* @return the possible words uncoded
*/
public static List<String> getMyRainbowTable(){
List<String> rainbowTable = new ArrayList<String>();
byte[] temp = new byte[3];
//a--z || A--Z
for (int i = 65; i <= 122; i++) {
for (int j = 65; j <= 122; j++) {
for (int j2 = 65; j2 <= 122; j2++) {
if(i >= 91 && i <= 96){
continue;
}
temp[0] = (byte) i;
temp[1] = (byte) j;
temp[2] = (byte) j2;
rainbowTable.add(new String(temp));
}
}
}
return rainbowTable;
}
/**
* find out the prototype of the given hashs
* @param words the possible words unchanged
* @param hashs coded words using md5
*/
public static void decode(List<String> words, String[] hashs) {
for (String word : words) {
for (int j = 0; j < hashs.length; j++) {
if(Hash.compact(word).equals(hashs[j])){
System.out.println(word + " is the prototype of the hash " + hashs[j]);
}
}
}
}
}
然后是生成hash码和进行下一步转换（双方一样）的代码。如下:
class Hash {
/**
* Converts an array of bytes into a readable set of characters in the range ! through ~
* @param bytes The array of bytes
* @return A string with characters in the range ! through ~
*/
public static String makeReadable(byte[] bytes) {
for (int ii=0; ii<bytes.length; ii++) {
bytes[ii]=(byte) ((bytes[ii] & 0x5E)+32); // Convert to character ! through ~
}
return new String(bytes);
}
/**
* produce a hash of a given string
* @param str The string to hash
* @return Returns a collection of sixteen "readable" characters (! through ~) corresponding to this string.
*/
public static String compact(String str) {
// setup the digest
MessageDigest md = null;
str += "foo"; // random text added to the string
try {
md = MessageDigest.getInstance("MD5");
md.update(str.getBytes());
} catch (NoSuchAlgorithmException e) {
System.err.println("Hash digest format not known!");
System.exit(-1);
}
return makeReadable(md.digest());
}
}
最后进行测试：
找出了源码，是几个单词。代码及显示如下：
<pre name="code" class="java"><span style="font-size:14px;">public class Main {
/*
* the hashs
*/
private static String[] hashs = new String[]{
"b*4&r<:b*|(24x26",//ok
"66 ,8n<.\" fpfnj>",//ok
"<pf\"|r x(\"8f|>ld",//ok
"z|j*r4*&xhfpjndb",//ok
"dnf (x:rt8( ,f6t",//ok
":f*n&>~2z 8zl> 6",//ok
" `<z6\">:tb~vfx*v",//ok
"x&*>t:.r<<:<d$2n",//ok
"x&rj&4r~f,*x~xht",//ok
"\"~0\"rvx~xjlx ldh"//ok
};
public static void main(String[] args) {
System.out.println(HashDecode.getMyRainbowTable().size());
//System.out.println(Hash.compact("mad"));
HashDecode.decode(HashDecode.getMyRainbowTable(), hashs);
}
}
</span><pre name="code" class="java">Cat is the prototype of the hash 66 ,8n<." fpfnj>
DAC is the prototype of the hash b*4&r<:b*|(24x26
Hat is the prototype of the hash <pf"|r x("8f|>ld
Let is the prototype of the hash z|j*r4*&xhfpjndb
bat is the prototype of the hash dnf (x:rt8( ,f6t
bed is the prototype of the hash :f*n&>~2z 8zl> 6
get is the prototype of the hash "~0"rvx~xjlx ldh
mat is the prototype of the hash `<z6">:tb~vfx*v
met is the prototype of the hash x&*>t:.r<<:<d$2n
wet is the prototype of the hash x&rj&4r~f,*x~xht
最后想总结的是。当拿到一个东西感觉无从下手，很困难的时候不妨从最初的地方开始思考。因为可能一开始就出现了偏差。
另一个就是要自信，很多东西别人可以搞出来，自己肯下功夫，肯学习。，就一定能搞出来。