【区块链技术第01期】区块链中的密码算法

原文链接：【区块链技术第01期】区块链中的密码算法

近两年，随着区块链的日益普及，密码算法再次频频出现在各大报刊上。

密码目标

密码学 David Kahn 在他的《密码学圣经》一书中这样定义密码学：“密码学就是保护。”

保护什么？

当然，最重要的是保护信息本身不被他人获取（保密）； 同时，保护信息不被伪造和篡改（完整性）； 能够验证信息的发送者（可证明）； 此外，还需要防止信息的发送者否认（non-deniable）。

密码的分类

密码学分为两个分支：密码学和密码分析：

在现代密码学中，密码算法分为对称加密和非对称加密两种。

非对称加密算法的实现方式有很多种，大部分都是基于解决数学问题，主要包括三大类：大整数分解、离散对数、椭圆曲线。

1、大整数分解问题：

给定两个近似数，很容易将它们相乘。 然而，鉴于他们的产品，找到他们的因素并不那么容易。 这是许多现代密码系统的症结所在。

2.离散对数问题：

目前，人们还没有找到求解复杂度在多项式范围内的离散对数问题的算法。

3.椭圆曲线问题：

它是将离散对数问题应用于椭圆曲线上的点。

需要注意的是，这些问题只是表面上看是无法解决的，因为多年过去了，还没有找到简单的解决办法，而一旦找到解决办法，基于这些问题的加密算法就不再安全了。

非对称加密算法可用于信息的加解密（主要用于对称加密的密钥信息的传递），也可用于数字签名和身份认证。

说到数字签名，就不得不提到密码学领域的另一个知识：哈希函数。

数字签名的标准方法通常是，给定一个消息m，使用哈希函数创建一个固定长度的消息摘要h(m)，然后使用私钥对摘要S[h(m)]进行签名。 签名消息作为 (m,S[h(m)]) 对发送。 通过公钥恢复h(m)的值，将h应用到接收到的消息m上，验证消息的真实性。

这个过程如下图所示：

其中，消息摘要是对消息内容进行哈希运算，得到唯一的摘要值来引用原始消息内容。

详细密码算法

区块链涉及的密码学知识主要包括哈希算法和椭圆曲线等，本文主要针对这两种算法进行介绍。

(1)哈希算法

1.哈希定义

散列算法可以计算任意长度消息的摘要，该消息非常短并且通常具有固定长度。 哈希函数没有密钥，函数本身在算法上是公开的。

比如计算一句话“helloblockchainworld,thisisyeasy@github”的SHA-256 Hash值。

$echo "helloblockchainworld,thisisyeasy@github"|shasum-a256

db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90

这意味着对于一个文件来说，不需要检查它的内容，只要它的SHA-256Hash计算的结果也是

db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90

这意味着该文件的内容极有可能是“helloblockchainworld,thisisyeasy@github”。

2.哈希特征

出于安全目的，哈希函数具有以下属性：

防撞有时也称为“抗碰撞”，分为“弱抗碰撞”和“强抗碰撞”。

如果在给定的明文前提下无法找到与其发生碰撞的其他明文，则该算法具有“弱抗碰撞性”； 如果找不到任何两个与哈希冲突的明文，则该算法具有“强抗冲突性”。

3. 常用算法

目前常见的专用哈希算法包括MD5和SHA系列算法、RIPEMD系列算法。

目前MD5和SHA1已经破解，一般建议至少使用SHA2-256或更安全的算法。

4. SHA256

SHA-256 是 SHA 家族的成员，也是 SHA-2 算法集群中的一个类。 对于小于 264 位的消息，将生成 256 位的消息摘要。

SHA-256的计算过程分为消息预处理和主循环两个阶段。

在消息预处理阶段，主要完成消息的填充和扩展，将所有输入的原始消息转化为n个512位的消息块； 在主循环阶段，每个消息块都使用 SHA-256 压缩功能进行处理。 具体计算步骤如下：

在处理完所有 512 位数据包后比特币采用的加密算法，SHA-256 算法的最后一个数据包的输出是一个 256 位消息摘要。

(2) 椭圆曲线

1. 椭圆曲线定义

密码学中使用的有限域上的椭圆曲线通常有两种类型：一种是定义在有限域 GF(p) 上对质数 p 取模； 另一个定义在特征为2 GF(2^m) 的伽罗华域上。 本文简要介绍第一种。

所谓有限域上的椭圆曲线，简单来说就是满足下式的曲线（x、y、a、b均为小于素数p的非负整数）：

2. 椭圆曲线的性质

椭圆曲线具有以下两个性质：

3.椭圆曲线的运算

由于椭圆曲线加密所进行的操作实际上是在椭圆曲线上进行的，因此需要对椭圆曲线上的一些操作进行定义（注意：“加法”和“乘法”的定义只是为了描述方便）。

因为0点为无穷远点，过A点和0点的直线垂直于X轴，与曲线相交于另一点B，则与X轴对称的B点为A点。

4.椭圆曲线上点的乘法

设P为椭圆曲线上的一点，则正整数k乘以点P的结果由下式定义，注意公式中的加法是上述椭圆曲线上的点的加法：

1*P=P

2*P=P+P

3*P=2*P+P

……

k∗P=(k−1)∗P+P

5.公钥生成

在实际应用中比特币采用的加密算法，我们不需要关心椭圆曲线的众多参数如何选择，我们只需要从密码学家精心挑选的曲线中选择一条即可。 比特币选择 secp256k1 来生成公钥。

从私钥生成公钥的过程如下：

确定椭圆曲线上的一点作为基点P。由于所有的点组成一个有限群，那么必须以基点P作为生成元来生成子群。 注意这个子群的阶数是n，也就是说群的单位元素（无穷远点）是由点P累加n次得到的，记nP=0（无穷远点）。

公钥点Q定义为K Ps的加法（即k乘以点P）。

密码学在区块链中的应用

密码学在区块链中的应用场景主要包括地址生成、交易签名和共识机制等。

1.钱包地址生成

以比特币系统为例，讲解密码学在钱包地址生成中的应用。

1）私钥

比特币系统一般通过调用操作系统底层的随机数生成器生成一个256位的随机数作为私钥。 比特币私钥总量很大，通过遍历整个私钥空间获取比特币存储的私钥极其困难，因此密码学是安全的。

2）公钥

比特币的公钥是由私钥先通过Secp256k1椭圆曲线算法生成的一个65字节的随机数。

3）钱包地址

对公钥进行SHA-256和RIPEMD160双重哈希运算，生成20字节的汇总结果，再经过两次SHA-256哈希算法和Base58转换，形成33个字符的钱包地址。

公钥生成过程是不可逆的，即不能从公钥推导出私钥。 比特币的公钥和私钥通常保存在比特币钱包文件中，其中私钥最为重要。 丢失私钥意味着丢失对应地址中的所有比特币资产。

2. 交易签名

在交易签名场景中，发送方A用自己的私钥加密信息发送给接收方B，B使用A的公钥对信息进行解密，从而验证信息是A发送的。

3. 共识机制

哈希函数的谜题友好性构成了基于工作量证明 (POW) 的共识算法的基础。 在比特币挖矿的工作量证明算法中，通过计算小于难度值的区块的SHA-256哈希值来完成挖矿。

4.默克尔树

区块链的数据结构以前后区块的哈希值作为指针，构建Merkle树进行完整性验证处理。

参考：

[1] 邹军、张海宁等.区块链技术指南[M]. 北京：机械工业出版社，2017

本文作者：清华大学电子系博士，链区块学院执行院长魏宏信

Chain Block Academy：专注于区块链技术研发和教育

- - - - - - - 结尾 - - - - - - -