（计算机软件与理论专业论文）基于vrf函数可证安全的概率签名体制.pdf

摘要 随着计算机网络、电子商务和办公自动化系统的广泛应用，电子世界将会 成为人们生活的一个重要部分，如何解决电子世界中的争端是一个十分迫切的问 题。而数字签名可以提供一个完美的解决方案。概率签名是一种随机化的数字签 名，即对同一消息由于随机参数选择不同而有不同的签名，因此大大提高了同一 对密钥的重复使用率，在实际生活中有着广泛的用途。 文章回顾了以往著名的e 1 g a m a l ，p s s 等概率签名体制，总结了他们的签名 过程和安全性。并且通过引入f i a t s h a m i r 变换以及它所带来的安全问题，深入 剖析了这些现有概率签名体制存在的安全隐患。然后利用可验证的伪随机函数 ( v r f ) 这一新的技术，构造出了一种新的概率签名体制，证明了其安全性，并 通过和以往的几种概率签名体制作比较，突出了这种新型概率签名方案的优点和 诸多好的性质。 关键词 数字签名概率签名哈希函数随机o r a c l e 伪随机性可验证性 v r f 函数f i a t - s h a m i r 变换 a b s t r a c t w j t l lt h ew i d e a p p l i c a t i o n o f c o m p u t e rn e t w o r k ，e - c o m m e r c e a n do f f i c e a u t o m a t i o n ，t h ee l e c t r o n i cw o r l d i sb e c o m i n ga ni m p o r t a n tp a r to fp e o p l e sl i f e h o w t od e a lw i t ht h o s ei n v o l v e di s s u e si nt h ee l e c t r o n i cw o r l di sa ne x i g e n tp r o b l e m d i g i t a ls i g n a t u r ec a np r o v i d ep e r f e c ts o l u t i o n p r o b a b i l i s t i cs i g n a t u r ei s ak i n do f r a n d o m i z e ds i g n a t u r e t h a ti s d i f i e t e n ts i g n a t u r e sc a nb eo b t a i n e df r o mt h es a m e m e s s a g ea c c o r d i n g t od i f f e r e n tr a n d o m p a r a m e t e r b e c a u s e o n e p a i r o fs e c r e tk e y sc a n b er e u s e df o rm a n yt i m e si nt h i sk i n do fs i g n a t u r e i ti sw i d l yu s e di no u rd a i l yl i r e i nt h i st h e s i s ，w er e v i e w e dt h o s ef a m o u s p r o b a b i l i s t i cs i g n a t u r es u c h a se 1 g a n m l s i g n a t u r ea n dp s ss i g n a t u r e a n ds u m m a r i z e d t h e i rs e c u r i t y w i 也t h ei n t r o d u c t i o no f f i a t s h a m i rt r a n s f o r m a t i o na n di t ss e c u r i t yp r o b l e m ，w ed i s c u s st h eh i d d e ni n s e c u r i t y o f t h o s e e x i s t i n gp r o b a b i l i s t i cs i g n a t u r e t h e nw e i n t r o d u c ean e w t e c h o n o l o g yn a m e d v r f ( v e r i f i a b l e r a n d o mf u n c t i o n ) a n db s ei tt oc o n s t r u c tan e wt y d eo fs e c u r e p r o b a b i l i s t i cs i g n a t u r e i t ss e c u r i t y , e f f i c i e n t ya n d o t h e rc h a r a c t e r sa r ea n a l y z e d c o m p a r e d w i t ho t h e r p r o b a b i l i s t i cs i g n a t u r e ，w ee m p h a s i z e o nt h en o t a b l em e r i t s a n df a v o r a b l ec h a r a c t e r so f o u rn e w p r o b a b i l i s f i cs i g n a t u r e k e y w o r d sd i g i t a ls i g n a t u r e p r o b a b i l i s t i cs i g n a t u r e h a s hf u n c t i o nr a n d o m o r a c l ep s e u d o r a n d o m n e s s v e r i f i a b l i l i t y v r ff i a t - s h a m i rt h a n s f o r m a t i o n 2 第一章绪论 数字签名在信息安全，包括身份认证、数据完整性、不可否认性以及匿名性 等方面有着重要应用，特别是在大型网络安全通信中的密钥分配、认证以及电子 商务系统中具有重要作用。数字签名是实现认证的重要工具。本章将介绍数字签 名的基本概念和技术，各种常用的数字签名体制，相关的背景以及我们所要做的 主要工作。 1 1 数字签名的基本概念 政治、军事、外交等的文件、命令和条约，商业中的契约以及个人之间的书 信等，传统上采用手书签名或印章，以便在法律上能认证、核准、生效。随着计 算机通信网的发展，人们希望通过电子设备实现快速、远距离的交易，数字( 或 电子) 签名法应运而生，并开始用于商业通信系统，如电子邮件、电子转账和办 公自动化等系统。类似于手书签名，数字签名也应满足以下要求：( 1 ) 收方能够确 认或证实发方的签名，且不能伪造。( 2 ) 发方发出签名的消息给收方后，就不能 再否认他所签名的消息。( 3 ) 收方对己收到的签名消息不能否认，即有收报认证。 ( 4 ) 第三者可以确认收发双方之间的消息传送。但不能伪造这过程。 数字签名与手书签名的区别在于，手书签名是模拟的，且因人而异。数字签 名是。和1 的数字串，因消息而异。数字签名与消息认证的区别在于。消息认证 使收方能验证消息发送者及所发消息内容是否被窜改过。当收发者之间没有利害 冲突时，这对于防止第三者的破坏来说是足够了。但当收方和发方之阀有利害冲 突时，单纯用消息认证技术就无法解决他们之问的纠纷，此时须借助满足前述要 求的数字签名技术。 消息签名与消息加密有所不同，消息加密和解密可能是一次性的，它要求在 解密之前是安全的；而一个签名的消息可能作为一个法律上的文件，如合同等， 很可能在对消息签署多年之后才验证其签名，而且可能需要多次验证此签名。因 此，签名的安全性和防伪造的要求更高些，并要求证实速度比签名速度还要快些， 特别是联机在线实时验证。随着计算机网络的发展，过去依赖于手书签名的各种 业务都可用这种电子数字签名代替，它是实现电子贸易、电子支票、电子货币、 电子购物、电子出版及知识产权保护等系统安全的重要保证。 为了实现签名e l 的，发方必须向收方提供足够的非保密信息，以便使其能验 证消息的签名；但又不能泄露用于产生签名的机密信息，以防止他人伪造签名。 因此，签名者和证实者可公用的信息不能太多。任何一种产生签名的算法或函数 都应当提供这两种信息，而且从公开的信息很难推测出用于产生签名的机密信 息。再有，任何一种数字签名的实现都有赖于仔细设计的通信协议。 数字签名有两种：一种是对整体消息的签名，它是消息经过密码变换的被签 消息整体；一种是对压缩消息的签名，它是附加在被签名消息之后或某一特定位 置上的一段签名图样。若按明文、密文的对应关系划分，每一种又可分为两个子 类：一类是确定性( d e t e r m i n i s t i c ) 数字签名，其明文与密文一一对应，它对一 特定消息的签名不变化，如r s a ，r a b i n 等签名；另一类是随机化( r a n d o m i z e d ) 或概率数字签名，它对同一消息的签名是随机变化的，取决于签名算法中的随机 参数的取值。一个明文可能有多个合法数字签名，如e i g a m a l ，p s s 等签名。 一般来说，一个签名方案是由两个部分组成；签名算法和验证算法。签名者 能使用一个( 秘密的) 签名算法s 喀来签名消息m ，产生的签名s i g ( m ) 能利用公 开的验证算法v e t 来验证。给定一个消息、签名对( m ，s 增( 聊) ) ，验证算法返回答 案是“真”或“假”取决于签名是否真实。标准的数字签名定义如下： 定义1 1 ：一个数字签名体制是一个三元组( g ，s ，y ) ，满足以下条件 密钥产生算法g ：概率多项式时间算法，输入为1 2 ，其中k 为安全参数。 输出密钥对( p k ，s k ) ，其中p k 是公钥，s k 是私钥。 签名算法s ：输入安全参数1 2 ，私钥s k 和消息m o ，1 。，输出m 的签名 盯。可以是概率多项式时间算法，在一些方案中，可以接受其他参数作为 输入。 验证算法v ：多项式时间算法。输入公钥p k ，消息m ，签名o ，输出1 ( “真”) 或0 ( “假”) 来表明签名是否合法。一般情况下不要求是概率算 法。满足矿( p k a 咖仨麓恶 1 2 数字签名的安全性 为考虑数字签名协议的安全性，我们首先介绍g o l d w a s s e r ，m i c a l i 和y a o 等提出的 2 2 ，在文献 2 1 ，4 ，3 5 ，1 2 ，3 7 中继续讨论的对数字签名体制的攻击方 法及其相应的安全要求。一般来说对数字签名体制的攻击可分为 1 唯钥攻击( k e y o n l ya t t a c k ) ：攻击者只知道签名者的公钥，因此只能验证 签名的合法性。 2 已知签名攻击( k n o w ns i g n a t u r ea t t a c k ) ：攻击者知道签名者的公钥以及 某些有效的消息签名对。现实生活中，这是一个攻击者至少能做到的。 3 选择消息攻击( c h o s e nm e s s a g ea t t a c k ) ：攻击者不仅可以得到一些消息的 签名，而且可以选择被签名的消息。 4 自适应选择消息攻击( a d a p t i v e l y c h o s e nm e s s a g ea t t a c k ) ：攻击者不仅 可以选择被签名的消息，而且也可以根据以前的签名结果来修正这一选 择。 相应地，攻击者对数字签名协议的攻击结果可以分为 1 存在伪造( e x i s t e n t i a lf o r g e r y ) ：攻击者可以伪造出对某一消息的签名， 但该消息的具体内容不是攻击者所能控制的。 2 选择伪造( s e l e c t i v ef o r g e r y ) ：攻击者可以伪造出对某一自己选择的消 息的签名。 3 全局伪造( u n i v e r s a lf o r g e r y ) ：攻击者虽然不知道签名者的私钥，但可以 伪造出对任一消息的签名。 4 完全攻破( t o t a lb r e a k ) ：攻击者可以求出签名者的私钥。 显然，对于一个数字签名协议，我们希望其在自适应选择消息攻击下，依然不可 存在性伪造。 常用的对数字签名的攻击方法有两种： 确定性分析法 利用一个或几个己知量，用数学关系式表示所求未知量，己知量和未知量 的关系视签名算法和验证算法而定。寻求这种关系是确定性分析法的关键步骤， 现在对数字签名方案的攻击绝大多数采用这种方式。 统计分析法 利用己知消息及其相应签名的某种概率关系来攻击。这种攻击方法目前基 于公钥体制的方案来说是不大适用的，它主要用来攻击分组密码和流密码的。 我们说一个数字签名体制是安全的，如果能够访问签名o r a c l e 的攻击者不 能在多项式时间内伪造出一个消息的签名，而这个消息是在访问签名o r a c l e 时 未被询问过的。 1 3 签名与验证所采用的技术 常用的签名与验证采用的技术包括：单向函数( 单向陷门函数和单向哈希函 数) 、零知识证明、时间标记、证书、秘密共享和密钥分配。我们简单地介绍一 下数字签名方案的这些基础模块。 1 单向函数：单向函数是这样一种函数，计算起来相对容易，但求逆却显得 困难。也就是说，己知x ，很容易计算f ( x ) 。但已知f ( x ) ，却难于计算x 。然 而，按照严格的数学定义，单向函数的存在性还没有证明，同时也还没有构造 出单向函数的可靠迹象。即使这样，还是有很多函数看起来和感觉起来像单向函 数，能够有效地计算它们，但至今还无法容易地计算出它们的逆。 在数字签名中，实际使用的单向函数有：幂指数函数，椭圆曲线函数和平方 函数等，主要用于验证签名。 2 单向陷门函数：是有一个秘密陷门的一类特殊单向函数。它的一个方向 易于计算，而反方向却难于计算。但是，如果知道那个秘密陷门，也能很容易反 方向计算这个函数。也就是说，己知x ，易于计算，( 砷，已知f ( x ) ，却难于计 算x 。然而，有一些秘密信息y ，一旦给出厂( 砷和y ，就很容易计算出x 。 3 单向哈希函数：单向哈希函数有很多种叫法：压缩函数、渐缩函数、消 息摘要、指纹、密码效验和数据完整性检测( d i c ) 、操作检验码( m d c ) 、消息鉴别 码( c a c ) 和数据鉴别码( d a c ) 。单向哈希函数既是单向函数，又是哈希函数，从输 4 入串很容易计算出其哈希值，但要产生一个串，使其哈希值等于这个值，却是很 难的。 单向哈希函数主要有两类：带密钥和不带密钥的哈希函数。不带密钥的哈希 函数任何人都可以计算，它仅仅是输入串的函数；带密钥的哈希函数是输入串和 密钥的哈希函数，只有持有密钥的人才能计算单向哈希值( 它等同于先计算单向 哈希值，然后再对它加密) 。 4 零知识证明：数字签名中有时会用到零知识证明协议，如群签名、不可 否认签名等。 所谓零知识证明，是指一方向另一方证明他知道某种事物或具有某种性质 时，不是直接出示或说出此事物使别人相信，而是以一种有效的数学方法，使验 证者p 可以检验每一步成立，最终确信证明者v 知道其秘密，而又能保证不泄漏 证明者所知道的信息。满足以下几条性质：( 1 ) 证明者几乎不可能欺骗验证者， 若p 知道证明，则可使v 几乎确信p 知道证明；若p 不知道证明，则他使v 相信 他知道证明的概率接近零。( 2 ) 验证者几乎不可能得到证明的信息，特别是他不 可能向其他人出示此证明。( 3 ) 验证者从证明者那里得不到任何有关证明的知 识。零知识证明按其性质可以分为计算零知识证明、统计零知识证明和完美零知 识证明；按其形式又可以分为交互式零知识证明和非交互式零知识证明。 5 时戳：使用一个数字签名方案时，可能会遇到一些麻烦问题，诸如，一 个签名者的签名算法可能被一个敌手偷走，此时，对签名者在敌手偷走签名算法 之前所做的签名的真实性会受到影响。也可能签名者签了名以后，他想否认签名， 他就将签名算法公布于众，然后声称他对消息的签名是一个伪造签名。出现这些 情况的主要原因是没有办法确定一个消息何时被签了名。这就建议我们考虑采取 对一个( 签名的) 消息加上时间标记的方法，一个时间标记将提供证明：一个消息 是在一个特定的时间签的名。那么如果某个人的签名算法泄露了，他将不会使先 前做的任何签名无效。概念上它类似于信用卡的工作方式：如果某人丢失了信用 卡，并通知以前发行该卡的银行，信用卡变得无用了，但信用卡的丢失并不影响 先前已作的购买记录。 6 证书：一个可信的发证机构给每一个用户分配唯一的名字并签发一个包 含名字和用户公开密钥的证书。证书有一个具体的有效日期。当证书失效后，它 将从c a ( 发证机构) 维护的任何公共目录中删除。然而签发此证书的c a 依旧保留 此证书的副本，以备目后处理解密可能引起的纠纷。 7 密钥的管理与分配：一个密码系统可以看成是一部机器，其中可变的仅是 密钥。在现代信息系统中，通常需要密码系统是公开的，一旦秘密密钥失密，则 整个系统则无安全性可言，若密钥出错，则不能传送正确信息，因而整个系统的 安全性就主要取决于对秘密密钥的保护管理。密钥的保密和安全管理在整个安全 信息系统中是极为重要的。密钥管理包括密钥的产生、分配、存储、保护、销毁 等一系列过程，其中密钥的产生、分配和存储是最关键的问题。 1 4 相关工作 数字签名一般是基于某种数学难题之上的，基本的有两种，一种是大数分解， 对应的签名方案有r s a 等；另一种是离散对数，对应的签名方案有e i g a m a l 等。 r s a 签名体制是基于r s a 公钥密码算法建立的，是一类常用的确定性签名体 制。1 9 8 5 年，e i g a m a l 第一次在有限域上基于离散对数问题设计了概率化的 e i g a m a l 数字签名方案，这是数字签名史上一个较重要的里程碑。虽然数字签名 方案越来越多，但缺乏统一的标准。美国国家安全局( n s a ) 与国家标准局( n b 8 ) 通力合作，于1 9 9 1 年提出了美国数字签名体制d s s 及其算法标准d s a ，d s a 也是 基于最初的e i g a m a l 数字签名方案的。与当初推出d e s 一样，d s a 的推出也引起 了密码学界的强烈反应。此外，概率数字签名还包括p s s 、p s s r 等方案。 针对数字签名的特殊用途和性质还可分为不可否认签名、盲签名、群签名、 代理签名等等。 不可否认的数字签名是由c h a u m 和a n t w e r p e n 在1 9 8 9 年提出的 7 。此种签 名有一新颖的特征，即验证者必须在签名者的合作下才能验证签名。它包括签名 算法、验证协议和否认协议三部分。签名者用签名算法签名后，验证者就可在签 名者的配合下验证签名。此种方案的新意在于，如果双方关于签名的真伪发生了 争执，则可以执行否认协议来推断签名的真伪，而不用求助于第三方，从而具有 一定的灵活性，节省了双方的时间等开销。人们围绕这一签名，又得到了一系列 的相关签名，如可转移的不可否认数字签名、零知识的不可否认数字签名等。不 可否认的数字签名在某些应用场合是十分有用的，诸如软件开发者可利用不可否 6 认的数字签名对他们的软件进行保护，使得只有付清了钱的顾客才能验证签名， 并相信丌发者仍然对软件负责并愿意提供完善的售后服务。 1 9 8 3 年，c h a u m 最先提出了盲签名的概念 8 。盲数字签名在需要实现某些 参加者的匿名性的密码协议中有着广泛而重要的应用，如在选举协议、安全的电 子支付系统中等。盲数字签名在某种程度上保护了参加者的利益，但不幸的是， 盲数字签名的匿名性能被犯罪分子滥用。为阻止这种滥用，文献 3 8 引入了公平 盲数字签名的概念并给出了一些具体实现。公平盲数字签名比盲数字签名多了一 个特性：借助于可信中心可将消息签名对和签名者在签名协议中观察到的对应的 盲消息联系起来。也就是说，通过可信中心，签名者可追踪签名。在文献 2 6 中，作者基于健忘传输协议提出了一个可恢复消息的公平盲签名方案。健忘传输 协议是r a b i n 在1 9 8 1 年首次提出的一种协议。在这种协议中，发送者可以5 0 的概率向接收者传送秘密，所以接收者有5 0 的机会收到秘密，也有5 0 的机会 收不到秘密。另一方面，接收者将知道他是否已收到秘密，而发送者则不知道接 收者是否收到了秘密。 1 9 9 1 年，c h a u m 和v a nh e y s t 在文献 1 0 3 中首次提出了群签名的概念。在这 类方案中，群中的每个成员都可以群的名义匿名地签发消息。与群数字签名相关 的两个概念是群定向数字签名和多重数字签名。群定向数字签名允许群的某些子 集代表那个子群签名，但它没有提供识别签名者的方法。多重数字签名要求由多 人来同时签署一个消息。群签名的一个实用例子是投标。每个公司匿名地使用群 数字签名签他的投标，当特定的投标被选中后，借助于可信中心能识别出实际的 签名者，而所有别的投标的签名者仍然是匿名的。如果签名者反悔他的投标，那 么无需签名者的合作，他的身份就可以被计算出来。 代理签名 2 5 的概念由m a m b o 等人在1 9 9 6 年引入。顾名思义，代理签名就 是允许某人( 称为代理签名者) 代表原始签名者来产生签名。必须保证只有经 过授权的代理者才能签名。对于验证者来说，代理者的签名和原始签名者的签名 具有同等的地位。代理签名一般可分为完全代理、部分代理以及证书代理等三种 类型。完全代理即把原始签名者的签名密钥直接交给代理者，从而代理者的签名 和原始签名者的签名是不可分的：在部分代理中，代理者的签名密钥可以从签名 者的密钥导出，但反过来不可行；证书代理即通过一个证书来验证代理者是不是 由原始签名者指定的，以及判断代理信息是不是有效。从安全性及处理速度等方 面考虑，部分代理最有发展前途。为防止原始签名者利用代理签名者的密钥来签 名然后否认，就出现了所谓的不可否认的代理签名，也就是在代理签名的基础上 加入了确认协议和否认协议，从而在出现争端时可以发挥作用。 1 5 本文的工作 本文着重研究了随机化的签名体制，也就是概率签名体制。文章回顾了以往 著名的e 1 g a m a l ，p s s 等概率签名体制，并对他们的安全性加以分析。由于他们的 安全性都是在随机o r a c l e 模型下证明的，而根据2 0 0 3 年g o l d w a s s e r 等人提出 的在一般情况下类似f i a t s h a m i r 变换得到的数字签名在实际情况下( 也就是用 一个函数簇来实现这个o r a c l e ) 都是不安全的重要结论，可以得出p s s 类的概 率签名在实际中是不安全的，而e i g a m a l 类的概率签名目前也不能保证在实际中 可证安全。为此，本文利用可验证的伪随机函数( v r f ) 构造出了一种新型的概 率签名体制，它不需要使用随机o r a c l e ，基于一定的复杂性假设就可以证明其安 全性，并且具有可验证性和伪随机性等很好的性质。 文章的结构安排如下： 第二章对现有的概率签名方案进行了总结，包括常用的e 1 g a m a l ，d s s 签名体 制以及p s s o ，p s s ，p s s r 签名体制，分析了他们的签名过程和安全性。并且通过 引入f i a t s h a m i r 变换以及它所带来的安全问题，深入剖析了这些现有概率签名 体制存在的安全隐患。 第三章介绍了一种新的技术：可验证的伪随机函数( v r f ) ，具体分析了如何 构造这样的函数，它所具有的性质和应用。 第四章着重介绍了我们所提出的基于v r f 的可证安全的概率签名方案，分析 了其安全性。并通过和以往的几种概率签名体制作比较，总结了这种新型概率签 名方案的优点和诸多好的性质。 最后，是对所做工作的总结和对未来数字签名发展方向的展望。 第二章现有概率签名方案总结 所谓概率签名体制，是指在签名算法中加入一个随机数，这样每次运行签名 算法时由于使用了不同的随机数而导致产生的签名也不同，也就是对于同一个消 息m 可以有不同的签名。本章介绍了几种常见的概率签名体制，并重点分析了 一类典型概率签名体制的不安全性，他们都是在r s a 签名的基础上构造出来的。 2 1e i g a m a l 类型的概率签名体制 2 1 1e 1 g a m a l 签名体制 e l g a m a l 签名体制由t e i g a m a l 在1 9 8 5 年给出 1 4 。其修正形式已被美国 n i s t 作为数字签名标准d s s 。它是r a b i n 体制的一种变形。此体制专门设计作 为签名用，方案的安全性基于求离散对数的困难性。我们将会看到，它是一种非 确定的双钥体制，即对同一明文消息，出于随机参数选择不同面有不同的签名。 1 体制参数 p ：一个大素数，可使z 。中求解离散对数为困难问题； g ：是2 ，中乘群z ；的一个生成元或本原元； z ：用户私钥x z y = g r o o d p p ，g ，y 为公钥，x 为私钥a 2 签名过程 给定消息m ，签名者进行下述工作： ( 1 ) 选择秘密随机数蟊2 ： ( 2 ) 计算：h ( m ) r = 矿m o d p ，s = ( ( m ) 一x r ) k 。1m o d ( p - 1 ) 9 ( 3 ) 将趿。( m ，七) = s = ( r i i s ) 作为签字，将m ，( ，| l s ) 送给对方a 3 验证过程 验证者收到m ，( ，l is ) ，先计算h ( m ) ，并按下式验证： v e r k ( h ( m ) ，s ) = t r u e y r ，= g “”m o d p 如果等式成立，则认为此签名通过验证。 在此方案中，对同一消息m ，由于随机数k 不同而有不同的签名s = ( r l l 5 ) 。 4 安全性 攻击者不知用户秘密钥x 的情况下，若想伪造用户的签名，可选r 的一个值， 然后试验相应s 取值。为此必须计算l o g ，g s 。也可先选一个s 的取值，而后求 出相应r 的取值，试验在不知r 条件下分解方b y 0 a b ；g ”m o d p ，这些都是离 散对数问题。至于能否同时选出a 和b ，然后解出相应m ，这仍面临求离散对数 问题，即需要计算l o 岛y r ，。而对于已知明文密文对攻击，仍然面临解离散对数 问题。如果攻击者掌握了同一随机数r 下的两个消息，则可以解出用户的私钥x 。 因此，在实际应用中，对每个消息的签名，都应变换随机数k 。而且对某个消息 m 签名所用的随机数k 不能泄露，否则将可以解出用户的私钥x 。 2 1 2d s s 签名标准 d s s 签名标准是1 9 9 1 年8 月由美国k i s t 公布，1 9 9 4 年5 月1 9 日正式公布， 1 9 9 4 年1 2 月1 日正式采用的美国联邦信息处理标准，它和e l g a r n a l 签名类似。 d s s ( d i g i t a ls i g n a t u r e s t a n d a r d ) 中所采用的算法简记为d s a ( d i g i t a ls i g n a t u r e a l g o r i t h m ) 。算法描述： ( 1 ) 全局公钥( p ，q ，g ) p ：是2 “1 p 2 中的大素数，5 1 2 l s l 0 2 4 ，按6 4 b i t 递增； q ：( p - 1 ) 的素因子，且2 ”9 q 2 1 6 0 , 即字长1 6 0 b i t ： g ：= h 9 m o d p ，且1 h i 。 ( 2 ) 用户私钥x ：x 为在o x q 范围内的随机或拟随机数。 f 3 1 用户公钥y ：= g 。r o o d p 。 ( 4 ) 用户每个消息用的秘密随机数k ：在o k g 范围内的随机或拟随机数。 ( 5 ) 签名过程：对消息m ，其签名为s = s g t ( m ，七) = ( ，s ) 式中r ；( 矿m o d p ) m o d q ，s = - 1 ( ( m ) + ) 】m o d q ( 6 ) 验证过程：计算 w = 5 1 m o d q地= 【日( m ) w lm o d q u 2 = r wm o d qv = 【( 矿y 。) m o d p 】m o d q v e r ( m ，s ) = t r u e 铮v = 7 d s s 签名和e l g a m a l 签名属于同一类的概率签名，自从他们产生以来，在很 长的一段时期内其安全性都被认为基于一个有限域的予群上离散对数问题的难 解性。1 9 9 6 年，p o i n t c h e v a l 和s t e m 则成功地证明了在随机o r a c l e 模型下 5 】 e i g a m a l 类型的签名体制是基于离散对数难解性假设安全的。 2 。2p s s 类型的概率签名体制 以上是两种常用的概率签名体制，下面介绍另外一类概率签名体制，他们的 随机化方法和f i a t - s h a m i r 签名【1 5 类似。首先引入一种改进的r s a 签名体制 f d h r s a 。 由于r s a 签名中所涉及的运算都是模乘法运算和模指数运算，所以这样做 带来的缺陷是速度慢，而且签名太长。克服这些缺陷的一个办法是在对消息进行 签名之前作变换，采用啥希( h a s h ) 变换，把任意长度的消息映射为瓦中的元素， 缩短签名的长度，提高签名的速度。下面首先给出f d h - r s a 的密钥产生算法： a l g o r i t h m k 任选两个不同的大素数p , q ，长度均为k 2 比特 卜p q ；p - l 乏( ) ；d - - - e 。m o d q a ( n ) 础卜( ，e ) ；s k 卜( ，d ) r e t u r n p k ，s k 消息m 的签名和验证算法如下：( h a s h ： o ，1 ) + 一z ：) a l g o r i t h ms d ( m ) y 卜h a s h ( m ) x + _ y 。r o o d n r e t u m r a l g o r i t h m 蠼。( 肘，c r ) y 卜h a s h ( m 1 y 卜r m o d n i fy = y t h e nr e t u r n1e l s er e t u r n0 这就是f d h r s a 签名体制，在此基础上产生了一系列概率签名体制，他们的基 本设计思路都是在哈希函数中加入一个随机串，从而产生签名的随机性。 2 2 1 概率签名p s s o 这是概率签名的第一个版本，由f d h - r s a 演变而来，其中用到公共的哈希 函数日： o ，1 ) 一z ：，使用时可以当作个随机o r a c l e ，并加入了一个随机串r 来使m 随机化。密钥产生算法k 同f d h - r s a 。消息m 的签名和验证算法如下： a l g o r i t h ms ：d t m 、 r 士 o ，l 5 x 4 - - y a m o d n r e t u r n ( r ，x ) a l g o r i t h m 巧忽( m ， p a r s e c r 船( ，x ) w h e r el ， s y 卜n ( r i l m ) i f r m o d n = y t h e nr e t u r nle l s er e t u r n0 其中s 是随机串r 的长度，由签名者选定。注意到这里的签名不仅仅是z ：中的 一个元素，还包括一个长度为s 的随机串r ，否则签名就无法验证。因此这种签 名的长度较长。 【6 6 中给出了p s s 0 的安全性分析，证明它和r s a 签名体制的可求逆性紧密 相关。如果攻击者能攻破p s s 0 体制，则一定能对r s a 求逆：而如果攻击者能 对r s a 求逆，则不一定能攻破p s s 0 体制。这个安全性差距可以由攻击者访问 哈希o r a c l e 和签名o r a c l e 的次数以及参数s 来表示。 2 2 2 概率签名p s s p s s o 相对r s a 签名体制来说安全性提高了，但是却是以增加了签名长度为 代价。1 9 9 6 年，b e l t a r e 等人提出了一种改进的概率签名体制p s s 【6 】。这神体制 的签名长度和f d h r s a 体制相同，安全性也比较高。 该签名的密钥产生算法足弼f d h - r s a ，与p s s 0 不同的是，该体制又引入 了两个参数k ，k 。，满f f ：l 1 - 2 一“ 这个概率是由v u f v e r 选择随机数。 2 ( 唯一可证性) ： 对每一个v u f p k ，x ，v t ，v 2 ，p r o o f , ，p r o o f 2 ，其中v 1 v 2 ，下面的不等式对于 i = 1 或i = 2 都成立： p r v u f v e r ( v u f p k ，x ，v f ，p r o 够) = y e s 0 是一个常数。t = ( 磊，乃) 是任意一对算法，满足第一次输入为1 时，珏( ，) 和弓( ，) 总共运行最多2 ”步。则t 在下面的实验中成功的概率 至多为1 2 + 1 2 ”： ( a ) 运行v u f g e n ( 1 。) ，得到( v u f p k ，v u f s k ) 。 ( b ) 运行硭”呲“8 e 、”“州”砒( 1 ，v u f p k ) ，得到( z ，g u e s s ) 。 ( c ) 如果x o ，1 4 “，g u e s s = v u f e v a l ( v u f s k ，x ) ，并且x 没有被毛或乃作 为v u f e v a i ( v u f s k ，或v u f p r o v e ( v u f s k ，) 的查询串查询过，则 t = ( 五，弓) 成功。 v u f 将v r f 的伪随机性替换为函数值的不可预测性，它又可以看做为对于 每一个消息和公钥签名也唯一的一种签名体制( u n i q u es i g n a t u r e ) 【2 3 。为了构 造v r f ，只要构造一个唯一签名，再把它转化为v r f 目p 可。 唯一签名对同一个消息只能有唯一的一个签名。它在随机o r a c l e 模型下的实 现是众所周知的。比如，某些r s a 签名是唯一的；吒“沏) = ( 日 ) ) zm o d n 是 ( 即，e ，h ，m ) 的函数，只要e 是一个大于n 的素数。 2 3 】中，g o l d w a s s e r 和o s t r o v s k y 给出了一种在公共随机串模型下的唯一签名。此外，m i c a l i ，r a b i n ，v a d h a n 还给 出了标准模型下的唯一签名。 3 1 】 下面我们举例说明如何构造唯一签名并用它来构造v r f ，我们所用的假设 是g d h 假设。 2 7 设g 是一个阶为素数q 的循环群，g 是其生成元，木是群上的运算。存在算法s ， 使得g 上的c d h 问题是难的；同时存在算法d ，使得g 上的d d h h i 题是容易的。 也就是晓，对于任意概率多项式时间的一组攻击者 4 ) ，存在一个可忽略的函数 v ( 女) ，满足： p r 【( 女，g ，g ) 七- s ( 1 。) ；x 卜乙；y 卜z 叮；z 卜a k ( ，g ，q ，g ) ：z = g v ( 尼) 同时算法d 可以判定语言。： 三d = ( ，g ，g ，x ，y ，z ) 3 x ，y z 。使得x = g ，y = g y , z = g ” 假设l ：( g d h 假设) 即上述算法s ，d 同时存在。 假设2 ：( 多元c d h 假设) 即对于任意一簇概率多项式时间攻击者 4 ) ，对于任 意，= o ( 1 0 9 k ) ，存在一个可忽略的函数v ( k ) ，满足： p r ( $ ，g ，g ) 七一s 0 。k y ，一z q ：1 i z ) ； 乙2 马”；乙2 9 乙：j 亡【f ) ； z 卜4 ( ，q ，g ， 乙：j c 【埘) ：z = g n ”】s v ( k ) 也就是已知g “一玎，其中j 是 1 ，f 的所有真子集，计算g “；一y 1 是难的。 假设3 ：( 多元g d h 假设) 多元c d h 问题是难的，而d d h i ； 题是容易的。 在多元g d h 假设下，构造唯一签名，也就是给定算法s ，d ，构造算法 g ，s g n ，您，痧： a l g o r i t h m g ： 运行算法s 得到( + ，g ，g ) 。选择乙中k 对随机值( d | 0 啊。) ，( 0 ，) ，构成签名者 的私钥s k 。再选择一个长度为w ( 七) 比特的随机串r ，其中w ( k ) 是唯一表示群 中元素所需的最少比特数。设4 。= g a 。, bl f 七，b o ，1 ) ，对应的公钥是 p k ：( ，g ，g ，r ， 4 o ，4 1 ：1 i 栉) ) 。 a l g o r i t h ms i g n ： 对一个n 比特长的消息坍：m 。，输出签名( 掰) = 砜。= g r i , = , a j 一：1 s f 目) a l g o r i t h mv e t 痧： 设s = 1