当前位置:天蓝信息港 > 两性 > 正文内容

漫谈区块链(5)——密码学的瑞士军刀(上)

字体+ 编辑:第三角度 来源:天蓝信息港所属栏目:两性2018-03-18 13:51:48我要评论

我要带朋友们潜入水下参观密码学的一些技术概貌。当然我们不可能把每个细节都搞清楚,我们仅深入到能够理解区块链技术原理的深度就返航(再深入会掉粉的)。再次提醒朋友们...

我要带朋友们潜入水下参观密码学的一些技术概貌。当然我们不可能把每个细节都搞清楚,我们仅深入到能够理解区块链技术原理的深度就返航(再深入会掉粉的)。再次提醒朋友们,区块链技术有现在的气质靠的是密码学,梦想创新创业的,建议深入了解密码学,然后用这个技术去比划各种行业,也许会有海阔天空的感觉。

未来这几期,我想介绍密码技术里最基础的两个,分别是散列函数和数字签名。这两个技术应用范围非常广,我们日常工作生活中已经有相当多的应用了,只是我们很多人并没有感受到。

先说散列函数。技术小白请不要吐槽,更不要退订我的公众号,尽管“散列函数”的名称不论听和看都不那么友好,其他的名字像什么“哈希函数”、"杂凑函数"也差不多德性,英文叫HASH还算简洁,它还有一个比喻称呼叫“数字指纹”,算是有点亲民了。

在计算机出现以前,人们就对文章书籍有提取摘要信息和关键词的需求,目的是为了提高查阅、检索的速度。计算机出现以后,由于计算机处理数据时最重要的工作之一就是检索,如何提高计算机的检索效率是提高计算机处理数据能力的重要指标。显然计算机检索数据的方式与人们翻阅图书馆信息检索卡片不一样,计算机有自己的语言和阅读方式,因此设计如何获取好用的信息摘要是一门看家手艺。

图示:大英图书馆纸质卡片目录

现代密码学以信息论、数学为依托,研究的主要目标就是如何处理信息并安全的传递。网上传递的各种各样信息,在网络的底层都是变成二进制数字在铜线里、空中电波中传递,如何让接收方校验发送方发来的数据是完整正确的?从数字通信应用开始之前,这个校验问题就必须解决掉。

专家们发明了许多校验技术。例如“校验和”(checksum),这种校验方式非常简单,就是发送方把传输的二进制数字按位加起来,例如要传输“0101101”这个数字串,就把里面4个1加起来,然后把结果数(例子的和为4)和原始数字串(要传递的信息“0101101”)传给接收方,接收方自己也把收到的信息加起来,比较与收到的“和”一样不一样,来确定是不是收对了。聪明的小白们看完一定一脑袋问号,这种校验也太粗糙了吧,原来技术世界的精细活也不是那么高深呀?

随着研究越来越深入,高深的散列函数出现了,它实在太有用了,被称为密码学的瑞士军刀。有了前面问题需求的铺垫,我现在可以直接介绍散列函数是干什么的。说白了(技术小白的白),散列函数就是把一段无论多长的数据串(可以是文字、文章、电影、音乐)转换成一个固定长度的数值,这个数值就是一个数字,计算机里面存的是二进制,一般显示给我们看的是16进制。而这个固定长度一般是指在二进制下的固定位数。

图示:散列函数被输入不同信息,哪怕非常小的差别,输出都是完全不一样的结果(SHA256是比特币中使用的散列函数)

如今散列函数有许多应用,我们网上下载文件是不是完整的校验就是靠它实现的。现在手机音乐都有“听歌识曲”功能,不了解原理的人一定很好奇,机器怎么做到这么智能的识别音乐呀?其实音乐歌曲都是数字方式存储的,对散列函数来说就是一串二进制数字,可以计算其中一段或者整首歌的散列值作为索引。那么手机在听歌的时候其实是在录制成数字音乐,再计算散列值并与歌曲库的散列值去对比查找,并不是手机也懂音乐了。

散列函数在比特币的技术架构主要用到三个方面的特性(还有许多其他特性,但不是比特币应用中所关注的,所以就不介绍了),本篇介绍碰撞阻力。

今天总是遇到这种每个字都认识,放在一起完全不知道啥意思的词,当然我会想尽办法让朋友们看明白的。这个特性的重要性直接关系到比特币的信任基础,上一篇我的副标题是信任的基石,是指整个密码学是比特币技术应用的信任之源,在密码学内,这个哈希函数的碰撞阻力可以说是基石的基石。

前面图示中我例举了几个输入,然后看看在SHA256算法的输出,我在图示中提到哪怕很接近的输入,都有不同的输出。一定有朋友会想,难道就不会出现不同信息输入,会有同样输出的情况吗?会的,如果出现这种情况,就叫出现了碰撞。碰撞阻力的意思就是很难找到碰撞,最好永远也找不到。这是一部分以加密为目标的散列函数的梦想。

但是理想归理想,现实很残酷,理论上人类是不可能找到这种完美算法的。为什么呢?我们拿上篇“生日悖论”的例子来说。

每个人生日就如同散列函数的结果一样,是有固定数量的,总共也就有365个可能性(不考虑闰年)。如果超出365人,有366个人,那么无论如何都会有两个人落在同一天过生日。这个也叫“鸽巢原理”、“抽屉原理”。

对于散列函数也是如此,SHA256这种算法的输出是256位二进制数字,也就是说总共就有2256个可能性,这个数字是很大,但也不是无限的呀。而我们可以选择的输入信息可是无限的可能性,最简单的就是我们可按1、2、3......不断输入来计算散列值,总有一天我们会输入到2256+1,那么就必然会出现两个输入产生了一个结果。

所以哈希函数完全杜绝碰撞是不可能的,可是数学家们不会因为不可能就不再去努力,因为可能性本身就是一门实用数学——概率论。既然完全杜绝是不可能的,那么能不能想办法让碰撞非常非常非常难发生呢?

有两个努力方向,首先是把算法研究的更加精深,这个咱就不介绍了(说的好像我能介绍似的,其实我根本不懂,但我相信世界上最聪明人的研究成果)。另外一个是增加固定输出的可能性数量,让尝试碰撞的努力变成天荒地老,海枯石烂的事情。

“生日悖论”的例子里,在365个可能性结果情况下,经过概率计算,需要23个人就能达到50%的碰撞可能性。同样的在2256个可能性结果情况下,数学家算出来达到50%碰撞可能性的尝试次数大约是2128次。这个数字有多大呢?

普林斯顿大学Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Steven Goldfeder等四位教授编著的网络课程教材《Bitcoin and Cryptocurrency Technologies》里是这么说的:如果一台电脑每秒计算一万个散列值,需要计算1027年;换个角度,如果人类到今天为止制造的所有电脑,在整个宇宙起源的时刻(137亿年前)便开始计算,到今天能找到碰撞的概率仍然很小,比两秒后地球被大陨石摧毁的概率还要小得多。(在视频课程里,教授停了一下,然后说,两秒钟过去了,咱们还在。)

散列函数有很多,区别在于采用的计算方法和输出的长度有区别,目前流行的有MD5,SHA1、SHA2等等。我很反感用英文单词首字母组合表示一个东西,又不解释一下的行为,这是人为制造学术壁垒。其实这些组合看上去高大上,其实解开来非常简单容易记。每当我遇到大写字母组合,我就要去查查到底是哪个单词组成的,例如MD,其实就是Message-Digest Algorithm(信息摘要算法),看看多朴素。再例如SHA,其实就是Secure Hash Algorithm(安全哈希算法),同样的朴实无华。后面的数字是更新迭代的序号。

如果说设计散列函数是一批绝顶聪明的数学家制造“盾”的工作,那么还有一些绝顶聪明的科学家在做“矛”的事情。这些人仔细研究各种算法的细节,然后想尽办法去找出碰撞的机会。正是这样的研究,让散列函数在现实应用中能保证其安全性。

山东大学的密码学专家,中国科学院院士王小云教授在这个领域有杰出贡献。2004年的国际密码讨论年会(CRYPTO)尾声,王小云及其研究同事展示了MD5、SHA-0及其他相关散列函数的散列冲撞。

图示:王小云教授(百度图片搜的)

2005年2月,王小云与其同事提出SHA-1散列函数的散列冲撞。由于SHA-1散列函数被广泛应用于现今的主流计算机安全产品,其影响可想而知。SHA-1输出的是160位长度的散列值,也就是说有2160个可能性,按照“生日悖论”所用计算的概率方法计算,理论上达到50%的碰撞可能性需要尝试280次,王小云所提的散列冲撞算法只需少于269次。同年8月,王小云、姚期智,以及姚期智妻子姚储枫联手,于国际密码讨论年会提出SHA-1散列函数散列冲撞算法的改良版,缩短为少于263次。

看到263次方这个数字,我脑袋里闪出小时候听过的故事,一个人向国王要奖赏,在国际象棋棋盘上,第一个格子放一粒米,第二个放2粒,第三个4粒,第四个16粒.....直到最后一个格子是264粒米的故事。看来263次好像也是天文数字呀。

目前公认最安全的是SHA-2家族,比特币采用的是SHA2家族中输出长度为256的算法,也被称之为SHA256。此外,SHA-3 相关算法也已被提出。

许多朋友心中有一句广告词——“一切皆有可能”,而这句话对散列函数防止碰撞能力一定是存疑的,总担心万一碰巧哪一天发现了碰撞呢。然而数学告诉我们“一切皆有概率”,相信数学,就信散列函数。如果建立不了这个信任,现实世界不仅仅是比特币,许多应用都将在你的心目中不再可靠,只是以前你不知道罢了。

好了,先结束这篇吧,其他两个散列函数的特性放到下一篇继续......

1.本站部分内容来源于互联网权威网站,内容具合法性,如需删除请联系我们;邮箱:qfiuoattksfb7@163.com

2.文章内容并不代表八卦来了观点或立场,如有关于文章内容,版权或其它问题请看下方免责声明或联系删除;

相关推荐相关推荐
  • 眉庄放的最大一招,就连甄嬛也蒙在谷里?

    眉庄放的最大一招,就连甄

  • 四岁儿童屡遭离婚母亲毒打,伊能静自愿承担孩子所有医疗费用

    四岁儿童屡遭离婚母亲毒打

  • 每日一笑话:女方父母不同意我们在一块,结果我这样做就让他们……

    每日一笑话:女方父母不同

  • 前“央视一姐”周涛现身机场,素颜出镜衣服穿成这样真没谁了,看见镜头一脸的不爽

    前“央视一姐”周涛现身机

  • 张钧甯趴下的那一刻,“全世界”都静止了,网友:为难摄影师!

    张钧甯趴下的那一刻,“全

  • 时尚街拍,走在街头看着穿清凉装的美女,一饱眼福

    时尚街拍,走在街头看着穿

  • 背包突然自燃?自燃物你也有!快看应该怎么办!

    背包突然自燃?自燃物你也

  • 搞笑GIF动图:竟然被一只老鼠给咬鼻子了,真是太丢人了

    搞笑GIF动图:竟然被一

热门话题热门话题
  • 眉庄放的最大一招,就连甄嬛也蒙在谷里?

    眉庄放的最大一招,就连甄

  • 四岁儿童屡遭离婚母亲毒打,伊能静自愿承担孩子所有医疗费用

    四岁儿童屡遭离婚母亲毒打

  • 每日一笑话:女方父母不同意我们在一块,结果我这样做就让他们……

    每日一笑话:女方父母不同

  • 前“央视一姐”周涛现身机场,素颜出镜衣服穿成这样真没谁了,看见镜头一脸的不爽

    前“央视一姐”周涛现身机

  • 宝宝学做家务学会的好处多到你想不到

    宝宝学做家务学会的好处多

  • 美国试管婴儿:怎么保证冻胚移植的成功?

    美国试管婴儿:怎么保证冻

  • 夏季一种菜叶,能缓解胃疼,降血压,你今天吃了吗?

    夏季一种菜叶,能缓解胃疼

  • 孩子免疫力变差,多半是喂药方法有问题,这5种错别再犯了

    孩子免疫力变差,多半是喂