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

两北大学硕十学位论文 摘要 目前的数字签名和代理数字签名方案大都是基于普通离散对数难解问题上的，其安 全性已经不能满足人们的需求。基于椭圆曲线上的密码体制具有更高的安全性，把它应 用到数字签名和代理签名的领域，再和各种特殊的签名方案相结合，具有更高的研究价 值。 围绕着数字签名和代理数字签名的理论、方法和应用，本论文取得了以下二个方面 的主要研究成果。 首先我们提出了一种改进的基于椭圆曲线的数字签名方案，并对其安全性和复杂度 进行了分析。它能够有效抵抗生日攻击，从而提高了数字签名的安全性。文中提出的数 字签名方案具有消息自动恢复的特性，且具有运算量低，易于实现的功能。接着我们通 过实例验证该算法。已有数字签名方案抗击生日攻击的概率为p = 1 一鼍，倾一1 ) ，而改 进的数字签名方案抗击生日攻击的概率为pl 【1 一他一1 ) 】2 ，所以改进的方案提高了 数字签名的安全性能。 其次，我们对m 和p e n g 提出的代理数字签名方案进行了安全性分析，发现原签 名方案不能够抵抗文中提出的两种伪造攻击。利用这两种伪造攻击的任何一种，原始签 名者都能够伪造出一个有效的代理数字签名。因而，我们对l i n 和p e n g 的签名方案进 行了改进，提出了一种新的代理数字签名方案，能够完全抵抗文中的伪造攻击一和伪造 攻击二。我们还对改进的新方案进行了安全性分析和复杂度分析。 关键词：数字签名；代理数字签名；椭圆曲线；离散对数问题；伪造攻击 西北大学硕士学位论文 t h er e s e a r c ha n dd e s i g no fd i g i t a ls i g n a t u r es c h e m eb a s e do ne l l i p t i c c u r v e s a b s t r a c t a tp r e s e n t ，d i 百t a ls i 印a t u r e 锄dp r o x yd i 百t a ls i 印a t u r es c h e m e sa r ca l m o s tb a s e do n o r d i n a r ys e p a r a t el o g a r i t l l i l lq u e s t i o n a n dt h es e c l l f i t yo ft h es c h e m e sc o u l d n ts a t i s f yt h e r c q u e s to ft h ep e o p l e t h es c h e m e s b a s e do ne c d l ph a v et h eh i g l l e rs e c l l r i t y i nt h i sp a p e r ，i t i sa p p l i e dt ot h ed o m a i no fd i 酉t a ls i 印a t u r e 柚dp r o x ys i 伊a t u r e 觚di su n i f i e dw i t hs p e c i a l l 【i n d0 fs i g n a t u r es c h e m e s s ot h es c h e m e sh a v et h eh i g h e rr e s e a r c hv a l u e c o n c c n t r a t i n go nt h e o r y ，m e t h o da n da p p l i c a t i o no fd i 舀t a ls i 铲a t u r ca n dp r o x ys i g n a t u f c ， m op 血c i p a la c h i e v e m e n t sh a v eb e 饥o b t a i n e di nt h i st h e s i s f i r s to fa l l ，i i lt h i sp a p e r 柚i m p r o v e dd i 西t a ls i g n a t u r es c h e m eb a s e do ne l l i p t i cc u n ，ew a s p r e s e n t e d t h es e c u r i t y 觚dc o m p l e x i t yo fd i 酉t a ls i 印a t u r ew a s 觚a l y z e d t 1 l i sp r o p o s e d s c h e m ec a nn o to n l ye f f i c i e n t l yr e s i s tb i r t h d a ya t t a c k ，b u ta l s oi m p r o v et l l es e c u r i t yo fd i 百t a l s i 萨a t u r e t h ei m p r o v e dd i 酉t a ls i 印a t u r em e s s a g er e c o v e r ys c h e m em a ye 勰i l yr e a l i z ew i t h l o wc o m p u t a t i o n ha d d i t i o n ，w ee x a m i n e dt h ei i i i p r 0 v e ds c h e m eb ym e a n so fe x a m p l e t h e p r o b a b i l i t y o ft h e o r i g i i l a ld i 百t a ls i 印a t u r e s c h e m et 0r e s i s t b i n h d a y a t t a c ki s p 一1 一鼍1 q 一1 ) ，b u t t h e p r o b a l i l i t y o ft h e i m p r o v e dd i 舀t a ls i 伊a t u r e s c h e m ei s p 昌【1 一味l 砌一1 ) 】2 t h e r e f o r e ，t h es e c l i f i t y o ft h ei m p r o v e dd i 舀t a ls i 弘a t u r cs c h e m ei s i n c r e a s e d s e c o n d ，t h es e c l l r i t yo fe l l i p t i cc u ep f o x yd i 酉t a ls i g i l a t u r es c h e m eb yl i n 锄dp e n gi s 觚a l y z e d ，t h eo r i 酉n a ls i 伊a t u r es c h e m ec a i ln o tr e s i s tt h et 、) l ，of b r g e r ya t t a c k s u s i n g 觚y o n e o ft h ef o 唱e r ya t t a c l 【s ，o r i 酉n a ls i g n e rc 柚p r o d u c cav a l i dp r o x ys i 萨a t u r e o nt h eb a s i s ，觚 i m p r o v e de l l i p t i cc u r v ep r o x yd i 酉t a ls i g n a t u r es c h e m ec 0 n c e m e di sp r e s e n t e di nt h ep a p e r 锄dt h i si m p r o v e ds c h e m ec a l lc o m p l e t e l yr e s i s tt h e 柳of b r g e r ya t t a c k s h la d d i t i o n ，t h e s e c u r i t y 趾dc o m p l e x i t yo ft h i sn e ws c h e m ei sa n a l y z e d i nv i e wo ft h i s ，t h ei i l l p r 0 v e dp r o x y d i 酉t a ls i g n a t u r ec a nn o to n l yr e s i s tt h et w of 0 玛e 巧a t t a c k sb u ta l s or c t a i nt h ef i l ua d v a n t a g e s o ft h ep r o x yd i g i t a ls i g n a t u r eb yl i na n dp e n g k e yw o r d s ：d i g i t a ls i 印a t u r e ；p r o x yd i 百t a ls i 萨a t u r e ；e l l i p t i cc u e ；d i s c r e t el o g a r i t h m p r o b l e m ；f o 唱e r ya t t a c k t t 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 ， ， 学位论文作者签名：竖l l 指导教师签名：弛 珈占年6 月6 日 ff y g 年s 只s 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：1 柄青 撕g 年6 月6 日 两北大学硕士学位论文 第一章绪论 计算机技术的高速发展为人类提供了高度的自动化和现代化，网络的迅猛发展为人 们提供了便捷、快速的信息交流方式，使我们人类社会迅速进入了信息化时代。互联网 的发展和壮大使得人们足不出户就可以洞晓天下人和事，极大的方便了人们的学习、工 作和生活。现在，计算机应用已经渗透到政治、经济、军事、科学文化和家庭生活等社 会的各个领域。然而，现代信息技术也是一把双刃剑，它给人们带来方便的同时，也带 来了许多麻烦。由于信息的传递、存储、处理等过程往往是在开放的通信网络上进行的， 所以信息容易受到窃听、截取、修改、伪造、重放等各种攻击手段的威胁。因此，与通 信技术的高速发展相对应，信息安全成了信息社会急需解决的最重要的问题之一。 信息安全技术是一门综合的学科，它涉及信息论、计算机科学和密码学等多方面知 识。它的主要任务是研究计算机系统和通信网络内信息的保护方法，以实现系统内信息 的安全、保密、真实和完整。其中，信息安全的核心是密码技术。密码技术是一门新兴 的交叉学科，它涉及计算复杂度理论、算法设计与分析理论、计算机科学和网络技术、 通信技术、数论、信息论、编码理论、图论、不定方程、组合数学、代数以及公共策略 和法律等方面的知识。密码技术除了提供信息的加解密外，还提供对信息来源的鉴别、 保证信息的完整性和不可否认性等功能，而这三种功能都是通过数字签名来完成的。 1 1 数字签名的研究背景与意义 1 9 4 8 年s h a 曲o n 发表了划时代的“通信的数学理论 【1 1 ，宣告了一门崭新的学科 一一信息论的诞生。1 9 4 9 年s h a 姗o n 的奠基性论著“保密系统的通讯理论 ( c o m m u n i c a t i o n n e o r yo f s e c r e c ys y s t e m s ) 的发表，标志着现代密码学的诞生。五十 多年后的今天，通信、计算机和半导体技术的发展已将人类社会推进到一个崭新的信息 时代。随着计算机网络及通信技术的迅猛发展，数字化、信息化、网络化正在冲击、影 响、改变我们社会生活的各个方面。因特网( i i l t e m e t ) 是信息社会发展到新阶段的重要标 志。它从原来的军用目的“铸剑为犁 演变成了现在的公共网络，为人类交换信息，促 进科学、技术、文化、教育、生产的发展，提高现代人的生活质量提供了极大的便利， 也正因为其全球性、开放性、无缝连通性、共享性、动态性，因特网已远非其初期的学 院式和相互信赖的网络环境，任何人都可以自由地接入，其中有善者，也有恶者。恶者 西北大学硕十学位论文 整天在试图穿透别人的系统、窃取重要情报、捣毁别人的信箱、散布破坏性信息、倾泻 信息拉圾、进行网络欺诈、施放病毒、发动黑客战等。因特网一方面成为人们离不开的 信息工具，同时它也成为公开的攻击对象和目标。 目前，由于我国很多重要的信息、网络系统基本上处于不设防状态，大都处于c 级 安全级别，可以说我国的信息、网络安全的形势很严峻。由于其防御能力的脆弱性，很 容易遭受攻击、破坏，而一旦遭受致命性攻击给国家、社会带来的损失将不可估量。电 子政务、电子商务得以广泛应用的前提和基础就是其安全要得以保障，不安全的协议会 给其带来致命的后果。所以研究适用于电子政务、电子商务运行机制的数字签名算法就 成为保障其安全的一项重要内容。可以说数字签名是社会信息化的必然产物和需要。在 传统现实社会里，各种合同、文件、命令、条约、票据等都需要手写签名或加盖印鉴， 以便获得法律上的认可，取得相当法律效力。随着社会的信息化发展，越来越多的文件 需要数字化，且以数据串的形式通过网络得以快速传递，这些数据串的来源和完整性都 需要认证，而且这些认证常常需要在以后的一段时期内多次重复，这就需要手写签名的 电子替代物数字签名( d i 西t a ls i 印a t u r c ) 。一般来说，网络世界的真实性要比现实世 界的真实性更难于保证，因此对数字签名的需求就显得更加迫切。数字签名作为重要的 数字证据，在电子商务开展得较早的国家和地区都相继通过相关法案赋予数字签名法律 效力，中国全国人大也已于2 0 0 4 年8 月通过了中华人民共和国电子签名法，使数字 签名与手写签名一样具有同等的法律效力。 数字签名是认证的主要手段之一，也是现代密码学主要研究内容之一。数字签名是 日常生活中手写签名的电子对应物，它的主要功能是实现用户对电子形式存放消息的认 证。数字签名技术是提供认证性、完整性和不可否认性的重要技术，因而是信息安全的 核心技术之一，特别地，在电子商务、电子银行、电子政务等应用领域，数字签名是关 键技术之一，在社会生活的各个领域也有极其广阔的应用前景。目前，数字签名技术己 开始应用于商业、金融和办公自动化等系统中，同时作为一种密码学原语( p r i m i t i v e ) ， 数字签名被广泛用于设计各种电子应用协议。 数字签名的实现基础是数字加密技术，其使用公钥加密算法和散列函数。常用的数 字签名算法有：r s a ，d s a ，e c d s a ，e l g 锄a l ，s c h n o 盯等：还有一些用于特殊用途的数 字签名，如盲签名、群签名、多重数字签名等。在日常生活中，使用手写签名或印章很 普遍，如签署合同、文件等。由于数字签名具有防冒充( 伪造) 、防篡改( 破坏信息的完 2 西北大学硕士学位论文 整性) 、防重放、防抵赖( 否认) 和机密性( 保密性) 等抵御网络攻击的特性，所以数字签 名可以在网络环境中代替传统的手写签名和印章，以便在网络上实现签字和印章的电子 化，极大的提高工作效率，方便人们的工作和生活。 现在，数字签名技术的常见实现方式是采用智能卡技术，有的还附加指纹、面部特 征识别、视网膜扫描以及语音识别等其他技术，或者所有这些技术的合成以提高签名和 认证的准确性。 1 2 信息安全简介 信息安全是一个综合性的交叉学科，它涉及数学、密码学、计算机、通讯、控制、 人工智能、安全工程、人文科学、法律等诸多学科。近1 5 年来，计算机、通讯和网络 技术的快速发展大大促进了对信息进行获取、处理、存储、传输等操作方面的能力，同 时也拓宽了信息应用的范围。 信息安全在其发展过程中经历了三个阶段：2 0 世纪6 0 年代以前，这一阶段的信息安 全可以简单称为信息保密( 1 n f 0 姗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 ) 、完整性 ( h l t i 鲥t y ) 、可用性( a v a i l a b i l i t y ) 为目标的信息安全( i n f o 册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 e i t y ) 、不可否认性 ( n o n r e p u d i a t i o n ) 等其他的原则和目标，信息安全也转化为从整体角度考虑其体系建设的 信息保障。 所谓信息安全，是指信息的五要素，即信息的保密性( c o n f i d e n t i a l i t y ) 、完整性 ( i n t e 鲥t y ) 、可用性( a v a i l a b i l i t y ) 、可控性( c o n t r o l l a b i l i t y ) 与可审查性。 a ) 保密性：对抗对手的被动攻击，保证信息不泄漏给未经授权的人。 b ) 完整性：对抗对手主动攻击，防止信息被未经授权的篡改。 c ) 可用性：保证信息及信息系统确实为授权使用者所用。 d ) 可控性：对信息及信息系统实施安全监控。 e ) 可审查性：对出现的网络安全问题提供调查的依据和手段。 3 西北大学硕士学位论文 1 3 国内外相关技术的研究与进展 1 9 7 6 年d i f ! f i e 和h e l l m 卸发表了著名的“密码学的新方向( 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 一文，提出了“公钥密码系统( p u b l i ck yr y p t o s y s t e m ) 的概念， 为信息安全提供了新的理论和技术基础，开创了密码学的一个新时代。此后人们相继提 出来许多公钥密码方案，如r s a 体制、e i g a m a l 体制、背包体制等。随着数学理论的 发展和计算能力的提高，许多方案被证明是不安全的，有些在实现上是不现实的。 1 9 7 8 年，由r i v e s t ，s h a m i r 和a d l e m a i l 给出的基于大整数分解困难性的著名的r s a 签名方案【3 1 ，他们同时给出了著名的r s a 公钥密码方案。它是第一个较完善的公开密 钥算法，它既能用于加密也能用于数字签名，而认证过程相当于保密过程的逆过程。 1 9 8 5 年n e a lk o b l i t z 【4 l 和v s m i l l e r 【5 l 把椭圆曲线的研究成果应用到密码学中，分别 独立地提出在公钥密码系统中使用椭圆曲线的思想。他们虽没有发明出一种新的公钥密 码算法，但他们采用椭圆曲线技术实现了已存在的密码算法如d i f f i e h e l l m a l l 算法等， 这就是椭圆曲线密码学的开端。1 9 8 5 年，s c h 0 0 f 最早提出了计算椭圆曲线上有理点个 数的算法，1 9 8 9 年到1 9 9 2 年之间，a t i l 【i n 和e l k i e s 对其作出了重大改进，而后又被 c o u v e 呼l e s ，m o r a i n 和l e r c i e r 等人进一步完善。在1 9 9 2 年s c o t t 、s t o n e 【6 】首先提出 了椭圆曲线密码体制的数字签名算法e c d s a ( e l l i p t i cc u r v ed i 酉t a ls i 印a t u r e 灿g o r i t h m ) 。 1 9 8 2 年，c h a u m 引入盲签名( b l i n ds i 印a t u f e ) 概念，使签名者在不知道消息具体内容 的情况下对其签名，而文件或消息的拥有者又可以签名得到签名人关于真实文件或消息 的签名，从而实现了电子货币的匿名性【7 1 。 1 9 8 9 年，c h a u m 和a m 俩e 叩e 首次提出不可否认签名( u n d e n i a b l es i 印a t u r e ) 的概念， 这种签名适合用于保护电子出版物的知识产权，可防止签名者的签署文件被复制或者散 布，在电子选举、电子现金、电子拍卖等各方面有着十分重要的应用【引。 1 9 9 1 年，群签名( g f o u ps i 萨a t u r e ) 的概念被c h a u m 和v a n h e y s t 提出，一个群体的任 意一个成员均能够以匿名的方式代表整个群体对消息进行签名，而只用单个群公钥就可 以实现公开验证【9 1 。同年，y d e s m e d t 等人提出门限签名，特点是必须有足够多的成员 参与密钥获取和签名生成，设置门限的主要目的是用于解决密钥泄露问题给加密带来的 威胁，签名是在共享密钥的基础上以分布式的方式完成的【1 0 】。 1 9 9 5 年，m 锄b o 、u s u d a 和o k 锄o t o 引入了代理签名( p r o x ys i n 龋a t u r e ) 的概念，使 4 西北大学硕士学位论文 得签名人由于某种原因不能行使签名权利时，可授权其他人代替其对消息签名【1 1 1 。可以 将代理签名分为完全代理签名、部分代理签名以及包含授权证书的签名三类。 2 0 0 1 年b o n e h 等提出了基于双线性对的短签名【1 2 】之后，双线性对成了构造签名的 重要工具。由双线性对构造的签名方案具有签字短、安全、高效等特点，所以一经提出 就引起了广泛的关注。 2 0 0 4 年8 月，我国正式颁布了中华人民共和国电子签名法，用于规范电子签名 行为，确立电子签名的法律效力和地位。这部法律将为数字签名的应用和推广提供了最 有力的保障和支持。 1 4 论文的主要贡献和组织结构 1 4 1 论文的主要贡献 数字签名技术是解决信息安全需求的关键技术之一，近几年来，数字签名的基础理 论研究一直十分活跃，二些新概念、新签名方案、新密码体制不断地产生和发展。本文 在前人工作的基础上，对数字签名技术及应用问题进行了研究，主要贡献和创新工作归 纳如下： ( 1 ) 我们对已有的基于椭圆曲线数字签名方案的安全性进行了分析，发现已有数字签 名方案不能有效抵抗生日攻击。接着我们对已有的数字签名方案加以改进，提出了改进 的数字签名方案。改进的数字签名方案的主要思想是对消息的签名人分配了两个私钥， 从而签名人对消息的签名由两部分组成。在签名过程中签名人随机选取两个数( 即两个 消息秘钥) ，这样，减少了两次选取相同随机数的概率，因此增加了生日攻击的难度。 从已有的数字签名方案抵抗生日攻击的概率p 一1 一鼍，肋一1 ) ，降低为 p _ 【1 一鼍。( 玎一1 ) 】2 ，所以改进的数字签名方案提高了数字签名的安全性能。 ( 2 ) 我们还对l i n 和p e n g 的代理数字签名方案进行了安全性分析，发现原始签名人 能够利用文中的伪造攻击一和伪造攻击二伪造一个有效的代理签名。我们对l i n g 和p e n g 的代理数字签名方案加以改进，提出了改进的代理数字签名方案。改进的代理数字签名 方案的主要思想是消息的代理签名人需要对代理身份和代理密钥进行验证。若原始签名 人通过代理签名人对代理身份和密钥的验证，那么，代理签名人确认代理身份的有效性， 并接受本次代理签名。因此，原始签名人就不能够利用伪造攻击一和伪造攻击二对消息 5 西北大学硕士学位论文 生成有效的代理签名。 1 4 2 论文的组织与结构 论文围绕着数字签名领域的一些关键技术，阐述了作者对某些原有签名方案的安全 性分析和构造的一些新的数字签名方案设计，较全面地概括了作者在三年来所做的工作 及取得的结果。论文的组织结构如下： 第一章介绍了数字签名研究的背景与意义、信息安全简介、国内外相关技术的研 究与发展、论文的主要贡献和创新之处以及论文的组织与结构。接着，介绍了本文需要 的数学和密码学的知识以及有限域上椭圆曲线的基本理论。本章最后介绍了椭圆曲线密 码体制和椭圆曲线以及椭圆曲线上的离散对数问题与安全性。 第二章介绍了具有消息自动恢复的数字签名方案。给出了数字签名方案的形式化 定义、已有的签名方案、改进的数字签名方案、改进方案的安全性和复杂度分析以及 m a t l a b 实例验证。 第三章介绍了椭圆曲线代理数字签名方案。阐述了代理数字签名的定义、性质、 分类，两种伪造攻击和改进的代理数字签名方案、改进的代理数字签名的安全性和复杂 度的分析。 1 5 公钥密码体制 公钥密码算法的思想是1 9 7 6 年由d i m e 和h e l l m a n 首先提出的，他们建议利用计 算复杂性来构造算法，开创了现代密码学的新领域。当d i f f i e 和h e l l m 觚提出这种公钥 思想时，还没有一个实际的公钥系统可以操作。但两年后，几乎同时提出了“背包公钥 和“r s a 公钥 两个密码系统。最著名的是1 9 7 8 年美国麻省理工学院的r i v e s t ，s h a m i r 和a d l e m a l l 【3 】联合提出的r s a 公钥密码算法；从那时起，各式各样的公钥密码算法层出 不穷，并取得了一系列理论和应用成果，其中颇具影响的有r s a 算法、w r e r k e h e l l m 柚 算法、m c e l i e c e 算法、e l g a m a l 算法等；1 9 8 5 年，n e a lk o b l 池和v i c t o rm i l l e r 相互独立 地提出了在密码学中应用椭圆曲线的思想。这样做的主要好处之一就是在相同安全性下 可以使用更短的密钥，同有限域上的离散对数相比，椭圆曲线有如下优点：简单的算术 实现，更少的带宽和内存需求。一个最需要这些特征的应用便是智能卡。 6 西北大学硕士学位论文 公钥密码体制的安全性主要基于一些数学上难解的问题，它主要分为三种： ( 1 ) 基于素因子分解的公钥密码技术，如r s a ，r a b i n w i l l i 锄s 体制【”1 ； ( 2 ) 基于离散对数的公钥密码技术，如d s a ，e l g 锄a l 密码体制； ( 3 ) 基于椭圆曲线离散对数的公钥密码技术，如e c c 。 公钥密码技术的主要价值是解决下列问题： ( 1 ) 密钥分发； ( 2 ) 大范围应用中，数据的保密性( s e c r e c y ) 和完整性( i n t e 笋i t y ) ； ( 3 ) 实体鉴别( a u t h e n t i c a t i o n ) ； ( 4 ) 不可抵赖性( n o n r e p u d i a t i o n ) ； 1 5 1 椭圆曲线的数学基础 定义1 5 1f 是至少含两个元素的集合，对f 定义了两种运算“+ 和“木 ，并 且满足以下三条件的代数系统 称为域。 ( 1 ) f 的元素关于运算“+ 构成阿贝尔群，设其单位元为o 。 ( 2 ) f 0 ) 关于运算“ 构成阿贝尔群。 ( 3 ) 对于口，6 ，c f ，分配律成立。即： ( 口+ 6 ) 母c 耸口事c + 6 宰c c 宰( 口+ 6 ) ；c 宰口+ c 宰6 若域f 的元素有限个，则称之为有限域或伽罗瓦( g a l o i s ) 域。r 0 ) 表示集合f 除去元素 o ) 后的元素1 4 】。 定义1 5 2 有限域中元素的个数称为该有限域的阶。 1 5 2 椭圆曲线的概念1 5 1 定义1 5 3 域k 上的椭圆曲线e 由下述方程定义； e ：y 2 + 口1 拶+ 口3 y = z 3 + 口2 x + 口4 石+ 口6 ( 1 一1 ) 其中口1 ，口2 ，口3 ，口4 ，口6 k 且乒o ，是e 的判别式，具体定义如下： = 一d ；d 8 8 d ：一2 7 d ：+ 9 d 2 d 4 d 6d 2 一口；+ 4 口2 d 4 = 知4 + 口1 口3d 6 一口；+ 4 口6 d 8 = 口? 口6 + 4 口2 口6 一口1 口3 口4 + 口2 口；一口： 7 西北大学硕士学位论文 若l 是k 的扩域，则e 上的l 有理点的集合是： e 仁) ； o ，y ) l 工：) ，2 + 口1 夥+ 口3 y x 3 一口2 2 2 一口4 石一口6 = 0 u d ( 1 2 ) 其中o 是无穷远点。式( 卜1 ) 称为w e i e r s t r a s s 方程。 我们称e 是域k 上的椭圆曲线，这是因为系数口。，口：，口，口。，口。均为域k 的元素。有 时我们将椭圆曲线记为e k 以强调椭圆曲线e 定义在域k 上，并称k 为e 的基础域。 条件o 确保椭圆曲线是“光滑的或非奇异的，即曲线上的所有点都没有两个或两 个以上的不同切线。点o 是曲线的唯一的一个无穷远点，它满足投影形式的w r e i e r s t r a s s 方程。曲线e 的l 有理点是满足曲线方程且坐标x 和y 属于l 的点( x ，y ) ，并认为无穷远 点是k 的所有扩域l 上的l 有理数点。 1 5 3 有限域上的椭圆曲线 市限域f ，( 也谒为g f ( p ) ) 由整数集合 o ，1 ，2 p - 1 ) 组成，每个这样的整数可以用 一个长度恰为f p g ：p 1 ( 其中卜1 表示不小x 的最小整数) 的二进制表示，该表示由 整数的二进制表示及在其左边添加适当个数的0 组成。瓦中元素的算术运算如下： 加法 如果口，6 瓦，则a + b = r ，其中r 是a + b 被p 整除所得的剩余，0 s ，sp 一1 。 乘法如果口，6 t ，则口6 ；s ，其中s 是口6 被p 整除所得的剩余，0s ss p 一1 。 令巧表示巴中所有非零元素，可以证明在中至少存在一个元素g ，使得中任 意非零元素可以表示成g 的方幂，这样的元素g 称为c 的生成元( 或本原元) ，即 ，：一 g ：os fs p 一2 ) ( 1 3 ) 口= g e 的乘法逆是口；g 一g 一1 删，1 。 定义在上的椭圆曲线：令p 3 是一个素数，口，6 满足4 口3 + 2 砀2 乒。由参数a 和b 定义的c 上的一个椭圆曲线是方程y 2 一z 3 + 似+ 6 的所有解( x ，y ) ，工连同 一个称为“无穷远点 ( 记为o ) 的元素组成的点集合。( ) 的点数用撑e ( ) 表示。 由h a s s e 定理知： p + 1 2 ps 挣e ( ) sp + 1 + 2 p ( 1 4 ) 点集合e ( 瓦) 对应下面的加法规则构成一个群，即 ( 1 ) d + d = d ； ( 2 ) 对所有 ，) ，) e ( l ) ，o ，y ) + d = ，y ) ； 8 西北大学硕十学位论文 ( 3 ) 对所有o ，) ，) e ( c ) ，o ，y ) + ，一y ) = d ( 即点( x ，y ) 的逆为( x ，一y ) ) ； ( 4 ) ( 两个不同且不互逆的点加法法则) 令瓴，) ，。) e ( ) ，o ：，y ：) e ( ) 满足 而z ：的两个点，则 ，y ，) + ：，y ：) = 3 ，y ，) 。 p 32 _ 哇 ( 1 5 ) l y 3 一( a ( x 。一z 3 ) 一y 1 ) 其中a ：丝丛。 石2 一z 1 ( 5 ) ( 倍点规则) 令o 。，y 。) ( c ) 是一个点，y ，乒0 ，则2 0 。，) ，。) = 0 3 ，y 3 ) ， p ，。矛一缸t ( 卜6 ) i y 3 = a 0 1 一工3 ) 一y l 其中a ：娑。 y 1 群( ) 是a b e l 群，即对( ) 中所有的点p 和q ，p + q = q + p 。如果撑e ( ) ；p + 1 ， 则称曲线为“非光滑，的或超奇异的，否则称曲线为“光滑娩的或非奇异的。 1 5 4 椭圆曲线密码体制 将椭圆曲线用于公钥密码学的思想是1 9 8 5 年由v i c t o rm i l l e r 及n e a lk o b l 池共同提 出的。其理论基础是定义在有限域上的某一椭圆曲线上的有理点可构成有限交换群。如 果该群的阶包含一个较大的素因子，则其上的离散对数问题是计算上难解的数学问题。 业已证明，除了某些特殊的椭圆曲线外，目前已知的最好攻击算法( p d 砌耐一p 算法) f 嚣 也是完全指数级的。就安全强度而言，密钥长为1 6 3 比特的椭圆曲线密码体制( e l l i p t i c c u ec r y p t o s y s t e m ，e c c ) 相当于1 0 2 4 比特的r s a 。即在相同安全强度下，e c c 使用的 密钥比r s a 要短约8 4 。这使得e c c 对存储空间、传输带宽、处理器的速度要求较低。 这一优势对于资源环境有限的移动用户终端，具有极其重要的意义。e c c 目前在国外已 得到广泛的应用，各种采用e c c 的软硬件产品已相继出现。可以预计，e c c 将逐渐取代 r s a 而成为最主要的公钥密码体制。 1 5 5 椭圆曲线上的离散对数问题与安全性 离散对数问题( d l p ) ：给定一大素数p ，p 一1 含有另一个大素数因子q 可构造一乘法 群z ；，它是个p - 1 阶循环群，其生成元为整数g ，且1 g 2 1 ； e 有限域f q 上的椭圆曲线：y 2 ；工_ 3 + 甜+ 6 ( m o d 口) ； a ，ba ，b 是两个小于q 的整数，且满足锄3 + 2 伯2 o ( 玎 g椭圆曲线e 上的基点，阶为n 即n g 二o 0 椭圆曲线无穷远点 h单向散列函数 ( 1 ) 初始化过程 用户a 的秘钥和公钥分别为：k a ，p a = k 用户b 的秘钥和公钥分别为：k b ，p b = k b g ( 2 ) 签名的产生过程 a 选择随机整数k 乏，k 称为消息秘钥，z ：表示模n 同余类的非零元； a 计算尺一弛0 ，y ) ，r ) 小( m o d 丹) ，若r = 0 则返回； 计算j k + 蚂( m o d ，z ) ，若s = o ，则返回； 消息m 的签名是( r ，s ) 。 ( 3 ) 消息恢复和验证过程 b 接收到签名( r ，s ) ，首先下载域参数及a 的公钥，然后作如下运算： 检验r ，s 是否在区间 1 ，n 一1 上，若否，则b 拒绝此签名； 计算x = s g 一峨= o ，) ，) 和，l = ( k 口x ) 厂( m o d ，1 ) 为消息恢复方程； 若x = 0 则b 拒绝接受签名，否则b 计算原始消息m ，并检验消息末尾能够确认身份的冗 1 3 西北大学硕士学位论文 余位，若正确，则接受签名，否则拒绝签名。 给消息末尾加冗余位有多种方式。例如将参与者的身份认证或另外一些被通讯双方 所指定的字符串，由于b 的私钥是秘密的，所以任何人都不能恢复消息并判断发消息之 人是谁。只有b 能够计算出原始消息且知道与他通讯的人是谁。 2 3 2 改进的椭圆曲线数字签名方案 在上述方案中，两次选中相同的k 的概率是多少呢? 我们先给出生日问题的计算公 式：在m 个人中，至少两个人的生日是同一天的概率为p = 1 一瑶3 6 罗。由生日问题类似 可计算出两次选中同一个消息秘钥k 的概率为p = 1 一毛伽一黟，其中t 表示签名的次数， 要使p 大于0 5 ，则t 大约取如一1 ，来破解a 的私钥k ，假设两次签名选相同的k ， 墨= k + 吒巧( m o d 刀) ，s ：- k + ，2 髟( n 1 0 d ，1 ) 则一，一1 ( s 。一s ：) 。改进的方案使用两个随机 数，减少了两次签名选用相同的随机数，从而增加生日攻击的难度。具体算法如下： 首先椭圆曲线参数定义如同2 3 1 ( 1 ) 初始化过程 用户a 的私钥：k t ，k z 其中，髟：乏，如一巧： 用户a 的公钥： 易；k 虹g ，只：= 巧：g 用户b 的私钥：磁z j ：，z ：表示模n 同余类的非零元 用户b 的公钥：b k 口g ( 2 ) 签名的产生过程 a 选择随机数k 。，k ：z ：，其中，k ，k z 称为消息密钥； a 计算r = ( 墨+ k 2 ) b ； ，y ) ，= o ) 1 m ( m o d 忍) 若r = 0 ，则返回； a 再计算s 1 = k + 心1 ( m o d ，1 ) ，s 2 = k + 心2 ( m o d 咒) ，若s = o ，或s z = o ，则返回； a 对消息m 的签名是( r ，s 。，s ：) 。 ( 3 ) 消息恢复和验证过程 b 收到签名( r ，s 1 ，s 2 ) ，先下载域参数及a 的公钥，作如下运算： 检验r ，s l ，s 2 是否在区间 1 ，n 一1 上，若否则b 拒绝签名； b 计算z = s 。g + 5 ：g 一吧，一哆2 = ，y ) 和历；j i l ( k 口x 。) ，( m o d 咒) ，其中k 丑x 表示k 口x 的 横坐标； 1 4 西北大学硕士学位论文 若x = o ，则b 拒绝接受签名，否则b 计算原始消息m ，并检验消息末尾能够确认身份 的冗余位，若正确，则b 接受签名，否则拒绝签名。 这个签名体制的正确性可以通过以下等式证明： 尺- ( k1+k2 ) p 口- ( k1+k2 ) k 口g = k 口( k l + k2 ) g = k 80 1 g + s2 g 一，p z l 一，p 2 ) = k 口( 工。，) ，。) ，露一矗( k 口石) ，( m o d 疗) 石一s l g + 52 g 一厂p l 一，j p 月2 一k l g + k 爿l g + k2 g + n k 彳2 g 一，- ( k l + k 2 ) g tk 1 g + k2gt ( k 1 + k2 ) ge ( 石。，y 。) 2 4 改进的数字签名方案的安全性与复杂度分析 ( 1 ) 对改进的数字签名方案的攻击依赖于在f q 上求解方程d g = q ( m o d q ) 或 d l o g g q ( m o d 口) 。e c d 比有限域上的d l p 更难求解，在f q 上选取一条椭圆曲线e ， 及一个高阶基点g e ( f q ) ，计算d g 相对较容易，但已知q 和d g 求d 则是很困难。基于 椭圆曲线密码的安全性最终归结为解e c d l p 问题。对于一般的e c d l p ，目前有两种较 好的求解法：p o h l i g h e l l m 越方法和p 0 l l a r d p 方法。但对两类特殊的椭圆曲线，已经 有了其他有效的求解方法。一类特殊的椭圆曲线一一超奇异椭圆曲线，采用概率亚指数 算法m o v 算法和f r 算法可以解决e c d l p 。另一类是异常( a n o m a l o u s ) 椭圆曲线， s s s a 算法可以解决e c d l 玑 ( 2 ) 改进的数字签名方案的主要思想是签名人的私钥有两个整数( 即两个私钥) ，并 且签名的过程中使用两个随机数( 即两个消息秘钥) ，这样减少了两次签名选用相同随 机数的概率，从而增加了生日攻击的难度。如果签名t 次，则k 。，k 。同时出现的概率为 p 【1 一他一1 ) 】2 ，所以要使概率p 大于o 5 ，t 要大约等于n l ，而n 是一个很大的素 数，此情况几乎不可能出现。若k ，= k 2 ，则可得到k 。一k ：一，一( s ，一s ：) ，即知签名 者a 的两个私钥之差，由于k 一，k 一：z ：，破解k t ，k z 的概率为p = 1 ( ，l 一1 ) 2 ，n 是一个非常大的素数，p 也会非常小。若攻击者截获一则消息( r ，s 。) 或( r ，s ：) ，则他也 不能冒充a 对消息m 进行签名。 ( 3 ) 若攻击者想冒充a 对消息m 产生签名，攻击者随机选取k ，k ：计算 尺= ( k + 砭) b = 冠，y r ) ，一 o 只) 1 研( m o d ，1 ) ，s 。一足。+ 4 l ，s 2 一k2 + _ 2 ，解决 西北大学硕士学位论文 s 。，s ：的方法归结为求l ( 。，k a ：即解决e c d l p 。所以攻击者不能冒充a 产生签名( r ，s 。，s z ) 。 ( 4 ) 改进的数字签名方案的思想是密钥为两个整数，所以新方案和原方案在签名产 生过程中有关椭圆曲线的计算量是完全相同的，只是在签名过程中比原签名多出一个模 运算，和椭圆曲线运算相比，大整数模运算所需计算量可以忽略不计。验证过程中所需 要的计算量与原方案所需计算量比较多了个椭圆曲线倍点运算。 2 5m a tia b 实例分析 例若a 想签署消息i i l ：1 2 3 4 ( 假定前三位表示消