（计算机应用技术专业论文）椭圆曲线身份认证机制在无线环境中的研究与应用.pdf

东北大学硕士学位论文 椭圆曲线身份认证机制在无线环境中的研究与应用 摘要 认证技术是信息安全理论与技术的一个重要方面，而身份认证是安全系统中 的第一道屏障，因此在安全领域中占着举足轻重的地位，而在安全性要求较高的 电子商务领域中尤为重要，目 前电子商务领域中均使用以证书为基础的公钥密码 系统来解决相关的安全问题。但是由于无线环境与有线环境之间存在着不可忽略 的差异，如:较小的带宽、传输时有较大延迟、易断线、移动设备存储能力较低 以及电力不足等，因此有线环境中的诸多安全体制是不适应于无线环境的，发展 适合于无线环境的身份认证体制是十分有必要的。 本文首先介绍了与论题密切相关椭圆曲线密码体制，然后就目前典型的身份 认证算法和协议及其在无线环境中的应用进行了详细分析，最后结合椭圆曲线密 码体制与自 我验证的身份认证公钥密码系统， 建立了一个基于g f ( 2 - ) 域椭圆曲 线 的自 我验证身份认证方案。此方案具有如下主要优点: ( 1 ) 本方案选用基于g f ( 2 ) 域上的椭圆曲 线作为密码学基础，因 此具有椭圆 曲线密码系统密钥较短、运算效率较高的优点，这非常适合于无线环境; ( 2 ) 采用自 我验证的身份认证体制，不使用证书就可以 验证公钥的 有效性， 减 少了验证证书的操作，节省了计算时间; ( 3 ) 由 于不使用证书，因此认证中心不必费时费力去维护证书目 录， 减少了认 证中心的操作; ( 4 ) 在身 份认证的 过程中 可同时 进行了 公钥有 效性验证。 文中还刘密码系统中出现频率最高的数乘运算进行了研究，并讨论了一些改 进方法从而提高程序的运行效率。通过对此方案安全性与复杂度的分析可知，此 方案可有效减小密钥大小和运算复杂度、降低传输成本，因此非常适用于无线环 境中。 关键词椭圆曲线密码体制 身份认证 自 我验证公钥密码系统 无线环境 东北大学 硕士学位论文 abs t ract r e s e a r c h a n d a p p l i c a t i o n o f i d e n t i t y a u t h e n t i c a t i o n s y s t e m b a s e d o n e l l i p t i c c u r v e i n wi r e l e s s e n v i r o n me n t ab s t r a c t a u t h e n t i c a t i o n t e c h n o l o g y i s a n i m p o r t a n t a s p e c t o f t h e i n f o r m a t i o n s e c u r i t y t h e o r y a n d t e c h n o l o g y , a n d t h e i d e n t i t y a u t h e n t i c a t i o n i s t h e f i r s t b a r r i e r o f s e c u r i t y s y s t e m , t h e r e f o r e i t i s o f v i t a l i m p o r t a n c e i n s e c u r i t y s y s t e m , p a r t i c u l a r l y in t h e a r e a o f e - c o m m e r c e w h i c h r e q u ir e s h i g h e r s e c u r i t y . a t p r e s e n t , a l l o f e l e c t r o n i c c o m m e r c e a c t i v i t i e s o n t h e i n t e r n e t e m p l o y t h e c e r t i f i c a t e - b a s e d p u b l i c k e y c r y p t o s y s t e m t o s o l v e t h e i r r e l a t e d s e c u r i t y i s s u e s . h o w e v e r , d u e t o t h e n o t i c e a b l e d i f f e r e n c e b e t w e e n w i r e l e s s e n v i r o n m e n t a n d c o n v e n t i o n a l l i n e a t e e n v i r o n m e n t , f o r i n s t a n c e , t h e r e l a t i v e l y n a r r o w n e t w o r k b a n d w i d t h , t h e g r e a t e r t r a n s m i s s i o n d e l a y t i m e , t h e u n s t a b l e n e t w o r k , t h e l o w e r m e m o ry c a p a c i t y a n d e l e c t r o n i c p o w e r , e t c . a s a r e s u l t m a n y s e c u r i t y s y s t e m i n l i n e a t e e n v i r o n m e n t a r e n o t s u i t a b l e f o r w i r e l e s s e n v i r o n m e n t , i t i s v e r y e s s e n t i a l t o d e v e l o p a k i n d o f i d e n t i t y a u t h e n t i c a t i o n s y s t e m s u i t f o r w i r e l e s s e n v ir o n m e n t . f i r s t l y w e i n t r o d u c e e l l i p ti c c u r v e c r y p t o s y s t e m c l o s e l y r e l a t e d t o t h e t h e s i s , t h e n m a k e a d e t a i l e d a n a l y s i s c o n c e r n i n g a l g o r i t h m s a n d p r o t o c o l s a b o u t i d e n t i t y a u t h e n t i c a t i o n a n d a p p l i c a t i o n i n w i r e l e s s e n v i r o n me n t , f in a l l y d e v e l o p a s e l f - c e r t i f i e d i d e n t i t y a u t h e n t i c a t i o n s y s t e m b a s e d o n e l l i p t i c c u r v e o v e r f i n i t e f i e l d f 2 , c o m b i n i n g e l l i p t i c c u r v e c r y p t o s y s t e m a n d s e l f - c e rt i f i e d p u b l i c k e y c r y p t o s y s t e m. t h e p r o j e c t h a s t h e f o l l o w i n g a d v a n t a g e s : ( l ) o w i n g t o b a s e d o n e l l i p t i c c u r v e o v e r f i n i t e f i e l d f z , t h e p r o j e c t h a s t h e f o l l o w i n g a d v a n t a g e s : t h e s h o rt e r k e y l e n g t h a n d t h e h i g h e r e f f i c i e n c y , a n d w h i c h i s v e r y s u i t f o r w ir e l e s s e n v i r o n m e n t ; ( 2 ) a d o p t i n g s e l f - c e rt i f i e d p u b l i c k e y c r y p t o s y s t e m s a n d v e r i f y i n g t h e v a l i d i t y o f p u b l i c k e y w i t h o u t c e r t i f i c a t i o n , a n d t h a t c a n r e d u c e t h e o p e r a t i o n o f v a l i d a t i n g c e rt i f i c a t i o n a n d t h e a m o u n t o f c o m p u t a t i o n ; ( 3 ) o w i n g t o n o n e e d o f c e rt i f i c a t i o n , t h e c e r t i f i c a t i o n a u t h o r i t y n e e d n o t s p e n d m o r e t i m e t o m a n a g e t h e c a t a l o g o f c e rt i f i c a t i o n , s o r e d u c e th e o p e r a t i o n o f c a ; ( 4 ) b o t h v e r i f y i n g t h e v a l i d i t y o f p u b l i c k e y a n d i d e n t i t y a u t h e n t i c a t io n c a n b e c o n c u r r e n t l y a c h i e v e d . we a l s o h a v e s t u d i e d s c a l a r m u l t i p l i c a t i o n a l g o r i t h m w h i c h a p p e a r c o n t i n u a l l y i n t h i s s y s t e m a n d p r o p o s e d s o m e m e a s u r e s切 i m p r o v e t h e r u n n i n g e f f i c i e n c y o f t h e p r o g r a m . b a s e d o n t h e a n a ly s i s o f s e c u r i t y a n d c o m p l e x i t y o f s y s t e m , w e b e l i e v e t h a t t h e p r o j e c t c a n e ff e c t i v e l y r e d u c e t h e l e n g t h o f k e y , c o m p l e x it y o f c o m p u t a t i o n a n d t h e c o s t o # t r a n s m i s s i o n , a n d t h a t i s v e ry s u i t f o r m o b i l e e q u i p m e n t a n d w i r e l e s s i i i 东北大学硕士学位论文 里巨目口.里口旦里旦旦 旦 巴皿旦 旦 e n v i r o n me n t . abs tract k e y w o r d s e l l i p t i c c u r v e c r y p t o s y s t e m , i d e n t i t y a u t h e n t i c a t i o n , s e l f - c e r t i f i e d p u b l i c k e y c r y p t o s y s t e m s , w i r e l e s s e n v i r o n m e n t i v 东北大学硕士学位论文 声明 独创性声明 本人声明所呈交的学位论文是在导师的指导下 完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示m意。 学 位 论 文 作 者 签 名 : 羡 内 夔 ， 日期: 2 o 0 s . l . i b 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定:即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如 作者 和导 师同 意网上 交 流， 请 在下 方签 名; 否 则 视为 不n 意 . ) 学位论文作者签名: 签字日期:t o o l. 导师签名 签字 日期 : 尺 帅 ; ， 夕 翻 了 、2 、 东 北大学硕士学位论文 第一章 绪 论 第一章 绪论 1 . 1研究背景与主要问题 随着网络技术的迅猛发展，人们的通讯也从有线发展到无线的传输方式，而 移动通信与电 子商务的结合，更是引发了2 1 世纪移动电子商务的风潮。如今，儿 乎每个人都随身携带着一个移动设备，如手机、p d a等。信息产业的不断发展， 也使人们手中的移动设备所提供的服务越来越多样化，然而其中的安全问题也越 来越突出。移动设备由于地域、设备的限制，其通讯效果往往不是很理想，尤其 是在通讯带宽不足的条件下将大大影响传输效果。此外，它还具有存储容量较小、 计算速度较慢、传输时出现较大延迟等特点，因此，有线环境中的很多机制都不 适用于无线环境，研究无线环境下的安全且有效的机制是刻不容缓的。而作为安 全系统中的第一道关卡，身份认证机制在安全性要求比较高的电子商务系统中尤 为显得重要。 目 前所身份认证安全机制基本上都是基于美国m i t 三位学者所提出的r s a 算 法f i l l 。 但是， 先进的 椭圆曲 线公钥密码体制 ( e c c ) 现在己 经得到了 世界上广泛的 认 可。 许多国际标准化组织( 政府、工业界、 金融界、商业界等) 己 将各种椭圆曲 线密 码体制作为其标准化文件向全球颁布。椭圆曲线密码体制以其密钥长度较短、运 算效率较高等优点逐步占领了移动通信的安全领域阵地。目 前广泛适用于无线环 境的 是w a p ( w i r e l e s s a p p l i c a t i o n p r o t o c o l ) 。 这是一种开放式的 标准无线协议， 其 中的 无线安全传输层wt l s 为无线通讯提供了安全保证。wt l s 是由s s l 协议发 展而来的，其中的身分认证与 s s l一样都是基于证书的方式，即当网络上的两个 用户想要进行通信时，必须先互相验证对方的身份，他们验证对方身份是通过一 个可信任的第三方所发放的身份证明来实现的，这个证明就是数字证书。而这个 可信任第三方，也就是认 证中心( c e r t i f i c a t e a u t h o ri t y , c a ) 负责用户证书及密钥的 管理工作。认证中心之间还可能存在着阶层关系，用户验证证书时就需要逐层验 证。如此繁琐的工作将大大增加系统的计算时间，降低通讯效率，因此，寻找 - 种高效、可靠、简便的认证体制是十分有必要的。 木文通过研究椭圆曲线密码体制的特点，结合自 我验证的公钥密码系统，设 计了一种适用于无线环境的身份认证方案。自我验证的公钥密码系统与基于证书 的公钥密码系统不同，其不需要证书即可验证公钥的有效性及用户的身份，还可 达到与基于证书的公钥密码系统相同的安全等级甚至更高。我希望通过这个方案， 东 北大学硕士学位论文 第一章 绪 论 第一章 绪论 1 . 1研究背景与主要问题 随着网络技术的迅猛发展，人们的通讯也从有线发展到无线的传输方式，而 移动通信与电 子商务的结合，更是引发了2 1 世纪移动电子商务的风潮。如今，儿 乎每个人都随身携带着一个移动设备，如手机、p d a等。信息产业的不断发展， 也使人们手中的移动设备所提供的服务越来越多样化，然而其中的安全问题也越 来越突出。移动设备由于地域、设备的限制，其通讯效果往往不是很理想，尤其 是在通讯带宽不足的条件下将大大影响传输效果。此外，它还具有存储容量较小、 计算速度较慢、传输时出现较大延迟等特点，因此，有线环境中的很多机制都不 适用于无线环境，研究无线环境下的安全且有效的机制是刻不容缓的。而作为安 全系统中的第一道关卡，身份认证机制在安全性要求比较高的电子商务系统中尤 为显得重要。 目 前所身份认证安全机制基本上都是基于美国m i t 三位学者所提出的r s a 算 法f i l l 。 但是， 先进的 椭圆曲 线公钥密码体制 ( e c c ) 现在己 经得到了 世界上广泛的 认 可。 许多国际标准化组织( 政府、工业界、 金融界、商业界等) 己 将各种椭圆曲 线密 码体制作为其标准化文件向全球颁布。椭圆曲线密码体制以其密钥长度较短、运 算效率较高等优点逐步占领了移动通信的安全领域阵地。目 前广泛适用于无线环 境的 是w a p ( w i r e l e s s a p p l i c a t i o n p r o t o c o l ) 。 这是一种开放式的 标准无线协议， 其 中的 无线安全传输层wt l s 为无线通讯提供了安全保证。wt l s 是由s s l 协议发 展而来的，其中的身分认证与 s s l一样都是基于证书的方式，即当网络上的两个 用户想要进行通信时，必须先互相验证对方的身份，他们验证对方身份是通过一 个可信任的第三方所发放的身份证明来实现的，这个证明就是数字证书。而这个 可信任第三方，也就是认 证中心( c e r t i f i c a t e a u t h o ri t y , c a ) 负责用户证书及密钥的 管理工作。认证中心之间还可能存在着阶层关系，用户验证证书时就需要逐层验 证。如此繁琐的工作将大大增加系统的计算时间，降低通讯效率，因此，寻找 - 种高效、可靠、简便的认证体制是十分有必要的。 木文通过研究椭圆曲线密码体制的特点，结合自 我验证的公钥密码系统，设 计了一种适用于无线环境的身份认证方案。自我验证的公钥密码系统与基于证书 的公钥密码系统不同，其不需要证书即可验证公钥的有效性及用户的身份，还可 达到与基于证书的公钥密码系统相同的安全等级甚至更高。我希望通过这个方案， 能大大提高无线环境下身份认证的效率。 1 . 2椭圆曲线密码体制的优点 建立在椭圆曲线理论上的椭圆曲线密码系统是一种比较新颖的密码技术，也 是当今密码学领域最热门的课题。椭圆曲线理论是代数几何，数论等多个数学分 支的 一个交叉点，1 9 8 5 年由n e a l k o b l i t z h 和v i c t o r m i l l e r l t $ 将椭圆曲 线理论和 密 码学完美结合，提出了 椭圆曲线密码机制。相对于r s a密码机制，建立在椭圆曲 线离都对数问题难解性之上的e c c具有更强的安全性，更高的实现效率，更低的 实现代价。与其它公钥密码体制相比，椭圆曲线密码体制具有以下优点: ( 1 ) 椭圆曲 线密码体制有最强的单比 特安全性。 加拿大的 公司对椭圆曲 线密 码 体制的女全性与r s a和d s a的安全性进行了详细的比较。 表 1 . 1 说明了三者在安 全性方面的关系， 其中一个m i p s 年等于一个计算能力为1 m i p s ( 每秒钟执行1 百 万条指令) 的机器工作一年。 表 1 . 1 r s a / d s a与 f c c密钥长 度比较 f a b l e 1 . 1 t h e c o m p a ri s o n o f k e y l e n g t b b e t w e e n r s a / d s a a n d e c c mi p s 密钥长 度 ( b i t ) r s a / d s a密钥长度 ( b i t ) e c c密钥长度 ( b i t ) r s a / d s a密 钥长度比 1 0 45 1 21 0 65 : 1 1 0 7 6 81 3 26 : 1 l o l l1 0 2 41 6 0 7: 1 l o l l2 0 4 8 21 01 0 : 1 1d21 0 0 0 6 0 03 5 : 1 从表1 . 1 中可以看出每一比特的椭圆曲线密码体制的密钥至少相当于5 比特的 r s a或者d s a密钥的安全性，并且这种比例关系随密钥长度的增加呈上升趋势。 这特点使椭圆曲线密码体制比其它两类体制具有更强的竞争力。它所具有的相 对小的密钥长度使其特别适合于计算能力和集成电 路受限( 如p c卡， s i m卡) 、带 宽受限 ( 如 无线 通信和某些计 算机网 络) 、 要求高 速实 现的 情况。 ( 2 ) 在相同的基域下，椭圆曲 线密码系统具有更多的可选择性。也就是说对给 定的素数，都唯一对应一个r s a算法，但是对于椭圆曲线，改变椭圆曲线方程的 系数就能得到不同的曲线。 ( 3 ) 椭圆曲线密码体制基于椭圆曲 线上求解离散对数问题，它优于基于有限域 的乘法群上的离散对数问题的密码体制。目 前，椭圆曲线离散对数还没有发现亚 指数时间攻击。椭圆曲线密码体制的一个迷人之处在于，基于它的离散对数问题 比一般的基于整数的离散对数问题和整数分解问题更加困难。 更加明确地说， 设e 能大大提高无线环境下身份认证的效率。 1 . 2椭圆曲线密码体制的优点 建立在椭圆曲线理论上的椭圆曲线密码系统是一种比较新颖的密码技术，也 是当今密码学领域最热门的课题。椭圆曲线理论是代数几何，数论等多个数学分 支的 一个交叉点，1 9 8 5 年由n e a l k o b l i t z h 和v i c t o r m i l l e r l t $ 将椭圆曲 线理论和 密 码学完美结合，提出了 椭圆曲线密码机制。相对于r s a密码机制，建立在椭圆曲 线离都对数问题难解性之上的e c c具有更强的安全性，更高的实现效率，更低的 实现代价。与其它公钥密码体制相比，椭圆曲线密码体制具有以下优点: ( 1 ) 椭圆曲 线密码体制有最强的单比 特安全性。 加拿大的 公司对椭圆曲 线密 码 体制的女全性与r s a和d s a的安全性进行了详细的比较。 表 1 . 1 说明了三者在安 全性方面的关系， 其中一个m i p s 年等于一个计算能力为1 m i p s ( 每秒钟执行1 百 万条指令) 的机器工作一年。 表 1 . 1 r s a / d s a与 f c c密钥长 度比较 f a b l e 1 . 1 t h e c o m p a ri s o n o f k e y l e n g t b b e t w e e n r s a / d s a a n d e c c mi p s 密钥长 度 ( b i t ) r s a / d s a密钥长度 ( b i t ) e c c密钥长度 ( b i t ) r s a / d s a密 钥长度比 1 0 45 1 21 0 65 : 1 1 0 7 6 81 3 26 : 1 l o l l1 0 2 41 6 0 7: 1 l o l l2 0 4 8 21 01 0 : 1 1d21 0 0 0 6 0 03 5 : 1 从表1 . 1 中可以看出每一比特的椭圆曲线密码体制的密钥至少相当于5 比特的 r s a或者d s a密钥的安全性，并且这种比例关系随密钥长度的增加呈上升趋势。 这特点使椭圆曲线密码体制比其它两类体制具有更强的竞争力。它所具有的相 对小的密钥长度使其特别适合于计算能力和集成电 路受限( 如p c卡， s i m卡) 、带 宽受限 ( 如 无线 通信和某些计 算机网 络) 、 要求高 速实 现的 情况。 ( 2 ) 在相同的基域下，椭圆曲 线密码系统具有更多的可选择性。也就是说对给 定的素数，都唯一对应一个r s a算法，但是对于椭圆曲线，改变椭圆曲线方程的 系数就能得到不同的曲线。 ( 3 ) 椭圆曲线密码体制基于椭圆曲 线上求解离散对数问题，它优于基于有限域 的乘法群上的离散对数问题的密码体制。目 前，椭圆曲线离散对数还没有发现亚 指数时间攻击。椭圆曲线密码体制的一个迷人之处在于，基于它的离散对数问题 比一般的基于整数的离散对数问题和整数分解问题更加困难。 更加明确地说， 设e 盆 监 宝 监 盆 盆 孟 - 一 一 一 - - 一 一. 为 基于 有限 域凡的 椭圆曲 线， 其中p 为 素 数或 素数的 幂次， n 为 椭圆曲 线土点的 个数， n 一般近似于p ， 当n 为素数或含有一个大数因 子时， 计算e 上的离散对数 的 最 著 名 的 方 法 就 是p o lla r d 的 完 全 指 数 算 法 ， 其 预 期 的 运 行 时 间 为 杯刃 万 。 值 得 指出 的是 这个函 数的 变化比 基于整数域z p 的 离散 对数和整数分解的 运行时间函 数 的 变 化决 得 多 。 举 一 个 具 体 的 例 子 ， 设e为 基 于 域f 2 ,. 的 一 条曲 线， 作一 个 乐 观 的估计，设一台速率为 1 mi p 5的机器每秒可以完成 4 0 0 0 0 个椭圆曲线操作，则以 这个 运算能 力， 为计 算一 个单 个的e上的 椭圆曲 线离 散 对 数需 要 1 0 1 2 m y ( m i p s y e a r ) 。 相反的， 根据d o d s o n 和l e n s tr a 2 2 的 最新的 数 域分 解法的 实 现 来看， 分解 一个 1 0 2 4比 特的整数需要花这种运算能力的机器大约 3 x 1 0 my 。因此，基于 1 6 0 比 特 的 域j - 的 椭 圆 曲 线 密 码 体 制 可 以 提 供 与1 0 2 4 比 特 的r s a 或d s a同 样 的 安 全 度 。 而 且 ， 基 于 凡 。 的 椭 圆 曲 线 密 码 体 制 的 域 运 算 比1 0 2 4 比 特 的 模 运 算 快 得多。此外，基于此椭圆曲线的加密和签字也要比1 0 2 4比特的r s a和d s a快 - 个数量级。从上面的 讨论可知， e c c具有更小的密钥长度，更小的带宽，而且它 的实现速度更快， 这些优点使得它更适合十功率和集成电路空间受限的应用场合， 比如灵巧卡、p c卡和无线设备等。 1 . 3论文结构安排 本文共分为五章，各章内容说明如下: 第一章为绪论。介绍了本论文的研究背景与动机，并讨论了本文的基础 椭圆曲线密码体制的优点。 第二章介绍了椭圆曲 线密码体制。本论文所研究的身份认证方案是建立在椭 圆曲线密码学基础之上的，因此这一章对相关的椭圆曲 线密码学知识进行了介绍， 如基于椭圆曲线的数字签名原理、椭圆曲线的安全性分析以及如何选取安全的椭 圆曲线等。 第三章讨论了现有的一些身份认证算法以及典型的一 些认证协议，并比较其 优缺点。这一章还对目 前无线环境中所采用的协议及身份认证方案进行了分析， 指出本文所采用的身份认证方案的可行性与优势。 第四章依据相关理论， 详细设计了一种适合于无线环境下基于g f ( 2 勺域的自 我验证身份认证方案，然后说明了此方案的模拟实现，最后对其安全性和复杂度 进行了分析。 第五章总结了本文的工作，并对今后进一步的研究提出了展望。 盆 监 宝 监 盆 盆 孟 - 一 一 一 - - 一 一. 为 基于 有限 域凡的 椭圆曲 线， 其中p 为 素 数或 素数的 幂次， n 为 椭圆曲 线土点的 个数， n 一般近似于p ， 当n 为素数或含有一个大数因 子时， 计算e 上的离散对数 的 最 著 名 的 方 法 就 是p o lla r d 的 完 全 指 数 算 法 ， 其 预 期 的 运 行 时 间 为 杯刃 万 。 值 得 指出 的是 这个函 数的 变化比 基于整数域z p 的 离散 对数和整数分解的 运行时间函 数 的 变 化决 得 多 。 举 一 个 具 体 的 例 子 ， 设e为 基 于 域f 2 ,. 的 一 条曲 线， 作一 个 乐 观 的估计，设一台速率为 1 mi p 5的机器每秒可以完成 4 0 0 0 0 个椭圆曲线操作，则以 这个 运算能 力， 为计 算一 个单 个的e上的 椭圆曲 线离 散 对 数需 要 1 0 1 2 m y ( m i p s y e a r ) 。 相反的， 根据d o d s o n 和l e n s tr a 2 2 的 最新的 数 域分 解法的 实 现 来看， 分解 一个 1 0 2 4比 特的整数需要花这种运算能力的机器大约 3 x 1 0 my 。因此，基于 1 6 0 比 特 的 域j - 的 椭 圆 曲 线 密 码 体 制 可 以 提 供 与1 0 2 4 比 特 的r s a 或d s a同 样 的 安 全 度 。 而 且 ， 基 于 凡 。 的 椭 圆 曲 线 密 码 体 制 的 域 运 算 比1 0 2 4 比 特 的 模 运 算 快 得多。此外，基于此椭圆曲线的加密和签字也要比1 0 2 4比特的r s a和d s a快 - 个数量级。从上面的 讨论可知， e c c具有更小的密钥长度，更小的带宽，而且它 的实现速度更快， 这些优点使得它更适合十功率和集成电路空间受限的应用场合， 比如灵巧卡、p c卡和无线设备等。 1 . 3论文结构安排 本文共分为五章，各章内容说明如下: 第一章为绪论。介绍了本论文的研究背景与动机，并讨论了本文的基础 椭圆曲线密码体制的优点。 第二章介绍了椭圆曲 线密码体制。本论文所研究的身份认证方案是建立在椭 圆曲线密码学基础之上的，因此这一章对相关的椭圆曲 线密码学知识进行了介绍， 如基于椭圆曲线的数字签名原理、椭圆曲线的安全性分析以及如何选取安全的椭 圆曲线等。 第三章讨论了现有的一些身份认证算法以及典型的一 些认证协议，并比较其 优缺点。这一章还对目 前无线环境中所采用的协议及身份认证方案进行了分析， 指出本文所采用的身份认证方案的可行性与优势。 第四章依据相关理论， 详细设计了一种适合于无线环境下基于g f ( 2 勺域的自 我验证身份认证方案，然后说明了此方案的模拟实现，最后对其安全性和复杂度 进行了分析。 第五章总结了本文的工作，并对今后进一步的研究提出了展望。 东北大学硕士学位论文 第二章 椭圆曲线密码体制 第二章 椭圆曲线密码体制 1 9 7 6年 d i ff i e和 h e l l m a n提出的基于离散对数的第一个公钥密码体制 1 6 1 及 1 9 7 8 年由r i v e s t , s h a t n ir 和a d l e m a n 提出的基于大数分解的r s a公钥体制 1 7 把密 码学推进到了一个新的的阶段。尽管r s a等公钥体制在加密和数字签名方面有许 多应用，但随着r s a安全密钥位数的不断增长，对那些需要处理大量安全事务的 电子商务站点来说，无疑增加了沉重的负担，也大大影响了加密速度。因此，椭 圆曲线以其相对比较新颖的加密技术、快速的加密结果和具有短密钥等特点，逐 渐被人们所认识，并开始大量应用于网络系统的数字签名等密码系统中。 椭圆曲 线己 经 研究了 很多 年， 关于 这方 面有 大量的 文献。 1 9 8 5 年n e a l k o b lit z 7 1 和v .s .m il l e r 1 8 】 分 别 独 立的 将它 们用于 公钥 密码 体制， 他 们没 有发明 使 用椭圆曲 线 的密码算法，但他们用有限域上的椭圆曲线实现了已经存在的公钥密码算法，例 如 d i f fi e - h e l l m a n 密钥交换算法 1 6 和e l g a m a l 加密和签名算法 1 9 1 。 定义在有限 域 上的椭圆曲线的有理点全体构成一个加法交换群，利用这个群上的求离散对数困 难可以构造密码体制。下面简单介绍与本文相关的椭圆曲线的基本原理。 2 . 1椭圆曲线基本原理概述 2 . 1 . 1椭圆曲线基本数学原理 椭 圆 曲 线 的 研 究 来 源 于 椭 圆 积 分丁 - 里， 这里的e ( x ) 是x 的 三次 多 项式 或 e ( x ) 四次多项式。这样的积分不能用初等函数来描述，为此引入了椭圆曲线的概念， 从椭圆 积分继而5 出了 椭圆曲 线。 所谓椭圆曲 线指的 是由 式( 2 . 1 ) 所示的w e i e r s t r a s s 方程: 尹+ a lx y + a 3 y = x + a 2 x + a 4 x + a 6 ( 2 . 1 ) 所确定的平面曲 线。 f是一个域， 满足上式的数偶( x ,y ) 称为f域上的 椭圆曲 线 e 的点。 f 域可以是有理数域，也可以 是复数域，还可以是有限域g f ( p ) o 椭圆曲 线通常用e表示。 除了曲线e的所有点， 还需加上一个叫做无穷远点的特殊点d a 上 述 方 程 是 建 立 在 仿 射 平 面a , , 上 的 ， 由 于 射 影 平 面凡 : 是 由 仿 射 平 面人2 添 加 一 条 虚 直 线 而 成 的 ， 故p k : 上 的 椭 圆 曲 线 有 其a k , 上 的 等 价 形 式 ， 只 要 再 等 式 中 令 东北大学硕士学位论文 第二章 椭圆曲线密码体制 第二章 椭圆曲线密码体制 1 9 7 6年 d i ff i e和 h e l l m a n提出的基于离散对数的第一个公钥密码体制 1 6 1 及 1 9 7 8 年由r i v e s t , s h a t n ir 和a d l e m a n 提出的基于大数分解的r s a公钥体制 1 7 把密 码学推进到了一个新的的阶段。尽管r s a等公钥体制在加密和数字签名方面有许 多应用，但随着r s a安全密钥位数的不断增长，对那些需要处理大量安全事务的 电子商务站点来说，无疑增加了沉重的负担，也大大影响了加密速度。因此，椭 圆曲线以其相对比较新颖的加密技术、快速的加密结果和具有短密钥等特点，逐 渐被人们所认识，并开始大量应用于网络系统的数字签名等密码系统中。 椭圆曲 线己 经 研究了 很多 年， 关于 这方 面有 大量的 文献。 1 9 8 5 年n e a l k o b lit z 7 1 和v .s .m il l e r 1 8 】 分 别 独 立的 将它 们用于 公钥 密码 体制， 他 们没 有发明 使 用椭圆曲 线 的密码算法，但他们用有限域上的椭圆曲线实现了已经存在的公钥密码算法，例 如 d i f fi e - h e l l m a n 密钥交换算法 1 6 和e l g a m a l 加密和签名算法 1 9 1 。 定义在有限 域 上的椭圆曲线的有理点全体构成一个加法交换群，利用这个群上的求离散对数困 难可以构造密码体制。下面简单介绍与本文相关的椭圆曲线的基本原理。 2 . 1椭圆曲线基本原理概述 2 . 1 . 1椭圆曲线基本数学原理 椭 圆 曲 线 的 研 究 来 源 于 椭 圆 积 分丁 - 里， 这里的e ( x ) 是x 的 三次 多 项式 或 e ( x ) 四次多项式。这样的积分不能用初等函数来描述，为此引入了椭圆曲线的概念， 从椭圆 积分继而5 出了 椭圆曲 线。 所谓椭圆曲 线指的 是由 式( 2 . 1 ) 所示的w e i e r s t r a s s 方程: 尹+ a lx y + a 3 y = x + a 2 x + a 4 x + a 6 ( 2 . 1 ) 所确定的平面曲 线。 f是一个域， 满足上式的数偶( x ,y ) 称为f域上的 椭圆曲 线 e 的点。 f 域可以是有理数域，也可以 是复数域，还可以是有限域g f ( p ) o 椭圆曲 线通常用e表示。 除了曲线e的所有点， 还需加上一个叫做无穷远点的特殊点d a 上 述 方 程 是 建 立 在 仿 射 平 面a , , 上 的 ， 由 于 射 影 平 面凡 : 是 由 仿 射 平 面人2 添 加 一 条 虚 直 线 而 成 的 ， 故p k : 上 的 椭 圆 曲 线 有 其a k , 上 的 等 价 形 式 ， 只 要 再 等 式 中 令 东 北大学硕士学位论文 第二章 椭圆曲线密码体制 一 合 ， 一 普 ， 得 : 2z + a ,二+ a 3y z 一 x 十 2x 2z + a 4x z 2 + a 6z 。 其 中 虚 点 为 ( 0 , 1 ,0 ) ,气 : 上的 虚 线 为z = o o 射 影 平 面凡 。 上 ， 设f (x , y , 劝 一 y 2 z + a ,x y z + a , y z 2 - x - a 2 x , z - a 4 x z z - a 6 z 3 称 f (x ,y ,z ) 为 w eierstra s侈 项 式 。 当 f (x ,y , z )篇，器 ，器 ) / (0,0 ,0 ) 时 ， 则 根 据 w e ie r s tr as s 等 式 所 确 定 的 曲 线 即 为 椭 圆 曲 线 。 如 果 在 点 尸 ， 巡，塑，磐 # ( 0 ,0 ,0 ) dx ay a z 成立，则椭圆曲线成为光滑的或是非奇异的，否则称为奇异的，此时点p称为奇 异点 。 若e 是 定 义 在 有限 域 儿l 的 域 椭圆曲 线 且q = p 灿 为 素 数 ) ， 这 样的p 被 称 为 有限 域儿的 特征， 其 数值即 为 有限 域儿的 特征 值。 若p 是 椭圆曲 线e 上的 一点， 若存在最小的正整数n ， 使得n p = o ,其中o是无穷远点， 则称n 是p点的阶。 椭 圆曲线上有理点的个数即为该椭圆曲线的阶。 2 . 1 .2有限域g f ( 2 m ) 上的椭圆曲 线 常 用的 椭圆 方 程的 有限 域 有 两 种: f p 和f ., 当 椭圆 曲 线 定 义 在f上的 时 候 ( p 3 ， 且p 为 奇 素 数 )，取a , b e f并 满 足4 a + 2 7 b 2 # 0 ( m o d p ) ， 则 椭 圆 方 程 定 义 为 少二 x + a x + b , 椭圆 曲 线e ( 凡) 为 该 椭圆 方 程上 的 点 外 加 一 无 穷 远 点o 构 成的 集 合。 当 椭圆 方 程 定 义 在凡 ， 上的 时 候， 取。 , b e 凡 。 ，b # 0 ， 则 椭圆 方 程定 义为 y 2 + x y 一3x 十 。 2 + b , 椭 圆 曲 线 e ( 气 m ) 为 该 椭 圆 方 程 上 的 点 外 加 一 无 穷 远 点口 构 成的集合。 在密 码学中， 我们 主要 关 心 有限 域 上的 椭圆曲 线， 特别是 大素 数域f p 和 特征 为2 的 有限 域g f ( 2 与。 数学上已 经 确定对于域尺寸近似相等的 域凡和g f ( 2 0 ) 而 言， 椭圆曲 线离散对数问 题( e c d l p ) 一样困 难。 在一些对安全性要求很高的领域如涉及军事机密或国防安全的保密通信等应 用场 合， 人们 倾向 于 选 择用有限 域f p 上的 椭圆曲 线 来构 造 椭圆曲 线密 码体 制。 可 是，随着安全性的提高，其计算复杂度也相应增加了，从而信息的加、解密速度 也受到了影响。对于一些商业应用，不必要求过高的安全性，而运行速度确是一 个需要重点考虑的因素。由 于有限域g f ( 2 - ) 上b i t 位值大于2的算术运算容易用 硬件实 现， 且g f ( 2 ) 域上 的元素进行两点相 加时 乘法次数可以 相应减小， 因 此如 果椭圆曲线密码体制用定义在有限 域g f ( 2 - ) 上的 椭圆曲 线来实现， 则可以 获得更 高的运算效率。在硬件实现中尤其如此。因为硬件中存在着用于有限域乘积的非 东 北大学硕士学位论文 第二章 椭圆曲线密码体制 一 合 ， 一 普 ， 得 : 2z + a ,二+ a 3y z 一 x 十 2x 2z + a 4x z 2 + a 6z 。 其 中 虚 点 为 ( 0 , 1 ,0 ) ,气 : 上的 虚 线 为z = o o 射 影 平 面凡 。 上 ， 设f (x , y , 劝 一 y 2 z + a ,x y z + a , y z 2 - x - a 2 x , z - a 4 x z z - a 6 z 3 称 f (x ,y ,z ) 为 w eierstra s侈 项 式 。 当 f (x ,y , z )篇，器 ，器 )