加密技术：对称密码算法与SM3密码哈希算法的应用

比特币的所有权是通过数字密钥、比特币地址和数字签名来确立的,这样的设计也影响了后续所有的区块链产品。这一特性已经成为区块链技术的一个最为重要特征。数字密钥实际上并不存储在网络中,而是由用户自己生成并存储在文件或简单的数据库中,被称为“钱包”。早期的钱包功能非常简单,存储在用户钱包中的数字密钥完全独立于比特币协议,可由用户的钱包软件生成并管理,而无须区块链或网络连接。后来,在比特币及其他数字货币开始广泛应用后,有人专门针对钱包功能进行开发、优化,并提供第三方的钱包服务,使用户更加方便地使用数字货币。

在比特币中,每笔交易都需要有效的签名才能被存储记录到区块链中,只有有效的数字密钥才能产生有效的数字签名。密钥的生产都是成对产生的,一个私钥对应一个唯一的公钥,因此,拥有密钥副本就意味着拥有了其账户的所有权及控制权。我们可以把公钥理解为银行的账户代码,私钥则是控制这个账户的密码,秘钥不会在网络中传输或被其他人看见,需要存储在钱包文件或者其他安全的地方。

现代密码学的一个革命性的突破是解决对称密码算法无法在大规模的信息加密传输中普及的问题。对称密码算法是指加密和解密共用一个密码,也称单钥密码算法。它的最大缺陷是,信息发送方必须和每个接受方约定好对称密钥,那么在密钥的大规模分发过程中,无法有效防止密钥被窃取或者被人攻击,也不太容易去管理那么多的密钥。

对此,1976年,Diffie(迪菲)和Hellman(赫尔曼)提出了新的思路,他们将原来的一个密钥一分为二,成一对密钥,一个密钥用于加密,一个密钥用于解密。加密密钥公开,称为公钥。解密密钥不能公开,唯独本人秘密持有,不能给别人知道,称为私钥。

如果别人想给我发信息,他要用我的公钥对信息进行加密,而只有我的私钥才能解开,其他任何人都解不开。同样,我想给别人发消息,要用对方公开的加密密钥进行加密,而只有他手上有的那把私钥才能解开加密后的信息。

这样的思路就很好地解决了单密钥体系下的密钥大规模分发的问题。这就是非对称密码机制的思想。1978年,Rivest(李维斯特)、Shamir(萨莫尔)和Adleman(阿德曼)提出著名的RSA 密码算法,首次实现了非对称密码算法。

非对称密码算法除了解决开放系统中密钥大规模分发的问题,还带来原来对称密码体制不具备的功能,那就是非常独特的认证功能。

比如,如果我想给别人发信息,我不仅用别人的公钥对报文进行加密,同时我还可用我的私钥进行签名,这样别人就可以用我的公钥进行验签,判定报文是不是从我这发送的。

认证功能的出现使信息加密传输形式发生革命性的变化:信息既可以加密,也可以签名,就像支票一样,让信息的加密传输有了主人的感觉。所以说,非对称密码机制的实现是密码学的一次重大革命,密码学的应用也因此从军事领域开始走向民用领域。

另外,哈希算法是现代密码学的另一个巨大成就。它也被称为“散列函数”,最早的SHA(Secure Hash Algorithm)哈希算法由美国国家安全局设计,于1993年发布。2010年,中国国家密码管理局公布中国商用密码哈希算法标准——SM3密码哈希算法。

哈希算法的优点是,它可以用非常简单的摘要信息描述原始信息集;且计算是不可逆的,给定输入很容易得到输出,迅速收敛,但是从输出计算回输入是不可行的或者需要非常高的代价。还有一个有意思的特性是,只要输入信息发生一点点变化,输出就变得完全不一样。

基于这样优秀的特性,哈希函数得到广泛的应用,在数字文件的校验,电子签名等诸多方面都得到大规模的商业应用。在数字货币领域,哈希算法常常被当成数字货币交易挖矿、交易区块链以及钱包地址压缩生成的工具更是得到广泛的应用。

自公私钥体系建立以来,包括素数幂运算、椭圆曲线乘法等数学函数都相继被应用,其中重要的特点是这些函数都是不可逆的。也就是说,我们很容易从一个方向计算出结果,但想从结果倒推是不可行的(或者说是在相当长的时间里不可行)。由于这些数学方法及理论的引入,数字密码及数字签名技术得以创建和实现。因此,可以说数字密码技术是构建在数学基础之上的,是经过充分的理论证明后才在应用领域得以推广的。

在比特币及后续的区块链技术当中,基本都是利用公钥密码学创建密钥对,以此来控制对数字货币的控制权,区别在于使用的具体公私密钥算法有所不同。密钥对由私钥和公钥(由私钥派生出来的)组成,公钥用于接受数字资产,私钥用于对支付交易进行签名。在一次交易中,私钥可以对交易数据进行签名,生成已签名交易数据,在不泄漏私钥的情况下,公钥可以对已签名的交易数据进行有效性的验证。在花费数字货币时,数字货币持有人在交易中同时提交公钥和签名数据。通过附带的公钥和签名数据,区块链网络中的所有参与者都可以验证交易的有效性,确认该交易确实是由交易发起人发起。

在大部分的钱包实践中,私钥和公钥是以密钥对的形式存储在一起的。但由于公钥是可以由私钥计算出来,因此,只存储私钥也是可行的。

比特币公私钥及地址生成过程如图2-8所示。

图2-8 比特币公私钥及地址生成过程

比特币地址是一串由数字和字母构成的字符串,可以分享给任何想给你转比特币的人。地址是由公钥转换而来的,包含数字和字母。比特币地址是由公钥通过哈希值运算产生的,这是个不可逆过程。地址产生后,并与公钥进行关联,从而不仅可以代表一个公钥又代表区块链上的用户ID。当你知道一个用户的地址后,你就可以通过区块链网络向该地址发送比特币,当发送方对交易进行签名并通过后,交易即完成。比特币地址是用户可以看到的唯一表现形式,交易过程中不必知道对方是男是女,姓什么叫什么,身处何地,只要知道其地址就可以完成交易。这也是比特币及区块链技术匿名性的重要表现形式,由于地址数量足够多,表示范围足够大,理论上几乎可以被认为是无限量,在现实的交易过程中,经常临时生成地址,在交易完成后将地址弃用的情况。

比特币的地址是通过单向的加密哈希算法从公钥推导出来的。由于“哈希算法”是一种单向函数,它可以对任意长度的输入进行计算,生成输入信息的数据指纹。加密哈希函数在比特币及其他区块链项目中得到广泛的应用,包括:区块链地址、脚本地址、挖矿中的工作量证明算法、区块链哈希等。目前,普遍应用的哈希算法是SHA 体系,比特币用于从公钥创建地址的算法采用的是安全哈希算法(SHA)和RACE 完整性原语求值信息摘要算法(RIPEMD),应用的具体算法是SHA256和RIPEMD160。

具体比特币地址的生成过程是从公钥K 开始,通过SHA256计算出它的哈希值,然后将其结果在进行RIPEMD160运算得出一个160比特(20字节)长度的数字。

A=RIPEMD160(SHA256(K))

式中,K 是公钥;A 是比特币地址。

比特币地址是以Base58Check编码形式展现给用户的,它使用58个字符和一个校验码,能够达到方便阅读、避免歧义、防止地址转录及输入时犯错的效果。图2-9描述的比特币地址是如何从公钥产生的。这里强调一点,比特币地址的校验码设计得很巧妙,在一定情况下,可以避免用户因为输入错误地址而导致误操作。因为如果输入的地址有误,极有可能无法通过地址校验上,从而就无法进行交易,在一定程度上避免人为误操作,而以太坊的地址设计上并没有这么做。当然,即便是这样,在转账过程中还是要小心确认目标地址是否正确,不要误操作。

除了比特币之外,后续的各种数字货币及区块链应用都离不开密码技术的应用,而对于区块链上的操作几乎都是沿用了比特币密钥生成和操作的过程,只是采用的具体加密算法略有区别而已。

此外,在记录交易账本的数据结构上,比特币也采用了密码学技术,通过哈希算法将交易的数据内容在逻辑上形成不可回溯的链条,进而具有不可随意篡改的数据结构特性。

默克尔树是在区块链中所使用的数据结构。默克尔树属于二叉树的一种,而二叉树是数据结构中的最基本数据模型,并且在计算机领域里得到广泛的使用。

图2-9 比特币地址的具体生成过程

那么什么是默克尔树?

默克尔树是由一个根节点,一组中间节点和一组叶子节点组成。根节点表示最终的那个节点,且只有一个。叶子节点可以有很多,但是不能再扩散也就是没有子节点了。就像一棵树,由树根长出树干,树干上长出树枝,树枝长出叶子,而叶子上不会再长出叶子。其逻辑结构如图2-10所示。

Root:这个就是根节点,所有的子节点汇总到这里,像一棵倒立的树。

Hash:能将任意长度的二进制明文映射为较短的二进制串的算法,也称为“哈希”算法,如MD5、SHA 系列等,哈希后的结果也称哈希值。

Data0...Data3:这些代表的是具体的原始数据。

B0,B1...B3:这些是把原始数据进行哈希运算后得到对应的哈希值。(www.xing528.com)

图2-10 默克尔树的逻辑结构

这里要注意的是,B0 的数据就是Data0 做哈希运算的结果,也就是B0可以作为Data0的唯一数据标识,B0的哈希值对应的是Data0这一条数据。

现在重点来了,一个简单的默克尔树就是像图2-10中显示的那样,有以下三步:

第一步把最底层的Data0...Data3 这四条数据,每一条单独进行哈希,得出4个哈希值作为叶子节点;

第二步把相邻的两个叶子节点的哈希值拿出来再进行哈希,如B0+B1哈希后得出B4;

第三步递归执行这样的哈希操作,直到最终哈希出一个根节点,就结束了。

这就是默克尔树的运行原理,在图中展现是:B0+B1哈希得出B4,B2+B3哈希得出B5,B4+B5哈希得出Root根节点。由于每个节点上的内容都是哈希值,所以也称为“哈希树”。

默克尔树的特性是:默克尔树属于二叉树,而又有自己独特的名字,那么一定是有区别与经典二叉树的特性。其主要有三大特性如下所述。

第一特性:任意一个叶子节点的细微变动,都会导致Root节点发生翻天覆地的变化,可以用来判断两个加密后的数据是否完全一样。

第二特性:快速定位修改,如果Data1中数据被修改,会影响到B1、B4和Root,当发现根节点Root的哈希值发生变化,沿着Root→B4→B1最多通过O(log n)时间即可快速定位到实际发生改变的数据块Data1。

第三特性:零知识证明,它指的是证明者能够在不向验证者提供任何有用的信息的情况下,使验证者相信某个论断是正确的。比如怎么证明某个人拥有Data0...Data3这些数据呢?创建一棵如图2-11所示的默克尔树,然后对外公布B1、B5、Root;这时Data0的拥有者通过哈希生成B0,然后根据公布的B1生成B4,再根据公布的B5生成Root,如果最后生成的Root哈希值能和公布的Root一样,则可以证明拥有这些数据,而且不需要公布Data1、Data2、Data3这些真实数据。

图2-11 默克尔树

这里,首先介绍一个概念:默克尔路径,图2-11中Root→B4→B1这就是一条路径,表示从根节点到叶子节点所经过的节点组成的路径。

比特币中,默克尔树被用作归纳一个区块中的所有交易,同时生成整个交易集合的数字签名,且提供了一种校验区块是否存在某交易的高效途径,就是默克尔路径。生成默克尔树需要递归地对各个子节点进行哈希运算,将新生成的哈希节点插入到默克尔树中,直到只剩一个哈希节点,该节点就是默克尔树的根节点。

假设一个区块中有16笔交易,根据上文提到的公式O(log n)可以算出16的对数是4,也就是要找到这个区块中的任意一笔交易,只需要4次就可以了,它的默克尔路径会保存4个哈希值,可能读者们对这个高效率的查找没有认识,我们来看一个统计,如表2-1所示。

表2-1 查找统计数据

一笔交易大概250字节左右。路径数代表哈希值的数量,路径数是4表示这条路径存了4个哈希值,每个哈希值是32字节。

区块大小=交易数×250字节

路径大小=路径数×32字节

可以看出,当区块大小由16笔交易(4 KB)增加至262 144笔交易(65 MB)时,为证明交易存在的默克尔路径长度增长极其缓慢,仅仅从128字节到576字节。有了默克尔树,一个节点能够仅下载区块头(80字节/区块,里面包含上一区块头的哈希值、时间戳、挖矿难度值、工作量证明随机数,包含该区块交易的默克尔树的根哈希值),然后通过从一个满节点回溯一条小的默克尔路径就能认证一笔交易的存在,而不需要存储或者传输大量区块链中大多数内容,这些内容可能有几个GB的大小。这种不需要维护一条完整的区块链的节点,又被称为简单支付验证(SPV)节点,它不需要下载整个区块而通过默克尔路径去验证交易的存在。再来献上一张V 神(维塔利克·布特林)画的图,在比特币网络中找出了TX3的默克尔路径,如图2-12所示。

图2-12 TX3的默克尔路径

以上介绍了什么是默克尔树,以及它的三个特性和在比特币中的应用。其核心就是将大量数据进行哈希运算后增加其分布式索引性能,通过维持一个较小的高效索引(默克尔路径)进而管理复杂的大量数据。

由此,区块链中,一个区块内的基本结构如图2-13所示。

通过默克尔树以及哈希算法的应用,形成了区块链自身独特的数据结构。比特币通过将一定周期时间内容的交易内容打包,并以默克尔树的形式存储,然后再通过包头存储的自身和前一个哈希值形成了一个逻辑链条,进而实现所有的数据按照一定的时间演进过程存储下来。这也就是为什么将比特币的底层技术抽象出来后,被概括为“区块链”技术的原因。因为,其数据结构的逻辑就是类似于一种将数据打包成“块”后,再由哈希值串联在一起,而数据块的内部除块头信息外,交易的数据都是以默克尔树的形式组织并存储起来的。

图2-13 一个区块的基本结构