将任意长度的二进制串映射为固定长度的二进制串,这个映射规则就是 哈希算法 ,而通过原始数据映射之后得到的二进制串就是 哈希值 。 哈希算法简单的说就是一种将任意长度的消息压缩到某一固定长度的摘要的函数。
一、特点
以下讨论密码学哈希应具备的性质;用于哈希表的普通哈希函数不一定满足单向性、抗碰撞性等安全要求:
- 易压缩:对于任意大小的消息,都能计算固定长度的哈希值
- 易计算:即使给定很长的消息,也能快速地计算出哈希值
- 单向性:对于给定的哈希值,要找到原始消息是不可行的,即求哈希值的逆很困难,这是哈希算法安全的基础
- 抗碰撞性:固定长度输出必然存在碰撞;密码学要求的是在可行的计算成本内难以找到两个不同输入具有相同哈希,而不是完全没有碰撞
- 高灵敏性:对输入数据非常敏感,哪怕原始数据只修改了一点,最后得到的哈希值也大不相同
二、哈希碰撞
实际上,不管是什么哈希算法,我们只能尽量减少碰撞冲突的概率,理论上是没有办法做到完全不冲突的。根据组合数学中的鸽巢原理,哈希值的长度是固定且有限的,而要哈希的数据是无穷的,所以总有一些原始值会有到相同的哈希值。 从理论上来说,哈希值空间N越大,碰撞概率P越低,两个数据的 碰撞概率大约为P=1/N 。这里指两个独立随机输入的哈希相等的概率。寻找任意一对碰撞受生日界影响,通用攻击约需平方根 N 次尝试;而对已知哈希寻找一个原像,通用穷举约需 N 次尝试。两种问题不能混为一谈,所以如果哈希值空间很大,即便哈希算法存在冲突,但是在有限的时间和资源下,哈希算法还是很难被破解的。
三、应用
- 消息摘要与密码存储 :哈希计算不是加密,没有对应的解密操作;输出称为 消息摘要(Message Digest)。密码存储应使用带盐和适当成本参数的专用密码哈希方案,不能把普通快速哈希或 MD5 直接当作安全的密码存储方案。攻击者仍可能进行字典猜测, 其实安全和攻击是一种博弈关系,不存在绝对的安全。所有的安全措施,也只是增加攻击的成本而已 。
- 唯一标识 :对数据集( 数据量大 )中的每一个元素根据其内容计算出一个哈希值,这个哈希值可作为这个元素在数据集中的唯一标识。比如,要在庞大的图库中,搜索一张图是否存在,我们不能单纯地用图片的的名称来对比,因为有可能存在名称相同但图片内容不同,或者名称不同图片内容相同的状况,这时我们可以取图片的哈希值作为标识查找图片。
- 数据校验 :用文件(或消息)的哈希值检验文件的完整性和正确性,计算文件的哈希值和收到的哈希值进行对比,如果不一致则说明文件被篡改了。通常用于分段下载较大的文件的检验。
- 负载均衡 :对客户端IP或者会话ID计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号,这样就可以把客户端的请求平均的分配到多个服务器中。
- 数据分片 :对于海量的数据,可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度,分片方法就是把数据的哈希与机器个数取模即是机器编号。
- 哈希表 :哈希表是基于哈希函数建立的一种查找表,可以提高查找效率。把哈希值作为元素的存储地址的位置,在查找时只需计算出元素的哈希值就可以知道元素的位置,由此,不需比较便可直接取得所查元素。
- 分布式缓存(存储) :采用 一致性哈希算法 ,把哈希值空间视为一个环,再对数据和机器进行哈希并映射到这个环上,数据哈希往顺时针方向最近的机器哈希就是数据对应存储的机器。对于数据分布不均衡的情况可使用虚拟机器方式,即一个机器映射到环上多个节点。
四、哈希原理方法
- 加法 :把输入元素一个一个的加起来构成最后的结果,如additiveHash
- 位运算 :通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素,如rotatingHash
- 乘法 :利用了乘法的不相关性,直接累乘或者乘以某个数累加等,如bernstein
- 取余 :将整数哈希值对桶数取模,是把哈希值映射到桶编号的常见方法;非密码学哈希表经常使用
- 查表 :预定义一个哈希值表,把元素循环和这些预定义的哈希值进行位运算、加法元素等,如Universal
- 混合 :利用了以上各种方式,这样处理的哈希破解更难,它们一般很少在面向查找的哈希函数里面使用,如MD5
五、MD5算法实现
MD5将数据按每个512位为一组进行分组,依次对每个分组处理从而得到一个长度为128位的结果。
1、填充
- 在数据后面按位先填充一个1,再填充最少数量的0,直到数据位长满足N*512+448(N>=0)。
- 在这个结果后面附加一个64位的填充前信息长度,如果填充前信息长度超过64位,则取低64位。
经过这两步的处理,信息的位长为
N*512+448+64=(N+1)*512,即长度恰好是512的整数倍。
2、初始化变量
MD5有四个32位的被称作链接变量的整数参数,这是个参数我们定义为A、B、C、D其取值为:A=0x01234567,B=0x89abcdef,C=0xfedcba98,D=0x76543210。但考虑到大小端的问题我们将其赋值为:
A=0x67452301
B=0xefcdab89
C=0x98badcfe
D=0x10325476
同时MD5算法规定了四个辅助操作函数:
F(X,Y,Z) =(X&Y)|((~X)&Z)
G(X,Y,Z) =(X&Z)|(Y&(~Z))
H(X,Y,Z) =X^Y^Z
I(X,Y,Z)=Y^(X|(~Z))
这些函数是这样设计的:如果X、Y和Z的对应位是独立和均匀的,那么结果的每一位也应是独立和均匀的。 利用上面的四种操作,生成四个重要的计算函数。这四个计算函数为:
FF(a, b, c, d, M[j], s, Ti)表示 a = b + ((a + F(b, c, d) + M[j] + Ti) << s)
GG(a, b, c, d, M[j], s, Ti)表示 a = b + ((a + G(b, c, d) + M[j] + Ti) << s)
HH(a, b, c, d, M[j], s, Ti)表示 a = b + ((a + H(b, c, d) + M[j] + Ti) << s)
II(a, b, c, d, M[j], s, Ti)表示 a = b + ((a + I(b, c, d) + M[j] + Ti) << s)
其中M[j]表示数据的第j个子分组(从0到15),<<表示循环左移s,Ti是4294967296*abs(sin(i))的整数部分,i取值从1到64,单位是弧度。
3、处理分组数据
每个 512 位分组按小端字节序拆成 16 个 32 位字,每组只执行 64 步,四轮分别使用不同的消息索引和移位量。下面是压缩函数的 Python 表达;state 是上一分组的四个状态字,words 是当前分组的 16 个字。加法均按模 2^32 处理。
from math import sin
def md5_compress(state, words):
mask = 0xffffffff
shifts = ([7, 12, 17, 22] * 4 + [5, 9, 14, 20] * 4
+ [4, 11, 16, 23] * 4 + [6, 10, 15, 21] * 4)
constants = [int(abs(sin(i + 1)) * 2**32) for i in range(64)]
a, b, c, d = state
for i in range(64):
if i < 16:
f, g = (b & c) | (~b & d), i
elif i < 32:
f, g = (d & b) | (~d & c), (5 * i + 1) % 16
elif i < 48:
f, g = b ^ c ^ d, (3 * i + 5) % 16
else:
f, g = c ^ (b | ~d), (7 * i) % 16
value = (a + f + constants[i] + words[g]) & mask
shift = shifts[i]
rotated = ((value << shift) | (value >> (32 - shift))) & mask
a, b, c, d = d, (b + rotated) & mask, b, c
return [(old + new) & mask
for old, new in zip(state, (a, b, c, d))]
初始状态为前节列出的四个状态字;返回值继续用于下一分组。实际实现通常把 64 个常量预先保存,避免重复计算。
4、输出
最后将 A、B、C、D 分别按小端字节序编码后连接,得到 128 位摘要。
六、常见摘要算法对比
下表保留原稿整理时的对比,不应视为当前安全评估。MD5、SHA-1 不适用于要求抗碰撞性的用途;MD5 原理参见 RFC 1321,安全限制参见 RFC 6151。
| 算法名称 | 输出大小 | 内部大小 | 区块大小 | 长度大小 | 字符尺寸 | 碰撞情形 |
|---|---|---|---|---|---|---|
| MD2 | 128 | 384 | 128 | No | 8 | 大多数 |
| MD4 | 128 | 128 | 512 | 64 | 32 | 是 |
| MD5 | 128 | 128 | 512 | 64 | 32 | 是 |
| RIPEMD | 128 | 128 | 512 | 64 | 32 | 是 |
| RIPEMD-128/256 | 128/256 | 128/256 | 512 | 64 | 32 | 否 |
| RIPEMD-160/320 | 160/320 | 160/320 | 512 | 64 | 32 | 否 |
| SHA-0 | 160 | 160 | 512 | 64 | 32 | 是 |
| SHA-1 | 160 | 160 | 512 | 64 | 32 | 有缺陷 |
| SHA-256/224 | 256/224 | 256 | 512 | 64 | 32 | 否 |
| SHA-512/384 | 512/384 | 512 | 1024 | 128 | 64 | 否 |
| WHIRLPOOL | 512 | 512 | 512 | 256 | 8 | 否 |
| SM3 | 256 | 256 | 512 | 256 | 32 | 否 |
七、哈希函数源码
基本哈希函数 :
public class HashAlgorithms {
/**
* 加法hash
*/
public static int additiveHash(String key, int prime) {
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return (hash % prime);
}
/**
* 旋转hash
*/
public static int rotatingHash(String key, int prime) {
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); ++i)
hash = (hash << 4) ^ (hash >> 28) ^ key.charAt(i);
return (hash % prime);
}
static int M_MASK = 0x8765fed1;
/**
* 一次一个hash
*/
public static int oneByOneHash(String key) {
int hash, i;
for (hash = 0, i = 0; i < key.length(); ++i) {
hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
// return (hash & M_MASK);
return hash;
}
/**
* Bernstein's hash
*/
public static int bernstein(String key) {
int hash = 0;
int i;
for (i = 0; i < key.length(); ++i)
hash = 33 * hash + key.charAt(i);
return hash;
}
/**
* Universal Hashing
*/
public static int universal(char[] key, int mask, int[] tab) {
int hash = key.length, i, len = key.length;
for (i = 0; i < (len << 3); i += 8) {
char k = key[i >> 3];
if ((k & 0x01) == 0)
hash ^= tab[i + 0];
if ((k & 0x02) == 0)
hash ^= tab[i + 1];
if ((k & 0x04) == 0)
hash ^= tab[i + 2];
if ((k & 0x08) == 0)
hash ^= tab[i + 3];
if ((k & 0x10) == 0)
hash ^= tab[i + 4];
if ((k & 0x20) == 0)
hash ^= tab[i + 5];
if ((k & 0x40) == 0)
hash ^= tab[i + 6];
if ((k & 0x80) == 0)
hash ^= tab[i + 7];
}
return (hash & mask);
}
/**
* Zobrist Hashing
*/
public static int zobrist(char[] key, int mask, int[][] tab) {
int hash, i;
for (hash = key.length, i = 0; i < key.length; ++i)
hash ^= tab[i][key[i]];
return (hash & mask);
}
static int M_SHIFT = 0;
/**
* 32位的FNV算法
*/
public static int FNVHash(byte[] data) {
int hash = (int) 2166136261L;
for (byte b : data)
hash = (hash * 16777619) ^ b;
if (M_SHIFT == 0)
return hash;
return (hash ^ (hash >> M_SHIFT)) & M_MASK;
}
/**
* 改进的32位FNV算法1
*/
public static int FNVHash1(byte[] data) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (byte b : data)
hash = (hash ^ b) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
/**
* 改进的32位FNV算法1
*/
public static int FNVHash1(String data) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < data.length(); i++)
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
/**
* Thomas Wang的算法,整数hash
*/
public static int intHash(int key) {
key += ~(key << 15);
key ^= (key >>> 10);
key += (key << 3);
key ^= (key >>> 6);
key += ~(key << 11);
key ^= (key >>> 16);
return key;
}
/**
* RS算法hash
*/
public static int RSHash(String str) {
int b = 378551;
int a = 63689;
int hash = 0;
for (int i = 0; i < str.length(); i++) {
hash = hash * a + str.charAt(i);
a = a * b;
}
return (hash & 0x7FFFFFFF);
}
/**
* JS算法
*/
public static int JSHash(String str) {
int hash = 1315423911;
for (int i = 0; i < str.length(); i++) {
hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
}
return (hash & 0x7FFFFFFF);
}
/**
* PJW算法
*/
public static int PJWHash(String str) {
int BitsInUnsignedInt = 32;
int ThreeQuarters = (BitsInUnsignedInt * 3) / 4;
int OneEighth = BitsInUnsignedInt / 8;
int HighBits = 0xFFFFFFFF << (BitsInUnsignedInt - OneEighth);
int hash = 0;
int test = 0;
for (int i = 0; i < str.length(); i++) {
hash = (hash << OneEighth) + str.charAt(i);
if ((test = hash & HighBits) != 0) {
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}
return (hash & 0x7FFFFFFF);
}
/**
* ELF算法
*/
public static int ELFHash(String str) {
int hash = 0;
int x = 0;
for (int i = 0; i < str.length(); i++) {
hash = (hash << 4) + str.charAt(i);
if ((x = (int) (hash & 0xF0000000L)) != 0) {
hash ^= (x >> 24);
hash &= ~x;
}
}
return (hash & 0x7FFFFFFF);
}
/**
* BKDR算法
*/
public static int BKDRHash(String str) {
int seed = 131; // 31 131 1313 13131 131313 etc..
int hash = 0;
for (int i = 0; i < str.length(); i++) {
hash = (hash * seed) + str.charAt(i);
}
return (hash & 0x7FFFFFFF);
}
/**
* SDBM算法
*/
public static int SDBMHash(String str) {
int hash = 0;
for (int i = 0; i < str.length(); i++) {
hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
}
return (hash & 0x7FFFFFFF);
}
/**
* DJB算法
*/
public static int DJBHash(String str) {
int hash = 5381;
for (int i = 0; i < str.length(); i++) {
hash = ((hash << 5) + hash) + str.charAt(i);
}
return (hash & 0x7FFFFFFF);
}
/**
* DEK算法
*/
public static int DEKHash(String str) {
int hash = str.length();
for (int i = 0; i < str.length(); i++) {
hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
}
return (hash & 0x7FFFFFFF);
}
/**
* AP算法
*/
public static int APHash(String str) {
int hash = 0;
for (int i = 0; i < str.length(); i++) {
hash ^= ((i & 1) == 0) ? ((hash << 7) ^ str.charAt(i) ^ (hash >> 3))
: (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));
}
// return (hash & 0x7FFFFFFF);
return hash;
}
}
MD5 C++源码 : MD5.hpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
typedef struct{
unsigned int count[2];
unsigned int state[4];
unsigned char buffer[64];
}MD5_CTX;
#define F(x,y,z) ((x&y)|(~x&z))
#define G(x,y,z) ((x&z)|(y&~z))
#define H(x,y,z) (x^y^z)
#define I(x,y,z) (y^(x|~z))
#define ROTATE_LEFT(x,n) ((x<<n)|(x>>(32-n)))
#define FF(a,b,c,d,x,s,ac) { a+=F(b,c,d)+x+ac; a=ROTATE_LEFT(a,s); a+=b;}
#define GG(a,b,c,d,x,s,ac) { a+=G(b,c,d)+x+ac; a=ROTATE_LEFT(a,s); a+=b;}
#define HH(a,b,c,d,x,s,ac) { a+=H(b,c,d)+x+ac; a=ROTATE_LEFT(a,s); a+=b;}
#define II(a,b,c,d,x,s,ac) { a+=I(b,c,d)+x+ac; a=ROTATE_LEFT(a,s); a+=b;}
void MD5Init(MD5_CTX *context);
void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputlen);
void MD5Final(MD5_CTX *context, unsigned char digest[16]);
void MD5Transform(unsigned int state[4], unsigned char block[64]);
void MD5Encode(unsigned char *output, unsigned int *input, unsigned int len);
void MD5Decode(unsigned int *output, unsigned char *input, unsigned int len);
MD5.cpp
#include "Md5.hpp"
unsigned char PADDING[] = {
0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
void MD5Init(MD5_CTX *context){
context->count[0]=0;
context->count[1]=0;
context->state[0]=0x67452301;//链接变量,注意与大端字节序的区别,内存中是小端字节序
context->state[1]=0xEFCDAB89;
context->state[2]=0x98BADCFE;
context->state[3]=0x10325476;
}
void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputlen){
unsigned int i=0,index=0,partlen=0;
index=(context->count[0]>>3)&0x3F;//模64字节的余数,第一次调用为0
partlen=64-index;//第一次partlen为64
//预留最前面的64位存放数据长度
context->count[0]+=inputlen<<3;//文本总的位数,低32位
if(context->count[0]<(inputlen<<3)) context->count[1]++;
context->count[1]+=inputlen>>29;//先左移3,求出位数,再右移32位,求出左32位
if(inputlen>=partlen){
memcpy(&context->buffer[index], input, partlen);
MD5Transform(context->state, context->buffer);
//512位为1组
for(i=partlen;i+64<=inputlen;i+=64) MD5Transform(context->state,&input[i]);
index=0;
}
else i=0;
memcpy(&context->buffer[index], &input[i], inputlen-i);//最后剩下的一部分
}
//32位md5
void MD5Final(MD5_CTX *context, unsigned char digest[16]){
unsigned int index=0,padlen=0;
unsigned char bits[8];
index=(context->count[0]>>3)&0x3F;//模64字节的余数
padlen=(index<56)?(56-index):(120-index);//需要填充的长度,注意长度占8字节
MD5Encode(bits,context->count,8);
MD5Update(context,PADDING,padlen);
MD5Update(context,bits,8);//这里调用时,index=0
MD5Encode(digest,context->state,16);
}
void MD5Encode(unsigned char *output, unsigned int *input, unsigned int len){
unsigned int i = 0, j = 0;//len是char的长度
while (j<len){
output[j]=input[i] & 0xFF;
output[j+1]=(input[i]>>8)&0xFF;
output[j+2]=(input[i]>>16)&0xFF;
output[j+3]=(input[i]>>24)&0xFF;
i++;
j += 4;
}
}
void MD5Decode(unsigned int *output, unsigned char *input, unsigned int len){
unsigned int i = 0, j = 0;
while (j < len){
output[i] = (input[j]) |
(input[j + 1] << 8) |
(input[j + 2] << 16) |
(input[j + 3] << 24);
i++;
j += 4;
}
}
void MD5Transform(unsigned int state[4], unsigned char block[64]){
unsigned int a = state[0];
unsigned int b = state[1];
unsigned int c = state[2];
unsigned int d = state[3];
unsigned int x[16];
MD5Decode(x, block, 64);
FF(a, b, c, d, x[0], 7, 0xd76aa478);//32位运算
FF(d, a, b, c, x[1], 12, 0xe8c7b756);
FF(c, d, a, b, x[2], 17, 0x242070db);
FF(b, c, d, a, x[3], 22, 0xc1bdceee);
FF(a, b, c, d, x[4], 7, 0xf57c0faf);
FF(d, a, b, c, x[5], 12, 0x4787c62a);
FF(c, d, a, b, x[6], 17, 0xa8304613);
FF(b, c, d, a, x[7], 22, 0xfd469501);
FF(a, b, c, d, x[8], 7, 0x698098d8);
FF(d, a, b, c, x[9], 12, 0x8b44f7af);
FF(c, d, a, b, x[10], 17, 0xffff5bb1);
FF(b, c, d, a, x[11], 22, 0x895cd7be);
FF(a, b, c, d, x[12], 7, 0x6b901122);
FF(d, a, b, c, x[13], 12, 0xfd987193);
FF(c, d, a, b, x[14], 17, 0xa679438e);
FF(b, c, d, a, x[15], 22, 0x49b40821);
GG(a, b, c, d, x[1], 5, 0xf61e2562);
GG(d, a, b, c, x[6], 9, 0xc040b340);
GG(c, d, a, b, x[11], 14, 0x265e5a51);
GG(b, c, d, a, x[0], 20, 0xe9b6c7aa);
GG(a, b, c, d, x[5], 5, 0xd62f105d);
GG(d, a, b, c, x[10], 9, 0x2441453);
GG(c, d, a, b, x[15], 14, 0xd8a1e681);
GG(b, c, d, a, x[4], 20, 0xe7d3fbc8);
GG(a, b, c, d, x[9], 5, 0x21e1cde6);
GG(d, a, b, c, x[14], 9, 0xc33707d6);
GG(c, d, a, b, x[3], 14, 0xf4d50d87);
GG(b, c, d, a, x[8], 20, 0x455a14ed);
GG(a, b, c, d, x[13], 5, 0xa9e3e905);
GG(d, a, b, c, x[2], 9, 0xfcefa3f8);
GG(c, d, a, b, x[7], 14, 0x676f02d9);
GG(b, c, d, a, x[12], 20, 0x8d2a4c8a);
HH(a, b, c, d, x[5], 4, 0xfffa3942);
HH(d, a, b, c, x[8], 11, 0x8771f681);
HH(c, d, a, b, x[11], 16, 0x6d9d6122);
HH(b, c, d, a, x[14], 23, 0xfde5380c);
HH(a, b, c, d, x[1], 4, 0xa4beea44);
HH(d, a, b, c, x[4], 11, 0x4bdecfa9);
HH(c, d, a, b, x[7], 16, 0xf6bb4b60);
HH(b, c, d, a, x[10], 23, 0xbebfbc70);
HH(a, b, c, d, x[13], 4, 0x289b7ec6);
HH(d, a, b, c, x[0], 11, 0xeaa127fa);
HH(c, d, a, b, x[3], 16, 0xd4ef3085);
HH(b, c, d, a, x[6], 23, 0x4881d05);
HH(a, b, c, d, x[9], 4, 0xd9d4d039);
HH(d, a, b, c, x[12], 11, 0xe6db99e5);
HH(c, d, a, b, x[15], 16, 0x1fa27cf8);
HH(b, c, d, a, x[2], 23, 0xc4ac5665);
II(a, b, c, d, x[0], 6, 0xf4292244);
II(d, a, b, c, x[7], 10, 0x432aff97);
II(c, d, a, b, x[14], 15, 0xab9423a7);
II(b, c, d, a, x[5], 21, 0xfc93a039);
II(a, b, c, d, x[12], 6, 0x655b59c3);
II(d, a, b, c, x[3], 10, 0x8f0ccc92);
II(c, d, a, b, x[10], 15, 0xffeff47d);
II(b, c, d, a, x[1], 21, 0x85845dd1);
II(a, b, c, d, x[8], 6, 0x6fa87e4f);
II(d, a, b, c, x[15], 10, 0xfe2ce6e0);
II(c, d, a, b, x[6], 15, 0xa3014314);
II(b, c, d, a, x[13], 21, 0x4e0811a1);
II(a, b, c, d, x[4], 6, 0xf7537e82);
II(d, a, b, c, x[11], 10, 0xbd3af235);
II(c, d, a, b, x[2], 15, 0x2ad7d2bb);
II(b, c, d, a, x[9], 21, 0xeb86d391);
state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
}