第
3
章
区块链密码学基础
密码学是区块链的底层支撑技术,区块链功能的实现基于密码学基础,密
码学也是保障区块链系统安全运行的重要理论支撑。最早期的比特币系统涉
及的密码学知识较为简单,主要为数字签名、哈希等。随着区块链的去中心化
应用的不断推广,越来越复杂的密码学技术,例如零知识证明、同态等被引入区
块链领域。本章将从密码学基础角度,对区块链应用中会用到的密码学方案进
行介绍。此外,本章还会进阶地描述一些较为复杂的密码学方法。
3.信息安全基础特性
1
信息安全的定义是,在任意一个信息系统中,其中所有硬件设施和内在单
元,例如硬件、软件、数据、物理环境等都可以得到安全保护,并且有能力抵御偶
然或恶意的破坏、更改、泄露的操作,或者有能力快速恢复,使得该信息系统能
够连续可靠地运行,保证该系统能够为用户提供服务,信息服务不会中断,保证
系统服务的正确性和连续性。
在20 世纪初,信息安全的概念没有被提炼和定义。在经历了一个漫长的历
史发展阶段后,在20 世纪90 年代初,信息安全的概念才得到了进一步深化。进
入21 世纪后,随着互联网的不断发展,各类信息系统以及信息技术不断增加,
络上的信息数据进入爆炸式增长阶段,信息安全问题也逐渐引起重视。现在,(网) 如何确保信息安全已成为全球重点关注的问题。国际上的发达国家对于信息
安全的研究起步较早,美国、日本等发达国家或地区已经投入了大量的资源进
行网络安全技术的研究。近年来,我国对信息安全的研究也已经上升到新的高
度,取得了诸多的成果,并得以在实际中推广应用。
如图3.信息安全基础特性如下。
1所示,
(1)保密性(Anonymity): 指信息按给定要求不泄露给非授权的个人、实体
的过程,且提供其利用的特性,即杜绝有用信息泄露给非授权个人或实体,强调
有用信息只被授权对象使用的特征。
(2)完整性(nert:指信息在传输、存储和处理的过程中,始终保
Itgiy)交换、
持未被修改、未被破坏和未丢失,即始终保持信息原样性,使信息能正确生成、
存储、传输,信息安全的基本特性就是指信息的完整性。
38区块链安全
图3.1信息安全基础特性
(3)可用性(Usability):指信息可以被授权的实体正确访问,并可以按要求正常使
用,或者在非正常情况下也能够恢复使用的特征,即在系统正常运行时能正确存取所需信
息,当系统遭受攻击者攻击或破坏时,也能够迅速恢复并且投入使用,提供正常服务。信
息的可用性是衡量信息系统在面向用户时的一种安全性能指标。
(4)可控性(Controlability):指信息以及系统具体内容在网络系统中流通时,系统
可以实现有效控制的特性,即系统需要实现对其中的任何信息在一定传输范围和存放空
间内有效控制。实施有效控制采用的方法包括传播站点以及传播内容监控这两类,最常
用的方法还包括基于密码的托管政策,当加密算法交由第三方管理时,算法步骤就必须严
格按规定可控执行。
(5)不可否认性(Non-repudiation):指任意通信双方在消息的交互过程中,所有参
与者都不可能否认或抵赖本人的真实身份和其提供消息进行否认和抵赖,这需要对参与
者本身的身份进行确定,保证参与者所提供的信息的真实同一性和其原样性。
3.密码学数学基础
2
本节将介绍密码学中所需的数论基础知识。如前所述,密码学基础是构建区块链技
术的基石。现代密码理论中大部分方案是基于安全假设,即密码学方案的安全性可以被
规约到一个困难问题,该困难问题在多项式时间内都无法被解决。困难问题设计的本质
是基于数论,下面介绍有关数论的基础知识。
2.群基本定义及性质
3.1
1.群的定义
在非空集合
G
上定义一个二元运算符“·”,并且该集合满足下面4个属性。
b∈G, b∈G。
(1)封闭性:对于任意a,有
a
·
第3章区块链密码学基础39(2)结合律:对于任意a,b,c∈G,有a·b· c=(a·b)· c=a·(b· c) 。
(3)存在单位元:.i∈G,对于元素a∈G,都可以得到a·i=i· a=a。
(4)存在逆元:对于任意a∈G,存在一个元素a-1∈G,使得a· a-1=a-1· a=i。
a-1则为元素a在集合G上的逆元。
如果某个代数系统满足上述所有性质,则称其为群(Group), 记为(G,·) 。
交换律:对任意的a,b∈G,有a·b=b· a。
如果某个群除了满足以上封闭性、结合律、存在单位元、存在逆元4个属性之外,还满
足交换律,则称该群为交换群或者阿贝尔群。
2.群的性质
(1)群中的单位元是唯一的。
(2)群中任一元素的逆元是唯一的。
(3)对于任意的a,b,c∈G,如果有a·b=a· c,则有b=c。
(4)对于任意的a,b∈G,有(a·b)-1=b-1· a-1。
(5)对于任意的a∈G,元素a与自身的n次运算,其中n∈N,可以表示为
an=a·a·…·a
这里需要注意n=0的情况,定义a0=i,其中元素i是G中的单位元。
如果分别使用普通乘法和普通加法的符号来定义G中的二元运算“ +”和“·”,则对
于乘法运算,an表示a的n次幂,加法运算na=a+a+…+a,可以得到如表3.1所示的
性质。
表3.1普通乘法与普通加法的运算性质
普通乘法
n
aam
=am+
n
aamn
(
n
)
m
=
n
a
-
a
-1)
n
=(
普通加法
na+mn+m)a=(
a
m(a)
n=mna
(-n)n(a)
a=
如果群
G
中包含的所有元素个数是一个有限整数,则称
G
为有限群,否则称为无限
群。有限群
G
中元素的个数,称为这个有限群的阶。若
G
是一个有限群,它的阶表示
为|G|。
特别地,如果一个集合在某种运算上是一个群,但其在其他运算上未必是一个群。
3.
有限域
有限域指的是包含有限个元素的域。显然,Zq
(就是一个有限域。可以得
q
为素数)
到关于有限域的性质为,有限域的阶必为素数的幂。举例而言,假设
F
是一个有限域,则
存在素数
p
和正整数n,使得|F|=pn
,将这个有限域记为Fn
或GF(pn
)。反之,对于每
一个这样的素数幂pn
,都存在这样唯一的阶为pn
的有限域(p) 。当n=1 时,把有限域
GF(p)称为素数域。密码学中普遍采用的域是阶为
p
的素数域GF(p)和特征为2的
GF(2m
)域。
40区块链安全
3.2.2整数群、椭圆曲线群和双线性映射群
1.整数群
由整数集合Z构成的群,即为整数群。整数群有如下的一些性质。
(1)整数集合Z在加法运算上可以构成阿贝尔群,写作(Z,+),它的全部元素都是由
1生成的,0是这个群的单位元,每一个元素的逆元是自身的相反数。
(2)整数集合Z在乘法运算上不能够构成群,因为除了元素1和-1外,其他所有元
素的乘法逆元都不存在。
特别地,(Zp,+)称为模p的整数群,它包含的元素是模p的p个剩余类{[0],[1],
[2],…,[p-1]}。显然,Zp是一个加法循环群,Zp=<[1]>,其中[1]就是它的一个生
成元。对于任何与p互素的整数r,[r]都是Zp的生成元。
2.椭圆曲线群
椭圆曲线密码(EllipticCurvesCryptography,ECC)是基于椭圆曲线数学理论的算
法,属于公钥加密算法,是迄今为止被实践证明安全有效的三类公钥密码体制之一,其以
高效性能在实际系统中被广泛应用。椭圆曲线离散对数问题的困难性决定了ECC算法
的安全性。椭圆曲线离散对数问题是一个比大整数因子分解问题(RSA算法基础)以及
离散对数问题(DSA算法基础)更困难的问题。相比于RSA算法,ECC算法的优势在于
其能够用更少的位长度获得与RSA同等强度的安全性,因此ECC算法可以节约计算开
销、密钥管理存储开销以及通信带宽,使得ECC算法可以适
用于一些计算能力较弱或者对移动性要求较高的设备,例如
手机、智能卡等小型或移动型设备。
所有满足椭圆曲线方程点的集合就构成了椭圆曲线群,
下面将介绍3种基于不同域的椭圆曲线。
1)实数域上的椭圆曲线
椭圆曲线并非字面上理解的椭圆,只是它的曲线方程与
图3.椭圆曲线示意图
计算椭圆的周长方程类似(见图3.椭圆曲线
2
ierstra2)。一般来说,
指的就是维尔斯特拉斯(Wes)方程,即
y2+ay+by=x3+cx+
e
3.
b,c,
解集(y)
x2+d(1)
椭圆曲线是由满足方程的全体(x) x,再加上一个无穷远点
O
构成的集合,该方
程中的参数a,
d
是满足某些特定条件的实数。上述曲线方程通过坐标转化为以下
的简化式,即
y=x3+a(2)
2x+
b
3.
由这个方程确定的椭圆曲线记为E(b)或E。椭圆曲线是关于
x
轴对称的。椭圆
a,
曲线的加法运算可以定义为:如果椭圆曲线上3个点位于同一直线,那么它们的和为O。
椭圆曲线上的加法也具有加法运算的一般性质,如交换律、结合律等。
第3章区块链密码学基础41
2)有限域GF(p)上的椭圆曲线
3.x,有限域GF(p)上的椭圆曲线定义为满足式(3)同余式的所有几何解(y)∈
GF(p)和一个无穷远点O=(x,∞)构成的集合:
2≡x3+a(3)
yx+
b
(modp)3.
式中,
p
是一个大于2160 a,p) a3+27mo的常数。这
的素数;b∈GF(是满足4b2≠0(dp)
类椭圆曲线通常用Ep
a,来表示,
Ep
a,
(b)
x,
即
x+
b
(3.(b)={(y)∪O|y2≡x3+amodp)} (4)
该椭圆曲线上只有有限个点数
N
(称为椭圆曲线的阶,包含有无穷远点)。
N
越大,
安全性越高,即群中元素越多,越能抵抗穷举搜索攻击。
比特币系统的区块链实现采用的是椭圆曲线secp256k1,secp256k1 是基于有限域
GF(p)上的椭圆曲线,其中p=2256-232-29-28-27-26-24-1。
3)有限域GF(2m
)上的椭圆曲线
有限域GF(2m
)中的元素是
m
位的字符串,这些字符串可以表示为系数在GF(2)上
的多项式:
am-2+
…+a1x+a0∶ai
∈{3.
{1xm-1+am-2xm-0,1}} (5)
GF(2m
)3.的所有几何解(y)∈GF(
m
)和一
上的椭圆曲线是定义为满足同余式(6) x,2
个无穷远点O=(x,∞)构成的集合。
6)
其中,a,
m
)
y2+xy=x3+ax2+
b m
(b)来表示,
(3.
m>160,b∈GF(2且b≠0 。这类椭圆曲线通常可以用E2a,
E2b)={(y)∪O|y2+xy=x2+b} 7)
m
(a,x,x3+a(3(即) .
3.
双线性映射群
双线性映射也称双线性配对,一个双线性映射是由两个向量空间中的元素,一起生成
第三个向量空间中的一个元素的函数,并且该函数对每个参数都是线性的。总而言之,给
出一个双线性群组的定义(GT,g1,e), 其中G1,G2 和GT 是阶为素数
p
的
G1,G2,p,g2,
乘法循环群,g1 和g2 分别是G1 和G2 的一个生成元。一个映射e:G1×G2→GT 称为双
线性映射,当它满足如下3个性质。
aba
(1)双线性:对于.a,
p
, 1,g=g1,
b
。
b∈Z均有e(g2)e(g2)
(2)非退化性:.g1∈G1,使得e(g2)≠1 。
g2∈G2, g1,
(3)可计算性:对于.u∈G1,u,
v∈G2,存在有效的算法计算e(v)
。
若G1=G2,则称这个双线性映射是对称的,否则是非对称的
。
3.密码学困难问题
在密码学中,几乎所有的加密系统的安全性都建立在计算问题的困难性假设基础
上。这些困难性假设问题,经过专家的长期研究,认为从群论的角度上是计算困难的,
因为它与计算复杂度理论存在着密切的联系。随着计算机技术的不断发展,这些假设
是否成立,仍然是密码学的一个重要的研究课题。接下来将主要介绍有关群论方面的
42区块链安全
困难性问题。
3.3.1离散对数问题
基于离散对数的公钥加密算法作为常用的公钥加密算法之一,其加密算法的安全性
要远远高于基于大整数分解的RSA加密算法,而且离散对数问题(DiscreteLogarithm
Problem,DLP)的计算复杂度要比大整数分解问题更高。经过多年研究,人们无法构造
出一个概率多项式时间来解决离散对数问题的方案。
1.离散对数问题定义
离散对数问题的定义为:当给定一个素数p,以及有限域Zp上的一个本原元a时,
对Zp上的任意正整数b,都可以找到唯一的整数c,0≤c≤p-2,使得ac≡b(modp),通
常用logab来表示c。一般而言,如果仔细选择p,则可以认为该问题是难解的,目前还没
有找到可以在多项式时间内计算离散对数问题的算法。为了抵抗已知的攻击,选择的素
数p需要满足以下两个条件:一是为至少150位的十进制整数;二是p-1至少有一个大
的素数因子。
2.离散对数问题性质
离散对数问题的困难性与有限域上的生成元无关,任何可以计算loab的离散对数算
法同样可以用来计算任意其他底数的离散对数问题。
g
3.2
大整数分解问题
3.
大整数分解问题(tgrFcoiainPolIFP)指的是对于任意给定的两个大
Ineeatrztorbem,
素数的乘积,找出该乘积的因子,这个问题是困难的。大整数分解问题是数论中的一个基
本问题,普遍认为不存在高效的概率多项式时间算法能够分解一个大整数,因此它是一个
非常重要的研究问题。
将大整数分解问题具体定义为:任意选定两个长度为
λ
的大素数
p
和q,并计算n=
pq。对于给定n, el(使得
n
能够被分解为
p
乘以
q
的概
gl(
若存在一个可忽略的函数
则可以称该大整数
n
的分解问题是一个困难问题
ngλ),
。
率不大于neλ),
3.3
CDH/DDH
问题
3.
计算Difie-Helman(ComputationalDifie-Helman,CDH)假设是WhitfieldDifie
和MartinHelman两位教授在构造密钥协议协商的时候提出来的。一般把任意群
G
的
三元素组(gx
,gxy
) g∈
G
是一个生成
gy
,称为DH组。对于任意阶为素数
q
的循环群G,
gY∈G,=gY=
元,二元函数dh:G2→
G
的定义为:随机选择两个元素X,令Xx
,gy
,计
算dhg
(X,=
y
。CDH问题的困难性指的是在已知G,gx
,计算二元
Y)gxg,gy
的情况下,
函数dhg
是困难的, el(使得计算出二元函数dhg
不大于negλ)。
即存在一个可忽略的函数ngλ), 的概率
l(
判定Difie-Helman(DecisionalDifie-Helman,DDH)假设是CDH假设的判定形
第3章区块链密码学基础43
式,也就是计算问题对应的判定问题,用来判断不可分辨性。DDH假设具体定义如下:
对于任意阶为素数
q
的循环群G,随机选取3个元素
X
,Z∈G,
g∈
G
是一个生成元, Y,
其中X=gY=gy
,且有dhg
=gy
。存在一个可忽略的函数negl(λ),使得区分Z=dhg x
,xgλ)。
或者
Z
是随机选取的概率不大于nel(
3.4
BDH/DBDH
问题
3.
双线性Difie-Helman(BilinearDifie-Helman,BDH)问题是对给定的3个元素
ab
a
,
b
,
c
,计算e(g,g)
c
。具体定义如下。
计算BDH假设是对于任意阶为素数
q
的循环群G1,G2,G3,其中g∈G1,h∈G2 是
两个生成元,存在一个可高效计算的同构φ:G1→G2,使得对于生成元g,h,有φ(g)=
a
,
c
,hb
,b
ggg
a
,ac
h。随机选择a,b,c∈Zq
,有gghBDH问题的难解性在于计算e(g,h)是困
难的,即存在一个可忽略的函数ngλ), g,abc的概率不大于ngλ)。
el(使得计算出e(h)el(
同样地,BDH假设的判定形式是DBDH(DecisionalBilinearDifie-Helman)假设。
对于任意阶为素数
q
的循环群G1,G2,其中g∈G1,存在一个
G3, h∈G2 是两个生成元,
可高效计算的同构φ:G1→G2,使得对于生成元g,h,有φ(g)=h。随机选择a,c∈
b,
ZqW
∈G3, ghg,h)egl(
,已知ga
,c,
a
,hb
和e(abc,存在一个可忽略的函数nλ),使得区分
W
=e(h)el(
g,abc
或者
W
是随机选取的概率不大于ngλ)。
3.对称密码体制
4
4.基本概念
3.1
对称密码体制是一种传统的密码体制,也称私钥密码体制。在对称密码体制中,加
密和解密采用相同的密钥。由于加解密采用的密钥相同,所以通信的双方必须选择和
保存相同的密钥,并且双方密钥的传输必须通过安全信道,保证不会被攻击者窃听或
者截获,此外双方也必须信任对方都不会将密钥泄露出去。以此实现数据的保密性和
完整性。
3所示, 加密算法、
对称密码模型如图3.基本元素包含有原始的明文、密钥、密文、
解
密算法、信息发送者以及信息接收者。其中,传输加密信息的信道是不安全且公开的,
因
此发送者用于加密消息的密钥则需要通过安全的密钥交换渠道来传输给接收者
。
图3.对称密码模型
3
44区块链安全
发送者通过加密算法E根据输入的消息m和密钥k生成密文c:
c=Ek(m) (3.8)
接收者通过解密算法D根据输入的密文c和共同协商的密钥k恢复出明文m:
m=Dk(c) (3.9)
攻击者可以基于不安全的公开信道观察密文c,它无法接触到明文m或者密钥k,但
攻击者可以试图恢复明文m或者密钥k。由于加密算法和解密算法是公开的,假设攻击
者对某个特定的消息感兴趣,他可以针对性地通过分析方法(例如穷举攻击)分析出明文
m或者密钥k。
通过上述的例子可以知道,对称密码体制的安全性主要取决于以下两种因素。
(1)加密算法:加密算法无须保密,使得仅仅通过密文以及算法,而不通过密钥,就
想破译出明文是非常困难的。
(2)密钥:密钥的安全性决定了明文信息的安全性,因此密钥空间必须保证足够大。
对称密码体制的优势是不仅速度快,并且具有较高的保密强度,一些常用的对称加密
算法明显地快于当前任何非对称加密算法。此外,有些对称加密方案甚至可以达到经受
国家级破译力量的分析和攻击的安全性。对称密码体制的缺点在于,对称密码体制的安
全性是建立在它的密钥必须通过安全可靠的路径进行传输之上的,这样对称密码的密钥
安全传输和管理成了影响系统安全性的关键因素。
国际上经典的对称加密算法包括数据加密标准(DataEncryptionStandard,DES)算
法、三重数据加密标准(rpl或称为三重DES) 国际数据加密算法(
TieDES, 算法、IDEA )、
RC5 算法以及高级加密标准(AdvancedEncryptionStandard,AES)算法等。DES 算法由
美国国家标准局提出,主要应用场景是银行业的电子资金转账(EFT )。DES 是一个分组
密码算法,采用的是替换和移位的方法,并使用56 位的密钥,用于处理64 位的明文数据。
DES 算法的优势是加解密速度快、易于软件实现。但是,DES 算法的缺点是密钥过短,56
位的密钥长度会影响它的保密强度。为了克服这一缺点,提出了一系列的DES 变形算
法。如TripleDES 算法,它使用两个独立的56 位密钥对交换的信息进行3次加密,从而
使其有效长度达到112 位。类似于DES 算法,
IDEA 也是一种对称的数据块加密算法,
采用了128 位的密钥和8个循环,每轮加密都使用从完整的加密密钥中生成的一个子密
钥,同一算法既可用于加密又可用于解密。该算法本身的密码结构,使其具有对采用软件
实现和采用硬件实现同样快速的优势。此外,RC5 是一种具有可变字长、可变轮数和可
变密钥长度的对称分组密码算法。该算法的特点是使用依赖于数据的循环,安全性依赖
于循环运算和不同运算的混合使用。AES 算法在密码学中又称Rijndael加密法,已经作
为美国联邦政府采用的一种区块加密标准。该标准用来替代原先的DES 算法,现如今已
经被多方分析证明安全,且被全世界所使用。从2006 年开始,AES 算法已经正式取代了
DES 算法,成为对称密钥加密中最流行的算法之一。
第3章 区块链密码学基础 45
3.4.2 对称加密算法AES
美国国家标准与技术研究所(NationalInstituteofStandardsand Technology,
NIST)在1997年发起,向全球所有研究人员提出征集AES算法,用于取代DES算法。
NIST首先要求算法的分组长度为128位,允许3个不同的密钥大小:128位、192位或
256位,同时算法必须是可以公开的。2000年,NIST 通过对候选算法的安全性(是否基
于稳定的数学基础、无算法弱点、具备测试算法抗密码分析的强度、测试算法输出的随机
性)、性能(是否能在多种平台上以较快的速度实现)、大小(算法不能占用大量的存储空间
和内存)、实现特性(灵活性、可扩展性、硬件和软件适应性、算法的简单性等)等方面进行
综合评估,最终采用了两位比利时研究者VincentRijmen和JoanDaemen所提出的
Rijndael算法,NIST于2001年正式发布了AES算法。
AES算法作为分组密码算法的一种,即通过把明文分成一组一组的等长数据,每次
加密一组数据,直到加密完整个明文。在AES算法中,明文的分组长度只能是128位,也
就是说,每个分组为16字节(每字节8位)。密钥的长度则可以使用128位、192位或256
位。一般而言,加密轮数取决于密钥长度,即密钥长度不同,加密轮数也不同,如表3.2
所示。
表3.2 AES密钥标准
标 准密钥长度(32位) 分组长度(32位) 加密轮数
AES-128 4 4 10
AES-192 6 4 12
AES-256 8 4 14
AES算法涉及4种操作步骤:字节替代、行移位、列混淆和轮密钥加。下面给出4
种操作的详细描述。
1.字节替代
字节替代(SubBytes)是一种非线性变换,主要功能是通过S 盒来完成一字节到另一
字节的映射。其中,S 盒用于提供密码算法的混淆性。通过一个简单的对S 盒查询的操
作,它将输入或者中间态的每一字节映射成为另一字节。这种映射方法具体表述为:将
输入的字节的高4位作为S 盒的行值,低4位作为列值,然后输出S 盒或S-1盒中对应行
和列的元素。表3.3为S 盒,表3.4为S-1盒(S 盒的逆)。
S 盒和S-1盒都为16×16的矩阵,包含了8位所能表示的256个数的一个置换,完成
一个8位输入、8位输出的等位映射。字节替换的简单示意如式(3.10):
S0,0 S0,1 S0,2 S0,3
S1,0 S1,1 S1,2 S1,3
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2 S3,3
.
è
..... .
.
÷÷÷÷÷
→S 盒→
S'0
,0 S'0
,1 S'0
,2 S'0
,3
S'1
,0 S'1
,1 S'1
,2 S'1
,3
S'2
,0 S'2
,1 S'2
,2 S'2
,3
S'3
,0 S'3
,1 S'3
,2 S'3
,3
.
è
.....
.
.
÷÷÷÷÷
(3.10)
4
6
区块链安全
表3.
3 S
盒
列
行
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 0x
63
0x
7c
0x
77
0x
7b
0xf
2
0x6
b
0x6
f
0xc
5
0x3
0
0x0
1
0x6
7
0x2
b
0xf
e
0xd
7
0xa
b
0x7
6
1 0xc
a
0x8
2
0xc
9
0x7
d
0xf
a
0x5
9
0x4
7
0xf
0
0xa
d
0xd
4
0xa
2
0xa
f
0x9
c
0xa
4
0x7
2
0xc
0
2 0xb
7
0xf
d
0x9
3
0x2
6
0x3
6
0x3
f
0xf
7
0xc
c
0x3
4
0xa
5
0xe
5
0xf
1
0x7
l
0xd
8
0x3
1
0xl
5
3 0x0
4
0xc
7
0x2
3
0xc
3
0xl
8
0x9
6
0x0
5
0x9
a
0x0
7
0xl
2
0x8
0
0xe
2
0xe
b
0x2
7
0xb
2
0x7
5
4 0x0
9
0x8
3
0x2
c
0xl
a
0xl
b
0x6
e
0x5
a
0xa
0
0x5
2
0x3
b
0xd
6
0xb
3
0x2
9
0xe
3
0x2
f
0x8
4
5 0x5
3
0xd
1
0x0
0
0xe
d
0x2
0
0xf
c
0xb
1
0x5
b
0x6
a
0xc
b
0xb
e
0x3
9
0x4
a
0x4
c
0x5
8
0xc
f
6 0xd
0
0xe
f
0xa
a
0xf
b
0x4
3
0x4
d
0x3
3
0x8
5
0x4
5
0xf
9
0x0
2
0x7
f
0x5
0
0x3
c
0x9
f
0xa
8
7 0x5
1
0xa
3
0x4
0
0x8
f
0x9
2
0x9
d
0x3
8
0xf
5
0xb
c
0xb
6
0xd
a
0x2
1
0xl
0
0xf
f
0xf
3
0xd
2
8 0xc
d
0x0
c
0xl
3
0xe
c
0x5
f
0x9
7
0x4
4
0xl
7
0xc
4
0xa
7
0x7
e
0x3
d
0x6
4
0x5
d
0xl
9
0x7
3
9 0x6
0
0x8
1
0x4
f
0xd
c
0x2
2
0x2
a
0x9
0
0x8
8
0x4
6
0xe
e
0xb
8
0xl
4
0xd
e
0x5
e
0x0
b
0xd
b
A 0xe
0
0x3
2
0x3
a
0x0
a
0x4
9
0x0
6
0x2
4
0x5
c
0xc
2
0xd
3
0xa
c
0x6
2
0x9
1
0x9
5
0xe
4
0x7
9
B 0xe
7
0xc
8
0x3
7
0x6
d
0x8
d
0xd
5
0x4
e
0xa
9
0x6
c
0x5
6
0xf
4
0xe
a
0x6
5
0x7
a
0xa
e
0x0
8
C 0xb
a
0x7
8
0x2
5
0x2
e
0xl
c
0xa
6
0xb
4
0xc
6
0xe
8
0xd
d
0x7
4
0xl
f
0x4
b
0xb
d
0x8
b
0x8
a
D 0x7
0
0x3
e
0xb
5
0x6
6
0x4
8
0x0
3
0xf
6
0x0
e
0x6
1
0x3
5
0x5
7
0xb
9
0x8
6
0xc
1
0xl
d
0x9
e
E 0xe
1
0xf
8
0x9
8
0xl
1
0x6
9
0xd
9
0x8
e
0x9
4
0x9
b
0xl
e
0x8
7
0xe
9
0xc
e
0x5
5
0x2
8
0xd
f
F 0x8
c
0xa
l
0x8
9
0x0
d
0xb
f
0xe
6
0x4
2
0x6
8
0x4
l
0x9
9
0x2
d
0x0
f
0xb
0
0x5
4
0xb
b
0xl
6
第3章区块链密码学基础47
4
S
表3.1盒
列
行
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 0x5
2
0x0
9
0x6
a
0xd
5
0x3
0
0x3
6
0xa
5
0x3
8
0xb
f
0x4
0
0xa
3
0x9
e
0x8
1
0xf
3
0xd
7
0xf
b
1 0x7
c
0xe
3
0x3
9
0x8
2
0x9
b
0x2
f
0xf
f
0x8
7
0x3
4
0x8
e
0x4
3
0x4
4
0xc
4
0xd
e
0xe
9
0xc
b
2 0x5
4
0x7
b
0x9
4
0x3
2
0xa
6
0xc
2
0x2
3
0x3
d
0xe
e
0x4
c
0x9
5
0x0
b
0x4
2
0xf
a
0xc
3
0x4
e
3 0x0
8
0x2
e
0xa
1
0x6
6
0x2
8
0xd
9
0x2
4
0xb
2
0x7
6
0x5
b
0xa
2
0x4
9
0x6
d
0x8
b
0xd
1
0x2
5
4 0x7
2
0xf
8
0xf
6
0x6
4
0x8
6
0x6
8
0x9
8
0xl
6
0xd
4
0xa
4
0x5
c
0xc
c
0x5
d
0x6
5
0xb
6
0x9
2
5 0x6
c
0x7
0
0x4
8
0x5
0
0xf
d
0xe
d
0xb
9
0xd
a
0x5
e
0xl
5
0x4
6
0x5
7
0xa
7
0x8
d
0x9
d
0x8
4
6 0x9
0
0xd
8
0xa
b
0x0
0
0x8
c
0xb
c
0xd
3
0x0
a
0xf
7
0xe
4
0x5
8
0x0
5
0xb
8
0xb
3
0x4
5
0x0
6
7 0xd
0
0x2
c
0xl
e
0x8
f
0xc
a
0x3
f
0x0
f
0x0
2
0xc
1
0xa
f
0xb
d
0x0
3
0x0
1
0xl
3
0x8
a
0x6
b
8 0x3
a
0x9
1
0xl
1
0x4
1
0x4
f
0x6
7
0xd
c
0xe
a
0x9
7
0xf
2
0xc
f
0xc
e
0xf
0
0xb
4
0xe
6
0x7
3
9 0x9
6
0xa
c
0x7
4
0x2
2
0xe
7
0xa
d
0x3
5
0x8
5
0xe
2
0xf
9
0x3
7
0xe
8
0xl
c
0x7
5
0xd
f
0x6
e
A 0x4
7
0xf
1
0xl
a
0x7
1
0xl
d
0x2
9
0xc
5
0x8
9
0x6
f
0xb
7
0x6
2
0x0
e
0xa
a
0xl
8
0xb
e
0xl
b
B 0xf
c
0x5
6
0x3
e
0x4
b
0xc
6
0xd
2
0x7
9
0x2
0
0x9
a
0xd
b
0xc
0
0xf
e
0x7
8
0xc
d
0x5
a
0xf
4
C 0xl
f
0xd
d
0xa
8
0x3
3
0x8
8
0x0
7
0xc
7
0x3
1
0xb
1
0xl
2
0xl
0
0x5
9
0x2
7
0x8
0
0xe
c
0x5
f
D 0x6
0
0x5
1
0x7
f
0xa
9
0xl
9
0xb
5
0x4
a
0x0
d
0x2
d
0xe
5
0x7
a
0x9
f
0x9
3
0xc
9
0x9
c
0xe
f
E 0xa
0
0xe
0
0x3
b
0x4
d
0xa
e
0x2
a
0xf
5
0xb
0
0xc
8
0xe
b
0xb
b
0x3
c
0x8
3
0x5
3
0x9
9
0x6
1
F 0x1
7
0x2
b
0x0
4
0x7
e
0xb
a
0x7
7
0xd
6
0x2
6
0xe
1
0x6
9
0xl
4
0x6
3
0x5
5
0x2
1
0x0
c
0x7
d
48 区块链安全
与DES算法的S 盒相比,AES算法的S 盒具有严格的数学推导和计算,能进行代数
学上的定义,涉及了有限域GF(28)和系数在GF(28)上的多项式。
2.行移位
行移位(ShiftRows)的目的是实现一个4×4矩阵内部字节之间的置换,完成基于行
的循环位移操作,其具体操作:保持第一行不变,循环左移第二行1字节,循环左移第三
行2字节,循环左移第四行3字节。变换如式(3.11):
S0,0 S0,1 S0,2 S0,3
S1,0 S1,1 S1,2 S1,3
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2 S3,3
.
è
.....
.
.
÷÷÷÷÷
→
S0,0 S0,1 S0,2 S0,3
S1,1 S1,2 S1,3 S1,0
S2,2 S2,3 S2,0 S2,1
S3,3 S3,0 S3,1 S3,2
.
è
.....
.
.
÷÷÷÷÷
(3.11)
3.列混淆
列混淆(MixColumns)是将每一列的值与固定多项式进行乘法运算,为了确保运算结
果不会溢出定义域,运算中涉及的加法和乘法都是定义在GF(28)上的。列混淆可以用式
(3.12)进行描述。
02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02
.
è
....
.
.
.
÷÷÷÷
÷
S0,0 S0,1 S0,2 S0,3
S1,0 S1,1 S1,2 S1,3
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2 S3,3
.
è
.....
.
.
÷÷÷÷÷
=
S'0
,0 S'0
,1 S'0
,2 S'0
,3
S'1
,0 S'1
,1 S'1,2 S'1
,3
S'2
,0 S'2
,1 S'2
,2 S'2
,3
S'3
,0 S'3,1 S'3
,2 S'3
,3
.
è
.....
.
.
÷÷÷÷÷
(3.12)
在式(3.12)中,为确保每列的所有字节具有良好的混淆性,采用的矩阵的系数是基于
码字间的最大距离的线性编码。经过几轮列混淆变换和行移位变换后,所有的输入位与
所有的输出位线性相关。逆向列混淆变换可由式(3.13)矩阵乘法定义。
0E 0B 0D 09
09 0E 0B 0D
0D 09 0E 0B
0B 0D 09 0E
.
è
....
.
.
.
÷÷÷÷
÷
S0,0 S0,1 S0,2 S0,3
S1,0 S1,1 S1,2 S1,3
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2 S3,3
.
è
.....
.
.
÷÷÷÷÷
=
S'0
,0 S'0
,1 S'0
,2 S'0
,3
S'1
,0 S'1
,1 S'1
,2 S'1
,3
S'2
,0 S'2
,1 S'2
,2 S'2
,3
S'3
,0 S'3
,1 S'3
,2 S'3
,3
.
è
.....
.
.
÷÷÷÷÷
(3.13)
4.轮密钥加
轮密钥加的(AddRoundKey)目的是将轮密钥与状态进行逐位异或操作如式(3.14):
S0,0 S0,1 S0,2 S0,3
S1,0 S1,1 S1,2 S1,3
S2,0 S2,1 S2,2 S2,3
S3,0 S3,1 S3,2 S3,3
.
è
.....
.
.
÷÷÷÷÷
..
W0,0 W0,1 W0,2 W0,3
W1,0 W1,1 W1,2 W1,3
W2,0 W2,1 W2,2 W2,3
W3,0 W3,1 W3,2 W3,3
.
è
.....
.
.
÷÷÷÷÷
=
H0,0 H0,1 H0,2 H0,3
H1,1 H1,2 H1,3 H1,0
H2,2 H2,3 H2,0 H2,1
H3,3 H3,0 H3,1 H3,2
.
è
.....
.
.
÷÷÷÷÷
(3.14)
由此可见,轮密钥加的逆运算与正向的轮密钥加运算是完全一致的,这是由于异或运
算后进行逆操作得到其自身。轮密钥加变换虽然简单明了,但却能够影响S 数组中的每
第3章区块链密码学基础49
一位,满足对于对称加密算法要求的对于明文处理的扩散性。
以密钥长度为128 位的AES 算法为例,图3.4给出了AES 的加解密流程,从图中可
以看出:解密算法分别对应加密算法中的每一步的逆操作,即加解密所有操作的顺序正
好是相反的。正是由于这些过程,同时加上每步的加密算法与解密算法的操作均为互逆,
共同保证了算法的加解密的正确性。加解密中每轮的密钥分别由种子密钥经过密钥扩展
算法得到,算法中16 字节的明文、密文和轮子密钥都用一个4×4 的矩阵表示。
图3.
4
AES
算法流程图
50区块链安全
3.5哈希函数
3.5.1哈希函数定义
密码学上的哈希函数(HashFunction),也称杂凑函数。其目的是将任意长度的消息
m压缩或者映射为某一固定长度的消息摘要,表示为H(m),该映射是一个多对一的映
射。H(m)也可以当作消息m的指纹,一旦m发生变化,H(m)也会随之改变。
根据是否需要密钥,哈希函数可分为以下两类。
(1)带密钥的哈希函数:有两个不同的输入,分别为消息和密钥。一个带密钥的哈
希函数通常用来作为消息认证码,即消息验证码(MessageAuthenticationCode,MAC )。
(2)不带密钥的哈希函数:只有一个消息输入,这样产生的消息摘要必须被安全存
放,不能被篡改。
根据设计结构,哈希函数可以分为3类。
(1)标准哈希函数。
(2)基于分组加密的哈希函数。
(3)基于模数运算的哈希函数等。
目前,主要的标准哈希函数可以分为两类。
(1)MD系列的哈希函数,例如MD4 、MD5 、MDS 、HAVAL 、RIPEMD等。
(2)SHA系列的哈希函数,例如SHA-1、SHA-256 、SHA-384 、SHA-512等。
5.哈希函数主要性质
3.2
哈希函数
H
必须满足以下6种性质。
(1)
H
的输入可以是任何大小的数据块,即
H
的输入可以是任意长度的。
(2)
H
的输出是固定大小的数据块。
(3)对任意消息x,求
H
(x)是可行的,并可用软件或硬件实现。
(4)对任意给定的哈希值h,找到
x
且满足
H
(x)=h,计算上是不可行的。
(5)对任意给定的值x,找到y,满足
H
(x)=
H
(y)并且x≠y,计算上是不可行的。
(6)找到任意的x,使得
H
(=
H
(计算上是不可行的。
y
且x≠y, x)y),
基于以上性质,可以将哈希函数分为两大类:弱碰撞哈希函数和强碰撞哈希函数。
弱碰撞哈希函数与强碰撞哈希函数必须同时满足前3个条件,主要区别在于后3方面。
1.弱碰撞哈希函数
满足上面性质(4)和(5)的哈希函数,称这个哈希函数
H
(x)是弱碰撞的。
2.强碰撞哈希函数
满足上面性质(4)、(5)和(6)的哈希函数,称这个哈希函数
H
(x)是强碰撞的。
在以上的性质中,性质(4)的意义是指哈希函数是单向性的,通常也称抗原像性,那么
第3章区块链密码学基础51H(x)也是单向杂凑函数;性质(5)代表弱碰撞性,可以称为抗第二原像性;性质(6)代表
强碰撞性,也可以称为抗碰撞性,用来防止攻击者对哈希函数实施自由起始碰撞攻击,即
生日攻击。
3.5.3哈希函数安全性
哈希函数在密码系统中使用十分广泛,包括加密方案、签名方案等都有哈希函数的存
在,因此哈希函数也已经成为很多黑客攻击的目标。对哈希函数的攻击主要在于破坏其
某些特性。例如,可以根据其输出求得输入,找到某条消息使得它的输出与原消息的输出
相同,或者找到不同的两条消息,使它们的输出相同。最具有代表性的对哈希函数的攻击
为以下两种。
1.字典攻击
字典攻击(DictionaryAttack)的定义是,在破解密码或密钥过程中,通过逐一尝试用
户自定义词典中所有可能的密码(单词或短语),这种攻击方式称为字典攻击。字典攻击
与暴力破解相似,区别在于,暴力破解会逐一尝试所有可能的组合密码,没有预先预定好
的单词列表,而字典攻击会使用一个预先定义好的单词列表(可能的密码)进行逐一尝试。
因此,字典攻击对用单向哈希函数加密的口令文件特别有效。攻击者通过编制含有多达
几十万个常用口令的表,然后用单向哈希函数对所有口令进行运算,并将结果存储到文件
中,攻击者通过非法途径获得加密的口令文件后,比较这两个文件,观察是否有匹配的口
令密文,这种攻击方式的成功率非常高。
2.生日攻击
生日攻击(BirthdayAtack)的原理是一个统计问题。一个房间里有多少人才能够使
得最少有一人与你的生日相同的概率大于1/2呢? 答案是253 。那么应该有多少人才能
够使得他们中至少有两人的生日相同的概率大于1/2呢?23人即可。寻找特定生日的
某人,或者是寻找两个随机的具有相同生日的两个人,与对单向哈希函数进行穷举攻击的
方法是相同的原理:前者对应了给定消息
m
的哈希值
H
(m),攻击者不断生成其他消息
'
,以使得
H
(m)=
H
(');后者对应的场景是,攻击者寻找两个随机的消息
m
和m' , 并(m) 使得
H
(m)=
H (m'),(m) 而后者称为生日攻击,这种攻击方式没有利用哈希函数的结构
和任何代数弱性质,只依赖于消息摘要的长度,即哈希值的长度。为了抵抗生日攻击,哈
希函数安全性的一个必要条件就是消息摘要必须足够长。
5.哈希函数主要应用
3.4
在密码学中,哈希函数有非常多的应用场景,包含数据认证、数字签名、伪随机数生成
和密钥生成等。
1.数据认证
哈希函数的重要应用之一就是生成文件或者消息
m
的摘要值
H
(m),该值被安全地
52区块链安全
存储,对消息m的任意改动都可以通过对改动后的m进行相同的哈希运算而被检测出
来,这样的操作保证了数据的完整性,也可以实现对消息的安全认证。对于哈希函数的不
同应用,包括HMAC,即基于哈希函数的消息验证码,其基本思想就是用密钥和消息一起
进行哈希操作,确保消息的完整性,使得在传输过程中对消息的任何修改都能够被接收者
检测到。
2.数字签名
哈希函数经常被应用在数字签名算法中。在现实应用中,需要签名认证的消息m本
身非常大,如果直接在消息m上做数字签名效率会非常低。通常情况下,为实现对消息
m的高效数字签名,首先计算出m的哈希值H(m),然后采用私钥对H(m)进行签名操
作,所得到的Sig(H(m))就是用户对消息m的签名。利用哈希函数进行数字签名的优
势是,可以实现对于消息的不可否认性,消息发布者只能用自己的私钥对哈希值进行签
名,接收者使用发布者的公钥进行解密,从而确认消息确实由该消息发布者发出。
3.伪随机数生成
从哈希函数的定义来看,哈希函数具有生成随机性质的数据序列的特征。通过选择
一个随机函数,把消息的随机函数值作为它的哈希值来产生,从而得到伪随机数。因此,
哈希函数也可以用作伪随机数的生成器。
4.密钥生成
利用哈希函数的单向性,用旧的密钥计算出新的密钥序列,从而使得现有密钥具有泄
露后不危及先前所用的密钥的性质,也就是使用哈希函数能够产生具有前向安全的密钥。
总体而言,哈希函数在密码学的应用中一直发挥着重要的作用,在区块链中也有着十
分广泛的应用,如区块链中的链式结构就是通过让每一个区块包含上一个区块的区块头
哈希值来实现的。此外,区块链中的默克尔树构造、工作量证明算法、钱包地址等都用到
了哈希算法。
3.默克尔树
6
1.基本概念
默克尔树(MerkleTre),也称HashTre,是用于存储哈希值的二叉树。默克尔树
包含叶节点和非叶节点,其中叶节点用于存放数据块(例如,文件或者文件的集合)的哈希
值,所有非叶节点是其对应所有子节点的组合结果的哈希值。
图3.也就是叶节点, 需
5为一个默克尔树的结构。在树的最底层, 类似于哈希列表,
要计算的数据被分割成不同的数据块,将数据块的哈希值存放于叶节点。接着计算时并
不是直接计算叶节点的哈希值,而是把相邻的两个叶节点的哈希值合并成一个字符串,然
后运算这个合并字符串的哈希值。例如,图3.=
H
(=
H
(
5中H6H2,H3)
H
(L1),
第3章区块链密码学基础53H(L2)),从而得到一个“子哈希值”。如果最底层的叶节点总数不是双数,那么必然出现
一个无法配对的单身哈希数据块,这种情况就直接对它进行哈希运算,也能得到它的子哈
希值。以此类推,就可以得到数目更少的新一层的哈希值,最终必然形成一个哈希树结
构,直到树根的位置,就只剩一个根哈希值,称为默克尔树根节点值(MerkleTreeRoot)。
图3.5默克尔树示意图
2.主要特点
默克尔树相比其他数据结构,具有一些特殊的性质。
(1)默克尔树是一种树状结构,大多数是二叉树,也有可能是多叉树,但无论是几叉
树,它都具有树状结构的所有特点。
(2)默克尔树的所有叶节点的值是数据集合的单元数据的哈希值。
(3)默克尔树非叶节点的值是根据它左右子节点的值,按照特定的哈希算法计算
得出。
一般而言,通常采用SHA-2和MD5作为加密的哈希算法。但如果仅仅防止数据不
是蓄意的损坏或篡改,可以改用一些安全性较低但效率较高的校验和算法,如循环冗余校
验(CyclicRedundancyCheck,CRC )。
在区块链中,假设一个默克尔树包含
N
笔交易数据,当需要验证一笔指定的交易是
否存在于某一区块中时,参与者至多花费2log2(
N
)次的计算就可以得到结果。这主要是
由Merkle树的构建方式来决定的,它的叶节点值由交易数据的哈希计算得到,并自底向
上计算哈希值构建更新上一层节点的数值,直到计算得到默克尔树根节点值,并验证其是
否发生变化。假设区块中的交易数量为奇数,则可以重复某笔交易来获得偶数笔交易,避
免叶节点无法配对的现象出现,并实现默克尔树的构建。
3.布隆过滤器
7
1.基本概念
20世纪70年代,BurtonHowardBloom教授提出了布隆过滤器(BloomFilter)的概
念,它的核心包含一系列哈希映射函数和一个很长的二进制向量,用于快速检索判断一个
54区块链安全
元素是否存在于某个集合中。布隆过滤器的优点在于空间效率和查询效率非常高,远远
超过一般的算法,因为它在进行查询时,采用位数组表示一个集合,这样的算法结构大大
节省了存储空间,提高了效率,但它也有不足之处:删除困难,以及存在一定概率的误识
别,也就是假正例(FalsePositives)的现象,即当布隆过滤器经过运算向系统报告某一元
素在集合中时,事实上它判断错误,该元素并不在集合中,布隆过滤器将一个不属于集合
的元素误检测为集合中的元素。相对于假正例现象,布隆过滤器不会发生假反例(False
Negatives), 也就是如果一个元素不在查询集合中,那么布隆过滤器是不会向系统报告该
元素属于集合。换句话说,布隆过滤器判断一个元素不在集合中,就一定不在,但当它判
断一个元素在集合中,就存在一定的判断误差,可能导致结果不准确。布隆过滤器的优缺
点反映了它是用较小的错误率来换取较高的运算效率,适用能容忍容错率的应用场景,而
无法适用“零错误”的场景。
布隆过滤器的常用的应用场景包含:判别某个元素是否存在于一个集合中,为实现
这个目标,通常的做法是采用哈希表(HashTable)数据结构,它可以通过一个哈希函数
将一个元素映射成一个位阵列中的某个点,并且这些位阵列的初始值都为0,当有元素映
射到位阵列中的某一点时,就将这一点的值设置为1。因此,要知道某个集合中是否有该
元素,只需要判断这个点在哈希表中对应的位置是否为1,就可以知道集合中有没有该元
素。这就是布隆过滤器的基本思想,算法的具体过程如图3.6所示。将所有元素通过布
隆过滤器保存至集合中,然后通过比较确定该元素是否存在于该集合。链表、树等结构也
采用同样的方式进行判断。
图3.布隆过滤器
6
但采用这样的方式进行数据存储和查询,存在着一些难以避免的问题:首先,随着集
合中元素的增加,哈希表所需要的存储空间越来越大,检索速度也会变得越来越慢。其
次,这样的结构面临的另一个问题就是冲突,假设哈希函数是合适并且良好的,如果位阵
列长度为
m
个点,那么若想将冲突率降低到1%,这个哈希表就只能容纳m/100 个元素,
显然就无法实现所有空间有效的要求;为解决无法实现所有空间有效的问题,解决方法是
可以使用多个哈希函数,数据可以采用多个哈希函数进行映射存储,便可以实现空间有
效,正确判断某个元素是否在集合中。
2.
布隆过滤器的算法过程
(1)选取
k
个哈希函数,每个函数可以把目标数据
d
哈希为1个整数。
(2)初始化一个长度为
n
位的数组,每位初始化为0。
第3章区块链密码学基础55(3)在某个数据d加入集合时,用k个哈希函数计算出k个哈希值,并把数组中对应
的位置为1。
(4)在判断数据d是否存在于该集合时,用k个哈希函数计算出k个哈希值,并查询
数组中对应的位,如果所有的位都是1,则认为该key在集合中;反之,则不存在。
3.布隆过滤器的主要特点
布隆过滤器的优势有以下5点:①空间上的低存储量和时间上的高效性,布隆过滤
器的存储空间、插入和查询时间都是常数,相比于其他的数据结构,布隆过滤器有着天然
具备的高效性;②布隆过滤器中采用的哈希函数相互之间没有关系,具有硬件并行实现
的编辑性;③布隆过滤器不需要存储元素本身,因此对于某些保密要求非常严格的数据
和场合,在安全性上相比其他数据结构具有绝对优势;④布隆过滤器可以用于表示全集
数据,实现数据的完备性;⑤布隆过滤器还具备的特点是,当哈希函数的数量k和阵列数
量m相同时,使用同一组哈希函数的两个布隆过滤器的交并差运算可以使用位操作进行。
布隆过滤器也存在一定劣势:①随着存入的元素数量增加,数据查询的误算率也会
随之增加。②从布隆过滤器中安全地删除元素信息较为困难,通常采用的方法是把位列
阵变成整数数组,对插入元素进行计数,每插入一个元素相应的计数器加1,这样删除元
素时将计数器减1。然而,这样的操作可能导致信息的泄露,因为首先必须保证删除的元
而这一点单凭过滤器是无法保证的。
素的确在布隆过滤器里面,
3.公钥密码体制
8
3.1
基本概念
8.
20世纪70年代,WhitfieldDifie和MartinHelman在NewDirectionsinCryptography
中提出了公钥密码体制,又称非对称密码体制或公开密钥密码系统的概念,是现代密码学
蓬勃发展的关键一步,开创了一个全新的密码学时代。他们在这篇划时代的文章中做出
了如下设想:假设系统中有两个用户Alice和Bob,Alice拥有一对公钥kp(加密密钥)和
私钥ks(解密密钥),其中公钥可以在全网公开,私钥由Alice自己保存。当Bob想要发送
一条消息给Alice,同时他又不希望别人看到,Bob首先在系统中找到Alice的公钥kp,然
后用kp 对消息进行加密,再将加密后的密文传输给Alice。Alice收到密文后,使用自己
保存的私钥ks 对密文解密,就可以获得明文消息。如果存在攻击者截获了Bob发送给
Alice的密文消息,但由于它不知道Alice的私钥,也是没有办法解密密文、读取明文的。
在这个过程中,加密密钥是公开的,因此它和解密密钥必须不同,同时在已知加密密钥的
前提下,不能反推出解密密钥,从而保证密码体制的安全性。在对称密码体制中,系统的
通信双方需要提前通过安全信道交换彼此的密钥,但这一条件非常苛刻,现实生活中很难
找到绝对安全的信道,公钥密码体制的思想就很好地解决了这个问题,至此开启了现代密
码学的新篇章,相继出现了诸如RSA 、ECC和ElGamal等公钥密码方案。
如图3.7所示,数据发送者和数据接收者的通信使用公钥密码体制,明文
m
用加密
56
区块链安全
密钥kp 来加密,数据接收者则采用与加密密钥不同的解密密钥ks 来解密。
图3.公钥密码体制
7
若将公钥密码体制表示成一个五元组{
M
,C,
K
,EK
,DK
},则其数学公式满足以下
条件。
(1)
M
是可能的消息集合。
(2)
C
是可能的密文集合。
(3)密钥空间
K
是一个可能的密钥有限集。
(4)对于密钥空间
K
中的每一个元素K={K1,K2},都有与之对应的加密算法EK1和
解密算法DK2,使得对于任意明文m∈
M
都满足c=m),(
EK1(c∈C,并且有m=DK2c);
其中EK1是公开函数,K1 表示公钥,而DK2 是保密函数,K2 表示私钥,用户秘密保存。
公钥密码体制的核心问题便是如何对EK1和DK2进行描述。
3.2
Eal公钥加密
8.lGma
1984年,斯坦福大学的TatherElGamal提出ElGamal公钥密码体制,这种密码体制
不仅适用于加密算法,而且也能用于数字签名算法。TatherElGamal在提出ElGamal公
钥密码体制之后,于1985年设计出ElGamal数字签名方案,美国著名的数字签名算法
(DSA)就是ElGamal数字签名算法的演化。基于有限域上离散对数问题难以解决的特
性,ElGamal公钥密码体制的安全性得以保障。在ElGamal加密过程中,算法都会选择
一个随机数参与运算,产生密文,因此对于同一个消息,每次加密后得到的密文都是不同
的,攻击者不仅不能从密文中获得任何明文信息,也不能通过观测密文来判断加密的是否
是同一个明文。此外,加密算法产生的密文形式包含两部分,一个可以看作是Difie
Helman的密钥交换,另一个是对明文的隐藏,所以密文的长度是明文长度的两倍。下面
是ElGamal公钥加密算法的详细描述。
(1)密钥产生:对一个大素数,有限域GF(p)上的离散对数问题是难以解决的。首
先任选一个大素数
p
和GF(p)上的生成元α。将参数
p
和
α
公布出去,选择一个随机整
数
d
作为私钥,2≤d≤p-2。计算y=αd
modp,选取
y
为公钥。
(2)ElGamal加密:对明文
M
加密,随机地选取一个整数k,2≤k≤
p
-2,使用
式(3.计算
C1=αk
modp
(3.
15)
C2=
M
· yk
modp
15)
最后,得到密文为C=(C1,C2)。
amaC2/Cd
(3)ElGl解密:计算
M
=1modp,可以由密文得明文
M
。