BeWithYou

胡搞的技术博客

  1. 首页
  2. 数据结构/实用算法/知识
  3. 从MD5预处理看Javascript中的编码/解码/进制等问题

从MD5预处理看Javascript中的编码/解码/进制等问题


从MD5预处理看Javascript中的编码/解码/进制等问题

昨天遇到一个js中md5加密的问题——使用的第三方库文件对中文加密(其实应该叫hash)的结果,与PHP加密的结果不对等。
后来换了一个库就好了,通过对比发现,第一次加密失败的原因在于其流程中对于中文编码未处理好。或者说,并未帮我们事先编码好中文串。
于是学习了一下js中有关知识,总结一下。

还是放在实用算法目录下吧,感觉web前端的东西占比点多了,我真的不是写前端的呀!

进制转换

  • Javascript中可以直接表示16进制的数字,比如0xe5, 0x54c8。
  • 10进制转换成其他进制,方法如下
3..toString(2)//没错,是2个点,第1个点将3转换为float。结果输出11。
0x10.toString(2)//这里取到的是0x被10进制以后的值,再转换成2进制 。输出10000
  • 其他进制转换成10进制
parseInt("0xff",16)//输出255
parseInt("ff",16)//输出255

编码解码

  • escape是一个全局函数,它使用十六进制的数字(%xx 或 %uxxxx)编码字符串。它不会对 ASCII 字母和数字以及标点进行编码。小于等于0xFF的字符将被转义为 %xx,大于0xFF的将被转移为 %uxxxx,他其实是返回的Unicode的编码结果,不是UTF8的
  • unescape,该函数的工作原理是这样的:通过找到形式为 %xx 和 %uxxxx 的字符序列(x表示十六进制的数字),用 Unicode 字符 \u00xx 和 \uxxxx 替换这样的字符序列进行解码。当unescape用于encodeURI编码过的字符串解码时,可以获得其16进制的字符表示方式。我们后面将会提到将字符转换成UTF8编码下二进制数组的方法,就是基于这种转换为前提的。
  • encodeURIComponent,encodeURI 将字符串中某些字符用十六进制的转义序列进行替换,不会对ASCII字母和数字以及标点符号编码,url 的编码用这两个。他们的区别在于前者可以编码 url 中的某些参数,从而保留一些符号,而后者用于编码整体的 url。可以用decodeURIComponent,decodeURI来对其解码。

举个例子:

escape("中2");//'%u4E2D2'
escape("中2").length;//7
encodeURI("中2");//'%E4%B8%AD2'
encodeURI("中2").length;//10

unescape(encodeURI("中2"));//'中2' 输出一个乱码
unescape(encodeURI("中2")).length;//4

可以看到:

  • escape将"中"用unicode编码成16进制字符%4E2D,并且保留了ASCII数字2。
  • encodeURI将中用UTF-8编码成%E4%B8%AD,保留了ACSII数字2。中文在UTF-8中占用2-4个字节。"中"字占用了3个字节E4B8AD,被加上%编码了。
  • escapeencodeURI编码后的字符串求长度,得到的就是其字面长度。
  • unescapeencodeURI编码后的字符串解码(前者可以找到%xx形式的字节,将其解码为unicode形式),我们看到的结果是乱码,因为编码解码方式不对应。
  • 但是,unescape解码完的UTF-8编码字符串,它的长度很神奇的等于它所占的真实字节数!"中2"里面,"中"占了3个字节,"2"占了1个字节,总共4个字节。

联动一下PHP里面关于求字符串长度和字节数:

strlen("中2");//4 字节数,在全是ASCII字符时也就是字符串长度
mb_strlen("中2","utf-8");//2 字符真实长度

MD5算法中的预处理操作

这里只提一下MD5预处理的流程,它关系到字符串的位运算。预处理流程是这样的:

  • 填充。如果输入信息的长度(bit位数)对512取余不等于448,则在后面填充一个1和无数个0直到满足前面一个条件。填充完后,信息长度为 N*512+448 个bit。
  • 记录信息长度。用末尾的64bit来记录填充之前的长度。
  • 上面两步处理完后,输入信息的长度为 (N+1)*512。是512的倍数了。

我们使用的是这个js文件:github地址
下面简单来看看它是如何进行输入字符串的预处理操作的。
首先,将字符串UTF8化,采用encodeURI然后再unescape的方法。

/*
 * Encode a string as utf-8
 */
function str2rstr_utf8(input) {
    return unescape(encodeURIComponent(input));
}

然后将其转换为小端模式的bit位数组,每个元素32个bit,过程见注释。

/*
 * Convert a raw string to an array of little-endian words
 * Characters >255 have their high-byte silently ignored.
 */
function rstr2binl(input) {
    var i,
        output = [];
    output[(input.length >> 2) - 1] = undefined;
    //设置output长度为字节数/4,即每个元素8*4=32bit
    //初始化每个元素为0x00000000 32bit位全部置为0
    for (i = 0; i < output.length; i += 1) {
        output[i] = 0;
    }
    for (i = 0; i < input.length * 8; i += 8) {
        //每个循环处理1个字节,8位。4个循环处理完一个元素。如0>>5=24>>5=0。
        //采用小端模式,先遇到的字节放在低位。
        //假如输入信息的前4个字节依次为0x01 0x02 0x03 0x04,则转换后的0号元素为
        //0x04030201
        output[i >> 5] |= (input.charCodeAt(i / 8) & 0xFF) << (i % 32);
    }
    return output;
}

接上面的代码,举个例子。我有这么一段已经转换为raw string的字符串,总共4个字节,依次为0x01, 0x02, 0x03, 0x04,我们测试一下上面函数的处理结果。

var rawStr = String.fromCharCode("0x01","0x02","0x03","0x04");
//即'\u0001\u0002\u0003\u0004'
rstr2binl(rawStr);
//输出[67305985] 即[0x04030201]

与我们预判的结果一致,生成了一个32bit小端模式元素。

之后进行填充,记录长度的操作。如下,其中len=输入信息的总bit数,x为上一个步骤处理好的array:

/* append padding */
x[len >> 5] |= 0x80 << (len % 32);//补齐448
x[(((len + 64) >>> 9) << 4) + 14] = len;//记录原来的长度

x[len >> 5] |= 0x80 << (len % 32);其中 len>>5表示要补齐到取余448的开始位置。例如: len=8 (1字节)时,len>>5=0,即在0号位置继续补齐; len=32 (4字节)时,len>>5=1,即在1号位置新建元素补齐。当开始位置与原数组最后一个位置重合的时候,表明最后一个元素的4个字节并未用完,可以在后面继续补齐。0x80.toString(2)='10000000'。只需要左移len%32位即可将这个1放在合适的位置。后面的默认用0补齐。
x[(((len + 64) >>> 9) << 4) + 14] = len;将原长度len写入到最后一个(len=32时其实是倒数第二个)元素中。MD5用最后一个小端模式的64bit的integer来记录len,所以在占用的2个字节中,低位写入第一个(低地址的)字节。例如len=32, (((len+64)>>>9)<<4)+14=14 ,最后14、15号元素为最后的64bit,把len=32写入到低地址14号中。新的input整体长度为 16 * 32 = 512, 可以被512整除啦!但这个下标如何算出来的,我还没琢磨明白。看见位运算就晕了。
后面就可以进行装入幻数,循环运算等hash算法流程了。

回到顶部