（计算机软件与理论专业论文）基于完美单向函数的fiatshamir类数字签名协议及安全性研究.pdf

摘要： 在日益信息化的当代世界，网上各种信息流通和各种电子商务的开展过程 中，提高信息安全成了一个非常紧迫的课题。为了在数字世界中实现个人通信的 私密性以及完成各种授权、认证等功能，大量密码方案应运而生，而数字签名方 案是其中一个重要组成部分。 同其他密码体制一样，数字签名的应用过程中，人们主要关注他们的安全性 和签名的运算效率。本文分析了已有的数字签名方案在安全性上的缺陷，着重分 析了流行的f i a t - s h a m i r 方法设计数字签名方案的安全隐患，然后利用能完美隐 藏输入信息的完美单向函数这个新近被提出的方案，构造出一个新的概率签名方 案p o 、肌s c l l l l o r r 签名方案。我们在这个方案的防伪造安全性证明中，完全抛 弃了随机o r a c l e 模型，而是在标准模型下借助黑盒访问证明了它的安全性。这就 基本解决了g o l d w a s s e r 等人在0 3 年指出的f j a t s h a m i r 类签名方案在理想的随机 o r a c l e 下和实际使用时的安全鸿沟问题。本文同时还证明了该方案还有内容隐藏 等良好性质，而且计算复杂度方面只比s c h n o r r 签名方案多一次模平方运算，更 进一步的，如果使用较强假设的散列函数代替完美单向函数，那么得到的方案几 乎和s c h n o r r 签名同样高效，因此是很有吸引力的一个签名方案。 关键词：f i a t s h a m i r 方法，2 - u n i v e r s a l ，正规函数，完美单向，随机o r a c l e ，黑 盒模型，内容隐藏 中图法分类号：t p 3 9 3 0 8 a b s t r a e t ： i nt h em o d e mw o r l d ，、i t ht h ei n f o r m a t i o nr e v o l u t i o n ，t h ei m p r o v e m e n to f i n f o r m a t i o ns e c u r i t yi nt h ec o m m u n i c a t i o na n de - c o m m e r c eo n - l i n ei sb e c o m i n ga v e r yu r g e n tt a s k i no r d e rt os a t i s f ya l lk i n d so f f u n c t i o n ss u c ha sp r i v a c y ， a u t h o r i z a t i o na n da u t h e n t i c a t i o n ，m a n yc r y p t o g r a p h i cs c h e m e sh a v ee m e r g e d a m o n g t h e m d i g i t a ls i g n a t u r es c h e m e s a r ev e r yi m p o r t a n t j u s ta so t h e rc r y p t o g r a p h i cs c h e m e s ，i nt h ea p p l i c a t i o no f d i g i t a ls i g n a t u r e s ， p e o p l ef o c u so nt h e i rs e c u r i t ya n de f f i c i e n c y i nt h i st h e s i s ，w ea n a l y z es o m ef l a w so f k n o w ns i g n a t u r es c h e m e s ，a n de s p e c i a l l yf o c u so nt h es e c u r i t yc o n c e mo f t h ep o p u l a r s oc a l l e df i a t - s h a m i rp a r a d i g m t h e n ，w i t ht h eh e l po f ar e c e n t l yp r o p o s e dp r i m i t i v e n a m e dp e r f e c t l yo n e - w a yf u n c t i o nw h i c hc a np e r f e c t l yh i d et h ei n p u tm e s s a g e ，w e c o n s t r u c tan e w p r o b a b i l i s t i cs i g n a t u r es c h e m e p o ws c h n o r rs i g n a t u r es c h e m e t h e nb yu s i n gb l a c k - b o xa c c e s s ，w ep r o v e di t ss e c u r i t yu n d e rt h ec h o s e n - m e s s a g e a t t a c ku n d e rs t a n d a r dm o d e l ，n o tr a n d o mo r a c l em o d e l w ea l s op r o v e dt h a to u r s c h e m eh a sap r o p e r t yn a m e dc o n t e n t - c o n c e a l e ds e c u r i t y , a n df u r t h e rm o r e ，o u r s c h e m eu s e sj u s to n em o r em o d u l a r s q u a r et h a ns c h n o r rs i g n a t u r e ，a n di sa l m o s ta s e f f i c i e n ta ss c h n o r ri f w eu s eh a s hf u n c t i o nw i ms t r o n g e rs e c u r i t ya s s u m p t i o nt o r e p l a c ep e r f e c t l yo n e - w a yf u n c t i o n s oi ti sa l la p p l i c a b l ya t t r a c t i v es i g n a t u r es c h e m e k e yw o r d s ：f i a t - s h a m i rp a r a d i g m ，2 - u n i v e r s a l ，r e g u l a rf u n c t i o n ，p e r f e c t l yo n e w a y , r a n d o mo r a c l e ，b l a c k b o xm o d e l ，c o n t e n t - c o n c e a l e d c l a s s i f i e a t i o nc o d e ：t p 3 9 3 0 8 2 第一章引言 数字签名在信息安全领域有许多应用，包括授权、数据完整性和不可抵赖性 等等。数字签名的最重要的应用之一是在大型网络中使用于公钥的数字证书中。 数字证书是受信第三方( t r u s t e d t h i r d p a r t y ) 对用户的身份和公钥进行绑定的手 段，这样在往后他人要验证该用户的公钥时可以在没有受信第三方的协助下完 成。 1 9 7 6 年，d i 伍e 和h e l l m a n 发表了他们开创性的论文“密码学的新方向” 1 ，开创了公钥密码学。在这篇论文中他们提出了数字签名的概念。两年后， 实用的数字签名方案才开始出现。第一个实用的数字签名方案是r s a 数字签名 2 】。该签名方案至今仍然是最广泛使用的数字签名方案之一。 所谓对一条信息的数字签名实际上是一个数字，该数字的产生依赖于签名者 掌握的某个秘密。通常数字签名必须是公开可验证的，如果对于签名者是否对某 文档签过名产生了纠纷的话，一个公正的第三方应该可以在不需要知道签名者的 秘密的情况下验证签名，解决争端。 消息签名与消息加密有所不同，消息加密和解密可能是一次性的，它要求在 解密之前是安全的；而一个签名的消息可能作为一个法律上的文件，如合同等， 很可能在对消息签署多年之后才验证其签名，而且可需要多次验证此签名。因 此，签名的安全性和防伪造的要求更高些，并要求验证速度比签名速度还要快些， 特别是联机在线实时验证。随着计算机网络的发展，过去依赖于手书签名的各种 业务都可用这种电子数字签名代替，它是实现电子贸易、电子支票、电子货币、 电子购物、电子出版及知识产权保护等系统安全的重要保证。 为了实现签名目的，发送方必须向收方提供足够的非保密信息，以便使其能 验证消息的签名：但又不能泄露用于产生签名的机密信息，以防止他人伪造签名。 因此，签名者和证实者可公用的信息不能太多。任何一种产生签名的算法或函数 都应当提供这两种信息，而且从公开的信息很难推测出用于产生签名的机密信 息。再有，任何一种数字签名的实现都有赖于仔细设计的通信协议。 1 1数字签名的基本定义 数字签名有两种：一种是对整体消息的签名，它是消息经过密码变换的被签 名消息整体；一种是对压缩消息的签名，它是附加在被签名消息之后或某特定 位置上的一段签名图样。若按明文、密文的对应关系划分，每一种又可分为两个 子类：一类是确定性( 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 1 g a m a l ，p s s 等签名。 一个签名方案是由两个部分组成：签名算法和验证算法。签名者能使用一个 ( 秘密的) 签名算法s i g 来签名消息m ，产生的签名s i g ( 小) 能利用公开的验证算 法w ，来验证。给定一个消息、签名对( m ，s i g ( m ) ) ，验证算法返回答案是“真” 或“假”取决于签名是否真实。标准的数字签名定义如下： 定义1 1 ：一个数字签名体制是一个三元组( g ，s ，矿) ，满足以下条件 密钥生成算法g ：概率多项式时间算法，输入为1 ，其中k 为安全参数。 输出密钥对( p k ，8 k ) ，其中蹦是公钥，s k 是私钥。 签名算法s ：输入安全参数1 ，私钥s k 和消息m o ，1 r ，输出m 的签名 盯。可以是概率多项式时间算法，在一些方案中，可以接受其他参数作为 输入。 验证算法v ：多项式时间算法。输入公钥p k ，消息m ，签名盯，输出1 ( “真”) 或0 ( “假”) 来表明签名是否合法。一般情况下不要求是概率算 法a 满趴胀删= 雠尹巍鬣哟 ! 2数字签名的安全性 为考虑数字签名协议的安全性，g o l d w a s s e r ，m i c a l i 和y a o 等在 3 中首先提 出数字签名安全性定义，并在文献( 4 ， 5 ， 6 ， 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 时未被询问过的。稍弱一点的签名安全性定义是指在 唯钥攻击下的存在性不可伪造。所谓唯钥攻击，其实也就是不让攻击者访问签名 o r a c l e 。 下面给出自适应性选择消息攻击下存在性不可伪造安全和唯钥攻击下存在 性不可伪造安全的形式化定义： 定义1 2 抗自适应选择消息攻击的存在性不可伪造签名：我们称一个数字 签名方案( g ，s ，矿) 是在白适应性选择消息攻击下存在不可伪造的，如果对于任意 的( 胀，s k ) 卜g ( 1 ”) ，任意概率多项式时间算法m ，任意多项式p 和足够大的h ， 满足： p r ( a ，) 卜m 5 “( p k ) & a 诺q ( p k ) ：v ( p k ，口) = 1 1 p ( n ) 其中是供m 访问的签名o r a c l e ，鳓( 胀) 是m 以p k 为输入时向签名o r a c l e s 。提出的签名请求集合。 定义1 3 ，抗唯钥攻击的存在性不可伪造签名：我们说一个数字签名方案 ( g ，s ，矿) 是在唯钥攻击下存在性不可伪造的，如果对于任意的( p x ，s k ) 卜g ( 1 ”) ， 任意概率多项式时间算法m ，任意多项式p 和足够大的n ，满足： p r ( a ，) 卜m ( p k ) ：v ( p k ，口) = 1 】 1 p ( 门) 1 3 常用数字签名方案介绍 我们把常用的数字签名方案分成三大类：1 ，基于大数分解难解性的r s a 及 其相关签名方案：2 ，基于离散对数难解性的d s a 及其相关签名方案；3 ，从身 份认证体制使用f i a t s h a m i r 方法转化得到的签名方案，我们称为f i a t s h a m i r 类 数字签名方案。这里简单介绍第一、第二种签名方案，第三种是本文研究的重点， 将在第二章详细介绍。 1 3 1r s a 类数字签名方案 和r s a 加密方案相同，r s a 签名方案及其相关方案如r a b i n 签名方案的安 全性主要依赖于大整数因式分解问题的难解性。 首先介绍r s a 签名方案。 密钥生成算法g ：随机产生两个( 二进制表示) 长度差不多的素数p 、q ， 计算n = p q ，庐= ( p 一1 ) ( g 一1 ) ，随机选择一个8 ，1 e 庐，要求满足 g c d ( e ，) = 1 ，再使用扩展的欧几里德算法计算满足l d 庐和e d = 1 m o d e 的d 。 选用个散列函数h ： 0 ，1 ) 斗乙作为系统参数。发布( 聆，e ) 作为公钥，d 作为私 钥。 签名算法s ：计算j = ) 4 r o o d n 作为对消息 的签名。 验证算法v ：以m 、s 和经认证的公钥( n ，p ) 为输入，计算h = j 。m o d 月如果 h = ( m ) 则通过验证，否则拒绝。 签名和验证的可靠性来自费马小定理，如果s 是m 的一个签名，那么 s = ( 卅) 4 r o o d 胛，由于e d = 1 m o d 庐，所以旷= 厅( m ) “= h ( m ) m o d 即。 如果存在一个敌手( 一个适用的算法) 能分解某签名模数n ，那么它就可以 算得n 的欧拉函数值，进而由公开的验证密钥p 使用扩展的欧几里德算法算出 相应的签名密钥d ，如此就可以随意伪造签名，r s a 方案被完全攻破。 4 1 3 2 ，d s a 类数字签名方案 d s a 类数字签名方案通常是随机签名方案，签名和验证过程主要是z 上的 运算，其中p 是大素数。z ：上的离散对数难解性是这类数字签名方案保持安全 性的必要条件。 d s a 数字签名方案于1 9 9 1 年8 月由美国国家技术和标准局提出( n i s t ) ，之后 不久成为一个美国联邦信息处理标准( f i p s l 8 6 ) ，称为数字签名标准( d s s ) 。d s a 是第一个被一个国家政府承认的数字签名方案。 密钥生成算法：选择大素数p ，q ，使得qp l 。产生一个z ：中q 阶循环群的 一个生成元口，随机选取一个a ( 1 o q ) ，计算y = 口。m u d p 。最后输出 ( p ，q ，口，y ) 作为公钥，日作为私钥。 签名算法：随机选取整数k ，1 卅。如果对于任意的 概率多项式时间算法a 都有p r k 。以口( 七) = ( x ；y ) ：x y ，五( x ) = 五( y ) * 。0 ，则 称，是抗碰撞的。如果对于所有的k 蚝都有l ( u 。) = u 。，则称厂是正规的。 如果a ( n ) = ”，并且对于所有的k k ，五是一个排列，则称厂是排列簇。如果 z ( n ) o ) 完美单向函数，则称咒为 多值完美单向函数。多值完美单向函数直观上可以这么理解：给敌手a ( 概率多 项式时间算法) 一个o r a c l e ，要求a 在以下两种试验间进行区分：第一个试验： x 从一个预定义的分布中选出，并且一直固定不变，每次o r a c l e 被查询时都返回 这个x 的散列值瑰( x ，) ，其中r 是每次独立选取的随机串。第二个试验是o r a c l e 在每次被查询时回答一个散列函数值h a x ，) ，其中x ，r 是每次都按照各自得概率 分布独立选取的。r ( n 1 一v a l u e 完美单向性就是要求任意这样一个概率多项式时间 算法都不能区分这两种试验。 显然有：如果爿是t - v a l u e 完美单向，对任意的t ，咒都是r l _ v a l u e 完美 单向的。此外，文【3 1 还证明了以下结论：如果一个函数簇爿是相对于分布簇z 是2 一v a l u e 完美单向的，则它也是相对于刀语义完美单向的。 文【3 3 】提出的强完美单向性是针对其在证明 2 4 1 中提出的加密体制在非随机 o r a c l e 模型下的安全性的应用的，因此它针对的散列函数方案是一对算法 而不是函数簇，它们的完备性和抗碰撞性的定义类似于函数簇的相关定 义。 定义3 6 不可逆函数：厂是 o ，1 - - o ，1 的函数，抬 x 。) 。是一个概率 分布簇，如果对于任意的概率多项式时间算法a ，p 。即( 1 ”，( 力) = z ) 0 定义3 7 强( 预知部分信息的) 完美单向性：对于一个散列函数体制 ，如果对于任意一个输出时一个二进制位的概率多项式时间算法a ，对 任意一个良分布的分布簇胎 以 。，对任何相对于船 ) 。是不可逆的函数 ，都有： x ，4 ( ( x ) ，t t ( x ，) ) 。 其中，。r k ，x ，y 是按照 瓦 。各自独立的抽取，“。表示计算不可区分。则这 个散列函数体制称为是强完美单向性的。 3 2 完美单向函数的构造 本小节简单介绍完美散列函数的构造。这里介绍的构造基于正规的抗碰撞散 列函数的存在性假设。这种构造在统计学意义上满足完美单向性，但是其抗碰撞 性是计算性的。我们在第四章中提出的标准模型下可证安全的签名方案将要使用 这个完美单向函数方案。 在这里，我们构建一个相对于有足够大的最小熵的分布簇 瓦 的t v a l u e 完 美单向散列函数，这里要求函数t 不是太大，例如t ( n ) = 旷，f l 。简单的说这个 方案的是这样的：对于一个输入x ，首先用一个从2 一u n i v e r s a l 排列族中随机选 取的排列对x 随机化，然后再对这个结果用一个正规的抗碰撞散列函数进行散 列。 令c = l c ” 是一个抗碰撞的正规散列函数簇，输出长度是五= 五( n ) ，令 p = p 加) 是一个2 一u n i v e r s a l 排列簇，令t = t ( n ) 是一个正整数值的函数满足 n ( ，+ 1 ) a 。那么构造的概率散列函数簇以百”为密钥空间，以p 似为随机串空涮， 定义啊( x ，玎) = ，其中f e 叠”，丌p ( 。这样一个完美散列函数方案 相对于任意满足最小熵- l o g | | x o 忙o + 1 ) 五的分布簇 以) 是f v a l u e 完美单向 的。证明详见f 3 1 。 在实现这个方案时，可以使用现有的抗碰撞的散列函数如s h a 2 5 6 等代替 ，产生非常实用的体制，这时，对散列函数的假设只是强抗碰撞性和正规住， 虽然具体的s h a 2 5 6 等散列函数是否满足这两个性质还需要仔细斟酌，但是至 少这些是定义良好的属性，而不是像随机o r a c l e 那么空泛的假设。 3 3 完美单向函数的应用 完美单向函数有许多应用，首先是将某些在随机o r a c l e 模型下安全的方案转 换为标准模型下安全的方案；第二可以构造一个签名方案，使得签名不透露被签 名内容的任何信息：最后，完美单向函数还可以用于构造承诺方案和密钥交换协 议，使他们具有一些较特殊的性质。 先介绍用完美单向函数来构造内容隐藏签名方案。假定有人想要对一个文档 或者消息m 进行签名，使得别人如果事先知道m 内容的话就可以正常的验证， 而对于一个事先不知道m 的人来说，他不能通过这个签名获取关于m 的任何信 息，称签名方案的这种性质是内容隐藏的。这种签名可以用在签名方案的使用各 方事先对签名文档达成一致，而签名本身必须在一个无法加密的公开信道上传送 1 9 的场合。另外一个应用场合就是签名者想要事先发布对一个文件的签名，而这个 文件本身则必须稍后才公开。 这个内容隐藏的问题表面上看来根本不成问题，因为一般的签名方案都是先 对签名内容用一个安全的散列函数进行散列，然后再对这个散列值进行签名变 换，人们一般以为这样的散列函数隐藏了输入的所有部分信息，但实际上这是一 个假象，到目前为止都没有一个安全的敖列函数( 指传统意义上的强抗碰撞的散 列函数) 解决这个问题。事实上，这种签名方案所要求的内容隐藏的属性实际上 和完美单向函数的安全属性是完全一样的。 类似于完美单向函数的安全性有语义安全性的定义和不可区分性定义，内容 隐藏的签名方案也可以这样从两个不同角度进行定义。3 3 1 提出了不可区分性定 义： 定义3 1 0 内容隐藏( 不可区分) 签名方案：一个签名方案 ，如 果对任意输出是个二进制位的概率多项式时间算法4 ，任意良分布的签名消 息空间 眠) ，其签名算法s 满足： * 。 ，其中 m ，m ：是按照分布 丸) 独立选取的，则称此签名方案是内容隐藏的。 为了本文后面的讨论分析，我们引入内容隐藏签名方案的语义安全的概念。 定义3 1 l内容隐藏( 语义安全) 签名方案：一个签名方案 ，如 果对任意输出是个二进制位的概率多项式时间算法以，任意良分布的签名消 息空间 彤。 ，都存在概率多项式时间算法a ，使得： p r ai s ( m ) ) = 尸( m ) ) - p r a ( ) 叩( m ) ) 是随消息空间的长度n 可忽略的值，则称此签名方案为内容隐藏的。 ( 其中村 是提示o r a c l e ，并且l ( 鸭) = 1 如果m 1 = m 2 ，否则l m ( m 2 ) = 0 ，而尸是关于m 的 谓词) 。 显然，只需要在对消息m 进行签名前首先用一个完美单向函数进行处理就可 以达到内容隐藏的目的。因为假设存在一个输出二进制位的概率多项式时间算法 4 能区分对两条不同消息进行的签名的话，那么可以利用这个算法对完美单向 函数的安全性进行攻击，因为给定一个消息的散列值，只需对他进行签名变换， 然后将结果交给一4 进行区分即可，这个攻击的成功概率等于原算法4 的成功概 率。 完美单向函数还可以用来构建承诺( c o m m i t m e n t ) 方案：给定一个完美单向函 数h ，若相对m 进行承诺，则选择一个随机值p ，和m 进行( 二进制位串) 联 结，算得散列值h ( p l l m ，) 就是对m 的承诺，想要解承诺( d e c o m m i n t ) 的话， 只要公布p 和r n 即可。显然，由于完美单向函数的安全性( 完美单向性) ，而 且无论m 的长度如何，由于p 是随机选取得，因此p i i 所有足够大的最小熵，因 此得到的承诺方案是语义安全的。 另一个应用就是在密钥交换协议中，完美单向函数可以用来公布交换后的秘 密密钥的散列函数值，以便合法的各方验证自己是否正确无误的获得了那个密 钥，同时又保证原本就不该知道那个密钥的人无法从这个公开的散列函数值中获 得任何关于密钥的信息。 2 1 第四章基于完美单向函数的f i a t s h a m i r 类数字签名协议 本章将在前面两章分析的基础上，提出一个内容隐藏的在黑盒模型下抗选择 消息攻击的数字签名方案。首先分析s c h n o r r 签名方案的缺陷，由此得到新方案 的设计思路，然后给出p o w - s c h n o r r 数字签名方案的形式化定义，最后基于所 用的散列函数的语义完美单向性，证明我们的签名方案具有内容隐藏性。 4 1s c h n o r r 数字签名方案及缺陷分析 s c h n o r r 数字签名方案属于f i a t - s h a m i r 类数字签名，是由s c h n o r r 身份认证 协议经过f i a t s h a m i r 方法转变而来。第二章介绍一般的f i a t s h a m i r 方法，这里 具体介绍s c h n o r r 签名方案的产生过程。原身份认证方案的安全性基于离散对数 难解性假设，其基本思想是a 向b 证明自己掌握一个秘密( 但不揭示这个秘密) ， 即a 通过向b 证明自己掌握与公钥v 相对应的私钥a 来确认自己的身份，而这 个公钥v 经过第三方签名认证。为简明起见，阱下说明时默认公钥得到第三方认 证。 我们首先介绍s c l m o r r 身份认证方案。 a 通过以下描述的一个三轮协议向b 证明自己的身份： 1 ) 系统参数及密钥对选择： ( a ) 首先选择一个合适的素数p ，以使得p 一1 能被另一个素数q 整除。( 为 保证离散对数难解，一般取p 为t 0 2 4 位素数，q 为1 6 0 位素数) ( b ) 在乘法群z ：中选择q 阶元素。 ( c ) a 选择一个私钥a ，0 a q 一1 ，计算v = ”m o d p 作为公钥发布 2 ) 协议过程，此协议涉及三轮信息： a 寸b ：x = 7 m o d p( 1 ) a 卜b - e ( w h e r el e g ) ( 2 ) 爿 b ：y = a e + r m o d q ( 3 、 ( a ) ，a 随机选择一个r ，1 ，q - 1 ，计算x = p 7 m o d p ，发送( 1 ) 给b 。 ( b ) ，b 获取a 的公钥v 并发送( 2 ) 给a ( c ) ，a 发送( 3 ) 给b 。 ( d ) ，b 计算z = v 8 r o o d p ，并且在z = x 时确认a 的身份，否则拒绝 对s c h n o r r 身份认证方案使用f s 方法进行转变，也即选定一个散列函数作为 公钥的一部分，并且以m 和第一轮信息的散列函数值作为( 签名方自己生成的) 第二轮信息就得到了s c h n o r r 签名方案。系统参数的选择和身份认证协议完全相 同和密钥生成增加一个散列函数h ： 0 ，l + 寸乙作为公钥的一部分，即私钥是a ( 0 口s q 1 ) ，公钥是 。 签名算法s ( m ， ) ：随机选择一个k ( 0 k g 一1 ) ，然后计算r = “， e = h ( m i i ，) ，s = a e + k m o d q ，那么s 对消息m 的签名就是( j ，e ) 。 验证算法v ( ，v ) ：计算y = p 5 伊m o d p ，e = h ( m l | y ) ，当且仅当e = g 时接受 为m 的合法签名。 p o i n t c h e v a l 等人在 2 5 1 中证明了s c h n o r r 签名方案在随机o r a c l e 模型下的安全 性，但是由于s c l m o r r 签名同f i a t - s h a m i r 数字签名方案一样都是由对于诚实验证 者零知识的三轮公开随机串身份认证协议通过f s 方法转变而来的，因此，他也 受到【1 9 的攻击，也即这种方案用任何安全的散列函数进行实例化所得到的签名 方案的安全性都是不可靠的。 在完美单向函数的介绍中，注意到在用2 - u n i v e r s a l 散列函数簇构建完美单向 函数的时候，由于万p ( ”是随机选择的，而，是正规散列函数，因此，7 仍 然是2 - u n i v e r s a l 的，对于良分布的x 来说，l o t ( x ) ) 是在值域中随机均匀分布的， 这点性质将可以在以后的p o w - s c h n o r r 签名方案的安全性证明中用到，同时由 于2 - u n i v e r s a l 散列函数构建的p o w 作为较强性质的散列函数，具有通常对散列 函数要求的公开可验证性和强抗碰撞性等优良的特性，因此我们考虑在签名方案 中代替原来的散列函数的使用，以构造较强安全性质的签名方案。 同时由于运用了完美单向函数，所得到的签名方案具有一个额外的性质，就 是内容隐藏性。 4 2p o w s c h n o r r 数字签名方案 这一小节中，为了解决已有的f i a t s h a m i r 类签名方案在随机o r a c l e 模型下和 标准模型下安全性的分离问题，将完美单向函数应用到s c h n o r r 签名方案中，代 替原来的散列函数，得到一个新的称之为p o w - s c h n o r r 的数字签名方案，并且 在第5 章将证明该方案在标准模型下在选择消息攻击下是存在性不可伪造的。 p o w s c h n o r r 签名方案完整表述如下： 密钥生成算法g ：首先选择一个合适的素数p ，以使得p 一1 能被另一个素数 g 整除。( 为保证离散对数难解，一般取p 为1 0 2 4 位素数，g 为1 6 0 位素数) ， 定义q 的长度k 为安全参数，然后在乘法群z ：中选择g 阶元素。产生一个输出 长度为五= k 的正规抗碰撞散列函数簇c = f ，一个2 一u n i v e r s a l 排列簇 p = f p ( 川，( 为证明简单起见，这里令被签名的信息长度为n ，显然如果一般情况 的活。可以先用一个散列函数把任意长度的文档映射到长度为n 的串，再使用本 签名方案) 。选择一个私钥a ，0 s a 叮一1 ，计算v = m o d p ，随机选择，l c ， 然后将( v ，f ) 作为公钥发布。 签名算法s ( m ， ) ：随机选择一个k 和石( 0 k q 一1 ，石p “1 ) ， 然后计算，= 。，e = h j ( m ；r ，疗) = ，j = a e + k r o o d q ，那么s 对 消息m 的签名就是( s ，曲 验证算法v ( ， ( v ，) ) ：计算y = 4 v 。 ， e = 啊( 肌；y ，万) = ，当且仅当p 一= e 时接受 为m 的 合法签名。 这个新的签名方案是一个概率签名方案，就是两次进行对同一消息的签名将 得到不同的签名结果。这个随机性不仅来源于原来产生r = 卢“随机选择不同的 k ，还由于使用的完美单向函数本身含有随机性。每次选择不同的2 - u n i v e r s a l 排列得到不同的散列值。 4 3p o w s c h n o r r 数字签名方案的内容隐藏性 新签名方案是一个内容隐藏签名方案，下面证明签名方案满足语义安全的内 容隐藏性。 定理4 1 ：p o w 。s c h n o r r 签名方案是内容隐藏( 语义安全) 的数字签名方案。 证明：采用反证，即如果p o w s e h n o r r 不是内容隐藏的，那么其中使用的完 美单向函数不满足语义安全的完美单向性。即： 假设存在概率多项式时间算法4 和某多项式p ( n ) ( n 是被签名消息的长度) 对于任意概率多项式时间算法a 和按照分布m 抽取的m 满足： p r 4 ( h z ( m o r k ) ，a e + 尼) = p ( m ) 卜p r m ( ) = = p ( 埘) 】1 p 0 ) 由4 可构造概率多项式时间算法c ，对于p o w - s c h n o r r 签名方案中使用的 完美单向函数进行攻击。 首先有一个p o w ，其密钥空间是 ，挑战者在这个p o w 的定义域( 良 分布的x = m ) 中选择一个x x ，按相应分布选出，卫，计算出岛( x ) ，要求 c 以相对于任何概率多项式时间算法c k ( ) 有不可忽略的优势计算出某个关于 x 的谓词。 2 4 c 。首先利用这个p o w 产生一个p o w s c h n o r r 签名方案，相关参数同签名方 案定义，然后随机选择七( 0 k q 1 ) ，算得e = h a x ) ，a e + k ( m o d q ) ，那么 我们可以看出( 岛( x ) ，a e + k ) 实际上是对x o 矿的签名。这样，可以运行 a o a x ) ，+ k ) 输出一个谓词p ( x 矿) ，显然可以把和异或并入到谓词定义 中去产生另一个关于x 的谓词p 。于是有： p r c i 啊( x ) ) = p i x ) 】= p r 4 x ( 岛( x ) ，a e + 七) ) = p ( x o ) 】 而任意概率多项式时间算法c ，以，为o r a c l e 算出谓词尸( 曲( = p ( x o ) ) 的概率等于其以l x e p k 为o r a c l e 计算出谓词尸( z j ，而在已知矿的条件下， o r a c l e l x e p 和o r a c l