（计算数学专业论文）门限群签名方案的安全性分析.pdf

中南人学硕士学位论文摘要 摘要 在日常生活中，我们用签名来表示个人身份，在i n t e r n e t 上，数字 签名成为手写签名有效合法的替代者。数字签名的概念最初是由 d i f f i e 和h e l l m a n 提出的，他们提出让每一个用户公布一个公钥用于验 证签名，同时还保存一个私钥用于产生签名。 自从d e s m e d t 和f r a n k e l 于1 9 9 1 年提出( ，z ) f - j 限群签名以后，门限 数字签名得到了广泛的研究，学术界提出了各种各样的( ， ) 门限群签 名方案。本文对门限群签名做了研究，介绍了文章中用到的基本概念 和工具，然后介绍了门限群签名方案应该具有的八条性质，以这些性 质为标准仔细分析了现有的p - g - c 和l - w 两个门限群签名方案，发现 它们均有缺陷和不足。最后，用m a p l e 编程计算椭圆曲线上t a r e 对。 关键词数字签名，秘密共享，h a s h 函数，门限群签名 中南人学硕： 学位论文 a b s t r a c t a bs t r a c t i nt h ed a i l ye x i s t e n c e ，w eu s et h es i g n a t u r et od e n o t eo u ri d e n t i t i e s ， a c c o r d i n g l y , d i g i t a ls i g n a t u r ei s t h el e g a lr e p l a c e ro ft h em a n u s c r i p t s i g n a t u r ei nt h ei n t e r n e t i ti sd i f f i ea n dh e l l m a nw h ob r i n g e df o r w o r d t h e c o n c e p to ft h ed i g i t a ls i g n a t u r e t h e y a d v a n c e dt h a te a c hu s e r p u b l i c i z e sap u b l i ck e yt ov e r i f yt h es i g n a t u r e ，a c c o r d i n g l y , h es h o u l d s a v ea p r i v a t ek e yt og e n e r a t et h es i g n a t u r e s i n c ed e s m e d ta n df r a n k e lp r o p o s e dt h ei d e ao f ( t ，n ) t h r e s h o l d g r o u p s i g n a t u r e 19 9 1 ，l o t s o fs c h o l a r sd e v o t e dt h e m s e l v e st oi ta n d p r o p o s e dm a n yd i f f e r e n ts c h e m e s t h er e s e a r c ho f t h i st h e s i sf o c u s e so n t h r e s h o l d g r o u p - s i g n a t u r e f i r s t l y t h et h e s i si n t r o d u c e ss o m eb a s i c c o n c e p t sa n dt o o l sw h i c hu s e db yo t h e rp a r t s ，t h e ni n t r o d u c e se i g h t p r i n c i p l e so ft h r e s h o l dg r o u p s i g n a t u r e ，a n da n a l y s e st w os c h e m e so f t h r e s h o l dg r o u p s i g n a t u r e t h ea n a l y s i ss h o w st h e s es c h e m e sa l lh a v e s o m ed e f e c t s f i n a l l y , t h et h e s i sc o m p u t e st h et a t ep a i r i n go ne l l i p t i c c u r v ew i t hm a p l e k e y w o r d s d i g i t a ls i g n a t u r e ，s e c r e ts h a r i n g ，h a s hf u n c t i o n ， t h r e s h o l dg r o u p s i g n a t u r e i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者繇扯眺早年j 月粤日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 名：牝新签名逝嗍千哪习 中南大学硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 随着网络信息技术的出现和快速发展，人类进入了信息时代。信息技术正从 政治、经济、和社会生活的各个方面改变着人类的生存和发展方式。无论是在打 开电灯、乘坐飞机、应急求助等日常事务中，还是在国家经济运行、安全防御等 方面，都需要依赖于复杂的信息系统的支持。然而，这个充满希望的时代也充斥 着危险。当人们通过网络来交流思想、吐露内心的秘密、商讨业务、支付金钱， 甚至传递涉及国家的重要经济、外交和军事信息时，都可能被他人窃取秘密。因 此，如果人们希望继续享用信息时代所带来的种种益处，那就必须建立有效的安 全防护措施，这就是所谓的信息安全。与同俱增的以非法入侵和非法获利为目的 的信息犯罪日益增多，对网络的安全运行和进一步发展提出了挑战。人们对信息 安全的要求越来越强烈，这些现实的需求成为信息安全研究的主要动力。信息安 全技术涉及信息论、计算机科学和密码学等多方面知识，它的主要任务是研究计 算机系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和 完整，其中，信息安全的核心是密码技术，密码技术除了提供信息的加密解密外， 还提供对信息来源的鉴别、保证信息的完整和不可否认等功能，而这三种功能都 是通过数字签名来实现的。 数字签名是认证的重要手段之一，也是现代密码学研究的内容之一。数字签 名是同常生活中手写签名的电子模拟物。它的主要功能是实现用户对电子形式存 放消息的认证。在传统的商业系统中，书面文件的亲笔签名或者印章是用来规定 契约的责任。签名或者印章起到认证、核准与生效的作用。在电子商务中，传送 的文件是通过数字签名来证明当事人身份与数据真实性。数据加密是保护数据的 基本方法，但也只能防止第三者获得真实数据，不能保证通信双方的相互欺骗。 数字签名则可以解决否认、伪造、篡改及冒充问题。使用数字签名技术使得发送 者事后不能否认发送的报文签名，接收者能够核实发送者发送报文的签名，接收 者不能伪造发送者的报文签名。接收者不能对发送者的报文进行篡改。随着数字 签名研究的深入，使得其本身具有良好的性能。从而在信息安全、身份认证、数 据的完整性、不可否认性与匿名性等方面有广泛的应用前景，特别在电子商务、 电子支票、电子购物、电子政务与知识产权等方面的广泛应用，有力显示了它的 重要性。正是由于数字数字签名具有独特功能和实际用途，在一些特殊行业比如 金融、商业及军事也有广泛的应用。 中南大学硕十学位论文第一章绪论 1 2 门限群签名的发展概况 数字签名包括普通数字签名和特殊数字签名。普通数字签名算法有：r s a 、 e i g a m a l 、s c h n o r r 、d s a 、e c d s a 和有限自动机数字签名算法等；特殊数字签 名有：盲签名、代理签名、群签名、不可否认签名、公平盲签名、门限签名和具 有消息恢复功能的签名等。群数字签名是一个相对比较新的概念。它是由 d c h a u m h e 和e v a nh e y s t 于1 9 9 1 年提出的1 4 。j c a m e n i s h 和m s t a d l e r ， j c a m e n i s h 和m m i c h e l s ，g a t e n i e s e 和g t s u d i k 等对其进行了修改和完善。在 一个群签名方案中，一个群体中的任意一个成员可以以匿名的方式代表整个群体 对消息进行签名。与其他数字签名一样，群签名是可以公开验证的，而且可以只 用单个群公钥来验证。 一个完整的群签名方案应包含创建、加入、签名、验证、打开等过程，安全 性应满足匿名性、不关联性、防伪造性、可跟踪性、防陷害攻击、防联合攻击等 【5 5 1 。将密码学中的门限方案【2 7 之8 1 引入到群签名方案中就形成了门限群签名。 一般的( f ，n ) 门限群签名是指群内，个或更多个成员可代表群进行签名，任何 小于t 个或更少的参与者则不能进行群签名。 d e s m e d t 和f r a n k e l 于19 9 1 年提出( ，”) f - j 限群签名以来【4 9 1 ，门限数字签名得 到了广泛的研究，提出了各种各样的( ，”) f - j 限群签名方案1 5 5 。下面简要介绍一 下近几年国内外比较典型的几个门限群签名方案。 1 9 9 8 年w a n g 等【5 2 】提出了两个u ，船jf - j 限群签名方案，一个可以追查签名者 身份，另一个不可以。王贵林和卿斯汉【”】、t s e n g j e n l 2 1 、“等【3 j 分别给出了不同 的攻击方法，证明w a n g 等的方案无法抵抗其他小组冒充该小组生成有效的签名、 不具备可追查性【5 5 】；无法抵抗恶意攻击者的伪造攻击1 4 ，5 j 。徐秋亮提出了改进门 限r s a 数字签名体制【5 4 】，王贵林和卿斯；! ! 叉【”坤旨出它无法抵抗合谋攻击，并且进 一步指出了性能良好的门限群签名应该具有的特点：群签名特性、门限特性、签 名验证的简单性和匿名性、身份的可追查性、系统的强壮性和稳定性。根据这些 特点衡量已有的( r ，n ) 门限群签名体制，都存在一些弱点。2 0 0 3 年甘元驹等提出 了一种基于因式分解的可证实的门限群签名方案【5 引，该方案对g u i l l o u q u i s q u a t e r 的数字签名方案进行改进，并在此基础上提出了一个新的( ，n ) 门限签名方案。 签名过程主要包括系统初始化、秘密影子( 子秘密) 的生成与验证、部分签名的生 成与验证、群签名的生成与验证等几部分。2 0 0 4 年王晓明等基于r s a 和离散对 数问题的安全性，提出了一个动态门限群签名方案1 6 2 1 ，该方案不仪能满足门限 2 中南人学硕十学位论文 第一章绪论 群签名的性质，而且也能抵抗联合攻击；方案的突出优点是能够动态的改变( f ，刀) 门限的门限值，当门限值改变时，无需修改群成员的秘密子密钥和群公钥；能方 便的增加或注销群成员，群成员只需保存一个密钥；更换系统密钥时，采用并行 过程，提高了运行效率，但美中不足的是该方案没有考虑到签名参与者的欺诈问 题；但在2 0 0 5 年郭兴阳等【6 5 】指出该方案有亢余，门限更新、群成员注销和系统 密钥更新过程不安全，不能抵抗合谋攻击，不能防止冒充。2 0 0 6 年王明文等人 提出了一个无可信中心的门限r s a 数字签名体制1 6 4 j 。该方案基于b o n e h 等学者 的分布式r s a 密钥产生协议和s h a m i r 秘密共享方案而构建。签名过程分为四个 阶段：系统初始化、生成个体签名、生成群签名以及签名验证。在系统的初始化 阶段不需要可信中心的参与，并且个体签名的生成、群签名的生成和验证都可以 方便的实现。 1 3 本文的主要内容与组织 随着信息科学技术的迅速发展，使得人们对信息安全的要求越来越高。如何 实现系统内信息的安全、保密、真实与完整，这就需要数字签名技术。本文就是 围绕着数字签名的研究展开的，并通过m a p l e 编程计算椭圆曲线上的t a t e 对。 本文具体安排如下： 第一章：主要介绍了数字签名的背景及国内外的研究现状与进展。 第二章：主要介绍密码学领域的相关基础数学知识，主要包括大整数分解问 题、l a g r a n g e 插值公式、中国剩余定理以及离散对数问题等数学知识和概念； 第三章：主要介绍密码学基本知识，包括密码学算法、单向h a s h 函数、秘 密共享等。阐述了数字签名的定义与分类、安全性分析、设计方法、攻击类型及 安全性证明。分析了几种典型的数字签名方案：r s a 签名体制、e 1 g a m a l 签名方 案、d s s 签名体制、s c h n o r r 数字签名方案。 第四章：主要介绍了门限群签名的概念并分析了它应该具有的性质，以此为 标准对现有的p g c ，l w 这两个门限群签名方案进行了安全性分析。发现这两 个方案都没有解决群内f 个成员联合攻击的问题。 第四章：主要介绍了门限群签名的概念并分析了它应该具有的性质，以此为 标准对现有的p g c ，l w 这两个门限群签名方案进行了安全性分析。发现这两 个方案都没有解决群内t 个成员联合攻击的问题。 第五章：通过m a p l e 编程实现椭圆曲线上两点的加法，计算椭圆曲线上的 t a t e 对。 第六章是本文的总结和研究展望。 中南人学硕士学位论文 第一二章数字签名基础 2 1 有关数学基础 第二章数字签名基础 在描述门限群签名方案之前，我们需要了解一些关于模算法、同余、大素数 分解等数论知识。本章主要介绍的是大整数分解问题、l a g r a n g e 插值公式、中国 剩余定理及相关结论以及离散对数问题及其性质等。 2 1 1 大整数分解问题 在数论中，整数的唯一分解定理指出，任何一个大于1 的整数，若不考虑因 子的次序，则它能唯一的表示成若干素数的乘积。 定义2 1 ( 大整数分解问题) 给定整数聆，找出它的素因子，即对门进行因 式分解刀= p l q p ：吃p k 龟，其中只是互不相同的素数，e ，是正整数。 在现有的计算能力下，已知若干不同的素数p 。，p ：，仇，求这些素数的 乘积在计算上是可行的，是一个多项式时间算法，反之，已知”，求它的素因子 是困难的。 定义2 2 ( 欧拉函数) 设n 是一个正整数，( 月) 的值等于序列1 , 2 ，3 ，刀一1 中与n 互素的整数的个数，若，2 的因子分解已知，则很容易计算( 聆) ，但当n 很 大时，若刀的因子分解未知，则很难计算矽( 刀) 。 在数论中，大整数分解问题是一个古老的问题，分解一个大整数理论上很简 单，但是实际过程很费时，尽管如此，在这方面现在还是有一些进展。对于小于 1 1 0 位左右的十进制数来说，目前最好的大整数分解算法是数域筛选法( n f s ) ； 对于大于1 1 0 位左右的十进制数来说，一般的数域筛选是目前己知最快的大整数 分解算法。而二次筛选法( q s ) 【1 2 ，1 3 1 对于低于1 1 0 位的十进制数来说，是目前已 知的最快算法。1 0 2 4 比特的数在目前看来是安全的，现在广泛应用的基于大整 数分解问题提出的r s a 密码体制，仍被认为是安全性最好的体制之。 4 中南大学硕士学位论文第二章数字签名基础 2 1 2 中国剩余定t - 里( c r t ) 定义2 3 ( 中国剩余定理) 假定铂，m ，为两两互素的正整数( 即当i 时， g c d ( 似，) = 1 ) 。假定口l ，口，为整数，m = 铂xm 2 x x ，m = i m ，则同余 方程组x - a ，( m o d m , ) 有唯一解为y = a , m , y , ( m o d m ) ， ( 其中 t = l m y l 三i ( m o d ) ) 。 2 1 3 离散对数问题 离散对数问题【5 】【1 4 】是公钥密码体制的一个基本问题，它的安全性决定了很多 密码算法和方案的安全性，在密码学中，许多方案【1 5 棚1 都是基于这个问题的，如 数字签名标准 2 0 , 2 1 , 2 2 】、e i g a m a l 型签名体制及其变形等。 定义2 4 ( 离散对数)设g 是一个有限循环群，且g g 是g 的一个生成 元，元素a g ，整数x ( 0 x o r d ( g ) ) 满足口= g ，则称x 为口的以g 为底数 的离散对数。用l o g 异口表示。离散对数有以下的性质： 设g = 是阶为1 的有限循环群，a ，b ，c g ( 1 ) l o g ga b = l o g ga + l o g gb ( m o d n ) ， ( 2 ) l o g ga 。= x l o g ga ( m o d n ) ，v x z ， ( 3 ) 若h 是g 的另一个生成元，则l o g ga = l o g a 1 0 9 g 】( m o d n ) ，其中 l o g gh = 1 0 9 g - l ( m o d n ) 。 定义2 5 ( 离散对数问题) 对于一个有限循环群g = 和元素a g ，寻 找x ( 0 x o r d ( g ) ) ，使a = g 。成立。 5 中南大学硕十学位论文 第二章数字签名基础 2 1 4l a g r a n g e 插值公式 定义2 6 ( l a g r a n g e 插值公式) 已知一个聍次多项式上的n + 1 个点( 一，”) ， 月+ l疗+ l 令缈( x ) = 兀( x - - x i ) ，厂( x ) = 仍( x 班，其中仍( x ) = 妒( x ) ( ( x 一薯) 伊( 誓) ) ，则厂( x ) p i，；i 就是此多项式。 2 1 5 二次剩余 定义2 7( 二次剩余) 设刀是两个素数p ，q 的乘积，且少乙，若存在 整数z ，使得x 2 = y m o d n 成立，则y 是模，2 的二次剩余( 平方剩余) ；若不存在 整数x 使得x 2 = y m o d n 成立，i ) - l l j y 是模玎的二次非剩余。 定义2 8 ( 二次剩余问题) 给定整数玎与y ( 0 y 功，判定是否存在整数 x ( 0 x 功，使得x 2 = ym o d n 成立。 2 2 密码学基础 密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律， 应用于编制密码以保守通信秘密的，称为编码学；应用于破泽密码以获取通信情 报的，称为破译学，总称密码学。 密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照 这些法则，变明文为密文，称为加密变换；变密文为明文，称为解密变换。密码 在早期仅对文字或数码进行加、解密变换，随着通信技术的发展，对语音、图像、 数据等都可实施加、解密变换。 6 中南人学硕士学位论文第二章数字签名基础 2 2 1 相关密码学算法 基于密钥的算法通常有两类：对称密钥算法和公开密钥算法【2 4 1 。 对称密钥算法( s y m m e t r i c k e ya l g o r i t h m ) 有时又叫传统密码算法，就是加密密 钥能够从解密密钥中推算出来，反过来也成立。在大多数对称密钥算法中，d i l l 解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和 接收者在安全通信之前，商定一个密钥。对称密钥算法的安全性依赖于密钥，只 要通信需要保密，密钥就必须保密。 对称密钥算法可分为两类。对位流或字节流进行操作运算的算法称为序列密 码或流密码( s t r e a mc i p h e r ) 。另一类算法是对明文分为若干组，一组一组进行运算， 这些位组称为分组或块( b l o c k ) ，相应的算法称为分组密码或块密码( b l o c kc i p h e r ) 。 课题中使用的排列码加密算法属于分组密码，是一种新型的对称加密算法。 公开密钥算法( p u b l i c k e ya l g o r i t h m ) 出现于1 9 7 6 年。它最主要的特点就是加 密和解密使用不同的密钥，每个用户保存着一对密钥一公开密钥以和私有密钥 s k ，因此，这种体制又称为双钥或非对称密钥密码体制【2 5 】。 在这种体制中，肷是公开信息，而需要由用户自己保密。加密算法e 和 解密算法也都是d 公开的。虽然麒与s k 是成对出现，但却不能根据麒计算出 s k 。 公开密钥算法的特点如下：用公开密钥尸k 对明文m a n 密后，再用私有密钥 s k 解密，即可恢复出明文，如下所示： d ( 昱雎( m ) ) = m 明文同样可以用私有密钥加密而用公开密钥解密，如下所示。 d 雕( e 麟( m ) ) = m 这就是用作数字签名( d i g i t a ls i g n a t m e ) 。 2 2 2 单向h a s h 函数 单向h a s h 函数【2 6 1 就是把任意长度的明文比特映射为固定长度七比特的函 7 中南人学硕七学位论文第二章数字签名基础 数，即4 ( ) ：他1 ) 专 0 ，1 k 。记消息为m ，散列值厅= 暾砷，一个安全的单向h a s h 函数应该至少满足以下要求： ( 1 ) 输入长度是任意的； ( 2 ) 输出长度是固定的； ( 3 ) 给定m ，很容易计算办； ( 4 ) 给定h ，根据办= 脚计算所很难，即求逆不可行； ( 5 ) 给定m ，要找到另一消息砌，并满足以砌= 域砌) 在计算上是不可行； ( 6 ) 给定h ( ，) ，要找两个不同的川和慢，使得顾川) = 爿( 慢) 在计算上是不 可行。 满足前五条性质的单向h a s h 函数称为弱单向h a s h 函数，满足以上六条性质 的h a s h 函数称为强单向h a s h 函数。单向h a s h 函数的安全性依赖于输出的比特 长度，一般要求输出长度至少为k = 1 6 0 比特。比较流行的单向h a s h 函数有 m d 2 ，朋d 5 ，删一l 等。 容易看出，强抗碰撞的h a s h 函数同时也满足单向性，当然也满足弱抗碰撞 性。弱抗碰撞的h a s h 函数，是在给定x 下，考察与特定x 的无碰撞性；而强抗 碰撞的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 函数的攻击法关于h a s h 函数的长度，n i s t ( 美国国家标准技术研 究所) 在其安全h a s h 标准中建议用1 6 0 位的h a s h 值这将使得生日攻击更难进行， 因为需要岁次的随机h a s h 运算。 2 2 3 秘密共享 秘密共享是信息安全和数据保密中的重要手段。其概念最早是由s h a m i r 2 7 1 8 中南大学硕士学位论文 第二章数字签名基础 和b l a k l e y 2 8 】于1 9 7 9 年提出的。它是指将秘密j 分割成若干个子秘密，或者称为 份额( s h a r e ) ( 或者碎片p i e c e ，或者影子s h a d o w ) 在一组参与者p = p l ，p2 ，p 。) 中进行分配，使得每一个参与者都得到关于该秘密的一个秘密份额，而只有p 的 一些特定的子集( 称为授权子集) 才能有效地恢复，其他子集( 非授权子集) 不能有 效地恢复，为了加强安全性，甚至不能得到关于秘密的任何有用信息。由此，引 入门限秘密共享方案的一般概念 定义2 8 ( 秘密共享) 设秘密s 被分成n 个部分信息，每一部分信息称为 一个子秘密或者影子，由一个参与者特有，使得： ( 1 )由其中任意，个参与者所特有的子秘密可重构s ： ( 2 )由少于f 个参与者所特有的子秘密则无法重构。称为( f ，门) 门限共享方 案，f 称为方案的门限值。 如果一个参与者或者少于，个的一组参与者在猜测秘密s 时，并不比系统外 人有优势，则称这个方案是完善的。如果任意一组参与者，若其个数少于 个， 则由他们所特有的子秘密得不到秘密s 的任何信息。 最常用的秘密共享体制是门限秘密共享体制。在( f ，刀) 门限秘密共享体制中， 秘密信息的持有者用一个概率多项式算法，把秘密信息s 分割成n 个份额，分别 由刀个不同的人来保存或者保存于n 个不同的地方，使得只有获得这即个份额中 的至少r 个才一可以有效地恢复出，而任何少于f 个都不能恢复出，甚至得不到 关于s 的任何信息。门限群签名方案通常都采用了门限秘密共享体制。 2 2 4 数字签名的定义 一般地，数字签名方案都是基于某个公钥密码体制，签名者用自己的私钥对 消息进行签名，验证人用签名者的公钥对签名进行验证。从表面上看，数字签名 与公钥加密使用密钥的顺序不同，实际上，数字签名与公钥加密一样也是通过单 向陷门函数确保其安全性的。本质上，大数分解困难问题和离散对数困难问题等 各种计算困难问题的存在是安全的数字签名方案存在的根本。 数字签名方案通常包括三个主要过程：系统的初始化过程、签名产生过程和 签名验证过程。系统的初始化过程产生数字签名用到的一切参数；签名产生过程 中，用户利用给定的算法对消息产生签名；签名过程中，签名者利用公开的验证 9 中南大学硕+ 学位论文 第二章数字签名基础 方法对给定消息的签名进行验证，得出签名是否有效的结论。 数字签名的形式化定义是数字签名描述性定义的一种抽象和形式化的概括， 签名过程与验证过程本质上是两个不同的算法。 定义2 9 ( 数字签名方案) 称三个集合：消息集合m 、密钥集合k 、签名 集合s 和两个算法，即签名算法s i g , 、验证算法v e t 组成的五元组( m ，s ，k ， 跪，v e t ) 为一个数字签名方案，其中k 是包含公钥和私钥在内的所有密钥的集 合，并要求满足下列条件： ( 1 ) 签名算法：对密钥集合k ，相应的签名算法s 喙s i e , ，踞：m 斗s ， 对任意的消息m m ，有s = s 喙( 砷，s s 为消息m 的签名，将( m ， s ) 发送给签名验证者。 ( 2 ) 验证算法：对于密钥集合k ，有签名验证算法 v e t k ：m x sj 讧r t l 弓f c i l s 每 如果 v e r x 力= t r u e ，y = s i g , ，否则v e r x ( x , 力= f a 瓜e ，y 陇。 签名的接受者或验证者收到( m ，s ) 后，计算v e r k ( x , 力，若v e r x ( x , 力= t r u e ， 签名有效；否则，签名无效。 2 2 5 数字签名的分类 1 ) 基于数学难题的分类： ， 根据数字签名所基于的数学难题，数字签名方案可分为基于离散对数的数字 签名方案、基于素因子分解的签名方案、基于椭圆曲线离散对数问题的签名方案、 基于离散对数和素因子分解的签名方案、基于二次剩余问题的签名方案等。 2 ) 基于签名用户的分类： 分为单用户签名和多用户签名，多用户签名方案又称多重数字签名方案。根 据签名的过程不同，多重数字签名又分为有序多重数字签名和广播多重数字签 名。 3 ) 基于签名人对消息是否可见： 分为普通数字签名与盲签名方案，盲签名方案表示签名者对消息不可见，但 事后可以证明消息的存在。 l o 中南大学硕+ 学位论文 第二章数字签名基础 4 ) 基于签名人是否受别人委托签名： 分为普通数字签名方案和代理签名方案，如果授权的不是一个人，而是多个 人，这时的数字签名方案称为代理多重签名方案。 2 2 6 数字签名面临的攻击 攻击者攻击一个密码算法通常采取的攻击方法可以分为两大类【3 4 1 ，其一是 确定性分析法，其二是统计分析法。确定性分析法是指利用一个或几个已知量， 用数学关系式表示所求未知量，己知量和未知量的关系视签名算法和验证算法而 定，寻求这种关系是确定性分析法的关键步骤，现在对数字签名方案的攻击绝大 多数采用这种方式。统计分析法是指利用消息及其相应签名的某种概率关系来进 行攻击的方法。这种攻击方法目前对基于公钥体制的方案来说是不大适用的，它 主要是用来攻击分组密码和流密码。 与讨论加密方案时的情况一样，对签名方案也有不同类型的攻击。如果一个 攻击者能够以不可忽略的概率达到如下的至少一项的目的，那么我们说这个攻击 者成功的攻破了他所试图攻击的数字签名方案攻破数字签名方案的攻击类型1 3 副： ( 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 ) ：虽然不能找到签名人的私钥，但攻击 者能够伪造所有消息的签名。 敌手攻击一个数字签名方案通常采用以下基本攻击类型p 6 j ： ( 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 ) 消息攻击：敌手在试图攻击一个签名方案之前，能够获得某些消息或 选定的消息及其签名。这其中又包括选择消息攻击和适应性选择消息 攻击两类： 1 ) 选择明文攻击( c h o s e n m e s s a g ea t t a c k ) ：敌手可选择一个消息 中南人学硕十学位论文第二章数字签名基础 列表并要求合法签名人签名这些消息。 2 ) 适应性选择明文攻击( a d a p ti v e l y c h o s e n m e s s a g ea t t a c k ) ： 敌手可以适应性地选择消息让签名人签名，他可以选择一些消息并得到 相应的签名，然后进行密码分析，并根据他的分析结果，选择下一个要 签名的消息，然后继续上述过程。 虽然大多数数字签名方案的安全性并没有得到证明，但是多年来也并没有明 显的验证表明这些方案是不安全的，例如基于大数分解问题的r s a 方案。因此， 把一些数字签名方案的安全性转化为这些公认安全的数字签名方案的安全性，是 一个实际有效的保证数字签名方案安全性的方法。同时，利用计算复杂度理论， 将数字签名方案的安全性转化为一些己知不可解的数学难题，就是通常所况的可 证明安全性的研究，也足近年来的研究热点之一。但是，如此证明安全的数字 签名方案普遍存在效率偏低的问题。在可证明安全性的研究中，还有一种是将数 字签名算法中常用到的h a s h 函数看作一个r a n d o mo r a c l e 模型。假设h a s h 函数 没有弱点的情况下，基于该模型的证明能够保证一个签名方案的安全性。 2 2 7 数字签名安全性证明方法 数字签名的安全性主要有以下三种证明方法【3 7 j 。 ( 1 ) 可证明安全性 标准模型下，利用计算复杂性，将数字签名的安全性转化为一些己知的难题， 如大整数分解问题，离散对数问题或者一般胛完全问题 ( 2 ) 利用转化证明 虽然很多数字签名方案( 如e 1 g a m a l ) 的安全性性没有得到证明，但是十几 年来并没有明显的迹象表明这些方案是不安全的。因此，把一些数字签名方案的 安全性转化为这些公认安全的数字签名方案的安全性，是一个有效的证明方法。 ( 3 ) 基于随机预言模型证明 众所周知，数字签名方案经常使用h a s h 函数，使用h a s h 的目的是为了用一 个简短的签名来签署许多长的消息，同时要求h a s h 函数是无碰撞的。后来，人 们认识到，为了增强签名方案的安全性，h a s h 函数的使用实质也是签名方案安 全性的一个本质要素。同样，为了给签名方案提供一个安全性证明，提出更强的 假设是有必要，于是，一些学者建议将h a s h 函数看成是一个随机函数，并给出 了相应的模型，称为“随机预言机模型”。假设h a s h 函数没有弱点的话，基于此 1 2 中南人学硕+ 学位论文第二章数字签名基础 模型的证明能够保证一个签名方案的总体设计的安全性。 2 2 8 数字签名方案的设计要求 ( 1 ) 方案设计的基础或自玎提条件 一个单向陷门函数，正向计算是可行的，但逆向计算是不可行的，也就是说 不存在一个有效的多项式算法以不可忽略的概率进行逆向计算。比如，r s a 数字 签名方案的单向哈希函数是f ( m ，”，e ) = m 。m o d n ，输入m ，刀，e ，输出密文c ， e = m 。m o d 疗。反过来，已知( 胛，c ) ，求m 是不可行。但是，如果掌握私钥，即 陷门信息d ，则可计算m = c dm o d 刀。因此，单向陷门函数的构造是关键。 ( 2 ) 方案设计的安全性要求 1 ) 防完全攻破 这是最根本的安全基础，所依赖的是一个数学难题，即数字签名所依赖的单 向陷门函数，也就是说不可能由公共参数攻破陷门信息。当不知道陷门信息时， 逆向求解在计算上是不可行。除在密码算法中常见的数学难题外，要设计符合这 个要求的数学难题是困难的，因为要对这个算法进行时间复杂度估计和实际计算 效率比较。现在公布的那些数字签名标准所依赖的数字签名难题可以说是久经数 学家、密码学家长期研究成果的基础上形成的。 2 ) 防一般伪造 这是最起码的要求，如果攻击者找到了一个功能等效于签名算法的有效算 法，这等于签名已被完全攻破。 3 ) 防选择明文攻击 如果攻击者把签名者当作一个随机预言机，可以有选择性选取消息，获取其 签名，利用这些消息进行攻击。 4 ) 防确定性攻击 这是签名方案设计者最难克服的一种攻击手段。因为只有符合验证算法要 求，验证者就无从判断它的真伪，按照协议要求，认为签名是正确的。 5 ) 防其他攻击 除了防上述可能存在的攻击外，从理论上讲，应该预防可能存在的其他攻击。 只有数字签名符合上述安全性要求，一般认为方案是安全的，但要证明一个方案 符合这些要求，往往是困难的。长期以来数字签名的安全性一直困扰着密码学家， 学者提出很多数字签名方案，漏洞是在所难免的。在数字签名方案的研究中，较 中南人学硕十学位论文第二章数字签名基础 有趣的现象是当一种新的数字签名被提出后，往往有很多文章对它进行进一步的 密码分析。这也许是最近几年来数字签名可证安全问题成为热点的原因吧。 ( 3 ) 方案设计的计算复杂度要求 计算复杂度是数字签名方案设计必须考虑的因素，我们在比较具有同等功效 的数字签名时，计算效率高的方案备受欢迎，特别是网络宽带有限的情况下，优 势史有甚者明显。实际应用中，既要安全性能好，又要计算效率高。应用中，既 要安全性能好，又要计算效率高。 2 2 9 几种典型数字签名方案及分析 ( 1 ) r s a 签名方案 r s a 是目前使用较多的签名体制。1 9 7 8 年美国麻省理工学院三名密码学者 r l r i v e s t ，a s h a m i r 和l m a d l e m a n 提出了一种基于大整数因子分解困难性的公 钥密码体制，简称r s a 密码体制。r s a 密码体制既可用于加密又可用于数字签 名。它的安全性是基于大整数因子分解的困难性。因式分解理论的研究现状表明： 所使用的r s a 密钥至少需要1 0 2 4 比特，才能保证有足够的中长期安全。 r s a 签名方案的实现：设彳为签名人，任意选取两个大素数p 和g ， ( 甩) = ( p 1 ) ( g 一1 ) ，随机选取整数e ( 刀) ，满足g c d ( e ，矽( ，2 ) ) = 1 ；计算 整数d ，满足e d = lm o d 矽( 即) 。p ，q 和矽( 胛) 保密，私钥为d 。 1 ) 签名：对任意消息朋( 朋 刀时，可利用哈希函数h 进行压缩，计算 s = 办( 脚) dm o d 刀，接收方或验证方受到( 聊，s ) 后，计算聊= s 8m o d 刀，后 检查m 。= 办( 脚) 是否成立，即鉴别签名是否正确。在这里m 只起到一种支撑的 1 4 中南人学硕士学位论文第二章数字签名基础 作用，没有实质的作用，如果m 包含重要的信息，不能泄露，那么签名还要进 行加密处理，再传送。 ( 2 ) e 1 g a m a l 签名方案 e i g a m a l 算法既可以用于数字签名，也可用于加解密，其安全性依赖于计算 有限域上离散对数的困难性上。e i g a m a l 数字签名体制3 8 1 是由t e 1 g a m a l 于1 9 8 5 年提出的，其变体已经使用于d s s 中。e 1 g a m a l 签名方案是非确定性的，这意 味着对任何给定的消息又许多有效的签名，并且验证算法能够将它们中的任何一 个作为可信的签名而接受。 1 ) 系统参数：设系统( 或网络中) 存在一大素数p ，及模p 的生成元g ， 使得求离散对数为不可能。用户私钥：签名者任选一整数x ， l x p ，x 为其密钥。用户公钥：签名者求出 y 2 9 3m o d p ，( p ，g ，y ) 为其公开密钥。 7 一，、“il l lf oo 2 ) 签名生成：对于明文l m p 一，签名者先任选一整数k 满足 ( p ，k 一1 ) 一 。接 着计 算签名组 ( r ，s ) ： r2 g 。m o d p ，s = k - l ( 办( m ) 一x r ) m o d p ，其中h 为h a s h 函数。 3 ) 签名验证：验证者验证下式是否成立：g 州2y r ，_ m o d p 。若j 下确， 则【r ，s ) 为聊的合法签名，否则为非法签名。 显然e 1 g a m a l 签名的安全性基于求解离散对数问题困难性。对手无法由签名 公钥推算出签名秘密钥。但是若对手得到签名时签名者选择的随机数k ，即可得 到秘密钥x ( 求解一元一次方程) ，进而破解系统。同时如果在两个不同消息签 名时选用同一个随机数k ，通过求解两个二元一次方程组成的方程组求出秘密钥 x ，系统也可破，所以系统中伪随机生成器要足够安全。 ( 3 ) d s a 签名方案 d s a ( d i g i t a ls i g n a t u r ea l g o r i t h m ，数字签名算法，用作数字签名标准的一 部分) ，它是另一种公开密钥算法，它不能用作加密，只用作数字签名，d s a 使 用公开密钥，为接受者验证数据的完整性和数据发送者的身份。它也可用于由第 三方去确定签名和所签数据的真实性。d s a 算法的安全性基于解离散对数的困难 性，这类签名标准具有较大的兼容性和适用性，成为网络安全体系的基本构件之 一o 1 ) 参数与密钥生成 中南人学硕十学位论文第二章数字签名基础 首先选取两个大素数p 和g ，p 是，位长的素数，其中，从5 1 2 到1 0 2 4 且是 6 4 的倍数。 g 是1 6 0 位长且是p 一1 的因子。然后选择一个生成元g = h p 一m o d p ，且 1 h l 。最后选择随机数1 x g 作为私钥，计算 y = g 。m o 作为公钥。 消息空问m = 0 ，1 ) ， 签名空间彳= z 。z 。， 密钥空间 k = p ，q ，g ，_ y ；x z 。母，y = g 。m o d p ) 。 2 ) 签名算法 设待签名消息为m ，签名者选择秘密随机数k z 。，计算： ，= ( g m o d p ) m o d q ，s = 【k 。1 ( 办( 朋) + x r ) m o d q ，则数字签名为( ，s ) 。其中h 为 h a s h 函数。d s a 标准指定了安全敖列算法( s h a 一1 ) 。 3 ) 签名的验证算法 签名接收者收到签名( ，s ，m ) 后首先计算：w = s m o d q ， u 1 = h ( m ) w m o d q ，甜2 = r w m o d q ，v = ( g 蛳y 沁) m o d p m o d q 。 然后验证v = ，如果等式成立，则签名有效。否则签名无效。 ( 4 ) s c h n o r r 数字签名方案 c s c h n o r r 于1 9 8 9 年提出了一种数字签名方案，即s c h n o r r 数字签名方案， 它的安全性基于离散对数。因为s c h n o r r 数字签名所需要的大部分计算都可在预 处理阶段完成，并且这些计算与预处理的消息无关。因此，s c