（计算机软件与理论专业论文）可截取签名体制研究.pdf

摘要 信息安全是信息社会急需解决的最重要问题之一，它已成为信息科学领域的一个重要新 兴学科。数字签名技术是提供认证性、完整性和不可否认性的重要技术，因而是信息安全的 核心技术之一，是安全电子商务和安全电子政务的关键技术之一。随着对数字签名研究的不 断深入，随着电子商务、电子政务的快速发展，传统的密码体制已不能完全满足需求，需要 研究更方便、更快捷和更高效的密码体制。 可截取签名是一种新的签名体制。与传统的数字签名体制不同，可截取签名允许使用者 针对原消息的一部分，从原始签名中截取一个可公开验证的签名，而无需和最初的签名者进 行交互。通过对可截取签名和传统的数字签名的比较，深入分析了可截取签名在电子商务、 电子政务等应用中的优势。在现有可截取签名体制的研究基础上，结合基于身份的密码系统 和群签名体制，构造了一个双线性对上基于身份的可截取群签名方案，可有效地实现对签名 的截取而无须和签名者多次交互，并给出了安全性和效率分析。 门限签名将密钥以门限方式分散给多个成员管理，整体签名由成员产生的部分签名组合 而成，可以提高系统的安全性，并解决了权利过于集中的问题。基于双线性对理论，提出了 一个基于身份的可截取门限签名方案，可有效地实现对签名的门限生成、签名截取而无须和 签名者多次交互。方案保证了签名效率和签名的强壮性，在随机预言模型下，证明了其在适 应性选择消息攻击和身份攻击下都能抵抗存在伪造。 与传统的公钥体制相比，自认证公钥体制不需要公钥证书，验证者在验证签名的同时就 能验证公钥的真伪，减少了对存储空间、计算代价和通信代价的需求。将自认证公钥体制与 可截取签名相结合，基于离散对数难题，提出了一个基于自认证的可截取签名方案，并分析 了其安全性。 关键词：数字签名；可截取签名；基于身份的可截取群签名；基于身份的可截取门限签 名；基于自认证的可截取签名 a b s t r a c t i n f o r m a t i o ns e c u r i t yi so n eo ft h em o s ti m p o r t a n tp r o b l e m si nm o d e mi n f o r m a t i o ns o c i e t ya n d b e c o m e san e wi m p o r t a n ts u b j e c ti nt h ei n f o r m a t i o ns c i e n c e d i g i t a ds i g n a t u r e ，w h i c hc a np r o v i d e a u t h e n t i c a t i o n ，i n t e g r i t ya n dn o n - r e p u d i a t i o n , i so n eo ft h ek e yt e c h n i q u e so fi n f o r m a t i o ns e c u r i t y a n dp l a y sav e r yi m p o r t a n tr o l ei ne - c o m m e r c ea n de - g o v e r n a n c e a st h ed e e p e n i n go fd i g i t a l s i g n a t u r er e s e a r c ha n dt h er a p i dd e v e l o p m e n to fe - c o m m e r c ea n de - g o v e r n a n c e ，t h es t a n d a r d c r y p t o l o g ys y s t e mc a nn o ts t i l lm e e tt h en e e di np r a c t i c e ，t h u sn e e dt os t u d ym o r ec o n v e n i e n t ，f a s t e r a n dm o r ee f f i c i e n t l yc r y p t o l o g ys y s t e m c o n t e n te x t r a c t i o ns i g n a t u r ei san e wd i g i t a ls i g n a t u r es y s t e m i te n a b l e st h eu s e rt oe x t r a c t s e l e c t i v e l yv e t i f i a b l ec o n t e n tf r o ms i g n e dd o c u m e n ta n di su n n e c e s s a r yf o r t h eu s e rt oc o n t a c tw i t h t h es i g n e r w ec o m p a r ec o n t e n te x t r a c t i o ns i g n a t u r ew i t hs t a n d a r dd i g i t a ls i g n a t u r e ，a n da n a l y z e t h ea p p l i e da d v a n t a g eo fc o n t e n te x t r a c t i o ns i g n a t u r e si ne - c o m m e r c ea n de - g o v e r n a n c e b a s e d o nt h eb i l i n e a rp a i r i n g s ，c o m b i n ei d e n t i t y - b a s e dc r y p t o g r a p h ya n dg r o u ps i g n a t u r e ，a ni d - b a s e d c o n t e n te x t r a c t i o ng r o u ps i g n a t u r ei sp r o p o s e d i te n a b l e st h eu s e rt oe x t r a c ts i g n a t u r ee f f i c i e n t l y a n di su n n e c e s s a r yf o r t h eu s e rt oc o n t a c tw i t ht h es i g n e f a n da n a l y z e si t se f f i c i e n c ya n ds e c u r i t y i nt h r e s h o l ds i g n a t u r es y s t e m ，s e v e r a lu s e r ss h a r et h ep r i v a t ek e yw i t ht h r e s h o l dm o d ea n dc a n c o o p e r a t ew i t he a c ho t h e rt og e n e r a t eav a l i dg r o u ps i g n a t u r e i tc o u l de n h a n c es e c u r i t yo ft h e s y s t e ma n ds o l v et h ep r o b l e mo fh i g hc o n c e n t r a t e dr i g h t s a n i d b a s e dc o n t e n te x t r a c t i o n t h r e s h o l ds i g n a t u r eb a s e do nt h eb i l i n e a rp a i r i n gi sp r o p o s e d e f f e c t i v et h r e s h o l ds i g n a t u r e g e n e r a t i o na n ds i g n a t u r ee x t r a c t i o no ft h ep r o p o s e ds i g n a t u r es c h e m ec a n b er e a l i z e dw i t h o u tm o r e i n t e r a c t i o nw i t ht h es i g n e r t h ep r o p o s e ds i g n a t u r es c h e m ee n s u r e se f f i c i e n c ya n dr o b u s t n e s s ，a n di s s h o w e ds e c n r ea g a i n s te x i s t e n t i a lf o r g e a b l eo na d a p t i v e l yc h o s e nm e s s a g ea n di da t t a c ki nt h e r a n d o mo r a c l em o d e l a sc o m p a r e dw i t hs t a n d a r dp u b l i ck e yc r y p t o s y s t e m s ，s e l f - c e r t i f i e dp u b l i ck e ys y s t e md o e sn o t n e e dp u b l i ck e yc e r t i f i c a t e ，av e r i f i e rc a nv e r i f yb o t hc e r t i f i c a t ea n ds i g n a t u r et o g e t h e r s oi tr e d u c e s t h es p a c es t o r a g ea n dc o m p u t a t i o n a le f f o r t s , a n ds a v e sc o m m u n i c a t i o nc o s t s b a s e do nt h ed i s c r e t e l o g a r i t h mp r o b l e m ，c o m b i n es e l f - c e r t i f i e dp u b l i ck e ya n dc o n t e n t e x t r a c t i o n s i g n a t u r e , a s e l f - c e r t i f i e dc o n t e n te x t r a c t i o ns i g n a t u r ei sp r o p o s e d ，a n da n a l y z e si t ss e c u r i t y k e yw o r d s ：d i g i t a ls i g n a t u r e ；c o n t e n t e x t r a c t i o ns i g n a t u r e ( c e s ) ；i d b a s e dc o n t e n t e x t r a c t i o ng r o u ps i g n a t u r e ；i d b a s e dc o n t e n te x t r a c t i o nt h r e s h o l ds i g n a t u r e ；s e l f - c e r t i f i e d c o n t e n te x t r a c t i o ns i g n a t u r e m 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包括其他人已经发表或撰写过的研究成果，也不包含为获得西 北师范大学或其他教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意。 签名： 垒j 堡丛e t l i 田：丝竺：兰：翌 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵守此规定) 签名： 痉f 颦压导师签名：巡! 日期：卫翌z ：丝 第一章绪论 信息安全是信息社会急需解决的最重要问题之一，它已成为信息科学领域的一个重要新 兴学科。数字签名技术是提供认证性、完整性和不可否认性的重要技术，因而是信息安全的 核心技术之一，是安全电子商务和安全电子政务的关键技术之一随着对数字签名研究的不 断深入，随着电子商务、电子政务的快速发展，传统的密码体制已不能完全满足需要，因此 需要研究更方便、更快捷和更高效的密码体制从这个研究角度出发，本篇论文对可截取签 名体制作了进一步的理论研究。 1 1 密码学和数字签名 1 1 1 信息安全和密码学 信息安全的中心内容是保证信息在信息系统中的保密性和认证性。所谓信息的保密性， 是指信息在生成、传递、处理和保存等过程中不能被未授权者提取。所谓信息的认证性，是 指信息在生成、传递、处理和保存等过程中，不能被非法地窜改、删除、重放和伪造等。解 决信息安全问题是一个庞大的系统工程，需要综合运用数学、计算机、信息论、密码学、通 信技术、管理技术等各种学科和技术的研究成果，并且需要在实践中不断提高和不断探索。 其中，密码学给解决信息安全问题提供了许多有效的核心技术，在保证信息的保密性、认证 性等方面发挥着关键性的作用。 简单地说，密码学( c r y p t o l o g y ) 是研究信息系统安全的一门学科。它主要包括两个分支， 即密码编码学( c r y p t o g r a p h y ) 和密码分析学( c r y p t a n a l y s i s ) 。密码编码学是对信息进行编码以 实现信息隐蔽的一门学科，其主要目的是寻求保护信息保密性和认证性的方法。密码分析学 是研究分析破译密码的学科，其主要目的是研究加密消息的破译和消息的伪造。密码编码学 和密码分析学既相互对立又相互促进地发展。 密码技术的基本思想是对消息做秘密变换，变换的算法即称为密码算法。决定秘密变换 的秘密参数叫做密钥( k e y ) 。在密钥的作用下，把有意义的明文( p l a i n t e x t ) 变换成无意义的密 文( c i p h e a e x t ) 的变换叫做加密算法( e n c r y p t i o n ) ，相应的逆变换叫解密算法( d e c r y p t i o n ) 。若 在密钥的作用下把消息变换成一种“证据”，用来说明某个实体对消息内容的认可，则称变换 为签名算法( s i g n a t u r e ) ，相应的逆算法称为验证算法( v e r i f i c a t i o n ) 。 根据密钥的特点，密码体制( c r y p t o s y s t e m ) 可分为公钥密码体制( p u b l i c - k e yc r y p t o s y s t e m ) 西北师范大学硬士学位论文 第一章绪论 和私钥密码体制( s e c r e t k e yc r y p t o s y s t e m ) 。公钥密码体制也称作非对称密钥密码体制，而私 钥密码体制也称其为对称密钥密码体制。在私钥密码体制中，加密和解密算法使用的密钥相 同或实质相同。在公钥密码体制中，加密和解密算法使用的密钥不同，而且从一个难于得到 另一个。 1 1 2 公钥密码体制和数字签名 1 9 4 9 年，s h a n n o n “1 发表了“保密系统的通信理论”，用信息论的观点对信息保密问题作 了全面的阐述。这使得信息论成为研究密码编码学和密码分析学的一个重要理论基础，宣告 了科学的密码学信息理论时代的到来。虽然s h a n n o n 证明了理论上不可攻破的传统密码体制 的存在，但是密钥管理始终是传统密码体制的一个主要难题。假设开个用户想要两两进行秘 密通信，那么他们必须通过安全信道交换大约厅伽一1 ) 2 个密钥。而真正安全的信道是很难得 到的，安全信道的费用比非安全信道要高得多。 1 9 7 6 年，d i f f i e 和h e l l m a n 。1 为了解决密钥管理问题，在他们奠基性的工作“密码学的新 方向”中，提出了一种密钥交换协议，允许通信双方在不安全的媒体上交换信息，安全地协 商一致的密钥。在此新思想的基础上，很快出现了“非对称密钥密码体制”，即“公钥密码体 制”。由于在公钥密码体制中，加密和解密的密钥不同，且能公开加密密钥，而仅需保密解密 密钥，所以公钥密码体制中存在的密钥管理问题变得相对简单。公钥密码体制还有一个优点 就是拥有信息认证性等新功能。 在文献 2 中，d i f f i e 和h e l l m a n 利用公钥密码学的思想提出了数字签名的概念。数字签 名是指用户用自己的私钥对原始消息进行加密所得的数据。信息接收者使用信息发送者的公 钥对附在原始消息后的数字签名进行解密后获得明文，并通过与自己收到的原始消息对照， 便可确信原始信息是否被篡改，这样就保证了数据传输的不可否认性。 第一个数字签名方案由r i v e , s t 、s h a m k 和a d l e m a n ”1 提出，即r s a 方案。这一方案是建 立在他们提出的一个假设，即r s a 假设之上的。早期的数字签名方案主要由l a m p o r t 、 m e r k l e “1 和r a b i n 呦等提出。1 9 9 0 年，r o m p e l m 证明了数字签名存在的充分必要条件是单向函 数的存在。经过二十多年的发展，己经有许多高效、安全的数字签名方案被相继提出，比较 著名的有e l g a m a l 伽，s c l m o r r 伽，d s a “们，o k a m o t o ，f i a t s h a m i r ，n y b e r g r u e p p e l 1 等。 1 2 数字签名理论 1 2 1 数字签名的一般定义n 帕 数字签名是一种给以电子形式存储的消息签名的方法。签名之后的消息能通过计算机网 2 西北师范大学颈上学位论文 第一章绪论 络传输，签名算法必须以某种形式将签名“绑”到所签文件上，数字签名能通过一个公开的 验证算法对它进行确认。 一个数字签名是由两个部分组成：签名算法和验证算法。签名者使用一个( 私有的) 签名 算法咄来为消息工签名，签名结s i g ( x ) 随后能使用一个公开的验证算法阳得到验证。给 定数据对0 ，) ，) ，验证算法根据签名是否有效而返回该签名为“真”或“假”。签名方案的正 式定义如下： 一个数字签名方案是由一个五元组( p ，a ，k ，s ，矿) 组成，它满足下列条件： ( 1 ) p 是一个所有可能消息的有限集； ( 2 ) a 是一个所有可能签名的有限集； ( 3 ) k 是密钥空间，是所有可能密钥的有限集； ( 4 ) 对每一个七k ，有一个签名算法啦l s 和一个相应的验证算法旧ie v 。对每一个 消息x e p 和每一个签名y e a ，每一个s 喀t ：p - 彳和v e r k ：p 彳- - ) t r u e ，f n t s e 都是满足下列 方程的函数： v e r ( x , y ) - 氍；。= s 啦i g 暑( x 由x e p 和y e a 组成的数据对o ，y ) 称为签名消息。 对每一个七e k ，s i g tv e r k 应该是多项式时间函数。v e r k 是公开的函数，i l 百s i g t 是保密 的。给定一个消息工，除了签名者之外，任何入去计算使v 盯o ，y ) 一t r u e 的数字签名y 应该是 计算上不可行的( 注意，对给定的石，可能存在不止一个y ，这要看函数v e t k 是如何定义的) 。 如果攻击者能够计算出使得v e r ( x ，y ) 一t r u e 的数据对 ，y ) ，而工没有事先被签名者签名，则 签名y 称为伪造签名。非正式地，个伪造签名是由签名者之外的其他人产生的一个有效的 数字签名。 1 2 2 数字签名的基本要素 数字签名方案包括五个部分，签名( 静态数据) 、协议( 签名、发送和验证) 、签名方、验 证方和仲裁方。签名与验证的技术包括：单向函数( 单向陷门函数和单向h a s h 函数) 、零知识 证明、证书、密钥管理与分配。数字签名包括以下基础模块： 1 单向函数：单向函数是这样一种函数，计算起来相对容易，但求逆却很困难，即已知 x ，很容易计算厂 ) ，但已知f ( x ) ，却难于计算x 。然而，按照严格的数学定义，单向函数 的存在性还没有证明。即使这样，还是有很多函数看起来象单向函数，我们能够有效地计算 它们，但至今依然没有找到能够容易地计算它们的逆的有效办法。在签名中，实际使用的单 向函数有：幂指数函数、椭圆曲线函数和平方函数等。 3 西北师范大学硕士学位论文 第一章绪论 单向陷门函数：单向陷门函数是一个有秘密陷门的特殊单向函数。它的一个方向易于计 算，而反方向却难于计算。但是。如果知道秘密陷门，则可以很容易地反向计算这个函数。 单向h a s h 函数：单向h a s h 函数有很多种叫法：压缩函数、渐缩函数、消息摘要、指纹、 密码校验和、数据完整性检测( d i c ) 、操作检验码( m d c ) 、消息鉴别码( m a c ) 和数据鉴别码 ( d a c ) 。单向h a s h 函数既是单向函数，又是h a s h 函数，从输入串很容易计算出其哈希值， 但要产生一个串，使其哈希值等于这个值，却是很困难的。单向h a s h 函数主要有两类：带密 钥和不带密钥的h a s h 函数。不带密钥的h a s h 函数任何人都可以计算，它仅仅是输入串的函 数；带密钥的h a s h 函数是输入串和密钥的h a s h 函数，只有持有密钥的人才能计算单向哈希 值( 它等同于先计算单向哈希值，然后再对它加密) 2 零知识证明( z e r ok n o w l e d g ep r o o f ) ：以p 表示示证者，以v 表示验证者，p 要向v 证 明知道某个秘密。如果以一种有效的数学方法，使v 可以验证每一步成立，最终确信p 知道 这个秘密，而又能保证不泄露p 所知道的信息，这就是所谓的零知识证明问题。 零知识证明满足以下条件： ( 1 ) 示证者几乎不可能欺骗验证者，若p 知道证明，则可使v 几乎确信p 知道证明。若p 不知道证明，则他使v 相信他知道证明的概率接近于零。 ( 2 ) 验证者几乎不可能得到证明的信息，特别是他不可能向其他人出示此证明。 ( 3 ) 验证者从示证者那里得不到任何有关证明的知识。 这些证明通过交互协议实现，v 向p 提问，若p 知道证明，则可正确回答v 的提问；若 p 不知道证明，则对提问给出正确回答的概率仅为1 2 。v 以足够多的提问就可推定p 是否知 道证明，且要保证这些提问及相应的回答不会泄露出p 所知道的有关知识。 3 证书：一个可信的发证机构给每一个用户分配唯一的名字并签发一个包含名字和用户 公开密钥的证书。证书有一个具体的有效日期，当证书失效后，它将从c a ( 发证机构) 维护的 公共目录中删除。签发此证书的c a 依旧保留此证书的剐本，以备日后处理解密可能引起的 纠纷。 4 密钥管理与分配：在现代信息系统中，通常需要的密码系统是公开的，一旦秘密密钥 失密，则整个系统无安全性可言，若密钥出错，则不能传送正确信息，因而整个系统的安全 性就主要取决于对秘密密钥的保护管理。密钥管理包括密钥的产生、分配、存储、保护、销 毁等一系列过程，其中密钥的产生、分配和存储是最关键的问题。 一个通信网信息系统通常需要大量不同功能的密钥。主机、节点和用户中的密钥的产生 是不同的。按使用功能区分，一个信息安全系统的密钥可以大致分为以下几种： ( 1 ) 基本密钥：它是由用户专用并在较长时问内保持不变的秘密密钥，它和会话密钥一起 用于控制产生加密密钥的密钥流。它可用随机或伪随机方法产生。 4 西北师范大学硕士学位论文 第一章绪论 ( 2 ) 会话密钥：它是用户在一次传送消息或通话过程中用于保密传送信息的密钥。这种密 钥一般更换频繁，可以由系统在密钥加密密钥的作用下，通过某种加密算法动态地产生。 ( 3 ) 用户密钥：它是用于区分不同的用户而附加于基本密钥上的密钥 ( 4 ) 密钥加密密钥：它是用于对会话密钥进行保密的密钥。它可以由伪随机产生器自动产 生，也可以由主密钥控制下的某种算法来产生，随基本密钥分发。 ( 5 ) 主机主密钥：它是对密钥加密密钥进行加密保护用的密钥，它长时间保持不变，因而 其安全性是至关重要的。它的产生必须用绝对随机的方法来产生 密钥分配可以分为三种类型：集中式分配和分布式分配以及集中和分布的结合分配。集 中式分配是利用网络中的密钥管理中心来为用户提供安全分配密钥的服务；分布式分配是用 户之间通过它们自己的协议来实现密钥分配；第三种方式是前两种方式的结合。 1 2 3 数字签名的安全性所基于的困难问题 数字签名方案的安全性都是基于某些困难问题的，这些困难问题主要有以下三个： 1 离散对数问题。这类应用特别广泛，现在的大部分签名方案，如e i g a m a l 方案、d s a 方案和许多协议的设计都是基于此困难问题的。 2 椭圆曲线问题。这是近年来研究的热点，椭圆曲线问题于离散对数问题是相对应的， 它与离散对数问题相比，优点在于速度快，更加实用，但缺点是安全参数的选取比较复杂。 3 大数分解问题。众所周知的r s a 数字签名方案就是基于大数分解问题的数字签名方 案。基于二次剩余问题也可以设计数字签名方案，例如r a b i n 签名方案等。二次剩余问题既 可以认为是一个单独的数学难题，也可以认为是大数分解问题的特殊情况。 近年来，利用双线性对技术来构造各种不同形式的数字签名方案，成为数字签名领域的 又一研究热点，它是利用超奇异椭圆曲线中w e i l 或t a t c 对所具有的双线性性质来构造各种数 字签名方案。 有基于一个困难问题的签名，也有基于多个困难问题的签名。基于多个困难问题的签名 方案的提出主要是多个困难问题的同时解决比一个困难问题的解决更难，从而增强了签名方 案的安全性。 1 2 4 数字签名的安全性 1 可能存在的攻击 攻击者攻击一个密码算法通常采取的攻击方法可以分为两大类“”。其一是确定性分析法， 其二是统计分析法。确定性分析法是指利用一个或几个已知量，用数学关系式表示所求未知 量，已知量和未知量的关系视签名算法和验证算法而定，寻求这种关系是确定性分析法的关 键步骤，现在对数字签名方案的攻击绝大多数采用这种方式。统计分析法是指利用已知消息 西北师范大学硕七学位论文 第一章绪论 及其相应签名的某种概率关系来进行攻击的方法，这种攻击方法目前对基于公钥密码体制的 方案来说是不大适用的，它主要是用来攻击分组密码和流密码的。 针对数字签名方案有不同类型的攻击，敌手攻击一个数字签名方案通常采用以下基本攻 击类型“： ( 1 ) 唯密钥攻击( k e y o n l ya t t a c k ) ：敌手仅知道签名者的公开密钥。而没有其它任何信息。 ( 2 ) 已知签名攻击( k n o w s i g n a t u r ea t t a c k ) ：敌手知道签名者的公钥并且看到了一些签名 者产生的消息签名对。 ( 3 ) 消息攻击：敌手在试图攻击一个签名方案之前，能够获得某些消息或选定的消息及其 签名。这其中又包括选择消息攻击和适应性选择消息攻击两类： 选择消息攻击( c h o s e n - m e s s a g ea t t a c k ) ：敌手可选择一个消息列表并要求合法签名人 签名这些消息 适应性选择消息攻击( a d a p t i v e l y - c h o s e n m e 豁a g ea t t a c k ) ：敌手可以适应性地选择消息 让签名人签名。敌手可以选择一些消息并得到相应的签名，然后进行密码分析，并根据他的 分析结果，选择下一个要签名的消息，然后继续上述过程。 如果一个攻击者能够以不可忽略的概率至少达到如下一项目的，那么我们说这个攻击者 成功的攻破了他所试图攻击的数字签名方案。攻破数字签名方案的攻击类型“时： ( 1 ) 完全攻击：攻击者计算出签名者的秘密陷门信息即签名密钥。 ( 2 ) 一般伪造：找到一个功能等效于签名者的签名算法的有效算法，伪造合法签名。 ( 3 ) 存在性伪造( e x i s t e n t i a lf o r g e r y ) ：敌手有能力伪造至少一个消息的签名，敌手对他获 得的消息及其签名没有任何控制作用。 ( 4 ) 选择性伪造( s e l e c t i v ef o r g e r y ) ：敌手能成功伪造他优先选择的一些消息的签名。 ( 5 ) 完全伪造( u n i v e r s a lf o r g e r y ) ：虽然不能找到签名人的私钥，但攻击者能够伪造所有消 息的签名。 虽然大多数数字签名方案的安全性并没有得到证明，但是多年来也并没有明显的验证表 明这些方案是不安全的，例如基于大数分解问题的r s a 方案。因此，把一些数字签名方案的 安全性转化为这些公认安全的数字签名方案的安全性，是一个实际有效的保证数字签名方案 安全性的方法。同时，利用计算复杂度理论，将数字签名方案的安全性转化为一些已知不可 解的数学难题，就是通常所说的可证明安全性的研究，也是近年来的研究热点之一。 2 对策 有两种特别的措施可以提高数字签名的安全性n 刀。一种是签名前首先增加消息的冗余度。 此时，只有满足某种断言的消息才予以签名，这使得选择明文攻击变得更复杂，而且，只有 当消息满足这个断言时签名才是有意义的，这样，在原方案中的扩展伪造看起来将不可能产 6 西北师范丈学硕士学位论文 第一章绪论 生有效的消息。第二个措施是签名前对消息使用单向h a s h 函数。此时，攻击者不可能为选择 明文攻击找到对他有用的消息，而且消息的h a s h 值就是实际签名的值。使用h a s h 函数还有 一个额外的优点，就是如果h a s h 函数的执行速度快，它将使得整个方案更有效。因此，选择 好的冗余函数或者h a s h 函数，能够对方案的安全性提供更好的保障。 还有一种保障数字签名算法安全性的方法是应用可证明安全性的思想，通过引进随机预 言机模型，形式化数字签名算法中的单向函数。 数字签名的安全性主要有以下几种证明方法： ( 1 ) 可证明安全性 标准模型下：利用计算复杂性理论，将数字签名的安全性转化为一些已知的难题，如 大整数分解问题，离散对数问题或者一般n p 完全问题。 随机预言机模型下：数字签名经常使用h a s h 函数，为了给签名方案提供安全性证明， 一些学者建议将h a s h 函数看成是一个随机函数，并给出了相应的模型，即随机预言机模型“”。 假设h a s h 函数是安全的情况下，基于此模型的证明能够保证一个签名方案的总体设计的安全 性。 ( 2 ) 转化证明 把需要分析和确定其安全性的数字签名方案的安全性转化为一些公认安全的数字签名方 案的安全性，也是一个有效可行的方法。 1 2 5 数字签名的类型 不同的数据信息处理环境常常需要不同的数字签名方案。到目前为止，所有数字签名方 案都可以按照以下方式进行分类。 1 根据数字签名方案所基于的数学难题，数字签名方案可以分为基于离散对数问题的签 名方案、基于大数分解问题的签名方案和基于椭圆曲线问题的签名方案。 2 根据数字签名方案是否具备由合法的签名接收者能够从所生成的签名恢复出被签名消 息的特性，可将数字签名方案分为不具有消息恢复特性的数字签名和具有消息恢复特性的数 字签名。 3 根据产生数字签名时签名方案所涉及到的签名生成者或系统用户的个数，可将数字签 名方案分为面向单用户的数字签名方案和面向群体的数字签名方案。 4 根据签名产生的方法分类。 由于各种不同的应用需要，人们基于不同的目的研究了具有特殊用途的数字签名，大致 可以分为：代理签名、盲签名、多方参与的数字签名、验证受限的数字签名、群签名、环签 名、基于身份的数字签名等。 7 西北师范大学硕士学位论文第一章绪论 1 3 本文工作 1 3 1 论文安捧 第二章 介绍基本的数字签名体制 第三章 介绍可截取签名理论 探讨可截取签名的应用 第四章 介绍基于身份数字签名和群签名 提出一个基于身份的可截取群签名方案 第五章 介绍门限签名体制 提出一个基于身份的可截取门限签名方案 第六章 介绍自认证理论 提出一个基于自认证的可截取签名方案 1 3 2 主要研究成果 1 通过对可截取签名和传统的数字签名的比较，深入分析了可截取签名在电子商务、电 子政务等应用中的优势。 2 在现有可截取签名体制的研究基础上，结合基于身份的密码系统和群签名体制，构造 了一个双线性对上基于身份的可截取群签名方案，可有效地实现对签名的截取而无须和签名 者多次交互，并给出了安全性和效率分析。 3 基于双线性对理论，提出了一个基于身份的可截取门限签名方案，可有效地实现对签 名的门限生成、签名截取而无须和签名者多次交互。方案保证了签名效率和签名的强壮性， 在随机预言模型下，证明了其在适应性选择消息攻击和身份攻击下都能抵抗存在伪造。 4 将自认证公钥体系与可截取签名体制相结合，基于离散对数难题，提出了一个基于自 认证的可截取签名方案。方案具有可截取签名的特点和优势，同时又具有自认证公钥体系计 算代价小、通信传输量少等优点。 8 第二章基本的数字签名体制 2 1 基本的数字签名方案 最基本的数字签名方案的安全性都是基于数学难题的难解性n 1 。一般的数字签名方案都 是基于求解离散对数困难性的签名方案或基于大整数分解困难性的签名方案。e i g a m a l 型数 字签名方案，d s a 签名方案和s c l m o r r 签名方案是基于离散对数问题的数字签名方案。而r s a 数字签名方案和f i a t s h a m k 签名方案则是基于大数分解问题的数字签名方案。离散对数问题 和大数分解问题的描述如下： 离散对数问题( d i s c r e t el o g a r i t h m ，简称d l ) ； 给定大素数p ，p 一1 包含另一个大素因子口，可构造一个乘法群z ：。它是一个p - 1 阶循 环群，其生成元为整数g ，1 g p 一1 。已知x ，容易求得_ ) ，一g 。m o d p ，若已知y ，g ，p 求x 是 一件十分困难的事情，这就是离散对数求解困难性闯题。 在密码学中，一般用到三种群上的离散对数问题，它们是素数域的乘法群、特征为2 的 有限域的乘法群和有限域上的椭圆曲线群。迄今为止，最快的求解素数域的乘法群上的离散 对数问题的算法需要o ( c l o g p l o g l o g p ) 次整数乘法，其中c 是一个常数。 大整数分解问题( f a c t o r i z a t i o np r o b l e m ，简称f a c ) ； 已知两个大素数p 和q ，求na p 孽十分容易，但由n 求解p 和口是十分困难的事情。这 就是大数分解困难性问题。 根据算术基本定理，只要能够快速求出p 和口，那么就可以递归的快速求出n 的素数分解 式。和求解离散对数问题一样，人们也尚未找到满意的快速整数分解算法，目前世界上最快 的整数分解算法是j p o l l a r d “”首创的数域筛法( n f s ) 。 以下介绍基本的数字签名方案。 2 1 1 基于离散对数问题的数字签名方案 e i g a m a l 、s c h n o r r 、d s a 等签名体制都可归结为离散对数签名体制的特例。 1 e i g a m a l 签名体制1 e 1 g a m a l 签名体制由t e i g a m a l 在1 9 8 5 年给出。其修正形式已被美国n i s t 作为数字签 名标准d s s 。e i g a m a l 体制专门设计作为签名用，方案的安全性基于求离散对数的困难性。 它是一种概率的双钥体制，即对同一明文消息，由于随机参数选择的不同而会得到不同的签 名。 9 西北师范大学硬上学位论文第二章基车的数字签名体制 设p 是一个使得在z ，上的离散对数问题是难处理的素数，；漫a e z ；是一个本原元。设消 息集p z ：，签名集a - z ：x z ，。，定义密钥空间： k - ( p ，口，a ，声) ：卢- a ( m o d p ) 值p ，a ，芦是公钥，a 是私钥。 对k 一( p ，口，4 ，芦) 和一个秘密随机数七z ：。，定义赡x 似k ) 一( y ，6 ) ，其中y 一口m o d p ， 6a o - a y 弦- 1 m o d 【p 一1 ) 。对工，y e z ；和6 t = z 。- i ，定义： v e r x ( 膏，( y ，d ) - t r u e 卢7 y 4 - 口。( m o d p ) 2 s c h n o r r 签名体制n 帕 c s c h n o n 于1 9 8 9 年提出一种签名体制一一s c h n o f r 签名体制，它的安全性同样基于求离 散对数的困难性，也是非确定性的双钥体制。s c l m o r r 签名是受到f i a t - s h a m i r 签名思想的启 发从s c l m o n 身份识别协议转换而来的。最终生成的签名长度与数字签名标准算法d s s 生成 的签名长度相同。 设p 是使得在z ：上的离散对数问题难处理的一个素数，口是能被p 一1 整除的素数。设 a e z p 是模p 同余1 的q 次根，消息集p 一 蚺，签名集a z 。x z 。，定义密钥空间： k 一 ( p ，q ，口，a ，芦) ：芦- a 4 ( m o d p ) 其中1 s a s q 一1 ，值p ，q ，a ，卢是公钥，a 是私钥。最后，设h ： 0 册一z 。是安全的h a s h 函数。 对于k 一( p ，q ，a ，a ，卢) 和一个秘密随机数k , 1 ks q 一1 ，定义堙k o ，k ) 一( y ，6 ) ，其中 yt h ( xn 口) ，6 一t + a r m o d q 。 对工 0 ，1 和y ，6 z 。，定义； v e k 0 ，( y ，6 ) ) = t r u e h ( x0 口。芦1 ) ；r s c h n o r r 签名和e i g a m a l 签名相比较，两者的不同点如下： ( 1 ) 在e i g a m a l 签名体制中，a 为z 。的本原元，而在s c h n o r r 签名体制中，口为z ：的子 集z ：的本原元，不是z ：的本原元。显然e i g m m 签名体制的安全性高于s c l m o r r 签名体制。 ( 2 ) s c h n o r r 签名长度较短，由i q i 及l | j | ( 艉) i 决定。 ( 3 ) 在s c h n o r r 签名中，所需计算量少，速度快。 2 1 2 基于大数分解问题的数字签名方案 r s a 数字签名和f i a t s h m i r 数字签名都是基于因子分解问题的数字签名体制。 1 r s a 签名体制“町 1 9 7 8 年，m i t 的三位青年数学家r l r i v e s t 、a s h a m i r 和l a d l e m a n 发现了一种用数论 结果构造公钥体制的方法。这就是后来被广泛称为r s a 体制的公钥密码体制。它是第一个较 完善的公钥密码体制，既可用于加密，又可用于数字签名，简单易懂且容易实现，是目前仍 西北师范大学硕士学位论文第二章基本的数字签名体制 然安全并且最被广泛应用的一种体制。r s a 体制已经经受了多年深入的密码分析，尽管密码 分析既没有证明也没能否定r s a 体制的安全性，但却对该体制提供了一个可信度。目前，最 有效的大数分解法是数域筛法。到2 0 0 2 年1 2 月为止，因子分解的记录是5 1 2 比特，p 和窜都 是2 5 6 比特，用2 9 2 台计算机花费五个多月的时间完成了这个工作。据此推算，破解1 0 2 4 比 特的密钥大约需要3 百万到3 千万年。因此，当前使用的r s a 密钥通常都采用1 0 2 4 比特。 设n p q ，其中p , o q 是素数。设消息集p z 。，签名集a z ，定义密钥空间： k - o ，p ，q ，a ，6 ) ：万一p q ，p 和口为素数，a b l ( m o d 妒o ) ) 值 和b 为公钥，值p ，鼋，a 为私钥。对k o ，p ，q ，a ，6 ) ，定义： s g e - 耳4m o d n 以及 v e r 茁0 ，y ) 一t r u e 营耳。y b ( m o d n ) 其中工，) ，z 。 2 f i a t - s h a m i r 签名体制删 f i a t 和s h a m k 在1 9 8 6 年给出了一个从安全的三轮f i a ts h a m k 身份识别协议设计数字签 名方案的一般方法，利用该方法得到的数字签名方案，即f i a t - s h a m i r 签名方案是可抗选择消 息攻击的。1 9 9 6 年p o i n t c h e v a l 和s t e m 证明了在随机预言模型下f i a t s h a m i r 签名是可证明安 全的。f i a t s h a m i r 数字签名较之与r s a 的主要好处在于速度，f i a t s h a m i r 数字签名只需要 r s a 的1 - - - 4 的模乘法。 选择n 为两个大素数之积。产生公开密钥v 。，v ：，和私人密钥毛，s ：，满足