Js哈希摘要算法

更新日期: 2019-04-11阅读: 3.7k标签: 算法

前言

最近在看一些npm库的时候总是看到各种哈希签名算法,之前工作中也有用到过签名算法,但并没有深入理解过其中的原理,于是找了点资料稍微了解了一下,总结了这篇文章


哈希摘要算法

哈希函数(也称散列函数),是一种根据任意长度数据计算出固定签名长度的算法,比如MD5,SHA系列。


哈希签名摘要算法特点

  • 不是加密算法,而是一种摘要算法
  • 不可逆,“单向”函数
  • 签名长度固定
  • 存在2的N次方种结果,N表示签名长度


以MD5为例

MD5是由美国密码学家罗纳德·李维斯特(Ronald Linn Rivest)设计一种加密算法。

  • 128个bits长度,也就是16个字节
  • 输出结果由为“0-F”字符组成,不区分大小写
  • 存在2的128次方种输出结果


MD5算法

一、源数据处理

计算原文长度(bits)对512求余的结果,需要填充原文使得原文对512求余的结果等于448, 填充的方法是第一位填充1,其余位填充0。填充完后,信息的长度为512 * N + 448。

剩余64bits存储空间用来填充源信息长度,填充在448byte 数据之后。

最终经过处理后的数据长度为 512 * N。

动手画了一张简单的图来说明:


二、处理数据

1、数据进行处理前,会定义4个常量,作为初始值
这4个常量分别是

var a = 0x67452301;
var b = 0xEFCDAB89;
var c = 0x98BADCFE;
var d = 0x10325476;

翻译成二进制就是

var a =  1732584193;
var b = -271733879;
var c = -1732584194;
var d =  271733878;

2、将处理后的数据,外循环处理N次,N为第一步中512的整数倍。
每次外循环处理的会产生新的“a、b、c、d”值,每次新产生的“a、b、c、d”值会再一次提供给下一次外循环使用

3、在每个外循环中又进行内循环处理64次,在这64次数据处理中会不停的将 512 bytes 数据中的 16个小单元不停的通过4个函数进行交叉处理,共计进行64轮计算。

4、最终生成新的“a、b、c、d”,新的“a、b、c、d”分别是占用32bytes的数据

5、最终生成的“a、b、c、d”转换为对应的ascll占用的字节,32 bytes * 4 = 128 bytes, 一个字节占用8个bytes, 也就是16个字节,16个字节转换为ASCII码,再将ASCII码转换为16进制数据,即可得到一个32个字节长度的hash值。

内外循环代码

function binl_md5(x, len) {
    /* append padding */
    x[len >> 5] = x[len >> 5] | 0x80 << (len % 32);
    x[(((len + 64) >>> 9) << 4) + 14] = len;    

    var i, olda, oldb, oldc, oldd,
        a =  1732584193,
        b = -271733879,
        c = -1732584194,
        d =  271733878;
    
    // 每次计算位移值,可以理解为是常量
    var ffShift = [7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22];
    var ggShift = [5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20];
    var hhShift = [4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23];
    var iiShift = [6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21];

    // Todo: 四个字节一组,每个组别之间不停的交叉计算,不停的根据已计算出来的值多次计算赋值
    // x[i]装的是4个字节的数据
    // x.length 为 512 * N / 32
    // i += 16 每512bits长度的数据分为了16组,而每次循环的计算单位是以512为一个单元的,所以每次都是+16 
    for (i = 0; i < x.length; i += 16) {
        olda = a;
        oldb = b;
        oldc = c;
        oldd = d;

        // 64轮计算中包含原始“a、b、c、d”值。 
        // 以及位移值,以及一个计算常量,这两个是MD5规范中所定义的常量
        a = md5_ff(a, b, c, d, x[i],      ffShift[0], -680876936);
        d = md5_ff(d, a, b, c, x[i +  1], ffShift[1], -389564586);
        c = md5_ff(c, d, a, b, x[i +  2], ffShift[2],  606105819);
        b = md5_ff(b, c, d, a, x[i +  3], ffShift[3], -1044525330);
        a = md5_ff(a, b, c, d, x[i +  4], ffShift[4], -176418897);
        d = md5_ff(d, a, b, c, x[i +  5], ffShift[5],  1200080426);
        c = md5_ff(c, d, a, b, x[i +  6], ffShift[6], -1473231341);
        b = md5_ff(b, c, d, a, x[i +  7], ffShift[7], -45705983);
        a = md5_ff(a, b, c, d, x[i +  8], ffShift[8],  1770035416);
        d = md5_ff(d, a, b, c, x[i +  9], ffShift[9], -1958414417);
        c = md5_ff(c, d, a, b, x[i + 10], ffShift[10], -42063);
        b = md5_ff(b, c, d, a, x[i + 11], ffShift[11], -1990404162);
        a = md5_ff(a, b, c, d, x[i + 12], ffShift[12],  1804603682);
        d = md5_ff(d, a, b, c, x[i + 13], ffShift[13], -40341101);
        c = md5_ff(c, d, a, b, x[i + 14], ffShift[14], -1502002290);
        b = md5_ff(b, c, d, a, x[i + 15], ffShift[15],  1236535329);

        a = md5_gg(a, b, c, d, x[i +  1], ggShift[0], -165796510);
        d = md5_gg(d, a, b, c, x[i +  6], ggShift[1], -1069501632);
        c = md5_gg(c, d, a, b, x[i + 11], ggShift[2],  643717713);
        b = md5_gg(b, c, d, a, x[i],      ggShift[3], -373897302);
        a = md5_gg(a, b, c, d, x[i +  5], ggShift[4], -701558691);
        d = md5_gg(d, a, b, c, x[i + 10], ggShift[5],  38016083);
        c = md5_gg(c, d, a, b, x[i + 15], ggShift[6], -660478335);
        b = md5_gg(b, c, d, a, x[i +  4], ggShift[7], -405537848);
        a = md5_gg(a, b, c, d, x[i +  9], ggShift[8],  568446438);
        d = md5_gg(d, a, b, c, x[i + 14], ggShift[9], -1019803690);
        c = md5_gg(c, d, a, b, x[i +  3], ggShift[10], -187363961);
        b = md5_gg(b, c, d, a, x[i +  8], ggShift[11],  1163531501);
        a = md5_gg(a, b, c, d, x[i + 13], ggShift[12], -1444681467);
        d = md5_gg(d, a, b, c, x[i +  2], ggShift[13], -51403784);
        c = md5_gg(c, d, a, b, x[i +  7], ggShift[14],  1735328473);
        b = md5_gg(b, c, d, a, x[i + 12], ggShift[15], -1926607734);

        a = md5_hh(a, b, c, d, x[i +  5], hhShift[0], -378558);
        d = md5_hh(d, a, b, c, x[i +  8], hhShift[1], -2022574463);
        c = md5_hh(c, d, a, b, x[i + 11], hhShift[2],  1839030562);
        b = md5_hh(b, c, d, a, x[i + 14], hhShift[3], -35309556);
        a = md5_hh(a, b, c, d, x[i +  1], hhShift[4], -1530992060);
        d = md5_hh(d, a, b, c, x[i +  4], hhShift[5],  1272893353);
        c = md5_hh(c, d, a, b, x[i +  7], hhShift[6], -155497632);
        b = md5_hh(b, c, d, a, x[i + 10], hhShift[7], -1094730640);
        a = md5_hh(a, b, c, d, x[i + 13], hhShift[8],  681279174);
        d = md5_hh(d, a, b, c, x[i],      hhShift[9], -358537222);
        c = md5_hh(c, d, a, b, x[i +  3], hhShift[10], -722521979);
        b = md5_hh(b, c, d, a, x[i +  6], hhShift[11],  76029189);
        a = md5_hh(a, b, c, d, x[i +  9], hhShift[12], -640364487);
        d = md5_hh(d, a, b, c, x[i + 12], hhShift[13], -421815835);
        c = md5_hh(c, d, a, b, x[i + 15], hhShift[14],  530742520);
        b = md5_hh(b, c, d, a, x[i +  2], hhShift[15], -995338651);

        a = md5_ii(a, b, c, d, x[i],      iiShift[0], -198630844);
        d = md5_ii(d, a, b, c, x[i +  7], iiShift[1],  1126891415);
        c = md5_ii(c, d, a, b, x[i + 14], iiShift[2], -1416354905);
        b = md5_ii(b, c, d, a, x[i +  5], iiShift[3], -57434055);
        a = md5_ii(a, b, c, d, x[i + 12], iiShift[4],  1700485571);
        d = md5_ii(d, a, b, c, x[i +  3], iiShift[5], -1894986606);
        c = md5_ii(c, d, a, b, x[i + 10], iiShift[6], -1051523);
        b = md5_ii(b, c, d, a, x[i +  1], iiShift[7], -2054922799);
        a = md5_ii(a, b, c, d, x[i +  8], iiShift[8],  1873313359);
        d = md5_ii(d, a, b, c, x[i + 15], iiShift[9], -30611744);
        c = md5_ii(c, d, a, b, x[i +  6], iiShift[10], -1560198380);
        b = md5_ii(b, c, d, a, x[i + 13], iiShift[11],  1309151649);
        a = md5_ii(a, b, c, d, x[i +  4], iiShift[12], -145523070);
        d = md5_ii(d, a, b, c, x[i + 11], iiShift[13], -1120210379);
        c = md5_ii(c, d, a, b, x[i +  2], iiShift[14],  718787259);
        b = md5_ii(b, c, d, a, x[i +  9], iiShift[15], -343485551);

        a = safe_add(a, olda);
        b = safe_add(b, oldb);
        c = safe_add(c, oldc);
        d = safe_add(d, oldd);
    }
    // 最终生成4个占用32 bytes控制的值
    return [a, b, c, d];
}

四轮计算线性函数

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)) 

6、第五点可以解释为什么生成的hash值中只会包含“0-F”,且不区分大小写的原因,长度为16。

function rstr2hex(input) {
    var hex_tab = '0123456789abcdef',
        output = '',
        x,
        i;
    for (i = 0; i < input.length; i += 1) {
        x = input.charCodeAt(i);
        output += hex_tab.charAt((x >>> 4) & 0x0F) +
            hex_tab.charAt(x & 0x0F); x:${input.charCodeAt(i)}, output: ${output}`);
    }
    return output;
}

以上代码来自 https://github.com/blueimp/JavaScript-MD5,稍有改动。


适用场景:

  • 私密数据加密,比如用户密码一般都不会明文存储,而是通过加密后存入数据库
  • 赌场开盘前将开票结果公布,开盘后通过签名对比校验是否存在作弊行为
  • 检测文件是否下载完成,比如迅雷下载
  • ...


如何破解

MD5中,虽然由源文可以推导出签名,反过来,并不能由签名推导出源文。但MD5并不是坚不可摧,目前有两种破解方式

  • 碰撞法,虽然MD5签名存在2的128次方种输出结果,但每个签名对应的原文并不是唯一的,只要计算机性能够强大,给予充足的时间,总能找到能输出相同签名的数据源。
  • 映射法,把常规字符串对应的签名存储,比如常用的“123456”,“abcdefg”等。当得到MD5签名时,就可以映射出源数据。


如何防范:

  • 使用安全性更高的SHA256,并不是说SHA256不能被破解,只是相对于MD5来说算法步骤更多,也更复杂,破解难度更大。
  • 源数据 + KEY,比如“123456”加上KEY就变成了“123456@#DFF23DS”,其中“@#DFF23DS”就是服务端存储的KEY。“源数据 + KEY” => 签名。
  • 源数据 + KEY + 动态数据,KEY有可能会被猜到,如果再加上动态数据的话,破解难度会进一步提升,比如用户名、动态密码。“源数据 + KEY + 动态密码” => 签名。
  • 多次MD5,MD5("123456")很容易被猜到,MD5(MD5("123456")),将MD5后的签名再进行一次MD5呢,如果进行三次,十次,是不是破解的难度会更大,当然这么做会增加计算时间,需要权衡。


其他:

  • 中文编码需要转码,否则前端与后端编码后的值可能不一致。
  • 除了MD5算法,还存在很多其他形式的哈希函数算法,比如SHA系列,他们的设计思路大体相同。


来自:https://segmentfault.com/a/1190000018839324


链接: https://www.fly63.com/article/detial/2833

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!