http://www.umut.cn

发源:区块链中的暗码学

前言:谈区块链离不开密码学。通常来讲,区块链技术是利用块链式数据结构来验证与存储数据、利用分布式节点公式算法来生成和更新数据、利用密码学的方式保证数据传输和访问的安全、利用由自动化脚本代码组成的智能合约来编程和操作数据的一种全新的分布式基础架构与计算范式。区块链的核心是它按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构,并以密码学方式保证的不可篡改和不可伪造的分布式账本。我们对此做一个总结,可以发现区块链中有四项不可缺的核心技术,分别是分布式存储、共识机制、密码学原理和智能合约。而今天我们将主要从密码学的角度聊一聊区块链的起源问题。

【恺撒密码】

密码学作为一门古老的学科,有着悠久而奇妙的历史。它用于保护军事和外交通信可追溯到几千年前文字刚刚产生的上古时期。几千年来,密码学一直在不断地向前发展。而随着当今信息时代的高速发展,密码学的作用也越来越显得重要。它已不仅仅局限于使用在军事、政治和外交方面,而更多的是与人们的生活息息相关:如人们在进行网上购物,与商务交流,使用信用卡等等,都需要密码学的知识来保护人们的个人信息和隐私,当然对于我们关注的区块链技术,密码学作为其基石而存在。

凯撒(Caesar)是第一个把替换密码用于军事用途、并且记录下来的人。在他的那本歌颂自己丰功伟绩的《高卢记》里,凯撒描述了他把密信送到正处于围困之中、濒临投降的西塞罗手中。凯撒非常喜欢使用密文,后世的《凯撒传》详细地记录了凯撒使用的一种密文。而这种加密方法,甚至沿用到今天。   

凯撒密码的表示方法是:将每个字母,用字母表中这个字母之后三位的那个字母替代。它是一种替换加密的技术,明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。例,当偏移量是3的时候,所有的字母A将被替换成D,B变成E,以此类推。也就是字母A用字母D替代,字母B用字母E替代。比如Abroad,凯撒在用密文写信的时候,就被替换为Deurdg。这样就得到了敌人看不懂的密文。

假如有这样一条指令:RETURN TO ROME
用恺撒密码加密后就成为:UHWXUQ WR URPH

如果这份指令被敌方截获,也将不会泄密,因为字面上看不出任何意义。

现在看来这种加密方式可能稍显幼稚,但作为历史上文字记载的最早使用加密密钥的案例:由发件人和收件人共享加密密钥,标志了现代密码学的发端。可以说,从凯撒密码,到20世纪公共密钥被发明之前的这几千年时间里,密码学的原理都是一样的。比特币和区块链的加密方式,跟凯撒密码的原理区别,也就是多了公钥而已。直到今天,我们在看很多谍战片的时候,会发现不少特工和间谍还是采取这种方式传输情报。

这里有几个术语,需要特别指出。密码学家通常讲用来书写原始信息的字母表,也就是正常的字母表,称为明码表;而用来替换明码字母的称为密码表。这也是密码这个词的来历。那么往后移动三位,这个“三”则被称为密钥。当然,学过数学的人都明白,这里有26个字母,仅仅按照顺序移动,每个字母就有25个不同的替代方式,即25种密钥,要是把字母顺序打乱,密钥就更多了。算法则是通过各种尝试,破译密码的过程。

可以想象,在公元前100年左右,也就是相当于中国的西汉时期,要想破译凯撒的密码,那可能性几乎为零。在密码学中,恺撒密码是一种最简单且最广为人知的加密技术。恺撒密码还在现代的ROT13系统中被应用。但是和所有的利用字母表进行替换的加密技术一样,恺撒密码非常容易被破解,而且在实际应用中也无法保证通信安全。

【多表代换】

最早的古典密码体制主要包含单表代换密码体制和多表代换密码体制。作为古典密码中的两种重要体制,一直在古代历史上的全球各个区域广泛地被使用。凯撒密码就是一种典型的单表代换密码。

单表代换密码在长达一千年的时间里,被认为是无法破解的,因为存在着数量庞大的密钥,依靠手工是根本计算不过来的。但是随着社会的发展和技术的进步,来自东方的阿拉伯人,找到了更新的技术,从而发现了一条捷径来破获这个被认为是无解的密码,这次胜利是由阿拉伯世界的语言学家、统计学家和宗教学家三者共同完成的。

这还要间接感谢中国的造纸术的发明,伊斯兰文明得以快速传播。因为书籍需求量大增,那么就需要有人来校对,最能胜任这个工作的自然是神学家。他们在校对的同时,还在统计默罕默德启示录的用词频率,如果这个启示录出现了新词,那么它出现的年份肯定就更往后等等。在梳理的过程中,他们也顺道发现了一些字母出现的频率就是比其他的字母要高得多。

学习过英语的我们知道,字母e是最常见的,其次是字母t和a。如果按照凯撒密码加密,一个密码字母对应明码字母,那么密码字母中出现次数最多的很有可能就应该对应明码字母E,以此类推,很容易就可以排除掉大量的密钥,从而快速地找到正确的破译方法。现在无法考证究竟是谁把字母出现的频率和破译密码联系在了一起,但是可以肯定的是,公元九世纪的时候,阿拉伯人就已经非常擅长破译凯撒密码了。

阿拉伯人从公元7世纪到公元12世纪期间,建立了辉煌灿烂的文明,相比较而言,欧洲当时还是愚昧落后贫穷的地方。伊斯兰文明的繁盛,不仅带来了艺术、科学等文化的繁荣,社会的统治和管理也是非常有条理和高效的。当时的管理者,不仅在政府的关键事务上进行加密,而且记录税收的时候也采用了密码术,他们在《大臣手册》等管理文献里还在探讨与密码术有关的技术性问题。正是因为有了巨大的需求,再加上科学技术的进步,阿拉伯人终于有机会破译替换密码这道千年难题。

单表代换的破译十分简单,因为在单表代换下,除了字母名称改变以外,字母的频度、重复字母模式、字母结合方式等统计特性均未发生改变,依靠这些不变的统计特性就能破译单表代换。相对单表代换来说,多表代换密码的破译要难得多。

多表代换大约是在1467年左右由佛罗伦萨的建筑师Alberti发明的。多表代换密码又分为非周期多表代换密码和周期多表代换密码。在一个多表替换密码中,会使用多个字母作为密码。为了加快加密或解密速度,所有的字母通常写在一张表格上,密码学上称作tableau。这种表格通常是26×26,因为这样才能放下全部26个英文字母。填充表格及选择下次使用的字母的方法,就是不同多字母替换密码之间的定义。多字母替换密码比单字母更难打破,因为其替换可能性多,密文要较长才可。

其中最著名的一种为贝拉索于1585年推出的维吉尼亚密码。它于1863年之前一直未被破解。法国人称它作“不能破译的密码”(法语:le chiffre indéchiffrable)。此密码曾被误以为由布莱斯·德·维吉尼亚所创,所以才叫作维吉尼亚密码。

维吉尼亚密码中,表格的第一行只需直接填上26个字母,然后以下每一行的字母都是向左偏移一格。(这叫作表格横移,数学上每一列同余26。)要用这种密码需要使用一个关键字来作为密钥。关键字每次用完就再次重复。假设关键字是“CAT”,明文的第一个字由“C”加密,第二个字由“A”加密,第三个则由“T”加密,然后再回到C加密,一直重复。然后按照右边的密码表加密,例如BALL用CAT作关键字时会加密至DAEN,可见即使是同一个“L”亦会加密至另一个字母。现实中,维吉尼亚密码的关键字非常长。

非周期多表代换密码,对每个明文字母都采用不同的代换表(或密钥),称作一次一密密码,只要加密表够长,这是一种在理论上唯一不可破的密码。这种密码可以完全隐蔽明文的特点,但由于需要的密钥量和明文消息长度相同而难于广泛使用。为了减少密钥量,在实际应用当中多采用周期多表代换密码。在16世纪,有各种各样的多表自动密钥密码被使用,最瞩目的当属法国人B.de Vigtnère的Vigenère密码体制。有名的多表代换密码有Vigenère、Beaufort、Running-Key、Vernam和转轮机(rotor machine)。对于单表代换和多表代换密码来说,唯密文分析是可行的。单表代换和多表代换密码都是以单个字母作为代换对象的,而每次对多个字母进行代换就是多字母代换密码。大约1854年L.Playfair在英国推广Playfair密码,它是由英国科学家C.Wheatstone发明的。这是第一种多字母代换密码,在第一次世界大战中英国人就采用这种密码。多字母代换的优点是容易将字母的自然频度隐蔽或均匀化而有利于抵抗统计分析。这种密码主要有Playfair密码、Hill密码等。

到二十世纪二十年代,人们发明了各种机械加密设备用来自动处理加密。大多数是基于转轮的概念。1918年美国人E.H.Hebern造出了第一台转轮机,它是基于一台用有线连接改造的早期打字机来产生单字母表替代的,输出是通过原始的亮灯式指示。最著名的转轮装置是Enigma,它是由德国人Scherbius发明并制造的。它在第二次世界大战中由德国人使用。不过在第二次世界大战期间,它就被破译了。

【近代密码学】

近代密码学研究信息从发端到收端的安全传输和安全存储,是研究“知己知彼”的一门科学。其核心是密码编码学和密码分析学。前者致力于建立难以被敌方或对手攻破的安全密码体制,即“知己”;后者则力图破译敌方或对手已有的密码体制,即“知彼”。人类有记载的通信密码始于公元前400年。古希腊人是置换密码的发明者。1881年世界上的第一个电话保密专利出现。电报、无线电的发明使密码学成为通信领域中不可回避的研究课题。

在第二次世界大战初期,德国军方启用“恩尼格玛”密码机,盟军对德军加密的信息有好几年一筹莫展,“恩尼格玛”密码机似乎是不可破的。但是经过盟军密码分析学家的不懈努力,“恩尼格玛”密码机被攻破,盟军掌握了德军的许多机密,而德国军方却对此一无所知。

太平洋战争中,美军破译了日本海军的密码机,读懂了日本舰队司令官山本五十六发给各指挥官的命令,在中途岛彻底击溃了日本海军,导致了太平洋战争的决定性转折,而且不久还击毙了山本五十六。相反轴心国中,只有德国是在第二次世界大战的初期在密码破译方面取得过辉煌的战绩。因此,我们可以说,密码学在战争中起着非常重要的作用。

编码密码学主要致力于信息加密、信息认证、数字签名和密钥管理方面的研究。信息加密的目的在于将可读信息转变为无法识别的内容,使得截获这些信息的人无法阅读,同时信息的接收人能够验证接收到的信息是否被敌方篡改或替换过;数字签名就是信息的接收人能够确定接收到的信息是否确实是由所希望的发信人发出的;密钥管理是信息加密中最难的部分,因为信息加密的安全性在于密钥。历史上,各国军事情报机构在猎取别国的密钥管理方法上要比破译加密算法成功得多。

密码分析学与编码学的方法不同,它不依赖数学逻辑的不变真理,必须凭经验,依赖客观世界觉察得到的事实。因而,密码分析更需要发挥人们的聪明才智,更具有挑战性。

现代密码学是一门迅速发展的应用科学。随着因特网的迅速普及,人们依靠它传送大量的信息,但是这些信息在网络上的传输都是公开的。因此,对于关系到个人利益的信息必须经过加密之后才可以在网上传送,这将离不开现代密码技术。

1976年Diffie和Hellman在《密码新方向》中提出了著名的D-H密钥交换协议,标志着公钥密码体制的出现。 Diffie和Hellman第一次提出了不基于秘密信道的密钥 分发,这就是D-H协议的重大意义所在。

PKI(Public Key Infrastructure)是一个用公钥概念与技术来实施和提供安全服务的具有普适性的安全基础设施。PKI公钥基础设施的主要任务是在开放环境中为开放性业务提供数字签名服务。

二十世纪六七十年代以来计算机和通信系统的普及,带动了个人对数字信息保护及各种安全服务的需求。IBM的Feistel在七十年代初期开始其工作,到1977年达到顶点:其研究成果被采纳成为加密非分类信息的美国联邦信息处理标准,即数据加密标准DES,历史上最著名的密码体制。

1977年,美国国家标准局公布实施了“美国数据加密标(DES)”,军事部门垄断密码的局面被打破,民间力量开始全面介入密码学的研究和应用中。民用的加密产品在市场上已有大量出售,采用的加密算法有DES、IDEA、RSA等。

DES至今依然是世界范围内许多金融机构进行安全电子商务的标准手段,是迄今为止世界上最为广泛使用和流行的一种分组密码算法。然而,随着计算机硬件的发展及计算能力的提高,DES已经显得不再安全。1997年7月22日电子边境基金学会(EFF)使用一台25万美金的电脑在56小时内破译了56位DES。1998年12月美国决定不再使用DES。美国国家标准技术研究所(NIST)现在已经启用了新的加密标准AES,它选用的算法是比利时的研究成果“Rijndael”。以上这两个阶段所使用的密码体制都称为是对称密码体制,因为这些体制中,加秘密钥和解秘密钥都是相同的,而进入密码学发展的第三个阶段,则出现了非对称密码体制——公钥密码体制。

现有的密码体制千千万万,各不相同。但是它们都可以分为私钥密码体制(如DES密码)和公钥密码(如公开密钥密码)。前者的加密过程和脱密过程相同,而且所用的密钥也相同;后者,每个用户都有公开秘密钥。

【多链与非对称加密】

对称加密指的就是加密和解密使用同一个秘钥,所以叫做对称加密。对称加密只有一个秘钥,作为私钥。 常见的对称加密算法:DES,AES,3DES等等。

非对称加密指的是:加密和解密使用不同的秘钥,一把作为公开的公钥,另一把作为私钥。公钥加密的信息,只有私钥才能解密。私钥加密的信息,只有公钥才能解密。 常见的非对称加密算法:RSA,ECC。

非对称加密算法需要两个密钥:公开密钥(publickey)和私有密钥(privatekey)。公开密钥与私有密钥是一对,如果用公开密钥对数据进行加密,只有用对应的私有密钥才能解密;如果用私有密钥对数据进行加密,那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥,所以这种算法叫作非对称加密算法。 非对称加密算法实现机密信息交换的基本过程是:甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开;得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方;甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。

另一方面,甲方可以使用乙方的公钥对机密信息进行签名后再发送给乙方;乙方再用自己的私匙对数据进行验签。甲方只能用其专用密钥解密由其公用密钥加密后的任何信息。 非对称加密算法的保密性比较好,它消除了最终用户交换密钥的需要。

非对称密码体制的特点:算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂,而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥,并且是非公开的,如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全,而非对称密钥体制有两种密钥,其中一个是公开的,这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。

在EKT中,我们就使用了公私钥结合的非对称加密和路由策略的机制实现拜占庭容错。我们EKT的多链,采用“多链分而治之”的新方案重新设计了一个保障每个合约都能正常运行的公链,其中就使用到了非对称加密对用户的信息进行保存,同时主链和子链信息共享但是功能隔离。这一创新极大程度上简化了架构,降低了数据处理压力,确保一条链上流量激增不会影响到另一条链的效率,在链上进行的任何业务都不会收到其他业务干扰,有效实现了资源隔离。

在EKT中Token链是一个并行多链的结构,多链多共识,共享用户基础。EKT的Token是链上的一个属性,就像使用了utxo模型的链utxo有其他Token一样,我们的转账事件也是内置的。

其实EKT解决的一个核心问题是,目前Dapp的开发难度的问题如果使用以太坊的Solidity开发,需要学习以太坊的一整套逻辑,在复杂应用开发的时候需要考虑各种优化方案,同一个功能使用传统C/S结构一天写完的,用以太坊可能要写几周时间,对开发者来说很不友好。

例如针对C/S模型,要写一个非对称加密服务需要: 

1. 设计一个服务端,可以计算出一对秘钥pub/pri。将私钥保密将公钥公开。 
2. 设计一个客户端请求服务端时,拿到服务端的公钥pub。 
3. 客户端通过AES计算出对称加密的秘钥X。 然后使用pub将X进行加密。 
4. 客户端将加密后的密文发送给服务端。服务端通过pri解密获得X。 
5. 最后还要设计两边通讯机制,通过对称密钥X以对称加密算法来加解密。

这一套流程若要Dapp/公链开发者写出来,势必在真正开发区块链功能之前就已经被这些繁琐但其实通用的步骤耗费过多精力和资源。

EKT的中心思想就是设计一个社区的机制,让开发者可以轻易的开发一个可以承载DAPP的主链,其他的交给EKT来处理, EKT 的“一链一主币,多链多共识”的机制为后来的区块链项目开发提供了很大的便利,可以使用于任何区块链适用的应用场景。

EKT 提供了一套底层的区块链机制,其他的区块链项目可以很容易的基于 EKT 的主链代码部署一套自己的主链。在EKT上编写的区块链项目将无需过于担心安全性问题,因为每一个接口都是非常简单并且在许多条并行主链上部署和运行的。部署主链时可以灵活的发行自己主链的代币以及选择共识算法。新部署的主链也可以加入到 EKT 的整个生态,共享 EKT 生态的用户资源,代币也可以和EKT 主币以及其他主链的代币进行交换和流通。

EKT主链上每个DPoS节点的公钥都是公开的。这是一种兼顾效率、安全和去中心化的解决方案。Token现在一般被定义成一个智能合约,但如果把它变成一个预先定义好事件的“对象”,这个“对象”可以有自己的参数(比如总量、共识机制等等),则会带来更好的安全体验。接受token的地址可以有两种:普通的用户地址和合约地址,合约地址收到token之后可以执行非图灵完备的合约语言,进行简单的状态计算和token转移。

【失灵的SHA-1】

区块链玩家应该都对一个词非常的熟悉——哈希Hash,一般学术界翻译做“散列”,程序员直接音译为“哈希”,它的操作是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数 所有散列函数都有一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数。

但另一方面,散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同,这种情况称为“散列碰撞(collision)”,这通常是两个不同长度的输入值,刻意计算出相同的输出值。输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值哈希函数需要满足下述条件

a.确定性:哈希函数的算法是确定性算法,算法执行过程不引入任何随机量。这意味着相同消息的哈希结果一定相同
b.高效性:给定任意一个消息m,可以快速计算HASH(m) 
c.目标抗碰撞性:给定任意一个消息m0 ,很难找到另一个消息m1,使得HASH(m0)= HASH(m1)
d.广义抗碰撞性:很难找到两个消息m0不等于m1 ,使得HASH(m0)= HASH(m1) 在密码学上,一般认为如果d条件不满足,那么此哈希函数就不再安全。

在实际中,一般认为如果在某种程度上c条件不满足,那么此哈希函数就不再安全。当然了,如果c个条件完全不满足,那么此哈希函数已经彻底不安全,应该被直接弃用。

哈希一般的实际应用被称为安全散列算法,(英语:Secure Hash Algorithm,缩写为SHA),它是FIPS认证的安全散列算法,是一个密码散列函数家族。能计算出一个数字消息所对应到的,长度固定的字符串(又称消息摘要)的算法。且若输入的消息不同,它们对应到不同字符串的机率很高(以前被认为无限趋近于99.99999999%,为啥是以前,稍后解释)密码学作为一门古老的学科,有着悠久而奇妙的历史。它用于保护军事和外交通信可追溯到几千年前文字刚刚产生的上古时期。

几千年来,密码学一直在不断地向前发展。从凯撒密码开始,人们在发展新密码学算法的时候也在孜孜不倦的破解已有的密码学算法,因为对于破解者来说,密码难度越高,意味着其背后守护的秘密价值就越大。SHA家族的五个算法,分别是SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512,后几个一般也可以统称为SHA-2,由美国国家安全局(NSA)所设计,并由美国国家标准与技术研究院(NIST)发布;是美国的政府标准。也是众多互联网和电子产品的密钥门神SHA系列Hash函数家族是最为知名的Hash函数家族,MD5,SHA-1和SHA-2都一直被广泛的使用,比特币使用的就是属于SHA-2系列里的SHA-256凑杂算法。

1990年MD4算法被提出,但是被很快发现了严重的安全问题,在1992年被MD5算法取代。MD5算法在之后的十几年内被软件行业广泛使用,直到2004年我国密码学家王小云在国际密码讨论年会(CRYPTO)上展示了MD5算法的碰撞并给出了第一个实例。该攻击复杂度很低,在普通计算机上只需要几秒钟的时间。

在2005年王小云教授与其同事又提出了对SHA-1算法的碰撞算法(Finding Collisions in the Full SHA-1, CRYPTO 2005),不过计算复杂度为2的69次方,在实际情况下难以实现直到去年(2017年)的2月24日,谷歌抛出了他们惊人的实验结果——公布第了一例SHA-1哈希碰撞实例,这项发表甚至使密码学界最为著名的顶会CRYPTO为等其论文修改结果延期了19个小时。因为简单来说,Google的工作基本宣判了SHA-1的死刑。在这项工作公布前,大多数网站https的证书都涉及使用SHA-1算法,包括GitHub在内的众多版本控制工具以及各种云同步服务都是用SHA-1来区别文件,很多安全证书或是签名也使用SHA-1来保证唯一性。

长期以来,人们都认为SHA1是十分安全的,至少大家还没有找到一次碰撞案例, 不过如今不得不为用户安全考虑开始升级至SHA-2或者其他算法了。CWI和Google的研究人员们成功找到了一例SHA1碰撞,而且很厉害的是,发生碰撞的是两个真实的、可阅读的PDF文件。这两个PDF文件内容不相同,但SHA1值完全一样。

为什么这一研究结果的发表如此引人注目?这是因为大家都知道散列算法可能存在碰撞, 但只要这种碰撞难以创造,散列算法所支撑的系统就是安全的——而大家之前一直认为SHA1的碰撞案例很难实现。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。