（计算数学专业论文）椭圆曲线密码体制研究及其在数据保密中的应用.pdf

摘要 椭圆曲线密码体制研究及其 在数据保密中的应用 作者简介：郑志静，女，生于1 9 8 1 年1 2 月，于2 0 0 4 年9 月师从于成都理 工大学王新庄教授，于2 0 0 7 年6 月获硕士学位。 摘要 随着互联网的广泛应用，各种信息资料在网上传输越来越频繁，资料 在传输过程中的安全性问题同益突出。信息安全技术备受关注，其中密码 理论的研究与应用是信息安全技术的核心领域。 椭圆曲线密码体制是一种公钥密码体制，相对于以往基于有限域上离 散对数问题或大整数分解问题的传统公钥算法，椭圆曲线密码算法具有安 全性高、速度快、密钥短、实现时所需占用资源少的特点。椭圆曲线加密 系统与其他公钥加密系统相比有许多优点，受到国内外安全专家的极大关 注。 本文首先讨论此课题的研究现状与意义；密码学概述；对相关数学理 论进行分析研究；其次，讨论椭圆曲线基本运算和椭圆曲线密码体制，并 实现在一条给定的曲线上进行加解密工作的程序；最后以成都理工大学对 外横向合作项目资料共享信息管理系统为背景，设计并实现基于椭圆曲线 密码体制的混合加密方案，与传统的混合加密方案来比较，更安全、快速。 本项研究主要成果如下： 1 ) 对椭圆曲线密码体制进行分析研究。 2 ) 根据项目对文件加密程度的不同要求，得到不同的混合加解密方案，在 保证效率和安全性达到要求的前提下，完成加解密工作。 关键词：椭圆曲线；椭圆曲线密码体制；数据加密；混合加密 成都理r 大学硕十学位论文 r e s e a r c ha n da p p l i c a t i o no f e l l i p t i cc u r v e c r y p t o s y s t e m si nd a t ae n c r y p t i o n a b s t r a c t a l o n gw i mt h ei n f o r m a t i o nm a n a g e m e n ts y s t e m , m a t e r i a lt r a n s m i s s i o ni n v o l v e s i nm o r ea n dm o r es e c u r e q u e s t i o n t h ei n f o r m a t i o ns e c u r i t yt e c h n o l o g yi sp a i d a t t e n t i o n t h er e s e a r c ha n da p p l i c a t i o no fp a s s w o r dt h e o r yi st h ec o r ed o m a i ni nt h e i 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 e l l i p t i cc u r v ec r y p t o s y s t e m 。si so n ek i n do fp u b l i ck e yc r y p t o s y s t e m s ，w h i c hi s c a r r y i n gt h es e c u r i t yh i g h i ta l s oh a sh i g hs e c u r i t y , s p e e d ，a n ds h o r tk e y , a n dt a k e st h e r e s o u r c e sf e wc h a r a c t e r i s t i c sc o m p a r e dw i t ht h et r a d i t i o n a la l g o r i t h m s e c u r i t y e x p e r t si na n do u to fc o u n t r yh a v ea l r e a d yp a i da t t e n t i o nt ot h ee l l i p t i cc b r v e e r y p t o s y s t e m s t h ea r t i c l ef i r s td i s c u s s e st h er e s e a r c hp r e s e n ts i t u a t i o n t l l es i g n i f i c a n c eo ft h i s t o p i ca n dt h ec r y p t o l o g yo u t l i n e ，c o n d u c t st h er e s e a r c ht ot h ec o r r e l a t i o nm a t h e m a t i c s t h e o r y , i ta l s od i s c u s s e st h ee l l i p t i cc u r v ef u n d a m e n t a lo p e r a t i o na n dt h ee l l i p t i cc u r v e c r y p t o s y s t e m s ，a n dh a sr e a l i z e de n e r y p t i o n d e c i p h e ri nt h ea s s i g n e dc u r v e b a s e do n t h ec h e n g d uu n i v e r s i t yo ft e c h n o l o g y c o o p e r a t i o np r o j e c t - - - m a t e r i a ls h a r i n g i n f o r m a t i o nm a n a g e m e n ts y s t e m , p m d u c e dam i xe n c i p h e r m e n ts c h e m e ，s a f e ra n d f a s t e rc o m p a r e dw i t ht h et r a d i t i o n a lm i xe n c i p h e r m e n ts c h e m e t h i sa r t i c l eo b t a i n ss e v e r a lr e s u l t s ： 1 ) r e s e a r c ha n da n a l y s i st h ee l l i p t i cc u r v ec r y p t o s y s t e m s 2 ) a c c o r d i n gt od i f f e r e n tr e q u e s t sf r o mt h ep r o j e e t , t h i sp a p e ro b t a i n e ds e v e r a l d i f f e r e n ts c h e m eo f m i xe n c r y p t i o n d e c i p h e r ，i ta l s oh a sf i n i s h e dt h ew o r ko f e n c r y p t i o n d e c i p h e rb yt h ep r e c o n d i t i o nw h i c hs e c l l r e st h ee f f i c i e n c ya n d s e c u r i t y k e y w o r d s ：e l l i p t i cc u r v e s ；e l l i p t i cc u r v ec r y p t o s y s t e m s ；d a t ae n c r y p t i o n ；m i x e n e r y p t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得盛壑堡王太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 2 川年。月2 f 日 学位论文版权使用授权书 本学位论文作者完全了解盛壑堡王太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盛壑堡王太堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文储躲智怎，前 2 加7 年 s 月一2 1 日 第1 章引言 1 1 课题背景 第1 章引言 管理信息系统( m a n a g e m e n ti n f o r m a t i o ns y s t e m s 简称m 1 s ) 的应用能够使一 个组织在激烈的竞争中保持优势并不断发展，在迅速变化的环境中灵敏地做出有 效的反应。但计算机网络、数据通讯及存储系统中存在着许多潜在的不安全因素， 密码技术是保护信息机密性、完整性、不可抵赖性和身份验证的有效手段。 本选题以成都理工大学对外横向合作项目山东省胜利油田地质科学研 究院资料共享信息管理系统为背景。研究院经过多年积累了大量有价值的资料， 但在资料的管理和利用上，却比较欠缺，既没有形成有效的管理，也没有得到充 分利用。在新的项目工程实现过程中，需要花大量的时间重复同样类似的整理工 作。如何充分利用资料，共享资源，将共享资源转化为资本，为研究院高效合理 地利用现有资源，规划建立一个共享平台成为研究院要解决的问题。 在资料共享时，研究院要求对共享的资料进行加密，资料仅在部门内部进行 免费共享，对于外界来说，超过一定密级的文件不予共享。这就要求文件在上传 前有相应的保护措施，使得不同密级的文件得到不同程度的安全保护。 在对文件进行安全保护时，用密码技术来完成是比较理想的。椭圆曲线密码 体制与量子加密、混沌加密是当今密码学中的三大研究热点，其中，椭圆曲线在 公钥密码学领域中以其有安全性能高、计算量小、密钥长度短、处理速度快、存 储空间占用小和带宽要求低等特点而有着广泛的应用前景。本文将以椭圆曲线密 码体制研究为重点，对其基本理论和实现应用进行分析研究。 1 2 课题研究意义 1 9 8 5 年，n e a l k o b l i t z 和腿埘r 分别独立提出将椭圆曲线应用于公开密钥 密码体制，使得椭圆曲线，这个被数学家研究了一百多年的数学问题，在密码学 领域发挥了重要的作用。椭圆曲线密码体制( e l l i p t i cc u r v ec r y p t o g r a t p h y ，简称 政) 用群的形式来构造密码算法，具有完全相似的特性，但它们并没有减少密 码分析的工作量。由于e c c 的提出只有二十多年，在各方面都还没做到尽善尽 l 成都理i ：人学硕+ 学位论文 美，有进一步研究的需要，在信息管理系统中也很少使用。本文所做的工作是基 于对e c c 的研究，并将其应用于实际问题中。 e c c 是目前已知的公钥体制中，对每一比特提供加密强度最高的一种体制， 它具有安全性高、密钥量小、灵活性好的特点，受到了国际上的广泛关注；深入 研究基于椭圆曲线离散对数问题的公钥密码具有很大的现实意义。一方面它在因 数分解上有很突出的表现，对r 鲥密码体制提出了挑战；另一方面在椭圆曲线 上建立的公钥密码系统计算效率很高。 在传统的信息管理系统开发过程中，根据流程完成需求者在需求分析中提到 的要求，而对于在网络上传输的数据本身，很少有进行保护的，这就对数据的安 全性造成了很大的隐患。本文采用混合加密密码体制，用对称加密算法加密数据 文件本身，用非对称加密算法对会话密钥进行加密，以实现加解密操作，使得 在信息管理系统的文件传输过程中对文件本身提供安全保护。 1 3 椭圆曲线国内外研究概况 椭圆曲线密码，即基于椭圆曲线离散对数问题的各种公钥密码体制，在1 9 8 5 年被提出，它是利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体制 中的有限循环群所得到的一类密码体制。椭圆曲线密码有着许多独特的性质，使 得人们从一开始就对它进行单独的研究，本文也正是因为这一点，对其进行研究 实现，在实际应用中体现其价值。 加拿大的c e r t i c o m 公司对椭圆曲线密码体制的安全性和r s a 算法的安全性 进行了详细的比较，此表由美国国家标准与技术研究所( m 龃) 提供，具体的数 据如表1 1 ： 表1 - 1 冠鲥和e c c 在同一安全性下所需的密钥比特比较表 e c c 密码& 度( b i t s )r s a 密码长度( b i t s )密码艮度比 1 6 31 0 2 41 ：6 2 5 63 0 7 2l ：1 2 3 8 47 6 8 0l ：2 0 5 1 21 5 3 6 0l ：3 0 与其他系统相比，e c c 所需的设备在存储空间上要求少、功耗小、内存和 带宽消耗少。这可以在诸如无线设备、手持计算机、智能卡和瘦客户端等限定的 第1 章引言 平台中实施加密技术。因此，在效率极为重要的情况下e c c 还能提供强大的竞 争优势。目前应用得较为成熟的e g c 产品有基于大素域的c c 系统和基于二进 制域的e c c 系统。由于二进制域本身的运算特点，它更适合于硬件s m a r t 卡。 目前n i s t ，a n s i 和i e e e 都已对e c c 进行了标准化，美国国家标准与技术 研究所发布了要求美国联邦政府机关使用的加密算法标准，如：美国联邦信息处 理标准( f i p s ) 1 8 6 2 数字签名标准( o s s ) ，此标准用于对椭圆曲线数字签名算 法( e c d s a ) 进行标准化，并推荐了1 5 组椭圆曲线域参数。美国国家标准协会 ( a n s i ) 委员会x 9 为美国金融服务行业编制x 9 6 2 ( 椭圆曲线数字签名算法) ， 该标准针对歇m 翱做出了相应的标准化规定；美国国家标准x 9 6 3 ：使用椭圆 曲线加密技术的密钥协商和密钥传输，该标准针对e c d h 和e c m q v 密钥协 商以及e c i e s 密钥传输做出了相应的标准化规定。电子和电器工程师协会 ( 饱砸) 开发的i e e e1 3 6 3 2 0 0 0 公钥加密算法的标准规范，该标准针对e c d s a 、 e c d h 和e c m q v 做出了相应的标准化规定。 1 4 本文主要工作 本文首先研究椭圆曲线密码体制的数学基础及基本算法，在算法优化上进行 改进，既提高速度，又未失其原有的安全性。选择一条m s r 给出的安全椭圆曲 线，实现了加解密字符串和文件、数字签名等操作。 其次从信息资源本身的安全性考虑，采用混合形式的加密算法对数据文件进 行加解密，以达到既安全又容易实现的加密方案，使得数据文件在被加解密时 能保证安全又不失效率。在实际应用中，采用n 1 s t 所提供的椭圆曲线参数。 在本文中重点研究椭圆曲线密码算法及对数据资料所进行的加解密工作。 最后，用n e t 实现整个方案。 成都理i ：人学硕十学位论文 第2 章密码学概述 2 1 信息安全与密码学 信息安全只能是相对而言的，它是动态发展的。任何人都不能宣称自己终极 了对信息安全的认识。 广义地讲，安全是指防止其他人利用、借助你的计算机或外围设备，做你不 希望他们做的任何事情，让你能够完成既定任务而不受任何干扰，真正安全的目 的是保护存储在计算机中的数据。 随着计算技术与通信技术的飞速发展，人们对信息的需求与日俱增，人类社 会正在步入信息化时代。与此同时，各种非法获取有效信息的事件不断发生，使 得信息的保护越来越受到人们的关注。信息保护涉及许多方面的因素，这些因素 可以归纳为三个主要方面：人为因素、物理因素和信息的安全处理方式。为了防 止这些因素造成信息的丢失和泄密，人们采取了许多安全策略，如加密、软硬件 控制、各种物理控制，严格的管理制度等。但是，在信息安全与数据保护方面， 即在对信息的安全处理模式方面，密码学提供了保护信息的重要方法与手段。 目前针对i n t e r n e t 系统安全实施的防卫措施主要有防火墙、入侵监测、数据 加密、安全协议、内容检测( 防病毒木马) 等安全手段。一般说来，安全涉及技术 安全、管理安全、法律政策。密码技术安全能确保最基本的安全。 人们对信息安全的各种需求不断促进密码学的发展。为了获得具有高安全强 度且实现简易的信息安全系统，许多学科的学者和科学家试图从不同的学科和角 度研究信息安全的机制和实现手段，由此出现了从数学理论出发的基于数学的密 码体制、从物理学角度出发的基于物理学的密码体制、利用生物特性设计的生物 密码体制等。由于基于数学的密码体制在信息保护中的悠久历史和重要性，人们 习惯于将目前所提出的密码系统划分为两个大类：数学密码和非数学密码。不管 怎么划分，所有密码体制都具有共同的特征和目标，主要区别在于这些密码体制 实现的手段和密码系统的设计原理。 4 第2 章密码学概述 2 2密码技术简述 作为一门科学，早在几千年前就有了密码学的雏形并在实践中得到应用和发 展。但是，直到2 0 世纪4 0 年代密码学才具有系统的科学体系结构。因此，密码 学是一门古老而年轻的科学。密码学经历了从神秘到明朗，从纯军事应用到商用， 从艺术形式到科学研究的进程。从学科发展历程来看，目前，密码学正得到广泛 应用和普及，成为国家安全、经济活动和人们生活中的重要组成部分。从学科发 展来看，经过多个不同学科的交叉与融合，以及成果的不断积累，密码学的内容 得到不断的丰富和完善，成为一门典型的跨多个学科的交叉学科。 密码学是研究将可理解的符号变换为不可理解的符号及其逆变换的方法、手 段、理论，并分析这种变换可能存在的破译方式和获取有效信息可能性的一门科 学。因此，密码学的本质就是“变换”以及对这种“变换”的分析。当然，密码 学中的“变换”不是任意的，必须保证合法用户容易实现，而非法用户从经过变 换后的符号序列中恢复出原来的有用信息是不可能或者非常困难，以至于进行破 译得不偿失。实现这个目标可以采用不同的机理来实现所需的变换，如数学方法、 物理方法、化学方法、生物方法、电子方法、光学方法等，这也j 下是密码学可以 跨多个学科的根本原因。在同一种方法中，还可以采用不同的方式来实现所需的 变换。如在本文中以椭圆曲线密码体制为基础，混合a e s ，r s a 等不同算法对数 据传输进行合理保护。下面简要介绍一下本文要用到的密码算法。椭圆曲线密码 体制为本文的研究重点，在后续章节中重点分析研究。 2 2 1 对称加密算法 对称算法，又称传统密码算法。在大多数的对称算法中，加密密钥和解密密 钥相同，所以也称这种加密算法为秘密密钥算法或单密钥算法。算法要求发送方 和接收方在安全通信之前，商定一个会话密钥。对称算法的安全性依赖于密钥， 泄漏密钥就意味着任何人都可以对他们发送或接收的文件解密，所以密钥的保密 性至关重要。 对称加密算法的优点为运算速度快，缺点为密钥量大且分发困难。 常用的对称加密算法有d e s ，a e s 等。 1 ) 删 5 成都理l ：人学硕十学位论文 d e s ( d a t a e n c r y p t i o n s t a n d a r d ) 算法的基本设计思想是通过多次迭代， 将简单的基本运算( 例如左移、右移、模2 加等) 和变换( 选择函数、置 换函数) 构造成数据流的非线性变换。d e s 算法加密时把明文以6 4 b i t 为单 位分成块，采用美国国家安全局精心设计的8 个s 盒( s ：s u b s t i t u t i o m 和p 置换 ( 尸：p e r m u t a t i o n ) ，经过1 6 轮迭代，最终产生6 4 b i t 密文，每轮迭代使用的4 8b i t 子密钥由原始的5 6 比特产生。d e s 的加解密密钥和流程完全相同，区别仅是 加密与解密使用的子密钥序列的施加顺序j 下好相反。 2 ) a e s a e s ( a d v a n c e d e n c r y p t i o ns t a n d a r d ) 算法，也称为r i j n d a e l 算法，是一种灵 活的算法，信息块长度可变( 1 2 8 、1 9 2 或2 5 6 位) ，密钥长度可变( 1 2 8 、1 9 2 或2 5 6 位) ，迭代次数也可变( 1 0 、1 2 或1 4 ) ，且信息块长度与密钥长度可以决 定迭代次数。正因为这种灵活性，r i j n d a e l 有三个版本：a e s - 1 2 8 、a e s - 1 9 2 和 a e s 2 5 6 。 以上两种算法在相关论文中有详细的研究和描述，故在本文中不再赘述。 22 2 非对称加密算法 非对称加密算法中加密密钥和解密密钥不同，且加密密钥可以和算法一起公 开，正是这一特点，非对称加密算法也叫公钥加密算法。从算法本身来看，其核 心算法是运用一种特殊的数学函数单向陷门函数，即从一个方向求值是容易 的，而其逆向计算却很困难，以至于在实际上是不可行的。这类算法在1 9 7 6 年 由d 劣e 和h e l l m a n 最先提出，而r i v e s t 、s h a m i r e 和a d l e m a n 提出了第一个比较 完善的公钥密钥体制，即r s a 算法。后来陆续出现了e i g a m a l 公钥密码体制、 m c e i e c e 公钥密码算法和椭圆曲线公钥密码体制等。 r s a 算法是r i v e s t 、s h a m i r e 和a d l e m a n 于1 9 7 8 年在美国麻省理工学院研制 出来的，其安全性建立在“大数分解和素性检测”这一著名数论难题基础上，即： 将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计 算量是相当大的，以至于在实际计算中不能实现。虽然这一算法在当时可以算得 上安全，但随着计算技术的发展，r s a 要不断增加密钥长度以达到安全性。 6 第3 章椭圆曲线数学基础及算法 第3 章椭圆曲线数学基础及算法 本章给出椭圆曲线基本的数学理论。非对称加密算法以丰富的数学知识作 为基础。有限域上的椭圆曲线加密算法涉及数论、群论、有限域理论及椭 圆曲线等数学知识。本章首先介绍有限域的基本理论，其次介绍椭圆曲线的定 义及算术法则。 3 1有限域 域是对常见的数系( 如有理数域q ，实数域r 和复数域c ) 及其基本特性的 抽象。域由一个集合f 及两种运算共同组成。这两种运算分别为加法( 用+ 表示) 和乘法( 用表示) ，且满足下列算术特性： ( 1 ) ( f ，+ ) 对于加法运算构成加法交换群，单位元用0 表示； ( 2 ) ( ，、 o ) ) 对于乘法运算构成乘法交换群，单位元用1 表示； ( 3 ) 分配律成立：对于所有的a ，b ，c f ，都有+ 6 ) c = a c + b c 。 若集合f 是有限集合，则称此域为有限域。 有限域算术运算的有效实现是有效实现椭圆曲线密码的重要先决条件，因为 椭圆曲线运算是基于有限域算术运算的。椭圆曲线密码体制的有效实现主要用到 两大特征的有限域，它们分别是素域和二进制域。 3 1 1 素数域 素数域e 由整数集合 o ，1 ，2 ，p - 1 组成，每个这样的整数可以用一个长度 粼j t = f l o g ：q l ( 其中苫 表示不小于z 的最小整数) 的二进制表示，该表示由 整数的二进制表示及其左边添加适当个数的0 组成。e 中元素具有以下算术运 算： 加法：如果口，b ，则a + b = ，其中，是被q 除所得的剩余，0 ，p 一1 。 乘法：如果a ，b c ，则皿= j ，其中s 是被q 除所得的剩余，0 j s p - 1 。 求逆：如果口是e 中的非零元素，a 模q 的逆元，记为口一，是唯一的整数 c e ，c 满足出= 1 。 成都理l ：人学硕士学位论文 令表示中所有非零元素，可证明在中至少存在一个元素g ，使得 中任意非零元素可以表示成g 的方幂，如公式3 - 1 所示，这样的元素g 称为c 的 生成元( 或本原元) 。 巧= g ：0 i p 一2 ) ( 3 1 ) 口2 9 t e 巧的乘法逆是三a 。g 5 9 1 ”础”，可见在上进行一次求逆运算 要进行p 一1 一i 次域乘法，显然p 一1 一i 的二进制长度为f l o g ：( p 一1 一们，由数论 知识，可对模幂运算优化，使运算操作次数为口( 1 0 9 ：( p 一1 一0 1 ) 。即求逆在最坏 情况下相当于口( r l o g ：( p 一1 ) ) 次域乘法。 3 1 2 = 进制域 特征为2 的有限域只，称为二进制域，可以看作域e ( 有两个元素0 、1 ) 上的脚维空间。即存在互。上的肌个元素，嘶，一使得每个口，可以被 唯一的表示成式3 - 2 ： 口= 嘞铴+ 口l q + + a - 1 a 一l ，q 0 ，l ( 3 2 ) 对于一组 ，o r i ，一，) 称其为0 的基。为于基，域元素口可以表示为比特 串( 喁口。一1 ) 。 3 ，2 椭圆曲线 椭圆曲线的研究来源于椭圆积分与彘，其中e ( x ) 是x 的三次或四次多项 式。这样的积分不能用初等函数来表达，为此引进了椭圆函数。这也是本文的研 究基础，下面给出这部分的基础理论。 3 2 1射影平面和无穷远点 通常情况下两条平行直线永不相交，但可以假设两条平行直线相交于一个无 穷远点，从而可以在原来平面坐标系的基础上建立射影坐标系。 对于普通平面直角坐标系上的点坐标( x ，y ) 做如下变换： 第3 章椭圆曲线数学基础及算法 令x = i x ，y = j y ，z 0 ，则爿点可以表示为( x ，y ，z ) 。这样就将二维的 坐标变成了三维的坐标，同时，对于平面上的点建立了一个新的坐标体系。同时 得到直线的方程a x + 6 y + 以= 0 ( 普通平面直角坐标系下直线一般方程是 耐+ 砂+ c = 0 ) 。无穷远点是两条平行直线的交点，将两条直线对应的方程联立 求解： a x + b y + q z ，= o ( c 1 c 2 ) ( 3 - 3 ) i a x + b y + c z = 0 1 解得c l z = 岛z = 一( a x + b y ) ，q c 2 z = oa x + b y = 0 。即无穷远 点可以用( x ，y ，0 ) 表示。注意，平常点z 0 ，无穷远点z = 0 ，因此无穷远直 线对应的方程是z = 0 。 下面列出无穷远点的几个性质，以统一平行与相交： 1 ) 直线上上的无穷远点只能有一个。 2 ) 平面上一组相互平行的直线有公共的无穷远点。 3 ) 平面上任何相交的两直线厶，厶有不同的无穷远点。 4 ) 平面上全体无穷远点构成一条无穷远直线。 5 ) 平面上全体无穷远点与全体平常点构成射影平面。 3 ，2 2w e i e r s t r a s s 方程和椭圆曲线定义 在代数几何中，亏格为1 的代数曲线称为椭圆曲线，但这样定义椭圆曲线会 使本文脱离所要讨论的主题。由r i e m m a n - r o c h 定理知道，任意一条椭圆曲线总 可以用一个三次方程来表示，这个三次方程一般称为w e i e r s t r a s s 方程。 定义3 3 ：设k 是一个域。域k 上的w e i e r s t r a s s 方程是 ) ，2 + q x y + a 3 y = x 3 + 口2 x 2 + n 4 x + a 6 ( 3 - 4 ) 其中a l ，a 2 ，a 3 ，a 4 ，a 6 k 。 当域足的特征不为2 时，上述方程可变形为 ( j ，+ 三口，工+ j 12 = x 3 + ( 1 口? + 口：) x 2 + ( 1 a 。a 3 + a 4 ) x + i i 口，2 + 口。 或 9 成都理l ：人学硕十学何论文 f b 2 = a ? + 4 a 2 b 4 = 口l a j + 2 a 4 ( 3 5 ) 【b 6 = a ；+ 4 a 6 ( 2 y + a l x + a 3 ) 2 = 4 ( 肿1 1 2 b ：) 3 + ( 6 2 2 + 2 b 4 ) ( 斛1 1 2 b ：) + 丽1 酲一：”+ 6 6 ) 1 0 8 2 ( 2 y + a ，x + a 3 ) 2 = 3 6 3 ( x + l b 2 ) 3 2 7 印3 6 ( x + 丧6 2 ) - 5 4 吒 ( 3 6 ) c 42 彬2 - 2 4 b 4 ( 3 7 ) 【c 6 = 一b ；+ 3 6 b 2 b 4 2 1 6 b 6 j x = 3 6 ( x + 击” ( 3 8 ) iy = 1 0 8 ( 2 y + a l x + a 3 ) i x ：上x 一三6 或 i y ：善y 二2 。去r 一去也，一圭d ， 1 0 ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) ( 3 - 1 2 ) ( 3 1 3 ) 第3 章椭圆曲线数学基础及算法 其中a l ，a 2 ，a ，a 4 ，a 6 k ， 若对于所有椭圆曲线e 上的点p 使得方程： f ( x ，y ，z ) = y 2 z + a l x y z + a 3 y x 3 一a 2 x 2 z a 4 x z 2 一口6 2 3 = 0 ( 3 - 1 4 ) 中至少有一个偏导数( 篆或嚣或誓之一) 在p 点为非零，则称耽抬r s t r a s s ，：5 程是平滑的或非奇异的。若存在一点p 使得以上三个偏导数都不存在，则称该点 p 是奇异点，相应地称该w e i e r s t r a s s 方程是奇异的。当且仅当判别式a 0 ，椭 圆曲线是非奇异的。 定义3 4 ：当a 0 ，域k 上的点集 e ；= ( x ，y ) ly 2 + a t x y + a 3 y = x 3 + 口2 x 2 + 口4 x + 口6 ) u o ( 3 - 1 5 ) 其中a i ，a 2 ，a 3 ，a 4 ，a 6 k ，0 为无穷远点，其齐次坐标点为( o ，1 ，o ) ，这也 是椭圆曲线上唯一一个z 坐标为0 的点。点集e 叫做域k 上的椭圆曲线。 在对域k 上椭圆曲线e 的研究中，通常取如下形式的w e i e r s t r a s s 方程： 1 ) 当域k 的特征不为2 ，3 时，w e i e r s t r a s s 方程为 v 2 = x 3 + a 4 x + a 6 , = 一1 6 ( 4 口。3 + 2 7 口；) ，j = 1 7 2 8 i ：i ；无虿 2 ) 当域k 的特征为2 ，i j j ( e ) 0 时，w e i e r s t r a s s 方程为 y 2 + x y = x 3 + 口2 x 2 + a 6 ，a = a 6 ，j = l a 6 3 ) 当域k 的特征为2 ，i jj ( e ) = 0 时，w e i e r s t r a s s 方程为 j ，2 + a 3 y = x 3 + 口4 x + a 6 ，a = 码4 ，j = o 4 ) 当域k 的特征为3 ，i jj ( e ) 0 时，w e i e r s t r a s s 方程为 y 2 = x 3 + 口2 x 2 + 口6 ，a = 一口2 3 4 6 ，j = 一a ；a 6 5 ) 当域的特征为3 ，且，( e ) = 0 时，w e i e r s t r a s s 方程为 y 2 = x 3 + 口4 x + 吼，= 一4 ；，j = o 3 2 3 椭圆曲线的算术法则 设e 是由w e i e r s t r a s s 方程定义的域k 上的椭圆曲线，定义e 上的运算法则， l l 成都理f ：人学硕十学位论文 记为o 。 算术法则设p ，q 是e 上的两个点，三：是 x q t p 和q 的直线( 过，点的切线， 如果p = q ) ，r 是三与曲线e 相交的第三点。设工是过r 和o 的直线，则尸o q 就是三与e 相交的第三点。 定理3 - 2e 上的算术法则0 具有如下性质： 1 ) 如果直线三交e 于点尸，q ，r ( 三点不必不同) ，则 ( 尸0 q ) 0 r = 0 2 ) 对任意p e e ，p 0 0 = p 。 3 ) 对任意p ：o e ，p 0 9 = q o p 。 4 ) 设p e ，存在一个点，记作一p ，使得 ，o ( 一p ) = 0 5 ) 对任意尸，r ，q e ，有 ( p o q ) o r = p 0 ( q e r ) 由以上性质可以得知，e 对于算术规则。构成一个交换群。 更进一步可以得知，如果e 定义在k 上，则 e ( k ) ：= ( x ，y ) k x k iy 2 + 口l x y + a 3 y = x 3 + a 2 x 2 + 口4 x + a 6 u d ( 3 1 6 ) 是e 的子群。 对于定理3 2 给出群运算的精确公式： 定理3 - 3 设椭圆曲线e 的一般w e i e r s t r a s s 方程为： e ：= ( 工，y ) 1y 2 + a l x y + a 3 y = x 3 + a 2 x 2 + 口4 x + a 6 ) u d ) ( 3 1 7 ) 设只= ( 毛，y 。) ，只= ( 算：，y ：) 是曲线上e 上的两个点则 一只= ( x t , - y l - a i x l a 3 ) ( 3 1 8 ) 取 兄：丝二苎 x 2 一五 a ：! i ! 丝苎鱼二鱼苎 2 y l + a l x i + a 3 1 2 若而 ( 3 1 9 ) 觏= x 2 第3 章椭圆曲线数学基础及算法 如果b = ( 屯，乃) = 只+ 最o ，贝z j x 3 ，y 3 可以由公式给出 x 3 = 2 + a ；, - a 2 一墨- - x 2 ( 3 - 2 0 ) 【y 3 = 2 ( x i x 3 ) 一a t x 3 一y l a 3 在实数域r 上椭圆曲线及其运算法则有着特殊的几何意义。 因为实数域r 的特征不为2 ，3 ，所以实数域月上椭圆曲线e 的w e i e r s t r a s s 方 程可设为e ：y 2 = 矿+ 口4 x + 吼，其判别式= - 1 6 ( 4 a ：+ 2 7 4 ：) 0 ，则e 在r 上 的运算规则为： 设只= ( 一，y ) ，b = ( x ：，y ：) 是曲线上e 上的两个点，d 为无穷远点，则 1 ) 0 + 只= 只+ 0 ； 2 ) 一异= ( ，- y 1 ) ； 3 ) 如果与= ( 而，乃) = 只+ 最0 ，贝t j x 3 ，y 3 可以由公式给出 j 而2 刀一而一工2( 3 2 1 ) 【y 3 = a ( 一善3 ) 一y l 其中 a ：丝二苎 恐一而 旯：堑鱼 2 y l 运算法则的几何意义是： 设鼻= ( _ ，y 。) ，最= ( x ：，y 2 ) 是曲线上e 上的两个点，0 为无穷远点。则一日 为过点e 和点0 的直线上与曲线的交点，即一只是点只关于x 轴的对称点。 而点e 与点昱的和置+ b = 只= ( x 3 ，y ，) 是过点只与点最的直线上与曲线e 的交点r 关于z 轴的对称点只= 一r 。 特别地，在密码学中，用到基于素域( q 3 且为素数) 和域。( n 1 ) 上的椭圆曲线b 给出具体的运算公式。 3 2 3 1 素域f q ( g 3 且为素数) 上椭圆曲线e 因为素域的特征不为2 ，3 ，所以素域上椭圆曲线e w e i e r s t r a s s 方程 可设为： 22孓 屯 砭 = 渤 觏 成都理i ：人学硕十学位论文 e ：y 2 = x 3 + 口4 x + 口6 其判别式= - 1 6 ( 4 a ：+ 2 7 口：) 0 ，则e 在e 上的运算规则为： 其中 ( 3 2 3 ) 设置= ( 一，y 。) ，b = ( 秘，y 2 ) 是曲线上e 上的两个点，o 为无穷远点，则 i ) d + 只= 鼻+ o ； 2 ) 一只= ( x i , - y 1 ) ； 3 ) 如果只= ( 屯，y 3 ) = e + 只o ，则而y 3 可以由公式给出 f x 3 = 名一x 1 一x 2 1 y 3 ：五( _ 一屯) 一y f a ：丝二约 j 屯一五 l 旯：3 x ? + a 4 【2 m 3 2 3 2 域f 2 ”( n - 2 _ 1 ) 上的椭圆曲线e 若五屯 觏= x 2 ( 3 2 4 ) ( 3 2 5 ) 因为域的特征为2 ，所以域上椭圆曲线e 的w e i e r s t r a s s 方程可设为 e ：y 2 + x y = + 口2 x 2 + 民 e 在，上的运算规则为： 其中 ( 3 2 6 ) 设置= ( _ ，y 0 ，最= o ：，y ：) 是曲线上e 上的两个点，o 为无穷远点，则 1 ) o + e = 只+ o ； 2 ) 一只= ( x l ，x l + m ) ； 3 ) 如果只= ( x 3y ，) = 只+ 只o ，则屯，y ，可以由公式给出 一= 名+ a + _ + x 2 + 口2 ( 3 - 2 7 ) 【y 3 = 旯( 一- i - 工3 ) + x 3 + m 1 4 第3 章椭圆曲线数学基础及算法 3 2 4 椭圆曲线群的阶 若葺x 2 ( 3 2 8 ) 若薯x 2 椭圆曲线群的阶( 即椭圆曲线e 上所含有的点的个数) ，记为把( f q ) ，由h a s s e 定理：令= 群e ( ) = g + l t ，则h 2 g ，可得把( b ) 的一个大概的个数范 围，但是这样的范围对于密码学来说，并不是很实用，故在此引入两种用于计算 椭圆曲线阶的常用方法； 1 ) r s c h o o l 做了开创性的工作，提出了著名的s c h o l 算法，后经a t k i n 和e l k i e 的改进，提出了s e a ( s c h o o le l k i e sa t k i n ) 算法。之后，m o r a i n ，l e r c i e r 等 人又对它作了一些优化，如今s e a 算法已成为计算椭圆曲线阶的有效算法。另外， s a t o h 也提出了比较有效的s a t o h 算法及目前对于二进制域效率较高的 s a t o h f g h ，a g m ，s s t ，m s s t 等算法。 2 ) 仅限于有限域为只上的算法。并且这种算法要求所定义的有限域中的m 能分解为m = d e ，其中d 为一个小整数，通过计算小域r 上的# e ( b ) ，从而计 算出撑e ( 只) 。这种方法简单易实现，但是适用范围小，不能计算出任意m 或固 定m 的撑e ( 只，) 。 3 2 5 椭圆曲线基点及其阶 要构造基于离散对数的密码体制，就必须找出椭圆曲线加法群的大素数因子 子群的一个生成元，即这个群的基点，记为p ( x ，y ) 。3 n n ( j 为整数) 使得 n p = 0 成立的最小正整数，则称n 为基点，的阶。 1 5 鬻华 = = m 一、 成都理j ：人学硕+ 学位论文 第4 章椭圆曲线密码体制 公钥密码体制根据其所依据的数学难题一般分为三大类：大整数分解类、离 散对数类、椭圆曲线离散对数类。有时也把椭圆曲线离散对数类归为离散对数类。 1 9 8 5 年，n e a lk o b l i t z 和矿s m i l l e r 分别独立提出将椭圆曲线应用于公钥密码体 制，使得椭圆曲线，这个被数学家研究了一百多年的数学问题，在密码学领域发 挥了重要作用。椭圆曲线公钥密码体制一直是密码学界研究的热点，并且随着研 究的深入同渐成熟。 椭圆曲线公钥密码体制的安全性建立在解椭圆曲线离散对数问题( e l l i p t i c c u r v ed i s p e r s el o g a r i t h mp r o b l e m ，简称e c d l p ) 的困难性之上，现在求解 e c d l p 最好的算法具有全指数时间复杂度，与此不同的是，整数因子分解问题 却只有亚指数时自j 算法。这意味着在达到相同安全性时，椭圆曲线密码使用的密 钥长度比r s a 密码更短。由于密钥短而获得的优点包括加解密速度快、节省能源、 带宽和存储时间。 使用椭圆曲线公钥密码体制可以实现信息加密，签名与认证，密钥分配三大 功能。椭圆曲线密码算法有如下特点： 1 ) 离散性 密码算法需要的是离散值的定点运算，而不是连续值的浮点运算，在密码算 法中不允许舍入。 2 ) 大数运算 密码算法往往是大数运算，如r s a 体制中要求5 1 2 位6 4 个字节的模幂运算。 安全的椭圆曲线密码系统要求1 6 0 位的大数运算i 但现有微机的c p u 最多只支 持6 4 位的运算。 3 ) 要求大容量的数据存储 密码运算通常都要利用大容量的数据表，即用空间来换取时间上的加速，这 就要求运算部件具有大容量的存储。 4 1 包含大量的并行性 这种并行性同时包含多种粒度的并行或多层次的并行。既有结点之间并行， 也有结点内部并行。故要求处理结点本身具有一定的并行性。 1 6 第4 章椭圆曲线密码体制 下面给出椭圆曲线公钥密码体制的基本原理，分别为椭圆曲线密码体制的参 数组，椭圆曲线公钥密码体制加解密方案，椭圆曲线公钥密码体制的数字签名算 法。 4 1 椭圆曲线离散对数 椭圆曲线离散对数问题实际上是一个纯粹的数学问题，椭圆曲线密码体制依 赖于它的困难性而构造。作为椭圆曲线密码学的基础，e c d l p 具体描述如下： 给定定义于有限域上的椭圆曲线e ，基点p e ( ) ，阶为玎，点q e ( ) ， 寻