第
5
章
物联网安全基础———数据完整性检验
无论是对称密码方案或非对称密码方案,都是保护传输、存储数据的机密
性,即实现安全通信。然而在现实中,仅仅保护数据的机密性是不够的。使用
可以保护通信的内容不被攻击者获知。但对于接收者,如何验证所
加密方案,
接收到的数据是指定的发送方发送的呢? 在实际应用中,攻击者可能对传输中
的加密信息进行篡改,令接收方得到错误的加密信息。因此,如何让接收者验
证接收到的消息确实是指定的发送方产生的,在实际的应用中与安全通信同样
重要。由于数据加密与数据完整性检验所要达到的目标是不同的,因此要采用
不同的技术手段。在本章中,先介绍广泛使用在数据完整性检验及其他领域中
的哈希函数,再介绍两种数据完整性检验的方法,即基于对称密钥的消息认证
码和基于非对称密钥的数字签名。这两种方法也刚好与数据加密技术中的对
称加密和公钥加密相对应。
5.哈希函数与伪随机函数
1
1.哈希函数
5.1
哈希函数(HashFunction)也称散列函数,是一种将任意长度的字符串压缩
成为固定长度的短字符串的函数,有时这个短字符串也称消息的摘要。哈希函
数广泛使用在数据结构中用于构造哈希表(HashTable)等。哈希函数的一个
重要性质就是抗碰撞性。在哈希表中,希望两个不同的值落在同一个位置的概
率尽可能小,即尽量避免碰撞的发生。而密码学中的哈希函数则希望碰撞发
生的概率是可忽略的,即需要更强的抗碰撞性要求。非正式地讲,一个安全的
哈希函数应当满足几乎不可能找到不同的两个值x1,x2,使它们的哈希结果
相等。安全的哈希函数对构造安全的数字签名方案至关重要,几乎所有安全
的数字签名方案都需要用到哈希函数。
定义5.哈希函数。一个哈希函数由一对概率多项式算法(HGn,
H
)组
1
e
成,并且满足下面两个条件。
(1)HGen是一个概率算法,其输入为安全参数λ,输出一个密钥s。
第5章物联网安全基础———数据完整性检验69(2)H是一个确定性算法,对于确定的s和输入x∈{0,1}* ,输出Hs(x)={0,1}l(λ)
的字符串。其中,l(λ)是一个λ的多项式。
需要注意的是,s虽然称为密钥,但是在一般的应用中由于不需要保密的,因此s经
常省略,直接将H称为哈希算法。
在密码学中,使用以下3种安全定义来表示一个哈希函数所达到的安全强度。
(1)单向性(One-Way):给定哈希函数H和一个哈希值y,如果寻找一个原像x,使
H(x)=y在计算上是不可行的,则称H是单向的,也称抗原像(PreimageResistant)攻
击的。
(2)弱抗碰撞性(WeakCollision-Resistant):给定哈希函数H和一个原像x,找到
另一个x',使H(x')=H(x)在计算上是不可行的,则称H具有弱抗碰撞性,也称可抵
抗第二原像(SecondPreimageResistant)攻击。
(3)强抗碰撞性(StrongCollision-Resistant):给定哈希函数H,找到任意两个不同
的x、x',使H(x')=H(x)在计算上是不可行的,则称H具有强抗碰撞性。
实际上,当约定哈希函数中输入的长度大于输出的长度时(即哈希函数是一个压缩算
法),任何一个强抗碰撞性的哈希函数都具有弱抗碰撞性和单向性,而任何一个弱抗碰撞
性的哈希函数都是单向的,即抗原像攻击的。这3种安全定义的强度逐级增强,其中强抗
碰撞性是最强的安全定义。
哈希函数的通用攻击方法是生日攻击。在不考虑构造安全性的情况下,哈希函数的
安全强度与输出的长度密切相关。常见的安全哈希函数有MD家族(MD4 、MD5)与
SHA家族(SHA1 、SHA2 、SHA3 )。其中MD4 、MD5以及SHA1已经被认为是不安全的
哈希函数,且无法保证抗碰撞性。现代的攻击方法可以在几分钟之内找到MD4 、MD5中
有效的碰撞。如何构造和攻击哈希函数是属于密码学领域的研究方向,这部分内容超出
了本书的范围。基于目前的研究,普遍认为SHA2(SHA256 、SHA384 、SHA512 )、SHA3
哈希函数是安全的,而MD家族及SHA1哈希函数是不安全的。
5.2
伪随机函数
1.
在4.3节,我们讲到使用伪随机生成器来产生安全的序列密码。与伪随机生成器,
2.
伪随机函数(PseudorandomFunction)也是一种产生随机字符串的函数。伪随机函数可
以接收任意长度的输入,并且输出一个随机的字符串。一个安全的伪随机函数,其输出应
当与真正的随机字符串是不可区分的。伪随机函数与哈希函数类似,都是确定性的算法。
对于确定性的算法,讨论其伪随机性是无意义的,实际上伪随机函数输出的伪随机性其实
是针对函数输出的分布。因此伪随机函数的输入还需要包括一个密钥。
定义5.伪随机函数。一个伪随机函数
F
是一个确定性的函数,对于确定的输入
2
x∈{0,1}*和密钥k∈{0,1}*,其输出为固定的值y∈{0,1}*,即
***
F:{0,1}×{0,1}→{0,1}
上述对伪随机函数的定义是一个一般形式的定义。而在实际使用中,密钥的长度往
往会与安全参数相关,并且其输入和输出均为固定长度。则对于一个确定性的密钥k,伪
随机函数可以定义为Fk
:{0,1}0,1}λ),此处l(·)为关于输入长度
λ
的多项式。
λ
→{l(
70 物联网安全:原理与技术
伪随机函数作为一种基本原语,在密码学中具有十分重要的作用。基于伪随机函数,
可以构造安全的加密方案、消息认证码方案等。在4.2节,介绍了对称密码和一些常见的
密码方案。实际上,利用一个安全的伪随机函数可以一般化地构造一个安全的对称加密
方案。方便起见,假设F 为一个输入、密钥和输出长度均为λ 的定长伪随机函数,则基于
F 构造的对称加密方案如下。
(1)Gen(λ):密钥生成算法。算法输入安全参数λ,然后输出一个随机密钥k∈
{0,1}λ。
(2)Enc(k,m ):加密算法。算法输入对称密钥k∈{0,1}λ 和加密消息m ∈{0,1}λ,
输出密文:
c=(r,Fk(r)..m )
其中,r 是长度为λ 的随机字符串。
(3)Dec(k,c):解密算法。算法输入对称密钥k∈{0,1}λ和一个密文c=c( 1,c2 ) ,输
出明文:
m =Fk(c1)..c2
在上述加密构造中,消息和一个随机值r 的伪随机函数输出Fk (r)进行异或,从而被
隐藏起来。在每次加密过程中,随机值r 都是均匀随机从{0,1}λ空间中选取的。因此,即
使加密同一个消息,也会得到完全不同的密文。实际上,如果伪随机函数是安全的,这种
加密方法其实达到了选择明文攻击安全。
5.2 消息认证码
5.2.1 消息认证码的基本概念
正如前面所提到的,加密并不能保证数据的完整性。利用加密方案,可以使通信双方
在公开信道上进行消息的传输,并且不用担心通信内容被监听者获取。然而这并不能保
证恶意的攻击者对通信的内容进行篡改(攻击者不需要知道通信的内容是什么就可以篡
改通信内容)。例如,在使用公钥密码的通信系统中,攻击者可以简单地拦截发送方发送
的密文,并替换为自己想要接收者收到的内容,从而使通信双方遭受巨大的损失。即使使
用对称加密方案,攻击者仍然可以通过翻转密文中的某些位,使解密的结果完全不同。因
此,加密无法保证数据的完整性,并且所有的加密方案单独使用都无法保证数据的完
整性。为
了实现数据完整性验证,就需要额外的验证机制来检查通信的消息是否被篡改。
消息认证码可以实现:如果有攻击者在数据传输过程中修改了数据,接收者能够以极大
的概率检测出来。消息认证码与对称加密相似,都假设通信的双方掌握了其他人不知道
的秘密信息,即共享一个密钥。在这个前提下,发送消息的一方使用这个共享密钥,对消
息产生认证标签,然后将消息和标签一起发送给接收方(为了保证机密性,可以对消息和
标签进行加密)。消息接收方收到消息和标签后,使用共享的公私钥对消息和标签进行验
证,从而得出该消息的来源是否可靠。
第5章物联网安全基础———数据完整性检验71
定义5.3消息认证码。一个消息认证码(MessageAuthenticationCode,MAC)由一
组概率多项式算法(Gen,Mac,Verify)组成,并满足下面3个条件。
(1)Gen算法。密钥生成算法是一个概率算法,其输入为安全参数λ,输出一个密
钥k。
(2)Mac算法。标签生成算法同样是一个概率算法,其输入为密钥k和一个消息
m∈{0,1}* ,输出一个关于消息m的标签t。
(3)Verify算法。验证算法是一个确定性算法,其输入为密钥k、消息m和消息的标
签t,输出为1位,意味着标签t是否有效。
消息认证码的正确性:对于任意的安全参数λ、任意长度的消息m∈{0,1}*和密钥
k←Gen(λ),都有Verify(k,m,Mac(k,m))=1。
类似加密方案的安全性定义,消息认证码的安全性也从方案所要达到的目标以及攻
击者的能力两方面来定义。对于攻击者的能力,一般总是约束攻击者为概率多项式时间
(PPT)的攻击者。考虑消息认证码的目的是保证消息来源总是可靠的,因此一个攻击者
的目标则是伪造一个消息m*和相应的标签t* ,使它们能够通过Verify算法的检验。为
此,允许攻击者适应性地选择消息,并获得对应的标签帮助其攻击消息认证码。这种攻击
者称为适应性概率多项式攻击者,而这种攻击方式则称为适应性选择消息攻击。而消息
认证码所要达到的目标则是让攻击者无法伪造一对有效的消息和标签,即达到存在性不
可伪造。因此,一个安全的消息认证码的安全需求是在适应性选择消息攻击下达到存在
性不可伪造。
重放攻击。当攻击者获取到消息和相应的标签后,可以重新将这组消息和标签发送
给接收方。在重放过程中,攻击者没有对消息或标签进行任何的修改,因此这组消息和标
签可以合法地通过Verify算法的检验。对于没有合理设计的系统,重放攻击是一种有效
且直接的攻击方式,往往会对系统造成极大影响。消息认证码无法抵抗重放攻击。这是
因为消息认证码只对消息本身进行认证,而不考虑其状态。
抵抗重放攻击的方法一般有两种,即在消息中加入序列号或时间戳。序列号技术的
基本思路是对每个消息都进行编号,任何被认证过的消息序号都会被接收者存储。当接
收者收到的消息包含已经认证过的序号时,就可以认为该消息被重放了。使用序列号方
式的缺点是接收者必须存储消息序列,会产生额外的存储开销。因此在实际使用中,往往
会在消息中加入时间戳。此时,发送者和接收者之间需要同步一个时钟。发送者发送消
息时会将当前时间附加在消息中,进行认证产生标签。而接收者在收到消息时,除了验证
标签的有效性外,还要验证消息中的时间是否在一个合理的时间区间中;否则就认为这是
一个不合法的消息。时间戳也只能在一定程度上抵抗重放攻击。当攻击者的重放速度很
快时(在合法的时间区间内进行重放),攻击依然可能有效。
5.2
常见的消息认证码方案
2.
1.CBC-MAC方案
在4.2节对称密码部分介绍了密码分组链接(Cipher-BlockChaining,CBC)模式,
72
物联网安全:原理与技术
CBC-MAC 方案与其构造十分相似,主要用于处理较长消息时使用。设消息
m
的长度为
lλ,其中
λ
是每个消息分组的长度,并且MAC 标签的长度只有λ。CBC-MAC 方案基于
带密钥的伪随机函数。在5.2节中,介绍了如何使用伪随机函数构造安全的对称加密
1.
方案,因此很多时候,在构造CBC-MAC 方案时也可以使用对称加密方案来代替伪随机
函数。不失一般性,我们假设
F
为一个输入、密钥和输出长度均为
λ
的定长伪随机函数。
则基于伪随机函数
F
构造的CBC-MAC 方案标签生成过程如图5.CBC-MAC 构
1所示,
造方法如下。
图5.1
CBC-MAC
方案标签生成过程
(1)Gn:算法输入安全参数λ, 0,
λ
。
e然后输出一个随机密钥k∈{1}
(2)Mac:对于一个长度为lλ
的消息m,将消息分为
l
份,每份消息mi长度均为λ,并
令
λ
,迭代计算tFk
(1..mi),1≤i≤l。输出t。
t0=0i=ti-=t(3)Verify:对于输入密钥k、消息
m
和标签t,当且仅当(l) t=Mak,m)时输出1,
则输出0。
c(否
在CBC-MAC 方案中,使用了伪随机函数作为构造组件。标签生成算法最终的输出
只有最后一个区块的标签tl,前面l-1个区块的标签都不需要发送给接收者。这是因为
接收者不需要中间的标签,即可验证消息的有效性。此外,这部分标签如果被中间的攻击
者拦截,反而会导致方案不安全。例如,攻击者通过获取标签t-1,可以让接收者通过消息前
(-
λ
位的验证, 虽然新消原始消息的一部分)。
l1)即产生了对新消息的合法标签( 息为(l)
如果底层的伪随机函数(或对称加密方案)是安全的,那么上述所构造的CBC-MAC
方案对于固定长度的消息也是安全的,但是对于不固定长度的消息却是不安全的。也就
是说,对于任意一个密钥
k
只能对固定长度的消息或已知长度的消息产生消息认证码。
当上述CBC-MAC 方案在处理变长消息时,攻击者可以利用两个消息-认证码对(m1,t1)
和(m2,构造一个新的消息
m
* 使它的消息认证码为t2。不失一般性,假设消息m1和
t2) ,
m2的长度为l1λ
位和l2λ
位,mn
为mb
的第
n
个
λ
位。攻击者将构造的新消息
m
* 设置为
(2)m22 验证者去验证新的消息认证码对(t2) 在输入
2|…|ml2。当(b) -
m
*,时,
m
*
CBC-MAC 方案的第l1个块后会得到中间标签t1。这是因为
m
*的前l1λ
位刚好为m1。当
t1..m1
t1..m1
m1
中间标签t1与
m
* 的第l1+1 个块进行异或时,由于
m
*l1+1=2,因此有
m
*l1+1..
t1=m1。所以,计算
m
*的认证码时的第l1+1 个块输入伪随机函数的值与计算m2的认证码时的第(2) 一个块输入伪随机函数的值相同。最终得到
m
*的标签也与m2的标签相同,即
为t2。
将CBC-MAC 方案扩展到变长消息场景下的方法主要有3种:Input-lengthkey
第5章物联网安全基础———数据完整性检验73separation,Length-prepending和Encryptlastblock。在这3 种方法中,Length-
prepending和Encryptlastblock方法被讨论和使用的场景最多。如图5.2所示,使用
Length-prepending可以保证CBC-MAC 方案的安全性。在这种方法中,想要对一个消息
产生消息认证码,首先将消息的长度作为一个单独的区块附在消息的第一个块中,然后再
执行标准的CBC-MAC 方法。这种方法要求消息认证码的产生要预先知道消息的长度。
这就要求用户需要先存储消息,再进行消息认证。因此,有不少开发者在实际的使用中采
取将消息的长度附在消息最后来产生消息认证码,但这种做法是不安全的。在这里不再
展开如何攻击一个将消息的长度作为后缀的CBC-MAC 变形,而是将它作为读者课后的
扩展学习和调研。再次强调,使用不经验证的密码方案或对原有的密码方案进行改变,在
实际应用中是十分危险的行为,可能给系统引入十分严重的安全漏洞。
图5.2Length-prependingCBC-MAC方案标签生成过程
加密密码分组链接(EncryptlastblockCBC-MAC,ECBC-MAC)方案可以使消息认
证码产生方在不知道消息长度的情况下产生消息认证码,并且保证方案是安全的。如
图5.在ECBC-密钥由两个不等的部分组成,即k0和k1,其中k0为伪
3所示, MAC 方案中,
随机函数密钥,首先使
k1则为一个对称加密密钥。在对一个消息
m
计算消息认证码时,
用密钥
m
经过原始的CBC-MAC 方法计算
m
的一个临时标签t,再使用k1将
t
进行加密
得到消息
m
的最终标签t'。即表示为
k0,c(k0,m))
ECBC-MAC(k1,m)=Enk1,CBC-MAC(
其中,Enc为对称加密方案的加密算法。在收到一组消息-m,之后,验证者可
认证码对(t)
以通过两种方法验证消息的有效性:①同样使用的ECBC-MAC 方法计算出另一个标签
t'
,使之与
t
进行对比;②先将
t
进行解密,再将解密结果与通过CBC-MAC 方法计算出
来的标签对比。
图5.MAC
方案标签生成过程
3
ECBC
74
物联网安全:原理与技术
细心的读者可能也会发现CBC-MAC方案与CBC模式相比,初始向量也是不同的。
在CBC-MAC方案中,初始向量始终为全0的位串,而CBC模式则要求使用一个随机的
初始向量。这是因为在CBC-MAC方案中使用随机的初始向量是不安全的。这个问题
也留给读者进行思考。
2.从哈希函数构造MAC方案
留意到哈希函数可以将任意长度的消息压缩为一个短的随机的摘要信息,因此从哈
希函数构造MAC方案是一种很直觉的想法,事实上也有一些方案是这样做的,如基于哈
希函数的消息认证码(Hash-basedMesageAuthenticationCode,HMAC )。在HMAC
出现之前,由于CBC-MAC方案是基于对称加密方法或伪随机函数的,不少工业界开发
者认为它太慢而拒绝使用,反而采取基于哈希函数的构造方法。一个典型的例子就是将
MAC方案的密钥作为消息的一部分输入哈希函数中,并产生摘要信息作为该消息的标
签。然而,在使用这类构造时,必须十分小心。在介绍HMAC前,先给出一个基于该思
路来构造的MAC例子,并指出它是不安全的。假设Hs
(·)是一个强抗碰撞性的哈希函
数,则基于该哈希函数的MAC方案构造如下。
(1)Gn:算法输入安全参数λ,
λ
,
0,
λ
。
e然后输出一个随机密钥k∈{1}
k(2‖
)
m
Mac:对于一个消息m∈{0,1}*和密钥k∈{0,1}算法输出该消息的标签t=
Hs()。
(3)Veiy:对于输入密钥k、当且仅当t=Mak,时输出1,
则输出0。
rf消息
m
和标签t, c(m) 否
从直觉上看,由于密钥
k
是通信双方秘密保存的,因此对于一个消息m,任何人都无
法计算出它的标签Hs()。然而事实却是上述的构造方法在采用某些哈希函数时,
k‖
m
是极不安全的,如基于Merkle-Damgard变换的哈希函数。这部分内容由于涉及哈希函
数的构造方法,超出了本书的讲解范围,因此不再进行详细解释。不过仍然提醒读者在实
际使用密码方案时,不经验证地改动密码算法或使用拍脑袋密码算法可能会使系统暴露
在不可知的安全威胁之下。
3.HMAC方案
基于哈希函数的消息认证码(Hash-basedMesageAuthenticationCode,HMAC)是
结合了哈希函数的消息认证码,并且克服了上述使用哈希函数构造MAC时的缺陷。设
H
为一个具有强抗碰撞性质的哈希函数。HMAC方案标签生成过程如图5.
4所示,
HMAC方案的构造方法如下。
(1)Ge0,
λ
。
n:算法随机选取一个密钥k∈{1}
(2)Mac:对于一个任意长度的消息m∈{0,1}*,算法输出标签
t=
H
((ak..ipad)‖m))
k..opd)‖
H
((
其中,opad和ipad为两个常量,分别为外部填充和内部填充。
(3)Verf消息
m
和标签t, c(m)
iy:对于输入密钥k、当且仅当t=Mak,时算法输出
1,否则输出0。
第5章物联网安全基础———数据完整性检验75
图5.4HMAC方案标签生成过程
HMAC 中使用的哈希函数必须要求是抗碰撞的,这样才能保证其安全性。需要注意
的是,由于密钥k的长度,有可能超过一次哈希函数所能处理的块的长度,因此在这种情
况下,实际输入Mac算法中与opad和ipad进行异或的值为k的哈希值,即k'=H(k) 。
另外opad和ipad分别为不同的常量,即重复0x36 和0x5C 这两个十六进制值。HMAC
本身是工业标准,并且广泛使用在各类系统的实现中。HMAC 中的操作只涉及哈希运
算、字符串拼接与异或操作,因此它十分高效。同时它也保证了极高的安全性,即当哈希
函数满足强抗碰撞性时,在适应性选择消息攻击下达到存在性不可伪造。
5.3数字签名
5.3.1数字签名的基本概念
数字签名(DigitalSignature)与消息认证码的作用类似,都可以对数据的完整性进行
检验。不同的是,数字签名允许公开检验,即检验者不需要共享数字签名产生者的秘密信
息,而是基于公开信息就可以对数据的完整性和来源有效性进行检验。数字签名产生者
首先会产生一对密钥,这与非对称加密方案有些类似。这组密钥中由数字签名者保存的
称为签名密钥(私钥), 而另一个用于验证签名有效性的密钥则会被公开,称为验证密钥
(公钥)。一旦签名者产生了上述的公私钥对后,可以对任意的消息签署一个签名,并允许
任何拥有公钥的人来验证该签名的有效性。如果对某个消息的签名是合法的,则证实该
签名确实是由签名者认证签发的,即消息来自签名者。除此之外,数字签名还提供了不可
抵赖的性质,即数字签名的产生者一旦对某个消息进行签名后,无法否认这个签名的有效
性(有时也称该性质为不可否认性)。公开验证和不可抵赖性是数字签名的重要性质,也
正是由于这两个性质,数字签名可以用于签署网络合同、文档等,并在很多国家中具有法
律效力。
定义5.数字签名。一个数字签名方案由一组概率多项式算法(n,n,
4
GeSigVerify)
组成,并满足以下3个条件。
(1)Gen是一个概率算法,其输入为安全参数λ,输出一对密钥(vk,sk), 分别为验证
密钥和签名密钥,其中vk公开,k由签名者秘密保存。
s(2)Sign是一个概率算法,其输入为签名密钥sk和一个消息
m
∈{0,1}*,输出一个
关于消息
m
的签名σ。
(3)Verify是一个确定性算法,其输入为验证密钥vk、消息
m
和消息的签名σ,输出
为1位,意味着签名
σ
是否有效。
76 物联网安全:原理与技术
数字签名的正确性:对于任意的安全参数λ、消息m∈{0,1}* 和密钥(vk,sk)←Gen(λ),
都有Verify(vk,m,Sign(sk,m))=1。数字签名的安全性要求与消息认证码类似,也是需要
达到适应性选择消息攻击下的存在性不可伪造。
5.3.2 常见的数字签名方案
1.RSA 签名方案
初学者往往会认为RSA 签名方案是RSA 加密方案的逆向操作,即使用RSA 加密方
案的私钥加密,公钥解密。实际上这种认识是错误的,并且构造是不安全的。类似RSA
加密,先从不安全的教科书式RSA 签名方案出发来讲述安全的签名方案的构造。RSA
签名方案同样是基于RSA 假设的,具体构造如下。
(1)Gen(λ):算法输入安全参数λ,然后选取两个长度为λ 的大素数p 和q,n=pq,
.(n)=(p-1)(q-1)。随机选取一个e,使gcd(e,.(n))=1,并计算d,使de=1mod.(n)。
则RSA签名的验证密钥为vk=(n,e),签名密钥为sk=(n,d)。
(2)Sign(sk,m ):算法输入RSA 签名密钥sk=(n,d)和消息m ∈Z*N
,输出签名
σ=md modn。
(3)Verify(vk,m ,σ):算法输入RSA 签名验证密钥vk=(n,e),消息m ∈Z*N
和一个
签名σ∈Z*N
。当且仅当m =σe modn 时输出1,否则输出0。
从上述的构造可以看出,教科书式RSA 签名方案与教科书式RSA 加密方案的计算
过程十分相似,其正确性也很容易验证。但是这个方案是不安全的。
在数字签名(消息认证码)的安全定义中,允许攻击者进行适应性地选择消息,从而产
生签名(标记)。基于这种操作,攻击者可以对任意的消息产生有效的签名。假设攻击者
想要产生的签名的消息为m 。攻击者可以通过以下步骤产生对消息m 的有效签名σ。
(1)攻击者随机产生m1,m2,使m1m2=m modn。
(2)攻击者分别对m1和m2进行签名询问,得到签名σ1和σ2。
(3)计算σ=σ1σ2 modn。
其中,σ 为消息m 的有效签名
σe=σ( 1σ2 )e=σe1
σe2
=m1m2=m
即σ 可以通过对m 的有效性验证。
从上述的攻击中可以发现,教科书式的RSA 签名方案不安全的原因是不同消息的签
名可以进行结合,从而产生一个有效的对另一个消息的签名。为了实现安全的RSA 签
名,打破消息和签名之间的关联性是关键。因此,改进的RSA 签名方案的核心思想是对
需要签名的消息进行哈希,然后对哈希的结果进行签名:
σ=H (m )d modn
由于哈希函数是公开的,因此任何人都可以重新计算消息的哈希值,并验证签名的有
效性。由于哈希函数的单向性和强抗碰撞性,因此对于攻击者,找到3个消息m ,m1,
m2,使H (m )=H (m1)H (m2)是困难的。
上述的哈希后签名过程实际上是构造安全签名方案的常用方法。当然在实际使用
第5章 物联网安全基础———数据完整性检验 77
中,并不是简单地对消息进行哈希,而是会使用一些填充技术加入随机数或固定填充等方
法对消息进行处理后,再进行哈希运算。这种方法在很多签名方案中除了可以打破消息
和签名之间的关联性外,还可以使签名方案对任意长度或任意类型的消息进行签名,或使
签名方案变成概率性方案。
2.ElGamal签名方案
ElGamal签名方案很少在实际中使用,但是它的一个变形方案作为数字签名标准算
法(DigitalSignatureAlgorithm,DSA)被广泛使用。下面先介绍ElGamal签名方案,再
介绍DSA 签名方案。
假设p 是一个大素数,使离散对数问题在Z* p 上是困难的,g 是Z* p 中的一个随机生
成元,H 是一个密码学哈希函数H :{0,1}* →Zp 。则ElGamal签名方案的构造如下。
(1)Gen(λ):算法输入安全参数λ,然后随机选取一个长度为λ 的大素数p。随机选
取一个生成元g∈Z* p 。随机选取x∈Zp ,计算y=gx modp。ElGamal签名方案的签名
密钥为sk=(x,g,p),验证密钥为vk=(y,g,p)。
(2)Sign(sk,m ):算法输入签名密钥sk=(x,g,p)和消息m ∈{0,1}* ,随机从[1,
p-2]区间中选取k,使gcd(k,p-1)=1。计算r=gk modp,并计算s=(H (m)-xr)k-1
modp-1。如果s=0,则重新随机产生k 并计算s,直至s 不等于0。算法输出σ=
(r,s)。
(3)Verify(vk,m ,σ):算法输入签名验证密钥vk=(y,g,p),消息m ∈{0,1}* 和一
个签名σ=(r,s),当且仅当gH (m)=rsyr modp 时,算法输出1,否则输出0。
ElGamal签名算法的正确性:在签名过程中,H (m )=sk+xr modp-1。因此有
gH (m)=gsk+xr
=gskgxr
= (gk )s(gx )r
=rsyr modp
则可证明ElGamal签名算法的正确性。
3.Schnorr签名方案
DSA 签名方案同时借鉴了ElGamal签名方案和Schnorr签名方案。因此,在正式介
绍DSA 签名方案之前,还要介绍Schnorr签名方案。Schnorr签名方案是Claus-Peter
Schnorr在1989年提出的。与ElGamal签名方案基于素数阶整数群不同,Schnorr签名
方案是基于任意素数阶循环群的(仍然要求离散对数问题在该群上是安全的)。这就允许
Schnorr签名方案在长度更小的椭圆曲线群上实现。
假设G 是一个阶为p 的循环群,其中p 是一个大素数,使离散对数问题在G 上是困
难的。令H 是一个强抗碰撞性的哈希函数H :{0,1}* →Z* p 。则Schnorr签名方案的构
造如下。
(1)Gen(λ):算法输入安全参数λ,产生满足上述条件的群G。随机选取一个生成元
g∈G。随机选取x∈Z* p ,计算y=gx 。Schnorr签名方案的签名密钥为sk=x,验证密