区块链中的密码算法

近两年,随着区块链日益火爆,密码算法也再次高频地出现在各大报端。

密码的目标

密码学DavidKahn在他的被称为“密码学圣经”的著作中是这样定义密码学的:“密码术(cryptology)就是保护。”

保护什么呢?

首要的当然是保护信息本身不被别人获取(机密性);同时,保护信息不被伪造、篡改(完整性);能够验证信息的发送者(可认证);另外,也需要防止信息发出者抵赖(不可抵赖)

密码的分类

密码学分为密码编码学密码分析学两大分支:

前者的目标是构建功能更强大、更有效的新的加解密算法;

后者的目标则是发现已有密码算法的弱点,以便不用秘钥就能还原明文。

现代密码学中将密码算法分为对称加密非对称加密两类。

对称加密,加解密采用预先分配好的相同的密钥;

非对称加密,加密和解密采用预先分配好的秘钥,但是加密和解密采用不同的密钥。

实现非对称加密算法有多种方法,大多数都是基于求解数学难题的,主要包括三类:大整数分解、离散对数和椭圆曲线

1 大整数分解类问题:

给出两个大约数,很容易就能将它们两个相乘。但是,给出它们的乘积,找出它们的因子就不那么容易了。这就是许多现代密码系统的关键所在。

2 离散对数类问题:

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

3 椭圆曲线类问题:

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

需要注意的是,这些问题只是看上去不可解,因为历经多年仍未能找到一个简单的解决办法,一旦找到了一个解决办法,那么基于这些问题的加密算法就不再安全了。

非对称加密算法可以用于加解密信息(主要是用于对称加密的密钥信息传递),也可以用于数字签名和身份认证等

提起数字签名,不得不提起密码学领域的另一个知识:哈希函数

数字签名的标准方法通常是,给定一个消息m,利用哈希函数先创建一个定长的消息摘要h(m),之后用私钥签署摘要S[h(m)]。所签署的消息以(m,S[h(m)])对的形式发送。通过公钥恢复h(m)的值,并将h应用到所接收到的消息m上,验证消息的真实性。

这个过程如下图所示:

其中,消息摘要是对消息内容进行哈希运算,获取唯一的摘要值来指代原消息内容。

密码算法详解

区块链中涉及的密码学知识主要包括哈希算法椭圆曲线等,本文着重介绍一下这两种算法。

(一)哈希算法

1 哈希定义

哈希算法能计算任意长度消息的摘要,该摘要非常短且通常是固定长度的。哈希函数没有密钥,且函数本身是算法公开的。

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

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

db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90

这意味着对于某个文件,无需查看其内容,只要其SHA-256Hash计算后结果同样为

db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90

则说明文件内容极大概率上就是“helloblockchainworld,thisisyeasy@github”。

2 哈希特性

对于安全用途来说,哈希函数具备如下特性:

正向快速:给定明文和哈希算法,在有限时间和有限资源内能计算得到哈希值

逆向困难:给定哈希值,在有限时间内很难逆推出明文

输入敏感:原始输入信息发生任何改变,新产生的哈希值有很大不同

冲突避免:很难找到两段内容不同的明文,使得它们的哈希值一致

冲突避免有时候又称为“抗碰撞性”,分为“弱抗碰撞性”和“强抗碰撞性”。

如果给定明文前提下,无法找到与之碰撞的其他明文,则算法具有“弱抗碰撞性”;如果无法找到任意两个发生Hash碰撞的明文,则称算法具有“强抗碰撞性”。

3 常见算法

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

MD4(RFC1320)是MIT的RonaldL.Rivest在1990年设计的,MD是MessageDigest的缩写。其输出为128位。MD4已被证明不够安全。

MD5(RFC1321)是Rivest于1991年对MD4的改进版本。它对输入仍以512位进行分组,其输出是128位。MD5比MD4更加安全,但过程更加复杂,计算速度要慢一点。MD5已被证明不具备“强抗碰撞性”。

SHA(SecureHashAlgorithm)并非一个算法,而是一个哈希函数族。NIST(NationalInstituteofStandardsandTechnology)于1993年发布其首个实现。目前知名的SHA-1算法在1995年面世,它的输出为长度160位的Hash值,抗穷举性更好。SHA-1设计时模仿了MD4算法,采用了类似原理。SHA-1已被证明不具备“强抗碰撞性”。为了提高安全性,NIST还设计出了SHA-224、SHA-256、SHA-384和SHA-512算法(统称为SHA-2),跟SHA-1算法原理类似。SHA-3相关算法也已被提出。

RIPEMD(RACEIntegrityPrimitivesEvaluationMessageDigest),是HansDobbertin等3人在MD4、MD5的基础上,于1996年提出来的。算法共有4个标准128、160、256和320,其对应输出长度分别为16字节、20字节、32字节和40字节。RIPEMD建立在MD的基础之上,所以,其添加数据的方式和md5完全一样。

目前,MD5和SHA1已经被破解,一般推荐至少使用SHA2-256或更安全的算法。

4 SHA256

SHA-256属于SHA家族一员,SHA-2算法簇中的一类。对于小于264位的消息,产生一个256位的消息摘要。

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

在消息预处理阶段,主要完成消息的填充和扩展,将所有输入的原始消息转换为n个512比特的消息块;主循环阶段,对每个消息块利用SHA-256压缩函数进行处理。具体计算步骤如下:

步骤1:填充附加位特。填充消息使其长度n≡(448mod512)。填充由一个1和后续0组成。其中,448=512-64预留了长度位。

步骤2:附加长度。在填充后的消息后附加64位的长度信息。

步骤3:初始化缓存。哈希函数的中间值及最终结果保存在256bit的缓存中,缓存由8个32位的寄存器(A、B、c、d、e、f、g、h)表示,将这些寄存器初始化为如下的整数(十六进制):

A=0x6A09E667,B=0xBB67AE85,C=0x3C6EF372,D=0xA54FF53A,

E=0x510E527F,F=0x9B05688C,G=0x1F83D9AB,H=0x5BE0CD19

步骤4:以512位分组为单位处理消息并输出结果。

所有的512-bit分组处理完毕后,对于SHA-256算法最后一个分组产生的输出便是256-bit的消息摘要。

(二)椭圆曲线

1 椭圆曲线定义

密码学中采用有限域上的椭圆曲线,一般有两种:一种是定义在以素数p为模的有限域GF(p)上;另一种则是定义在特征为2的伽罗瓦域GF(2^m)上。本文简要介绍第一种。

所谓有限域上的椭圆曲线,简单来说就是满足下面式子要求的曲线(x,y,a,b都是小于素数p的非负整数):

2 椭圆曲线性质

椭圆曲线有如下两个性质:

1)椭圆曲线关于X轴对称;

2)画一条直线跟椭圆曲线相交,最多有三个交点。

3 椭圆曲线上的运算

由于椭圆曲线加密进行的运算实际上都是在椭圆曲线上进行的,所以需要定义一些椭圆曲线上的运算(注意:“加法”和“乘法”的定义仅仅是为了方便描述)。

1)椭圆曲线的0点

定义坐标系中距离X轴无穷远点为椭圆曲线上的一个特殊点,称为0点。上述第二条性质可以加强为:过曲线上任意两点(可重合)的直线必定与曲线相交于第三点。

2)椭圆曲线上点的加法

设椭圆曲线上有两点A和B,过这两点的直线与该曲线相交于第三点C,C点关于X轴对称得到D点,则D为A和B两个点的和,记作D=A+B。很明显,D点也在该曲线上。所以椭圆曲线上两点之和也是曲线上的点。

特别地,如果两点重合,则作椭圆曲线在A点处的切线,与曲线相交于B,B点关于X轴对称得到C点,则C点为A点与自身的和,记作C=A+A。

那么关于这个加法,我们可以得到以下结论:

椭圆曲线上的加法满足交换律,即A+B=B+A

A点为A点和0点之和,即A+0=A

因为0点是无穷远点,所以过A点与0点的直线是垂直于X轴的,它与曲线相交于另一点B点,那么B点关于X轴对称的点就是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生成公钥。

由私钥生成公钥的过程如下:

1)选取基点P

确定椭圆曲线一个点作为基点P,由于所有的点构成一个有限群,那么基点P必然可以作为一个生成元生成一个子群。记这个子群的阶数为n,也就是说P点累加n次得到群的单位元(无穷远点),记做nP=0(无穷远点)。

2)选取私钥

3)计算公钥

公钥点Q定义为K个P相加(即k乘以点P)。

密码学在区块链中的应用

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

1 钱包地址生成

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

1)私钥

比特币系统一般通过调用操作系统底层的随机数生成器来生成256位随机数作为私钥。比特币私钥的总量大,极难通过遍历全部私钥空间来获得存有比特币的私钥,因而密码学是安全的。

2)公钥

比特币的公钥是由私钥首先经过Secp256k1椭圆曲线算法生成65字节长度的随机数。

3)钱包地址

将公钥进行SHA-256和RIPEMD160双哈希运算生成20字节长度的摘要结果,再经过2次SHA-256哈希算法和Base58转换形成33字符长度的钱包地址。

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

2 交易签名

交易签名的场景则是由发送者A采用自己的私钥对信息进行加密后发送给接收者B,B使用A的公钥对信息解密,从而验证信息是由A发送的。

3 共识机制

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

4 Merkle树

区块链的数据结构使用前后区块的哈希值作为指针构造Merkle树,用来进行完整性验证处理

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180314G1R1JG00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券