（计算数学专业论文）基于椭圆曲线上的数字签名、签密方案的研究.pdf

摘要 摘要 随着信息技术的高速发展和计算机网络技术的广泛应用，信息安全问题显得 越来越重要，已经成为国内外计算机和网络应用领域普遍关注的热门研究课题。 数字签名作为认证的主要手段，为信息安全提供了重要的技术支撑。 1 9 8 5 年k o b l i t z 和m i l e r 分别提出在椭圆曲线上构造密码系统( e e c ) 的思想 【- l 【：l ，基于椭圆曲线上的具有签密功能的数字签名方案整合了加密、解密、数字 签名三种技术，比单独进行加密、解密、数字签名节省了计算量和通信成本【，1 。 本文对椭圆曲线上的基于证书和基于身份的数字签名方案进行了深入地研究。主 要工作如下： 介绍了椭圆曲线公钥密码系统理论和基于证书和基于身份的数字签名理论。 在基于证书的椭圆曲线上的数字签名和签密方案中，选取了具有代表性的赵 的数字签密方案，指出了赵的方案不完全满足数字签密的安全特性。针对赵方案 的缺陷，提出了一种理想的数字签密方案，此方案满足消息的机密性、完整性、 签名方程的不可伪造、可身份认证、防抵赖、前向安全性、密文的公开验证性， 且能抵抗b o b 的恶意伪造攻击等8 项安全性能。 利用椭圆曲线上双线性对的性质，另辟新径，构造了一个新的签名方案。这 种方案可以同时满足公开验证性和前向安全性及其他安全特性，不需要利用双私 钥，并把这种签名思想应用到基于身份的门限签密方案中，从而使得基于身份的 门限签密方案也同时具有前向安全性和公开验证性且满足其他特性。 通过对基于证书的公钥密码体系与基于身份的公钥密码体系的比较，指出了 现有的基于身份的公钥密码体系的优点及存在的问题。利用椭圆曲线上双线性对 的性质以及基于椭圆曲线上的c d l p 难解问题和双线性对上c d h p 难解问题， 提出了一个不需要用户公钥证书，也不需要密钥托管的密钥分发新协议，并结合 c h a c h e o n 【4j 签名给出了安全性和性能分析。 关键词：公钥证书；基于身份；双线性对；密钥托管；密钥分发协议 摘要 t h er e s e a r c ho n d i g i t a ls i g n a t u r es c h e m e sa n ds i g n c r y p t i o n s c h e m e sb a s e do ne 1 1 i p t i cc u e s a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fi n f b n n a t i o nt e c h n i q u ea n dt h el a r g e - s c a l e a p p i i c a t i o no fn e t w o r kt e c h n i q u e ，i n f o 咖a t i o ns e c u r i t yi sb e c o m i n gm o r ea n dm o r e i n l p o r t a n t ，a n di sb e c o m i n gag e n e r a l l yc o n c e r n e dr e s e a r c ht o p i ci nd o m e s t i ca n d i n t e m a t i o n a lc o m p u t e r 锄dn e t w o r ka p p l i c a t i o nf i e l d a st h em a i nm e a n so ft h e a u t h e n t i c a t i o n ， t h e d i g j t a ls i g n a t u r e h a sp i d v i d e da ni m p o r t a n t t e c h n i q u e f b r i n f o 册a t i o ns e c u r i t y 1 n1 9 8 5 ，k o b l i t za n dm i l l e ri n d e p e n d e n t l yp r o p o s e du s i n gt h eg r o u po fp o i n t so n 柚e l l i p t i cc u ed e f i n e do v e raf i n i t e f i e l dt oc o n s t r u c tc r y p t o s y s t e m 【1 】【2 1 ，w h i c hi s e l l i p t i cc i l e sc r y p t o s y s t e m s ( e c c ) t h es i g l l c r y p t i o ns c h e m eb a s e do ne l l i p t i cc u e s c 0 m b i n e se n c r y p t i o n 、 d e c r y p t i o n 、d i 舀t a ls i g n a t u r et e c h n o l o g y ，w h i c hn e e d sl e s s c o m m u n i c a t i o n锄dc o m p u t a t i o nt h a n e n c r y p t i o n 、d e c r y p t i o n 、d i g i t a ls i g i l a t u r e s e p a r a t e i y 【3 】i n t h i s p a p e r ， t h ec e n i f i c a t e b a s e d d i g i t a ls i g n a t u r e s c h e m ea n d i d e n t i t y - b a s e dd i g i t a ls i g n a t u r es c h e m ea r ed i s c u s s e d 7 i l em a i nw o r k sa r ea sf o l l o w s ： t h ep u b l i ck e yc r y p t o s y s t e m sa n dt h ec e r t i f i c a t e b a s e dd i 酉t a ls i g n a t u r es c h e m e 锄d i d e n t i t y - b a s e dd i 舀t a ls i 印a t u r es c h e m eo ne l l i p t i cc u ea r ci n t r o d u c e d a m o n gt h ec e n i f i c a t e b a s e dd i g i t a ls i g n c r y p t i o n s c h e m e sb a s e d0 n e l l i p t i c c u r v e s ，a sae x a m p l eo fz h a o sd i g i t a ls i g n c r y p t i o ns c h e m e ，t h ep a p e rd e s c r i b e st h a t z h a o ss c h e m ed o e sn o ta l l s a t i s f ys e c u r er e q u i r e m e n t so fd i g “a ls i g n c r y p t i o n s c h e m e s t bg e to v e rt h ed r a w b a c k so fz h a o ss c h e m e ，t h ep a p e rp r o p o s e da ni d e a l d i g i t a ls i g n c r y p t i o ns c h e m e w h i c hs a t i s f i e st h ec o n f i d e n t i a l i t y 、 i n t e g r a l i t y 、 u n f b r g e a b i l i t ys i g n a t u r e 、 a u t h e n t i c a t i o n 、 n o n - r e p u d i a t i o n 、f 6 r 、a r ds e c u r i t y 、p u b l i c v e r i f i c a t j o no fc i p h e r 、r e s i s tb o b se v i lf o 唱es j g n a t u r es c h e m e t h ep a p e rp r o p o s e san e wd i g i t a ls i g n a t u r es c h e m eb a s e do nt h ep r o p e n i e so f b i l i n e a rp a i r i n g ，t h es c h e m es a t i s f i e ss e c u r i t yo fd i g i t a ls i g n c r y p t i o ns i m u l t a n e o u s l y ； s u c ha sp u b l i cv e r i f i c a t i o na n df b n ，a r ds e c u r i t y ，w h i c hd o e sn o tn e e dd o u b l ep r i v a t e k e y s a n dt h e n ，a p p l y i n gt h i st e c h n o l o g yt oi d e n t i t y - b a s e dt h r e s h o l ds i g n c r y p t i o n i l 摘要 s c h e m e ，s e c u r i t yo fs c h e m ei ss a m e ( 、o m p a r i n gi d e n t i t y _ b a s e dc r y p t o s y s t e m sw i t hc e r t i f i c a t e - b a s e dc r y p t o s y s t e m s ， t h ea d v a n t a g e sa n di n h e r e n td r a w b a c k s0 fe x i s t e n ti d e n t i t y b a s e dc r y p l o s y s t e m sa r e a n a l y z e d a n dt h e n ，an e w s e c u r ek e yi s s u i n gp r o t o c o lb a s e do nt h ed i f f i c u l tp r o b l e m o fe l l i p s e ( c d l p c d h p ) a n dt h ep r o p e n i e so fb i l i n e a rp a i “n ga r ep r o p o s e d ，w h i c h d o e s n tr e q u i r ec e n i f i c a t e st o g u a r a n t e et h ea u t h e n t i c i t yo fp u b l i ck e y sa n dd o e s n t r e q u i r ek e ye s c r o w a tl a s t ，as e c u “t ya n dp e r f o r m a n c ea n a l y s e so fn e w c h a n c h e o n 4 1 s i g n a t u r es c h e m ea r e 舀v e n 1 【e yw o r d s ：p u b l i ck e yc e r t i f i c a t e ； i d e n t i t y - b a s e d ； b i l i n e a rp a i r i n g ； k e ye s c r o w ；k e yi s s u i n gp r o t o c o l 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 加谚年6 月fd 日 炒择6 月f - ，日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 刘铆未碎 加d 8 年占月f d 日 引言 引言 1 基于证书和基于身份的数字签名的研究背景和发展概况 随着信息技术的高速发展和计算机网络技术的广泛应用，为人们提供了快 速、高效、和廉价的通信，大量敏感的信息常常要通过互联网进行交换。人们之 间的信息交流呈现出国际化、网络化、数字化、智能化、宽带化的趋势，可以说 人类已经进入了“信息时代”。信息时代的主要特征是信息成了社会中最重要的 一种资源和财富，信息的交流和处理手段成了人们生活必不可少的组成部分，过 去人们想象不到的许多事情都已经变成了现实。然而，现代信息技术是一把双刃 剑，它一方面给人类带来了巨大的好处，另一方面又给人类带来了前所未有的威 胁。由于互联网的开放性，任何人都可以接入互联网，使得一些人就有可能采用 各种非法手段窃取、假冒、欺骗、篡改和破坏各种重要信息，甚至进行计算机犯 罪。具体地说，信息的接收方可以伪造一份报文，并声称是由发送方发送过来的， 从而获得非法利益。例如，银行通过网络传送一张电子支票，接受者有可能改动 电子支票的金额，并声称是由银行发送过来的。同样的，信息的发送方也可以否 认发送过报文，从而获得非法利益。例如客户给委托人发送一份进行某项股票交 易的报文，结果这项股票交易亏损了，客户为了逃避损失，否认发送交易的报文。 从某种角度来讲，正因为存在的种种信息安全问题，才催生了信息安全技术的发 展。随着社会和技术的发展，信息安全问题显得越来越重要，已经成为国内外计 算机和网络应用领域普遍关注的热门研究课题。 在“信息时代 ，人们迫切需要新的信息安全技术来保证传输信息的真实性、 解决通信双方的争端，这种技术就是数字签名技术。数字签名作为认证的主要手 段，为信息安全提供了重要的技术支撑。数字签名可以解决否认、伪造、篡改及 冒充等问题：使用数字签名技术使得发送者事后不能否认发送的报文签名、接受 者能够核实发送者发送的报文签名、接受者不能伪造发送者的报文签名、接受者 不能对发送者的报文进行篡改、网络中的用户不能冒从另一用户。正是由于数字 签名具有的独特功能和实际用途，在一些实际行业中，比如金融、商业、军事等 有着广泛的应用，尤其是数据完整性检验、身份鉴别、身份证明、防否认等方面， 功能独特。例如安全的电子交易s e t 是v i s a 和m a s t e r c a r d 两大信用卡公司和 多家科技公司于1 9 9 7 年指定的一个在i n t e m e t 上进行的在线交易的安全标准。 引言 s e t 提供了消费者、商家和银行间的认证，确保了交易数据的安全、完整可靠和 交易的不可否认，特别是保证了消费者的隐私。 随着对数字签名研究的不断深入，随着电子商务、电子政务的快速发展，对 数字签名的研究己从一般数字签名发展成研究满足特定需要、具有特殊性质或特 殊功能的数字签名，具有特殊性质的数字签名己成为数字签名的主要研究方向。 1 9 7 6 年，d i 仟i e 和h e l l m a n 在其“密码学的新方向”一文首先提出了公钥密 码理论【5 】，公钥密码理论的发展是整个密码编码学历史上的一次革命。在公钥密 码系统出现以前，几乎所有的密码编码学系统都建立在基本的代替和换位基础 上。公钥密码系统与以前的所有方法都截然不同，公钥密码算法基于数学函数而 不是代替和换文操作，通讯双方都拥有一个密钥对，一个为密钥拥有者保管，称 为私钥，不涉及分发问题，另一个密钥可以公开，称为公钥，基于公开的渠道就 可以实现分发，大大提高了分发的方便性。公钥密码理论有效地解决了对称加密 系统的密钥管理、分发、和数字签名问题。 基于证书的公钥基础设施( p u b l i ck e yi n f r a s t l l j c t u r e ，p ) 是一个利用现代密 码学的公开密钥密码技术，并在丌放的i i l t e m e t 网络环境中提供数据加密以及数 字签名服务的、统一的技术框架。p 的主要目的是通过自动管理密钥和证书， 可以为用户建立起一个安全的网络运行环境，使用户可以在多种应用环境下方便 地使用加密和数字签名技术。从而保证网上数据的机密性、完整性、有效性。一 个有效的p 系统是安全的和透明的，用户在获得加密和数字签名服务时，不 需要详细地了解p 是怎样管理证书和密钥的。p 系统的核心就是c a 中心， 同时由c a 中心管理的证书绑定了个人的身份( i d ) 和这个人的公钥。证书同时可 以发布在目录服务上，如l d a p ，使得用户可以方便获取别人的证书。同时对于 失密的证书，可以用证书撤销列表( c r l ) 来撤销它。p 系统也是目前市场上的 主流解决方案。 基于证书的公钥密码系统最大的问题就是证书的管理。在基于证书的公钥密 码系统中，用户的私钥是用户所选的一个随机数，正因为密钥的生成过程导致了 所有公钥的随机化，因此，在认证过程中，把一个主体的公钥和他的身份结合起 来是十分必要的。基于证书的密码系统的公钥是基于证书的，也就是说，公钥和身 份是通过证书形式绑定在一起的，有多少用户就需要多少证书。用户的公钥的生 引言 成、分发、注销、存储、证书的管理问题等，对证书颁发机构柬说都是极其繁重 的负担，因而需要越来越庞大的基础设施来支撑。 为了解决这一问题，1 9 8 4 年s h a m i r 【6 j 提出基于身份的加密、签名、认证的 设想，其中身份可以是用户的姓名、身份证号码、地址、电子邮件地址等。系统 中每个用户都有一个身份，用户的公钥就是用户的身份，或者是可以通过一个公 开的算法根据用户的身份可以容易地计算出来，而私钥则是由可信中心统一生 成。在基于身份的密码系统中，任意两个用户都可以安全通信，不需要交换公钥 证书，不必保存公钥证书列表，也不必使用在线的第三方，只需一个可信的密钥 发行中心为每个第一次接入系统的用户分配一个对应其公钥的私钥就可以了。基 于身份的密码系统不存在传统c a 颁发证书所带来的存储和管理开销问题。但 s h a m i r 并未给出基于身份的密码系统的实现。在基于身份的密码系统思想面世 后，很多研究者提出了一些基于身份的密码系统，如1 9 8 9 年l a i h 、k e 、h a m 和c h e n 【7 1 提出一个基于e l g a m a l 的基于身份的签名方案，1 9 9 1 年c h a n g 和l i n l 8 】 给出一个基于r a b i n 公钥密码系统的基于身份的数字签名方案，他们的方案在计 算上要比此前的方案高效。1 9 9 3 年h a m 和y a n g 提出一个基于a 印e m 等的签 名方案【9j 的基于身份签名方案f 1 0 1 ，1 9 9 9 年n i s h i o k a ，h a n a o k a 和i m a i 提出一种 用基于身份的密钥共享系统( i d b a s e dk e y s h a r i n gs y s t e m ) 构造签名方案的方法 1 1 1 1 。直到2 0 0 0 年法国的j o u x 博士和2 0 0 1 年史坦佛大学的b o n e h 和f r 柚“i n 【1 2 】 两位学者先后在密码系统上利用椭圆曲线上的双线性对的性质，提出了一个新的 基于身份的密码系统，基于身份的的密码系统才有了实质性进展。2 0 0 0 年后， 比较具有代表性的有：b o n e h 短签名方案【13 1 ，h e s s 、c h a c h e o n 【4 1 、 c h e n g - l i u w a n g 【1 5 l 等方案被提出，基于身份的签密方案如l i b e t q u i s q u a t e r 【1 6 1 、 c h o w y i u h u i c h o w 【1 7 】等被提出。c h o w y i u h u i c h o w 提出了一个能同时满足前 向安全性和公开验证性的方案，但是需要用到双私钥，即同时需要签密私钥 d ，d = s 1 q ，d 和解密私钥d 名= 5 q ，d 。另外有些方案利用动态私钥来实现前向安全 性，但是每次加密完后都要修改密钥，非常繁琐。 基于身份的签名方案最大的缺陷是存在密钥托管问题。由于私钥生成中心 3 引言 p k g 掌握着系统主密钥s ，所有用户的私钥都由p k g 对用户的身份q ，d 签名s q ，d 生成，用户的私钥和系统的安全性完全依赖于私钥生成中心p k g 。p k g 知道所 有用户的私钥，可以伪造所有用户的签名，如果p k g 有任何不诚实的行为或者 主密钥的泄露将直接导致用户私钥的公开化。如何有效的解决密钥托管问题，并 且保留基于身份的签名方案的优势，一直是我们关注的问题。 2 本论文的主要成果 提出了一个基于证书的理想数字签密方案，该方案满足消息的机密性、完整 性、签名方程的不可伪造、可身份认证、防抵赖、前向安全性、密文的公丌验证 性，且能抵抗b o b 的恶意伪造攻击等8 项安全性能。 利用椭圆曲线上双线性对的性质，另辟新径，构造了一个新的签名方程。利 用这种系统可以同时满足签名的公开验证性和前向安全性及其他安全特性，不需 要利用双私钥，并把这种签名思想用到应用到基于身份的门限签密方案中，从而 使得基于身份的门限签密方案也同时满足前向安全性和公开验证性且满足其它 特性。 利用椭圆曲线上双线性对的性质以及基于椭圆曲线上的c d l p 难解问题和 双线性对上c d h p 难解问题，提出了一个不需要用户公钥证书，也不需要密钥 托管的密钥分发新协议，并结合c h a c h e o n 签名给出了安全性和性能分析。 4 西北大学学位论文 第一章绪论 1 1 公钥密码系统( 又称非对称加密系统) 1 9 7 6 年，d i 仟i e 和h e l l m a n 在其“密码学的新方向”一文首先提出了公钥密 码理论i5 1 ，公钥密码理论的发展是整个密码编码学历史上的一次革命。 典型的公钥密码算法是r s a 、d s a 、e c c ，其原理是基于求解数学问题的困 难性，用公钥推导出私钥的难度在计算上是不可行的，r s a 算法是迄今为止理论 上最为成熟完善的公钥密码算法，e c c 算法具有广泛的应用前景。公钥密码系 统优点是密钥管理方便，通信过程中不需要交换对称密钥，安全性高；缺点是加解 密速度慢，因为公钥密码系统都是基于数学难题，计算非常复杂，所以它的实现 速度比对称加密技术要慢许多。例如：在r s a 算法的模为5 1 2 b i t ，用硬件实现 时，d e s 大约比r s a 快1 0 0 0 倍，用软件实现时，d e s 大约比r s a 快1 0 0 倍。 公钥加密系统所需要的密钥量少：对于具有n 个用户的网络，仅需要2 n 个 密钥。公钥加密系统还能够很容易的实现数字签名。 1 1 1 基于证书的公钥密码系统 在公钥密码系统中，用户只的私钥是用户只所选的一个随机数，相应的公钥 也是随机的，公钥的随机化导致了这样一个问题：如何才能将公钥与签名人的身 份关联起来? 传统的方法是为每个公钥发行一个公钥证书，这个证书由可信机构 ( t r u s t e da u t h o r i t y ，1 a ) 或认证中心( c e n i f i c a t i ea u t h o r i t y c a ) 对用户的公钥及其 身份的一个签名。公钥的分配使用证书( c e n i f i c a t e ) 来实现，证书中包含了用户 的公钥、i d 以及权威机构对证书的签名。k o h n f e l d e r 【1 8 】最早提出了使用证书的方 案，该方案有以下要求： ( 1 ) 任何参与者都可以阅读证书以确定证书拥有者的名字和公丌密钥； ( 2 ) 任何参与者都可以验证证书是来自管理机构还是赝品； ( 3 ) 只有管理机构才能制作和更新证书； ( 4 ) 任何参与者都可以验证证书的时效性。 因为证书不可伪造，证书可以放在一个目录内供参与者访问，用户也可以直 接把证书发送给其他用户。认证中心c a 在公钥密码系统中起着关键的作用，c a 西北大学学位论文 负责管理系统中的所有用户( 包括人、各种应用程序、主机) 的证书。 认证中心( c a ) 的功能有：证书发放、证书更新、证书撤销和证书验证。c a 的 核心功能就是发放和管理数字证书。 1 1 2 基于身份的公钥密码系统 基于证书的公钥密码系统最大的问题就是证书的管理。在基于数字证书的系 统中，使用一个用户的公钥之前，人们需要验证其证书是否f 确、合法、有效， 这需要较大的存储空间来存储用户的公钥证书，也需要较多的时间丌销来验证用 户的公钥证书。另一方面，由于公钥是基于证书的，有多少用户就需要多少证书。 用户的公钥证书的生成、分发、注销、证书的管理问题等，对证书颁发机构来 说都是极其繁重的负担，因而需要越来越庞大的基础设施来支撑。为了解决这一 问题，1 9 8 4 年s h 锄i r 在文献【6 1 提出了基于身份的公钥密码体系。在基于身份的 公开密钥体系中，用户的公钥q ，d 就是用户的仍或者由，d 导出的，因此不存 在公钥的管理和认证问题。用户只的私钥s 口由私钥生成中心p k g ( p r i v a t ek e y g e n e r a t o r ) 生成，这样，就不需要证书颁发机构，也不需要专门的目录来存放证 书，这大大减轻了管理的负担，减少了系统的代价和复杂度。 在基于身份的密码体系思想面世后，很多研究者提出了一些基于身份的加密 系统，其中有的方案不能防止用户的合谋攻击，有的方案需要p k g 用长时间来 生成私钥，有的方案需要硬件保护来实现。直到2 0 0 1 年b o n e h 和f r a n k l i n 【1 2 】利 用椭圆曲线上的双线性对的性质，提出了一个新的基于身份的密码系统，基于身 份的密码系统才有了实质性进展。在其方案中，通信双方用对方的i d 例如e m a i l 地址作为公钥给邮件加密。发送方无需获取接收方的证书以获取收方公钥。接收 方甚至可以在收到邮件之后再向p k g 申请自己的私钥，得到私钥后用之解密密 文。 基于身份的公钥密码系统还天生具有密钥托管功能。由于私钥生成中心p k g 掌握着系统主密钥s ，所有用户的私钥都由p k g 对用户的身份q ，d 签名s q ，d 生成， 用户的私钥和系统的安全性完全依赖于私钥生成中心p k g 。p k g 知道所有用户 的私钥，可以伪造所有用户的签名，如果p k g 有任何不诚实的行为或者主密钥 6 西北大学学位论文 的泄露将直接导致用户私钥的公丌化。即使把主密钥分别部署在几个不同的p k g 上，这样增强了安全性，但仍然避免不了几个p k g 的合谋攻击。，因为p k g 可 以根据公钥( 即e m a i l 地址) 计算出每个用户的私钥。 基于身份的公钥系统可能存在的问题有： ( 1 ) 基于身份的公钥系统无需管理证书，但是用户的l d 管理也同样麻烦。 ( 2 ) 基于身份的公钥系统天生具有密钥托管功能，但在需要不可否认性的环 境中，比如电子签名，则不适用。 ( 3 ) 在基于身份的公钥系统中，可能存在互操作的问题，因为不同的系统可能 使用不同的算法、不同的主密钥、不同的系统参数，则不同系统相互之 间有互操作问题。 ( 4 ) 基于证书的体系中，可以撤销证书，而在基于身份的体系中，撤销证书 意味着废弃原来的l d ，使得撤销成为一个难题。 ( 5 ) 基于证书的体系通过交叉认证、证书链来实现不同系统之间互联，而基于 身份的体系在大规模使用时，可能会碰到身份唯一性问题。 ( 6 ) 需要在p k g 和用户之间提供安全的方法、通道来解决私钥分发的问题。 1 1 3 基于证书的公钥系统和基于身份的公钥系统的比较 1 1 3 1 基于身份的公钥系统和基于证书的公钥系统的相同之处有 ( 1 ) 都是属于公开密钥体系，一个公开密钥，可以公开，另一个私有密钥由用 户保存，不公开。 ( 2 ) 都是公钥用于加密，私钥用户解密，私钥用于签名，公钥用于验证签名。 ( 3 ) 已知公钥，不能推算出私钥。 ( 4 ) 己知公钥、密文，不能推算出原文。 ( 5 ) 系统的安全性依赖于大数分解、离散对数求解、椭圆曲线求解等数学难题。 1 1 3 2 基于证书的公钥系统和基于身份的公钥系统的不同之处有 ( 1 ) 在基于身份的体系中，用户l d 可以直接得到。在基于证书的体系中，i d 和证书绑定，需要在验证c a 的签名后才能确认。 ( 2 ) 在基于证书的体系中，公钥、私钥作为一对密钥同时计算出来，通过证书， 用户的公钥与用户i d 才绑定在一起。在基于身份的体系中，公钥、私钥对 都是由用户i d 计算出来，在基于证书的体系中，用户的公钥必须经过c a 7 西北大学学位论文 中心的签名，才能被其他用户接受。在基于身份的体系中，公钥就是i d ， 无须一个权威机构签名。 ( 3 ) 在基于证书的体系中，需要有一个目录来存放用户的证书( 公钥) ，在基于 身份的体系中，由于公钥由i d 计算得到，无需单独的目录来存放证书。 ( 4 ) 在基于证书的体系中，认证需要由c a 来完成，在基于身份的体系中，认 证无需第三方介入。 1 2 椭圆曲线公钥密码系统 在目前流行的系统中既具有一定安全性又能比较容易实现的，按照所基于的 数学难题可分为如下三类：基于大整数分解问题的公钥密码系统( 如r s a ) ；基 于有限域上的离散对数问题的公钥密码公钥密码系统( 如d s a ) ；基于椭圆曲线 上的离散对数问题的公钥密码加密系统( 如e c c ) 。由于本论文主要研究椭圆曲 线上的数字签名与签密，所以下面只对椭圆曲线公钥密码系统进行介绍。 椭圆曲线密码系统( e c c ) 是基于椭圆曲线上的离散对数的计算困难性而提 出的公钥密码系统，椭圆曲线公钥密码系统离散对数的计算困难性是有限域离散 对数问题的一种变形，它是在椭圆曲线空间中决定公钥和私钥的关系。椭圆曲线 密码系统被认为是最有希望成为下一代通用的公钥密码系统。安全电子交易协议 ( s e t ) 的制定者已经把它作为下一代s e t 中缺省的公钥密码算法。为了鼓励 开发基于椭圆曲线密码体制的应用产品，几个国际标准化组织已经把椭圆曲线密 码体制作为新的信息安全标准。椭圆曲线密码所具有的巨大商业价值以及重大的 军事价值正在为越来越多的人所关注。 1 2 1 椭圆曲线密码系统上的离散对数问题 1 2 1 1 有限域g 上的离散对数问题的定义 已知口，p g ，确定一个整数七使得卢= 口，若七存在，即七= l o g ! ，则七称作 以a 为底的卢的离散对数。若已知口、七，计算卢是容易的。反过来，已知a 、 ，求解七是数学界公认的难题。 1 2 1 2 椭圆曲线上的离散对数问题的定义 用椭圆曲线e 上的点的群代替g ，用群加法代替群乘法，若为c 上的椭 圆曲线，尸为e 上一点，给定一点q ，q 为e 上一点，求解整数七c ，使护；q 8 西北大学学位论文 是数学界公认的难题。在这里舻表示数乘，即七个p 相加。 一般认为，椭圆曲线上的离散对数问题是比有限域上离散对数更困难的问题。 1 2 2 椭圆曲线密码系统的优势 基于椭圆曲线上的具有签密功能的数字签名方案整合了加密、解密、数字签 名三种技术，比单独进行加密、解密、数字签名节省了计算量和通信成本。 ( 1 ) 、椭圆曲线密码系统是迄今为止每比特具有最高安全强度的密码系统。 椭圆曲线密码体制的诱人之处在于在安全性相当的前提下，可以使用较短的 密钥。一般认为，椭圆曲线密码体制的密钥长度为1 6 0 比特时，其安全性相当 于r s a 使用1 0 2 4 比特。密钥短意味着小的带宽和存储要求，这在某些应用中 可能是决定性的因素。 ( 2 ) 、椭圆曲线资源丰富 同一个有限域上存在着大量不同的椭圆曲线，这为安全性增加了额外的保 证，也为软、硬件实现带来了方便。 ( 3 ) 、椭圆曲线密码体制的加密效率 评价公钥算法的效率主要考虑三个因素：计算负荷、密钥大小和带宽。加拿 大c e r t i c o m 公司从这三个方面对e c c 进行了评估【1 9 1 。 计算负荷是进行公钥和私钥转换所需要的计算量。与e c c 相比，其他公 钥体制由于产生密钥所需要的计算非常复杂，在计算能力有限的情况下很难产生 合适的密钥，而e c c 可在很短时间里产生符合条件的密钥。 密钥大小是存储密钥对和系统参数所需要的比特数。c e n i c o m 公司对 e c c 、r s a 和d s a 三种密码系统的密钥长度进行了比较，如表1 所示。由此 可见，e c c 所用的密钥长度比r s a 、d s a 的要短的多。 表1e c c 、r s a 和d s a 的密钥长度比较 密码系统 公丌密钥( b i t ) 私有密钥( b i t ) r s a1 0 8 82 0 4 8 d s a1 0 2 41 6 0 e c c1 6 1 1 6 0 带宽：要传输的加密消息或签名的比特数。c e n i c o m 公司认为，当e c c 、 r s a 和d s a 三类公钥系统用于加密长消息或进行长消息的数字签名时，具有 9 西北大学学位论文 相似的带宽要求。但对于短消息而言，情况就不一样了。实际上，公钥加密系统 通常用来传送短消息的，如为对称密码系统传送会话密钥。因此，c e n i c o m 公 司进行了相关的实验，以测定e c c 、r s a 和d s a 三类公钥系统在加密长短消 息或进行长短消息的数字签名时带宽的要求。如表2 所示。 表2 ：e c c 、r s a 和d s a 加密长短消息所需带宽的比较 加密2 0 0 0 比特长消加密1 0 0 比特短消息 算法息所需的带宽( b i t )的带宽要求( b i t ) r s a2 0 4 81 0 2 4 d s a2 0 4 8 1 0 2 4 e c c1 2 8 0 1 2 0 通过比较可以看出，在加密系统中传输短消息时，e c c 能比其他公钥系统提 供更大的带宽节省。 1 2 3 对椭圆曲线密码系统上攻击 目前，对椭圆曲线离散对数问题最有影响的攻击方法是p l l a r d a 方法和 p o h l i g h e l l m a n 方法，这两种方法属于碰撞搜索法，具有纯指数的时间复杂度 【矧。椭圆曲线密码的强度主要依赖于其阶是否含有大素数因子。因为，对于小 素数因子，已有算法p o h l i g s l i v e 卜h e l l m a n 可解其椭圆曲线离散对数问题。目前 对于阶中含有大素数因子的椭圆曲线离散对数问题，还没有有效的攻击方法。 超奇异椭圆曲线由于存在m o v 攻击【2 1 】一直被避免使用，但是m b a l l r e t o 研 究【2 2 l 中表明，有3 类超奇异椭圆曲线可以用来构造可证明安全的密码体制。由 于存在m o v 攻击存在，降低了椭圆曲线整体使用上的安全度，造成这些超奇异 椭圆曲线长久以来不被众多密码学研究学者所采用。甚至一度令学者对于双线性 对函数抱持着负面的看法。一直到2 0 0 0 年法国的j o u x 博士和2 0 0 1 年史丹佛大 学的b 0 n e h 和f r a n k l i n 两位学者先后在密码系统上对双线性对函数提出应用后， 这样的情况才有了实质性的改变。 1 3 数字签名的概念与基本原理 数字签名是认证的主要手段之一，也是现代密码学的主要研究内容之一。数 字签名是同常生活中手写签名的电子对照物，它的主要功能是实现用户对电子形 1 0 西北大学学位论文 式存放消息的认证。 1 3 1 数字签名形式化定义 一般的数字签名方案包括3 个过程： ( 1 ) 系统的初始化过程 产生数字签名方案的基本参数 m ，s ，k s l g v e r ，) m 消息集合，s 签 名集合， k 密钥集合，包含私钥和公钥，s i e 一签名算法集合，v e r 签名验证算法集合。 ( 2 ) 签名的产生过程 对于密钥集合k ，相应的签名算法为s 喀。册，s 喀。：m 呻s ，对任意的消息 加m ，有s ；s 瓴( ，1 ) ，那么s s 为消息所的签名，将枷，s 】- 发送到签名验证者。 ( 3 ) 签名的验证过程 对于消息集合k ，有签名验证算法： 吲呻触嘶小船，z 篓篡， 签名验证者收到枷，s 】后，计算陀气( x ，) ，) ，若v p 丘o ，y ) = 砌，e ，则签名有效； 否则签名无效。 1 3 2 数字签名与手写签名的区别【2 3 1 ( 1 ) 数字签名中签名同消息是分开的，需要一种方法将签名与消息绑定在一起。 而传统的手写签名中，签名是被签消息的一部分； ( 2 ) 在签名的验证上，数字签名利用一种公开的算法对签名进行验证，任何人 都可以对签名进行验证，而传统的手写签名的验证时由经验丰富的消息接受者 通过与以前的签名进行比较来确定的； ( 3 ) 在数字签名中，有效签名的复制仍是有效的签名，而在传统的手写签名中， 签名的复制是无效的。因此，在数字签名方案的设计中要预防签名的非法重复使 用。 1 3 3 数字签名的分类 按不同的标准，数字签名方案有不同的分类方法。 ( 1 ) 基于数学难题的分类 西北大学学位论文 根据数字签名方案所基于的数学难题，数字签名方案可分为基于离散对数问 题的签名方案，如e l g a m a l 型数字签名方案和d e s 方案；基于素因子分解问题 的签名方案，如r s a 方案基于离散对数问题和素因子分解问题的数字签名方案， 如1 9 9 4 年h a m 设计的一种数字签名方案；1 9 9 7 年l a i h 和k u o 设计的一种新的 数字签名方案。基于二次剩余问题的签名方案可以认为是素因子分解问题的特殊 情况，如r a b i n 数字签名方案。 ( 2 ) 基于签名用户的分类 根据签名用户的情况，可将数字签名分为单个用户签名的数字签名方案和多 个用户的数字签名方案。一般的数字签名是单个用户签名方案，而多个用户的签 名方案又称多重数字签名方案。根据签名过程的不同，多重数字签名可分为有序 多重数字签名方案和广播多重数字签名方案。 ( 3 ) 基于数字签名所具有特性的分类 根据数字签名方案是否具有消息自动恢复的特性，可将数字签名方案分为两 类：一类不具有消息自动恢复的特性，另一类具有消息自动恢复的特性。一般的 数字签名不具有消息自动恢复特性，如最初的e l g a m a l 数字签名。1 9 9 4 年， n y b e r g 和r u e p p l e m l 首先提出了一类基于离散对数问题的具有消息自动恢复特 性的数字签名方案。 ( 4 ) 其它分类 常规的数字签名方案并不能完全满足实际需要，为了适应计算机通信和电子 商务迅速发展的需要，人们根据实际的需要，还提出了由常规数字签名推广的具 有特殊应用的数字签名方案。具有代表性的由群签名方案、多重数字签名方案、 代理数字签名方案等。 1 3 4 数字签名的功能 数字签名技术可以解决伪造、篡改、冒充、抵赖等问题，其功能表现在以下 几个方面： ( 1 ) 机密性；( 2 ) 完整性；( 3 ) 身份认证；( 4 ) 防伪造；( 5 ) 防抵赖； ( 6 ) 防重放攻击： 1 3 5 数字签名的的应用 互联网的出现和发展，为人们提供了快速、高效和廉价的通信，大量敏感的 1 2 西北大学学位论文 信息常常要通过互联网进行交换。由于互联网的丌放性，任何人都可以接入互联 网，使得一些人就有可能采用各种非法手段窃取、假冒、欺骗、篡改和破坏各种 重要信息，甚至进行计算机犯罪。 因此，需要新的信息安全技术来保证传输信息的真实性、解决通信双方的争 端。由于数字签名可以有效地解决否认、伪造、篡改及冒充等问题，所以在一些 实际行业中，比如金融、商业、军事等有着广泛的应用，尤其是数据完整性检验、 身份鉴别、身份证明、防否认等方面，功能独特。例如，s e t 已经成为目前最流 行通用的安全电子商务标准，它的核心技术主要是公丌密钥加密、数字签名、数 字证书、数字信封等。安全的电子交易s e t 是v i s a 和m a s t e r c a r d 两大信用卡 公司和多家科技公司于1 9 9 7 年指定的一个在i n t e m e t 上进行的在线交易的安全 标准。s e t 提供了消费者、商家和银行间的认证，确保了交易数据的安全、完整 可靠和交易的不可否认，特别是保证了消费者的隐私。 西北大学学位论文 第二章基于证书的椭圆曲线的数字签名与签密 本章在基于证书的椭圆曲线上的数字签名和签密方案中，选取了具有代表性 的赵的数字签密方案，指出了赵的方案不完全满足数字签密的安全特性，此方案 虽能抗击明