（计算机科学与技术专业论文）椭圆曲线密码系统的研究与实现.pdfVIP

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：碎垒盈刮姿一 日期：塑生i _ 弓、lo 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：礁违邀 日期： 丝f 里：至：! 旦 导师签名：同期：丝! ! ：至：! 竺 北京邮电大学硕士学位论文 椭圆曲线密码系统的研究与实现 摘要 随着信息产业的不断发展和移动互联网的广泛应用，手机等移动 终端设备所能提供的服务越来越多样化，逐渐成为人们日常生活中不 可或缺的一部分，然而其安全问题也日益突出。如何有效的保护手机 用户的个人信息及数据安全，成为目前社会普遍关注的问题。密码学 作为信息安全技术的核心领域，提供了多种密码算法与应用协议以满 足人们实际应用的需要。椭圆曲线密码体制是其中一种基于椭圆曲线 离散对数问题的公钥密码体制，具有安全性高、速度快、密钥短、实 现时所需占用资源少等特点，特别适用于手机等资源有限的终端设 备。 论文围绕椭圆曲线密码系统的研究与实现这一课题展开，在针对 现有椭圆曲线加密技术进行深入研究的基础上，设计并实现了一个安 全高效的椭圆曲线密码系统。 论文首先讨论了课题的研究目的与意义，对公钥密码系统进行了 综述，概括介绍和分析了椭圆曲线密码体制的特点、现状及其发展趋 势。其次详细论述了椭圆曲线密码体制的原理，包括相关的数学基础 知识、基本概念，以及基于椭圆曲线密码体制的密钥交换、数据加密、 数字签名算法。接着重点研究了椭圆曲线上的各种点乘算法，提出了 一种基于混合坐标系统的改进的滑动窗口算法，有效的提高了运算效 率口最后提出了一种无需明文嵌入的带认证机制的加密方案，设计实 现了一个安全高效的椭圆曲线密码系统，并指出了进一步的研究方 向。 关键词：信息安全椭圆曲线椭圆曲线密码系统( e c o 有限域 点乘算法 北京邮电大学硕上学位论文 r e s e a r c ha n di m p l e m e n l 嗡t i o no f e l l i p t i cc u r v ec r y p t o s y s t e m a b s t r a c t a l o n gw i t ht h ec o n t i n u o u sd e v e l o p m e n to fi n f o r m a t i o ni n d u s t r ya n de x t e n s i v e u s eo fm o b i l ei n t e m e t ，m o b i l ep h o n eh a sb e c o m ea ni n d i s p e n s a b l ep a r to fo u r e v e r y d a yl i v e s t h em o b i l ep h o n ec a np r o v i d em o r es e r v i c e st h a ne v e rb e f o r e ，w h i c h a l s oi n v o l v em o r es e c u r i t yp r o b l e m s t h ep r o t e c t i o no fu s e r sp e r s o n a li n f o r m a t i o n a n dd a t as e c u r i t yh a sb e c o m ea ni n t e r n a t i o n a li s s u e c r y p t o g r a p h yi st h ec o r ed o m a i n i nt h ei n f o r m a t i o ns e c u r i t yt e c h n i q u e i tp r o v i d e sm a n ya l g o r i t h m sa n dp r o t o c o l st o m e e tp r a c t i c a ln e e d e l l i p t i cc u r v ec r y p t o g r a p h yi sak i n do fp u b l i ck e yc r y p t o g r a p h y b a s e do nt h ee l l i p t i cc u l v ed i s c r e t el o g a r i t h mp r o b l e m i ti ss a f e ra n df a s t e rt h a nt h e t r a d i t i o n a la l g o r i t h m ，w h i c hm a k e si te s p e c i a l l ys u i tf o rm o b i l et e r m i n a l t h i sp r o p o s e dr e s e a r c hi sa i m e dt oi n v e s t i g a t et h ed e s i g na n di m p l e m e n t a t i o no f t h e e l l i p t i c c u r v ec r y p t o s y s t e m b a s e do n i n d e p t hs t u d y o f e l l i p t i c o l i v e c r y p t o g r a p h y ，t h ei m p l e m e n t a t i o no fas a f ea n de f f i c i e n te l l i p t i cc u r v ec r y p t o s y s t e mi s a c h i e v e d i nt h i st h e s i s ，t h ep u r p o s ea n ds i g n i f i c a n c eo ft h i st o p i ci sd i s c u s s e d a tf i r s t ，a n o v e r v i e wo ft h ep u b l i c - k e yc r y p t o s y s t e ma n di n t r o d u c t i o nf o rt h ec h a r a c t e r i s t i c s ， s t a t u sq u oa n de v o l u t i o nt r e n do fe l l i p t i cc u r v ec r y p t o s y s t e mi sm a d e s e c o n d l y , t h e p r i n c i p l eo fe c c ，i n c l u d i n gt h em a t hf o u n d a t i o na n db a s i cc o n c e p t i o na r ee x p o u n d e d d a t ae n c r y p t i o na l g o r i t h m ，k e ye x c h a n g ea l g o r i t h ma n dd i g i t a ls i g n a t u r ea l g o r i t h m b a s e do nt h ee l l i p t i co l i v ee n c r y p ts c h e m ea r ea n a l y z e d m e a n w h i l e ，t h es c a l a r m u l t i p l i c a t i o na l g o r i t h m i s m a i n l ys t u d y ，a n di m p r o v e ds c a l a rm u l t i p l i c a t i o n a r i t h m e t i ci sb r o u g h tf o r w a r d a c c o r d i n g l yt h ee f f i d e n c yo fo p e r a t i o ni si m p r o v e d t h i r d l y ，t h ei m p l e m e n t a t i o no fas a f ea n de f f i c i e n te l l i p t i c c u r v ec r y p t o s y s t e mi s a c h i e v e d an e w e n c i p h e r m e n ts c h e m et h a th a st h ea b i l i t yo fc e r t i f i c a t i o na n dw i t h o u t p l a i nt e x te m b e d d i n gi sp r o p o s e d f i n a l l y ，at e s tf o rt h es y s t e mi sc o n d u c t e da n d p r o p o s a l sf o rt h er e s e a r c hd i r e c t i o na r em a d e i i r 一 ，v j r 北京邮电大学硕二i ：学位论文 k e yw o r d s ：i n f o r m a t i o ns e c u r i t y e l l i p t i cc u r v e c r y p t o s y s t e m ( e c c ) f i n i t ef i e l d s c a l a rm u l t i p l i c a t i o n i n e l l i p t i cc u i v e a l g o r i t h m ， 1 一 r ，毛 _ i i 北京邮电火学硕士学位论文 目录 第一章绪论。1 1 1 课题的研究背景和意义。1 1 1 1 手机安全问题现状1 1 1 2 研究目的与意义2 1 2 椭圆曲线密码系统3 1 3e c c 研究现状及发展方向。4 1 4 论文结构6 第二章密码学基础7 2 1 密码学历史7 2 2 密码系统的组成7 2 3 对称密码体制8 2 3 1 对称加密的原理9 2 3 2 对称加密的特点9 2 4 公钥( 非对称) 密码体制10 第三章椭圆曲线密码体制12 3 1 群和域12 3 2 椭圆曲线基础13 3 2 1 椭圆曲线的基本概念13 3 2 2 椭圆曲线的群运算1 4 3 3 不同坐标系下椭圆曲线加法运算1 5 3 3 1 射影坐标下的加法运算1 6 3 3 2j a c o bja n 和j a c o bia n c h u d n o v s k y 坐标下的加法运算16 3 3 3m o difie dj a c o bia n 坐标系下的加法运算1 7 3 3 4 混合坐标系下的效率分析18 3 4 椭圆曲线密码体制的应用1 9 3 4 1 椭圆曲线密码系统的参数19 3 4 2 椭圆曲线密钥交换方案e c d h 。1 9 3 4 3 椭圆曲线加密方案e c e ig a m ai 2 0 3 4 4 椭圆曲线数字签名方案e c d s a 2 1 3 5 对椭圆曲线密码系统的攻击。2 3 第四章椭圆曲线点乘算法的研究2 5 4 1 二进制平方乘算法2 5 t 、 北京邮电大学硕：l ：学位论文 4 2 窗口法2 6 4 2 1 固定窗口算法2 6 4 2 2 滑动窗口算法。2 6 4 3 非相邻表示型( n a f ) 算法2 7 4 4n a f w 滑动窗口算法。2 8 4 5 改进的n a f w 滑动窗口算法2 9 第五章椭圆曲线密码系统的实现3 2 5 1 系统总体设计。3 2 5 2 系统各模块的设计与实现3 4 5 2 1 有限域上的大整数运算模块3 4 5 2 2 椭圆曲线参数生成模块3 8 5 2 3 椭圆曲线上的点操作模块。4 3 5 2 4 加密与解密模块4 8 5 3 附加算法简介5 2 5 3 1 散列算法s h a 1 5 2 5 3 2 伪随机数的生成5 3 5 4 系统实现。5 4 5 4 1 系统环境5 4 5 4 2 系统功能演示5 4 5 4 3 测试结果分析5 9 第六章总结与展望6 0 参考文献6 1 致谢6 5 攻读学位期间发表的学术论文。6 6 2 一k卜 1 _ i 北京邮电人学硕+ 卜学位论文 第一章绪论 1 1 课题的研究背景和意义 1 1 1 手机安全问题现状 随着3 g 时代的到来和移动互联网的普及，手机在人们的生活中扮演着越来 越重要的角色。中国互联网络信息中心( c n n i c ) 发布的第2 5 次中国互联网 发展状况统计调查报告显示，2 0 0 9 年底我国手机上网用户数已经超过2 3 7 亿。 手机上网在方便用户的同时，也不得不开始面对网络攻击、安全威胁、未授权访 问、病毒木马攻击等一系列安全问题。与传统手机相比，智能手机具有更加丰富 的内容，更加强大的功能以及硬件设备的可升级性，是集通话、短信、网络接入、 影视娱乐、商务办公等为一体的综合性个人手持终端设备，能够真正实现通信， 电脑和互联网的融合。根据英国科技分析公司g a r t n e r 调查，全球2 0 0 8 年销售 了超过1 3 9 万部智能手机，与2 0 0 7 年相比增长1 3 9 。与此同时，智能手机又 因其开放的操作系统给不法分子留下了可乘之机，与p c 上各种病毒及恶意流氓 软件肆虐的现状雷同，智能手机平台上也开始出现了各种各样的病毒及恶意软 件，极大的威胁了机主的信息安全。 手机病毒和其它计算机病毒一样，也是一种计算机程序，具有传染性、破坏 性。这些恶意软件可以利用发送短信、彩信、电子邮件、浏览网站、下载铃声等 方式进行传播，可能会导致用户手机死机、关机、资料被盗被删、向外发送垃圾 邮件、拨打电话等，甚至还会损毁s i m 卡、芯片等硬件，给用户带来极大的损失。 最早的手机病毒出现在2 0 0 0 年，当时，手机公司m o v i s t a r 收到大量由计算机发 出的名为“t i m o f o n i c a 的骚扰短信，该病毒通过西班牙电信公司“t e l e f o n i c a ” 的移动系统向系统内的用户发送脏话等垃圾短信。事实上，该病毒最多只能被算 作短信炸弹。真正意义上的手机病毒直到2 0 0 4 年6 月才出现，那就是“c a b i r ” 蠕虫病毒，这种病毒通过诺基亚6 0 系列手机复制，然后不断寻找安装了蓝牙的 手机。之后，针对手机的各类恶意软件开始迅速发展，到目前已经出现约有1 0 0 0 多种。 3 g 所带来的最大影响就是传统的语音业务会越来越少，数据业务、网络应用 则会越来越多，而这些业务的推广无疑会使手机面临一个非常大的安全问题。恶 意软件可能通过电子邮件和信息附件、下载应用程序以及蓝牙等方式传播，此外， 网络钓鱼诈骗、垃圾邮件和移动间谍软件也开始将魔掌伸向移动通信设备，而黑 客们也在通过新型社交网络，采用一些狡猾的伎俩诱使用户安装这类恶意软件。 与此同时，人们对手机安全问题也越来越重视，m c a f e e 在m w c 上公布的调 北京邮i 乜大学顾1 ：学位论文 查数据表明，大部分的消费者开始关心手机安全： 超过8 6 的消费者担心接收不适当或来路不明的内容，被欺诈或资料遗失 或被窃。 超过7 2 的用户对安全移动服务表示关心。 有近1 4 的全球移动用户已直接感染或已经知道有人被感染手机病毒。 手机等移动设备具有存储容量小、计算速度慢、传输时延迟较大等特点，现 有环境中的很多安全机制都不完全适用于手机等移动终端，因此，研究适合嵌入 式环境中手机等移动终端使用的有效的安全机制是刻不容缓的。 1 1 2 研究目的与意义 针对智能手机的安全问题，项目组提出一种可在移动智能手机嵌入式环境中 普遍部署实施的高可靠的安全机制基于可变指令系统的安全机制。它可以有 效的防止恶意代码对应用的核心功能的入侵，保护用户数据以及个人信息安全， 为用户使用要求高度安全和可靠性的业务( 如电子支付) 提供了附加的安全性和 可靠性，保障手机平台安全，从而实现更加可靠的文件访问控制和信息数据管理。 当对敏感信息进行传输时，对信息的保护就是必不可少的，密码学为我们提 供了有力的支持。用户用一个加密密钥对要保护的数据进行加密，加密后的数据 只能被相应的解密密钥恢复，非法用户则因为没有解密密钥而无法取得真实数 据。根据密钥类型的不同，可以将现代密码技术分为两类：一类是对称密码体制， 另一类是公钥密码体制。公钥密码体制从根本上克服了对称密码体制在密钥分配 上存在的困难，且易于实现数字签名，因而得到了广泛的应用。目前常用的公钥 密码系统有三类：( 1 ) 基于大整数因子分解问题的系统( 代表性的有r s a 体制砼1 和 r a b i n 体制口1 ) ；( 2 ) 基于有限域的乘法群上离散对数问题的系统( 代表性的有d s a 数字签名算法h 1 和d i f f i e - h e l l m a n 密钥协商协议畸1 ) ；( 3 ) 基于椭圆曲线离散对数 问题的椭圆曲线密码系统。 其中，椭圆曲线密码系统是目前所有公钥密码系统中单位密钥安全性最高的 密码系统，逐渐成为近年来研究的热点。椭圆曲线公钥密码体制现在已经得到了 世界上广泛的认可，许多国际标准化组织( 政府、工业界、金融界、商业界等) 都将各种椭圆曲线密码体制作为其标准化文件向全球颁布。与r s a 体制相比，椭 圆曲线密码体制在应用上具有安全性能更高、计算量小、处理速度快、存储空间 占用小、带宽要求低等很多技术上的优点，更适合于智能手机、p d a 等这类处理 能力、存储空间、带宽功耗都受到一定限制的设备的使用。 本文的目的是在深入研究椭圆曲线密码系统的基础之上，针对智能手机安全 性项目需求设计实现一个安全高效的椭圆曲线密码系统原型，实现信息的加密及 解密，从而达到保障手机平台的安全性，有效的屏蔽恶意软件，为用户提供数据 2 北京邮电人学硕十学位论文 和个人信息的保护的目的。它可以提升终端设备的安全性，高效的完成信息的加 密解密处理，为手机用户提供更好的安全性和可靠性。 1 2 椭圆曲线密码系统 1 9 8 5 年，v m i l l e r 和n k o h l i t z h l 分别独立地提出了椭圆曲线密码体制 ( e l l i p t i cc u r v e sc r y p t o g r a p h y ，e c c ) ，这是继g o l d w a s s e r 和k i li a n 的素性检 验，l e n s t r a 的椭圆曲线大数分解后，椭圆曲线理论在密码学中的又一次全新应 用。它的思想仍然是在各种涉及有限域乘法群的公钥密码体制中，用有限域上椭 圆曲线构成的群来类比有限域的乘法群，从而获得类似的公钥密码体制。这类体 制的安全性是基于椭圆曲线上的离散对数问题求解的困难性，因而它具有一些其 他公钥密码体制无法比拟的优点：如在相同的安全强度下系统参数和密钥尺寸较 短( 女1 1 6 0 b i t s 的e c c 和1 0 2 4 b i t s 的r s a 具有相当的安全强度1 ) ，计算量小，处 理速度快，存储空间占用少，带宽要求低等。另外利用椭圆曲线建立的公钥密码 体制还具有两大潜在的优点：一是有取之不尽的椭圆曲线可用于构造椭圆曲线有 限点群；二是不存在计算椭圆曲线有限点群的离散对数问题的亚指数时间算法。 因此椭圆曲线密码系统被认为是下一代最通用的公钥密码系统。 椭圆曲线离散对数问题，即e c d l p ( e l l i p t i cc u r v eo i s c r e t el o g a r i t h m p r o b l e m ) 是椭圆曲线密码学的基础口1 。椭圆曲线离散对数问题可描述如下：给定 一条椭圆曲线e 和曲线上的一点p ，x p 表示点p 与自身相加x 次，b p x p = p + p + + p 共x 个p 相加。假设曲线e 上有一点q ，使得q = x p 成立，那么椭圆曲线离散对数问题就 是给定点p 、q 求解x 的问题。相对于q 点，p 点被称为基点。 与其他公钥密码体制相比，椭圆曲线密码体制具有以下突出的优点： ( 1 ) 安全性能更高 椭圆曲线离散对数问题的计算复杂度是完全指数级的，而r s a 和e 1 g a m a l 均为 亚指数算法。这体现为椭圆曲线密码系统的每比特密钥的安全强度更高，因此椭 圆曲线密码体制在抗攻击性方面具有绝对的优势。 ( 2 ) 曲线资源丰富 椭圆曲线资源丰富，同一个有限域上存在着大量不同的椭圆曲线，这也为其 安全性增加了额外的保证。 ( 3 ) 计算量小 在相同的计算资源条件下，l i s a 可以通过选取较小公钥来提高加密和签名验 证运算速度，使其效率略高于e c c ，但同时其安全性也会显著降低。在解密和签 名方面，e c c 要优于r s a 、d s a ，同时椭圆曲线密码系统的密钥生成速度也l p , r s a 快得多，因而e c c 具有更好的性能。 3 北京邮电人学硕上学位论文 表1 - 1 等强度密钥尺寸比较 e c c 密钥长度位r s a 密钥长度位破解时问m i p s 年r s a e c c 密钥长度比 1 0 65 1 2 1 0 4 6 ：1 1 6 01 0 2 4 1 0 1 1 7 ：l 2 1 02 0 4 81 0 2 01 0 ：1 6 0 02 1 0 0 01 0 7 83 5 ：i ( 4 ) 存储空间小 e c c 的密钥尺寸和系统参数与r s a 、d s a 相比要小得多，如表1 一l 所示，1 6 0 位 e c c 与1 0 2 4 位r s a 、d s a 具有相同的安全强度，2 1 0 位e c c 贝o 与2 0 4 8 位r s a 、d s a 具有 相同的安全强度。短小的密钥与系统参数意味着它所需占用的存储空间也更小。 ( 5 ) 带宽要求低 对长消息进行加解密时，e c c 、r s a 、d s a 具有相同的带宽要求，但应用于短 消息时e c c 带宽要求则明显小于后两者，这使得椭圆曲线密码体制在无线网络领 域比如a d - h o c 、无线传感器网络中具有广泛的应用前景。 综上所述，椭圆曲线密码体制具有安全性高、运算速度快、占用存储空间小、 带宽要求低、功耗低等特点，尤其适用于智能卡、无线通信、w e b 服务器等设备， 具有广阔的应用前景。 1 3e c c 研究现状及发展方向 椭圆曲线密码体制自1 9 8 5 年被提出以来，一直受到各国研究学者的关注， 投入了大量的时间和精力对它进行研究，使得椭圆曲线密码体制在短短的三十几 年时间里从理论研究阶段发展到了应用开发阶段。目前，椭圆曲线密码体制主要 应用于认证、数字签名、数据加密等领域，加拿大c e r t i c o m 公司是国际上最著 名的e c c 密码技术公司，已授权3 0 0 多家企业使用e c c 密码技术，还联合了h p 、 n e c 等十多家著名的大公司开发了标准s e c 眵1 。美国n e x tc o m p u t e r 公司也开发 出了用于e c c 的集成电路，日本m i t s u s h i t a 、法国t l l o m p s o n 、德国s i e m e n s 、 加拿大w a t e r l o o 大学等也都在积极实现这一体制，这些产品广泛应用于保密通 信、网络安全、电子商务等方面。 目前，针对椭圆曲线密码体制的研究主要包括公钥密码标准的制定、相关算 法运算效率的改进以及椭圆曲线密码系统的应用等方面。其研究成果主要有： ( 1 ) i e e e 组织制定的公钥密码标准p 1 3 6 3 嘲，它对椭圆曲线密码体制中的加 密、签名和密钥交换作了详细规定，按照该标准可定义素数域f q 或二进制域f 2 4 北京邮电大学硕，l ：学位论文 上的椭圆曲线。 ( 2 ) 美国国家标准化组织( a n s i ) 制定的e c d s a 标准x 9 6 2 n 引，给出了e c d s a 算法 的具体细节，该算法是d s a 算法在椭圆曲线上的应用，已成为目前最有效的椭圆 曲线签名算法，e c d s a 还成为了美国联邦信息处理f i p s1 8 6 2 数字签名标准n 妇中 规定的三个使用算法之一。 ( 3 ) i e t f 公布了o a k l e yk e yd e t e r m i n a t i o np r o t o c o l ，实际上是素数域f q 和二进制域f 2 ”上的椭圆曲线上的d i f f i e h e l i m a n 变形。 ( 4 ) i s 0 i e c l 5 9 4 6 公布了基于椭圆曲线离散对数问题的公钥密码体制，包括 签名体制、加密体制和密钥管理体制。 ( 5 ) 中国颁布了无线局域网国家标准g b l 5 6 2 9 1 l ，其中包括全新的w a p i ( w l a na u t h e n t i c a t i o na n dp r i v a c yi n f r a s t r u c t u r e ) 安全机制，有w a i 和w p i 两部分，分别实现对用户身份的鉴别和对传输数据加密，w a i 采用公钥密码体制， 利用证书来对w l a n 系统中的用户和a p i 进行认证。证书里面包含有证书颁发者 ( a s u ) 的公钥和签名以及证书持有者的公钥和签名，这罩的签名采用了基于椭圆 曲线密码体制的算法。 ：。 现阶段，针对椭圆曲线密码技术的研究主要集中于以下几个方向： ( 1 ) 选取随机曲线 虽然现有实现方案基本上都采用了经过权威组织推荐的曲线或其它一些特 殊的曲线，但是要取得最佳安全性最好还是采用随机曲线。对随机选取的曲线， 尽管有s e a 算法能计算所选曲线的阶，但是要找到一条满足需求的曲线仍然开销 过大。如何能够更高效的找到大量满足需求的合适的随机曲线仍需进一步研究。 ( 2 ) 加快点乘的运算速度 在椭圆曲线密码系统中，椭圆曲线上的点乘运算是最耗时间的运算，它的效 率决定着整个椭圆曲线密码系统的性能。对一些特殊曲线或固定基点，现在己经 有了较成熟的算法。但是对一般曲线或对随机点，如何快速地计算k p 仍无一个好 的方法。因此，进一步加快计算点乘的速度，从而提高整个椭圆曲线密码系统的 性能正成为一个热门的研究领域。 ( 3 ) 快速产生椭圆曲线参数 要使用椭圆曲线密码系统，首先要确定系统的各个参数，这是建立椭圆曲线 密码系统最花时问的一个步骤虽然可以以离线的方式产生椭圆曲线参数，并且 一旦产生了一条安全的椭圆曲线后，以后就可一直使用该曲线来建立椭圆曲线密 码系统，但如何快速地以在线的方式产生可用于密码学的安全的椭圆曲线参数是 密码学者一直在谋求解决的问题。 ( 4 ) 实现椭圆曲线密码系统 5 北京i t l f f m _ , 人学硕i ：学位论文 椭圆曲线密码体制的特点使得它特别适合于在计算能力不强的环境下( 如 w a p 、手机、智能卡等) 实现。如何在此类环境中实现椭圆曲线密码系统，特别是 如何充分利用其计算量小，占用存储空间少，安全性高等优势，在不增加成本的 前提下，在资源有限的设备上安全高效的实现椭圆曲线密码系统，同时提高其实 用性，是目前研究者和商家都在积极考虑的问题。 ( 5 ) 开发专用硬件结构 如果像r s a 体制一样，能用硬件实现椭圆曲线密码体制，那么其效率将会提 高，因此如何开发设计有效的专用硬件结构来实现椭圆曲线密码系统也是人们正 在研究的一个热点。 ( 6 ) 设计椭圆曲线密码协议 要推广椭圆曲线密码技术的应用，就必须要有基于椭圆曲线理论的椭圆曲线 密码协议的支持，目前支持椭圆曲线理论的密码协议还比较有限，因此设计新的 基于椭圆曲线理论的密码协议也成为研究者们进一步努力的方向。 综上所述，椭圆曲线密码体制正以其密钥短、安全性高等特点引起业界的广 泛重视。如果椭圆曲线密码系统能够在进一步的研究中，突破安全曲线的快速产 生及应用、算法实现的复杂性等问题的限制，必将能够更多的应用在社会生活的 各个方面，有着良好的发展前景。 1 4 论文结构 第一章阐述了课题的研究背景、目的及意义，介绍了椭圆曲线密码体制的概 念、特点、现状以及发展方向。 第二章介绍了密码学基础知识，对称密码体制和公钥密码体制的组成、工作 原理、特点等。 第三章详细论述了椭圆曲线密码体制相关的基本概念，有限域上的加法和乘 法运算，分析了不同坐标系下的点加和倍点运算，此外，还研究了基于椭圆曲线 密码体制的密钥交换、数据加密、数字签名算法的工作原理，以及针对椭圆曲线 密码系统的常见攻击。 第四章重点研究了椭圆曲线上已有的各种点乘算法，并对n a f w 滑动窗口算法 进行了改进。 第五章设计实现了一个椭圆曲线密码系统。在混合坐标系下实现了改进的 n a f w 滑动窗口算法，提出了一种无需明文嵌入的带认证机制的加密方案，有效的 提高了系统的效率。 第六章概括总结全文，展望了未来的研究方向，提出进一步的工作设想。 6 北京邮电人学硕士学位论文 2 1 密码学历史 第二章密码学基础 密码学( c r y p t o l o g y ) 泛指所有有关研究秘密通信的学问，包括如何达到秘密 通信及破解秘密。密码学作为一门古老而又年轻的科学，它用于保护军事和外交 通信的历史可以追溯到几千年前。在当今的信息时代，大量的敏感信息通过公共 通信设施或计算机网络来进行交换，而这些信息的秘密性和真实性是人们迫切需 要保障的，因此现代密码学对于军事、政治、外交和商业的价值越来越重要。 密码学的发展历史大致可划分为三个阶段： 第一阶段：从古代至u 1 9 4 9 年，这一时期可看作是科学密码学的前夜时期。这 段时期的密码技术可以说是一种艺术而不是一种科学，人们凭借直觉和经验来进 行密码的设计和分析，而不是推理证明。例如最早应用替代的凯撒密码。 第二阶段：从1 9 4 9 年至u 1 9 7 5 年。1 9 4 9 年s h a n n o n 发表的保密系统的信息理 论一文，为对称密码系统建立了理论基础，从此密码学发展成为一门科学。这 一时期使用的加密方法称为传统的加密算法，其安全性依赖于密钥的私密性而不 是算法的私密性，也就是说，使用密文和有关加解密算法的知识去解密一段信息 在实现上不可能。其中最著名的是美国国家标准局正式公布实施的数据加密标准 d e s ( d a t ae n c r y p t i o ns t a n d a r d ) n 引，其算法是对外公开的，而安全性主要是依 赖于对称密钥的安全性。现在该标准仍在使用，但是多用于非机密单位和商业上 的一些要求不高的保密通信。 第三阶段：从1 9 7 6 年至今。1 9 7 6 年，d i f f i e 和h e l l m a n 的密码学的新方向一文 导致了密码学上的一场革命畸1 。他们首次证明了在发送端和接受端实现无密钥传 输的保密信息是可能的，从而开创了公钥密码学的新纪元。 密码学可分为以下两个领域： ( 1 ) 密码编制学( c r y p t o g r a p h ) ：研究如何达到信息的秘密性，鉴别性的科学； ( 2 ) 密码分析学( c r y p t a n a l y s i s ) ：研究如何破解密码系统，或伪造信息使密码 系统误以为真的科学。 密码编制学与密码分析学是两个相互对立的分支，它们彼此目的相反，相互 对立，但在发展中又相互促进o 2 2 密码系统的组成 一个密码系统由以下5 部分组成， 7 北京邮i 乜人学硕j ：学位论文 ( 1 ) 明文空间m ：全体明文集合： ( 2 ) 密文空n c ：全体密文集合； ( 3 ) 密钥空间k ：全体密钥集合，k = k e + k d ，k e 表示加密密钥，k d 表示解密密 钥( 密钥是一组信息编码，它参与密码系统的运算，并对密码系统的运算起特定 的控制作用) ； ( 4 ) 加密算法e ：明文和密文之间的变换规则； ( 5 ) 解密算法d ：密文和明文之间的变换规则。 发 送 方 接 收 方 恶意终端 图2 - 1 密码系统原理图 加密变换：c = e ( m ，k e ) ； 解密变换，m = d ( c ，k d ) = d ( e ( m ，k e ) ，k d ) 。 在发端，通过加密算法e 和加密密钥k e 将明文m 变换成密文c ，c = e ( m ，k e ) ， 接着将密文c 通过公开的信道传输到收端，收端利用解密算法d 和解密密钥k d 将密 文c 还原成明文m ，m = d ( c ，k d ) = d ( e ( m ，k e ) ，k d ) 。若密文c 在公开信道的传输过 程中，有一恶意终端并不知道解密密钥k d ，但欲利用各种方法得知明文p ，或假 冒发送方伪造信息让接收方误以为真，这一过程称为密码分析或密码攻击。密码 系统原理如图2 - 1 所示。 一般而言，密码系统依其应用可对信息提供下列功能： ( 1 ) 秘密性：防止非法的接收者发现明文。 ( 2 ) 鉴别性：确定信息来源的合法性，也即此信息确实是由发送方所传送， 而非别人伪造。 ( 3 ) 完整性：确定信息没有被有意或无意的更改，及被部分取代、加入或删 除等等。 ( 4 ) 不可否认性：发送方在事后不可否认其传送过的信息。 2 3 对称密码体制 对称密码体制，其加密密钥和解密密钥相同，系统的安全性主要取决于密钥 保管、传输过程中的安全性。其典型代表是美国的数据加密标准d e s ( d a t a 8 北京邮电大学硕+ l ：学位论文 e n c r y p t i o ns t a n d a r d ) 以及d e s 的变体三重d e s ；a e s ( a d v a n c e de n c r y p t i o n s t a n d a r d ) 。 2 3 1 对称加密的原理 由于对数据加密和解密所使用的密钥都是相同的，发端和收端采用相同的加 密算法并交换共享的专用密钥，因此对称密码系统的安全性完全依赖于所持有的 密钥的安全性。密钥的保管和传送的安全性面临着严峻的挑战，在使用对称加密 的系统中必须加强对密钥的管理。 若以m 表示所有的明文信息，c 表示密文信息，k 是所有的密钥。则对称密码 体制是由这样一组函数对构成的： e k m - c d k ：c m ，k k 在这里，对于所有的m e m ，k k ，都有d k ( e k ( m ) ) = m 。使用对称密码系统时， 发端a 和收端b 需要事先商定某一密钥k k ，他们可以通过直接会晤或者可以信赖 的信使来互相得到对方的密钥。之后，若a 想发送一组明文给b ，他传送密文信息 c e k ( m ) 。到了b 端，b 通过解密函数d k 复原信息。其原理如图2 2 所示。 2 3 2 对称加密的特点 对称加密体制具有加解密高效快速、密钥简短等特点，但它的密钥必须保证 通过安全可靠的途径传递，这就使得密钥管理成为影响系统安全的关键性因素。 对称加密体制的最大问题是密钥的分发和管理非常复杂、代价高昂。比如对于具 有n 个用户的网络，需要n ( n - i ) 2 个密钥，在用户群不是很大的情况下，对称加 密系统是有效的。但是对于大型网络，当用户群很大，分布很广时，密钥的分配 和保存就成了大问题。另外，由于通信双方必须统一密钥才能发送保密的信息， 那么如果发信者与收信人是素不相识的，就无法向对方发送秘密信息了。 现有的对称加密算法有：d e s 及其各种变形算法、i d e a 算法、s a f e r 系列算法、 r c 系列算法等等。 图2 - 2 对称密码系统原理图 9 北京邮f 乜人学硕 2 学- 位论文 2 4 公钥( 非对称) 密码体制 1 9 7 6 年，斯坦福大学的w h i t f i e l dd i f f i e 和m a r t i nh e l l m a n 在美国国家 计算机会议上首先公布了一种崭新的密码体制公钥密码体制。几个月后，他 们在i e e e 上发表了具有开创性的论文密码学的新方向，提出适用于网络上 保密通信的公钥密码思想，该论文的发表掀起了公钥密码研究的序幕。公钥密码 体制中，采用两个密钥将加密和解密功能分开：一个是公开的，作为加密密钥， 简称公钥；一个为用户专用，作为解密密钥，简称私钥，通信双方无需事先交换 密钥就可进行保密通信。它实质是基于单向门限函数的思想，用公开密钥加密的 信息只能用相应的私有密钥解密，反之亦然，而且不能从其中一个密钥推导出另 一个密钥。因此就可以把公开密钥公开发布，而用户只需保存私有密钥。若以公 钥作为加密密钥，以用户私钥作为解密密钥，则可实现多个用户加密的信息只能 由一个用户解读；反之，以用户私钥作为加密密钥而以公钥作为解密密钥，则可 实现一个用户加密的信息由多个用户解读。前者可用于数据加密，后者可用于数 字签名。 在通过网络传输信息时，公钥密码算法体现出了对称密码算法不可替代的优 越性。例如对于参加电子交易的商户来说，希望通过公开网络与成千上万的客户 进行交易。若使用对称密码，则每个客户都需要由商户直接分配一个密码，并且 密码的传输必须通过一个单独的安全通道。相反，在公钥密码算法中，同一个商 户只需自己产生一对密钥，并且将公钥对外公开。客户利用商户的公钥加密信息， 就可以保证将信息安全地传送给商户。 由于公钥密码体制不需要联机密钥服务器，密钥分配协议简单，极大的简化 了密钥管理，支持彼此互不相识的两个实体之间的安全通信。其主要缺点是算法 复杂，加密数据的速度和效率比对称密码体制低。 目前既具有一定安全性又能比较容易实现的体制，按照所基于的数学难题可 分为如下三类： ( i ) 基于大数分解问题的公钥密码体制。其中包括著名的r s a 密码体制和 r a b i n 密码体制。 ( 2 ) 基于有限域上离散对数问题的公钥密码体制。主要包括e i g a m a l 类n 鄙加密 体制和签名方案，d i f f i e h e l l m a n 密钥交换方案，d s a 签名方案和d s s 签名方案n 2 3 熊 1 亍0 ( 3 ) 基于椭圆曲线离散对数问题的公钥密码体制。其中主要包括椭圆曲线公 钥密码系统，有数据加密，数字签名和