（计算机应用技术专业论文）椭圆曲线密码算法的研究与实现.pdf

沈阳工业大学硕士学位论文 摘要 随着信息技术的不断发展和应用，信息的安全性变得越来越重要。现在广泛使用的 r s a 公钥密码系统已很难满足未来人们对信息高安全性的需求。椭圆曲线密码系统 ( e l l i p t i cc u r v ec r y p t o s y s t e m ) 是迄今为止每比特具有最高安全强度的密码系统。与其 他公钥密码系统相比，椭圆曲线密码系统除了安全性高外，还具有计算负载小，密码尺 寸短，占用带宽少等优点。因此，椭圆曲线密码系统被认为是最有希望成为下一代通用 的公钥密码系统。 本文首先对密码技术的发展现状及其发展趋势进行了分析和综述，详细的介绍了私 钥密码系统和公钥密码系统的发展，并给出了一些典型的加密体制的简要分析。其次， 探讨了椭圆曲线密码体制的原理，包括椭圆曲线密码的数学基础、椭圆曲线的基本概 念、椭圆曲线密码体制的构造思想、撼圆i l 黾线上点的运算等问题，同时分析了椭圆曲线 密码系统的安全性和有效性，给出了安全椭圆曲线应该符合的三个标准。第三，给出了 一个基于c m 算法的安全椭圆曲线产生算法，利用这个算法产生的椭圆曲线的阶是两个 大素数的乘积，并对其的正确性进行了理论上证明。第四，实现了椭圆曲线密码系统中 的一些关键性算法，包括椭圆曲线生成算法、椭圆曲线密码中的k p 运算、素性检测算 法以及大整数间的运算。第五，提出了一种基于e c c 的e i g a m a l 数字签名方案，将经 典的e i g a m a l 数字签名方案移植到椭圆曲线密码系统之上，并验证了该方案的正确性。 最后，对e c c 的发展趋势和研究方向进行了探讨。 关键词：椭圆曲线密码，信息安全，数字签名方案 婆堕王些查堂堕主塑迨塞 r e a r c ha n d i m p l e m e n t a t i o n o ft h e e l l i p t i cc u r v ec r y p t o g r a p h y a b s t r a c t w i 也t h ed e v e l o p m e n ta n da p p l i c a t i o no f i n f o r m a t i o nt e c h n o l o g y 。t h ep r o b l e mo f i n f o m a a - t i o ns e c u r i t yb e c o m e sm o r ea n dm o r ei m p o r t a n t r s a c r y p t o s y s t e m ，ap u b l i c - k e yc r y p t o s y s t e m b e i n g u s e dw i d e l y t o d a y ，s e e m s t oh a v ed i f f i c u l t yi nm e e t i n gt h eu s e r s n e e do f h i g h e rs e c u r i t y s of a r , t h ee l l i p t i cc u r v ec r y p t o s y s t e mf a c e ) p r o v i d e st h eh i g h e s ts l r e n g t h - p e r - b i to f a n yc r y - p t o s y s t c mk n o w n i na d d i t i o nt oi t sh i g hs e c u r i t y ，e c ca l s oh a sm a n y o t h e rm e r i t so v e ro t h e r p u b l i c - k e yc r y p t o s y s t e m ss u c h 踞l e s sc o m p u t a t i o no v e r h e a d s s h o r t e rk e ys i z e c o n s i d e r a b l e b a n d w i d t hs a v i n g s , a n ds oo n a l lo f t h e s em e r i t sh a v em a d ei tt h eb e s tp u b l i c - k e yc r y p t o s y s t e m t h a ti ss u i t a b l ef o rc u r r e n tu s ei nf u t u r e t h i s p a p e r f i r s ta n a l y s e sa n ds u m n l a 出e st h es t s t u sq u oa n de v o l u t i o nt r e n do f e n c r y p t i o n ， a n di n t r o d u c e si nd e t a i lt h e d e v e l o p m e n t o fp r i v a t e - k e y c r y p t o s y s t e m a n d p u b l i c - k e y c r y p t o s y s t c m , a n dp r o v i d e st h eb r i e f a n a l y s i s o f a f e w t y p i c a ls c h e m e s s e c o n d ，t h ep r i n c i p l eo f e c ci sd i s c u s s e d , i n c l u d i n gt h em a t hf o u n d a t i o no fe c c ，b a s i cc o n c e p t i o no f e l l i p t i cc u r v e ， c o n s t r u c t i n g i d e ao f e c c ，o p e r a t i o no nt h ee l l i p t i cc u r v ea n ds oo n m e a n w h i l e ，t h e s e c u r i t ya n d e f f i c i e n c yo f e c c 雠a n a l y z e d a n dt h u st h r e ec o n d i t i o n sr e q u i r e d b ye c c a l eg i v e n t h i r d a n e f f i c i e n ta l g o r i t h mt og e n e r a t et h es e c u r ee l l i p t i cc u r v e sw h i c hb a s e so nt h ec m a l g o r i t h mi s p r e s e n t e d a c c o r d i n gt ot h i sa l g o r i t h m ，t h er a n ko fe l l i p t i cc t l l w ec o n s t r u c t e di st h ep r o d u c to f t w o l a r g ep r i m en u m b e r s a n d i t sc o r r e c t n e s si sp r o v e di nt h e o r y f o u r t h , s o m e k e ya l g o r i t h m s i ne c ca r ci m p l e m e n t e d , i n c l u d i n l ga l g o r i t h mo fg e n e r a t i n gt h ee l l i p t i c c u r v e ，a l g o r i t h m o f c o m p u t i n g t h ek po f t h ee c c ，a l g o r i t h mo f d e t e c t i n g p 矗m en u m b e ra n dl g o r i t h r no f o p e r a t i n g b e t w e e nt h eb i gi n t e g e a s f i f t h , t h ev a r i a t i o no fe l g a m a ls i g n a t u r es c h e m eb a s e d0 1 1e c ci s p r e s e n t e da n di t sv a l i d i t y i s p r o v e d a n dt h ei 删s c h e m et r a n s p l a t e st h et y p i c a le l g a m a l s i g n a t u r es c h e m e i n te c c a t l a s t , t h ee v o l u t i o nt r e n da n d r e s e a c hd i r e c d o na l ed i s c u s s e d 。 k e yw o r d s ：e l l i p t i cc u r v ec r y p t o g r a p h y , i n f o r m a t i o ns e e u r i t y j ) a t as i g n a m r e s c h e m e 2 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究：l ： 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：肄日期： 关于论文使用授权的说明 娜峰 ? | 口 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩e j 或其他复制手段保存沦 文。 ( 保密的论文在解密后应遵循此规定) 签名：搏导帅签名：域鼬l 刚j z 哟嘻j | o 沈阳工业大学硕士学位论文 1 1 引言 随着现代通信技术的发展和迅速普及，特别是随着由通信与计算机技术相结合而诞 生的计算机互联网络全面的进入千家万户，使得信息共享应用日益广泛与深入。世界范 围的信息革命激发了人类历史上最活跃的生产力，但同时也使得信息的安全问题目渐突 出而且情况也越来越复杂。从大的方面来说，信息安全问题已威胁到国家的政治、经 济、军事、文化、意识形态等领域。因此，很早就有人提出了“信息战”的概念并将信 息武器列为继原子武器、生物武器、化学武器之后的第四大武器。从小的方面来说，信 息安全问题也是人们能否保护自己个人隐私的关键。 由此可见，加强对信息安全问题的研究，寻求解决信息安全问题的良方，是信息时 代提出的紧迫任务。 1 2 网络安全概况 信息安全【l 】是指通过采取措施，保障数据的完整性、机密性和可用性。网络安全1 2 是指网络系统的硬件、软件及系统中的数据受到保护，系统连续、可靠、正常运行，网 络服务不中断。网络安全的本质是网络上的信息安全。 随着计算机和通信技术的发展，信息安全技术越来越重要。现在的信息安全主要是 指网络上的信息安全。网络的安全与否直接影响储存在计算机上信息的安全与否。网络 不安全的主要原因有三个方面；网络协议自身的缺陷、网络的开放性和黑客的攻击。 目前，互联网上最广泛使用的通信协议是t c p i p 协议，早期研制该协议的目的是 追求网络的互通性和实用性，对协议可能受到的攻击考虑较少。这一协议为全球网络互 联奠定了基础，但同时也留下了安全隐患。如网络上的远程口令传输认证方式，让窃听 者容易获得口令。除了t c p i p 协议外。其他各种应有协议( 如f t p 、h t t p 、s m t p 、 s n m p 等) 都或多或少的存在安全缺陷。 网络的开放性爨怀言自明。全球互联使每一台连在i n t e m e t 上的主机无须到目的现 场即可访问全球各地的主机或资源服务器。这在提供全球通信便捷的同时，无疑也给非 法入侵者提供了机会。网络的开放性还表现在各种访问代理方式和远程登录方式使非法 沈阳工业大学硕士学位论文 入侵者能通过迂回路径跨越多国入侵，由于涉及多国的政策和法律限制，为跨国犯罪的 侦破追踪过程带来很大困难。 黑客作为有意或无意的非法入侵者，是网络安全犯罪的直接责任人，大部分黑客以 拥有高科技犯罪技术为宗旨，在网络上不断探询各种漏洞、窥测隐私、盗窃机密、破坏 设施，有些仅仅是恶作剧，有些则是有组织有目的的间谍行为。黑客犯罪由于带有智慧 较量的色彩，有些黑客乐此不疲，从而增加了网络的安全隐患。 信息网络安全的威胁因素层出不穷，相应的安全技术也不断发展。目前采用的网络 安全技术主要有密码技术、防火墙技术、入侵检测技术、漏洞扫描技术等。其中密码技 术，特别是加密技术是信息安全技术中的核心技术。 目前，国内外对安全技术的研究已经成现出多理论、多学科、多技术综合运用的趋 势，对于网络通信安全方面的研究则主要是以密码学为基础。密码学唧的信息理论主要 包括c e s h a n n o n 于1 9 4 8 年提出的保密系统的信息理论和s i m m o u s 的认证系统的信息 理论。自七十年代中期，d i i f i e 和h e l l m a n 在“密码学的新方向”一文中首次提出了公 钥密码的基本观点以及数据加密标准( d a t ae n c r y p t i o ns t a n d a r d ，简称d e s ) 的颁布以 来，密码学在理论上和应用上都有了很大的发展，提出了许多新的公钥密码体制，为解 决私钥密码体制的密钥管理与分配开辟了一条广阔的道路，其典型代表是r s a 公开密 钥密码体制和椭圆曲线公开密钥体制即e c c 。然而，无论是私钥密码体制还是公钥密码 体制，都存在着一定的局限性，例如：d e s 算法中的密钥长度过短，密钥分配需要在通 信之前进行秘密分配，密码体制本身不能进行身份识别等问题；e c c 算法存在生成安全 的椭圆曲线速度慢，计算椭圆曲线上点的数乘运算效率低等问题，这些都是当前公钥密 码研究领域中的热点问题。 计算机网络技术的发展以及网络通信中信息量的增加，对于密码理论与技术的研究 也起到了极大的促进作用。而面对密码分析者的攻击，面对数学理论方法的不断进步和 计算机技术迅速发展的威胁，研究并建立一种更好、更加完善、更安全的加密方法，以 实现网络通信中数据安全性的要求，更是国际上亟待解决的重大课题。 2 沈阳工业大学硕士学位论文 1 3 课题内容 本课题的研究内容是通过对密码技术研究现状的分析，根据密码技术的发展趋势， 针对当今密码研究领域中的热点椭圆曲线密码体制展开工作。 通过一年多学习和研究，本文主要完成以下几个方面工作： ( 1 ) 探讨了椭圆曲线密码体制的原理，包括椭圆曲线密码体制的数学基础、椭圆 曲线密码体制的基本概念、椭圆曲线密码体制的构造思想以及椭圆曲线上点的运算等问 题。 ( 2 ) 实现了椭圆曲线密码体制中的一些基本算法，如k p 运算、大整数间的运 算、素性检测算法和安全椭圆曲线产生算法等，为师弟们下一步继续工作打下了一定的 基础。 ( 3 ) 给出了一种基于c m 构造法的椭圆曲线产生算法。本文研究了已有的几种著 名的椭圆曲线产生方法，经过分析比较后，认为c m 构造法在实际应用中最有前途。在 c m 算法的基础上提出了一种新的椭圆曲线产生算法，这个算法产生的椭圆盐线的阶具 有双大素数乘积，安全性好。并在数学上证明了算法输出阶的正确性，同时也实现了该 算法。 ( 4 ) 给出了一种基于e i g a m a l 的椭圆曲线数字签名方案。本文在深入的研究了 e i g a m a l 数字签名方案后，首先，将其转换到椭圆曲线密码体制上，然后，针对原始 e i g a r n a l 签名算法的不足，提出了改进方法，生成了签名算法，在可用性和效率上均有 提高。 3 沈阳工业大学硕士学位论文 2 密码技术的现状和发展趋势 2 1 密码技术概述 密码技术作为- - i 古老的技术。其历史大概可追溯到人类社会出现战争的时候。在 当今的信息时代，随着计算机技术的发展，网络的开放性、共享性和互联程度也不断的 扩大，网络上传输了大量的敏感数据，诸如商业机密、资金转移及私人财产等，它们的 安全己受到严重威胁。因此，作为信息安全的核心问题，密码理论与技术越来越受到人 们的关注。现代密码学的应用已不再局限于军事、政治和外交领域，其商用价值和社会 价值也已得到了充分肯定，因此，对这一问题的研究具有很强的理论和现实意义。 密码技术主要由密码编码技术和密码分析技术两个既相对对立又相互依存的分支组 成。密码编码技术的任务是产生安全有效的密码算法，实现对信息的加密或认证。密码 分析技术的任务是破译密码或伪造认证码，以窃取保密信息或进行破坏。密码理论的发 展分为古典密码学、近代密码学和现代密码学。 目前，密码技术已发展成为一门系统的技术科学，它涉及到通信、计算机及微电子 等多个学科领域，所应用的数学工具包括数论、概率统计、近世代数、信息论、复杂性 理论、自动机理论、组合数学及椭圆曲线理论等，同时，该技术的发展还推动了并行算 法的研究，从而成为近若干年来非常引人入胜的领域。 2 _ 2 发展阶段 密码技术的发展历史大致可划分为三个阶段：1 9 4 9 年前为第一个阶段。这时的密 码学与其说是一门科学，不如说是一门艺术。密码学专家常常是凭直觉和信念来进行密 码设计和分析。而不是推理证明。1 9 4 9 - - 1 9 7 6 年为第二个阶段。1 9 4 9 年，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 沈阳工业大学硕士学位论文 新纪元，并指明了s h a n n o n 在1 9 4 9 年，提出的将密码建立在某些已知的数学难题之上 的具体实现途径。这一阶段，密码技术发展极为迅速。 2 _ 3 研究现状 目前，密码理论与技术主要包括两部分 4 1 ，即基于数学的密码理论与技术( 其中包 括公钥密码、分组密码、流密码、认证码、数字签名、h a s h 函数、身份识别、密钥管 理、p k i 技术等) 和非数学的密码理论与技术( 包括信息隐形、量子密码、基于生物特 征的识别理论与技术) 。 基于数学的密码理论与技术中，按照加密体制的不同可以分为：私钥( 单钥或对 称) 密码体制，该体制的加密密钥和解密密钥相同或彼此间容易确定，其典型代表是美 国的数据加密标准d e s 另一种是公钥( x 2 钥或非对称) 密码体制，该体制的加密密钥 和解密密钥不同且从一个很难推出另一个，加密密钥公开而解密密钥保密，其典型代表 是r s a 体制。 2 3 1 私钥加密体制 2 3 1 1 私钥加密体制的定义 私钥加密算法是指加密密钥与解密密钥相同或者彼此容易相互确定的加密算法。在 大多数私钥加密算法中，加密密钥和解密密钥是相同的。 使用私钥加密算法的加密体制称为私钥体制。 2 3 1 2 私钥加密体制的特点 私钥加密算法的实现速度快。从欧洲的n e s s i e ( n e w e u r o p e a ns c h e m e sf o rs i g n a - t i l l i n t e g r i t ya n de n c r y p t i o n ) 候选算法的测试结果 5 1 看，加密速度可达到每秒数兆到数 十兆，有的甚至超过每秒百兆。对称算法的这个特点使其有着广泛的应用，特别适合于 海量数据的加密。因为算法不需要保密，所以制造商可以开发出低成本的芯片以实现数 据加密。 但私钥加密系统最大的问题是密钥的分发和管理非常复杂、代价高昂。当用户群很 大、分布很广时，密钥的分配和保存都非常困难，因为，对于具有行个用户的网络，需 要n ( n 1 ) 2 个密钥。 私钥加密算法的另一个缺点是不能实现数字签名。 5 沈n z 业大学硕士学位论文 2 3 1 3 私钥加密体制的安全性 私钥加密系统的安全性依赖于加密算法的强度和密钥的秘密性。加密算法必须具有 足够的强度，使得仅根据密文去解密信息在计算上是不可能的，没有必要确保算法的秘 密性，但必须保证密钥的秘密性。 2 3 1 4 私钥加密算法举例 在私钥加密系统中。最著名的是美国数据加密标准d e s 、高效率加密标准a e s 和 欧洲数据加密标准i d e a 。 ( 1 ) d e s 在1 9 7 3 年和1 9 7 4 年间，美国国家标准局( n b s ) ，后来改名为美国国家标准技术 研究所( n i s t ) ，为了用于保护美国联邦机构的敏感信息，发布了征集加密算法的通 告。从提交的建议中，选择了由i b m 公司提交的算法。1 9 7 5 年，在受控的条件下对此 算法做了一些公开的评价。1 9 7 7 年，取名为数据加密标准( d e s ) 。1 9 8 1 年，d e s 被 美国商业组织所采纳作为美国国家标准数据加密算法。该算法很快被用于政府的机密 性目的和金融工业界的完整性目的，并且从那个时代起，被广泛用于各个领域。 d e s 使用5 6 比特的密钥，每次处理一个长度为6 4 比特的组。6 4 比特一组的明文 从算法的一端输入，6 4 比特的密文从另一端输出。密钥通常表示为6 4 比特的数，但每 个第8 位都用作奇偶校验，可以忽略。密钥可以是任意的5 6 比特的数，且可在任意的 时候改变。 d e s 由于提出时间已经很长了，5 6 位的密钥相对于当前的高速计算机来说，已经 太短。目前依靠i n t e r n e t 分布计算能力，用穷举法破译d e s 以成为可能。1 9 9 7 年3 月 1 3 日，美国科罗拉多州程序员v e 蹦x f 6 l ，在i n t e r n e t 上征集了数万名志愿者，在协同工 作下，用了9 6 天成功的破译了d e s 。 ( 2 ) a e s 1 9 9 7 年4 月1 5 月，美国国家标准技术研究所( n i s t ) 发起征集高级加密标准 ( a e s - a d v a r 砣e d e n c r y p t i o ns t a n d a r d ) 的活动，并专门成立了a e s 工作组，目的是为了 确定一个非密级的、全球免费使用的数据加密标准。1 9 9 7 年9 月1 2 日，公布了征集 a e s 候选算法的通告。a e s 的基本要求是比三重d e s 快而且至少与三重d e s 一样安 6 沈阳工业大学硕士学位论文 全，分组长度为1 2 8 比特，密钥长度为1 2 8 1 9 2 2 5 6 比特。1 9 9 8 年8 月2 0 日，n i s t 召 开了第一次a e s 候选会议，并公布了1 5 个候选算法。1 9 9 9 年3 月2 2 日，举行了第二 次a e s 候选会议，公布了1 5 个候选算法的讨论结果，并从中选出了5 个候选者。2 0 0 0 年4 月2 5 日，n i s t 举行了第三次a e s 候选会议，对这五个候选算法又进行了讨论。 n i s t 于2 0 0 0 年1 0 月2 日公布了最终候选结果，将r i j n d a e l 算法作为候选算法。 r i j n d a e l 算法是一个跌代分组密码算法，其分组长度和密钥长度都是可变的，但 是，为了满足a e s 的要求，限定分组长度为1 2 8 比特，密钥长度为1 2 8 1 9 2 2 5 6 比特， 相应的轮数为1 0 1 2 1 4 。 ( 3 ) i d e a i d e a 是x l a i 和j m a s s e y 于1 9 9 0 年发表的，当时的名称是p e s ( p r o p o s e d e n c r y p t i o ns t a n d a r d ) ，它产生的背景是作为d e s 的更新换代产品的候选方案。1 9 9 1 年，以色列数学家e b i h a m 和a s h a m i r 发表了差分分析方法，为了抵抗这种强有力 的攻击形式，i d e a 的更新版本出现了。新的算法更名为i p e s ( i m p r o v e dp r o p o s e d e n e r y p f i o ns t a n d a r d ) ，并于1 9 9 2 年再次更名为今天的i d e a ( i n t e r n a t i o n a ld a t a e n e r y p t i o na l g o r i t h m ) 。 i d e a 分组密码系统的明文和密文块长度为6 4 比特，密钥长度则为1 2 8 比特。加 密时，将6 4 比特的明文分成4 个1 6 比特的子块，这4 个子块就是算法的输入部分，这 4 个子块分别和密钥的6 个1 6 比特子块及中间结果进行不同的群运算。i d e a 分组密码 系统在加密和解密运算中仅仅使用作用于1 6 比特子块的一些基本运算，因此效率很 高。同时，i d e a 密码系统具有规则的模块化结构，有利于加快其硬件实现速度。 2 3 2 公钥加密体制 2 3 2 1 公钥加密系统的定义 公钥加密算法：也叫非对称加密算法，它使用的加密密钥与解密密钥不同，并且解 密密钥不能根据加密密钥在合理的时间内计算出来的加密算法。办密密钥可以公开，称 为公钥，任何人都可以用公钥加密消息；解密密钥需要保密，称为私钥，只有拥有相应 私钥的人才能解密消息。 使用公钥加密算法的加密体制称为公钥加密体制，又称非对称加密体制。 - 7 沈阳工业大学硕士学位论文 2 3 2 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 0 倍。 2 3 2 3 公钥加密系统的安全性 目前所使用的公钥密码体制的安全性基础主要是数学中的困难问题。在目前流行的 公钥密码体制中既具有一定安全性又能比较容易实现的，按照所基于的数学难题可分为 如下三类：基于大整数分解问题的公钥密码( 如r s a ) ；基于有限域上的离散对数问题 的公钥密码( 如d s a ) ；基于椭圆曲线上的离散对数问题的公钥密码( 如e c c ) 。 2 3 2 4 公钥加密算法举例 ( 1 ) r s a r s a 算法是r o nr i v e s t 、a d is h a m i r 和l e na d l e m a n 在1 9 7 8 年提出的，是最早且 最通用的公钥算法之一，它能够提供加密、解密、签名、验证和密钥传递等服务。r s a 的安全性是基于大整数因式分解的困难性。 由于分解大整数方法的进步及完善、计算机速度的提高以及计算机网络的发展，对 r s a 的安全带来了一定的威胁。目前，7 6 8 比特长的r s a 己不安全。般建议使用 1 0 2 4 比特，预计要保证2 0 年的安全就要选择1 2 8 0 比特长，但密钥长度的增加导致了 其加密解密的速度大为降低，硬件实现也变得越来越难以忍受，从而使其应用范围越来 越受到制约。 ( 2 ) d s a d s a ( d a t as i g n a t u r e a l g o r i t h m ) 是美国商业部下属的国家标准技术研究所 ( n i s t ) 公布的一个信息处理标准，它是e 1 g a m a l 签名机制的一个变形，专门用于数 字签名。它的安全性是基于有限域上的计算离散对数的困难性。它仅提供数字签名，不 提供数据加密功能。 8 沈阳工业大学硕士学位论文 目前，对有限域上的离散对数的研究表明：d s a 密钥至少需要1 0 2 4 比特，才能保 证有足够的中长期安全。 ( 3 ) e c c 椭圆曲线加密系统( e l l i p t i cc u r v ec r y p t o s y s t e m - e c c ) 是基于椭圆曲线上的离散对 数的计算困难性而提出的公钥加密系统。椭圆曲线加密系统使用的是离散对数问题的一 种变形，它是在椭圆曲线空间中决定公钥和私钥的关系。同时，因为椭圆曲线上的离散 对数的计算要比有限域上的离散对数的计算更困难，在目前的条件下只需要1 6 0 比特的 密钥长即可。 椭圆曲线加密算法是一种安全性高、算法实现性能好的公钥加密算法。与r s a 相 比，其1 6 0 比特密钥长度的安全性与r s a 的1 0 2 4 比特密钥长度的安全性相当。椭圆曲 线加密算法具有单位计算量安全性高、处理速度快、存储空间占用少、带宽要求低等优 点，因此它有望取代r s a ，成为通用的公钥加密算法。 9 沈阳工业大学硕士学位论文 3 椭圆曲线密码体制 椭圆曲线理论是代数几何、数论等多个数学分支的一个交叉点，一直被认为是纯理 论学科。近年来，由于公钥密码学的产生与发展，该学科也我到了它的应用领域。特别 的，以椭圆曲线上的有理点构成的a b e l 群为背景，实现各种密码体制已是公钥密码学 领域的一个重要课题。自8 0 年代中期被引入以来，椭圆曲线密码体制逐步成为一个十 分令入感兴趣的密码学分支，1 9 9 7 年以来形成了一个研究热点。这种密码体制的诱人 之处在于在安全性相当的前提下，可以使用较短的密钥。一般认为，椭圆曲线密码体制 的密钥长度为1 6 0 比特时【7 】，其安全性相当于r s a 使用1 0 2 4 比特。密钥短意味着小的 带宽和存储要求，这在某些应用中可能是决定性的因素。椭圆曲线密码体制的诱人之处 还在于它建立在一个不同于大整数因式分解及有限域上离散对数问题的数学难题之上。 自公钥密码产生以来，人们基于各种数学难题提出了大量的密码方案，但能够经受住 时间的考验而广泛为人们所接受的只有基于大整数因式分解及离散对数问题的方案，如 此狭窄的数学背景不能不引起人们的担忧，寻找新的数学难题作为密码资源早就是人们 努力的一个方向。同时。椭圆曲线资源丰富i 剐，同一个有限域上存在着大量不同的椭圆 曲线，这为安全性增加了额外的保证，也为软、硬件实现带来方便。 安全性显然是任何密码体制的必各条件，椭圆曲线密码体制的安全性分析，因此也 引起了国内外密码学家及有关部门的关注与重视，但成果却并不十分的丰富。也许这可 视为椭圆曲线密码体制具有高强度的一种证据，因此，大多数密码学家对这种密码体制 的前景持乐观态度【9 】。 所以。密码学界普遍认为它将替代r s a 成为通用的公钥密码体制。安全电子交易 协议( s e t ) 的制定者已经把它作为下一代s e t 中缺省的公钥密码算法【。为了鼓励开 发基于椭圆曲线密码体制的应用产品，几个国际标准化组织已经把椭圆曲线密码体制作 为新的信息安全标准。 椭圆曲线密码所具有的巨大商业价值以及重大的军事价值正在为越来越多的人所关 注。 1 0 沈阳工业大学硕士学位论文 3 1 椭圆曲线密码体制的基本概念 3 1 1 数学基础 3 1 1 ，l 群和域的概念 ( 1 ) 如果一个非空的集合g ，对于代数运算。来说满足以下条件： g 对于运算。是封闭的：对于任意的a ，6 g ，满足口o b g ； 结合律成立：对于a ，b ，c g 。满足0 0 6 ) o c = 口o ( 6o c ) ； g 里至少存在一个左单位元e ，对任意口eg 满足p o 口= 口； 对于g 里的每一个元a ，g 里至少存在一个左逆元a 。使口10 口= p ： 则称g 对于运算0 构成一个群。 ( 2 ) 如果一个非空的集合r ，对于一个称为加法的代数运算。和另一个称为乘法 的代数运算。满足以下条件： 震对加法运算。构成一个交换群( ：b 法单位元为零元) ： 启中至少含有一个非零元，r 对乘法运算。封闭，对乘法运算。满足结合律； 乘法有单位元，非零元有乘法逆元； 乘法交抉律成立两个分配律舔成立i 则称r 对该加法和乘法构成一个域。 3 1 1 2 有限域 元素个数有限的域称为有限域。常用的有限域是素数域e 和特征夯2 的有限域。 这里只介绍第一种。 素数域耳的定义为：设p 是一个素数，整数集合 o ，1 ，2 ，p - - i 】构成一个有 限域，记为r 。 ( 1 ) 耳的加法运算：设x ，j ，是中的元素，则加法结果为o + y ) r o o d p 。 加法单位元即为零元素：0 ； 域元毒x 的加法逆元为；( 却m o d p 。 ( 2 ) b 的乘法运算：设算，y 是耳中的元索，则乘法结果为( x y ) m o d p 。 乘法单位元：l ： 一 鎏塑三些奎堂堡主堂篁堡兰 非0 元素z 的乘法逆元为y ，其中y 满足x y = l ( m o d p ) 。 3 1 2 椭圆曲线的基本概念 椭圆曲线的研究来源于椭圆积分：b 簧荔，其中e ) 是x 的三次多项式或四次 多项式。这样的积分不能用初等函数来表达，为此引用了椭圆函数。 3 1 2 1 椭圆曲线的相关概念 ( 1 ) 仿射平面和射影平面 域足上的仿射平面：指集合( ( x ，y ) ix ，y k ) ，表示为4 2 ( k ) 。 域石上的射影平面：设是n o ，0 ，o ) 上的一个等价关( 一，y 。，z 1 ) 一( x ：，y ：，z ：) ， 当且仅当存在u c k ，使x l = 搬2 ，y 1 = u y 2 ，2 l = 船2 。域k 上的射影平面p ( 趵是指出 由关系决定的等价类的集合。每个包含( x ，y ，= ) 的等价类记为 ：y ：z ) 。 ( 2 ) 代数封闭域 如果每个系数在k 上的n 阶多项式恰有，z 个世中的根，则称域k 是代数封闭的。 对每个域心都存在一个代数封闭的域足，使k 包含于置中。 ( 3 ) w e i e r s t r a s s 方程 设r 是有f 良域，则其上的韦尔斯特拉斯( w e i e r s t r a s s ) 1 1 1 等式： 】，2 z + a , x y z + a 3 y z 2 = x 3 + a 2 x 2 z + a 4 爿z 2 + 口6 2 3 ( 3 1 ) 称为w e i e r s t r a s s 方程，其中a ia 2 ，d 3 ，a 4 ，a 6 耳。 ( 4 ) 奇异曲线与非奇异曲线 若仿射曲线，( 以_ y ) ：o 上有一个点( 口，6 ) ，且满足荽，_ o f 在点( 口，6 ) 都为o ，则称 o y ( 口，6 ) 是曲线f ( x ，力= 0 上的一个奇异点。 有奇异点的曲线称为奇异曲线( s i n g u l a rc u r v e ) 。没有奇异点的曲线称为非奇异曲 线( n o n _ s i n 4 耍d a rc u r v e ) 。 在射影平面上， - 1 2 沈阳工业大学硕士学位论文 f ( x ，y ，z ) = y 2 z + 口l 7 z 十口3 y z 2 一x3 一a 2 x 2 z 一日4 爿z2 一日6 2 3 ( 3 2 ) 如果对所有满足f ( z ，弘z ) = o 的点p ，f 在p 点的3 个偏导数篆，面o f ，篆不全为o ， 则称f ( x ，y ，：) 是非奇异的。 3 1 2 2 椭圆曲线的映射变换 设b 上的w e i o r s t r a s s 等式( 3 1 式) 是平滑的，则该方程在b 上的所有的解组成 的集合e ： e = ( ，y ，z ) 耳i f ( x ，y ，z ) = 0 ) ( 3 3 ) 称为域f p 上的一条椭圆曲线。在任意椭圆曲线中，存在唯一一点使其z 坐标为0 ，则该 点为无穷远点，记为0 。 椭圆曲线密码体制就是建立在集合e 上的： e = ( x ，y ，z ) e bi f ( x ，y ，z ) = o ) u 0 ) ( 3 4 ) 则 在w e i e r s l r a s s 等式中，令x = x z ，y = y z ，则可得 ，2 + 口i x y + a 3 y = x 3 + 口2 x 2 + 口4 x + a 6 ( 3 5 ) e = ( ，y ) e 耳| y 2 + 口l 爿】，+ 口，y = x 3 + 日2 2 2 + 口4 x + a 6 ) u o ) ( 3 6 ) 对w e i e r s l r a s s 方程可做如下变换1 2 】： ( x ，y ) - - ) ( x ，y _ 号一争 则可将曲线e 变为； e ：y 2 = x 3 + b 2 x2 + 6 4 x + b 6 - 1 3 ( 3 7 ) ( 3 8 ) 沈阳t 业大学硕士学位论文 对e 可做如下变换 则可将曲线变为 ( 削川等，甜y e ，：y 2 ：x 3 + a x + b 因此，有限域r 上的椭圆曲线为： e ：y 2 = x 3 + a x + b ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) 3 1 2 3 椭圆曲线的判别式和，不变量 对于( 3 1 1 ) 式所确定的椭圆曲线e 其判别式和_ ，不变量【川，定义如下： ：；1 5 0 另0 式：a ( e ) = 一1 6 ( 4 a 3 + 2 7 b 2 ) ( 3 1 2 ) ，不变量：j ( e ) = 一1 7 2 8 ( 4 a ) 3i a ( e ) ( 3 1 3 ) 椭圆曲线是非奇异的当且仅当( e ) 0 。 3 1 2 4 椭圆曲线背景域的选择 本文所讨论的椭圆曲线是在大素数域f p 上实现的，这里的p 是一个大素数。域b 上的元素( 通过对p 的取模) 表示为范围在0 ，l ，p l 间的整数。我们约定p 是 大于3 的素数。 3 1 2 ，5 椭圆曲线的阶 椭圆曲线的阶的定义，如下： 设e 是由( 3 1 1 ) 式定义的椭圆曲线，满足( 3 1 1 ) 式的点( z ，j ，) b 及一个特殊 点即无穷远点o 构成的集合，记为占( b ) ，即 e ( 耳) = ( x ，y ) 耳iy 2 = x 3 + a x + b u o ( 3 1 4 ) 1 4 沈阳工业大学硕士学位论文 e ( b ) 中的元素称为e 的有理点，e ( b ) 相应称为e 的有理点集合。 对域b 上的椭圆曲线e ，可在e ( b ) 上引入加法运算“+ ”，使 构 成一a b e l 群，称作e 的r 有理点子群。椭圆曲线密码体制既是建立在群e ( 以) 上的密 码体制。e ( f p ) 的阶【i “，记为撑e ( b ) ，并称之为椭圆曲线的e 的阶。 3 2 椭圆曲线离散对数问题 一个群g 上的离散对数问趔”l 是这样定义的：已知口，e - g ，确定一个整数x 使 得= 口。，若z 存在，即x = l o g 。声，则爿称作以口为底的声的离散对数。若已 知口、x ，计算卢是容易的。而反过来，已知口、，求解x 是数学界公认得难题， 这就被称为求解离散对数问题。 用椭圆曲线e 上的点的群替代g ，用群加法代替群乘法，用e 上的点p 代替t 2 ， 即可得椭圆离散对数的定义：若e 为r 上的椭圆曲线，p 为e 上一点，则e 上关于 p 的椭圆离散对数的问题定义为：给定一点，为e 上一点，求解整数m ，使 m p = n 。在这里，埘p 表示数乘，即所个p 相加。 求解有限域上的离散对数问题是公认的难题，而求解椭圆曲线离散对数问题比求解 有限域上的离散对数还要困难1 1 6 1 。在有限域b 上，选择椭圆曲线e 及一个具有较高阶 的基点g e ( 砟) ，要想计算该点的倍乘m g ( 即研个g 相加) ，相对来说是容易的。 但已知g 和r a g ，要求m 则是很困难的。这实际上就是椭圆曲线离散对数问题。 目前。对椭圆曲线离散对数问题最有影响的攻击方法是p l l a r dp 方法和p o b l i g - h e l l m a n 方法，这两种方法属于碰撞搜索法，具有纯指数的时间复杂度【1 7 。椭圆曲线密 码的强度主要依赖于其阶是否含有大素数因子。因为，对于小素数因子，已有算法 p o h l i g - s l i v e r h e l l m a n 可解其椭圆曲线离散对数问题。目前，对于阶中含有大素数 因子的椭圆曲线离散对数问题，还没有有效的攻击方法。 椭圆曲线密码的安全性取决于椭圆曲线离散对数问题的难解性。 3 3 椭圆曲线构造密码体制的设计思想 根据以上对椭圆曲线定义及性质的分析，可以知道椭圆曲线上的点对所定义的加法 运算构成阿贝尔群。 1 5 沈阳工业大学硕士学位论文 若我们能找到一条椭圆曲线e ，并将明文通过编码嵌入到e 上，就可以在e 上进行 加密。现有的椭圆曲线密码体制均是从其他群中平移而来的，并未针对e 产生新型的密 码体制，而这种平移主要是针对离散对数问题的密码体制，虽然也有将r s a 体制进行平 移的，但并无实际应有价值和