（应用数学专业论文）代理数字签名理论的研究.pdf

。t 摘要 论文题目：代理数字签名理论的研究 学科专业：应用数学 研究生：王波 指导教师：王尚平教授 摘要 f i i ii fi ii iii ii fl l l fiil y 1814 4 0 6 签名；堡丛 摊2 瑚 数字签名是保证数据交换的完整性、发送信息的不可否认性、交易者身份的确定性的 一种有效的解决方案。基于不同的应用背景，各种特殊的数字签名使得数字签名的理论和 应用研究日益深入和广泛。本文在对基于身份的数字签名、指定验证者数字签名和盲数字 签名研究的基础上，重点研究了代理数字签名，主要工作如下： 分析了代理数字签名的应用背景，分析了现有的代理数字签名方案及其安全模型， 分析了一般代理数字签名的构建方法和安全模型。研究分析了基于身份的数字签名、指 定验证者数字签名、盲签名的背景和一些现有的方案。 构造了一个基于身份的指定验证者代理签名方案。新方案具有基于身份的特性，可以 克服基于证书的密码系统中烦琐的密钥保管问题。并把指定验证者签名和代理签名相结 合，可以防止原始签名者的伪造和由于指定验证者故意泄露验证私钥而让其他人具有验 证签名的权利。 对a m i t 代理保护盲签名方案进行改进，克服了原方案中存在的安全缺点同时构造 了一个基于椭圆曲线的代理保护盲签名方案。 关键词：数字签名；代理签名；指定验证者签名；双线性对；盲签名 本研究得到以下基金资助 田家自然科学基金( 蚴0 8 9 ) 陕西省自然科学研究计划资助项目( 2 0 0 5 f 0 2 ) 陕西省教育厅自然科学研究计划资助项目( 0 3 j k l 6 5 ) 西安理工大学科技创新基金( 1 0 8 - 2 1 0 4 0 2 ) 陕西省教育厅专项科学研究计划资助项目( 0 6 l 2 1 3 ) 田际合作项目( 日本) 京通株式会社( 1 0 8 2 3 0 5 0 1 ) 企业项目( 西安) 西安瑞日电子发展有限公司( 1 0 & 2 3 0 6 0 8 ) 耆 霉 至 塞 a b 翻删 t i t l e ：t h er e a s e r c h o np r o ys i n g a t u r et h e o r y m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：b 0w a n g s i g n a t u r e ：幽丝： s u p e r v i s o r ：p r o f s h a n g p i n gw a n gs i g n a t u r e ： a b s t r a c t d i g i t a ls i g n a t u r ei s a ne f f e c t i v es o l u t i o nt oa s s u r ct h ei n t e g r a l i t yo f d a t ac h a n g i n g , n o n r e p u t a t i o no fs e n d i n gm e s s a g ea n dd e t e r m i n i s t i co fp a r t i e s m a n ys p e c i a ld i g i t a ls i g n a t u r e s b a s e do nd i f f e r e n tb a c k g r o u dd e e p e dt h et h e o r ya n da p p l i a n c er e s e a r c ho fd i g i t a ls i g n a t u r e s t h i s p a p e rf o c u s e so np r o x ys i g n a t u r e s ，m e a n w h i l e ，s o m eb a s i cr e s 髓r c ho ni d - b a s e ds i g n a t u r e s ， d e s i g a n t e dv e r i f i e rs i g n a t u r e sa n db l i n ds i g n a t u r e sw e r ed o n e t h em a i nc o n t r i b u t i o n sa r ea s f o l l o w s ： a n a l y s i n gd e l e g a t es i g n a t u r e s a p p l i e db a c k g r o u n di nd e t a i lt h ee x i s t i n gs c h e m e sa n d s e c u r i t ym o t i l ea n dn o r m a ld e l e g a t es i g n a t u r e sa l ea n a l y s e d a n ds o m es c h e m e so fi d b a s e d s i g n a t u r e s ，d e s i g a n t e dv e r i f i e rs i g n a t u r e sa n db l i n ds i g n a t u r e sw e r ei n t r o d u c e d a ni d - b a s e dd e s i g n a t e dp r o x ys i g n a t u r ei s p r e s e n t e dw h i c hi s a b l et or e d u c et h e c o m p l e x i 哆o fk e e p i n gt h ep u b l i ck e y , a n dd e s i g n a t e ds i g n a t u r ea n dp r o x ys i g n a t u r ea r c c o m b i n e dw h i c hc a nb eu s e dt op r e v e n ts i g n e rf r o mf o r g i n ga n dd e s g i n a t e dv e r i f i e rf r o m l e a k i n gp r i v a t ek e yo np u r p o s et h a tg i v eo t h e r st h ep r i v i l a g eo fv e r i f i e r i n gt h es i g n a t u r e t h ep r o x y - p r o t e c t e db l i n ds i g n a t u r es c h e m eo fa m i ti si m p r o v e d ，t h en e wo n e c o n q u e r st h e s e c u r i t yd i s a d v a n t a g ei nt h eo l do n e a n dap r o x y - p r o t e c t e db l i n ds i g n a t u r es c h e m eb a s e do n e l l i p t i cc u r v ei sp r c s e t e d k e yw o r d s ：d i 舀t a ds i g n a t u r e ；p r o x ys i g n a t u r e ；d e s i g n a t e d - v e r i f i e rs i g n a t u r e ；b i l i n c a r p a i r i n g s = b h n ds i g n a t u r e n f 、 l ，l 目录 1 绪论 目录 1 1 1 弓l 言1 1 2 密码学概述2 1 3 数字签名简介4 1 4 代理数字签名6 1 5 本文的研究内容及其科学意义。6 1 6 本文的章节安排6 2 数学理论 8 2 1 整数因子分解问题8 2 2 离散对数问题8 2 3r s a 问题及r s a 假设9 2 4d i f f i e _ li m a n 问题和d j 仟j e - h e ii m a n 假设1 0 2 5 二次剩余f 司j 巨1 0 2 6 哈希( h a s h ) 函数。：。1 1 2 7 双线性映射和双线性d i f f i e h e ii m a n 问题1 3 2 8 椭圆曲线上的离散对数问题1 3 2 9 本章小结1 4 3 数字签名 1 5 3 1 数字签名基本概念1 5 3 2 数字签名的一般组成。1 5 3 3 数字签名的安全性1 5 3 4 数字签名的研究现状1 6 3 5 几种常用的数字签名方案1 7 3 5 1r s a 签名体制1 8 3 5 2e ib mi 签名体制1 8 3 5 3d s s 签名体制1 9 3 6 几种特殊的数字签名加 3 6 1 基于身份的数字签名方案加 3 6 2 指定验证者数字签名方案。2 1 3 6 3 盲签名方案2 3 3 7 本章小结2 4 4 代理数字签名方案 4 1 弓l 盲2 5 4 2 代理数字签名的研究状况2 5 4 3 代理数字签名的定义。2 5 4 4 代理签名的安全性。2 6 4 5 代理签名的分类。2 7 4 6 几种典型的代理签名方案及其分析。勰 4 8 1m - u - o 代理签名方案。勰 西安理工大学硕士学位论文 4 6 2y - b 代理签名方案。2 9 4 6 3s u n 代理签名方案。3 0 4 6 4d y d 指定验证者代理签名方案3 2 4 6 5h a i r 代理保护盲签名方案3 3 4 7 本章小结3 4 5 基于身份的指定验证者代理签名方案 3 5 5 1 方案中的参数3 5 5 2 方案的实现过程。3 5 5 3 方案的安全性分析3 7 5 4 本章小结3 8 6 代理言签名方案3 9 6 1 改进方案3 9 6 2 椭圆曲线上的代理盲签名方案4 0 6 4 本章小结。4 1 7 结论 4 2 7 1 主要研究成果4 2 7 2 展望4 2 致谢 附录 4 4 4 9 ； 第一幸绪论 1 绪论 当今社会已进入信息化时代，计算机和通信技术的发展，使计算机网络已逐渐用于社 会生活的各个领域，伴随着信息化进程的推进和电子商务等网络新业务的兴起，整个社会 对计算机网络的依赖程度越来越高。计算机网络和信息系统的应用给人们带来了前所未有 的方便，大大地提高了劳动生产率，给社会带来了无限的商机与财富。 然而，互联网是个开放的环境，计算机网络在给整个社会带来便利的同时，也带来了 极大的安全威胁。网络上各种不安全因素的存在( 网络攻击、网络欺诈、网络犯罪) ，使 人们面临着如何进行安全信息交换的巨大挑战，先进的信息安全技术是网络安全的根本保 证。随着计算机网络的广泛应用，信息的安全问题也越来越受到人们重视，信息安全的重 要性也日渐突出，信息安全已经成为国家、国防及国民经济的重要组成部分。 在开放的网络环境下，主要的信息安全威胁有以下几个方面： 窃取：非法用户通过数据窃听的手段获得敏感信息。截取：非法用户首先获得信息， 再将此信息发送给真实接收者。伪造：将伪造的信息发送给接收者。篡改：非法用户对合 法用户之间的通讯信息进行修改，再发送给接收者。拒绝服务攻击：攻击服务系统，造成 系统瘫痪，阻止合法用户获得服务。行为否认：合法用户否认已经发生的行为。非授权访 问：未经系统授权而使用网络或计算机资源。传播病毒：通过网络传播计算机病毒，其破 坏性非常高，而且用户很难防范。 为了避免以上的安全威胁，信息安全技术的目标1 1 主要实现真实性、机密性、完整 性、可用性、不可否认性、可控制性和可审查性。真实性主要是指对信息的来源进行判断， 能对伪造来源的信息予以鉴别。机密性保证机密信息不被窃听，或窃听者不能了解信息的 真实含义。完整性用来保证数据的一致性，防止数据被非法用户篡改。可用性是保证合法 用户对信息和资源的使用不会被不正当地拒绝。不可否认性是指建立有效的责任机制，防 止用户否认其行为，这一点在电子商务中是极其重要的。可控制性是对信息的传播及内容 具有控制能力。可审查性用于对出现的网络安全问题提供调查的依据和手段。 1 1 引言 随着社会信息化步伐的加快，利用计算机技术、网络通信技术和i n t e r n e t 实现商务 活动的国际化、信息化和无纸化，已成为全球商务发展的趋势。电子商务以i n t e r n e t 为 基础，可以提供跨国、多种语言、多种货币的在线服务( 包括银行、保险、旅游、购物) ， 还可以提供包括产品寻求、讨价还价、作出决定、支付、送货及解决纠纷等全面的商业交 易服务。特别是信息产品还可以直接在线递送，从而大大降低了交易费用。成本低、及时 性和互通性好，以及在拓展市场等方面的优势，使得电子商务受到全球的广泛关注。但是， 由于i n t e r n e t 的全球性、开放性、无缝连通性、共享性、动态性发展，使得任何人都可 西安理工大学硕士学位论文 以自由地接入i n t e r n e t ，从而导致了网络的安全性受到严重影响，在开放的i n t e r n e t 平 台上，社会生活中传统的犯罪和不道德行为将变得更加隐蔽和难以控制。人们从面对面的 交易和作业，变成网上互不见面的操作、没有国界、没有时间限制，就产生了更大的安全 隐患。因此，在电子商务的发展热潮中，电子商务的安全性已成为制约电子商务发展的重 要瓶颈。 如何保证网上传输的数据的安全和交易对方的身份真实性是电子商务是否能够得到 推广的关键，可以说电子商务最关键的问题是安全性问题。 建立在现代数学理论之上的密码学就是专门用来解决信息安全问题的。数字签名 ( d i g i t a ls i g n a t u r e s ) 技术是现在密码学中的重要技术，是数据交换的完整性、发送信息 的不可否认性、交易者身份的确定性的一种有效的解决方案。它可以提供有力的证据，表 明自从数据被签名以来数据尚未发生更改，并且它可以用来验证签名者的身份。数字签名 ( d i g i t a ls i g n a t u r e s ) 实现了完整性和认证性这两项重要的安全功能，而这是实施安全电 子商务的基本要求。数字签名( d i g i t a ls i g n a t u r e s ) 可以解决信息安全的多方面的问题， 他在包括身份认证、数据完整性、不可否认性以及匿名性等方面都有重要应用，特别是在 大型网络安全通信中的密钥分配、认证以及电子商务系统中具有重要作用。 1 2 密码学概述 密码学是用来解决信息安全问题的一门科学。它主要包括两个分支，即密码编码学和 密码分析学。密码编码学的主要目的是寻求保证消息保密性或认证性的方法。密码分析学 的主要目的是研究加密消息的破译或消息的伪造。 密码学的发展历史可大致划分为三个阶段：1 ) 1 9 4 9 年以前是科学密码学的前夜时期， 这个时期的密码学专家常常是凭直觉和信念来进行密码设计和分析，而不是靠推理证明： 2 ) 1 9 4 9 年s h a n n o n 发表的“保密系统的信息理论 一文为私钥密码系统建立了理论基础， 从此密码学成为一门科学；3 ) 1 9 7 6 年d i f f i e 和h e l l m a n 在( n e wd i r e c t i o n si n c r y p t o g r a p h y ) 2 1 一文中首次提出了“公开密钥密码体制一，导致了密码学上的一场革命， 同时r m e r k l e 于1 9 7 8 年也独立提出了r s a 公钥密码体制，这一体制的出现在密码史上是 个划时代的时间，它为解决计算机信息网络中的安全提供了新的理论和技术基础。 密码学的分类：根据密钥的特点将密码体制分为对称和非对称( 公钥) 密码体制两 种。对称密码体制中加密密钥和解密密钥是一样的或者彼此之间是容易相互确定的( 图 1 1 ) 。主要的对称密码有d e s 和a e s 。公钥密码体制是采用两个不同但相互之间存在关系 的密钥进行加密和解密( 图1 2 ) ，其中一个密钥是可以公开的，称为公钥：另一个密钥 保密，称为私钥。这种体制有两种工作模式：1 ) 发送实体用公钥作为密码运算的输入得 到秘密信息：接受实体用私钥恢复发送实体所产生的秘密信息，私钥能且只能恢复相应的 公钥产生的秘密信息。这种工作模式用于保密通信。2 ) 发送实体用私钥作为密码运算的 输入得到秘密信息；接受实体用公钥恢复发送实体所产生的秘密信息，公钥能且只能恢复 2 f 第一章绪论 相应的私钥产生的秘密信息。这种工作模式用于数字签名。就加密而言，前者以公钥作为 加密密钥，以用户私钥作为解密密钥，则可实现多个用户加密的消息只能由一个用户解读； 反之，后者以用户私钥作为加密密钥而以公钥作为解密密钥，则可实现由一个用户加密的 消息使多个用户解读。 常用的密码分析攻击有四类： ( 1 ) 唯密文攻击密码分析者有一些消息的密文，这些消息都用同一加密算法加密。 密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便 可采用相同的密钥解出其他被加密的消息。 ( 2 ) 已知明文攻击密码分析者不仅可得到一些消息的密文，而且也知道这些消息 的明文。分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可以 对用同一密钥加密的任何新的消息进行解密。 ( 3 ) 选择明文攻击分析者不仅可得到一些消息的密文和相应的明文，而且他们也 可以选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定的明文块 去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密钥 或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。 ”。一? 。 ( 4 ) 自适应选择明文攻击这是选择明文攻击的特殊情况。密码分析者不仅能选择 被加密的明文，而且也能基于以前加密的结果修正这个选择。在选择明文攻击中，密码分 析者还可以选择一大块被加了密的明文。而在自适应选择密文攻击中，他可选取较小的明 文块，然后再基于第一块的结果选择另一明文块，以此类推。 根据密码的两种分类，对称密码和非对称密码。相应的数字签名也分为两种。但是利 用对称密码实现的数字签名除了文件签字者和文件接受者双方，还需要第三方认证，比较 麻烦。而相比于用对称密码的实现，利用非对称密码实现数字签名更为合适。由公钥密码 体制的第2 中工作模式看出，这种模式适用于数字签名的构造。因为，同一个实体产生的 多个签名应该能被不同的接收实体所验证，这是签名的基本要求所以可以总结数字签名 的基本模式：首先，需要选择系统所要求的密码参数，初始化系统，确定系统中签名的公 开钥y 和签名者的秘密钥s ；其次，要有一个签名计算算法6 - s z g ( s ，朋) ，其中m 是要签 署的消息，s i g ( - ) 是签名算法，6 是消息m 的签名：最后，存在一个签名验证算法v e r ( 6 ，n ， 对正确的签名6 ，算法附( ) 输出t u r e ，对非法签名输出f a l s e 。 图1 - 1 非对称密码的加解密 ( p i c l 一1a s y m m c u - i ct e c h n i q u e se n c r y p t i o n e e c o p f i o n ) 3 西安理工大学硕士学位论文 图卜2 对称密码的；o n 解密 ( p i c 3 1 s y m m e t r i ct e c h n i q u e se n c r y p t i o n d e c r y p t i o n ) 1 3 数字签名简介 数字签名作为密码学中重要的组成部分之一，是信息完整性、真实性的理论基础，它 可以保证信息传输的保密性、数据交换的完整性、发送信息的不可否认性以及交易者身份 的确定性。在当今的计算机网络通信时代，用密码学的方法实现数字签名显然有重要的实 际意义。政治、军事、外交等的文件、命令和条约，商业中的契约以及个人之间的书信等， 传统上采用手写签名或印章，以便于在法律上能认证、核准、生效。随着计算机通信网的 发展，人们希望通过电子设备实现快速、远距离的交易，因此在数字系统中同样有签名应 用的需要，如假定a 发送一个认证的信息给b ，如果没有签名确认的措施，b 可能伪造一 个不同的消息，但声称是从a 收到的；或者为了某种目的，a 也可能否认发送过该消息。 很明显，数字系统的特点决定了不可能再沿用原先的手写签名方法来实现防伪造或抵赖， 这就提出了如何实现数字签名的问题。 数字签名就是通过一个单向函数对要传送的报文进行处理得到的用以认证报文来源 并核实报文是否发生变化的一个字母数字串。用这几个字符串来代替手写签名或印章，起 到与手写签名或印章同样的法律效用。数字签名是电子信息技术发展的产物，是针对电子 文档的一种签名确认方法，所要达到的目的是：对数字对象的合法性、真实性进行标记， 并提供签名者的承诺。 具体说来，数字签名( d i g i t a ls i g n a t u r e s ) 主要包括以下四部分： ( 1 ) 被发送文件采用哈希算法对原始报文进行运算，得到一个固定长度的数字串， 称为报文摘要( m e s s a g ed i g e s t ) ，不同的报文所得到的报文摘要各异，但对相同的报文 它的报文摘要却是唯一的。 ( 2 ) 发送方生成报文的报文摘要，用自己的私钥对摘要进行加密来形成发送方的数 字签名。 ( 3 ) 这个数字签名将作为报文的附件和报文一起发送给接收方。 ( 4 ) 接收方首先从接收到的原始报文中用同样的算法计算出新的报文摘要，再用发 送方的公钥对报文附件的数字签名进行解密，比较两个报文摘要，如果值相同，接收方就 能确认该数字签名是发送方的。 目前主要是基于公钥密码体制的数字签名。包括普通数字签名和特殊数字签名。普通 4 ， 第一章绪论 数字签名算法有r s a 、e i g a m a l 、f i a t s h a m i r 、g u i l l o u q u i s q u a r t e r 、s c h n o r r 、 o n g - s c h n o r r s h a m i r 5 1 数字签名算法、d e s d s a ，椭圆曲线数字签名算法和有限自动机数 字签名算法等。特殊数字签名有代理签名、指定验证者签名、盲签名、群签名、不可否认 签名、公平盲签名、门限签名、具有消息恢复功能的签名等，它们与具体应用环境密切相 关。 随着信息技术的广泛使用，特别是电子商务、电子政务等的快速发展，数字签名的应 用需求越来越大。国际社会已开始制定相应的法律、法规，把数字签名作为执法的依据。 数字签名是对手写签名的模拟。分析手写签名的特点，一个数字签名方案至少要满足以下 三个条件： 不可否认性：签名者事后不能否认做过签名。 不可伪造性：其他人不能伪造签名。 可仲裁性：当双方对一个签名的真实性发生争执时，第三方应能解决争执。 数字签名同手写签名相比，具有巨大的优势。手写签名由于是模拟的，它因人而异，因 此很容易被人仿造，当收发双方一旦出现争端，第三方不容易仲裁：而数字签名是由o 和1 组成的数字串，它因消息而异，而且当收发双方出现争端时，它能给仲裁者提供足够的证据 来进行裁决，因此其安全性远远高于前者。此外，数字签名依托于计算机网络，因此其时效 性远远大于前者。 数字签名是指附加在数据单元上的一些数据，或是对数据单元所做的密码变换，这种 数据或变换可被接收者用以确认其来源和完整性，并保护数据不被他人伪造。从动态过程 ( 图3 1 ) 看，数字签名技术就是利用数据加解密技术、数据变换技术，根据某种协议来 产生一个反映被签署文件和签署人特性的数字化签名。数字签名涉及被签署文件和签署人 两个主体，密码技术是数字签名的技术基础。 一个安全有效的数字签名方案必须满足以下要求： ( 1 ) 签名是可信的：签名使文件的接收者相信签名者慎重签署了该文件。 ( 2 ) 签名是不能伪造的：签名能证明是签名者本人而不是别人签署了该文件。 ( 3 ) 签名是不能重用的：签名是文件的一部分，任何人不能将该签名移到别的文件上。 ( 4 ) 签名后的文件是不能更改的：文件签名以后，不能对文件进行更改。 ( 5 ) 签名是不能否认的：签名及文件是客观存在的，签名者不能事后称他或者她没有 签过字。 现今的数字签名技术以密码理论为基础，其核心是采用加密技术的加解密算法来实现 对报文的数字签名。但数字签名和加密有所不同，加密是为了防止信息被非法读取，而数 字签名是为了使接收者确信信息的发送者身份及信息是否被篡改。信息的加解密很可能是 次性的，而数字签名的验证可能进行多次。因此数字签名有不可伪造性的要求，安全性 的要求也更高。目前数字签名的研究主要集中在基于公钥密码体制中的数字签名的研究。 数字签名在身份认证、数据完整性保护、信息不可否认性以及匿名性等信息安全领域都有 5 西安理工大学硕士学位论文 重要的用途；在网络安全通信、电子商务系统的密钥分配、用户认证等过程中，数字签名 都有重要作用。 1 4 代理数字签名 数字签名作为认证的主要手段，在现代密码学中具有重要的地位，在信息安全领域具 有广泛的应用。在实际应用中，不同场景具有不同的安全需求，因而对数字签名也有不同 的应用需求，随着数字签名技术在密码学和信息安全的应用领域的不断扩大，涌现出各种 具有特殊性质的数字签名技术，如群签名、环签名、盲签名、代理签名、指定验证者签名 等等。其中，代理数字签名是一种让代理签名者代表原始签名者对消息进行签名的数字签 名。 1 5 本文的研究内容及其科学意义 本文对基于身份的数字签名、指定验证者数字签名和盲数字签名研究的基础上，重点 研究了代理数字签名。其中，基于身份的数字签名可以简化传统公钥密码对密钥的管理； 指定验证者数字签名在电子商务、电子政务中有很多用途，它可以有效地解决认证性和隐 私性的冲突；盲数字签名在数字现金，电子投票等领域都有较大的应用价值，它可以保护 签名者的签名信息；代理签名可以使得代理签名人去代表原始签名者去行使一些签名权 利，它在权利委托方面有重要应用。本文结合上边这些签名方案，利用已经有的数学知识， 构造新的签名方案，其中基于身份的指定验证者签名方案，克服了文献【5 】和【6 】中 提出的指定验证者代理签名方案的缺点，并且满足文献【5 ，6 】提出的指定验证者代理签 名方案应该满足的安全性要求，它在权利委托，电子商务中有很好应用。代理盲签名方案 克服了文献【7 】中的缺点，并且在椭圆曲线上实现了改进方案，继承了椭圆曲线密码系 统具有密钥短、速度快、安全性高的优点。 1 6 本文的章节安排 第l 章阐明了数字签名的产生背景和现实意义；概述了密码学和数字签名的基本概念 原理和要求； 第2 章研究了密码学中需要的基本数学理论。包括代数群、哈希函数、数论中困难问 题和密码学中常用数论假设； 第3 章对数字签名做了系统的介绍，分析了几种不同的数字签名方案，并做了总结， 6 第一章绪论 指出了各自存在的缺陷。 第4 章介绍了代理签名方案，并对几个有代表性的代理签名作了分析。 第5 章构造了一个基于身份的指定验证者代理签名方案，证明了新方案的安全性。新 方案具有基于身份的特性，并把指定验证者签名和代理签名相结合，在现实中有很好的 应用。 第6 章对a m i t 代理保护盲签名方案进行改进，克服了原方案中存在的安全缺点。同 时构造了一个基于椭圆曲线的代理保护盲签名方案。 7 西安理工大学硕士学位论文 2 数学理论 数字签名是现代密码学的一个重要组成部分，是公钥密码学的重要应用之一，现今已 发展成为一个独立的研究体系，其研究内容涉及到数论、概率论、信息论、计算复杂性理 论、代数学等多方面的知识。现今大部分的数字签名都是基于一些计算性困难问题( 如离 散对数问题、大数分解问题、计算性d i f f i e h e l l m a n 问题) 而提出的，这些困难问题的 直接理论基础是一些数学困难问题。本章将介绍和数字签名有关基础数学理论知识。 2 1 整数因子分解问题 定义2 1 8 1 整数因子分解问题：给定整数刀，对n 进行因子分解 只是不同的素数，e j 是正整数。 在现有计算能力下，已知若干不同的素数p ，p ：，p 。，求这些素数的乘积 n - p 。p ：p k 计算上是容易的，是一个多项式时间算法；但是反之，已知，求 其素因子却是困难的，目前没有多项式时间算法可以求解。由整数分解问题我们引出了 整数分解困难性假设。 假设2 1 整数分解假设：存在多项式时间算法k ，使得以1 为输入，输出2 k b i t 长的合数n p q ，其中p 和g 为k b i t 长随机奇素数。但对任何多项式时间算法a 和 安全参数k ，对任何充分大的参数k ，其成功解决整数分解问题的概率是可忽略的。 r 11 即：p r o b p ，q - 彳似矿) ) j = 击，其中p ( ) 为任一多项式。 2 2 离散对数问题 定义2 2 1 离散对数：设g 是一个有限循环群且g 是g 的一个生成元。元素a g 的离散对数是指唯一的整数x ( o szqg d ，使得a - g j 成立。记为工一l o g ，a 。 若g 不是生成元，口基于g 的离散对数( 若存在) 是指最小的正整数z 使a g i l lg j 成立。 定义2 3n 1 离散对数问题( 简称d l p ) 给定素数p 及z 。的两个独立的生成元 口，z 。；求卢关于口的离散对数。也就是说，要在l o ，p 一2 i 中找出使下式惟一成立 的整数工：卢- 口。m o d p 在现有计算能力下，已知口和x 计算出卢一口互m o d p 是容易的，是一个多项式时间 算法，但是反之已知拥卢求解整数x 使得卢- 口工m o d p 在计算上是困难的，没有多项 式时间算法可解。由离散对数问题引出离散对数假设。 假设2 2 离散对数假设( 简称d l a ) ：存在多项式时间算法k ，其以1 为输入，输出 k b i t 长大素数p 和g ，其中g 为z 。的生成元；对任何多项式时间算法a 和安全参数k ， 对任何充分大的参数k ，其成功解决离散对数问题的概率是可忽略的，即 8 第二章数学理论 t p r 。6 k 一彳( k 旷) ) 】 1 ， r e 满足g c d ( e ，q 一琐口一1 ) ) - 1 ，求解模万下z 的e 次根，即求得“e g 满足z h ( m o d n ) ， 这就是r s a 问题。 假设2 3r s a 假设：存在概率多项式时间算法k 对于输入安全参数z g ，输出满足r s a 问题要求的条件0 ，z ，e ) ；对所有概率多项式时间算法p ，算法p 解决r s a 问题的概率可以 忽略。即： 1 p r z - m 。i ( 刀，z ，e ) ik ( 2 k ) ，“- p ( n ，z ，e ) 】 1 ，这就是强r s a 问题。 假设2 4 强r s a 假设：存在概率多项式时间算法k 对于输入安全参数如，输出满足 强r s a 问题要求的条件o ，z ) ；对所有概率多项式时间算法p ，算法p 解决强r s a 问题的概 率可以忽略。即： 1 p r z - 口i ( 疗，z ) ：- k ( 2 k ) ，o ，e ) ：一p ( n ，z ) 1 去， p v o 其中，p ( ) 为任一多项式，乞是安全参数。 仔细分析可以发现，r s a 假设的安全性基础是大数的因子分解，如果能够分解万， 求解r s a 问题中的指数e 的逆元是很容易的，从而r s a 问题迎刃而解。进而比较r s a 问题和强r s a 问题给出的条件的强弱：r s a 问题给定了指数e ，而强r s a 问题则没有， 也就是说强r s a 问题只要求找到满足条件的数对o ，e ) 就可以了，那么强r s a 问题对求 解者来讲要求降低了。那么有结论：如果密码系统在强r s a 假设下安全，则在r s a 假 设下一定也是安全的；如果密码系统在r s a 假设下安全，则在强r s a 假设下不一定是 安全的。即，证明某个系统在强r s a 假设下安全就足够了。 9 西安理工大学硕士学位论文 2 4dif fie - h ei im a n 问题幂口dif fie - h eiim a n 假设 d i f f i e h e l l m a n 假设有两种类型：( 1 ) 计算性d i f f i e h e l i m a n 假设( c d h ) ：( 2 ) 判定性d i f f i e - h e l l m a n 假设( d d h ) 。 定义2 6 1 ：计算性d i f f h e l i m a n 问题( 简称c d h ) ：设p 为素数，g 为z 。的生 成元。给出g z p ，g y z p ( 其中z ，y e 1 , p 一1 是未知的) ，要求计算g 舯。 由计算性d i f f i e - h e l l m a n 问题引出计算性d i f f i e - h e l l m a n 假设： 假设2 5 ：计算性d i f f i e - h e l l m a n 假设( 简称c d a ) ：存在多项式时间算法k ，其 以1 为输入，输出k - b i t 长大素数p 和g ，g 。，g ，其中g 为z p 的生成元，g ( e z p ， g y ( e z 。；对任何多项式时间算法a ，对任何充分大的参数七，其成功解决c d h 问题的 ，11 概率是可忽略的，即：p r o b g 秽卜a ( k o ) ) j = 击，p ( ) 为任一多项式，乞是安全参 p v g ) 数。 定义2 7n ：判定性d i f f i e - h e l l m a n 问题( 简称d d h ) z 设p 为素数，g 为z 。的 生成元。给出g 。z p ，g y z p ，g 。z ，( 其e e x ，y ，z e 1 , p 一1 】是未知的) 要求判定 g 卅与9 2 是否相等。 由判定性d i f f i e h e l l m a n 问题引出判定性d i f f i e h e l l m a n 假设： 假设2 6 ：判定性d i f f i e h e l l m a n 假设( 简称d d a ) ：存在多项式时间算法k ，其 以r 为输入，输出七一b i t 长大素数p 和g ，g ，g y ，g 。，其中g 为z p 的生成元，g 。z p ， g y z p 。，g 。e z p ：对任何多项式时间算法a ，对任何充分大的参数k ，其成功解决 r，11 d d h 问题的概率是可忽略的，即：p r o b l g 夥一g 。- 么僻旷) ) i _ 击，p ( ) 为任一多项 ljp t t o ) 式，如是安全参数。 明显地，d d h 假设中蕴含着c d h 假设，也就是说d d h 假设比c d h 假设更强。事实 上，存在着这样的群，在它们中d d h 假设明显不成立，但是c d h 假设依然具有说服力。 即使这样，依然存在使得人们相信d d h 假设成立的群，经典的例子就是：z ：中的阶为 ，的循环子群，其中s 一2 r + 1 ，s 和，都是大素数( 也就是安全素数) 。 2 5 二次剩余问题 设m 为大于1 的整数，且g c d ( a ，历) - 1 ，若z 2 一口( m o d m ) 有解，则称a 是模m 的二次 剩余，否则称为m 的二次非剩余。二次剩余和二次非剩余的集合分别记为： 飒和煅 若m 的因子分解己知，容易判定一个元素是否是模m 的二次剩余。而当m 的因子 分解未知时，判定一个元素是否是模m 的二次剩余是一个困难性问题。 定义2 8 “o 二次剩余问题：给定整数万和口，( 0sa ，先计算h ) ， 并按下式验证： v e r ( p k ，h 伽) ，仃) 一真尊y 7 ，口i g 似磁m o d p ，这是因为 y 7 r 口ig = g 荫ig 晴+ t ) m o d p 由上式有( 肛+ 础) ih ( m ) m o d ( p 一1 ) 故有y 7 ，口ig 圩( 刖m o d p 在此方案中，对同一消 息小，由于随机数k 不同而有不同的签字值s 一( 厂0 盯) 。 显然e i g a m a l 签名的安全性基于求解离散对数问题苦难性。对手无法由签名公钥推 算出签名秘密钥。但是若对手得到签名时签名者选择的随机数七，即可得到秘密钥x ( 求 解一元一次方程) ，进而破解系统。同时如果在两个不同消息签名时选用同一个随机数 k ，通过求解两个二元一次方程组成的方程组求出秘密钥x ，系统也可破，所以系统中 伪随机生成器要足够安全。 3 5 3d s s 签名体制 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 ) 是s c h n o r r 和e i g a m a l 签名算法的变种，被美 国n i s t 作为d s s ( d i g i t a ls i g n a t u r es t a n d a r d ) 数字签名标准，并成为第一个经过各 国政府验证的数字签名方案。d s a 是e i g a m a l 签名方案的变种，它使用了安全哈希函数( s h a - - i ) 。 ( 1 ) 系统生成 每个实体a 进行以下操作： a 随机选择大素数口，2 1 卵口2 瑚； b 选择f ，0 st 8 ，素数p ，2 s 1 , 瑚p 2 m + 阳，g q i ( p 一1 ) ； p c 选择元素g z ：，并计算口i g ( ，1 m o d p ，若口- 1 ，则重新选择g ； d 选择随机数a ，1 口口一1l e 计算yi 口。m o d p 则a 的公钥为( p ，口，口，y ) ，私钥为a ( 2 ) 签名生成： a 选择随机数七，0 七q ： b 计算，- 口im o d p m o d q ； c 计算七一m o d q ； d 计算si 七以 i i l 伽) + a r m o d ql e 历的签名为( ，s ) 。 ( 3 ) 签名验证： a 验证0 ，口和0 墨q ，若不满足则拒绝； b 计算w i s 1 m o d