（计算机应用技术专业论文）基于椭圆曲线数字签名技术的研究与应用.pdf

摘要 摘要 题名：基于椭圆曲线数字签名技术的研究与应用 硕士研究生：秦媛嫒 导师：须文波教授 专业：计算机应用技术 在目前的加密方法中，椭圆曲线加密方法具有安全性高、密钥长度短、加密和 解密速度快等优点，其必将成为当今密码学领域中最具前途的加密方法之一。 从讨论信息安全需求开始，在论述密码技术的基础上，重点讨论了椭圆曲线密 码体制( e c c ) 。对当前使用广泛的公钥密码体制的数学基础、实现原理以及性能进 行全面比较。 椭圆曲线上点的标量乘和加法运算是椭圆曲线密码算法的核心运算。为了提高 运算速度，利用射影坐标思想，改进椭圆曲线上求两点和运算公式，对标量乘算法 进行优化。经理论分析证明，改进后的算法在一定程度上可以提高e c c 的实现速度， 增强e c c 的实用性。 由于椭圆曲线自身的优越性，其应用逐渐推广重点讨论了它在信息安全技术 之一数字签名中的应用。椭圆曲线数字签名算法( e c d s a ) 的安全性依赖于椭圆曲线离 散对数问题( e c d l p ) 的难解性。将e c c 的优化原理应用到e c d s a 中，有效地提高了数字 签名和签名验证的速度。 在以上研究基础之上，将优化的e c d s a 应用到电子政务系统中。x m l 用于电子公 文的传输是电子政务技术发展的趋势，对实现电子公文的标准化具有重要的意义 通过对基于e c d s a 的x m l 数字签名方案的讨论，并加以实现，证明了该设计的可行性 最后还对设计的性能做了一定的评价。测试结果表明，在x m l 数字签名中使用优化的 e c d s a 生成签名，使得x m l 签名技术兼具了x 札数字签名规范和e c d s a 签名的优点，具 有良好的实用价值。 关键词：椭圆曲线密码体制；射影坐标；点乘；椭圆曲线数字签名；电子政务 江南大学硕士学位论文 t i t l e ：t h er e s e a r c ha n da p p l i c a t i o no fd i g i t a ls i g n a t u r eb a s e do ne l l i p t i cc u r v e s g r a d u a t es t u d e n t ：q i ny u a n y u a n t u t o r ：p r o f x uw e n b o s u b j e c t ：c o m p u t e r a p p l i c a t i o nt e c h n o l o g y 1 1 e l l i p t i cc t l r v ec r y p t o s y s t e mh a s a d v a n t a g e so fh i g hs a f e t y , s h o r tk e yt e n g t h , q u i c k e 玳删a n d 出蜀呵p ts p e e da n ds oo n , s oi tw i l lb eh a v et h eb e s tf u t u r et h a no t h e r s b e g i n n i n gw i t ht h ed i s c u s s i o no fr e q u h e m e n t so fi n f o r m a t i o ns e c a r i t y , t h ef o u n d a t i o no f c r y p t o g r a p h i ct e c h n i q u e si sd i s c u s s e d o nt h ea b o v ed i s c u s s i o n s , t h ee l l i p t i cc u r v ec r y p t o s y s t e m i se l a b o r a t e di nd e t a i l m a t h e m a t i c sf o u n d a t i o n , r e a l i z a t i o np r i n c i p l ea n dt h ep e r f o r m a n c eo f p u b f i c - k e yc r y p t o s y s 把m sb e i n gu s e dw i d e l ya l ec o m p a r e d s c a l a rm u l t i p l i c a t i o na n dp o i n ta d d i t i o ni ne l l i p t i cc r v c sa t ec o f co p e r a t i o n si ne l l i p t i cc u r v e c r y p t o s y s t e m i no r d e rt oi m p r o v et h eo p e r a t i n gs p e e d ，t h ep r o j e c t i v ec o o r d i n a t e sa n di m p r o v i n g p o i n ta d d i t i o no p e r a t i o na l eu s e d ；t h es c a l a rm u l t i p l i c a t i o nm g o f i t h mi so p t i m i z e d t h eo p t i l n i z e d a l g o r i t h mc a ni m p r o v et h eo p e r a t i n gs p e e do fe c c a n de n h a n c et h ea v a i l a b i l i t yo fe c c ，w h i c h c a nb ep r o v e db yt h e o r e t i c a la n a l y s i s b e c a u s eo fe l l i p t i cc u r v ec r y p t e s y s t e m ss u p e r i o r i t y , i t sa p p l i c a t i o ni sb e i n ge x t e n d e d t h e e l l i p n cc u r v ed i g i t a ls i g n a t u r ea l g o r i t h m ( e c ：d s a ) i sd i s c u s s e de m p h a s i z e d d i g i t s ls i g n a t u r ei s 0 1 1 日o f t h e m o s t i m p o r t a n t i n f o r m a t i o ns e c u r i t y t e c h n o l o g i e s t h es e c u r i t y o f e c d s a r e l i c s o n t h e d i 伍c u l t yo ft h ee l l i p t i cc a l v ed i s c r e t el o g a r i t h mp r o b l e m 但c d i j p ) 1 ks p e e do fs i g n a t u r e g e n e r a t i o na n ds i g n a t u r ec h e c k i n go fe c d s a i se f f e c t i v e l yi m p r o v e db ya p p l i c a t i o no ft h ee c c o p t i m i z e dp r i n c i p l et oe c d s a b a s e d a b o v ed i s c u s s i o n , t h eo p t i m i z e de c d s ai sa p p l i e di ne l e c t r o n i cg o v e r n m e n t s y s t e m x m l f o r e l e c t r o n i c d o c u m e n t s t r a n s m i s s i o n i sa d e v e l o p i n g t r e n d o f e - g o v e m m e n l w h i c h i sg r e a t l ys i g n i f i c a n tf o ra c h i e v i n gs t a n d a r d i z a t i o no fe l e c t r o n i cd o c u m e n t s n c d e s i g no fx m ld i g i t a ls i g n a t u r eb a s e do ne c d s a i sp r o p o s e d t h e nt h ei d e ai sr e a r m e d , 缸 j a s t , t h ef c a s i b i l i t yo ft h i sj d e ai sp r o v e d t h ep e r f o r m a n c eo ft h ed e s i g ni st e s t i f i e di nc e r t a i n d e g r e e u s i n gt h eo p t i m i z e de c d s ap r o d u c es i g n a t u r ei nt h ex m ld i g i t a ls i g n a t u r em a d et h e x m l s i g n a t u r et e c h n o l o g yc o n c u r r e n t l yh a v et h ex m ld i g i t a ls i g n a t u r es t a n d a r da n dt h ee c d s a a d v a n t a g e s , w h i c hi sp r o v e db yt h et e s t , s ot h et h e s i sr e s e a r c hi sw e l lp r a c t i c a lv a l u e k e y w o r d s ：e l l i p t i cc u r v e sc r y p t o s y s t e m ；p r o j e c t i v ec o o r d i n a t e s ；s c a l a l rm u l t i p l i c a t i o n ； e l l i p t i cc u r v ed i g i t a ls i g n a t u r ea l g o r i t h m ( e c d s a ) ；e l e c t r o n i cg o v e r n m e n t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：塞盥日期：堋年；月厅日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：盔援遂导师签名：! ：至兰! 丛 日期：2 _ o 。7 年弓月5 h 第1 章绪论 1 1 研究背景与动机 1 1 1 信息安全概述 第1 章绪论 2 1 世纪是信息的时代、知识经济的时代。信息成为社会发展的重要战略资源， 信息技术改变着人们的生活和工作方式社会信息化已成为当今世界发展的主要潮 流。随着计算机在军事、政治、金融、商业等部门的广泛应用，社会对计算机的依 赖越来越大，如果计算机系统的安全受到破坏将导致社会的混乱并造成巨大损失。 因此，确保计算机系统的安全已成为世人关注的社会问题和计算机科学的热点研究 课题【1 1 。 i n t e m e t 是一个面向大众的开放系统，对于信息的保密和系统的安全考虑得并不 完备，加上计算机网络技术的飞速发展，网上的攻击与破坏事件层出不穷。现在， 计算机犯罪已经开始渗入到政府机关、军事部门、商业、企业等单位，如果不加以 保护的话，轻则干扰人们的日常生活，重则造成巨大的经济损失，甚至威胁到国家 的安全，所以网络安全问题已经引起许多国家，尤其是发达国家的高度重视，不惜 投入大量人力、物力和财力来提高计算机网络系统的安全性。 1 、常见的安全威胁与攻击 迄今为止，网络上已经存在着无数的安全威胁与攻击，按照攻击的性质、手段、 结果等暂且将其分为窃取机密攻击、非法访问、恶意攻击、社交工程、计算机病毒、 不良信息资源和信息战等几大类。 2 、计算机网络系统安全内涵 国际标准化组织i s o 在其网络安全体系设计标准( i s 0 7 4 9 8 - 2 ) 中定义了计算机 网络系统的五大安全服务功能：身份认证服务、访问控制服务、数据加密服务、数 据完整性服务和不可否认服务，比较全面地描述了计算机系统安全的内涵。 从另一个角度可将计算机系统安全划分为计算机系统的设备安全和计算机系统 的信息安全。火灾、水灾、雷击、霉变等都可能导致计算机设备的损坏，用户一般 都能直接发现。而对信息安全的危害行为，很多情况并不留下痕迹，常常是信息安 全已经受到危害，用户还不知道。 本文中所提到的计算机网络系统安全，主要指信息安全( 又称为数据安全) 3 、信息安全的要求 确保网络系统的信息安全是网络安全的目标，对任何种类的网络系统而言，就 是采取措施保护数据，使之免受未授权的泄漏、篡改和毁坏。信息安全性主要包括 信息的保密性( c o n f i d e n t i a l i t y ) 、完整性( i n t e g r i t y ) 、可用性( a v a i l a b i l i t y ) 、真实性 江南大学硕士学位论文 ( a u t h e n t i c i t y ) 、实用性( u t i l i t y ) 、占有性( p o g s c s s i o n ) 1 1 2 信息网络安全研究现状及发展方向 我国信息网络安全研究历经了通信保密、数据保护两个阶段，正在进入网络信 息安全研究阶段【n 。现己开发研制出防火墙、安全路由器、安全网关、黑客入侵检 测、系统脆弱性扫描软件等。但因信息网络安全领域是一个综合、交叉的学科领域 它综合了利用数学、物理、生化信息技术和计算机技术的诸多学科的长期积累和最 新发展成果，提出系统的、完整的和协同的解决信息网络安全的方案，目前应从安 全体系结构、安全协议、现代密码理论、信息分析和监控以及信息安全系统五个方 面开展研究，各部分相互协同形成有机整体。 国际上信息安全研究起步较早，力度大，积累多，应用广，在7 0 年代美国的网 络安全技术基础理论研究成果“计算机保密模型”的基础上，指定了“可信计算机 系统安全评估准则”，其后又制定了关于网络系统数据库方面和系列安全解释，形 成了安全信息系统体系结构的准则。 安全协议作为信息安全的重要内容，其形式化方法分析始于8 0 年代初，目前有 基于状态机、模态逻辑和代数工具的三种分析方法，但仍有局限性和漏洞，处于发 展的提高阶段。 作为信息安全关键技术的密码学，近年来空前活跃，美、欧、亚各洲举行的密 码学和信息安全学术会议频繁。1 9 7 6 年美国学者提出的公开密钥密码体制，克服了 网络信息系统密钥管理的困难，同时解决了数字签名问题，它是当前研究的热点。 而电子政务、电子商务、电子现金等的安全性已是当前人们普遍关注的焦点， 目前正处于研究和发展阶段，它带动了论证理论、密钥管理等研究，由于计算机运 算速度的不断提高，各种密码算法面临着新的密码体制的挑战。量子密码、d n a 密 码、混沌理论等密码新技术正处于探索之中。 因此网络安全技术在2 l 世纪将成为信息网络发展的关键技术，2 1 世纪人类步 入信息社会后，信息这一社会发展的重要战略资源需要网络安全技术的有力保障， 才能形成社会发展的推动力。在我国信息网络安全技术的研究和产品开发仍处于起 步阶段，仍有大量的工作需要我们去研究、开发和探索，以走出有中国特色的产学 研联合发展之路，赶上或超过发达国家的水平，以此保证我国信息网络的安全，推 动我国国民经济的高速发展1 2 j 。 1 1 3 论文研究意义 确保信息安全是一个系统工程，必须综合采用各种措施才能奏效。主要包括信 2 第1 章绪论 息系统的硬件结构安全技术、操作系统安全技术、数据库安全技术、密码技术、病 毒防治技术、信息隐藏技术、数字签名、防火墙、安全审计、入侵检测等。在这些 众多的技术措施中，信息系统的硬件结构安全和操作系统安全是确保信息安全的基 础，其它都是关键技术本文主要论述密码技术和数字签名技术。 在以计算机文件为基础的现代事务处理中，应采用电子形式的签名，即数字签 名( d i g i t a ls i g n a t u r e ) 。数字签名提出的初衷就是在网络环境中模拟日常生活中的 手工签名或印章，而数字签名又具有许多传统签名所不具有的优点，如签名因消息 而异，同一个人对不同的消息其签名结果不同，原有文件的修改必然反应为签名结 果的改变，原文件与签名结果两者是一个混合的不可分割的整体等，数字签名比传 统签名更具可靠性。 数字签名的特性及可抵御的网络威胁可以概括为身份鉴别，可辨别信源的真实 性且防冒充；数据完整性保护，抵御数据的篡改或重排；不可抵赖性，信源事后不 可否认以防其抵赖；一般还使用加密技术保护信息机密性，以防截听攻击；加入流 水号等技术，可防重放攻击。特别是其身份签别、数据完整性和不可抵赖性在电子 商务、电子政务等领域中有很重要的作用。 随着计算机科学技术的发展，电子政务、电子商务、电子金融等系统得到广泛 的应用，数字签名的问题就更加突出、更加重要，在这些系统中数字签名问题不解 决是不能实际应用的。 事实上数字签名不是一种具体的技术实现，它是基于各种加密技术组合的解决 方案。本研究的重点是数字签名算法在椭圆曲线密码体制中的实现。1 9 8 5 年 n k o b l i t z 和m i l l e r 各自独立提出将椭圆曲线用于密码算法其根据是有限域上的椭 圆曲线上的点群中的离散对数问题。它是比因子分解问题更难的问题，许多密码专 家认为它是指数级的难度。从目前已知的最好求解算法来看，1 6 0 比特的椭圆曲线 密码算法的安全性相当于1 0 2 4 比特的r s a 算法。椭圆曲线数字签名算法( e c d s a ) 的安全性依赖于椭圆曲线离散对数问题( e c d l p ) 的难解性，具有安全性高，计算量小， 处理速度快，存储空间占用小，带宽要求低，灵活性好等优点。但是现有的e c d s a 算法的实现速度仍不能满足实际应用的需要。 本研究将从算法设计和优化的角度来改进现有的椭圆曲线实现数字签名的算 法。通过讨论椭圆曲线的选取问题进一步提高数字签名的安全性，通过对于算法快 速实现的研究提高数字签名的实用性。 1 2 论文结构 论文共分为六章，各章具体内容如下： 第一章简要阐明论文的研究背景和研究动机，从信息安全需求，信息安全技术 着手，引入椭圆曲线数字签名的研究与应用。 3 江南大学硕士学位论文 第二章介绍椭圆曲线加密系统。描述了密码学的基本概念、密码技术的发展、 对称密码体制和公开密码体制加解密原理以及典型的加解密算法。 第三章介绍了对椭圆曲线密码算法的研究。包括椭圆曲线用到的数学理论、椭 圆曲线的定义、椭圆曲线上的数学运算等，对椭圆曲线理论进行全面、详尽的论述。 并在此基础上，通过改变椭圆曲线上求两点和的运算公式，改进椭圆曲线密码体制 实现中的点乘算法，提出了优化的椭圆曲线。之后论述了椭圆曲线密码体制需要解 决的两个问题，从而指出进一步研究的方向。最后通过密钥长度、安全性等多方面 的特性对几种典型公钥算法进行比较，论述了椭圆曲线密码的优越性以及实用性。 第四章详细地介绍了对椭圆曲线数字签名的研究。从数字签名的原理开始讨论， 讲述了利用r s a 密码、e l g a m a l 密码实现数字签名，之后详细论述了数字签名在椭 圆曲线密码体制上的实现。并根据第二章论述中的改进算法，对e c d s a 进行了优化。 最后，简要介绍了若干种特殊数字签名。 第五章将改进后的e c d s a 应用到电子政务系统中。首先介绍电子政务系统的安 全需求，因电子政务系统复杂庞大，论文中仅论述电子公文传输的安全需求。在前 面各章的理论基础上，使用j a v a 语言和j c e ( j a v a 加密扩展) 工具，辅以x m l 文档解析 工具，在发送端生成数字签名，发送给接收方。接收方通过x m l 解析器对x m l j ：档 进行解析，然后进行验证。最后评价设计性能。 第六章总结论文主要完成的工作，提出今后的研究方向，最后展望研究前景。 4 第2 章密码学基础 第2 章密码学基础 2 1 密码学相关基本知识 1 、密码学基本概念 密码学包括密码编码学和密码分析学翻。密码编码学是研究对数据进行变换的 方法、技术和原理的学科，目的是隐藏数据的真实内容，对数据进行保护。密码分 析学是对加密的方法、技术和原理进行分析、攻击的学科，通过对加密方案和加密 数据进行分析，从而取得隐藏的信息。由此可知，密码学= 密码编码学+ 密码分析学。 密码学是- - f - 交叉学科，其理论基础是数学中的数论、信息论、概率论、组合论及 计算机科学、语言学、电子学等学科。 密码学的基本思想就是隐藏、伪装信息，使未经授权者不能得到消息的真正含 义，伪装消息的方法就是进行一组可逆的数学变换。一个密码系统通常简称为密码 体制( c r y p t o s y s t e m ) ，由以下五个部分组成。 ( 1 ) 明文空问m ：全体明文集合； ( 2 ) 密文空间c ：全体密文集合； 密钥空间k ：全体密钥集合，每一个密钥k 均由加密密钥k 和解密密钥组 成，即k _ ( 1 ( c ，) ； ( 4 ) 加密算法e ；由明文到密文的加密变换规则； ( 5 ) 解密算法d ：由密文到明文的解密变换规则。 明文和密文都是计算机所处理的数据，有时也称消息或报文。对于每一个确定 的密钥，加密算法将确定一个具体的加密变换，解密算法将确定一个具体的解密变 换，而且解密变换就是加密变换的逆变换。对于明文空间m 中的每一个明文m ，加 密算法e 在密钥l ( e 的控制下将明文m 加密成密文c ：c = e ( m ，k ) 。而解密算法d 在密钥l ( d 的控制下将密文c 解密出同一明文m ：m = d ( c ，l 【d ) = d ( e ( m ，k ) ， ) 。如图2 1 所示。 当我们强调一个密码系统的保密功能时，称该密码系统为加密系统；强调一个 密码系统的认证功能时，称该密码系统为签名系统；强调一个密码系统的密钥交换 功能时，称该密码系统为密钥交换系统。密码编码学的目的可以简单理解为小秘密 保护大秘密，即通过密钥来保护要加密的消息。 5 江南大学硕士学位论文 图2 1 密码体制 2 、密码技术的发展及分类 密码技术是一门古老的技术，大概自人类社会出现战争便产生了密码。密码的 发展经历了由简单到复杂、由古典到近代的发展历程，并且在它发展的各个阶段， 都为确保信息安全发挥了重要作用。 密码技术的发展历史大致可划分为三个阶段： 第一阶段，这时的密码学专家常常是凭直觉和信念来进行密码设计和分析，而 不是推理证明。1 9 4 6 年电子计算机出现，可用于密码破译，使得密码进入电子时代。 第二阶段，1 9 4 9 - 1 9 7 6 年间。1 9 4 9 年商农( c d s h a n n o n ) 把信息论、密码学和 数学结合起来，研究了“保密系统的数学结构”，发表了题为 保密系统的通信理 论的著名论文。这篇文章把密码置于事件的数学基础之上，标志着密码学作为一 门学科形成。然而这一阶段的密码学发展缓慢，公开的文献也很少。 第三阶段，1 9 7 6 年至今。1 9 7 6 年d i f ! f i e 和h e l l m a n 发表的密码学的新方向首 次证明了在发送端和接收端无密钥传输的保密通信是可能的，从而开创了公钥密码 学的新纪元 4 l 。并指明t s h a n n o n 在1 9 4 9 年提出的将密码建立在某些己知的数学难题 之上的具体实现途径。这一阶段，密码技术发展极为迅速。 目前，密码理论与技术主要包括两部分，即基于数学的密码理论与技术f 其中包 括公钥密码、分组密码、流密码、认证码、数字签名、h a s h 函数、身份识别、密钥 管理、p k i 技术等) 和非数学的密码理论与技术( 包括信息隐形、量子密码、基于生物 特征的识别理论与技术1 。基于数学的密码理论与技术中，如果一个密码体制的& = k 。 或由其中一个很容易推出另一个，则称为私钥( 单钥或对称) 密码体制，其典型代表 是美国的数据加密标准d e s ；另一种是如果在计算上不能由k 推出，这样将k 公 开也不会损害l ( d 的安全，该体制称为公钥( 双钥或非对称) 密码体制，加密密钥公开 而解密密钥保密，其典型代表是r s a 体制。 6 第2 章密码学基础 2 2 对称密码体制 1 、对称密码体制定义 使用对称加密算法的加密体制称为对称密码体制。对称密码系统是从传统的简 单换位、代替密码发展而来，仍属于传统密码。代替密码( s u b s t i t u t i o nc i p h e r ) 其基本 思想就是根据某种算法将明文中一个字符换成另一个字符。密文和明文中的各对应 字符的相对位置保持不变。接收者对密文进行逆替换就可以恢复出明文来。如：凯撒 密码、多字母代替密码、多表代替密码等。换位密码( p c 瑚u 把c i p h 蜘其基本思想是 按某种算法将明文信息中的字符通过置换而形成新的捧列，即不改变明文中信息本 身的形式，仅改变其在明文中的位置，如转轮密码。加解密原理如图2 2 所示。 图2 2 对称密码系统原理框架 在图2 2 中，m 表示明文，c 表示密文，e 表示加密算法，d 表示解密算法，k 表 示秘密钥，i 表示密码分析员进行密码分析时掌握的其他有关信息，虚线表示安全通 道，m l 表示密码分析员对m 的分析和猜测。 2 、典型算法d e s 现今使用最广泛的对称密码体制d e s ( d a t ae n c r y p ts t a n d a r d ) 是f h i b m 公司开 发，1 9 7 7 年i 扫n i s t ( 美国国家标准局) 定为美国国家标准，用来保护一些未公开的档 案。由于d e s 中的密钥只有5 6 位，为了提高其安全性，人们提出了一些改进算法如 三重d e s 。d e s 具有的优点是在硬件和软件方面的完成速度很快。 d e s 是分组乘积密码，它用5 6 位密钥将“位的明文转换为6 4 位密文，其中密钥 总长为6 4 位，另夕f 8 位是奇偶校验位。其加密过程也可同样用于解密。 ( 1 ) 通过初始换位i p ，首先将输入的二进制明文块1 变换成t o = w ( t ) 。 ( 2 ) t i 经过1 6 次函数f 的迭代。 ( 3 ) 最后通过逆初始换位1 得到6 4 位二进制密文输出。 由于d e s 提出己经很长时间了，5 6 位的密钥相对于当前的高速计算机来说己经 太短。目前依靠i n t e r a c t 分布计算能力，用穷举法破译d l 三s 已成为可能。1 9 9 7 年3 月 7 江南大学硕士学位论文 1 3 日，美国科罗拉多州程序员v e r s e r 在i n t e m e t 上征集了数万名志愿者，在协同工作 下，用了9 6 天成功地破译了d e s 。 本文主要讨论的是公开密钥算法，这里仅简要介绍d e s 算法思想。 3 、对称密码体制特点 对称加密算法的实现速度快，加密速度可达到每秒数兆到数十兆，有的甚至超 过每秒百兆。对称算法的这个特点使其具有广泛的应用，特别适合于海量数据的加 密。因为算法不需要保密，所以制造商可以开发出低成本的芯片以实现数据加密。 但对称加密系统最大的问题是密钥的分发和管理非常复杂、代价高昂。当用户 群很大、分布很广时，密钥的分配和保存都非常困难。因为，对于具有n 个用户的 网络，需要n ( n 一1 犯个密钥。对称加密算法的另一个缺点是不能实现数字签名。 4 、对称密码体制的安全性 对称密码系统的安全性依赖于加密算法的强度和密钥的秘密性。加密算法必须 具有足够的强度，使得仅根据密文去解密信息在计算上是不可能的，没有必要确保 算法的秘密性，但必须保证密钥的秘密性。 2 3 公钥密码体制 1 、公钥密码体制定义和特点 在公钥密码体制产生和应用以前的整个密码学史中，所有的密码算法，包括原 始手工计算的和由机械设备实现的以及现在通过计算机软硬件实现的，基本上都是 基于代替和置换这两个基本工具。而公钥密码体制则为密码学的发展提供了新的理 论和技术基础，同时也是密码学发展的新的里程碑。一方面公钥密码算法的基本工 具突破传统的代替和置换，是数学函数；另一方面公钥密码算法是非对称的形式使 用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有划时代的意义。可 以说公钥密码体制的出现是密码学史上一个最大的而且是惟一真正的技术革命 公钥加密算法( 非对称加密算法) ，使用的加密密钥与解密密钥不同，并且解 密密钥不能根据加密密钥在合理的时间内计算出来的加密算法。加密密钥可以公 开，称为公钥，任何人都可以用公钥加密消息。解密密钥需要保密，称为私钥， 只有拥有相应私钥的人才能解密消息如图2 3 所示。使用公钥加密算法的加密体制称 为公钥加密体制，又称非对称加密体制。 8 第2 章密码学基础 图2 3 公钥加密系统原理框图 其中c ，d ，e ，i ，m ，m 1 含义与图2 - 2 同，k 1 表示公开密钥，k 2 表示秘密密钥。 公钥加密系统都是基于数学难题，计算非常复杂，它的实现速度比私钥加密系统要 慢许多。当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 倍。但公钥加密系统所需要的密钥数量少，对于具有n 个用户的网络，仅需要2 n 个密钥。公钥加密系统还能够很容易的实现数字签名。因 此，适合于电子商务、电子金融、电子政务的应用需要。下面介绍几种典型的公钥 密码算法。 2 、基于大整数因子分解困难性的r s a 密码 1 9 7 8 , ，r r i v e s ，a s h a m i r 并1 la d l e m a n 提出一种基于大合数因子分解困难性 的公开密钥密码，简称r s a 算法。它是迄今为止在理论上最为成熟完善的公钥密码 体制，既可以用于加密，又可以用于数字签名，安全、易懂，因此该体制已经得到 广泛的应用和实践1 5 】。 ( 1 ) r s a 密钥的产生 选取两个保密的大素数p , 0q 。 计算n = p x q ，妒( n ) = ( p - 1 x q - 1 ) ，其中“n ) 是n 的欧拉函数值 任选一整数e ，满足1 c 3 ) ( q 称为g f i q ) 的特征) 或 g f ( 2 “) ( m z + ) 。采用射影坐标系令x = 磋，y = ( z 删，代入可得 y 2 z + a l x y z + a 3 y z 2 = x 3 + a 2 x 2 z + a 4 x z 2 + a 6 2 3 。 其中a l ，a 2 ，a 3 ，a 4 ，a 6 k 且o ，是e 的判别式，参数具体定义如下： d 2 = a ；+ 4 a ： d = 2 a + a t a 3 d 6 = a ；+ 4 a 6 d 。= a ；a 6 + 4 a 2 a 6 a t a 3 a 4 + a 2 a ；一a ： a = _ d ；d 8 8 d ：- 2 7 d ：+ 9 d 2 d 4 d 6 若l 黾域k 的扩域，则e 上的l 有理数点的集合是： e ( l ) = 歉，y ) l x l ：y 2 + a l x y + a 3 y x 3 a 2 x 2 a 4 x a 6 = o ，u ( 固，其中是无穷远 点。通常用e 表示一条椭圆曲线。称e 是域l 上的椭圆曲线，记为e l k ，并称e 为k 的基础域，这是因为系数a ；( i = 1 , 2 ，6 ) 均为域l ( _ 上的元素。条件a o 确保椭圆曲线 是光滑的，即曲线上的任意一点没有两个或两个以上不同的切线存在。点o c 是曲线 上的惟一的一个无穷远点。 1 虱3 - 2 ，3 3 分别描述了实数域r 上的椭圆曲线e 。，e ：，其中e l ( r ) “畸和 e ：( r ) ， 时。 一 。 ， 。， ：j ： i p + ) c 孕+ 芦 。 t ，广n - 、。 。 = x c x 拳1 图3 2 实数域r 上的椭圆曲线e ， 图3 3 实数域r 上的椭圆曲线e 2 江南大学硕士学位论文 5 、w e i e r s t r a s s ，y 程的简化 定义在域k _ l 的w e i e r s t r a s s 方程能够用变量的相容性变换来简化。由w e i e r s t r a s s 方程给出的定义在域k 上的两个椭圆曲线e l 和e 2 ，e 1 ： y 2 + a l x y + a 3 y = x 34 - a 2 x 2 + a x + a 6 ，e 2 ：y 2 + i l x y + i 3 y = x 3 + i 2 x 2 + i 4 x + i 6 被 称为在域k 上是同构的，若存在u , r , s ，t eu o ，使用变量变换 ( x ，y ) 一( u 2 x + r ，u 3 y + u 2 s x + t ) 把方程e l 变成方程e 2 。 定义在域k 上的w e i e 搐仃a 鹧方程e ：y 2 + a l x y + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 ，使用 变量的相容性变换来简化，我们分三种情况讨论。 域k 的特征不等于2 或3 变量的相瓤菱换( x ，y ) 一( 学，案巫气 垫- ) 把e 变换为曲线y 2 = x 3 + a x + b ，其中a , b k ，a = 1 6 ( 4 a 34 - 2 t 0 2 ) 。 域k 的特征等于2 若a l - - 0 , 变量的相容性变换( x ，y ) 一( x + a ：，y ) 把e 变换为曲线 y 2 + c y = x 3 + a x + b ，其中a ，b ，c k ，= c 4 。注意，这样的曲线称为超奇异椭圆 曲线。 若a ，o ，则变量的相容性变换( x ，y ) 一( a ；x + a _ 。l ，a ，3 y + 三垒：堕) 把e 变换为曲 线y 2 + x y = x 3 + a x 2 + b ，其中a ，b k ，a = b 。注意，这样的曲线称为非超奇异 椭圆曲线。 域k 的特征等于3 若a ；= a 2 ，则变量的相容性变换( x ，y ) 一( x ，y - i - a l x + a 3 ) ( 其中 d 2 = a ；+ a 2 ，d 4 = a 4 a l a 3 ) ，把e 变换为曲线y 2 = x 3 + a x + b ，其中a , b k ，= - a 3 注意，这样的曲线称为超奇异椭圆曲线。 若a ：击a 2 ，则变量的相容性变换( x ，y ) 一( x + d d 4 ，+ a l 鲁+ a ，) ( 其中 d 2 = a ：+ a 2 , d 4 = a - a l a 3 ) ，把e 变换为曲线y 2 = x 3 + a x 2 + b ，其中a ，b k ， a = a 3 b 。注意，这样的曲线称为非超奇异椭圆曲线。 6 、离散对数问题 为了用椭圆曲线构造密码体制，我们需要找出椭圆曲线上的数学困难问题。椭 圆曲线离散对数问题，简记为e c d l p ( e l l i p t i cc u r v e d i s c r e t el o g a r i t h mp r o g r a m ) ， 是构造椭圆曲线密码体制的数学基础，即对于椭圆曲线e 上两点p 、q ，如果已知 存在k 满足：o = k p ，则求解k 的问题称为椭圆曲线上的离散对数问题。 除了几类特殊的椭圆曲线以外，对于一般e c d l p 目前尚没有找到有效的求解方 第3 章椭圆曲线公钥密码体制的研究 法。于是可以在这个循环子群中建立任何基于离散对数困难性的密码，并称这个密 码为椭圆曲线密码。因此，诸如e 1 g a m a l 密码、d i f f i e h e l l m a n 密钥分配协议、美国 数字签名标准d s s 等许多基于离散对数问题的密码体制都可以在椭圆曲线群上实 现。椭圆曲线密码方案众多，通常所提到的椭圆曲线密码大多是指e 1 g a m a l 型椭圆 曲线密码。 3 2 椭圆曲线上的加法运算规则 令e 是一个定义在域k 上的椭圆曲线。根据“弦和切线”法贝| j ，e ( k ) 上的两个 点相加得到e ( k ) 上的第三个点。点集合e ( k ) 及其这种加法运算构成一个加法交换 群，并且m 为其无穷远点。这个群被用来构造椭圆曲线密码体制嘲。 椭圆曲线上加法运算规则： ( 1 ) p = b l ，y l j 和q = b 2 ，y 2 j 是椭圆曲线上的两个不同的点，则p + q = r 定 义如下，画一条连接p 和q 的真线，这条直线与椭圆曲线交于第三点，则这个交点关 于x 的对称点就是r 点。图3 4 是它的几何表示。 r彩 jy 2 = j x ：3 - x f 确 凇 o 拈 l印 ! 一一 | i 叩 i j 。 ： 图3 4 椭圆曲线上加法运算p + q = r ( 2 ) p = ( x 。，y ，) 和0 = 【x ：，y ：) 是椭圆曲线上的两个相同的点，贝j j p + q = r 就 是计算p 的倍点，即2 p = r ，当p 毒p 时，定义如下，在p 点画椭圆曲线的切线，这 条切线与椭圆曲线交于第二点，则这个交点关于x 的对称点就是r 点。图3 - 5 是它的 几何表示。 1 7 图3 啃椭圆曲线上加法运算2 p ：r 3 3 椭圆曲线加法运算公式及优化 3 - 3 1 基于g f ( 2 - ) 上捆曲线上加法定义 程：嚣1 2 嚣黧梨兰繁奇主黑刚硼蚴撇方 妻一：蕊一嚣嚣黑。篡箍赫糟踹 若p q ，那么 若p = q ，那么c z 仁：意詈卜+ 黾 第3 章椭圆曲线公钥密码体制的研究 3 3 2 曲线上加法定义的改进 用公式1 和公式2 求曲线上两点和均需要求有限域内的求逆运算，为了避免有 限域中运算复杂度很高的求逆运算，可以选用适当的射影坐标系。有限域内大整数 运算耗时较大，而域内平方运算和加法运算都可以比乘法运算较快速地实现1 9 】。为 了提高运算效率，人们不断的提出新的坐标系，减少求两点和运算中乘法运算的次 数【1 0 l 。现在已有多种射影坐标系被提出使用，该文采用由l o p e z 和d a h a b 提出的射 影坐标系。在椭圆曲线的仿射坐标方程y 2 + x y 铽3 + a 】【2 + b 中令：x = x z , y = y z 2 得到 射影坐标方程：y 2 + ) ( y z = x 3 z + a x 2 2 2 + b z 4 。在射影坐标下，设己知曲线上两点 p = ( x 1 ，y 1 ，z 1 ) 、q = ( x 2 , y 2 , z 2 ) ，那么另一点r = ( x 3 , y 3 五) = p + q 在z 1 = 1 情况下定义如 下： 菁p q ，那么( 3 ) 若p = - q , 那么( 4 ) a 三y 。z 户+ y 2 b = x l z 2 + 池 c = z 2 b d = b 2 ( c + a z z 2 ) e = a c z 3 - - e ) 【3 = a 2 + d + e f = l + x ，z 3 g ：x 3 + y ：z 。 y 3 = e f + z 3 ( ； 乙= x 1 2 x 3 - x l + b y 3 = b z 3 + x 3 ( a z 3 + y , z + b ) 使用公式3 计算两点和需要的计算量约为9 m + 4 s ( m ，s 分别表示有限域上的 乘法和平方运算所需要的时间) ，由于加法运算可以较快速的实现，在比较效率时 暂且忽略。其他坐标系中求两点和的运算公式这里不再赘述。计算p + q 域操作的数 目( a = 0 或1 ，z l = 1 ) ，各坐标系的运算量比较如表3 1 所示，其中# m 、# s 分别表 示有限域上的乘法和平方运算的运算次数。 表3 1 计算p + q 域操作的数目( a = o 或1 ，z 。= 1 ) 江南大学硕士学位论文 使用l o p e z 和d a h a b 提出的射影坐标系的效率是目前为止效率最高的。改变在 该坐标系下求两点和的运算公式，通过减少有限域上乘法运算的次数，可以进一步 提高运算效率。在射影坐标下，曲线上两点p 。= ( x ，z ，y ，z ，2 ) ，p 产( x 2 z 。，y 2 z 0 在 z l - - 1 的情况下，定义p 3 = p 。+ p 2 = ( x 3 z 3