（信号与信息处理专业论文）基于椭圆曲线密码的数字签名的研究.pdf

西北大学硕士学位论文 摘要 摘要 数字签名是网络时代最重要的技术之一。它不仅提供消息的完整性认证、身 份认证，而且具有不可否认性和不可伪造性。所以，数字签名是实现网上电子贸 易、电子货币、电子购物、电子出版及知识产权保护等系统安全的重要保证。 论文研究了一种适用于实时性要求较高的应用场合的高效率数字签名方案。 方案基于公钥密码体系( p k i ) 中安全强度最高的椭圆曲线密码( e c c ) ，结合两 种典型的e c c 数字签名方案- e c d s a 和e c k c d s a ，在同等安全性前提下， 着重于计算效率的提高。因此在算法上有两个改进：其一从密钥产生到签名、验 证整个过程中都没有使用最费时的求逆运算；其二采用h a s h 函数的汉明重量代 替h a s h 函数本身参与签名和验证的计算。理论分析和仿真实验表明：在同等条 件下论文方案比已有的e c d s a 和e c - k c d s a 两种签名方案的运行时间要短。 论文的另一工作是对椭圆曲线编码进行了一些探讨。此前在这方面的研究只 将信息明文嵌入椭圆曲线上某点的x 坐标，这样就可能出现一个明文对应椭圆曲 线上多个点的情况。论文在k o b l i t z 概率算法的基础上提出一种编码嵌入方法， 将信息明文不仅嵌入椭圆曲线上某点的x 坐标，并且也与该点的y 坐标相关，使 信息明文嵌入椭圆曲线上的唯一点。 关键词：数字签名、椭圆曲线密码、h a s h 函数、汉明重量、椭圆曲线数字签名 1 1 西北大学硕士学位论文 英文摘要 t h e s t u d yo fd i g i t a ls i g n a t u r eb a s e d o n e l l i p t i c c u r v e c r y p t o g r a p h y a b s t r a c t d i g i t a ls i g n a t u r ei so n eo ft h em o s ti m p o r t a n tt e c h n o l o g i e si ni n t e r n e t i tn o to n l y p r o v i d e si n t e g r i t y a u t h e n t i c a t i o no f m e s s a g e ，i d e n t i t ya u t h e n t i c a t i o n , b u t a l s o n o n - r e p u d i a t i o n , u n f o r g e a b i l i t y t h e r e f o r e , d i g i t a ls i g n a t u r eg r e a t l y e n s u l e st h e s e c u r i t yo fs y s t e m s ，s u c ha se l e c t r i ct r a n s a c t i o n , e l e c t r i cc u r r e n c y , e l e c t r i cp u r c h a s e , e l e c t r i cp u b l i c a t i o na n di n t e l l i g e n tp r o p e r t yp r o t e c ti ni n t e m e t a l l i g he f f i c i e n c yd i g i t a ls i g n a t u r es c h e m ea d a p tt oh i g h e rr e a l t i m en e e d sh a sb e e n p r e s e n t e di nt h i sp a p e r i tb a s e do ne l l i p t i cc a l v ec r y p t o g r a p h ( e c c ) ，w h i c hh a st h e m o s ts e c u r i t yi n t e n s ei np u b l i ck e yi n f r a s t r u c t u r e 口r d ) c o m b i n e dw i t ht h et w o w e l l - k n o w ns c h e m e se c d s aa n de c - k c d s a ，t h ed e s i g no ft h ep r e s e n t e ds c h e m e e m p h a s i s o ni m p r o v i n gc o m p u t a t i o ne f f i c i e n c yw i t ht h ee q u i v a l e n ts e c u r i t yl e v e la s t h et w os c h e m e a c c o r d i n g l y , i t sa l g o r i t h mh a st w oi m p r o v e m e n t s t h ef l r s ti st h a tn o t i m ew a s t ei n v e r s eo p e r a t i o nt h r o u g ha l lt h ep r o c e s s ，f r o mk e yp r o d u c i n g ，s i g n a t u r e c a l c u l a t i o nt ov e r i f y i n gc a l c u l a t i o n 1 1 l es e c o n di st h a tu s et h eh a m m i n gw e i g h to f h a s hc o d eo fam e s s a g ei n s t e a do fh a s hc o d ei t s e l ft op a r t i c i p a t ei nt h es i g n a t u r e a n dv e r i f y i n gc a l c u l a t i o n t h et h e o r ya n a l y s i sa sw e l la se x p e r i m e n tr e s u l ti n d i c a t e t h a tt h en e w s i g n a t u r es c h e m ec o s tl e s st i m et h a nt h et w os c h e m e su n d e rt h ep r e m i s e o f e q u i v a l e n ts e c u r i t y b e s i d e s , e l l i p t i cc u r v ee n c o d eh a sb e e ns t u d i e di nt h i sp a p e r s o m ef o r m e r r e s e a r c h e so nt h i st o p i ce m b e da p l a i u t e x ti n t ox - c o o r d i n a t eo f p o i n t si ne l l i p t i cc u r v e , b u ti tw i l lo c c u rap l a i n t e x tc o r r e s p o n d i n gm o r et h a no n ep o i n ti ne l l i p t i cc u r v ei nt h i s w a y a ni m p r o v e dm e t h o db a s e do nt h ek o b l i t zp r o b a b i l i t ya r i t h m e t i ch a sb e e n p r e s e n t e d 1 1 1 em e t h o dn o to n l ye m b e d sap l a i n t e x ti n t ox - c o o r d i n a t eo fap o i n ti n e l l i p t i cc u r v eb u ta l s om a k et h ep l a i n t e x tc o r r e l a t i o nw i t hy - c o o r d i n a t eo f t h ep o i n t a s ar e s u l t , ap l a i n t e x ti se m b e d d e di no n ep o h a ti ne l l i p t i cc u r v e k e y w o r d s ：d i g i t a ls i g n a t u r e ，e l l i p t i cc u r v ec r y p t o g r a p h y , h a s h ，h a m m i n gw e i g h t , 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 e 1 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期 间论文工作的知识产权单位属于西北大学。学校有权保留并向国家有关部门或机 构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存和汇编本学位论文。同时，本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名： 兰继指导教师签名： 品彩色 庐唧7 年么月a 日 锄淬莎月歹日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其 他人已经发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：彳袤秀舄 棚7 年乡月a 日 西北大学硕士学位论文第一章绪论 第一章绪论 1 1 引言 互联网的普及，使得网上电子数据交换( e d i ) 大量增加。电子政务、在线 税务、网络银行、电子商务( 如电子订货系统e o s 、商业增值网v a n 等) 、股 票、经纪等越来越多的敏感或机密信息需要通过网络传输、存储和处理。各种小 型、无线设备也蓬勃发展并接入网络，利用网络传输信息或使用丰富的网上资源。 与此同时，信息的安全问题也显得至关重要。网络信息可能受到的攻击有被 动攻击和主动攻击。被动攻击试图了解或利用信息内容但不破坏信息，主动攻击 试图改变或影响信息。 被动攻击的特点是对传输信息进行窃听和监测，目的是获得信息内容而不改 变信息内容。传统密码体制的加密主要预防这类攻击，即防止敌方获得被加密信 息。 主动攻击包括对信息的篡改和伪造，具体有伪装、重放、消息篡改和拒绝服 务。现代密码体制具有的可认证性则为了防止敌方的主动攻击，包括验证信息真 伪及防止信息在通信中被篡改、删除、插入、伪造、延迟、重放等。 信息认证的目的有两个：信源识别( 身份认证) 和信息完整性( 内容认证) 认证技术一般有数字签名和数字水印。 数字签名主要用于对数字消息( d i g i t a lm e s s a g e ) 进行认证，以防消息的 伪造或篡改，亦可用于通信双方的身份鉴别。它可完成对合约、电子邮件等文本 数据及声音、图像、数字视频等多媒体数据的签署。通过在原始信息上附加一些 信息或对原始信息进行密码变换之后，发送给接收方，接收方根据收到的信息可 以确认信息发送者的身份及信息的完整性。并且发送者事后不可否认已发送信 息，接收者或非法者也无法伪造和冒充或篡改发送的信息。 数字签名作为网络时代最重要的技术之一，成为了信息安全领域的一个研究 热点。目前，国际组织及各国政府已陆续制定了数字签名标准和法律。法国是世 界上第一个制定并通过数字签名法律的国家，我国于1 9 9 5 年也制定了数字签名标 准g b l 5 8 5 1 1 9 9 5 。如今，中华人民共和国电子签名法开始实施，电子签名与 西北大学硕士学位论文第一章绪论 传统的手写签名和盖章具有同等的法律效力。 1 2 基于椭圆曲线的数字签名的研究意义 数字签名建立在公钥密码体制的基础上。基于公钥密码的数字签名体制一般 有三类：基于大整数分解问题( i f p ) 的如r s a 等数字签名；基于离散对数问题 ( d l p ) 的，如著名的e i g a m a l 。d s a 等数字签名；基于椭圆曲线离散对数问题 ( e c d l p ) 的，如e c d s a 、e c k c d s a 等椭圆曲线的数字签名。 下面分几个方面来论述基于椭圆曲线数字签名的研究意义。 首先，e c d l p 比i f p 、d l p 问题的数学背景更加广阔。椭圆曲线资源极丰富， 在一个有限域上可以有非常多的曲线适合建立密码系统，由群论中的拉格朗日定 理可知，有限域f 口仅有有限的几个乘法子群，但有数量级为g 的椭圆曲线的同构 类从这点而言，椭圆曲线在安全性保障和发展前景上比其它系统更有优势。 其次，e c d l p 安全性最高。因为求解e c d l p 比其他两类问题困难的多。求 解e c d l p 已知最好的算法是p o l l a r d ，sr h o 算法【1 1 ，期望运行的时间为0 5 磊， 其中雄* p 。运行的时间与p 的规模成指数关系；而对于d l p 已知的最好算法数 域筛选法( n f s ) ，具有亚指数的运行时间，其时间复杂度为亚指数表达式 e x p ( c ( 1 0 9 p ) v s ( 1 0 9 l o g p ) 印、。 据2 0 0 3 年的报道【2 】，用数域筛选法( n f s ) 分解的最大的r s a 模是5 3 0 b i t s ( 1 6 0 位十进制) ；用数域筛选法( n f s ) 解决的最大d l p 实例是3 9 7 b i t s 素数p ( 1 2 0 位十进制数) ；用p o l l a r d sr h o 算法求解的最大e c d l p 实例是1 0 9b i t s 素数域上 的一个椭圆曲线离散对数问题。 再次，若在相同安全级别下，基于e c d l p 的公钥系统要比其它公钥系统的 密钥长度都要短。 n i s t 0 0 ，【b l a k e 0 3 给出在相同安全级别下，e c c 与r s a 密钥 长度对照表1 3 1 ，如表1 1 ： 表卜l 几种公钥密码系统相应的密钥长度 r s a 密钥长度( b i t s ) 1 0 2 42 0 4 83 0 7 27 6 8 01 5 3 6 0 e c c 密钥长度素数域1 9 22 2 42 5 6 3 8 45 2 1 ( b i t s ) 二元域 1 6 32 3 32 8 34 0 85 7 1 西北大学硕士学位论文 第一章绪论 目前，广泛使用的还是5 1 2 b i t s 与1 0 2 4 b i t s 的r s a 数字签名算法。r s a 密码系 统己越来越不适应设备小型化、带宽受限及高安全性的需要。一方面小型化不允 许大运算量，另一方面高安全性必然要长密钥。2 0 0 3 年1 2 月3 日，r s a 一5 7 6 ( 相当 于1 7 4 位十进制) 被j f r a n k e 宣布攻破【4 】。为达到对称密钥1 2 8 b i t s 的安全水平， n i s t 推荐3 0 7 2 b i t s 的r s a 密钥长度。所以发展密钥相对较短的椭圆曲线密码体制 就显得非常必要。 总之，椭圆曲线密码系统( e c c ) 是迄今为止每比特具有最高安全强度的密码 系统，1 6 0 位e c c 密钥的安全性能与1 0 2 4 位r s a 或e i g a m a l s 的密钥相当。与其他公 钥密码系统相比，椭圆曲线密码系统除了安全性高外，还具有计算负载小，密码 尺寸短，占用带宽少等优点。基于e c c 的密码系统具有广阔的发展前景，必将成 为新一代信息安全技术的主流，尤其对智能卡、p c 卡及无线设备等实时性或计 算量受限的情况。 几个国际标准化组织已经把基于e c c 的数字签名作为新的信息安全标准1 2 1 1 5 1 ， 如i e e ep 1 3 6 3 ，a n s ix 9 6 2 等草案标准。又如s e t ( s e c u r ee l e c t r o n i c t r a n s a c t i o n ) 安全电子事务协议，作为开放的加密与安全的规范，用于保护 i n t e r n e t 上的信用卡事务。该协议的制定者己把基于e c c 的数字签名作为下一代 协议中缺省的公钥密码算法。 深入研究基于椭圆曲线离散对数问题的数字签名具有很大的现实意义。 1 3 椭圆曲线数字签名的研究背景及现状 椭圆曲线是代数几何的重要分支，对椭圆曲线进行的纯数学研究已经进行了 1 0 0 多年，并且取得了丰硕的成果。椭圆曲线被应用到密码学中是v i c t o r m i l l e r 和n e a lk o b l i t z1 9 8 5 年提出的。椭圆曲线密码具有安全性高、密钥量小、灵活 性好的特点。但是，从另一个方面来看，在学术界，目前对椭圆曲线密码体制的 分析结果并不丰富，还并没有一个成熟定性的结论，也没有一个完整的标准出台。 这可从正反两个方面来理解：这种密码体制确实很强，或是，这种密码体制尚未 被很好的认谚 【6 】m 。不管从哪个方面来看，椭圆曲线密码还需进一步的深入研究。 1 9 9 7 年以来，椭圆曲线密码体制及其安全性分析引起了密码学家和各界的 极大关注与重视。有关各界，包括学校( 如r o y a lh o l l o w a yc o l l e g e ) 、商业组 西北大学硕士学位论文第一章绪论 织( 如c e r t i c o m ) 及政府组织( 如美国国家安全局) 已从各个方面探索椭圆曲线密 码技术。i e e e 标准p 1 3 6 3 d 8 和p 1 3 6 3 d 9 对椭圆曲线密码体制做了较以前更为 详尽的讨论。美国国家标准局授权的金融业标准委员会的x 9 正在制订椭圆曲线 数字签名标准x 9 6 2 和密钥协议及传递标准x 9 6 3 。r s a 实验室也己开始着手制 订编号为p k c s # 1 3 的椭圆曲线密码标准。1 9 9 7 年底，w a t e r l o o 大学组织了一个 专门的学术会议，研究椭圆曲线离散对数问题，众多著名密码学家及数学家参加 会议。但直到现在，在密码分析方面仍未取得实质性进展。 目前，在e c c 方面已经有相当多的成果。例如，e c c 与其它公钥密码安全强 度对照、几种攻击算法与对抗攻击的方法【l 】【2 】、椭圆曲线点的不同坐标表示与运 算的关系嘲【9 】。其中大量的是关于e c c i g 算的各种算法的研究 2 1 ，围绕椭圆曲线 ( 尤其是特殊椭圆曲线) 点乘运算的快速算法有很多突出的成果( 如计算点乘的 窗 3 n a f 法、滑动窗口法、m o n t g o m e r y 点乘、固定窗口法等快速算法) 【1 】1 2 】，还 有点乘快速算法的硬件实现等。上述研究大多基于二元域g f ( 2 m ) 上的特殊曲 线，如s o l i n a s 在k o b l i t z 曲线上的点乘算法有重大突破，大大缩短了执行时间， 优于其它算法【。 基于椭圆曲线的数字签名的研究从它诞生起就显示了很强大的生命力。椭圆 曲线密码的理论还有很多没有解决的问题，将来关于椭圆曲线密码方面主要有这 样一些研究内容：椭圆曲线密码理论分析、椭圆曲线的编码理论和方法的研究， 这是现在的难点；椭圆曲线运算快速实现问题等算法研究、椭圆曲线密码的应用 研究、软硬件系统开发等一系列问题。 1 4 基于椭圆曲线的数字签名的最新进展 数字签名是互联网和电子商务的核心技术之一。如今，普遍使用的仍然是 基于r s a 的数字签名系统。基于e c c 的数字签名的研究随着椭圆曲线理论的发展而 发展。围绕椭圆曲线数字签名有各种各样的研究。国际上的一些研究机构如 w a t e r l o o 大学等在这一领域处于领先地位，最近的研究包括：特殊曲线的快速算 法、各种攻击与抗攻击算法等t 2 】；也有面向各种具体应用的基于e c c 的数字签名 l l l 】【1 2 】1 1 3 1 的研究。国内在这方面也有一些研究，大多集中在二元域的快速算法， 也有e c d s a 的硬件v l s i 设计【1 4 1 ，基于f p g a 的签名芯片的开剔1 5 l ；集签名、认证、 西北大学硕士学位论文第一章绪论 加密等功能为一体的安全智能卡 在数字签名系统中被广泛应用的h a s h 函数被我国数学家破解。山东大学王小 云教授带领的研究小组于2 0 0 4 、2 0 0 5 年先后破解了m d 5 、s h a 1 两个h a s h 函数 1 6 j ，被公认为国际密码学界最出色的成果之一。m d 5 的设计者r i v e s t 评论到：“数 字签名的安全性在降低，这再一次提醒要替换算法”。可以说m d 5 、s h a 1 的破解动摇了数字签名的理论根基，设计新的h a s h 函数算法对数字签名系统的 安全性极为重要。 1 5 本论文的主要研究工作 1 、在现有e c d s a 标准下，研究一种适用于实时性较高情况下的安全高效 的数字签名方案； 2 、以对文本文件数字签名为例，进行m a t l a b 实验仿真，以验证论文给 出方案的执行效率； 3 、研究一种将信息明文准确地编码嵌入椭圆曲线的有效方法，这是实现椭 圆曲线密码的基础。 西北大学硕士学位论文第二章椭圆曲线密码 第二章椭圆曲线密码 椭圆曲线密码( e c c ) 的数学基础是椭圆曲线离散对数问题( e c d l p ) 的难 解性。它是公钥密码系统中安全强度最高、同等安全性下密钥最短的密码体系。 随着密码学的不断发展，e c c 势必代替r s a 、d s a 等流行的密码体制而成为公 钥密码发展的主流。 本章将介绍椭圆曲线密码的有关问题。 2 1 公钥密码系统 密码技术分为私钥密码( 即对称密码、单钥密码) 和公钥密码( 即非对称密 码、双钥密码) 。私钥密码的加密密钥和解密密钥相同或可从一个密钥推出另一 个密钥，系统的保密性主要取决于密钥的安全性；公钥密码每个用户都有一对选 定的密钥：一个私钥( 保密) ，一个公钥( 公开) 。公钥密码可以实现多个用户 加密一个用户解读，也可实现一个用户加密多个用户解读。前者可用于公共网络 中实现保密通信，后者可用于认证系统中的数字签名。 公钥密码系统一般有三类：基于大整数分解问题( i f p ) 的系统，如r s a ； 基于离散对数问题( d l p ) 的系统，如著名的e i g a m a l ，d s a 等；基于椭圆曲线 离散对数问题( e c d l p ) 的系统，如1 e e ep 1 3 6 3 标准规定的e c d s a 等。 本节将对这三类公钥密码系统中具有代表性的密码体制作简单介绍。 2 1 1 枞密码体镧 r s a 是1 9 7 7 年由r i v e s - t s h a m i r a d l e m a n 实现的公钥密码系统，其安全性基于 大整数因子分解问题( i f p ) ，可用于保密和数字签名上。具体算法”a l s i 如下： ( 1 ) 随机地选择两个大素数p 和g ，且保密； ( 2 ) 计算，= 朋，n 公开； ( 3 ) 计算( 一) = ( p 一1 x q 一1 ) ，妒( 功是数论中的欧拉( e u l e r ) 函数，且保密； ( 4 ) 随机地选择一个正整数p ，1 p ( ，1 ) ，( f ，( 疗”= 1 ，公开p ； ( 5 ) 根据e d = l m o d 妒( n ) 求出d ，并保密； ( 6 ) 加密运算：c = m m o d p 西北大学硕士学位论文 第二章椭圆曲线密码 ( 7 ) 解密运算：m = c 4 m o d n 因为y a = ( r ，= x 出= 砌卜1 - - - - - - x z 州”= x 1 = x ( m o d 帕。 理论上，r s a 密码算法的安全性取决于大整数1 1 因子分解的困难性。随着大 整数分解方法、计算机速度等的发展，安全级别足够大的n 至少应取1 0 2 4 位， 最好取2 0 4 8 位。 2 1 2e i g 嘲i 密码体制 e i g a m a l 公钥密码体制是t e l g a m a l 于1 9 8 4 年提出的，在许多协议中被广 泛使用。其安全性基于离散对数问题的困难性。具体算法【1 7 1 8 1 如下： ( 1 ) 随机地选择一个大素数p ，且要求p 一1 有大素数因子。再选择一个模 p 的本原元口，将p 和口公开。 ( 2 ) 密钥生成：用户随机地选择一个整数d 作为自己私钥，1 d p 一2 ， 计算y ；m o d p ，y 为自己的公钥。由y 求解d ，必须求解离散对数，是极困难 的。 ( 3 ) 加密：设消息为m ，随机地选择一个整数k ，l k p 一2 ， 计算c l - - - - o ! m o d p ，c 2 = m y m o d p ，取( c 1 c 2 ) 作为密文。 ( 4 ) 解密：对密文( g ，c x ) ，计算v = c 1 4 m o d p ，所= c y - 1 m o d p 由于e i g a m a l 密码的安全性建立在有限域f 。离散对数的困难性之上，而目 前尚无求解有限域离散对数的有效算法，所以在p 足够大( 1 5 0 位以上) 时 e i g a m a l 密码是安全的，而且p l 应有大素因子。 2 1 3 椭圆曲线密码( e ) 椭圆曲线密码( e c c ) 是建立在有限域l 上的椭圆曲线的点所构成的阿贝 尔群上。椭圆曲线密码系统的安全性是基于椭圆曲线离散对数问题( e c d l p ) 的难解性，如第一章所述，在三类公钥密码系统中以椭圆曲线密码系统的安全性 最好，且密钥长度最短、签名短，软件实现规模小、硬件实现电路省电。 椭圆曲线公钥密码系统是当前代替r s a 公钥密码系统的最佳选择。因为要 达到1 0 2 4 位的r s a 安全水平，椭圆曲线密码只要1 6 3 位数上的运算。虽然椭 圆曲线运算比素数域的模运算要复杂，但是运算中所用密钥却短得多。而且，椭 西北大学硕士学位论文 第二章椭圆曲线密码 圆曲线群的特点是对同样的基域可以选择不同的椭圆曲线【r 丌，安全性可得到进一 步的保障。 正因为如此，一些国际标准化组织已把椭圆曲线密码作为新的信息安全标 准，如i e e ep 1 3 6 3 d 4 ，a n s if 9 6 2 ，a n s if 9 6 3 等标准，分别规范了椭圆曲线密 码在i n t e m e t 安全协议、电子商务、w 曲服务器、空间通信、移动通信、智能卡等 方面的应用。 作为论文研究课题，有关椭圆曲线密码的详细讨论将在2 4 节中进行。 2 2 群和域 由于椭圆曲线密码系统是建立有限域f 。上的椭圆曲线的点所构成的加法阿 贝尔群之上，在此简要介绍一下代数学中群和域的基本概念。 2 2 科嘲 群是一个代数系统，它由定义了一个二元运算的非空集合g 组成，并满足 封闭性、结合律、单位元和逆元。记作 交换群：如果 还满足交换律，则称其为交换群( 或阿贝尔群) 。 有限群：如果集合g 中只有有限多个元素，则称该群 为有限群。g 中 元素个数称为群的阶。 循环群：设 是一个群，如果群g 中存在一个元素a ，对群g 任意元素b 都存在一个整数i ，使得b _ a i ，则称g 是一个循环群，元素a 称g 的一个生成元。 循环群是交换群，循环群的子群也是交换群。 循环群 ，a 为g 的生成元，1 为g 的单位元，g 的阶为1 3 ，则酽= 1 2 2 2 埘1 9 1 1 2 1 域：是由一个集合f 和两种运算( 加+ ，乘) 组成的代数系统，并满足 ( 1 ) ( f ，+ ) 对加法运算构成加法交换群，单位元0 ； ( 2 ) ( f 、 o ) ，) 对乘法运算构成乘法交换群，单位元1 ： ( 3 ) 对所有f 域元素分配律成立，即( 口+ 6 弦= a c + b c 。 有限域：若f 为有限集合，则该域为有限域。有限域的全体非零元素构成一 个乘法循环群。 8 西北大学硕士学位论文第二章椭圆曲线密码 素域：设p 是一个素数，以p 为模，则模p 的全体余数的集合 o ，l ，2 ，p 一1 关于模p 的加法和乘法构成一个p 阶有限域，用符号l 表示。 域运算：一个域f 有两种运算，即加法和乘法。域元素的减法用加法来定义： 对于a , b f ，a b = 口+ ( 6 ) ，其中- 6 为使得6 + ( 一6 ) = 0 的唯一的一个域元素。类 似地，域元素的除法用乘法来定义：对于a , b f ，b 0 ，a b = 口b 一，其中b - 1 是b 的逆元素，它是使得b b = 1 的唯一的一个域元素。 2 2 3 素域算术 文献【2 1 给出一种特别适合软件实现的素域f 。的算术运算算法。 ( 1 ) 域元素表示法： 假设实现平台的字长为w 位，w 是8 的整数倍。w 位的字各位依次编号为0 到1 ，一l ，最右边的位是第0 位。 素域l 的元素为从。到p - 1 的整数。令所= 1 0 9 ：p 是p 的二进制长度， t = r 叫矿 是表示该域元素所用的w 位字的个数。 如图2 1 ，表示一个域元素a 以二进制的形式存储在一个由t 个w 位字组成的 数组a = ( 彳【f l 】，【2 】，a p ，彳【o 】) 中，其中最右边的a o 】是最低有效位。 图2 - 1 将域f 。的元素a 表示为w 位字的数组a ( 2 ) 算法： 素域f ，的算术运算算法为模p 运算，包括：域元素表示法、域f ，上的加法、 减法、乘法、平方、约减、求逆等算法，具体算法描述详见文献【阍。特别地， 当素数p 具有特殊形式时，其约减运算速度大大提高，如：n i s t 素数。 数字签名方案中的运算主要是模运算，模运算满足交换律、结合律和分配律， 并遵循按模计算原理。 按模计算原则：令a ，b ，n 为整数，o p 代表+ 、一，运算符，则有刚 ( a o p b ) m o d n = ( ( a m o d n ) o p ( b m o d n ) ) m o d n 按模计算有效地限制了模运算中间结果的范围。对于2 个k 比特长的数进行模 n 运算，任何加、减、乘的中间结果至多为2 k 比特长。这样将不会产生很大的中 西北大学硕士学位论文 第二章椭圆曲线密码 间结果，便于存储和处理。 ( 3 ) n i s t 素数【2 l 美国f i p s1 8 6 - 2 标准推荐采用5 个素域上的椭圆曲线，这五个素域分别是： p 1 9 2 = 2 1 ”一2 “一1 p 2 2 4 = 2 t m 一2 ”+ l p 2 5 6 = 2 瑚一2 2 2 4 + 2 1 妮+ 2 一l p 3 8 4 = 2 3 “一2 1 嚣一2 + 2 3 2 一l p 5 2 1 = 2 5 ”一l 从上式可见这些素数特性：都可以表示成少量的2 的幂或差，并且2 的幂( 除p 5 2 1 外) 都是3 2 的倍数。这使得在字长3 2 位的机器上约减算法的计算特别快。 例：p 1 9 2 = 2 1 ”一2 “一1 令c 是一个o c p 2 的整数，其2 “进制表示式( 其中q 【o ，2 “- 1 ) 为 c = c 5 2 3 + c 4 2 2 撕+ g 2 1 9 2 + c 2 2 1 嚣+ q 2 “+ 岛 则可以利用以下同余式约减上式中的2 的高次幂项： 2 1 ”= 2 “+ l ( m o d p 、 2 2 5 6 = 2 嚣+ 2 “( r o o d 力 2 ；2 0 = 2 “+ 2 “+ l ( m o d p l 于是得至0 f = c 5 ( 2 1 2 。+ 2 “+ 1 ) + c ( 2 1 嚣+ 2 “) + c 3 ( 2 h + 1 ) + ( c 2 2 1 嚣+ q 2 6 + e 0 x m o a p ) 通过4 次1 9 2 位整数相加，并重复地减p ，直到小于p 为止，便可得到c m o d p 。 以1 9 2 位素数为例，给出模素数域模p 1 9 2 - - 2 ”一2 “一1 的快速约减算法的描 述。 输入： c = ( 白，q ，c 3 ，巳，q ，c o ) 为2 “进制整数，o ， 其中，p 为大于3 的素数，确定了有限域f p ；元素a , b f p ，确定了椭 圆曲线；g 为椭圆曲线上的一个基点，该基点的阶为素数玑设椭圆曲线群e ( l ) 的阶为n ，i l j h = ，疗称为余因子。 随机地选择一个整数d 作为用户私钥，d o ，1 ，2 一1 1 1 ； 用户公钥q = d g 。 ( 2 ) 加密：( 用公钥) 将明文m 编码表示为椭圆曲线( f 。) 上的一点肘； 选择七 o ，1 2 n - i ，计算c l = k g ；计算c 2 = m + k q ； 密文为( c l ，c 2 ) ( 3 ) 解密：( 用私钥) 。 计算m = c 2 一娲，( 因为a c , = d ( k g ) = 七( 据) = 尥，即著名的椭圆曲线 的d i f f i e - h e l l m a n 密钥交换问题) 。 从点m 解码恢复出明文m 。 2 4 3 椭圆曲线密码( e g g ) 体制的特点【捌 ( 1 ) 在安全性相当的前提下，e c c 可使用较短的密钥。一般认为有限域勋上 的椭圆曲线密码体制，当p 的长度为1 6 0 b i t 时，其安全性相当于1 0 2 4 b i t 的r s a 密码。适合存储空间及处理能力受限制的小型设备，如智能卡，手持遥控设备等。 ( 2 ) e c c 建立在椭圆曲线离散对数问题的数学难题之上。椭圆曲线离散对 数问题不存在亚指数时间攻击算法，安全性很高；并且，椭圆曲线资源丰富，同 一个有限域上存在着大量不同的椭圆曲线，这为安全性增加了额外的保证。 西北大学硕士学位论文 第二章椭圆曲线密码 ( 3 ) 执行速度方面，由于椭圆曲线上的一次群运算最终化为域上的不超过 1 5 次乘法运算，因而便于实现。虽然目前难以对椭圆曲线密码体制与现存密码 体制，如：r s a 、d s a 等作出准确的定量比较，粗略地说，椭圆曲线密码体制 较对应的离散对数体制要快，c e t t i e o m 公司对e c c 和r s a 进行了比较，以4 0 m h z 的钟频实现1 5 5 b i t s 的e c c ，每秒可完成4 0 0 0 0 次椭圆曲线运算，其速度比d s a 和r s a 快l o 倍。】 ( 4 ) 安全性显然是任何密码体制的必备条件，椭圆曲线密码体制的安全性分 析因而也引起了各国密码学家及有关部门的关注与重视，但成果并不丰硕。也许 这可视为椭圆曲线密码体制具有高强度的一种证据。 2 5 椭圆曲线密码的实现技术 实现椭圆曲线密码的一个关键环节是椭圆曲线参数的产生，本节将阐述椭圆 曲线参数的产生问题。 2 - 5 1 椭圆曲线的阶 有限域f p 上的椭圆曲线e ( f 。) 的阶( 即该椭圆曲线上的点构成的阿贝尔群 的阶) 等于该椭圆曲线上点的数目，用表示。根据h a s s e 定理： i 一，一l i 描述一个椭圆曲线e 及其所在的有限域 f p ，基点g 及其阶一。参数的选择要使的e c d l p 抵抗所有已知的攻击，另外还 要考虑实现的问题。 一条良好的适于构建密码体制的有限域上的椭圆曲线应当满足下面的安全 性约束f 2 l ： ( 1 ) 抵抗p o h l i g h e l l m a n 和p o l l a r d sr h o 攻击。椭圆曲线e 上的有理点数( 即椭 圆曲线的阶) 群e ( f ，) = n 必须能够被足够大的素数一整除( n 2 ) ，并且 撑以f 。) 应为素数或近似素数，群e ( f p ) = n h ，其中甩为素数，h 非常小( = 1 ，2 ，3 ) 。 ( 2 ) 抵抗同构攻击。为避免攻击素域异常曲线，应保证撑e ( f 。) p ；为避免 w e f t 和t a t e 配对攻击，应该保证对于所有的l s 七c ，行不被q 一1 整除，其中c 应足够大，使e 。上的d l p 不可解( 若一 2 ”，则c = 2 0 就足够) 。 椭圆曲线的产生问题是一个十分复杂的问题，目前主要有两类产生方法，随 机法产生椭圆曲线和构造法产生椭圆曲线。为防止针对特殊类型椭圆曲线的攻 击，最好选择随机产生法。因为随机曲线满足已知的同构攻击的条件的概率非常 小且可忽略。 在满足安全性要求的基础上，在实际应用中还要考虑实现问题。是否能够快 速有效的产生安全的椭圆曲线是决定椭圆曲线密码体制在实际应用中是否有生 命力的关键性问题。文献1 2 1 给出源于a n s ix 9 6 2 标准的在素域随机产生椭 圆曲线的算法，该算法安全性很高，同时实现也较复杂。 在论文设计的椭圆曲线数字签名方案中，考虑到实现效率等问题，将使用本 节最后( 2 5 5 ) 确定出的算法来产生椭圆曲线的参数组t p ，a ，b , g ，t i ，h 。 2 5 4 椭圆曲线上基点的选择 西北大学硕士学位论文第二章椭圆曲线密码 e c c 参数选择中，在确定了安全的椭圆曲线y 2 = ，+ a r + b ( m o d p ) 之后，基 点g 的选择也是非常重要的。安全