哈希竞猜游戏开发（系统）丨哈希竞猜游戏系统开发（案例源码说明）

　哈希算法就是把任意长度的输入变换成固定长度的输出，每个字节都会对输出值产生影响，且无法通过输出逆向计算得到输入。

　　哈希算法主要包含构造函数及冲突解决两部分内容。

　　哈希算法的构造函数准则较为简单、均匀，即构造函数能够快速地计算出哈希值，同时构造函数能将关键字集合均匀地分布在输出地址集{0，1，…，n-1}上，保证冲突的可能性最小。

　　常见的构造方法包括：直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等。

　　直接定址法非常简单，通过线性函数（y=ax+b）构造哈希值，该算法输出和输入长度相等，因此实际中很少单独使用该算法。

　　数字分析法是取数据中某些取值较为均匀的位，丢掉分布不均匀的位，一次计算出哈希值。

　　例如使用数字分析法计算当前员工生日的哈希时，出生年份即为丢掉的分布不均匀的数据，月份日期用来构成哈希值。

　　平方取中法即求输入的平方，然后取中间几位作为哈希值。

　　除上述所列，构造函数还有很多种，在此不一一介绍。

　　当然，实际运用中的各种成熟的哈希算法库都是组合使用各种基本构造函数，从而消除哈希值输出的规律性，满足不可逆等特性。

　　由于输入无限而输出有限，哈希冲突（碰撞）是不可避免的，因此解决冲突是哈希法的另一个关键问题。

　　解决冲突的方法包含开放定址法、再哈希法、链地址法等。

　　开放定址法即在散列表中形成一个探测序列，当发生了冲突时，去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。

　　再哈希法很好理解，即产生冲突时，使用另一种算法生成下一个哈希值，该方法虽然不容易产生聚集，但是增加了计算时间。

　　链地址法即哈希值产生冲突时，多个哈希构成一个链表。解决冲突的方法还有很多，有兴趣的小伙伴可自行百度。

　　1.MD算法

　　当前已经提出并被广泛使用的算法包括消息摘要算法（Message-DigestAlgorithm,MD）系列和安全散列算法（Secure Hash Algorithm,SHA）家族。

　　MD系列主要由MIT的Ronald L.Rivest设计，1989年开发出第一个版本MD2算法，对输入值的字节数补齐成16的倍数，然后再加上一个16位校验值，最后基于该值输出哈希值。但是该方法如果忽略了校验将会产生冲突。

　　为了加强算法的安全性，在1990年推出MD4版本。

　　但是人们很快就发现了MD4的漏洞，利用当时的一台个人电脑几分钟就可找到MD4中的冲突，即发生碰撞。

　　1991年在MD4的基础上，又增加“安全—带子”（Safety-belts）的概念，推出MD5版本。

　　MD5相比MD4更复杂、更安全，也因此计算速度稍慢。

　　MD5在很长一段时间内被广泛使用，当前主流的编程语言均实现了MD5算法。

　　但是，现在MD5也被证明不具备“强抗碰撞性”。

　　只要通过穷举的方法，很快就可以找到一组碰撞的输入。

　　由于计算性能的飞跃提升，当前的智能手机几秒钟就可以找到一个hash碰撞的例子，所以MD5已经不推荐作为散列方案。

　　因此不再详细介绍MD5的计算过程。

　　2.SHA算法

　　SHA家族包含SHA-0、SHA-1、SHA-2等，由美国国家安全局（NSA）设计，并由美国国家标准与技术研究院（NIST）发布。

　　SHA-0于1993年发布，但是发布之后很快被NSA撤回。

　　1995年发布修订版SHA-1，修复一个在SHA-0中会降低杂凑安全性的缺点。

　　SHA-0和SHA-1的基本原理与MD算法相似。

　　SHA-0已经被攻破，SHA-1目前也已经被证明不具备“强抗碰撞性”。

　　SHA-2又可分为SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256六种不同的算法，这些算法基本结构一致，仅仅在生成的哈希值长度和循环运行次数方面存在细微的差异。

　　SHA-2算法需经过补位、增加长度、取常量、迭代计算等几步操作，此处以SHA-256为例说明。

　　首先将随机长度的输入值补位直到满足要求，即需要这个长度对512取余后的余数为448（512-64）。

　　即使输入刚好满足要求，也要进行一次补位操作。

　　补位的规则也很简单，第一位补“1”，然后补“0”，直到长度满足要求。

　　完成补位操作后，需再添加64位的长度信息，这就是为什么第一步补位是需要余数为448。

　　如果消息长度大于264，我们需要把长度分成512位的块，然后进行补位和添加长度的操作。

　　SHA算法在计算哈希值时，需要用到一个计算常量，在SHA-256中包含64个基础常量，这些常量是自然数中前64个质数的立方根的小数部分取前32比特而来，具体值不在此列出。

　　在迭代计算时，SHA-2采用6个基本逻辑函数，每个函数均基于32位字运算，同样地，这些函数的计算结果也是一个32位字。

　　密码学哈希算法的主要特性就是单向性，即在算法上，只能从输入值计算得到输出值，而从输出值计算得到输入值是不可行的。

　　因为哈希算法的输出值是固定长度的，所以哈希算法存在一个碰撞的问题，即哈希算法的输出值的长度为n比特，那么，任取2n+1个不同的输入值，就一定存在两个不同的输入值会得到相同的输出值。因此，在一定数量的输入值情况下，输出值越长的哈希算法，其碰撞的概率会越小。