（应用数学专业论文）指定验证者签名和变色龙签名的研究及应用.pdf

摘要 论文题目：指定验证者签名和变色龙签名的研究及应用 学科专业：应用数学 研究生：赵男 指导教师：王尚平教授 摘要 签名： 签名： 数字签名机制作为保障网络信息安全的主要手段之一，已成为信息安全科学领域一个 重要的研究热点。论文主要研究了指定验证者签名方案及其应用，分析了现有指定验证者 签名方案的优缺点，提出了一个新的指定验证者签名方案；对变色龙签名进行了初步研究， 提出了一个改进方案。主要研究成果如下： 1 指出了w i l l ys u s i l o 等提出的基于身份的强指定验证者签名方案的安全性证明存 在缺陷，对该方案的安全性给出了新的证明。并在此基础上提出了一个新的可恢复的基于 身份的强指定验证者签名方案，适用于在对隐私性和认证性要求良好协调并且带宽受限的 环境对短消息进行签名。 2 变色龙签名体制是基于传统的哈希签名范例的，但它使用的哈希函数比较特别， 叫做c h a m e l e o nh a s h ，正由于这种特殊的h a s h 函数，变色龙签名体制具备非交互性、不 可传递性和不可否认性等优良特性。利用双线性对，提出一个新的基于身份的变色龙签名， 在随机预言机下是安全的。 关键词：数字签名：指定验证者；变色龙哈希；基于身份 基金资助： 国家自然科学基金( 6 0 2 7 3 鹏9 ) 陕西省教育厅自然科学研究计划资助项目( 0 3 j k l 6 5 1 0 蚰2 0 3 1 3 ) 西安理工大学科技创新基金( 1 0 8 2 1 0 4 0 2 ) 陕西省自然科学基础研究计划项目( 2 0 0 5 f 0 2 1 0 8 - 2 2 0 6 ) 陕西省教育厅专项科学研究计划资助项目( 0 6 j k 2 1 3 ) 国际合作项目( 日本) 京通株式会社( 1 0 8 - 2 3 0 5 0 1 ) 企业项目( 西安) 西安瑞日电子发展有限公司( 1 0 8 _ 2 3 0 5 0 8 ) 筠 t i t l e ：r e s e a r c ho nd e s i g n a l - e dv e r i f i e rs i g n a t u r e s a n dc h a m e l e o ns i g n a t u r e s 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 ：n a nz h a o 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 g a b s t r a c t s i g n a t u r e ： s i g n a t u r e ： ”可 d i g i t a ls i g n a t u r e , a se r i co ft h em o s tp r i m a r ym e t h o d so fp r o t e c t i n gi n f o r m a t i o ns e c u r i t y , h a sb e c o m ean 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 n 辩删t y t h ef o c u so ft h i st h e s i si s a n a l y z i n gt h ed 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 sa n di t sa p p l i a n c e s , an o wd e s i g n a t e dv e r i f i e r s i g n a t u r e ss c h e m ei sp r e s e n t e d ；a tt h es a m et i m e ，c h a m e l e o ns i g n a t u r e sa r ee l e m e n t a r i l y r e s e a r c h e da n dap r o m o v e ds c h e m ei sp r e s e n t e d t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s 1 a st h e r ej ss o n i co b j e c t i o na b o u tt h es c c u r i t ya t t e s t a t i o no ft h es c h e m ep r o p o s e db yw i l l y s u s i l o 。e t e 。a n o t h e rm e t h o dt o a t t e s ti sg i v e ni nt h i sp a p e r b a s e do nt h e n e wa t t e s t a t i o n , a l l i d - b a s e ds t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r es c h e m ew i t hm e s s a g er e c o v e r yi sp r o p o s e dw h i c h a d a p t sf o rs i g n i n gs h o r tm e s s a g ew i t hh i g hh a r m o n yr e q u i r e m e n to fp r i v a c ya n da u t h e n t i c a t i o n a n dl i m i t e db 纽d 、i d t h 2 c h a m e l e o ns g n a t u r ei sb a s e do nt r a d i t i o n a lh a s ha n ds i g np a r a d i g m , b a tw h a tm a k e si t d i 伍o rf r o mt h eo r d i 删3 , s i g n a t u r e si st h eh a s hf u n c t i o ni tu s e d - c h a m e l e o nh a s h as e c l l r e c h a m e l e o ns c h e m ep r o v i d e st h e p r o p e r t i e s o f n o n - i n t e r a c t i o n , n o n - t r a n s f e r a b i l i t y a n d n o n - r e p u d i a t i o n an e wi d - b a s e dc h a m e l e o ns i g n a t u r es c h e m ei sp m p o s e d i nt h i sp a p e rw h i c h i sb a s e do nt h eb i l i n e a rp a i r i n g s i t ss e c u r cu n d e rr a n d o mo r a c 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 ：d e s i g n a t e dv e r i f i e r ；c h a m e l e o nh a s h ：i d - b a s c d 警 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名：墨聃 学位论文使用授权声明 月拍日 本人二钮：皂在导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为教学和 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) 论文作者签名：兰纭嘉 导师签名：妇a 汨 第一章绪论 1 绪论 信息技术的蓬勃发展，使得信息的流通与存取更为快速和便捷。计算机网络的广泛应 用，缩短了人与人之间的距离，淡化了国与国之间的界限。但相随地却也激起了人们的某 种危机意识，那就是当人们可以很方便地通过计算机网络，到处获取连接在网络上各部计 算机的信息同时，存储在计算机内部的机密信息该如何保护? 再者，一些重要的机密信息 在众目睽睽的计算机网络上流通时，我们应该怎么做才不至于让这些信息轻易曝光，而让 信息的拥有者免于蒙受无法弥补之重大损失。近年来，计算机密码学愈来愈受到世界各国 重视，而密码技术的发展更如雨后春笋一般，其应用已跨越了国防军事与商业，在可以预 见的将来，密码技术必然与个人的信息保密息息相关。 1 1 前言 1 1 1 信息安全 信息无所不在，无所不有。信息作为广义的概念，越来越被习惯地理解为：人类在认 识世界和改造世界过程中获取的各种数据、消息和知识，以及各种事物间运动差异表现出 来的不同状态和方式。通俗地讲，信息指的就是数据、消息和资讯等一类概念。 当今社会，信息越来越重要。信息不仅是一种宝贵的智力资源，同时也是每个国家重 要的战略资源。信息作为一种传播载体和可利用资源，已经深入人心。随着社会的进步发 展和不同社会的差异变化，使原本属于中性的“信息”概念，也逐渐显现出它的公开性和 保密性两个最基本的主要特征。信息的公开性概念反映出信息的传播属性范围，哪些信息 属公众信息，哪些信息属内部信息。公众信息一般理解为非保密的，内部信息通常理解为 带有保密性的。当然，公众信息也并非不具有保密安全性，公众信息和内部信息在某些特 定场合和范围也是有所界定的。比如，在报纸上登载一个工程师的特长档案信息没什么值 得大惊小怪，但若公开一个单位、一个系统、一个区域、一个省的整体工程师的特长档案 信息那是非常有价值的。信息的安全性强调信息保密的安全程度，一般地说，内部信息要 求具有保密性或安全性信息的保密性和安全性就是人们通常所说的“信息安全”的属性 范围的概念 何谓“信息安全”? 其实，它指的就是在网络环境下信息系统中的数据受到指定保护， 不因偶然和恶意的原因而遭到破坏、更改、泄露。使信息系统能连续、可靠、正常的运行， 或因破坏后还能迅速恢复正常使用的安全过程。信息安全反映出有用信息本身实用价 值以及收集、存储、传送、交换、加工处理过程中的保密程度要求信息安全也说明信息 本身价值的安全和信息技术安全两个层面。只要信息属于个人、企业、国家的使用价值范 围，以及它的保护外延型，就说明信息本身需要保护安全性。其次，对保护信息对象的操 作，不论是具体的信息内容，还是特定的信息系统，都需要信息安全技术来保证。对国家 西安理工大学项士学位论文 而言，信息安全就是确保社会信息化状态和信息技术体系不受外来侵袭和破坏。 在网络发展的今天，共享信息成为一种基本需求。信息安全实质上主要体现为网络信 息安全，这使得信息安全的概念所赋予的范围更广，内容更丰富，系统更复杂。因此，网 络上的信息安全从个人财产档案信息、企业的商业机密到国家信息化建设( 包括国防信息 现代化建设) 等等相关的信息安全内容都至关重要。忽略信息安全问题，只把安全机制建 立在物理安全机制上是远远不够的尤其对于国家来说，信息安全事关大局，切不可掉以 轻心。 由于计算机网络技术的飞速发展，依赖计算机网络系统完成传送、存储和处理信息的 作用明显加强。网上银行，网上市场，网上电子商务、网上电子政务等形式层出不穷。网 上数据流、信息流和资金流已成为当今网络世界不可缺少的主要部分。随之而来的网络信 息安全问题也更加突出保证信息安全，最根本的就是保证信息安全的基本特征发挥作用 信息安全的五大特征包括：( 1 ) 完整性( i n t e g r i t y ) 它指信息在传输、交换、存储和处理 过程保持非修改、非破坏和非丢失的特性，即保持信息原样性，使信息能够正确生成、存 储、传输，这是最基本的安全特征( 2 ) 保密性( c o n f i d e n t i a l i t y ) 它指信息按给定要求不 泄露给非授权的个人、实体或过程，或提供其利用的特性，即杜绝有用信息泄露给非授权 个人或实体，强调有用信息只为授权对象使用的特性。( 3 ) 可用性( a v a i l a b i l i t y ) 它指网 络信息可被授权实体正确访问，并按要求能正常使用或在非正常情况下能恢复使用的特 征，即在系统运行时能正确存取所需信息，当系统遭受攻击或破坏时，能迅速恢复并能投 入使用。可用性是衡量网络信息系统面向用户的一种安全性能。( 4 ) 不可否认性 ( n o n r e p u d i a t i o n ) 它指通信双方在信息交互过程中，确信参与者本身，以及参与者所提 供的信息的真实同一性，即所有参与者都不能否认或抵赖本人的真实身份，以及提供信息 的原样性和完成的操作与承诺。( 5 ) 可控性( c o n t r o l l a b i l i t y ) 它指对流通在网络系统中的 信息传播及具体的内容能够实现有效控制的特性，即网络中的任何信息要在一定传输范围 和存放空间内可控除了采用常规的传播站点和传播内容监控这种形式外，最典型的如密 码的托管政策。当加密算法交由第三方( 或任何方) 管理时，必须严格按规定可控执行。 1 1 2 网络信息安全与密码学 在网络信息安全基本特征中关键的问题是保密性。确保信息的保密安全，主要是使用 密码技术，因为密码技术是信息安全技术中的核心技术，它推进和加速了密码学理论的发 展。 密码学( c r y p t o l o g y ) 是研究信息系统安全保密的- - f l 科学其主要内容包括两个方 面：密码编码学( c r y p t o g r a p h y ) 和密码分析学( c r y p t a n a l y t i c s ) 。密码编码学是对信息进 行编码，保证消息保密性和隐蔽性及认证性的一门学问；而密码分析学是研究分析密码破 译或验证消息真伪的学问。密码编码学和密码分析学共同组成密码学。 密码学的历史既古老又年轻，随着人类社会战争的延续和通信发展的需要，为了保 2 第一章绪论 护真实信息，采用伪装后再传递的做法，逐步演变成了密码技术，以后慢慢形成一门独立 学科，而且逐步变成计算机科学、通信技术和信息领域中一门具有生命力的主要学科。科 学技术的发展和社会竞争( 主要是战争) 的刺激推动了密码学的发展。因为密码技术的基 本思想是伪装信息，尽可能地隐蔽和保护所需要的消息，使未授权者无法理解真实含义。 现代的信息伪装技术各种各样，常用的伪装方法就是对信息进行一组可逆的数学变换，变 成密文后在信道中传输。还原伪装的方法就是通过解密方法恢复信息的原样性。 在一个密码系统中，伪装前的原始信息( 或消息) 称明文( p l a i n t e x t ) ，伪装后的信 息( 或消息) 称为密文( c p h e r t e x t ) ，伪装过程称为加密( e n c r y p t i o n ) ，其逆过程，即由 密文恢复出原明文的过程称为解密( d e c r y p t i o n ) 。实现消息加密的一组伪装规则( 或数学 变换) 称为加密算法( e n c r y p t i o na l g o r i t l m a ) ，对密文进行解密时所采用的一组恢复伪装 规则( 或数学反变换) 成为解密算法。加密算法和解密算法的操作通常都是在一组密钥 ( k e y ) 的控制下进行的，分别称为加密密钥和解密密钥，这个过程如图1 - 1 所示。通过 各种手段窃取信息机密过程称为窃密，利用技术分析或破解所截获的密文，并用来推断出 明文或密钥的过程称为密码分析( c r y p t a n a l y s i s ) 。 厂司 i _ j 图1 - 1 加、解密过程 f i g l - 1e n e r y p t d c e r y p tp r o c e 进一步分析密码体制可以发现，当k - 配时，习惯上称为单密钥密码体制或对称密 码体制( o n e k e y o rs y m m e t r i ce r y p t o s y s t e m ) ，传统密码体制即属于这种类型，特点是：加 密密钥和解密密钥相同，由其中一个很容易推出另一个。算法简单易实现，但密钥管理相 对困难。而当恐，l 蜀时，通常称为双密钥密码体制或非对称密码体制( t w o - k e yo r a s y m m e t r i ce r y p t o s y s t e m ) ，现在流行的公开密钥密码体制即属此类型，特点是：鼍，j 乙 不一样，计算配时无法由k 推出，即使将k 公开，也不影响j 乙的安全因此，特别适 合计算机网络和分布式计算机系统应用算法复杂，难实现，但密钥管理相对容易 信息保密作用是伪装后的信息可以存储在计算机文件中，也可以流通在计算机网络 中，即使此时信息遭受窃取或某种原因破坏而泄露，未授权者也无法理解真实的含义。此 时保密便起到保护信息的真实性而不泄密的作用。 作为密码理论的重要发展，主要经历了密码技术发展的四个阶段： 4 第一阶段( 1 9 4 9 年前) ：密码学发展初级阶段，未形成一门独立学科； 4 第二阶段( 1 9 4 9 年1 9 7 6 年) ：密码学形成学科阶段，以1 9 4 9 年s h a n n o n 发表的 3 西安理工大学顽士学位论文 “保密通信的信息理论”为标志； 4 第三阶段( 1 9 7 6 年后) ：密码学新体制形成与发展阶段，以1 9 7 6 年d i f f i e 和h e l l m a n 发表的“密码学的新方向”为起点，公钥密码体制诞生为标志； 第四阶段( 2 0 世纪8 0 年代开始) ：量子密码学、基f 身份、椭圆曲线及可证明安 全的兴起。 1 2 数字签名综述 1 2 1 数字签名概念 数字签名是密码学和信息安全中最重要和最有用的概念之一。它的提出使得在网络环 境下，任一实体( 组织或者个人) 对在网络上传输的文件进行签名成为可能。任何得到该 签名的实体可以对签名的有效性进行验证。为了实现签名目标，签名方必须公开足够的验 证信息，以便使得到签名的验证方能顺利的检查签名的真伪；但又不能泄露产生签名的机 密信息，以防止他人伪造自己的有效签名。签名一旦发送，消息的签署者就承担了对所签 消息的责任。 国际化标准组织对数字签名2 1 是这样定义的：附加在数据单元上的一些数据，或是 对数据单元所做的密码交换，这种数据或交换允许数据单元的接收者用以确认数据单元来 源和数据单元的完整性，并保护数据。防止被人( 如接收者) 伪造。因此一个安全有效的 数字签名方案必须满足以下要求： ( 1 ) 要使签名有效，签名必须处于签名者的完全控制之下，即无人能够伪造关于签名者 另一个签名； ( 2 ) 签名者发出签名给接收者后。不能否认他所做的签发； ( 3 ) 接收者对已收到的签名消息不能否认； ( 4 ) 与签名联系的信息必须明确； ( 5 ) 第三者可以确认收发双方之间的消息传送，但不能伪造这一过程。 满足上述要求的数字签名能够实现以下功能； ( 1 ) 接收方能够证实发送方身份； ( 2 ) 发送方在事后不能否认签发的报文； ( 3 ) 接收方或非法者不能伪造、篡改报文。 1 2 2 数字签名的发展 数字签名最早的建议应用之一是用来对禁止核试验条约的验证。美国和前苏联互相允 许把地震测试仪放入另一个国家中，以便对核试验进行监控。问题是每个国家需要确信东 道国没有篡改从监控国家的地麓仪传来的数据。同时，东道主国家需要确信监测器只发送 规定的需要监测的信息。传统的鉴别技术能解决第一个问题，但只有数字签名能同时解决 4 第一章绪论 两个问题。东道国一方只能读，但不能篡改从地震测试仪传来的数据；而监控国确信数据 没有被篡改。 现今的数字签名技术以密码理论为基础，其核心是采用加密技术的加解密算法来实现 对报文的数字签名。从目前的密码学体制来分，可分为对称密钥密码体制和非对称密钥密 码体制( 公钥密码体制) 。前者是指加密和解密都使用相同的密钥，这种体制中最有代表 性的算法为d e s 3 1 算法；后者是指加密和解密使用不同的密钥，在这种密码体制中，有 一个密钥可以公开，称作公开密钥，另一个密钥保密，称作秘密密钥。这种体制中最有代 表性的算法为r s a b l 算法。因此目前实现的数字签名也可分为两种：基于对称密钥密码 体制的数字签名和基于非对称密钥密码体制的数字签名。但是由于非对称密钥密码体制有 公开密钥和秘密密钥两个密钥，这一独特的优点使得非对称密钥密码体制比对称密钥密码 体制更适合构建数字签名方案。这也是目前国内外的主要数字签名方案都是基于公钥密码 体制的原因。 1 9 7 6 年，d e f i l e 和h e l l m a n 在他们开创性的文章密码学的新方向中首次提出 了数字签名的概念。早在1 9 7 9 年g j s i m m o n s 就将数字签名讨论应用于美苏两国的的禁 止核试验条约的验证工作中。在1 9 9 1 年关国n i s t 公布了其数字签名标准，d s s 【5 1 ( d i g i t a l s i g n a t u r es t a n d a r d ) ，于1 9 9 4 年正式采用为美国联邦信息处理标准：d s s 标准中采用的签 名算法称为d s a 硒，随后其他一些国家也颁布了自己的数字签名标准，如俄罗斯1 9 9 4 年颁布的g o s t r 3 4 1 0 - 9 4 标准等。较早出现的数字签名算法，如1 9 7 8 年前后提出的r s a 盱1 等数字签名算法，至今还在使用。常见的数字签名算法玎1 如r s a 、d s a 、e l g a m a l 、 s c h n o r r 等。还有一些具有特殊用途的数字签名算法，如盲签名7 1 、不可否认签名嵋、 证实签名9 1 0 1 1 1 、群签名1 1 3 1 代理签名1 1 4 1 短签名 1 5 1 失败一终止数字签名1 1 6 1 盲签名t l t l 批量签名1 1 8 1 多重签名n 9 1 、门限签名2 0 2 等。总结现今普遍使用的数字 签名算法，都基于下面三个数学难题基础之上的；( 1 ) 整数的因子分解问题( i n t e g e r f a e t o f i z a t i o n ) 问题，如r s a 算法；( 2 ) 离散对数( d i s c r e t el o g a a t h i m ) 问题，如e l g a m a l 、 d s a 、s e l m o r r 等算法；( 3 ) 椭圆曲线( e l l i p t i c c u l v e ) 离散对数问题，如e c d s a 咙1 算 法。当然还有其他一些数字签名算法，如基于有限自动机原理的有限自动机数字签名算法； 基于背包系统的s h a m i r 背包数字签名算法等。其中基于有限自动机的公钥密码体制 是我国学者陶仁骥，陈世华提出的而x i n m e i 方案是我国王新梅教授提出的基于纠 错码理论的数字签名体制。 随着i n t e r n e t 的飞速发展和电子商务的提出，数字签名技术获得了更加广泛的研究和 应用。各国都已经制定详细研究计划开始着手对数字签名进行研究，都希望建立自己的数 字签名标准，而且相应的还建立了数字签名法案，使数字签名得到司法机关的认可，具有 法律效力。我国近几年也随着信息技术的高速发展在数字签名方面做出了很多的研究工 作，并开始了对我国数字签名标准的征集工作。新颁布的数字签名法，也于2 0 0 5 年4 月 正式实施。 西安理工大学硕士学位论文 1 2 3 数字签名的应用 数字签名机制作为保障网络信息安全的手段之一，可以解决伪造、抵赖、冒充和篡改 问题。数字签名比手工签名更具优越性。特别是在网络应用中，数字签名是进行身份鉴别 与网上安全交易的通用实施技术。数字签名在包括身份认证识别、数据完整性保护、信息 不可否认性和匿名性等诸多信息安全领域中有着重要的用途。甚至可以毫不夸张的说，有 信息安全的地方就有数字签名。特别是大型网络安全通信、电子商务系统的密钥分配、用 户认证等过程，数字签名都具有重要的作用。 下面我们具体看看数字签名在网络中的应用2 ”： 网上银行通过因特网向用户提供信息查询、对帐、网上支付、资金划转、信贷业务以 及投资理财等金融业务。网上银行将给传统银行业带来巨变，有人估计：网上银行将使劳 动生产率年均增长5 4 银行发放给你的i c 卡，就存储了代表你身份的数字证书与其他 信息，其交易过程就需要数字签名的支持。 电子商务能完成企业之间、企业与消费者之间在网上的商业交换活动。网上证券能在 网上完成股票交易、网上证券信息服务、网上银行证券转帐业务等。这些业务需要身份 鉴别、防篡改等功能，也要使用数字签名。 再看看电子政务。假如一个没有身份认证服务的电子政务系统，任何人都可以随便签 发文件散布，而不用担心事发后的追查，因为无法甄别出签字者，该电子政务系统的危害 性可想而知。电子政务系统必须提供身份认证服务、权限控制服务、信息保密服务、数据 完整性服务和不可否认服务。 我们平常的电子邮件，也常要求具有数字签名功能，比如流行的p g p ( p r e t t yg o o d p r i v a c y ) 。你可以用它对自己的邮件保密，以防止非授权者阅读；它还能对你的邮件加上 数字签名，从而收信人可以确认邮件是你发出的，它就提供了简单的数字签名模块，如下 图： 6 图1 - 2 p g p 加密功能 f i g1 - 2p g pd e c r y p tp r o p e r t y 第一章绪论 1 3 指定验证者签名及发展状况 c h a u m 和v a i l a n t w e r p e n 在1 9 8 9 年提出了不可否认签名”，使得签名者可以完全控 制他( 她) 的签名这种签名具有一个很优良的性质：一个声称的签名在没有签名者合作 的情况下无法被验证，并且签名者无法抵赖他生成过的有效签名。这在应用密码学中有大 量应用，但是一个明显的问题就是如果签名者拒绝合作，就无法确定任何事情。 由以上问题所激发，j a k o b s s o n ，s a k o 和1 1 1 1 p a 出i a z z o 在1 9 9 6 年首次提出指定验证者 签名2 4 这个概念。在这种体制中，消息的签名指向一个由签名者选择的具体的验证者， 只有这个验证者可以验证签名的有效性。其他任何人都不能确信这个签名是否有效，因为 验证者自己可以独立生成一个签名和真正的原始签名不可区分。指定验证者签名提供了对 消息的认证性，但是没有传统签名的不可否认性。这样的签名体制在电子商务，电子政务 中有很多用途，有效地解决了认证性和隐私性的冲突。 2 0 0 3 年，s a e e d n i a ，k r e m e r 和m a r k o w i t c h 提出了强指定验证者晒1 的概念，即任 何人都能生成一个具有相同分布的副本，使之与原始证明不能区分。我们的目标是允许 a l i c e 向b o b 证明陈述q 的有效性，使其确信这个事实，但他不能把这种确信转移给其他人。 那么形式化定义强指定验证者为：令p ( 4 ，曰) 是用于础i c e 向b o b 证明陈述q 的真实性的协 议，我们础，口) 说是一个强的指定验证者证明，如果任何人都可以产生具有相同分布的 副本，使之对于除了b o b 的任何人来说都是与p ，b ) 生成的无法区分。 同年，r o ns t e i n f e l d ，l a u r e n c eb u l l ，h u a x i o n gw a n g 和j o s e fp i p e r z y k 提出了广义 指定验证者签名( u d v s ) 哳1 ，一个u d v s 可以作为一个标准的公开可认证的数字签名， 但它具有一个特殊性质就是允许任何一个签名的持有者( 不必是签名者) 通过引入验证者 的公钥将签名指定给任意他( 她) 期望的指定验证者。给定被指定的签名，指定验证者能 够验证签名者签过的消息，但无法使其他人相信这个事实。 2 0 0 4 年，w i l l ys u s i l o 。f a n g g u oz h a n g 和y im u 提出了基于身份的强指定验证者签名 啪，避免了复杂的公钥证书分发问题，用户公钥可以很容易的由其身份标识计算得到， 私钥可由可信任权威机构得到，在不必获得对方公钥证书的情况下也可以完成签名，使方 案更加简洁并降低了通信与计算代价。 同年，f a b i e nl a g u i l h u m i c 和d a m i e nv c r g n a u d 提出了多重指定验证者签名嗌1 ， 签名者可以同时指定多个验证者。这在多用户的环境中有很多应用，例如可以用于设计公 平分发的合同签署方案。 2 0 0 5 年，r u iz h a n g , j t mf u r u k a w a , 和h i d e k ii m a i 提出了不在随机预言机下的短签名 和广义指定验证者签名啷1 ，使签名长度变短并使证明所依赖的环境更加接近实际情况。 在分析密码体制中，随机预言机是一个形式化模型，其将哈希函数看成一个含有一个随机 函数的黑盒子。但是许多情况显示出来，随机预言机下的安全性并不意味着实际环境中的 安全性。一个体制在随机预言机下可以是安全的，然而如果违背了任何一个具体的难处理 7 西安理工大学硕士学位论文 的假设或者攻破了一个基础的哈希函数，这个体制就可能被攻破。因此，设计一个基于标 准难处理假设的可证明安全的u d v s 在理论和实际上都是有重要意义的 1 4 变色龙签名及发展状况 变色龙签名啪1 非常近似于不可否认签名，但是其更加简单且易于实现。不可否认签 名往往需要以零知识证明的有关协议为基础；而变色龙签名与普通签名方式一样：先进行 散列函数变换，然后签名。变色龙签名的取名就是因为它使用的散列函数名为 c h a m e l e o nh a s h 。 变色龙体制首次在文献【3 0 】中提出。它指出接收方有能力以任意他( 她) 期望的 方式打开消息。这个概念后来得到了扩展，产生变色龙哈希体制个陷门函数，即在 通常情况下是抗碰撞的，但在拥有陷门信息的情况下能够找到碰撞。构造这种签名，首先 用变色龙哈希函数对消息进行哈希。然后用标准的数字签名体制( 比如r s a ) 对这个哈希 进行签名，整个体制的计算开销仅相当于直接r s a 签名的2 倍。这就导致产生了一种不可 否认签名体制，它不像以前的不可否认签名，并不依赖零知识证明。正因为如此，这种方 法的一个优势就是复杂度降低了。变色龙函数也是非交互的，签名者不需要与接受方交互 就可以生成一变色龙签名，验证也一样。非交互性也降低了体制的复杂度。变色龙体制为 计算开销大的不可否认签名体制提供了另一种选择，他们发展的更加高效。变色龙体制也 通过提供不可否认性和不可传递性解决了传统签名体制面对的认证性与隐私性的冲突问 题。 变色龙签名方案发展时问较短，自从k r a w c z y k ，h 和r a b i n ，t 在2 0 0 0 年首次提出以 来，陆续出现了一些基于身份的变色龙签名方案3 l3 2 1 ，基于身份的体制在密钥分发方 面是有优越性的。变色龙体制的一个最初的问题就是由证明导致发生一个碰撞，签名者可 以由此计算出接收者的密钥。在【1 3 3 】中已经克服了密钥泄漏的问题，在后期的体制中 就不再有这个问题。 1 5 论文章节安排 数字签名在信息安全，包括身份认证、数据完整性、不可否认性以及匿名性等方面有 重要应用，特别是在大型网络安全通信中的密钥分配、认证以及电子商务系统中具有重要 作用。但是对于普通数字签名，任何人都可以验证签名是否具有有效性，有时这是签名者 不希望的；另外一个方面，如果其他人不能验证签名的有效性，那么签名者就可以随意抵 赖，这又是与签名的最终目的相违背的。指定验证者签名在这种需求环境下应运而生，它 一方面可以保护签名者的隐私，同时又不需要与签名者交互就能验证签名是否有效，解决 了认证性和隐私性的冲突。 论文主要研究了指定验证者签名方案及其应用，分析了现有指定验证者签名方案的优 缺点，提出了一个新的指定验证者签名方案；对变色龙签名进行了初步研究，提出了一个 b 第一章绪论 改进方案。主要研究成果如下： 1 指出了w i l l ys u s i l o 等提出的基于身份的强指定验证者签名方案的安全性证明存在 缺陷，对该方案的安全性给出了新的证明。并在此基础上提出了一个新的可消息恢复的基 于身份的强指定验证者签名方案，适用于在对隐私性和认证性要求良好协调并且带宽受限 的环境对短消息进行签名 2 变色龙签名体制是基于传统的哈希一签名范例的，但它使用的哈希函数比较特别， 叫做c h a m e l e o nh a s h ，正由于这种特殊的h a s h 函数，变色龙签名体制具备非交互性、不 可传递性和不可否认性等优良特性。作者利用双线性对，提出一个改进的基于身份的变色 龙签名，在随机预言机下是安全的。 论文的章节安排如下： 第二章介绍密码学中用到的一些基础数学必备知识，内容包括基础数论、抽象代数、 复杂性理论以及计算性困难问题等。 第三章介绍现代网络高级密码体系，主要内容包括：散列( h a s h ) 函数、数字签名 体制、零知识证明等。其中详细描述散列函数的本质、分类，设计构造与分析攻击，介绍 数字签名的定义及安全模型并研究几种典型的数字签名体制，最后对零知识证明给出分析 并列举例予便于理解。 第四章先对指定验证者签名的相关内容及发展状况进行简单概括，然后研究分析现有 的指定验证者签名体制，在此基础上给出一个新的证明方法，并基于指定验证者签名体制 的基本思想利用双线性对提出一个带消息恢复的基于身份的强指定验证者签名方案。 第五章概述了变色龙签名体制，对其核心部分变色龙哈希进行分析，研究现有变 色龙签名体制，提出一个基于身份的变色龙签名方案。 最后对作者的工作进行总结，并对指定验证者签名和变色龙签名的进一步发展和应用 进行阐述。 9 西安理工大学硕士学位论文 2 信息安全数学基础理论 科学的实践证明，没有一个学科是可以离开数学基础理论的支持而发展起来的。密码 学可理解为以应用数学为主的一门交叉学科。内容涉及到数论、代数、复杂性理论、组合 数学及信息论等，打好学习密码学要求的数学基础是掌握网络信息安全中的密码理论及密 码应用技术的基本保证。 2 1 基础数论 2 1 1 同余 定义2 1 设口，b e z ，m ，1 0 ，若m i 和一酚，则称a 和参模辫同余，记为： 口- b ( m o d m ) ，整数m 称为同余式的模。 定理2 1 模f n 的同余关系满足； ( 1 ) 自反性，即a a m o d m ； ( 2 ) 对称性，即若口- b m o d m ，则6 - 口m o d m ； ( 3 ) 传递性，即若a - b m o d m ，b - c r o o d m ，则口- c m o d m ； 定理2 2 若a b m o d m ，c i l l d r o o d m ，则 ( 1 ) a c - b 士d r o o d m ( 2 ) a c _ b d r o o d m 定理2 - 3 若a c _ b c m o d m ，且c 和刖互素，则ai b m o d m 2 1 2e u l e r 定理 定义2 2 比m 小但与m 互素的正整数的个数，成为m 的欧拉函数，记为妒细) 定理2 4 若和埘2 互素，则妒( ，吼卅2 ) - v ( m ，砌伽2 ) 定理2 5 e u l c r 定理：若a 和m 互索，则9 = l m o d m 。 2 1 3f o r m a t 定理 定理2 6f o r m a t 定理：p 是素数，口是不能被p 整除的正整数，则4 ”- l m o d p 2 1 4 欧几里德算法( e u c l i da l g o r i t h m ) 定理2 7 带余除法：设a , b e z ，6 幸0 ，若存在唯一确定的整数q 和，使得 口= b q + ，0 6 则g c d ( 口，6 ) - g c d ( a ，a m o d 。具体描述如下：设a ，b e z ，b _ 0 ， 若bta ，重复应用带余除法，则有下列等式成立： 第二章信息安全数学基础理论 口1 b q l + ， b 1 9 2 + r 2 ， r i - ，2 日3 + ， - 2 1 - l q 。+ r 一，0 r 2 r 3 ，经过有限次带余除法后，总可以绲到一个余数为零，即上式 中+ t 1 0 。 2 2 抽象代数初步 2 2 1 群 定义2 3 称群c g 。，为一个代数系统，是指其中g 为非空集合，为g 上的一个二 元运算( 可加可乘) 。且满足以下条件： 1 ) 群运算，是封闭的。v a ，b g 女a + b e g ； 2 ) 群运算+ 是可结合的。v a ，b ，c g j a + p + c ) ； + 6 ) + c ； 3 ) 存在单位元e e g ，使得所有a e g 。满足e a a e 一4 ； 4 ) 对每一个元素a e g ，存在逆元a 1 ，使得a - 口一一a 1 口1 己 如果运算- 取 或，分别称g ，+ ，为加法群，tg ，i 为乘法群。 定义2 4 设t g ，为一个群，若g 为有限集，则称c g ，为有限群；若g 为无限集， 则称c g ，+ ，为无限群。g 中元素的个数通常称为该有限群元素的阶，记为i g i 。 2 2 2 有限域 定义2 5 非空集合f 上的两个运算加法“+ ，和乘法“x ”如果满足以下三个条件，就称 f 是一个域： 1 ) ( f ，+ ) 是一个a b e l 加法群； 2 ) ( f 、 0 ，x ) 是一个a b e l 乘法群，其中0 是加法单位元： 3 ) 对任意的a , b ，c e f ，有a x p + c ) 1 4 x b + 口x c ， + x c l 口x c + 6 x c ( 分配律) ； 定义2 6 若代数系统f 中的集合只含有有限个元素，则称该域f ，+ ，为有限域， 亦称g a l o i s ( 伽罗瓦域) 并用g f ( q ) 表示，其中口为域中元素个数。有限域中的个数称 为有限域的阶。 2 3 复杂性理论含义 复杂性理论u + 枷是一个具有广泛意义的研究领域，特别是在计算机科学和密码理论 研究中，有着非常重要的应用。从密码学角度说，破译密码牵涉到密码算法是否能够攻破 西安理工大学硕士学位论文 以及计算机分析能否实现问题。在具体实践中将取决于相关条件的约束，比如说，一个好 的密码算法能否被攻破，除了密码算法本身真正被攻破外，其次就是借助计算机分析，根 据某种破译算法，花费大量时间最终也能破译这种密码算法。我们说，如果只是由于算法 复杂的原因，结果花费了大量时间( 甚至比宇宙年龄还要大) 和存储空问的代价解决了这 个问题，尽管在理论上说可以攻破，但这种密码算法实际上是不可攻破的。这就牵涉到一 个密码算法的“难”与“易”问题，难到什么程度，“较难”、“很难”、“很容易”、“容易”， 需要对一个密码算法和技术成本进行比较，才能确定算法的安全性。一般地，我们把计算 机处理问题的“难”、“易”程度理解为“复杂”程度，简称为复杂度。在这一点上，复杂 性理论可为分析不同密码技术和算法的“复杂性”提供理论依据和比较方法。复杂性理论 主要包括丽个方面：算法复杂性( c o m p l e x i t y o f a l g o r i t h m ) 和问题复杂性( c o m p l e x i t y o f p r o b l e m ) 。 2 3 1 算法复杂性分析 算法的复杂性是指一个具体算法运行所需的计算机资源的量，通常由该算法所需的最 大时间与存取空间来确定，前者需要时间资源的量称为时间复杂度，后者需要空间资源的 量称为空间复杂度，两者取决于实际问题规模竹描述的量( 用来表征输入数据长度或尺寸 大小) 。为了避免不同对象引起的时间和空间差异而影响算法研究的尺度，通常采用输入 规模，l 所对应的时间与空间需求的平均值进行研究。也就是说，用平均时间复杂性函数 r 伽) 和平均空间复杂性函数s o ) 来表示算法所要解某种问题的规模撑大小对应的时间和 空间需求的平均值。这样就有一个基准尺度来衡量该算法在机器上运行所花费的时间和所 占用空间的大小。 任何算法都牵涉到复杂性，有的问题在有限步数内可望找到答案，而有的问题则随着 复杂程度而迅速增大计算量，甚至达到计算机无法对付的地步，前者称为多项式复杂性， 后者称指数复杂性。常见的时间( 空间) 复杂性算法分类主要有：多项式时间算法、指数 时间算法和超多项式时间算法等等。 多项式时间算法( p o l y n o m i a lt i m ea l g o r i t h m ) 指时间复杂度为d 伽) 类型的算法。其 中t 为常数，规模n 为输入数据长度。若f 一0 ，默认算法为常数；t 一1 ，称算法为线性的： t -