（应用数学专业论文）前向安全门限签名方案的研究.pdf

具有前向安全性质的门限签名方案硕士学位论文 摘要 本文重点研究了具有前向安全性质的门限签名方案。门限签名是将密钥分发给多个成 员，每个成员持有密钥的一个份额，只有多于特定数量的份额才能重构密钥。这样即使少 数成员的密钥份额泄漏，也不会影响到整个系统密钥的安全，从而降低了密钥泄漏的可能 性。一般的数字签名，一旦密钥泄漏，则攻击者不但可以伪造攻破时间段以后的签名，也 可以伪造此时间段之前的任何签名，从而有很大的危害性。为了使密钥泄漏所造成的危害 最小化，前向安全签名采用把整个签名阶段分成小阶段，而各个阶段的密钥采用单向函数。 本文基于e l g a m a l 签名体制提出了一个改进的前向安全门限签名方案，通过在签名过程中 ， 添加w 。= ( s k ：叭州g 片m o dp ) r o o dq 这一项，从而使当前密钥隐藏在签名中，在验证方程 ， u ，一 w = ( g 6 ”y 7 h f m ) w 哩m o d p ) m o d q 中引入有效的时间段参数，从而该方案具备了真 正的前向安全性。另外，本文以s c h n o l l r 签名方案为基础，通过在签名过程中添加 r 。= x 。g kr o o dp 这一项，从而使当前密钥隐藏在签名中，在验证方程 r = 9 5 y 。r p 。m o dp 中，时间段参数，是一个有效的参数，构造了一个有效的前向安全 门限签名新方案。通过两个新方案的实施，即使收买多于门限数目个成员的攻击者得到当 前密钥，也不能伪造当前时间段之前的签名，该体制具备了真正的前向安全性，因而降低 了密钥泄漏所造成的危害。本文的主要内容如下： 第一章，概括地介绍了数字签名的研究目的及意义、国内外研究概况、密码学相关的 知识及其数学背景知识。 第二章，概述了门限签名方案与前向安全签名方案的研究现状，并分析了现有门限签 名方案。在此基础上，对门限签名方案的发展给出了自己的展望。其次，描述了前向安全 签名方案的一般构建安全模型，最后，给出了前向安全数字签名方案的优点及其应用前景。 第三章，在前人的研究基础上，提出了一种改进的前向安全门限签名方案。该方案不 仅密钥是前向安全的，而且签名也是前向安全的，即使攻击者收买大于或等于门限数目个 成员后，攻破s k ，但由踊，仍然无法计算出踊，从而密钥具有前向安全性，使密钥 泄漏所造成的危害最小化。 第四章，基于s c h n o r r 体制构造了一种前向安全门限签名新方案。该方案在签名过程 中将当前私钥隐藏在签名中，在验证过程中有效地使用了时间段参数，从而保证签名密钥 与签名同时都是前向安全的，为电子商务的应用带来了更为广阔的前景。 第五章，对本文的工作作了总结与展望。门限签名方案与前向安全签名方案都是针对 为了减少密钥泄漏所造成的危害而设计的特殊性质的签名方案，具有很实用的利用价值。 关键j 闻：门限签名，前向安全，离散对数，e l g a m a l 体制，s c h n o r r 体制 a b s t r a c t t h ef o r w a r ds e c u r et h r e s h o l dd i g i t a ls i g n a t u r ei sm a i n l ya n a l y z e da n ds t u d i e di nt h i sp a p e r t h em a i ni d e ao ft h r e s h o l dd i g i t a ls i g n a t u r ei st od i v i d et h es e c r e tk e yi n t os e v e r a lp a r t i c i p a n t s e a c hp a r t i c i p a n th a sas h a r eo ft h es e c r e t , o n l yt h es p e c i f i cn u m b e r so fp a r t i c i p a n t sc a n r e c o n s t r u c tt h es e c r e t s oi tc a n n o tb r e a c ht h es y s t e ms e c u r i t ye v e ns o m ep a r t i c i p a n t se x p o s et h e i r s h a r e s t h eu s eo fs e c r e ts h a r i n ga n dt h r e s h o l dd i g i t a ls i g n a t u r er e d u c et h ep r o b a b i l i t yo ft h e e x p o s u r eo fs e c r e tk e y u n l i k et h eg e n e r a id i g i t a ls c h e m e ，t h ef o r w a r ds e c u r ed i g i t a ls i g n a t u r e s c h e m ec a ne n s u r et h ea d v e r s a r yc o u l d n tf o r g ea n ys i g n a t u r ep e r t a i n i n gt ot h ep a s t , e v e ni fh e h a do b t a i n e dt h ep r e s e n tk e y i nt h ek e ye v o l u t i o np a r a d i g m ：t h eu s e rp r o d u c e ss i g n a t u r e su s i n g d i f f e r e n ts e c r e tk e y sd u r i n gd i f f e r e n tt i m ep e r i o d sw h i l et h ep u b l i ck e yr e m a i n sf i x e d a n i m p r o v e df o r w a r d s e c u r et h r e s h o l dd i g i t a ls i g n a t u r ew a sf o r m e db a s e d o nt h ee l g a m a ls i g n a t u r e s y s t e mi n t h i st h e s i s t h r o u g hu s i n gw = ( s k 7 ”g 尺m o dp ) m o dq i ne a c hp e r i o dt i m e s i g n i n gp r o c e s st oh i d et h es e c r e tk e yi nt h es i g n i n gp r o c e s sw h i l et h et i m ep a r a m e t e rj i sa n a v a i l a b l e p 越吼e t e r i n 廿l e v e r i f y i n gp r o c e s sw ：( g ( m y 一( m w 2 卅m o dp ) m o dg ， t h e r e f o r e ，t h es c h e m eh a st h eg e n u i n ef o r w a r d s e c u r ep r o p e r t y m o r e v e r , w ep u tf o r w a r dan e w f o r w a r d s e c u r et h r e s h o l dd i g i t a ls i g n a t u r eb a s e do nt h es c h n o r rs i g n a t u r es y s t e m ，w eh i d et h e s e c r e tk e yi nt h es i g n i n gp r o c e s sb yu s i n g ，。= x ，g km o dpi ne a c hp e d o dt i m es i g n i n g p r o c e s sw h i l e t h et i m e p a r a m e t e rj i sa na v a i l a b l ep a r a m e t e ri nt h ev e r i f y i n gp r o c e s s r = g s y 。，2 1 叽m o dp b yi m p l e m e n t i n gt h et w os i g n a t u r ei n t op r a c t i c e ，i ti s i n f e a s i b l ef o ra n a t t a c k e rt of o r g ea n yv a l i ds i g n a t u r ep e r t a i n i n gt ot h ep a s te v e ni fh eh a sc o r r u p t e du pt om o r e t h a no re q u a lt ot h et h r e s h o l dm e m b e r sa n dh a so b t a i n e dt h ec u r r e n tk e y t h i ss c h e m eh a st h e g e n u i n ef o r w a r d - s e c u r ep r o p e r t yw h i c hr e d u c et h ep o t e n t i a ld a m a g ei nc a s es e c r e t sa r ee x p o s e d t ot h em i n i m u md e g r e e t h et h e s i si sc o m p o s e do ft h ef o l l o w i n gc h a p t e r s ： c h a p t e r lt h eo v e r v i e wo f t h ea i ma n ds i g n i f i c a n c eo fd i g i t a ls i g n a t u r e ，t h eg e n e r a ls i t u a t i o n o fd o m e s t i ca n df o r e i g nr e s e a r c ha n dk n o w l e d g er e l a t e dt oc r y p t o g r a p ha sw e l la ss o m em a t h p r e p a r a t o r yk n o w l e d g e c h a p t e r 2g e n e r a l l yi n t r o d u c e st h es i t u a t i o n a n dt h ea c t u a l i t yo ft h et h r e s h o l d d i g i t a l s i g n a t u r e b e s i d e st h i s ，w ea n a l y s i ss o m ef a m o u st h r e s h o l dd i g i t a ls i g n a t u r es c h e m e b a s e do n t h i s ，w ep u tf o r w a r do u re x p e c t a t i o no ft h et h r e s h o l dd i g i t a ls i g n a t u r es c h e m e t h eo v e r v i e wo f f o r w a r ds e e u r ed i g i t a ls i g n a t u r es c h e m ei sp r e s e n t e da n dg e n e r i cc o n s t r u c t i o n sa n ds e c u r i t y m o d e l so ff o r w a r ds e c u r ed i g i t a ls i g n a t u r ea r ed e s c r i b e d ，a tt h es a m et i m e ，t h em e r i ta n da p p l i e d i i 具有前向安全性质的门限签名方案硕士学位论文 f o r e g r o u n do ff o r w a r ds e c u r ed i g i t a ls i g n a t u r es c h e m ea r ea n a l y z e d c h a p t e r 3a ni m p r o v e df o r w a r d - s e c u r ed i g i t a ls i g n a t u r ei sp r e s e n t e db a s e do nt h ep r e d e c e s s o r t h i ss c h e m ei sn o to n l yt h es e c r e tk e yh a st h ef o r w a r d s e c u r ep r o p e r t yb u ta l s ot h es i g n a t u r e a s ar e s u l t , t h ea t t a c k e rc a l l to b t a i n x 卜l f r o mx ，t h a ti st os a yt h es e c r e tk e yh a sf o r w a r d - s e c u r e p r o p e r t yw h i c hr e d u c et h ep o t e n t i a ld a m a g ei nc a s es e c r e t sa r ee x p o s e d t ot h em i n i m u md e g r e e c h a p t e r4b a s e do nt h es c h n o r rc r y p t o s y s t e m ，an e wf o r w a r d s e c u r et h r e s h o l ds i g n a t u r e s c h e m ew a sp r o p o s e dw h i c he n s u r et h a tt h es i g n a t u r e ss e c r e tk e ya n dt h es i g n a t u r ea r e s i m u l t a n e o u s l ys e c u r et h r o u g hh i d i n gt h ec u r r e n ts e c r e tk e yi nt h es i g n a t u r ep r o c e s sw h i l eu s i n g t h et i m e - p a r a m e t e re f f e c t i v e l yi nt h ev e r i f i c a t i o np r o c e s s t h i ss c h e m eh a st h en e wp r o p e r t yt h a t i ti si n f e a s i b l ef o ra na t t a c k e rt of o r g ea n ys i g n a t u r ev a l i dp e r t a i n i n gt ot h ep a s te v e ni fh eh a s t a k e nc o n t r 0 1o fm o r et h a no re q u a lt h r e s h o l dm e m b e r sa n do b t a i n e dt h ec u r r e n tk e y c h a p t e r5w es u m m a r i z ea n de x p e c tt h ep a p e r b o t ht h r e s h o l ds i g n a t u r ea n df o r w a r d s e c u r e s i g n a t u r ea r es i g n a t u r e sw h i c ha r ed e s i g n e dt or e d u c et h ep o t e n t i a ld a m a g ei nc a s es e c r e t sa r e e x p o s e dt ot h em i n i m u m t h e r e f o r e ，t h e yh a v ep r a c t i c a l i t yu t i l i z ev a l u e k e yw o r d s ：t h r e s h o l dd i g i t a ls i g n a t u r e ，f o r w a r d - s e c u r es i g n a t u r e ，d i s c r e t el o g a r i t h m ， e l g a m a lc r y p t o s y s t e m ，s c h n o r rc r y p t o s y s t e m i 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发 表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 作者签名：当鹭终 日 期：玉窆! ：复盆 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸 质版：有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书 馆被查阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论 文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者签名：云颦，玺 日 期：墨璺：笠：丘 具有前向安全性质的门限签名方案硕士学位论文 第一章绪论 1 1 数字签名的研究背景及意义 数字签名是提供认证性、完整性和不可否认性的重要技术，因而是信息安全的核心技 术之一。随着社会的信息化发展，越来越多的文件、书信需要以数据串的形式通过网络传 递，这些数据串的来源和完整性都需要认证，而且这些认证常常需要在以后的一段时期内 多次重复，这就需要手写签名的电子替代物一数字签名( d i g i t a ls i g n a t u r e ) 。一般来说，整 个网络世界的真实性要比现实世界的真实性更难于保证，因此对数字签名的需求就显得更 加迫切。 数字签名的特性可抵御网络威胁，包括认证性、可辨别性及真实性，数据完整性保护， 抵御数据的篡改和重排，以防其抵赖。一般还使用加密技术来保护信息机密性，加入流水 号等技术来防止重放攻击。特别是认证性、完整性和不可否认性的特点使其在电子商务和 电子政务系统中起着重要作用。 1 2 数字签名的研究现状 1 9 7 6 年d i f f i e 和h e l l m a n 在“密码新方向”中利用公钥密码学的思想提出了数字签名 的概念【l l ，但是并没有提出具体的签名方案。第一个数字签名方案是在两年后，1 9 7 8 年有 r i v e s t 、s h a m i r 和a d l e m a n 给出的基于大整数分解困难性的著名的r s a 签名方案【2 】，他们 同时给出了著名的r s a 公钥密码方案，他们也因此共同获得2 0 0 2 年的图灵奖。此后的二 十几年里，新的数字签名如雨后春笋般不断涌现，其中比较著名的有：e l g a r n a l 数字签名 方案1 3 ，s c h n o r r 数字签名方案【4 】，r a b i n 数字签名方案1 5 j ，d s a 数字签名方案【6 j ，o k a m o t o 数字签名方案【7 】，f i a t s h a m i r 数字签名方案1 8 1 等。 随着对数字签名研究的不断深入，同时也由于电子商务、电子政务的快速发展，简单 模拟手写签名的一般数字签名已不能完全满足需要，因此，多年来许多具有特殊性质和特 殊功能的数字签名不断被提出，1 9 8 2 年c h a u m 引入了盲签名( b l i n ds i g n a t u r e ) 1 9 1 ；1 9 8 4 年s h a m i r 提出了基于身份的密码系统( i d b a s e dc r y p t o s y s t e m ) 的概念，并同时提出了基 于身份的签名( i d b a s e ds i g n a t u r e ) ；1 9 9 1 年d e s m e d t 和f r a n k e l 引入了门限签名( t h r e s h o l d s i g n a t u r e ) ；c h a u m 和h e y s t 引入了群签名( g r o u ps i g n a t u r e ) 1 1 2 1 ：m a m b l 、u s d a 和o k a m o t o 引入了代理签名( p r o x ys i g n a t u r e ) f j 引；1 9 9 7 年z h e n g 引入了签密( s i g n c y p t i o n ) f j ，这 些签名体制还可以组织成更多的签名体制。 具有前向安全性质的门限签名方案硕士学位论文 1 3 数字签名的基本概念 1 3 1 数字签名体制的定义与攻击 一个数字签名有以下几个部分组成： 1 ) 一个明文消息空间m ：某字母表中串的集合； 2 ) 一个签名空间s ：可能的签名集合； 3 ) 一个签名密钥空间k ：用于生成签名的可能密钥集合，和一个认证密钥空间豚+ ： 用于验证签名的可能密钥集合； 4 ) 一个有效的密钥生成算法g e n ：nhk k ，k 和k 分别为私钥和公钥空间； 5 ) 一个有效的签名算法s i g n ：m k hs ； 6 ) - - 个有效的签名验证算法v e r i f y ：m s k h t r u e ，f a l s e 。 一个好的数字签名方案至少需要满足不可否认性、不可伪造性和可仲裁性。其中，如 何确保签名的不可伪造性是数字签名设计的一个关键问题。这就意味着，在不掌握签名私 钥的条件下，要计算出一个有效的签名是不可行的。目前已经存在多种伪造攻击，可以根 据伪造方式的不同将其分为三类1 3 3 j ： 完全的伪造( t o t a lb r e a k ) ：攻击者能计算出签名者的签名私钥，或能够利用除s i g n 之 外的其他算法技术对任意消息进行有效签名。 选择性的伪造( s e l e c t i v ef o r g e r y ) ：在给定消息或某一类特殊消息的条件下，攻击者能 够计算出有效的签名。 存在性的伪造( e x i s t e n t i a lf o r g e r y ) ：一个攻击者能计算出对于至少一条任意消息的有 效签名。该攻击者也许对于被签名的消息无法进行控制或控制力较弱。 对于一个签名方案，若攻击者能成功发动存在性伪造攻击( 甚至是适应性选择消息攻 击) 在计算上不可行，则称该方案为安全的签名方案【3 0 1 。 1 3 2 数字签名的分类 基于数学难题 可以将数字签名方案按照公开密钥密码算法建立的数学基础进行分类： 1 ) 建立在大整数素因子分解基础上的密码算法。 r i v e s t 、s h a m i r 和a d l e m a n 于1 9 7 8 年提出了基于r s a 公钥算法的数字签名方案【l9 1 ： 2 ) 建立在有限域的离散对数的问题上的密码算法。 e l g a m l 于1 9 8 5 年提出的一种基于离散对数的公钥密码算法和数字签名方案刚； 3 ) 建立在椭圆曲线e c c 上的密码算法。 2 具有前向安全性质的门限签名方案 硕士学位论文 s c o t tv a n s t o n e 于1 9 9 2 年首先提出了椭圆曲线数字签名算法e c d s a l 2 l j 。 4 ) 基于二次剩余问题上的密码算法。 n y a n g 和s o n g 所设计的快速数字签名方案等。 基于特殊用途的分类 为了满足特定的实际需要，一般签名已经不能再提供相应的特殊性质，必须借助于特 殊的数字签名，为了不同的特殊需要而提出了下面特殊的数字签名。 1 1 盲签名：一般的数字签名，签名者可以查看所签署消息的内容，这和日常生活的情 形相符合：我们通常需要在知道文件内容之后才会签署。但当签名者要签署份不知道内 容的文件时，就需要使用盲签名。由于盲签名具有匿名的性质，因而在电子货币和电子投 票系统中有较大的应用价值，特别是目前的数字现金，大部分都是采用盲签名原理来实现。 2 1 门限签名：门限签名通过共享密钥方法实现，它将密钥分为n 份，只有当超过t 份 的子密钥组合在一起时才能重构密钥。门限签名在密钥托管技术中得到了很好的应用，某 人的私钥由政府的n 个部门托管，只有当其中超过t 个部门决定对其实行监听时，才可重 构密钥。 3 ) 代理签名：允许密钥持有者授权给第三方，获得授权的第三方能够代表签名持有者 进行数字签名。 4 ) 群签名：允许一个群体中的成员以整个群的名义进行数字签名，并且验证者能确认 签名者的身份。群签名中最重要的是群密钥的分配。 5 ) 不可否认签名：兼顾了签名者和接收者的利益，既保证签名不能被接收者滥用，又 能够以后使签名让其他人相信。最本质的是在无签名者的配合下，不可能验证签名的有效 性。利用这个特殊的性质，可以在一定程度上防止复制或散布他所签名的文件的可能性， 从而使产权所有者可以控制产品的散发，这在电子出版领域的知识保护中起着很大的作用。 6 ) 前向安全签名：一般的数字签名，一旦密钥泄漏，则攻击者不但可以伪造攻破时间 段以后的签名，也可以伪造此时间段之前的任何签名，从而有很大的危害性。为了使得密 钥泄漏所造成的危害最小化，我们采用把这个签名阶段分成小阶段，而各个阶段的密钥采 用单向函数，从而即使当前阶段密钥泄漏，攻击者也不能伪造此阶段之前的签名，从而降 低了密钥泄漏所造成的危害。 1 4 密码学相关知识 1 4 1 数学难解问题 许多密码学体制依赖于解决某个数学难解问题的困难性。所谓困难性是指在合理有限 的资源范围内找不到一个可行的算法来解决这个问题，即计算上的不可行性。在现实情况 下是指用运算速度最快的计算机和目前最优的算法在数年、数十年甚至上百年内不能计算 出这个问题的结果。下面给出在公钥密码体制中经常用到的一些困难性问题。 3 具有前向安全性质的门限签名方案 硕士学位论文 1 ) 大整数因子分解难题( i n t e g e rf a c t o r i z a t i o n ) 如果已知两个数p 和q ，求其乘积n = p q 会非常容易，但如果已知的是乘积n ，那么分 解这个乘积以求出两个因子就不那么简单了，尤其当这个乘积是一个大素数( 如超过1 0 2 4 位) 的时候，而这就是现代密码学一公钥密码体制提出的一个数理基础。 在数论中，大数分解问题是一个古老的的问题。分解一个大数理论上很简单，但是实 际过程很费。尽管如此，在这方面现在还是有一些进展。目前最好的大数分解算法是数域 筛选法( n f s ) ，对大于1 1 0 位左右的十进制数来说，一般的数域筛选法是目前已知最快的 大数分解法。还有一些算法如连分数算法。椭圆曲线算法( e c m ) 对较大数是没有用的， 而二次筛选法( q s ) 对于低于1 1 0 的十进制来说，是目前已知的最快算法。 大数分解是一个迅速发展的领域，但大数分解技术的发展未来仍不可知，因为没有人 能预见数学理论的进展。1 0 2 4 比特的数在目前看来是安全的。现在广泛应用的基于大数分 解问题提出的r s a 密码体制，仍被认为是安全性最好的体制之一。 密码中最常用也最重要的r s a 加密体制及其相关的r s a 签名算法都是建立在此大整 数难解问题之上。 2 ) 离散对数问题( d i s c r e t el o g a r i t h m ) 如果已知a ，x ，n 计算下面表达式很容易：b = a m o d 刀。然而反过来，求模指数的逆 问题也即离散对数问题：已知b ，a ，r ，求x ，使其满足关系式：b = 矿m o d n 。在计算上 是不可行的。 离散对数难题也是密码学中经常用的一个难题，很多著名的密码体制都是建立在其上 的，如e l g a r n a l t 2 9 1 、d s a t 6 1 等算法的安全性都是建立之上的。 1 ) 椭圆曲线离散对数问题( e l l i p t i cc u r v e ) 如我们最常用的e c d s a 签名体制。 2 ) 中国剩余定理 设碍，m 2 ，m 。，是n 个两两互素的整数， 令m = m 。，m i = 兀，m = 肌，m ( f = 1 ，2 ，z ) ，则一次同余式组 j = l f 藿 b l ( m o d ) b e ( r o o d m 2 ) b , ( m o d m 。) 有唯一解 x = m 1 6 l + m ： 乞6 2 + + m ：m 。b nr o o d m 其中 心m i 暑l ( m o d m ，) ( f = 1 ，2 ，玎) 4 具有前向安全性质的门限签名方案硕士学位论文 当然还有其它一些数字签名算法，如基于有限自动机原理的有限自动机数字签名算法： 基于背包系统的s h a m i r 背包数字签名算法：基于纠错码理论的x i n m e i 方案的数字签名算 法等。 1 4 2 密码杂凑函数 杂凑函数在实际中有着广泛的应用，在密码学和数据安全技术中，它是实现有效、安 全可靠的数字签名和认证的重要工具，是安全认证协议中的重要模块。杂凑函数主要有两 类：带密钥的和不带密钥的杂凑函数。不带密钥的杂凑函数任何人都可以计算，它仅仅是 输入串的函数；带密钥的杂凑函数是输入串和密钥的函数，只有持有密钥的人才能计算出 杂凑值。 密码学上的杂凑函数就是把任意长度的消息( m e s s a g e ) 压缩成固定长度( 通常比较短) 的消息摘要( m e s s a g ed i g e s t ) 的一种函数。 定义杂凑函数：就是将一个有限长度的二进制字符串映射为一固定长度k 的二进制字 符串。常用：h ： o ，1 ) 专 o ，1 j 来表示( 或用h ) 。 密码学上，人们要求一个杂凑函数必须容易计算，而且至少还要满足下面几个性质中 的一些： 1 ) 混合变换：对于任意的输x x ，输出的杂凑值厅 ) 应当和区间 o ，2 州 中均匀的二 进制串在计算上是不可分的。 2 ) 抗碰撞攻击：找两个输入x 和y ，且x y ，使得厅( x ) = h ( y ) ，在计算上应当是不 可行的。为使这个假设成立，要求h 的输出空间应该足够大。l h i 最小为1 2 8 ，而典型的值 为1 6 0 。 3 ) 抗原像攻击：已知一个杂凑值h ，找一个输入串x ，使得h = 办( x ) 在计算上是不可 行的。这个假设同样也要求h 的输出空间足够大。 4 ) 实用有效性：给定一个输入串x ，办 ) 的计算可以在关于x 的长度规模的低阶多项 式时间内完成。 杂凑函数的安全性取决于其抗各种攻击的能力，对手的目标是找到两个不同的字符串 映射为同一个杂凑值，从而可以进行伪冒攻击。对杂凑函数一般有三种基本的攻击方法： 穷举攻击法、生日攻击法、中间相遇攻击法。另外还有一些适用于特定杂凑函数的攻击法。 关于杂凑函数的长度，n i s t ( 美国国家标准技术研究所) 在其安全杂凑标准中建议用1 6 0 位的杂凑值。这将使得生日攻击更难进行，因为需要做2 8 0 次的随机杂凑运算。 杂凑函数广泛应用于密码学中。这里列出杂凑函数的几个重要用途。 在数字签名中：杂凑函数一般用来产生“消息摘要”或“消息指纹”。这种用法是为将 要签署的消息增加一个可以验证的冗余，以便这个杂凑消息包含可以识别的消息。 5 具有前向安全性质的门限签名方案 硕士学位论文 在具有使用安全性的公钥密码系统中，杂凑函数被广泛地用于实现密文正确性验证机 制。对于获得可证明安全的抗主动攻击的加密体制来说，这个机制是必不可少的。 在需要随机数的密码学应用中，杂凑函数被广泛的用作实用的伪随机函数。这些应用 包括：密钥协商、认证协议、电子商务协议、零知识证明协议。 1 4 3 随机预言模型 随机预言模型( t h er a n d o mo r a c l em o d e l ) 是在文献【2 2 】中首先提出的。该模型可视为一 座介于密码学理论与实践之间的桥梁。该模型的思想是简单的：首先，假设所有的参与方( 善 意的或恶意的) 都可以对一个公开的函数h 进行访问；然后，在h 为一个真正的随机函数( 即 将散列函数h 看作是一个预言自动机，每当向其中提出一个新的询问，它就会以一个随机 值作为回答。当然，若两次询问是相同的，则所得的回答也是相同的) 的假设下证明给定 协议的正确性：最后，在实际应用中可利用某个特定的函数替换h ，且该函数可利用标准 的密码散列函数( 如s h a 一1 或r i p w m a 1 6 0 ) 构造而得。随机预言模型具有以下优点： 1 ) 随机预言模型带来的是效率，它比起那些用于特殊协议设计的方法来要好得多。 2 ) 与完全特殊的设计相比，基于随机预言模型进行证明的优点在于：若一个方案在随 机语言模型下是可证安全的，则可以认为该方案满足了一个强的、形式化的安全性概念， 甚至假设这个方案是基于一个强的基本要素。这比基于方案的安全性进行任何形式化分析 要好得多。 3 ) 基于随机预言模型的安全性证明至少为研究者排除了一个攻击，即通用攻击( g e n e r i c a t t a c k ) 。 另一个方面，在安全性证明中，不能仅仅将一个基于随机预言模型的证明视为一个更 强的难解假设。这种证明方法至多是一个启发式的方法，该方法能提供一个强有力的证据， 以证明一个方案是安全的。然而，对一个方案来说，即使其在随机预言模型下是安全的， 也有可能被攻破，且并不需要违背任何特殊难解假设，也无需展示其所使用散列函数的任 何特定弱点。 1 5 本文内容安排 第一章，概括地介绍了数字签名的研究目的及意义、国内外研究概况、密码学相关的 知识及其数学背景知识。 第二章，详细介绍了门限签名方案的研究现状及其研究背景，并对现有的著名门限签 名方案进行了分析。在此基础上，对以后门限签名方案的发展给出了自己的展望。其次，总 结了前向安全数字签名的研究现状和进展，并描述了前向安全数字签名方案的一般构建和 安全模型，同时分析了前向安全数字签名方案的优点及其应用前景。 第三章，在前人的研究基础上，构造了一种改进的前向安全门限签名方案。该方案不 6 具有前向安全性质的门限签名方案 硕士学位论文 仅密钥是前向安全的，而且签名也是前向安全的，即使攻击者收买大于或等于门限数目个 成员后，攻破s k ，但由麟，仍然无法计算出豚n ，从而密钥具有前向安全性。使密钥 泄漏所造成的危害最小化。 第四章，基于s c h n o r r 体制构造了一种前向安全门限签名新方案。该方案在签名过程 中将当前私钥隐藏在签名中，在验证过程中有效的使用了时间段参数，从而保证签名密钥 与签名同时都是前向安全的。为电子商务的应用带来了更为广阔的前景。 第五章，对本文的工作作了总结与展望。门限签名方案与前向安全签名方案都是针对 为了减少密钥泄漏所造成的危害而设计的特殊性质的签名方案。 7 具有前向安全性质的门限签名方案 硕士学位论文 第二章两种特殊性质的签名体制 本章主要介绍两种具有特殊性质的签名方案。门限签名与前向安全签名，主要介绍了 它们的定义、研究背景、现状及有待解决的问题、并分析了已有的签名方案。 2 1 门限数字签名方案 2 1 1 门限签名方案的发展及研究现状 1 门限签名方案提出的背景 在财产继承法及律师制度尚不具有权威性的年代，一个子女众多的明智的富翁往往希 望在自己寿终正寝之后，自己秘藏遗嘱的匣子或珠宝箱在大多数子女到场的情况下才被打 开。可见，秘密共享问题古代有之。又例如，在诸如单控制发射、重要场所的通行等情况 都必须由两个人或多人同时参加才能生效。这时需要将秘密分给多人掌管并同时参与才能 恢复。 传统的密码学考虑一个发送者和一个接收者的情况，但是在互联网得到广泛应用的今 天，大量与信息相关的活动是在组织与个人、组织与组织之间进行的。如在电子政务中， 签署重要文件的权力通常不是掌握在一个人的手里，而是掌握在一个团体手里。签署的文 件表达的也不是一个人的意志，而是某个权力机关的决定，在电子商务中，合同的签署往 往代表的是公司的利益，是董事会集体意志的表达。诸如此类的情况就需要组织内部必须 制定某种策略，使相关人员分享签名，解密等权力。门限密码学的目标就是为这种情况提 供实用的解决方案。 门限签名体制确保有一组人发送给另一组或一个人的信息的安全性，但不能显著地增 加密钥或信息的长度。通常情况下人们会知道一个组织和其公钥，而没必要去了解谁在这 个组织内工作，甚至不需要知道由谁以这个组织的名义签署文件的权力。为了避免密钥管 理所带来的问题，一个组织或团体只能由一个外界所知的公钥，这个公钥不是组织内部个 人公钥的总和，它应当以分布的方式分散给每个相关成员。签名或解密必须按某种安全策 略进行，要考虑到避免滥用职权、抗( 内部或外部) 攻击、密钥安全、方便可行等多项因 素。特殊的门限签名是门限密码学的一个重要分支。( t ，n ) 门限签名体制的签名密钥由n 个人分开掌握，每个人只有密钥的一个碎片，为了产生一个给定消息m 的签名，至少需要 t 个人共同参与，每个人都要产生他们对于这个消息的“部分签名”，然后合并m 消息的总 签名。一个门限体制产生的签名应该与拥有全部签名密钥的单个签名者产生的签名看起来 是一样的，这个签名可以被任何拥有其对应公钥的人验证，即门限签名体制应当是透明的。 2 门限签名的形式化定义 门限签名是普通数字签名研究的一个重要分支。它解决了两个方面的问题：一方面是 8 具有前向安全性质的门限签名方案 硕士学位论文 数字签名不是面向单一的个人，而是面向组织或团体。它解决了如何由集体成员而非个人 代替组织或团体进行数字签名的问题；另一方面以分布式的方式更加有效的保护了签名密 钥的安全性，以防止敌手通过获得签名的密钥来伪造签名者的有效签名。 1 9 8 8 年门限签名的概念【4 6 】由d e s m e d t 提出。门限签名的主要思想是：设玎个人组成一 个群体，签名的秘密密钥通过某种方法分享给群体中的各个成员，使得签名密钥在群中不 少于f 个人的子集合作下才可以使用并签名。通常称这种形式的签名为( f ，玎) 门限签名，其 中t 就是所谓的门限值。从门限签名的特征可以看到，如果门限签名中的t 个或者大于f 个 成员被攻破，那么方案的安全性全无，所以形象的称，为门限值。 门限签名方案包含以下三个部分： 密钥的生成：生成密钥和分配密钥共享给参与者有两个方法。在有可信中心模型下， 可信中心选择密钥和分配共享给参与者；在分配密钥生成模型下，所有的参与者一起计算 密钥共享。 签名的分配：有两个阶段部分：签名生成和签名重建。在部分签名生成阶段，参与者 互相交流，每一个参与者生成给定消息m 的部分签名；在签名重建阶段，拥有门限值之上 个有效的部分签名，那么可以计算出消息m 的有效签名。 签名的验证：给定公钥下，一般个人都可以验证消息签名的有效性。 门限数字签名一般使用多方协议构成。目前，已经采用了不同的秘密共享方式提出了 有效的多方协议，利用这些协议得到了相应的门限数字签名方案。总结起来这些方案还是 基于现有密码学难解问题。 3 门限签名方案的研究现状 在( r ，”) 门限签名方案中，群体的签名密钥被 个成员所共享，任意不少于r 个成员可 以代表群体产生签名，而任意少于t 个成员不能代表群体产生签名。门限签名的基本假设 是至多有t 一1 个非诚实成员。如果任意少于t 个成员不能代表群体产生签名，则称方案是f 安全的。如果即使有f 1 个非诚实成员仍然可以计算出门限签名，则称方案是f 强壮的。 s c h n o r r 在1 9 9 3 年以s c h n o l l r 签名为基础提出了一个门限签名方案，由于只需要计算秘 密的线性组合。因此性能较好。 基于e l g a m a l 签名和数字签名标准签名的门限数字签名方案，由于要计算秘密的乘积 的逆，因此难以产生高效的方案。g e n n a r o 等在1 9 9 6 年基于离散对数提出了门限数字签名 标准签名方案，他们设计了两个重要的子协议来解决计算秘密的乘积和逆的问题，但是他 们的方案有一个缺点：签名密钥是( f ，玎) 共享的，可是生成一个有效的签名却需要2 f 一1 个 成员参加。 r s a 签名方案的研究就更复杂了。由于乙不是域，因此不能利用一般的秘密共享方 法共享密钥，而且为了保护的因子分解，不能让成员知道妒( ) ，b o y d 和f r a n k e l 在1 9 8 9 三- 年提出了一个简单的门限r s a 方案，各成员持有的子密钥满足d = 2 4 ，此时门限签名 l 9 具有前向安全性质的门限签名方案 硕士学位论文 为m d = ：惭睡。此方案的