《新编密码学》课件第6章 数字签名

数字签名

提供数据来源的真实性、数据内容的完整性、签名者的不可否认性以及匿名性等信息安全相关的服务和保障。

用于网络通信的安全以及各种用途的电子交易系统（如电子商务、电子政务、电子出版、网络学习、远程医疗等）中。6.1数字签名的基本原理

概念：

数字签名是对以数字形式存储的消息进行某种处理，产生一种类似于传统手书签名功效的信息处理过程。

它通常将某个算法作用于需要签名的消息，生成一种带有操作者身份信息的编码。示例：Alice和Bob进行通信，并使用消息认证码提供数据完整性保护：情况一：Alice向Bob发送消息并附加了用双方共享密钥生成的消息认证码，但随后Alice否认曾经发送了这条消息；情况二：Bob有能力伪造一个消息及认证码并声称此消息来自Alice。

分析：如果通信的过程没有第三方参与的话，这样的局面是难以仲裁的。

因此，安全的通信仅有消息完整性认证是不够的，还需要有能够防止通信双方相互作弊的安全机制。

数字签名

至少满足的三个基本要求：1）签名者任何时候都无法否认自己曾经签发的数字签名；

2）收信者能够验证和确认收到的数字签名，但任何人都无法伪造别人的数字签名；

3）当各方对数字签名的真伪产生争议时，通过仲裁机构（可信的第三方）进行裁决。数字签名与手写签名的差异

1）手写签名与被签文

件物理上是一个整

体，不可分离；2）手书签名通过物理

比对来判断真伪，

需要一定的技艺甚

至需要专门人员，

机构来执行；3）手书签名会因人而

异，复制品易于原

件分开。1）数字签名与被签名

的消息是可以相互

分离的比特串；2）数字签名通过一个

严密的公开的算法

来验证签名的真伪；3）数字签名的拷贝与其原件是完全相同的二进制比特串，无法区分，需防止签名重复使用。总结：

※签名者必须向验证者提供足够多的非保密信息，以便验证者能够确认签名者的数字签名；

※签名者不能泄露任何用于产生数字签名的机密信息，以防止他人伪造他的数字签名。

因此，签名算法必须能够提供签名者用于签名的机密信息与验证者用于验证签名的公开信息。数字签名体制：组成部分：※签名算法

※验证算法用于对消息产生数字签名，通常受一个签名密钥的控制签名算法或者签名密钥是保密的，有签名者掌握。用于对消息的数字签名进行验证，通常受一个验证密钥的控制，验证算法和验证密钥应该公开。数字签名体制五元组

※

代表消息空间，它是某个字母表中所有串的集合；

※

代表签名空间，它是所有可能的数字签名构成的集合；

※

代表密钥空间，它是所有可能的签名密钥和验证密钥对

构成的集合；

※

是签名算法；是验证算法。对于任意的一个密钥对，每一个消息和签名。

签名变换：和验证变换

：是满足下列条件的函数：数字签名的特性

※两大方面：—功能特性

—安全特性指为了使数字签名能够实现需要的的功能要求而应具备的一些特性。确保提供的的功能是安全的，能够满足安全需求，实现预期的安全保障。功能特性：

1）依赖性2）独特性3）可验证性4）不可伪造性5）可用性一个数字签名与被签消息是紧密相关，不可分割的，离开被签消息，签名不再具有任何效用。数字签名必须是根据签名者拥有的独特消息来产生的，包含了能够代表签名者特有身份的关键信息。通过验证算法能够准切地验证一个数字签名的真伪。伪造一个签名者的数字签名不仅在计算上不可行，而且希望通过重用或者拼接的方法伪造签名也是行不通的。数字签名的生成，验证和识别的处理过程相对简单，能够在普通的设备上快速完成，甚至可以在线处理，签名的结果可以存储和备份。安全特性：

1）单向性2）无碰撞性3）无关性

优点：从根本上消除了成功伪造数字签名的可能性。对于给定的数字签名算法，签名者使用自己的签名密钥sk对消息m进行数字签名是计算上容易的，但给定一个消息m和它的一个数字签名s，希望推导出签名者的签名密钥sk是计算上不可行的。对于两个不同消息，在相同的签名密钥下的数字签名相等的概率是可以忽略的。对于两个不同的消息，从某个签名者对其中一个消息的签名推导出对另一个消息的签名是不可能的。缺陷：不抵抗窃听。基于公钥密码的数字签名体制发送方签名算法验证算法密钥空间接受方mcmskpk基于公钥密码的加密和签名体制

注意：先签名，后加密的顺序不能颠倒发送方密钥空间解密算法加密算法签名算法验证算法密钥空间接受方mzzcmpk2sk2sk1pk1原始信息Hash算法Hash值加密签名私钥原始信息Hash算法Hash值验证公钥Hash值=?SenderReceiver数字签名的实现方法：数字签名的分类

※

直接数字签名体制

※

可仲裁的数字签名体制直接数字签名A：EKSa[M]→BB：EKPa[EKSa[M]]只有A具有KSa，可以进行加密（签名）任何第三方都可以用KPa验证签名只提供签名功能A：EKPb[EKSa[M]]→BB：EKPa[EKSb[EKPb[EKSa[M]]]]提供加密（KPb）和签名（KSa）功能KSa、KPa

分别是A的私钥和公钥直接数字签名A：M‖EKSa[H(M)]→BB：h=H(M)；EKPa[EKSa[H(M)]]=h’；h’=h?H(M)受到Hash算法不可逆的保护只有A能够生成EKSa[H(M)]提供签名和鉴别功能A：EKPb[M‖EKSa[H(M)]]→B B：EKSb[EKPb[M‖EKSa[(M)]]]；h=H(M)； EKPa[EKSa[H(M)]]=h’；h’=h?提供加密（KPb）、签名（KSa）和鉴别（H(M)）功能直接数字签名的缺点验证模式依赖于发送方的公钥发送方要抵赖发送某一信息时，可能会声称其私有密钥丢失或被窃，从而他人伪造了他的签名。需要采用与私有密钥安全性相关的行政管理控制手段来制止或至少是削弱这种情况，但威胁在某种程度上依然存在。改进的方式，例如可以要求被签名的信息包含一个时间戳（日期与时间），并要求将已暴露的密钥报告给一个授权中心。仲裁签名引入仲裁者所有从发送方A（Alice）到接收方B（Bob）的签名信息首先送到仲裁者C（Carol）。C将信息及其签名进行一系列测试，以检查其来源和内容。C将信息加上日期并与验证通过的指示一起发给B。前提条件：所有的参与者必须极大地相信这一仲裁机制的工作。仲裁签名－单密钥加密方式A与C之间共享密钥Kac，B与C之间共享密钥Kbc;A：M‖EKac[IDA‖H(M)]→CA：计算消息M的散列码H(M)，用A的标识符IDA

和散列值构成签名，并将消息和经Kac加密后的签名发送给C；C：EKbc[IDA‖M‖EKac[IDA‖H(M)]‖T]→BC：解密签名，用H(M)验证消息M，然后将IDA，M，经Kac加密后的签名和时间戳T一起经Kbc加密发送给B；B：解密C发来的信息，并将消息M和经Kac加密后的签名保存起来。B不能直接验证A的签名问题：C可以看到A给B的所有信息仲裁签名－单密钥加密方式验证签名B：EKbc[IDA‖M‖EKac[IDA‖H(M)]]→CC：用EKbc恢复IDA，M和签名EKac[IDA‖H(M)]，然后用EKac解密签名并验证散列码。在这种模式下，B不能直接验证A的签名，B认为C的消息正确，只因为他来自于C。因此，双方必须高度相信C。并且相信C处理争议时是公正的。A和B之间也可以约定一个对称密钥，并使用该密钥加密明文后，再进行以上的签名操作，这样C就无法看到明文的内容。问题C与A联手可以否认签名的信息C与B联手可以伪造A的签名仲裁签名－双密钥加密方式A：IDA‖EKSa[IDA‖EKPb[EKSa[M]]]→CA首先用自己的私有密钥KSa，然后用B的公开密钥KPb，生成经过签名的密文。最后将该信息以及A的标识符一起用自己的私钥EKSa签名后与IDA一起发送给C。这时加密过的消息对C，以及B以外的其他人都是保密的。C：EKSc[IDA‖EKPb[EKSa[M]]‖T]→BC检查A的签名是否有效，并确认消息。然后将包含IDA、经A加密并签名的消息和时间戳的消息用自己的私钥EKSc签名后发送给B。仲裁签名－的特点在通信之前，各方之间无需共享任何信息，从而避免了联手作弊；即使A的私钥EKSa泄露，只要C的私钥未泄露，不会有错误标定日期的消息被发送；A发送给B的消息的内容对C和任何除A、B以外的其他人是保密的。引入仲裁签名只是为了通过仲裁者证明指定信息是由A在指定的时间发送给B的。并不代表指定信息是由仲裁者签发的。6.2RSA数字签名

RSA签名体制是Diffie和Hellman提出数字签名思想后的第一个数字签名体制，它是由Rivest、Shamir和Adleman三人共同完成的。该签名体制来源于RSA公钥密码体制的思想，将RSA公钥体制按照数字签名的方式运用。RSA数字签名

※选取两个不同的大素数p和q，计算

※

选取一个与

互素的正整数

e，并计算出d满足

,即

d是e模

的逆。

※

最后，公开

n和

e作为签名验证密钥，秘密保存

p、

q和d作为签名密钥。RSA数字签名体制的消息空间和签名空间都是Zn，分别对应于RSA公钥密码体制的明文空间和密文空间。签名时：得到的结果s就是签名者对消息m的数字签名。验证时：验证者通过下式判断签名的真伪RSA数字签名的安全问题

对RSA数字签名算法进行选择密文攻击可以实现三个目的，即：

※消息破译

※骗取仲裁签名

※骗取用户签名消息破译即得到了原始的明文消息骗取仲裁签名攻击者骗取仲裁签名骗取用户签名主要思想：当攻击者希望某合法用户对一个消息m进行签名但该签名者可能不愿意为其签名时：

※

将m分解成两个（多个）更能迷惑合法用户的消息m1和m2，且满足m=m1×m2；

※

让合法用户对m1和m2分别签名；攻击者最终获得该合法用户对消息m的签名。结论：上述选择密文攻击都是利用了指数运算能够保持输入的乘积结构这一缺陷（称为可乘性）。

因此，任何时候都不能对陌生人提交的消息直接签名，最好先经过某种处理。攻击方法（续）1）伪造者Oscar选取一个消息y，并取得某合法用户的RSA公钥（n,e）；

2）计算：

3）伪造者声称y是该合法用户对消息x的RSA签名，达到了假冒该合法用户的目的。

这是因为，该合法用户用自己的私钥d对消息x合法签名的结果正好就是y，即：

因此从算法本身不能识别伪造者的假冒行为6.3Rabin数字签名

Rabin数字签名体制利用Rabin公钥密码算法构造而成。

由于Rabin公钥密码算法与RSA公钥密码算法的相似性，Rabin签名算法与RSA签名算法也具有类似的相似性。6.3.1Rabin数字签名算法Rabin数字签名算法的系统参数包括两个随机选取的相异大素数p和q，及它们的乘积。其中，n为公开密钥，p和q则需要保密。消息空间和签名空间都是由同为模p平方剩余和模q平方剩余的正整数构成的集合。签名时：对一个消息

m∈zn签名时※判断消息m是否同时是模

p和模q的平方剩余；

※否：

对m作一个变换，将其映射成满足要的。

是：对m签字就是计算模m的平方根，即:

求解合数模的平方根是困难的，除非能够对模数进行素因子分解。即：

知道模数n的两个素因子p和q，然后将问题转化成一次同余方程组，再利用中国剩余定理求解。

伪造Rabin签名是困难的验证时：

※验证者计算消息签名的平方；

※

通过下式确认数字签名的真伪：

Rabin签名正确性的验证是显而易见的。Rabin签名算法的安全问题Rabin算法是一种基于平方剩余的公钥体制，这种体制已经被证明它的安全性正好等价于大整数分解的困难性，但这种体制也容易遭受一种特定的攻击，其方法如下：攻击者签名者XM等待签名者送回数字签名S缺陷

※

它要求被签消息必须是模的平方剩余

※

若不是，将被签消息映射到满足要求的另一个消息m′上，再用m′的Rabin签名作为原消息的签名。6.4ElGamal数字签名

思想：

ElGamal签名体制是一种基于离散对数问题的数字签名方案。ElGamal签名算法是专门为数字签名设计的。

ElGamal数字签名算法

ElGamal签名体制也是非确定性的，任何一个给定的消息都可以产生多个有效的ElGamal签名，并且验证算法能够将它们中的任何一个当作可信的签名接受。ElGamal签名方案的系统参数

一个大素数p；

的生成元g；

任取的秘密数a；

一个由g和a计算得到的整数y；P的大小足以使Zp上的离散对数问题难以解决y满足：

这些系统参数构成ElGamal数字签名的密钥K=（p,g,a,y）,其中（p,g,y）是公开密钥，a是私有密钥。签名时：验证时：例6.1若要对消息m=100签名时，假设取随机数k=213且则有：（续）且所以，得到一个新的数字签名s=（126，350）（续）验证时：

对于第一个数字签名s=（29,51），有

而：（续）

对于第二个数字签名s=(126，350)，仍然有

而：

所以，两个数字签名都是有效的。对ElGamal签名算法的可能攻击

ElGamal数字签名算法的安全性依赖于求解离散对数问题的困难性，如果求解离散对数已经不再困难了，那么ElGamal数字签名算法也就没有任何意义了。

在假定离散对数问题依然难以求解的情况下，ElGamal签名方案仍然存在一些安全威胁。

这些安全威胁首先来自于对方案使用不当而造成的可能攻击，包括两个方面：

※

对签名中使用的随机整数k保管不当，发生

泄露；

※

重复使用签名随机数k。随机整数k保管不当注意：这时整个系统完全被破坏，攻击者可以随意伪造该签名者的数字签名。重复使用k可以使攻击者易于计算出签名者的私有密钥a。具体做法：

设和分别是某个签名者对消息和的签名，且

，有：

两式相减，得：设：

那么，

所以，

记：

则等式变成且

由于

所以，由扩展的欧几里得算法求出：

得：

故：，

利用同余式：

即可测出唯一正确的k。

找到签名随机数k，即可计算出签名者的私有密钥a。伪造签名攻击

方法一：由此可见，攻击者可以在惟密钥的情况下进行存在性伪造。

设：i和j是上的整数且可表示为：

那么签名验证条件是：于是有：若且

则上式成立。因此，在给定的i和j，且的条件下，很容易利用这两个同余式求出和，结果如下：

显然，按照种方法构造出来的是消息的有效签名，但它是伪造的。例6.2

设，，。选取和那么，

计算：

（435,425）是对消息m=285的有效签名，这可以从下面的式子得到验证：方法二：此方法属于已知消息攻击存在性伪造，伪造签名者需要从合法签名者的某个已知签名消息开始，来伪造一个新消息签名。具体实现：

计算：

那么，签名条件

于是，伪造出一个是的有效签名。小结这两种伪造签名的攻击都是对ElGamal数字签名的存在性伪造，对抗这种存在性伪造的简单办法是使消息格式化。

※

最简单的消息格式化机制：

在消息中嵌入一个可识别的部分；

※最有效的消息格式化机制：对消息进行Hash函数处理；方法三：小结

先计算：

然后计算，使满足

显然，可以通过中国剩余定理解出。

历史背景：

数字签名标准DSS（DigitalSignatureStandard）是由美国国家标准技术协会NIST于1991年8月公布，并于1994年12月1日正式生效的一项美国联邦信息处理标准。6.5数字签名标准DSS

DSS的数字签名算法

DSS数字签名标准使用的算法称为数字签名算法DSA（DigitalSignatureAlgorithm），它是在ElGamal和Schnorr两个方案基础上设计出来的。DSA的系统参数※※※

※一个用户随机选取的整数，并计算出※一个Hash函数H：。

这些系统参数构成DSA的密钥空间：

其中，

为公开密钥，a是私有密钥。签名时：

对消息m生成数字签名时，随机选取一个秘密整数，并计算出：

就是消息m的数字签名，即

由此可见，DSA的签名空间为，签名的长度比ElGamal体制短了许多。验证者知道签名者的公开密钥验证时：对于一个消息-签名对，计算下面几个值并判定签名的真实性：这是因为，如果是消息的有效签名，那么DSA数字签名算法基本框图

m

f1f3f2SHA-1

SHA-1f4比较m

p,q,gkaqwkv例6.3假设签名者的私有密钥为a=87，那么，签名时：

假如该签名者要对一个消息摘要为SHA-1（m）=132的消息m签名，并且签名者选择的秘密随机数为k=79，则需要计算：因此，（99,57）是消息m的签名验证时：

计算：

所以，

说明以上签名是有效的。DSA算法的评价

DSA算法不能用于数据加密，也不能用于密钥分配；DSA算法比RSA慢；DSA算法的密钥长度；验证签名时DSA比RSA慢10到40倍密钥长度变化范围在512比特到1024比特之间DSA算法的安全问题

主要有以下几个方面：

攻击秘密数k；

共用模数的危险；DSA的阈下信道；

允许签名者在其签名中嵌入秘密消息,只有知道密钥的人能提取签名者嵌入的秘密消息.小结数字签名与公钥加密的区别签名加密HashSIGHash解密比较mmsskAs=SIGsk

(Hash(m))pkA发送方加密算法解密算法接收方密钥空间mmc发送方A(,)pkAskA接收方B(,)pkBskBpkBskB发送方A接收方BAB小结数字签名与公钥加密的区别数字签名与消息加密的结合使用特殊数字签名随着网络技术和电子商务的迅猛发展,迫切需要解决网上数据传输安全以及交易双方的身份识别和认证。简单模拟手写签名的普通签名已不能完全满足应用的需要,许多新的应用环境要求数字签名能支持一些特殊的功能,因此，需要在基本数字签名技术的基础上进行扩展，以满足这些特殊的需求。特点：

如果没有签名者Alice的合作，签名的有效性就得不到验证。好处：防止了由Alice签署的消息在没有经过Alice本人同意而被复制和分发的可能性。1.不可否认签名签名的构成组成：

签名算法

验证协议

否认协议参数生成密钥空间为:

其中是公钥，是私钥。对于消息，签名者计算

签名验证协议随机选取参数e1,e2e1e2

c

d

当且仅当Bob认为签名合法

否认协议随机选取参数e1,e2e1e2

c

d计算随机选取CD计算

当且仅当Bob认为签名是伪造的。Alice能使Bob相信一个无效的签名是一个伪造签名Alice能使Bob以一个很小的概率相信一个有效的签名是伪造的不可否认数字签名的应用

软件公司A发行了一套最新的软件.它向用户承诺,此软件不含