（应用数学专业论文）基于离散对数的无证书数字签名的研究.pdf

硕i ：论文基于离散对数的无证书数7 - 签名的研究 摘要 数字签名是近年来研究的热点，在2 0 0 3 年亚洲密码学会议上，a l - r i y a m i 和 p a t e r s o n 提出了无证书的公钥密码学，该体制一经提出就得到了很多的关注。在无证书 的公钥密码体制中，用户的公钥不需要证书来验证，从而解决了基于证书的密码体制中 的证书管理等问题，减少了存储的空间。同时在无证书公钥密码体制中，用户的私钥是 自己和k g c ( k e yg e n e r a t i o nc e n t e r ) 共同产生的，这也克服了在基于身份的密码体制中 的密钥托管的问题，但是仍然保留了基于身份的公钥密码体制的优点。从而减少了开支， 更加适合在移动环境中的低带宽和低功率下应用。目前的无证书的数字签名大都基于双 线性对映射，效率都不是很高。 本文构造了一个在随机预言模型下可证明安全的基于离散对数( d l p ) 的无证书的数 字签名方案，其安全性是基于离散对数问题，没有使用双线性映射，效率也得到了很大 的提高。在结合无证书密码体制的优点与代理签名的有关知识时，本文还给出了一种代 理签名的无证书数字签名。该代理签名也是基于离散对数可证明安全的一种无证书数字 签名，且其代理密钥是利用s c h n o r r 短签名完成，安全性和效率都得到很大提高。 关键词：数字签名；无证书；公钥密码体制；代理签名；可证明安全；短签名 a b s t r a c t 硕i ：论文 a b s t r a c t d i g i t a ls i g n a t u r ei st h eh o t s p o ti nr e c e n ty e a r s i na s i a c r y p t2 0 0 3 ，a l - r i y a m ia n d p a t e r s o ni n t r o d u c e dan e w p a r a d i g mf o rp u b l i cc r y p t o g r a p h yn a m e dc e r t i f i c a t e l e s sp u b l i c k e yc r y p t o g r a p h y ( c l p k c ) c l - p k cr e c e i v e d ag r e a ta t t e n t i o na f t e r p r o p o s e d i n c e r t i f i c a t e l e s sp u b l i ck e yc r y p t o g r a p h y , i tr e m o v e st h en e c e s s a r yo fc e r t i f i c a t et oe n s u r et h e a u t h e n t i c a t i o no ft h eu s e r sp u b l i ck e yi nt r a d i t i o nc e r t i f i c a t e b a s e dp u b l i ck e yc r y p t o g r a p h y , a n dc u td o w nt h es t o r a g e i na d d i t i o n ，t h eu s e sp r i v a t ek e yd o e sn o ts i n g l yg e n e r a t e db yt h e k g c ( k e yg e n e r a t i o nc e n t e r ) i nt h ec e r t i f i c a t e l e s sp u b l i ck e yc r y p t o g r a p h y , b u tj o i n t l y g e n e r a t e db yt h ek g ca n dt h eu s e r t h a tm a k et h a to n l yt h eu s e rk n o wi t s p r i v a t ek e y i t o v e r c o m e st h ei n h e r e n tk e ye s c r o wp r o b l e mi nt h ei d e n t i t y - b a s e dp u b l i ck e yc r y p t o g r a p h y b u ti n h e r e n tt h em e r i t s i td e c r e a s e st h ee x p e n s e si nt h es y s t e m sw h i c hb e c o m em o r ef l e x i b l e i nt h el o wf r e q u e n c i e s i na l lt h ea v a i l a b l ec e r t i f i c a t e l e s ss i g n a t u r es c h e m e s ，t h e r ea r em a n y b i l i n e a rp a r i n gc o m p u t a t i o n st h a tt h ee f f i c i e n c yi sl o w i nt h i sp a p e r , w ep r o p o s eas i g n a t u r es c h e m e sb a s eo nd i s c r e t el o g a r i t h mp r o b l e m ( d l p ) w h i c hi sp r o v a b l es e c u r eu n d e rt h er a n d o mo r a c l em o d e l w ed on o tu s et h eb i l i n e a rp a i r i n g ， a n dt h ee f f i c i e n c yi si m p r o v e dt o o b a s e do nt h em e r i t so ft h ec e r t i f i c a t e l e s sp u b l i ck e y c r y p t o g r a p h ya n dc o m b i n et h ep r o x ys i g n a t u r e ，w eg i v eap r o x ys i g n a t u r es c h e m e sa n di t s s e c u r ei sa l s ob a s e do nt h ed l ea n do u rp r o x ys e c r e t ek e yu s et h es c h n o r rs h o r ts i g n a t u r e ， t h a tt h ee f f i c i e n c ya n ds e c u r i t yw i l lh a v ea g r e a ti m p r o v e k e yw o r d s ：d i g i t a ls i g n a t u r e ；c e r t i f i c a t e l e s s ；p u b l i ck e yc r y p t o g r a p h y ；p r o x y s i g n a t u r e ；p r o v a b l es e c u r e ；s h o r ts i g n a t u r e i l 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均己在论文 中作了明确的说明。 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：强堡垒 问。年舌月马日 硕一i j 论文基于离散对数的无证书数，签名的研究 第一章绪论 随着计算机网络及通信技术的迅猛发展，人类已经进入了信息社会。利用互联网获 取信息、交换信息及合作已经成为信息社会中一个非常重要的特征。与此同时，由于传 输过程中的公共信道和存储的计算机系统非常脆弱，容易受到各种主动与被动攻击，信 息安全问题日益突出，网络入侵、信息泄密及网络犯罪层出不穷，因此，如何堵住网络 的安全漏洞和消除安全隐患己成为人们十分关心和重视的问题，信息安全已成为信息科 学领域的热点课题。密码技术正是保障信息安全的有效方法之一，不仅可以利用密码来 打乱所传达的信息，以便只有我们所希望的接受着才能真正获取信息，通过密码技术的 使用，现实世界的许多事情，诸如签订合同，签字，发送收据等都可以通过数字信号来 完成。在信息技术的应用过程中，信息是最为宝贵的资源，因特网为信息的传播和获取 提供了极大的便利，它可以使我们不受时间和空间的限制，和任何人在任何地方通过网 络进行信息交流，并且以最快的速度和最短的时间进行交流，各种经济信息更是充斥网 络让人应接不暇，在当今的社会，信息就是生命，信息就是时间和财富。由于信息是共 享的，信息的扩散会产生社会影响，但是错误的消息则可以产生负面影响，因此对此方 向的研究不但具有理论价值，而且具有广泛的实际应用价值。数字签名作为一种非常重 要的密码技术正是在这样的背景下产生的。 本章第一节简单介绍了数字签名的基本概念及其研究意义与现状。第二节介绍无证 书公钥密码学的研究背景，第三节介绍本文研究的主要内容。 1 1 数字签名的研究背景与意义及其基本概念 数字签名的概念f 1 3 d i f f i e s n h e l l m a n t l j 提出，是现代密码学最重要最基本的概念之一。 数字签名的目的等同于手写签名，将签名者的身份和其签署的消息绑定，表示某人己对 消息进行了签字。任何的验证者能够验证消息确实是签名者所签署，而伪造一个用户的 签名却是困难的。可用于消息的完整性认证和消息源的认证，因此在电子政务和电子商 务中具有重要的作用。 1 1 1 数字签名的背景与意义 数字签名是现代密码学领域中一个非常重要的分支，也是信息安全方向一个重要 的研究内容。在日常生活中我们用签名来表示自己的身份，那么在i n t e m e t 上，我们该如 何表示身份昵? 数字签名的提出和其可靠的应用，使得数字签名成为手写签名的有效替 代者。 数字签名是网络通信和网络安全的一种非常特殊的密码认证形式，它包括很多方 笫一章绪论硕i j 论文 面，在实现身份认证方面，可辨别信源的真实性而达到防伪；在数据完整性保护方面； 能抵御数据的篡改或重排以保证完整性；在不可抵赖性方面，使信源事后不可否认以防 其抵赖；一般还使用加密技术保护信息的机密性。以防截听攻击；加人流水号等技术， 可防止重放攻击。特别是其身份鉴别，数据完整性和不可抵赖性在电子商务、电子政务 等领域有很重要的作用。 数字签名体制己经广泛应用于商业、金融、军事等领域，尤其是在网络通信、电子 邮件、电子商务、电子政务和电子购物等方面。数字签名还可以应用到访问控制、软件 验证、病毒检测等不同领域。在网络通信中，数据完整性的检验、身份鉴别、身份证明、 防否认等方面，功能独特，满足这些要求的最好的办法就是使用数字签名技术。由于数 字签名具有认证性，完整性和不可否认性等优点，使得数字签名促进了信息化的发展。 同时信息的发展也推动着数字签名的发展。由此可见数字签名技术在网络通信和信息安 全中有着重要作用和特殊位置。数字签名作为信息安全的一项重要技术，其应用领域日 益广泛。由于许多领域对数字签名技术提出了新的应用需求，在未来的信息领域中这一 技术仍有着广阔的发展前景。特别是对签名方案的设计方法和安全性分析以及对签名方 案的攻击是这一领域研究的热点。因此对数字签名的研究具有很强的适用性和远大的前 景，特别是互联网技术的普及，它也为i n t e m e t 的安全起着很好的技术支撑作用。 1 1 2 数字签名的基本概念 数字签名的定义： 数字签名方案通常包括三个主要过程：系统的初始化过程，签名产生过程和签名验 证过程。系统的初始化过程产生数字签名方案用到的一切参数；签名产生过程中，用户 利用给定的算法对消息产生签名；签名验证过程中，验证者利用公丌的验证方法对给定 的消息进行验证，得出签名是否有效的结论。通常数字签名有三个实体部分组成：密钥 生成算法、签名生成算法和签名验证算法。 一个数字签名方案是由一个五元组( m ，s ，k ，v ) 组成，它满足下列条件： ( 1 ) m 是一个可能消息的有限集； ( 2 ) s 是一个可能签名的有限集； ( 3 ) 密钥空间k 是一个可能密钥的有限集； ( 4 ) 对每一个k k ，m m ，这罩有一个签名算法s i g k s 和相应的验证算法 v e r k v ，每一个s i g k ：m0s 和v e r k ：m s 斗 真，假) 是一个对每一个消息m m 和每一个签名s s ，满足下列方程的函数：v e r ( 聊，s ) = 蠢：5 若昔：。s s i = s i g g ( ( m 删) ) 。 ( 5 ) 密钥生成算法k g ( k e yg e n e r a t i o n ) ：该算法是一个概率多项式算法，输入的是系 统的安全参数，输出用户的私钥s 七和相应的公钥础，其中妇，p k k 。 2 硕l 论文慕于离散对数的无i j f 书数字签名的研究 ( 6 ) 签名生成算法：该算法是一个概率多项式算法，输入用户的私钥睹和待签名的 消息m ，输出对应于私钥的关于该消息的签名o - 。 ( 7 ) 签名验证算法：该算法是一个概率多项式算法，输入是被签名的消息以及验证 对应于签名者的公钥，输出是真( t ) 表示签名有效或假( f ) 表示签名无效。 此外数字签名还必须至少满足以下三个性质： ( 1 ) j 下确性 我们称一个签名是正确的：如果签名人正确执行签名算法并得到签名仃s ，且盯不 能通过验证算法的概率是可忽略的，即对任意的常数s 和充分大的刀， p r 玩厂痧( o r ，m ，p k ) = f 】 n 。 ( 2 ) 不可伪造性 除签名人外，其他任何人不可能伪造消息的签名，因为签名密钥有公钥和私钥这对 密钥对组成，私钥只有签名人自己知道，其他任何人不可能构造出正确的签名数据。 ( 3 ) 不可否认性 对于签名者已经签发的消息，因为用到了签名者的私钥，他就不能否认自己对某个 消息的签名。 1 1 3 数字签名的发展概述 1 9 7 8 年，r i v e s t ，s h a m i r 矛h a d l e m a n l 2 】基于大整数的分解问题，即给定一个大的整数n ， 求两个大素数p 和q ，使得n = p q 。当n 很大时，分解这个因式是非常困难的。他们首先 提出了第一个具体的签名算法，即r s a 签名算法。从此以后，涌现出了大量基于不同问 题的新颖的签名算法方案，如基于有限域离散对数问题的e 1 g a m a l 签名方案1 3 j ，s c h n o r r 签名【4 】，d s a 签名【5 1 ，o k 锄o t o 签名f 6 】应用零知识证明思想的f i a t s h a m i r 签- 名【7 1 等。 1 9 8 6 年矛n 1 9 8 7 年，m i l l e r 和k o b l i t z l 8 分别独立建立了椭圆曲线密码体制，丌创了基 于椭圆曲线和超椭圆曲线的签名算法。椭圆曲线上的签名体制多基于椭圆曲线离散对数 问题，这和e l g 锄a l 签名有异曲同工之处，之自 许多基于离散对数的签名算法都可平移 到椭圆曲线密码体制下，其中最著名的算法是e c d s a 签名，其效率要优于d s a 的签名。 除了对具体算法的分析和设计以外，还有许多其他针对数字签名的出色的原创性的 工作，特别是数字签名的安全模型的研究和证明等方面。1 9 8 6 年，g o l d w a s s e r ，m i c a l i 和r i v e s t 提出了可证明安全性的思想，为数字签名的设计和分析提供了理论背景。b e l l a r e 和r o g a w a y 为) j h 密签名算法的设计引入了随机预言模型( r a n d o mo r a c l em o d e l ) 的概念， 这为设计高效的加密方案和签名方案提供了很好的方法。 随着电子通信的发展和对数字签名的进一步深入研究，一般的签名概念并不能满足 实际应用中涌现出的越来越多的问题。大量具有附加性质的签名概念也被相继的提出， 例如： 3 第一帝绪论 硕 二论文 ( 1 ) 1 9 8 2 年，c h a u m 提出了盲签名1 1 3 】，在盲签名中，消息的内容对签名者来说是盲化的， 即签名人是不知道消息内容的，而且签名被接收者泄露后，签名者也不能追踪签名。 ( 2 ) 1 9 9 1 年，d e s m e d t y 和f r a n k e l y 提出了门限签名【1 5 】，一个( t ，n ) 门限签名体制是指把 一个秘密s 分拆成n 个分秘密，分给每个成员，使得至少t 个成员才可以完成签名，而利用 公钥可以对签名进行验证。 ( 3 ) c h a u m 和h e y s t 在1 9 9 1 年提出了群签名【l 酬。_ 个群签名方案指任何群里面的成员匿 名代表群来进行签名，当该签名一旦发生纠纷，群管理员可以打开该签名从而知道签名 者的相关信息。 ( 4 ) c h a u m 在1 9 9 4 年提出了指定确认者签名1 1 。在这种签名方案中，签名者可以指定 某一确认者对签名进行确认，如果签名者无法验证签名，指定确认者也能对签名的有效 性进行确认。 ( 6 ) m a m b o ，u s u d a $ 1 1 0 k a m o t o 于1 9 9 5 年提出了代理签名l i 引，代理签名的目的是当某签 名人( 这里称为签名授权人) 因公务或其它事情等原因不能行使签名权力时，将签名权委 派给其它人替自己行使签名权。 ( 7 ) 2 0 0 1 年，s h a m i r 署l t a u m a n 提出了环签名。环签名实际上是对群签名的一种简化， 它仅包括坏成员而没有管理者，不需要群的建立过程，也无法撤销真实签名者的匿名性。 ( 8 ) 2 0 0 3 年，a l r i y a m i 和p a t e r s o n 在a s i a c r y p t 2 0 0 3 上首次提出了无证书公钥密码 学( c e r t i f i c a t e l e s sp u b l i ck e yc r y p t o g r a p h y ，c l p k c ) 1 9 ，目洲基于无证书公钥密码体制 也延伸许多签名概念。 以上的概一些概念可以进一步的组合，从而为满足不同的需求成为更加复杂的签名 概念，如群盲签名，门限代理签名等。对这些签名算法的研究与设计吸引了大量的优秀密 码学家，成为数字签名研究中非常活跃的领域之一。 1 1 4 数字签名的分类 ( 1 ) 基于签名用户的分类 一般分为单用户签名和多用户签名的数字签名方案。多用户的签名方案又称多重数 字签名方案。根据签名过程不同，多重签名方案又分为有序多重数字签名方案和广播多 重数字签名方案。 ( 2 ) 基于数学难题的分类 根据数字签名所基于的数学难题，数字签名方案可分为基于离散对数问题的签名方 案，基于大素因子分解的签名方案，基于椭圆曲线离散对数问题的签名方案，基于离散 对数和素因子分解的签名方案，基于二次剩余问题的签名方案等。 ( 3 ) 基于数字签名是否具有消息恢复特性的分类 一类是不具有消息自动恢复的特性，另一类是具有消息自动恢复的特性。 4 硕十论文基于离散对数的无i f e 书数字签名的研究 ( 4 ) 基于签名人对消息是否可见的分类 分为普通数字签名方案和盲签名方案。盲签名方案表示签名者对消息不见，可但事 后可以证明消息的存在。又根据签名者是否可以对消息拥有这进行追踪分为若盲签名和 强盲签名。 ( 5 ) 基于签名人是否受别人委托的分类 分为普通数字签名方案和代理签名方案。如果授权的不是一个人，而是多个人，这 时的签名方案称为代理多重数字签名。 ( 6 ) 其它特殊的数字签名方案 由于数字签名的应用领域广泛且多样，因此产生了许多具有特殊要求的签名方案， 如盲签名，代理签名，群签名，环签名，并发签名和同时签名等。 1 1 5 数字签名的安全性及其攻击模型 数字签名的安全性都是基于某些数学难题，这些数学难题有：有限域上离散对数 问题，这是大部分签名方案设计的基础。椭圆曲线问题，这是近几年研究的热点。 大合数的因子分解，主要有r s a 和r a b i n 体制。 ( 1 ) 对于数字签名安全性的证明方法有以下几种： 可证明安全性 利用计算复杂行理论，将数字签名的安全性下转化为一些已知的难题，如上面提到 的一些难题。但这种方法被证明安全的数字签名方案一般效率都不高。 利用相互转换证明 把数字签名方案转化成一些公认安全的数字签名的方法。 基于随机问答器模型( r a n d o mo r a c l em o d e l ) 该方法是将h a s h 函数看成一个随机函数，并给出相应的模型。对任何一个询问，它 产生一个随机值作为回答。若h a s h 函数没有弱点的话，基于此模型的证明能够保证一个 签名方案的总体设计的安全性。 ( 2 ) 数字签名的攻击模型 对数字签名方案的基本攻击可分两类： 唯密钥攻击( 无消息攻击n m a ) ：攻击者只知道签名人的公钥，而没有其他任何消 息。 已知消息攻击( k n o w n m e s s a g ea t t a c k ) ：攻击者不仅知道签名人的公钥，而且还知道 对应于该签名者的一些其他消息。 对于已知消息攻击又可以再细分为以下几种： 已知简单消息攻击( p l a i nk n o w n m e s s a g ea t t a c k ) ：敌方可以访问一些消息如 ，肌2 ，屹，m n 的签名，攻击者已知这些消息，但不能随便选择哪些消息的签名。 第一章绪论硕f ：论文 一般选择消息攻击( g e n e r i cc h o s e n m e s s a g ea t t a c k ) ：攻击者在知道签名者的公钥 之前，可以选择一些消息并请求服务器得到这些消息的正确签名对，但在知道签名认定 公钥之后就不能再请求签名服务了，这类攻击不针对特定签名人。 定向选择消息攻击( o r i e n t e dc h o s e n m e s s a g ea t t a c k ) ：这类攻击类似于一般的选择 消息攻击，只是这种攻击是针对某一定向用户。 自适应选择消息攻击( a d a p t i v e l yc h o s e n m e s s a g ea t t a c k ) ：攻击者可以将用户当作 一个“问答器”，不仅可以写消息并请求服务签名以得到相应的消息签名对，而且还 可以根据已知的消息签名对来选择新的消息并请求相应的签名服务。 以上四种攻击类型是向下逐渐增高的，自适应选择消息攻击是可以采用的最高级别 的攻击。 对数字签名方案的攻击目标是伪造签名，而攻击目标也可以分为3 个层次： 完全攻破( t o t a l b r e a k ) ：攻击者可以对任何消息产生有效签名，因为这种攻击已 经恢复出签名人的私钥。 选择性伪造( c h o s e n m e s s a g ef o r g e r y ) ：攻击者可以对自己选择的一些消息产生有效 的签名。 存在性伪造( e x i s t e n t i a lf o r g e r y ) ：攻击者可以产生一个有效的消息签名对，但该 消息不一定是有意义的，可能只是随即的比特串。 由上面的可知，此三种伪造是向下包含的，相对来说要做到完全攻破是相对困难的， 而存在性伪造是相对容易的。 1 2 无证书公钥密码学 1 2 1 公钥密码系统 公钥密码系统( p k i ) 是- - 季d e 标准的密钥管理平台，它给网络应用中提供的密钥和 证书等提供了很好的透明度和公正性，带来了很大的便利。通常p k i 由以下几部分组成： 证书颁发机构( c e r t i f i c a t i o na u t h o r i t y ，c a ) 、认证机构( r e g i s t r a t i o na u t h o r i t y ，r a ) 、 证书库、证书作废处理系统、密钥备份及恢复系统、p k i 应用接口系统等。 在p k i 中，用户的公钥是一个随机的比特串，这就需要为用户的公钥进行认证，这 里公钥的认证是通过使用证书来实现的，证书是证书机构即证书颁发机构( c a ) ，根 据用户的信息为用户颁发的。 随着用户的增多，p k i 的规模扩大，证书的数量也将随着不断的增加，此时若仅用 一个c a 来颁发证书，那么这个c a 将会成为认证过程中的瓶颈，目前解决这种问题的方 法大多采用层次结构的认证方式，c a 将权利授权于更多的c a 来完成认证。 在p k i 的数字签名方案中，要验证一个用户签名的有效性，首先必须要验证签名人 6 硕 ：论文 基于离散对数的无证书数字签名的研究 公钥的有效性，即验证公钥证书的有效性，在多层次的c a 结构中，上一层的c a 为下一 层的c a 的公钥提供认证，直到完成对所有用户的公钥提供认证，即在验证用户公钥的 有效性时就需要对一系列的证书进行验证，这将花费大量的时间，效率不高。同时在p k i 中还存在着管理问题，如证书的存储，撤销和发布等一些问题。 1 2 2 基于身份的公钥密码系统 在基于证书的公钥密码系统中，证书颁发机构( c a ) 为每一个用户发行一个与其 所分配的公钥相匹配的公钥证书。公钥证书的产生是一个复杂的过程，人们在使用一个 用户的公钥时，必须首先验证其证书是否正确，合法，有效。由上面的讨论我们知道在 基于证书的公钥密码系统中( p k i ) ，需要很大的存储空间来存储和验证众多用户的公 钥证书。在认证签名方案中，往往需要从证书颁发机构( c a ) 处获取通信方的公开密 钥，因此系统将会保存大量的公钥及公钥证书。为了克服这个缺点，提高系统的效率， s h a m i r l 2 2 1 在1 9 8 4 年提出了基于身份的公钥密码体制的概念( i d p k c ) ，同时给出了一 个基于整数分解困难性的基于身份的签名方案。在基于身份的密码体制中，用户的公钥 可以是用户的身份证号，姓名，地址，e m a i l 等，用户的私钥由认证中心产生。基于身 份的密码体制使得任意两个用户都可以安全通信，不需要交换公钥证书，因为公钥就是 用户的身份信息，从而不必保存公钥证书列表，也不必使用在线的第三方，只需一个可 信的密钥发行中心为每个第一次接入系统的用户发行一个私钥就行了。 可见，基于身份密码系统可作为p k i 的很好的替代品。自1 9 8 4 年s h a m i r 的开创性工 作以来，已有许多各种类型的基于身份的数字签名方案相继被提出。 在基于身份的公钥密码系统中，用户的私钥是由一个可信的第三方，称为密钥生成 器p k g ( p r i v a t ek e yg e n e r a t o r s ) 生成的。因而，p k g 矢i 道所有用户的私钥，也就是说， 基于身份的公钥密码系统具有密钥托管的问题，p k g 可以冒充系统的任何用户进行操 作。与基于证书的公钥系统不同，基于身份的公钥密码系统不能提供真正意义上的不可 否认性。用户可以否认自己的签名，因为p k g 也可以这样运行。产生这个问题的主要原 因是用户的私钥是有p k g 独立生成的。与p 一样，若只用一个p k g 同样会产生瓶颈问 题。目前对这方面的解决方法主要是采用( t ，n ) 门限来避免，但是这并不能从根本上解 决，因为多个p k g 联合仍然可以生成系统的主密钥，从而可以生成用户的私钥。 1 2 3 无证书公钥密码系统 无证书公钥密码( c l p k c ) 是a l r i y a m i 和p a t e r s o n 1 9 j 在2 0 0 3 年亚密会上提出来 的。这种密钥体制不需要公钥证书，降低了基于p k i 的密码体制中的证书认证消耗等复 杂度，是传统的基于p k i 的公钥密码体制和基于身份的公钥密码体制( i d p k c ) 的折中。 能有效的避免i d p k c 中密钥托管问题，同时在应用中带来了极大的便利。基于这些优 点，从其提出就得到了广泛的关注。并且根据需要提出了各种安全模型，以及签名方案 7 第一章绪论 硕l ? 论文 等。无证书的公钥方案系统需要一个可信第三方( k g c ) ，但不同于基于身份的密码体 制下的p k g ，这罩k g c 是根据用户的身份i d 为用户生成部分私钥，用户自己再产生部分 私钥，将k g c 与自己的私钥合并生成最后的私钥。因此只有用户自己知道自己的私钥， k g c 不知道用户的私钥，从而解决了密钥的托管问题。在无证书公钥系统中，用户的公 钥不再是用户的惟一可以识别的身份，而是需要额外的公钥。此外，在无证书公钥系统 中，不再需要证书来对用户的公钥和用户的身份进行绑定，从而克服了基于证书公钥系 统中存在的证书管理问题。 由此可见，无证书公钥系统能从根本上解决上面提到的基于证书公钥系统中的证书 管理问题和基于身份公钥系统中的密钥托管问题。 1 3 本文所做的主要工作 本文在分析已有的无证书数字签名的基础上，归纳出了无证书数字签名的一些性 质，针对数字签名的效率和安全性，取得了以下成果： ( 1 ) 提出了一种新型的无证书的数字签名方案，与目前已有的基于双线性映射的 方案不同，该方案中没有使用双线性映射，是基于离散对数问题作为安全性基础的方案。 ( 2 ) 对提出的方案进行了安全性的证明，在随机预言模型下，该方案是可证明安 全的。 ( 3 ) 分析了代理签名的相关知识，结合代理签名，提出了基于离散对数的无证书 代理签名方案。 ( 4 ) 对提出的无证书代理签名方案进行了详细的安全性证明，且在随机预言模型 下也是可证明安全的。 8 硕 ：论文基于离散对数的无证书数，签名的研究 2 1 预备知识 第二章基础知识 2 1 1 符号说明 下面给出本文用到的一些符号说明。 ( 1 ) 乙表示模q 的整数集合； ( 2 ) z g 表示模g 的整数乘法群，即乙 o ) ； ( 3 ) x 。a 表示均匀随机地从集合彳中选取元素； ( 4 ) 0 表示字符串连接符； ( 5 ) p r ( a 1 表示事件彳发生的概率。 2 1 2 单向函数( o n e - w a yf u n c t i o n ) 与哈希函数( h a s hf u n c t i o n ) ( 1 ) 单向函数 单向函数在密码算法的设计中经常用到，单向函数是一种易于计算而难于求逆的函 数。若说函数f ( x ) 是单向函数，则意味着：存在一个多项式时间算法a ，使得当输入为 x 时算法彳的输出为f ( x ) ( 即a ( x ) = f ( x ) ) ；f ( x ) 难求逆是指，给定一个输入y ，要求 在厂作用下y 的原象，在概率多项式时间算法内，能计算出的概率是可忽略的( 对y 的长 度) 。因此，下面给出单向函数的数学定义。 定义2 1 单向函数：设函数厂： o ，1 ) j o ，1 ) 刀以任意长度的消息m 作为输入，返回 固定长度为n 的值。如果满足以下两个条件： 1 ) 易于计算：存在一个确定的多项式时间算法a ，使得当输入为x 时算法a 的输出为 厂( x ) ( 即彳( x ) = 厂( x ) ) ； 2 ) 难于求逆：对于每一个概率多项式时间算法a ，每一个正多项式p ( n ) 和足够大的 刀，都有：e r a 。( 厂刀) ，1 刀) f - i ( ( ) ) 】 爿可，则称函数厂是单向函数。其中u 聆是服从 o ，1 1 聆上的均匀分布的随机变量。1 即是系统参数。 ( 2 ) 哈希( h a s h ) 函数 h a s h 函数也被称为散列函数、杂凑函数，是密码学中的重要工具。h a s h 函数是一个 确定的函数，就是将任意长的比特串映射为定长或任意比特串的杂凑值，严格地说，它 并不是一种密码算法，但是却和公钥密码体制有密切的关系，本质上是一种数学变换的 函数，而且其过程也是不可逆的。 9 第二章皋础知识 硕i ：论文 本文所讲的h a s h 函数都是单向的散列函数， 原像难解：存在h a s h 函数h ：x 一】，和y y ， 其安全性定义必须满足： 求x x 使得h ( x ) = y 是困难的，即任 意的多项式时间算法a 输出y ，使得( x ) = y 的概率是可忽略的。 无第二原象：设h a s h 函数h ：x 一】，己知x x ，求x ，使得h ( x ) = h ( x ) 在计算上 是不可行的，即任意的多项式时间算法a 输出x ，x ，使得日( z ) = h ( x ) 的概率是可忽略 的。 强无碰撞：设h a s h 函数h ：x 专】，求x x ，使得h ( x ) = h ( x ) 在计算上是可行的， 即任意的多项式时问算法a 输出x ，x ，使得h ( x ) = h ( x ) 成立的概率可忽略。 很容易看出，如果h a s h 函数是强无碰撞函数，则它也是无第二原象函数。也就是说 如果h a s h 函数是可求第二原象的，那么它一定是可碰撞的。 2 2 数学难题 大多数公钥密码算法都是基于以下数学难题： ( 1 ) 大整数分解问题：给定整数n 为两个大素数的乘积，确定这两个素因子 p 和g ，使得n = p q 。 ( 2 ) 离散对数问题( d l p ，d i s c r e t el o g a r i t h mp r o b l e m ) ：设p 是z ：中的大素数，g 是z ：的生 成元，给定n = 9 4 ，去计算a = l o g 。n 是困难的。 ( 3 ) 椭圆曲线离散对数问题：给定椭圆曲线e 上的一个点p ，对任意的点q ，如果存在 整数m 使q = m p ，则求解m 是困难的。 ( 4 ) 二次剩余问题：给定整数刀和口( 0 a ，7 ) ，判定是否存在整数 w ，( o w o ) 称该算法是时间多项式阶的；如果 r ( 聊) ：0 f 口p 【胛j1 ( 口1 ) ，( p ( 胛) 是多项式) 则称该算法是时间指数阶的。一般我们约定 若破译一个密码体制所需的时间是指数阶的，则称它是计算上安全的。 ( 2 ) 问题的复杂性 算法复杂度为多项式时间的问题我们称为p 类问题，在多项式时间内可以用非确定 第_ 二章幕础知识 硕l j 论文 性算法求解的问题称为n p 问题。所有的p 类问题都是属于n p 问题的，目前仍旧不知道p 是否等于n p 。但是，n p 问题不一定都是难解的问题。 后来人们发现还有一系列的特殊n p 问题，这类问题的特殊性质使得很多人相信p n p ，目前还无法证明。这类特殊的n p 问题就是n p 完全问题( n p c 问题，c 代表c o m p l e t e ) 。 n p c 问题是n p 类问题中困难最大的一类问题，不知道任何确定性算法在多项式时间内求 解该问题。现有的密码算法都是基于n p c 问题，破译一个密码算法就相当于求解一个 n p c 问题。 2 5 分叉引理 p o i n t c h e v a l 和s t e m 4 1 1 于2 0 0 0 年提出了一种新的关于数字签名的安全性证明方法， 即分叉引理。 分叉引理：在随机预言模型下，对于一个普通的签名方案，让f 是一个仅输入数据 的图灵机，假设f 在有效的时间内以可忽略的概率产生有效的签名( 聊，仃，h ) ，其中h 是哈 希函数。如果签名盯是在不知道密钥的情况下，以不可忽略的概率被模仿出，那么即有 另外的机器以控制形如f 的形式通过替换随机签署来得到新的有效的签名( 聊，仃，h 。) ，其 幸宰 中盯仃，h h 。 1 2 硕i j 论文 基于离散对数的无证书数，签名的研究 第三章无证书的数字签名 3 1 无证书数字签名的研究现状 a l r i y a m i 矛i p a t e r s o n 于2 0 0 3 年在亚密会上提出了无证书密码掣1 9 j ，并且利用椭圆曲 线上的双线性对构造出了无证书的公钥签名体制和密钥交换方案，并证明了在推广的双 线性对d i f f i e h e l l m a n 问题( g b d h p ) 下，对不可区分选择密文攻击( r n d c c a ) 是安全的。 基于该公钥体制所建立的签名体制不存在证书的管理问题，也没有密钥托管问题。这种 新体制虽然仍然需要一个可信第三方k g c ，但与基于身份签名体制中的k g c 不同的是， 它不知道用户的完整私钥，只能得到用户的部分私钥，用户的完整私钥是用户利用自己 选取的秘密值和部分私钥共同产生的。 在文献i l 叫中作者给出加密方案的安全定义和敌手模型，但并未给出签名方案的安全 性定义，也未对其签名方案进行安全性分析。在无证书签名中，张福泰等在这方面做卓 越的成就。2 0 0 5 年z h a n g 等在文献【2 0 j 提出上面的签名方案是不安全的，并给出上面签名 方案的一个替换公钥攻击，攻击者可以针对某用户对任意消息成功伪造签名。z h a n g 等 还在文献【2 0 j 中给出无证书签名方案的敌手模型，并给出一个改进的方案，同时也证明了 他们所提的改进方案在所提模型下是安全的。y u m 矛l l e e 在2 0 0 4 年提出了无证书签名方 案的一般性构造方法1 2 ，他们构造无证书签名方案是通过传统的数字签名方案和基于身 份的签名方案来实现的，先对消息做传统的数字签名，再对所得到的签名做基于身份的 数字签名，最终所得到一个有序双重签名。显然他们的签名方案效率低。他们还声称只 要所用的传统的签名方案和基于身份的签名方案在选择消息攻击下是存在不可伪造的， 那么他们的方案是安全的。然而b e s s i e 等人对y u m 禾l l e e 的方案给出了公钥替换攻击1 2 2 1 ， 并改进了原方案。此外，还定义了一种新的简化的安全模型，并证明改进方案在该安全 模型下是安全的。但改进后的方案仍是一个有序双重签名。2 0 0 5 年l i 等1 2 3 】给出了一个基 于双线性对的无证书的签名方案，其中的代理签名方案主要是基于文酬1 9 l 的思想。而文 献i l9 】的签名方案是不可抵御替换公钥攻击的。此时的替换公钥需要替换原始签名人和代 理签名人的公钥。h u a n g 等人1 2 4 j 在2 0 0 6 年首次提出无证书指定验证人签名的概念，并提出 一个具体的签名方案。该签名方案基于g b d h 困难性假设，并且在随机预言机模型下是 可证明安全的。g o r a n t l a 等1 2 5 j 也基于双线性映射构造了一个高效的无证书的数字签名， 整个签名方案中只需要3 个p a i r i n g 对的运算。文献【2 6 j 对上面的方案给出了一个替换公钥 攻击，且给出了一个改进的方法，可是遗憾的是，效率上却增加了一个“对”的运算且 也没有给出相应的安全性证明。z h a n g 等【2 7 】给出了一个无证书签名方案的安全性模型， 并给出一个可证明安全的无证书签名方案。该方案的效率得到了较大的提高，且方案构 造了一个紧的归约证明，该证明不需要引用分叉引理。 l3 第三章无证书的数字签名硕1 j 论文 3 2 无证书数字签名的一般性定义 一般地，一个无证书的数字签名由7 个算法和三个实体组成。7 个算法分别是：系 统生成( s e t u p ) 、部分私钥生成( p a r t i a l p r i v a t e k e y ) 、密钥值生成 ( s e t - s e c r e t - v a l u e ) 、私钥生成( s e t p r i v a t e k e y ) 、公钥生成( s e t p u b l i c k e y ) 、 签名( s i g n ) 和验证( v e r i f y ) 。三个实体是：密钥生成中心( k g c ) 、签名人、验证 人。 7 个算法分别是： ( 1 ) 系统生成( s e t u p ) ：这是一个概率多项式时间算法，通常由密钥生成中心k g c 运 行，是主密钥和系统参数生成的算法。输入安全参数1 ，返回系统主密钥s 和系统公开 参数p a r a m s ，k g c 公布系统参数p a r a m s ，秘密保存系统主密钥s 。 ( 2 ) 部分私钥生成( p a r t i a l - p r i v a t e - k e y - e x t r a c t ) ：这是一个概率多项式时间算法， 也是部分私钥发布算法，通常由密钥生成中心k g c 运行，输入用户身份m 。和系统公开 参数p a r a m s ，利用系统主密钥s ，为用户生成其部分私钥d 。 ( 3 ) 密钥值生成( s e t - s e c r e t - v a l u e ) ：该算法是一个概率多项式时间算法，输入系统 公丌参数p a r a m s 和用户的身份信息以，产生用户码的秘密值乃。 ( 4 ) 私钥生成( s e t - p r i v a t e - k e y ) ：该算法是一个概率多项式时间算法，输入系统公 开参数p a r a m s 、用户的部分私钥d - 和用户的秘密值乃，产生用户哦的私钥s 彳。 ( 5 ) 公钥生成( s e t - p u b l i c - k e y ) ：该算法是一个概率多项式时间算法，输入系统公 丌参数p a r a