（计算机应用技术专业论文）两种具有特殊性质的数字签名研究.pdf

摘要 数字签名是对传统手写签名的模拟，它具有防伪造、防篡改和防抵赖等特点，在 电子商务和电子政务中有重要应用随着数字签名研究的不断深入，近年来在理 论和应用研究上相继出现了许多具有特殊性质或特殊功能的数字签名，如盲签名、 基于身份签名、门限签名、群签名、多重签名和代理签名等本文的工作之一是研 究干弋理多重盲签名”，在分析他人提出的一个代理多重盲签名方案基础上。提出两 种高效的新方案，并给出了安全性证明和效率分析 数字签密是一种带加密功能的数字签名，它是公钥加密算法和数字签名在更高 层次上的结合由于其特殊的安全性。数字签密成为近年的一个研究热点本文工作 之二是借助双线性映射构造了一种“基于身份的多接收者代理签密”方案，并分析了 方案的安全性和实现效率 关键词：代理签名，盲签名，代理多重盲签名，签密，基于身份，代理签密 a b s t r a c t a d i g i u l ls i g n a t u r es c h e m ei sa n a l o g o u st ot h et r a d i t i o n a lh a n d w r i t i n gs i g n a t u r e s i n c ei ta c h i e v e su n f o r g e a b i l i t y , i n t e g r i 哆a n dn o n - r e p u d i a t i o n ，d i g i t a ls i g n a t u r ep l a y sa n i 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 m e n t w i t ht h ed e v e l o p m e n to ft h ed i g i t a l s i g n a t u r e r e c e n t l yal a r g en u m b e ro fd i g i t a ls i g n a t u r e sw i 血a d d i t i o n a lp r o p e r t i e sh a v e a p p e a r e d ( e g b l i n ds i g n a t u r e ，i d e n t i t y - b a s e ds i g n a t u r e ，t h r e s h o l ds i g n a t u r e ，g r o u ps i g n a - n l r e m u l t i - s i g n a t u r ea n dp r o x ys i g n a t u r e ) t h em a i ng o a lo f t h et h e s i si st os t u d yp r o x y b l i n d m u l t i - s i g n a t u r e t h r o u g h t h e a n a l y s i s o f as c h e m e p r e s e n t e d b y i m ，w e p r o p o s e t w o n e we f f i c i e n ts c h e m e s ，t h es e c u r i t ya n de f f i c i e n c ya r ea n a l y z e da sw e l l d i g i t a ls i g n c r y p t i o ni san e wk i n do fd i 百t a ls i g n a t u r ew h i c hi n t e g r a t e sp u b l i ck e y e n c r y p t l o na n ds i g n a t u r es i m u l t a n e o u s l yi nai n g i cs t e p n o ws i g n c r y p t i o na t t r a c t sm a n y c r y p t o l o g i s t s i n t e r e s t s d u e t o i t s m e r i t s i n t h e t h e s i s w e p r o p o s e a m u l t i r e c e i v e r i d e n t i t y - b a s e dp r o x ys i g n c r y p t i o nf r o mb i l i n e a rp a i r i n g s t h es e c u r i t ya n de f f i c i e n c ya n a l y s i sa r e a l s op r o v i d e d k e yw o r d s ：p r o x ys i g n a t u r e ，b l i n ds i g n a t u r e ，p r o x yb l i n dm u l t i s i g n a t u r e ，s i g n - c r y p t i o n ，i d e n t i t y - b a s e d , p r o x ys i g n e r y p f i o n 学位论文独创性声明 本人所呈交的学位论文是在我导师的指导下迸行的研究工作及取得的研究成 果据我所知，除文中已经引用的内容外，本论文不包含其他个人已经发表或撰写的 研究成果对本文的研究做出重要贡献的个人和集体，均已在本文中作了明确的说 明并表示谢意 作者签名：龇坚多嘲珥型 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或指定机构送交论文的电子版和纸质版有权将学位论文 用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文的 内容编入有关数据库进行检索有权将学位论文的标题和摘要出版保密的学位论 文在解密后适用本规定 学位论文作者签名：益出墼照 导师签名 学位论文作者签名：鳢墼! ! 羟 导师签名 e t 期：丝霉! ：! 日 期：2 乎：堡：竺 第一章引言弟一早jii 本文研究两类具有特殊性质的数字签名一代理多重盲签名和基于身份的多接 收者的代理签密，为了使读者对此有一个大致的了解。本章介绍数字签名和签密的 相关术语、发展史、研究现状和发展趋势，以及本文的主要工作和章节安排 1 1 信息安全和密码学 随着计算机网络和通信技术的飞速发展。人们之间的信息交流呈现出国际化、 网络化、数字化、智能化、宽带化的趋势，可以说人类已经进入了“信息时代”信息 时代的主要特征是信息成了社会中最重要的一种资源和财富，信息的交流和处理手 段成了人们生活必不可少的组成部分，过去人们想象不到的许多事情都已经变成了 现实现在，计算机应用已经渗透到政治、经济、军事、科学文化和家庭生活等各个 领域然而现代信息技术是一把双刃剑，它一方面给人类带来了巨大的好处，另一方 面又给人类带来了前所未有的威胁由于信息的存储、传递和处理等过程往往是在 开放的通信网络上进行，所以信息容易受到窃听、截取、修改、伪造和重放等各种 攻击手段的威胁因此，与通信技术的高度发展相对应，信息安全成了信息社会急需 解决的最重要的问题之一 信息安全的中心内容是保证信息在信息系统中的保密性和认证性所谓信息的 保密性，是指信息在生成、传递、处理和保存等过程中。不能被未授权者所提取所 谓信息的认证性，是指信息在生成、传递、处理和保存等过程中，不能被非法地篡 改、删除、重放和伪造等解决信息安全问题是一个庞大的系统工程，需要综合运用 数学、计算机、信息论、编码学、密码学、通信技术、管理技术等各种学科和技术的 研究成果，并且需要在实践中不断提高和探索其中，密码学给解决信息安全问题提 供了许多有效的核心技术，在信息的保密性、认证性等方面发挥着关键性的作用 简单的说，密码学是研究信息系统安全的一门学科它主要包括两个分支，即密 码编制学和密码分析学密码编制学是对信息进行编码实现信息隐蔽的一门学科。 其主要目的是寻求保护信息保密性和认证性的方法；密码分析学是研究分析破译密 码的学科，其主要目的是研究加密消息的破译和消息的伪造密码编制学和密码分 1 2 数字签名研究背景第一章引言 析学既相互对立又相互促进地发展 密码技术的基本思想是对消息做秘密变换，变换的算法即称为密码算法 而决定秘密变换的秘密参数叫做密钥( k e y ) 在密钥的作用下，把有意义的明 文( p a i n m x o 变换成无意义的密文( c i p h e r * t e x t ) 的变换叫做加密算法( e n c r y p f i o n ) ，相 应的逆变换叫解密算法( d c c t y p t i o n ) 若在密钥的作用下把消息变换成一种“证据”。 用来说明某个实体对消息内容的认可，则称变换为签名算法( s i g n a l u r e ) ，相应的逆算 法称为验证算法( v e r i f i c a t i o n ) 根据密钥的特点，密码体制可分为公钥体制( p u b l i c - k e ys y s t e m ) 和私钥体制( 蹦v a t 啦c ys y s t e m ) 在私钥密码体制中，一对加密或解密算 法使用的密钥相同或实质相同在公钥体制中，加密或解密算法使用的密钥不同。而 且从一个难于得到另一个 信息安全在其发展过程中经历了三个阶段：2 0 世纪6 0 年代以前，人们强调的 主要是信息交换过程中的信息保密性。对安全理论和技术的研究也只侧重于密码 学，这一阶段的信息安全可以简单称为信息保密( i n f o r m a t i o np r i v a c y ) 2 0 世纪6 0 年 代后，半导体和集成电路技术的飞速发展推动了计算机软硬件的发展，计算机和 网络技术的应用进入了实用化和规模化阶段，人们对安全的关注已经逐渐扩展 为以保密性( c o n f i d e n t i a l i t y ) 、完整。陛( t n t e g d t y ) 、可用性( a v a i l a b i l i t y ) 为目标的信息 安全( i n f o r m a t i o ns e c u r i t y ) 从2 0 世纪8 0 年代开始，由于互联网技术的飞速发展。信 息无论是对内还是对外都得到极大开放，由此产生的信息安全问题跨越了时间 和空间，信息安全的焦点已经不仅仅是传统的保密性、完整性和可用性三个原 则了，由此衍生出了诸如可控。眭( c o n t r o l l a b i l i t y ) 、认证性( a u t h e n t i c i t y ) 、不可否认 性( n o n - r e p u d i a t i o n ) 等其他的原则和目标，信息安全也转化为从整体角度考虑其体 系建设的信息保障( i n f o r m a t i o na s s u r a n c e ) 1 2 数字签名研究背景 数字签名是对传统手写签名的模拟，在实现身份认证、数据完整性、不可抵赖 性等方面都有重要应用，是计算机信息安全的核心技术之一利用这种技术，签名的 接收者可以确定签名发送者的身份是否真实同时，发送者不能否认发送的消息。接 收者也不能篡改接收到的消息在现实生活中，数字签名已在越来越多的产品及协 议中得到应用，尤其在电子邮件、电子银行、电子商务和电子政务等许多领域有重 要应用价值，是当前信息化建设中的关键安全机制之一 作为保障网络信息安全的重要手段，数字签名主要有以下特性【l 】： 1 防伪造：其他人不能冒充签名者对消息进行签名，接收方能鉴别发送方所宣称 的身份： 2 1 3 国内外研究现状第一章引言 2 防篡改：对消息进行签名后，消息的内容不能更改 3 防抵赖：签名者事后不能声称他没有签过名 除了具备以上特性，数字签名与传统的手写签名相比也更具优越性，比如签名 因消息而异，即同一个人对不同的消息签名。其结果是不同的；对消息的修改必然会 导致签名结果的改变，消息与其签名两者不可分割等但是在数字签名中，有效签 名的复制同样是有效的签名，而在传统的手写签名中。签名的复制是无效的因此， 在数字签名的方案设计中要预防签名的非法重放。可以通过在签名报文中添加流水 号、时间戳等技术来抵抗重放攻击 数字签名技术是提供认证性、完整性和不可抵赖性的重要技术，作为重要的数 字证据，美国、新加坡、日本、韩国、欧盟等电子商务开展的较早的国家和地区都相 继通过法案赋予数字签名法律效力，中国全国人大也已于2 0 0 4 年8 月通过了中华 人民共和国电子签名法，数字签名将与手写签名一样具有同等的法律效力 数字签名技术的研究与使用，拓宽了密码学的研究范围和领域，在网络通信身 份认证中占有独特的地位随着信息时代的到来，网络应用中涉及到伪造、抵赖、冒 充、篡改和身份鉴别的问题，都可以用数字签名技术来解决作为一种核心有效的 信息安全技术，数字签名技术的应用面将越来越广，需要数字签名技术支撑的应用 系统也将越来越多，数字签名将成为网络信息安全体系的基础与支柱 1 3 国内外研究现状 1 3 1 数字签名的发展 1 9 7 6 年d i f f i e 年d h e l l m a n 在“密码学新方向”吲中利用公钥密码学的思想提出了 数字签名的概念，但是并没有提出具体的签名方案，第一个数字签名方案是在 两年后。即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 签名方案吼同时给出了著名的r s a 公钥密码方案，他们也因此共同获 得2 0 0 2 年的图灵奖此后的二十几年里，新的数字签名方案如雨后春笋般不断涌现， 其中比较著名的有：e i g a m a l 数字签名方案【4 1 、s c h n o r r 数字签名方案【) 1 、r a b i n 数字 签名方案f 6 】、d s a 数字签名方案l 乱o k a m o t o 数字签名方案 8 1 、f i a t - s h a m i r 数字签名 方案【9 】等 随着对数字签名研究的不断深入，同时也由于电子商务、电子政务的快速发展， 简单模拟手写签名的一般数字签名已不能完全满足需要，多年来提出了许多具有特 殊性质或特殊功能的数字签名，如1 9 8 2 年c h a u m g l 入了盲签名l i n ds i g n a t u r e ) 1u 1 ； 1 9 8 4 年s h a m i r 提出了基于身份的密码系统l i d b a s e dc r y p t o s y s t e m ) 儿】的概念，同 3 1 3 国内外研究现状第一章引言 时提出了基于身份的签名( 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 纽k e l 引入了门 限签名( n l r e s h o l ds i g n a t u r e ) 1 2 ；c h a u m 和h e y s t 引入了群签名( g r o u ps i g n a t u r e ) 1 3 ； 1 9 8 3 年i t a 】( i l r a 首次提出多重数字签( m u l t i s i g n a t u r e ) 1 1 4 概念：m a m b o 。u s u d a 和o k a m o t 在1 9 9 6 引入了代理签名口r o x ys i g n a t u r e ) t 1 5 1 1 3 2 数字签密的提出以及研究现状 z h e n g 在c r y p t o 9 7 q b 首次提出了数字签密( s i 锄c r y p t i o n ) l lo 】的概念，这篇文献在 数字签密发展史上具有里程碑的意义数字签密包含两个相关的算法：签密算法和 解签密算法，它能够在一个合理的逻辑步骤内同时实现签名和加密两项功能，大大 降低了消息保密认证传输所需的时间代价和通信带宽值得注意的是，数字签密与 带加密的数字签名功能相同。但实现的技术不尽相同：数字签密是公钥加密算法和 数字签名在更高层次上的结合，签名与加密同时进行，不可分割 z h e n g 基于数字签名标准( d i g i t a ls i g n a t u r es t a n d a r d , 简称d s s ) 的短签名版 本( s d s s l 和s d s s 2 ) ，构造了首个签密方案【1 0 1 2 0 0 2 年b a e k 建立了f u o ( f l e x i b l e u n s i g n c r y p t i o no r a c l e ) 模型【l ，1 ，并在该模型下讨论了办e n g 签密方案的安全性分析 表明，在g a pd i f f i e - h e l l m a n 假设下。该方案作为密码算法可以抵抗自适应的选择密 文攻击( i n d i s t i n g u i s h a b i l i t yu n d e ra d a p t i v ec h o s e n - c i p h e r t e x ta t t a c k , 简称t n d - c c a 2 ) 。 作为签名协议可以抵抗选择消息攻击( c h o s e n m e s s a g ea t t a d 【，简称c m a ) 自此，构 造c c a 2 - c m a 型的数字签密成为一个研究热点基于有限域上椭圆曲线和整数 分解的数字签密方案在文献f 1 8 ，1 9 】中有记载2 0 0 2 年m a l o n e - l e e 首次提出基于身 份的签密方案【2 0 】，随后基于身份的代理签密方案f 2 1 ，2 2 被提出2 0 0 3 年，m a l o n e - l e e z j 】提出基于r s a 公钥密码系统的数字签密方案，并在随机预言机( r a n d o m o r a c l e ) 模型下证明了该方案的安全性l i b e n 和c ! 1 1 i s q u a 旧在文献 2 4 ，2 5 】中对如何利 用椭圆曲线的双线性对以及g a pd i f f i e h e l l m a n 群中的d i f l i e h e l l m a n 问题构造签密 方案进行了深入的探讨数字签密的相关研究可参阅文献 2 6 ，2 7 z h e n g 的开创性工作推动了数字签密研究的蓬勃发展，人们根据各种应用场合 的需要，相继提出了许多不同的数字签密方案例如：在一般情况下，只有接收者才 能验证签名的真实性也就是说，验证签名的过程需要输入接收者的私钥b a o 等 人【z 捌修改了z h e n g 的方案，使得在不泄露接收者私钥的前提下签名可以被公开验 证y u m 和l 鼬【d 】以及s h i n 等人【j u 】沿用并进一步发展了b a o 的思想文献| 3 1 1 将数字 签密推广到具有多个指定接收者的情形 4 1 4 论文的主要i 作 第一章引言 1 4 1 研究内容 1 4 论文的主要工作 随着代理签名和盲签名在电子商务等应用领域的广泛应用，结合两种方案的 优点，在s c h n o r r 签名的基础上。谭作文等提出了一个基于离散对数的代理盲签名方 案【3 2 ，但是t a n 方案在应用中存在一些安全上的缺陷，文献【3 ，j 指出该方案是不安全 的，它既受到广泛伪造攻击，又是可连接的 l u 等人于2 0 0 5 年提出了一个基于s c h n o r r 签名体制的代理多重盲签名方 案【j 卅a 乙u 方案) 方案结合了代理多重签名1 35 】和o k a m o t o s c h n 叫盲签名【8 】同时 具备两种方案的的优点l u 方案在随机预言模型下证明是安全的，但在l 舡方案中。 传递代理信息时原始签名人需要对其加密；同时，代理签名人在验证代理信息时要 先进行解密，从而实现传递代理信息不需要安全信道因此。l u 方案的计算量大。且 最后的签名长度随原始签名人的增加而增长当前对代理多重盲签名的研究还相当 缺乏，已有方案还存在一些安全和效率上的缺陷，因此代理多重盲签名的研究仍有 很多问题需要解决 虽然数字签密的理论研究于几年前就已经兴起，其应用领域也在不断扩大，但 对近几年才提出的基于身份的签密方案的研究还比较缺乏。类型不多例如，在已提 出的基于身份的代理签密方案中，签密文的接收者都只有一个，但在现实生活中，接 收者往往不止一个人，签密者的同一个消息有时需要发送给多名接收者，并且每一 个接收者都希望能够独立的解密且能验证签名的有效性，无需相互协作，任何无关 的其他人若没有签密者或接收者的帮助都无法得到消息且已有方案在实际应用中 还存在一些安全和效率上的缺陷，特别是在计算量上，因为双线性对是构造基于身 份的密码系统的有力工具，但双线性映射的计算效率很低，所以，设计一个安全高效 的基于身份的数字签密方案在实际应用中具有很大的研究价值 本文的工作主要有以下几方面： 1 系统地介绍了公钥密码体制和数字签名体制的基本概念及原理，概括了其发 展概况、研究进展和方向，简要地介绍了一些基本的数字签名方案，阐述了基 于身份的密码体制的研究背景和发展概况 2 分析了一个由l u 等人提出的代理多重盲签名方案，并提出了两种高效的代理 多重盲签名方案，并给出了安全性证明和效率分析，新方案的计算效率比l u 方 案有较大的提升，且签名长度不随原始签名人的增加而增长 3 借助双线性映射构造了一种基于身份的多接收者的代理签密方案，分析了方 案的安全性和实现效率 5 1 4 论文的主要i 作第一章引言 1 4 2 本文的组织结构 本文主要研究了两种具有特殊性质的数字签名技术一代理多重盲签名和基于 身份的代理签密 第一章首先介绍信息安全与密码学技术，然后介绍数字签名的发展。并且分析 了数字签密提出的背景和研究现状最后介绍了本文的主要工作和章节安排 第二章主要介绍本文相关的数学基础知识和密码学理论首先介绍密码学上常 见的困难问题，接着介绍了椭圆曲线以及双线性映射的基本概念，然后介绍了公钥 密码体制，最后讨论了数字签名和认证系统中的重要工具一散列函数和随机预言模 型 第三章主要构造了代理多重盲签名方案首先介绍数字签名技术和几种典型的 数字签名方案，接着介绍了代理签名和盲签名的发展背景、相关概念和研究现状 然后分析了一个代理多重盲签名方案一l u 方案给出了两个新的改进方案，新方案 具有计算量小、效率高和安全性强等优点 第四章主要构造了基于身份的多接收者代理签密方案首先介绍利用双线性对 的基于身份的数字签名和签密技术，接着给出了基于身份的代理签密方案基本结 构，提出了一个基于身份的多接收者的代理签密方案，并且对新方案的安全性和效 率做了分析 第五章对本文作了一个简要的总结，并对研究的方向做了进一步的展望 6 第二章预备知识 帚一早 以亩大u 识 1 9 7 6 年，d i f f i e h h e l l m e n 发表了在密码学领域中具有里程碑意义的文章“密 码学新方向，提出了公开密钥密码学口u b h c 山e y e r y p t o s y s t e m ) ，使得密码系统的 安全性常常建立在某个难解的数学问题之上本章首先介绍密码学上常见的困难问 题，椭圆曲线以及双线性映射的基本概念，然后讨论公钥密码体制，数字签名和认证 系统中的重要工具一散列函数以及随机预言模型 2 1 1困难问题 2 1 数论基础 证明密码系统是否安全的问题一般可归结为某些著名的数学难题，当然这种方 法仅仅为密码系统提供了一种相对于其它问题的安全性证明 大数分解问题 在公钥密码系统中，大数分解问题是最常见的困难问题之一，如r s a 公钥密码 系统、r a b i n 公钥密码系统等 定义2 1 1 大数分解问题( f a c t o r i n g ) ：给定一个正整数m 找出它的所有素因子即 找到不同的素数a ，和正整数白 1 ，i = 1 ，2 ，u ( 佗) ，使得佗= p e l 跨竹) ，其 中u ( 竹) 表示n 的不同素因子的个数 在数论中，大数分解问题是一个古老的问题分解一个大整数的思想很简单。但 是其计算过程比较费时尽管如此，在这方面的研究还是取得了一些进展目前。最 好的大数分解算法是数域筛选法( n u m b e rf i e l ds i e v e ，简称n f s ) 对二进制位长大 于1 1 0 的数来说，一般的数域筛选法是目前已知的最快的大数分解算法数域筛选法 刚被提出时还不是很实用，但随着过去几年一系列的改进，这一点已经得到改变早 期的数域筛选法曾对第九个费尔马数2 5 1 2 + 1 进行分解 7 2 1 数论基础第= 章预各知识 大数分解是一个迅速发展的领域推断大数分解技术的发展是很困难的，因为 没有人能够预见数学理论的进展在提出数域筛选法之前，许多人猜测二次筛选 法( q u a d r a t i cs i e v e ，简称q s ) 接近于任何大数分解算法所能做到的最快( 极限) ，但是 他们错了 r s a 问题是大数分解问题的一个特例 定义2 1 2 憨a 问题俾蚋p j ? 给定正整数竹，b 整数g 如果n 是两个素数鼽g 的乘槐 _ e g c d ( e ，砂) ) = 1 寻找m z 。使得m 。兰c ( r o o d n ) ，其中( n ) = 一1 ) ( g 一1 ) 换句话说，r s a 问题就是计算模竹的e 次方根n 和e 的性质保证了对任意的c 磊，存在唯一的m 磊，使得m 。兰c ( r o o d 扎) 成立 命题2 1 3 憨a 问题可多项式归约为大数分解问题 如果n 是两个素数的乘积，那么计算模几的平方根在计算上等价于对礼进行因子 分解【36 一般的观点认为，r s a 问题和大数分解问题在计算上是等价的，但尚未得 到证明 关于大数分解问题和r s a 问题。有以下假设【3 7 1 ： 假设2 1 4 大数分解假设? 对任意的多项式q ( ) 以及任意的概率多项式时间算法a 存在一个正整数当 时， 1 p r a ( 佗) 。p ：p i 扎且p 1 ，p 叫 时， 1 p r a ( n , e , r s a n ，c ( z ) ) = 叫 时， 1 p r a ( n ，8 ，础 ，e ( z ) ) = z 1 1 一亩 其中几凰= 伽= p q ：p ，q 都是素数，p g 且i p f = i q l = 耐，g c d ( e ，庐( 竹) ) = l ，霉 兹，j 碍a 。( 甸= 矿r o o d 仡 8 2 1 数论基础第二章预备知识 离散对数问题 离散对数问题是公钥密码系统中又一个基本问题，许多密码协议的安全性是基 于寻找离散对数的困难性，如d i f f i e h e l l m a n 密钥协商、e 1 g a m a l 加密、e 1 g a m a l 型签 名及其变型等。因此学者对这个问题进行了广泛而又深入的研究 定义2 17 设g 是一个阶为竹的有限循环群，g 是g 的生成元，a g 若整数z z 0 满足口= g 则称z 是以g 为底。的离散对毒匕用l o g g 口来表示 模指数运算是频繁用于公钥密码系统的一种单向函数不是所有的离散对数问 题都存在解，只有整数才是合法的解容易看出下面的方程没有解： 3 。兰7 r o o d l 3 对1 0 2 4 t k 特的数求离散对数将更加困难 定义2 18 离散对 i 1 墨返( d i s c r e t e l o g a r i t h mp r o b l e m , 简f f 末d l p ) ：给定素数易z 的 生成元9 以及召中的元素以寻找整数z z 0 1 ，使得a 三矿( r o o dp ) 定义2 1 9 广义离散对数i 1 # 返( g e n e r a l i z e d d i s c r e t e l o g a r i t h m p r o b l e m , 简称g d l p ) ： 设g 是一个阶为n 的有限循环税g 是g 的生成元a g ，寻找整数z 磊，使 得口= g 。 密码设计者对下面三个群的离散对数很感兴趣： 素数域的乘法群z ：； 特征为2 的有限域g f ( 2 ”) 上的乘法群； 有限域f 上的椭圆曲线群e c ( f ) 如果模数p 是素数，那么在兹上寻找离散对数的计算复杂度与对同样尺寸的整 数n 进行因子分解的计算复杂度一样，其中n 是两个大致等长的素数的乘积 离散对数的计算与因子分解有着紧密的联系如果可以解决离散对数问题，就 能解决大数分解问题( 逆命题的正确性尚未证明) 目前，在素数域上有三种计算离 散对数的方法：线性筛选法( i j n e a rs i e v e ) 、高斯整数 法( g a u s s i a ni n t e g e r 鲥1 蹦l e ) 以及 数域筛选法关于离散对数问题的综合性概述可参见文献 3 q 2 1 2 椭圆曲线概述 1 9 8 5 年，戤i b h t z 【3 8 】和m m 盯【39 分别提出将椭圆曲线用于公钥密码体制，利用有 限域上椭圆曲线的点构成的群实现了离散对数密码算法相对于r s a 、e i g a m a l 等 9 2 1 数论基础第章预各知识 密码体制，椭圆曲线密码体制是比较新的技术密码学界使用椭圆曲线的目的在于： 椭圆曲线上可以提供无数的有限a b e l 群，并且由于这种群的结构具有很好的性质、 易于实际计算，从而可以用于构造密码算法 所谓椭圆曲线 4 q 是指由w e i e r s f f a s s 方程： ! 2 + a l x y + a a y = 护+ a 2 矿+ a 4 x + 0 6 所确定的平面曲线刀，其中m f ，i = 1 ，6 ，f 是一个域点p = ( 2 ，y ) e 就是椭 圆曲线上的一点密码学通常在有限域的基础上研究椭圆曲线，如有限域昂和j k ， 可利用椭圆曲线上的“加法”构建一个a b d 群 椭圆曲线上的“加法”可用图2 1 表示设p = ( z 1 ，讥) ，q = ( x 2 ，驰) 是e 上任意两 点，z 是通过p 、q 两点的直线若p 和q 重合于一点，则；为过尸点的切线f 和椭圆曲 线相交于另一点爿，该点关于z 轴的对称点兄也在椭圆曲线上，定义为r = p + q 若p 和q 关于z 轴对称，即2 与y 轴平行，则f 和椭圆曲线相交于无穷远点d 1 ， 彩? 社胁 抛 0 如l如j i j 一i j 。 鬈 图2 1 ：椭圆曲线上“加法”示意图 椭圆曲线上的加法运算有如下性质： 1 若直线l 和e 相交于p ，q ，尉三点，则p + q + 尉= o ； 2 对v p e ，有p + o = p ； 3 对v 尸q e ，有p + q = q + p ； 4 对v p e ，存在e 上一点，记为一p ，使p + ( 一p ) 一d ； 5 若p q ，s e ，则( 尸+ q ) + s = p + ( q + s ) 如果记2 p = p + p ，3 p = p + p + p ，m p = p + + 尸( m 个p 相加) ，则 称m p 为椭圆曲线e 上的点乘运算如果存在最小的正整数n ，使得n p = 0 ，则称n 是 点p 的阶 1 0 2 1 数论摹础第二章预备知识 2 1 3 双线性映射的基本概念 在椭圆曲线中，有一类被称为超奇异曲线的椭圆曲线，该类曲线被认为“弱”椭 圆曲线j o u x 在文献 4 1 】中首先利用椭圆曲线中的w e i l 配对构造了一个一轮三方密 钥交换协议，b o n e h 和f r a n k l i n 用w e i l 配对构造了一个基于身份的加密体制 4 瑚从 此以w e i l 配对技术为基础的各种密码学算法层出不穷。成为近年来的一个研究热 点 双线性对的内容介绍如下： 定义2 5 设g 1 是由p 生成的循环加群，其阶为素数函g 2 是一个阶为q 的循环乘 群双线性对是指具有下面性质的映射e ：g 1 g l g 2 ； 1 双线性：对于v s q ，r g 1 ，e + q ，r ) = e ( s ，固e ( q ，r ) 和e ( s ，q - i - 固= e ( s q ) e ( s 硒； 2 不可退化性：存在s q g 1 使得e q ) 1 ； 3 可计算性：存在有效的算法来计算e ( s ，q ) ，对v s , q g 1 注：超奇异椭圆曲线中的w e f t 和t a r e 配对具有上述双线性性质 定义2 1 1 0 ( g 1 ，g 2 ，e ) 中的确定性双线- 生- d i f f i e 胁砌m ，l 问题是指给定( p ，a p , b e , o r ) ， 判定cia b r o o d 口是否成立，简记为d d h r 定义2 1 1 1 ( g 1 ，g 2 ，e ) 中的计算性双线性d 游f 胁砌m n 问题是指给定( p ，口p ，b p ) 来计算曲p 简记为c d h r 定义2 1 1 2 离散对数问题是指给定两个群中的元素p 和q 求一个整数n 使得q = n p 成立，简记为d l r 定义2 1 1 3 间隙d i f f i e - h e l l m a n i * l 题是指这样一类问题在群g 上，给定( p ，a p , b e , o f ) ， 容易判定c 三a b r o o d 口是成立的，但是计算a b p 是困难的，换句话说在群g 上， d d h p 易于解决而伽难以解决，则称此群为间隙d 筛e - h e l l m a n 群, 简记为a 姆群 这里假设c d h p 和d l p 是困难问题，即对该问题不存在具有不可忽略概率值的 多项式时间算法在群g 上，若d d h p 不是困难问题而c d h p 是困难问题，即群g 为间 隙d i f f i e h e l l m a n 群这类群存在于超奇异椭圆曲线上在g 上。求双线性配对的逆是 困难问题，即给出p g 1 和e ( p q ) g 2 ，找q g l 还不存在有效的算法 2 2 公钥密码体制第二章预备知识 2 2 公钥密码体制 2 2 1 r s a 密码体制 r s a 密码体制【3 】是公钥密码体制中最负盛名的密码体制，它以发明人r o n a l d l r i v e s t , a d j s h a m i r 昶l l e o n a r dm a d l e m a n 姓名的首字母来命名此密码体制既可用 于加密，也可用于数字签名，而且思想简单、易于理解和程序实现，是目前最为广泛 采用的一种密码体制r s a 密码体制描述如下： 1 选取密钥 选取两个大素数p ，g ； 计算n = p q ，( 凡) = 0 1 ) ( g 一1 ) ； 随机选取e ，满足1 e ( n ) 且g c d ( e ，砂( n ) ) = 1 ； 计算e 模( 竹) 的乘法逆元d ，使得e d = 1r o o d 庐( n ) ； 销毁p ，口，( n ) ，公钥为( e ，仃) ，私钥为d 2 加密：消息m ( n ) ，计算密文c = m 8 m o d n 3 解密：密文c 解密密文得m = c d r o o d 佗 分析密钥选取过程可知，如果能从n 正确分解出p i 目i q ，则不难计算出( n ) ，进一 步依据e 和( 竹) 可解出d 所以如果能有有效的算法对大数进行因子分解，则r s a 密 码体制将被攻破，其安全性是基于大整数因子分解困难性的对因子分解的安全威 胁主要来自两个方面：计算能力的增长( 即计算机速度的提高) 和因子分解算法的不 断改进目前，数域筛选法是一种很有效的因子分解方法，因此当前使用的r s a 密 钥通常都采用1 0 2 4 比特以保证其安全性 2 2 2e i g a m a l 密码体制 e l g a m a 】体制【4 】是由t e 1 g a m a 】于1 9 8 5 年提出的，美1 珩 1 9 9 4 年公布的数字签名 标准( d s s ) 就是e l g 眦a 1 密码体制的一个变体此密码体制应用广泛，在密码学研究 中占有重要地位，是除r s a 体制外另一个目前仍认为安全的、既可用于加密又可用 于数字签名的公钥密码体制e 1 g a m a l 密码体制描述如下： 1 选取密钥 随机选择大素数a 计算乘法群忍的一个生成元g ； 】2 2 2 公钥密码体制第誊预各知识 随机选取z z ；为私钥，计算! ，= 旷m o d p ； 公开公钥为( p ，g ，) 2 加密：消s i n ( p ) ，随机选取七召，计算密文 c 1 = g 女r o o d p 也= m y r o o d p 3 解密：密文( c 1 ，c 2 ) ，计算明文m = 勿 由上述加密过程可知，每个用户除了选取z 作为私钥参数，还要秘密选择一个 随机数七，并且为了安全起见。每次的k 都要重新选择，不能重复使用e 1 g a m a l 体制 的安全性是基于计算有限域上离散对数的困难性，即在已知的条件下，求召上的 解z 在计算上是不可行的，该难题被广泛认为是可以依赖的困难问题 2 2 3 基于身份的公钥密码体制 在传统的基于证书的密码系统中，在使用一个用户的公钥之前，人们需要验证 其证书是否正确、合法，其结果是需要大量的存储空间和计算开销来存储和验证众 多用户的公钥证书为了克服这个缺点，提高系统的效率，s h a m i r 在1 9 8 4 年提出了基 于身份的密码系统( m c ，i d - b a s e d c d ，p t o s y s t e m ) i 儿1 的概念其主要观点是：系统中 不需要证书，可以使用用户的标识如姓名、m 地址、电子邮件地址等作为公钥，用户 的私钥通过一个被称作私钥生成器p k g ( p r i v a t ek e yg e n e r a t o r ) 的可信第三方计算 得到基于身份的密码系统使得用户的公钥能够通过用户的身份信息直接计算出 来，不需要保存每个用户的公钥证书，避免了使用证书带来的存储和管理开销问题， 简化了基于证书的密码系统繁琐的密钥管理过程由此可见，基于身份的密码系统 是基于证书的公钥密码系统很好的替代品基于身份的密码系统中应该满足： 用户之间不用交换密钥： 不需要保持一个公共的证书服务器； 只在系统建立阶段需要可信中心服务 基于身份的密码系统是一个非对称系统，与普通的公钥系统相比不同之处在 于：基于身份的系统中实体公开的身份信息是实体的唯一标识，它起着公钥的作用； 用户的公开数据不需要明显地验证如果用户的公共数据不正确，将会导致使用它 的密码交换失败，如加密产生的密文不能正确解密、签名验证或实体验证失败、密 1 3 2 ，2 公钥密码体制第r - 章预各知识 钥协商双方产生的会话密钥不同等可信第三方用自己的私钥和实体的公开身份信 息计算出该实体的私钥，并安全地传送给用户这对于防伪造和防伪装是必要的，只 有可信中心能从给定地用户身份信息计算出相应的合法私钥 近些年来，各国学者对基于身份的密码系统进行了许多研究，取得了丰富的成 果，各种类型的基于身份的数字签名方案被相继提出继s h a m i r 在1 9 8 4 年给出的一 个基于整数分解困难性的基于身份的签名方案后，1 9 8 9 年l a i h ，l e e 等人提出一个基 于e 1 g a m a l 的基于身份的签名方案附】1 9 9 1 年c h a n g 和l i n 给出一个基于r a b i n 公钥 密码系统的基于身份的签名方案p a r k , k i m 和w o n 在1 9 9 7 年提出第一个基于身 份的群签名方案【斗引 双线性对( b i l i n e a r p a i r i n g ) 在密码学中得到了越来越广泛的应用，它已经成为构 造基于身份的密码系统的有力工具双线性对起初是用于密码攻击的。如代数曲线 上的w m 对和t a r e 对，在椭圆曲线密码中有着重要应用近些年来越来越多的利用 双线性对的基于身份的加密和数字签名方案被设计出来 利用双线性对构造的密码方案中有两个标志性的方案2 0 0 1 年b o n e h 和f r a n k l i n 利用椭圆曲线的双线性对设计出了实用的基于身份的加密方案i b e ( i d - b a s e d e n - c r y p t i o n ) m ，这是第一个高效且可证明安全的基于身份的加密方案实用 b e 公钥 密码体制的提出向公钥密码学增添了新的内容还有一个是b o n e h 。l y n n 和s h a c h a m 提出的基于双线性对的签名方案【4 0 ，这是签名最短的签名方案 在基于双线性对的基于身份的数字签名方案的研究方面：2 0 0 1 年s a k a i 。o h g i s h i 和k a s a h a r a 提出了第一个基于w e i l 对的基于身份的签名方案f 4 0 ；c h a 和c h e o n 提出 了一个可证明安全的基于g a pd i f f i e h e l l m a n 群的基于身份的签名方案【4 跚h e s s 提 出了一个可证明安全的基于双线性对的基于身份的签名方案【4 韧，是这几个