（计算机应用技术专业论文）基于椭圆曲线零知识证明的身份认证系统的研究和实现.pdf

摘要 身份认证技术是计算机网络安全问题的一个重要方面，是保护网络资产的第 一道关口，为网络中的信息安全提供了强有力的保障，对于需要处理大量货币的 银行业和保险业尤其重要。目前最常用的身份认证机制基本上都是基于r s a 算 法，但是随着对安全性要求地不断提高，r s a 所采用的密钥长度也在不断增加， 这就直接导致了r s a 计算量的增加。椭圆曲线密码体制( e c c ) 的出现对r s a 产生了巨大的挑战，e c c 的安全性是建立在椭圆曲线离散对数问题( e c d l p ) 之上的，e c d l p 问题到目前为止还没有发现亚指数时问的攻击方法，而且在实 现同等级别的安全性下，e c c 所需的密钥量比r s a 少得多。 但是上述身份认证仍然存在一些安全隐患，如重放攻击、离线字典攻击等。 为了解决以上问题，本论文提出了基于零知识证明的身份认证技术，该技术是指 在认证过程当中示证方可以不让验证方得到任何有用的信息而能证明自己就是 一个合法用户，从而保证了信息的安全性。 为了实现本论文的研究目标建立一个安全有效的身份认证系统，现将零 知识证明理论引入到椭圆曲线密码体制中，设计并实现了一种基于椭圆曲线零知 识证明的身份认证系统并应用于保险公司管理项目中。本论文的工作主要有以下 几个方面： ( 1 ) 对椭圆曲线的数学理论进行研究； ( 2 ) 对e c c 体制进行研究并得出结论：采用l 6 p e z d a h a b ( l d ) 投影坐标系 可以避免比较费时的求逆运算、减少乘法运算； ( 3 ) 通过对e c c 体制的核心算法标量乘算法的研究，得出结论：采用 m a r y 算法代替二进制算法计算标量乘运算，可以在一定程度上减少运算时 间； ( 4 ) 对零知识证明理论进行研究分析得出结论：椭圆曲线零知识身份认证 技术可以较好地解决如重放攻击等安全隐患问题； ( 5 ) 将本系统分为运算层、操作层和协议层来实现。 实验证明，系统在测试过程中运行稳定，在运行效率和安全性上基本达到了 预期的设计目标。 关键字：椭圆曲线密码体制( e c c ) ；零知识证明理论；身份认证；标量乘算法 a b s t r a c t a u t h e n t i c a t i o nt e c h n o l o g yi sa ni m p o r t a n ta s p e c to ft h ec o m p u t e rn e t w o r k s e c u r i t y , i ti st h ef i r s tb a r r i e ro fp r o t e c t i n gt h en e t w o r k a s s e t s ，a n di tp r o v i d e sas t r o n g g u a r a n t e ef o r t h en e t w o r ki n f o r m a t i o ns e c u r i t y e s p e c i a l l y , i tt a k e sa c r u c i a lp o s i t i o n i nn e e do fd e a l i n gw i t hal o to fm o n e yi nt h eb a n k i n ga n di n s u r a n c ei n d u s t r y t h e m o s tp o p u l a ra u t h e n t i c a t i o nm e c h a n i s mi sb a s i c a l l yb a s e do nt h er s aa l g o r i t h m ，b u t w i t ht h ei m p r o v i n gs e c u r i t yr e q u i r e m e n t s ，r s ak e yl e n g t hi sa l s oi n c r e a s i n g ，w h i c h l e dd i r e c t l vt oa ni n c r e a s ei nr s ac o m p u t a t i o n t h ea p p e a r a n c eo fe l l i p t i cc u r v e c r y p t o g r a p h y ( e c c ) c r e a t e dah u g ec h a l l e n g et or s a ，t h ee c c ss e c u r i t yi sb a s e d o n e l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ( e c d l p ) ，t h ee c d l p i s s u e sh a ds of a r f o u n dn os u b e x p o n e n t i a lt i m eo ft h ea t t a c km e t h o d s ，a n dt oa c h i e v et h es a m el e v e lo f s e c u r i t y , e c ck e y sa r er e q u i r e dm u c hl e s st h a nr s a s h o w e v e r , t h e s ea u t h e n t i c a t i o ns t i l lh a v es o m es e c u r i t yr i s k s ，s u c ha sr e p l a y a t t a c k ，o f f - l i n ed i c t i o n a r ya t t a c k se t c i no r d e rt os o l v et h ea b o v ep r o b l e m s ，t h i st h e s i s p r e s e n t saz e r o k n o w l e d g ep r o o f - b a s e da u t h e n t i c a t i o nt e c h n o l o g y , t h i st e c h n o l o g y i s t h a tw h e ni np r o c e s so fc e r t i f i c a t i o n ，t h ep e r m i t sc a np r o v ei t s e l fa sal e g i t i m a t eu s e r w i t h o u ts h o w i n ga n yu s e f u li n f o r m a t i o nt ot h ec e r t i f i e r s ，w h i c he n s u r ei n f o r m a t i o n s e c u r i t y i no r d e rt oa c h i e v et h er e s e a r c ho b j e c t i v e so ft h i st h e s i s - t h ee s t a b l i s h m e n to f a s a f ea n de f f e c t i v ei d e n t i t ya u t h e n t i c a t i o ns y s t e m ，t h ez e r o - k n o w l e d g ep r o o f w i l ln o w b ei n t r o d u t e di n t ot h et h e o r yo fe l l i p t i c c u r v ec r y p t o s y s t e m ，d e s i g n e da n d i m p l e m e n t e daz e r o k n o w l e d g ep r o o fb a s e do ne l l i p t i cc u r v ea u t h e n t i c a t i o ns y s t e m a n da p p l i e dt ot h ei n s u r a n c ec o m p a n ym a n a g e m e n tp r o j e c t s t h em a i nw o r ki s a s f o l l o w s ： ( 1 ) s t u d i e do f 也em a t h e m a t i c a lt h e o r yo fe l l i p t i cc u r v e s ； ( 2 ) s t u d yo ft h ee c cs y s t e ma n dc o n c l u d e d ：u s i n gt h el 6 p e z d a h a b ( l d ) p r o j e c t i o nc o o r d i n a t es y s t e mc a na v o i dt h em o s tt i m e c o n s u m i n g i n v e r s eo p e r a t l o n a n dr e d u c et h em u l t i p l i c a t i o no p e r a t i o n ； ( 3 ) b yt h er e s e a r c h o ft h ec o r ea l g o r i t h mf o re c cs c a l a rm u l t i p l i c a t i o n a l g o r i t h ms t u d yi tc o n c l u d e dt h a t ：t h em - 锄了a l g o r i t h m ，t oac e r t a i ne x t e n t ，c a n d e c r e a s et h ec o m p u t a t i o nt i m ei n s t e a do ft h eb i n a r ys c a l a rm u l t i p l i c a t i o na l g o r i t h m ； ( 4 ) b yt h es t u d yo f t h et h e o r yo fz e r o - k n o w l e d g ep r o o fi tc o n c l u d e dt h a t ：e l l i p t i c c u r v ez e r o k n o w l e d g ea u t h e n t i c a t i o nt e c h n o l o g yc a ne f f e c t i v e l y s o l v et h es a f e t y i i i p r o b l e m s ，s u c ha sr e p l a ya t t a c k s ，e t c ； ( 5 ) t h ep r e s e n ts y s t e mi sc o m p o s e do f a r i t h m e t i c a ll a y e r s ，t h eo p e r a t i o nl a y e ra n d p r o t o c o ll a y e r t h ee x p e r i m e n t ss h o wt h a tt h es y s t e mr u n ss t a b i l i t yi nt h et e s t i n gp r o c e s s ，a n d b a s i c a l l ya c h i e v e st h ee x p e c t e dd e s i g ng o a l so no p e r a t i o n a le f f i c i e n c ya n ds a f e t y k e y w 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 ( e c c ) ；t h e o r yo fz e r o k n o w l e d g ep r o o f ； a u t h e n t i c a t i o n ；s c a l a rm u l t i p l i c a t i o na l g o r i t h m i v 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所作的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名：转毛堡妇期：沙1 。缉了日，蹦 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他手段保存论文。保密的论文在解密后遵守此 规定。 作者签名渭压荔矗师签名：日期：加1 。缉蹋? 踊 上海师范大学硕t ：学位论文 第一章绪论 第一章绪论 1 1 论文的研究目的意义 1 1 1 论文来源 本论文主要来源于上海计算所项目保险公司管理项目的设计与开发。 1 1 2 论文研究的目的和意义 随着网络技术的普及，网上交易已经变成日常生活中很重要的一部分，网上 信息交流的安全性也越来越受到人们的重视。无论在金融、商业还是个人信息的 交流中，人们都希望能够确定对方的真实身份。然而在充满竞争的现实社会中， 身份欺诈现象却是层出不穷，因此身份认证技术就显得十分重要。身份认证技术 是计算机网络安全问题的一个重要方面，是防护网络资产的第一道关口，为网络 中的信息安全提供了强有力的保障，对于需要处理大量货币的银行业和保险业尤 其重要。例如在银行业，目前随处可见的自动出纳机( a u t o m a t i ct e l l e rm a c h i n e ， a t m ) ，它可以将现款发给经a t m 正确识别后的账号持卡人，不仅给广大人民 群众带来极大的便捷，而且也大大提高了服务质量和工作效率。然而任何事情都 是一分为二的，a t m 在带来便利的同时也让不法分子有了可趁之机，他们可以 仿冒合法用户盗取金钱。只有通过使用高效的身份认证技术才能够减少这种事情 的发生。 身份认证的传统方法是通过对本人持有“物”的有效性检验来实现的。“物 包括护照、身份证、学生证、社保卡、工作证等，这些证件上面的个人照片、身 份信息和权威机构对这些证件的签章都可以用来验证该持有人的身份，如银行卡 必须采用实名制，只有用相应的身份证才能更改银行卡的密码。 随着信息业务地不断扩大，这些原先靠人工识别的工作已经渐渐地由计算 机、智能卡、a t m 、p d a 等电子手段来替代。目前出现的采用电子手段实现个 人身份认证的方法有很多：当长途电话费用用电话公司发行的卡支付时，用户需 要输入四位十进制数字的p i n ：从银行的a t m 取款时，用户需要将银行卡和密 码输入其中，只有当银行卡和密码相匹配时才能通过验证；通过网络访问数字资 源时，访问者需要验证用户名和密码。但是这几种身份认证都只是简单地把密码 以明文的形式传送在网络上，这样密码在传输过程当中很容易被恶意者截获，那 么截获者便可以利用截获的密码伪装成合法用户进行非法访问，这样势必会造成 第一章绪论上海师范火学硕上学位论文 非常严重的危害。 目前最常用的身份认证机制基本上都是基于r s a 算法，该算法是由美国三 位科学家r l r i v e s t ，a s h a m i r 和l a d l e m a n ( 被称作m i t 体制) 所提出来的， 它既可以用于加密，又可以用于数字签名，而且又非常容易被实现，因此得到了 大家的认可并被广泛应用于各种场合。但是随着各个领域对安全性要求地不断提 高，r s a 所采用的密钥长度也在不断增加，由原来5 1 2b i t 的长度增加到1 0 2 4b i t 甚至是2 0 4 8b i t ，这就直接导致了r s a 计算量的增加( r s a 算法计算是以指数 乘为基础的) ，这对r s a 的广泛应用产生了一定的影响。 椭圆曲线密码( e c c ) 的出现，对r s a 的应用提出了巨大的挑战。从1 9 世 纪末起，很多标准化组织如i s o ( i n t e r n a t i o n a ls t a n d a r d so r g a n i z a t i o n s ) 、i e e e ( i n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c se n g i n e e r s ) 、n i s t ( n a t i o n a li n s t i t u t eo f s t a n d a r d sa n dt e c h n o l o g y )a n s i 【2 】【3 】( a m e r i c a nn a t i o n a ls t a n d a r d si n s t i t u t e ) 开始了对e c c 标准化工作。1 9 9 8 年底，出现了如i e e ep 1 3 6 3 、a n s ix 9 6 2 、 a n s ix 9 6 3 等技术标准。本论文所用到的关于e c c 的算法和参数都是参照i e e e p 1 3 6 3 标准。与r s a 相比，椭圆曲线密码体制以其较小的时延( 签名和加密速 度高) 和开销( 所需的存储量、计算量、带宽等) 等优点有较为广泛的应用前景。 但是上述身份认证仍然存在一些安全隐患，如重放攻击、离线字典攻击等。 为了解决以上问题，本论文提出了基于零知识证明的身份认证技术，该技术是指 在认证过程当中示证方可以不让验证方得到任何有用的信息而能证明自己就是 一个合法用户，从而保证了信息的安全性。 本论文的项目来源是一个保险公司管理项目，由于该项目涉及到大量的货币 处理，因此在安全性能方面有较高的要求。客户希望在身份认证方面能有一个新 的提高，为了解决这样一个问题本论文提出了基于椭圆曲线零知识证明的身份认 证方案，实验证明该方案能够较好地满足客户在安全性能方面的要求。 1 2 国内外的研究现状 1 2 1 将椭圆曲线引入到安全领域的研究现状 椭圆曲线( e l l i p t i cc u r v e ) 理论是一个代数几何问题，并且该理论在数学领 域中已经有了1 0 0 多年的研究历史，积累了大量的文献【4 】【引。1 9 8 5 年n k o b l i t z l 6 】 和v 。m i l l e r 7 1 第一次将椭圆曲线理论引入到密码领域中并与之完美结合，他们利 用有限域曰上椭圆曲线点集所构成的群上定义的离散对数系统，构造出了双钥 2 上海师范人学硕上学位论文第一章绪论 体制，如d i f f i e h e l l m a n 密钥交换算法【8 】和e l g a m a l 加密和签名算法【9 1 。 自从把椭圆曲线理论引入到密码领域以后，它成为了国际上热门的研究领 域。在最初的l o 年间，专家们主要专注于对椭圆曲线密码技术在理论方面的研 究，其中研究成果最为显著的是域操作算法【i o l 。 从1 9 9 5 年以后，专家们对椭圆曲线密码技术进行更加深入地研究并开始偏 重于应用方面【1 1 博副束找粥i 用瓯。加拿大c e r t i c o m 公司已经开发出实用的产品如p c 卡的信息安全模块c a r d s e c r e t s 和独立应用的安全传真模块f a x s e c r e t s 。 美国n e x tc o m p u t e r 公司也开发出快速椭圆加密( f e e ) 算法。法国的t h o m p s o n 公司、德国s i e m e n s 公司、日本的m i t s u s h i t a 公司和加拿大w a t e r l o o 大学等也都 在研究这一体制，其中有些还申请了专利。同时，中国对椭圆曲线的研究也非常 重视，已经有很多大学对其进行研究，其中以清华大学、西安交大、山东大学、 西安电子科技大学等几个学校的数学学院和计算机学院最为突出。 从椭圆曲线引入到密码领域中发展至今，专家们在椭圆曲线域操作算法方面 已经进行了比较深入的研究，并且有了非常显著的研究成果，除此之外还有另外 几个领域也是当今的研究热点： ( 1 ) 如何选取安全强度较高的椭圆曲线的参数。在建立椭圆曲线密码系统 的整个过程当中最费时的一个步骤便是选取合适的系统参数。这里以二进制域为 例，椭圆曲线的域参数d = ( m ，f ( z ) ，a ，b ，n ，h ，x ，y ) ，其中m 表示二进制域曰的扩展 次数，f ( z ) 表示次数为m 的约减多项式，( a ，b ) 表示椭圆曲线y 2 + x y = x 3 + 饿2 + 6 的系数，n 表示基点p 的( 素数) 阶，h 为余因子，( x ，y ) 表示基点p 的横坐标和 纵坐标。域参数d 可以以离线的方式产生，但是如何快速地以在线的方式产生 安全的域参数仍是一直在谋求解决的问题。 ( 2 ) 提高在椭圆曲线上计算标量乘的效率。计算舻( k 是一个大整数，尸 是椭圆曲线上的一点) 标量乘是椭圆曲线密码体制的核心算法，该算法的效率对 整个体制的执行效率有很大的影响。椭圆曲线密码体制的安全性主要是基于椭圆 曲线上离散对数问题( e c d l p ) 的复杂性，即对于二进制域f 上的一条椭圆曲 线y 2 + x y = r + a x 2 + 6 ，令p 、q 为该曲线上的两个点，求出正整数k 使之满 足公式q = k p 。到目前为止还没有找到一个令人满意的解决e c d l p 问题的亚 指数复杂性的算法l l3 1 ，因此标量乘的快速算法也成了目前的研究热点。计算标量 乘主要是由椭圆曲线上点的加法和倍点来实现的，而曲线上点的加法和倍点运算 又是以域操作( 包括域加法、域减法、域乘法、域除法等等) 为基础的，其中最 费时的是域除法，其次是域乘法，因此要提高椭圆曲线上计算标量乘的效率，途 第一章绪论 上海师范大学硕l ：学位论文 径之一便是尽量减少域除法与域乘法的运算次数。本论文中为了改进椭圆曲线标 量乘的计算效率引入了朋一口吵算法，在一定程度上减少了运算时间。 1 2 2 零知识证明理论的现状 为了解决身份认证中存在的重放攻击、离线字典攻击等问题，许多专家学者 们都在积极寻找解决方案。专家们研究发现零知识证明理论的零知识特性特别适 用于身份认证，随后便出现了许多基于零知识身份证明的协议。最早出现的零知 识身份证明协议是f e i g e f i a t s h a m i r 协议【l3 l ( 简称f f s 协议) ，但是该协议需 要经过多次交互才能保证身份认证的安全性，不仅费时而且也费资源。此后又提 出了g u i l l o u q u i s q u a t e r 协议【l5 1 ，该协议是f i a t s h a m i r 协议的扩展，需要第三 方参与并且利用公钥体制实现，它可以用较少的次数证明示证方的身份，解决了 f f s 协议存在的问题。周先存等在“一种基于签名和零知识证明的身份认证方案 文章中【l6 】利用e l g a m a l 签名方案和零知识证明理论提出了一种较为高效的身份 认证方案。王会进等人在“基于零知识证明的x m l 数字签名方案”文章中1 1 7 1 运用基于零知识证明的数字签名技术对x m l 文档进行签名及验证。郑晶等人在 “基于r s a 的零知识水印验证协议”文章中i l8 】提出了将r s a 公钥密码体制与零 知识证明理论相结合的水印验证协议，并将其应用到水印检测问题中。 1 3 本论文的主要工作 为了实现本论文的研究目标建立一个安全有效的身份认证系统，现将零 知识证明理论引入到椭圆曲线密码体制中，设计并实现了一种基于椭圆曲线零知 识证明的身份认证系统。本论文的工作主要有以下几个方面： ( 1 )对椭圆曲线的理论进行了研究，如有限域的理论、椭圆曲线的基本 概念、椭圆曲线上群的运算法则和标量乘运算。 ( 2 )对目前比较新颖的椭圆曲线密码体制进行了研究，分析了椭圆曲线 密码体制的优点。作者通过研究发现减少求逆运算和乘法运算可以 提高椭圆曲线密码体制的效率。作者对几种坐标系进行比较得出采 用l 6 p e z d a h a b ( l d ) 投影坐标系1 1 9 可以避免求逆运算，减少乘法运 算的次数，因此比较适合本论文的需求。 ( 3 )通过对椭圆曲线算法的研究可知：标量乘k p 是椭圆曲线的核心算 法。本论文中采用m 一口w 算法代替二进制算法计算标量乘运算， 4 上海师范人学硕t 学位论文 第一章绪论 在一定程度上减少了运算时间。 ( 4 ) 分析了几种零知识证明的算法，其中主要研究了椭圆曲线零知识证 明的算法，并用j a 、，a 予以实现 ( 5 )通过将系统分为三个层次来详细描述整个系统的具体实现，这三个 层次分别为运算层、操作层和协议层。测试结果表明该系统能够较 好地满足客户在安全性能方面的要求并能够稳定运行。 1 4 论文的内容安排 本文主要是针对保险公司管理系统安全性的问题，研究了一种基于椭圆曲线 零知识证明的身份认证系统，主要研究内容包括：椭圆曲线密码体制和算法设计、 零知识证明算法、数字签名、系统结构设计等。 本论文主要分为六章，各章的内容结构说明如下： 第一章为绪论。介绍了论文的研究目的意义、国内外的研究现状，总结了作 者在这个论文中所做的主要工作。 第二章介绍了与该论文相关的理论知识和技术。该论文是以椭圆曲线密码体 制和零知识证明理论为基础的，因此在这一章节中对这些相关的理论知识和技术 进行了介绍，包括椭圆曲线中关于有限域的数论知识、椭圆曲线的基本概念、椭 圆曲线的优点、基于零知识证明的身份认证技术。 第三章对整个系统进行总体的设计，并介绍了n i s t 推荐的五个在二进制域 曰上随机选择的椭圆曲线参数。 第四章将系统分为运算层、操作层和协议层三个层次，实现了一个基于椭圆 曲线零知识证明的身份认证系统，并应用于保险公司项目中。 第五章对整个系统加以实现分析并进行了实验测试，测试结果表明该系统能 较好地满足客户在安全性能方面的要求并能够稳定运行。 第六章对本论文的主要研究工作和创新点作一个总结，并对下一步的研究方 向提出了展望。 j ：海师范大学硕 ：学位论文第二章相关理论知识和技术的介绍 第二章相关理论知识和技术的介绍 2 1 椭圆曲线的理论知识 由于椭圆曲线所涉及到的运算都是基于有限域算术运算，因此有限域算术运 算是实现椭圆曲线密码体制的先决条件。本小节简单介绍了有限域的性质。 2 1 1 有限域的介绍 域【2 0 1 可以这样定义：对常见的数系以及这些数系基本特性的抽象称为域， 这里的数系可以是整数、分数、无理数、复数等等。域由两部分组成：一、两种 运算( 乘法运算与加法运算) ，其中乘法运算用表示，加法运算用+ 表示；二、 集合f ，并且域具有以下几个算术特性： ( 1 ) ( f ，+ ) 是指集合f 对于+ 构成加法交换群，单位元用0 表示，称为 零元素。 ( 2 ) ( f 1 0 ，) 是指集合f 中的所有非零元素( 除零元素之外) 对x 构 成乘法交换群，单位元用1 表示。 ( 3 ) 分配律成立：v a ，b ，c f ，都能使 ( 口+ 6 ) c = a c + b x c 成立，若f 是满足以上三个特性的有限集合，那么称，为有限域。 有限域中的减法和除法分别由加法运算和乘法运算来定义。减法运算定义 为：a - b = 口+ ( 一6 ) ，令a ，b f ，其中b 的负元素用( 一6 ) 表示，在有限域上与 b 对应的负元素只有一个。同理，除法运算定义为：c d - - - c x d ，令c ，d f ， d o ，其中d 的逆元素用d 一表示，在有限域上与d 对应的逆元素只有一个。 有限域的阶指的是有限域中含有的元素个数。假设有一个有限域f ，它的 阶为g ，令q = p ”，p 为域的特征，且p 是一个素数，聊( 域的扩展次数) 是 一个正整数。当所= 1 时，称有限域f 为素域，当m 2 且p = 2 时，称有限域f 为二进制域。本论文中用的是川为1 6 3 的二进制域。 7 第二章相关理论知识和技术的介绍f ：海师范人学硕十学位论文 2 1 2 素域f p 设p 是一个素数，以p 为模，则模p 的全体余数的集合 o ，1 ，2 ， o - 9p - 1 ) 关于模p 的加法和乘法构成p 阶有限域，称为素域，用符号印表示。在素域上 定义的加、乘、求逆操作算法如下： ( 1 ) 加法：a + b = r ，其中日b f p ，r ( 0 r p 1 ) 是a + b 被p 整 除的剩余。 ( 2 ) 乘法：a x b = s ，其中a ，b f p ，s ( 0 s p - 1 ) 是a x b 被p 整 除的剩余。 ( 3 ) 求逆：c 口= 1 ，如果口不是f p 上的零元素，那么有且仅有一个整数 c = 口，口- 1 称为口的模p 逆。 2 1 3 二进制域曰 阶为2 m 的二进制域用符号曰表示。有两种方法可以表示二进制域曰中的 元素：一、多项式基表示法【2 l l ；二、正规基表示法f 1 9 】。本论文采用的是多项式 基表示法，在这种表示方法中，曰中的所有元素可以用公式( 2 1 ) 表示。 f y = 口m l z ”+ g m 一2 z ”一2 + + g 2 2 2 + 口l z + 口o ；口， 0 ，1 ) ) ( 2 1 ) 从公式( 2 1 ) 中可知，该表达式的最高次数不会大于m ，且系数只能是o 或1 。令f ( z ) 为曰上的不可约垅项式，记厂( z ) = 口( z ) + ，( z ) ，其中口( z ) 表示 曰上的多项式，r ( z ) 表示次数低于脚的余式多项式。 现在假设系统的字长为形位( 矿= 8 t ，f 为正整数) ，用0 到形一1 从右到左 标记该位。 公式( 2 1 ) 的域元素也可以表示为朋维向量口= ( 幽一i ，踟一2 ，a 2 ， 口l ，a o ) ， 拈聃 s = 耽- m 。在软件实现中可以用一个数组 a = ( a t - 1 ，4 2 ，彳 1 】，彳 o 】) 来存储口，该数组有f 个长度为位的字，且 一j ：海师范人学硕j ：学位论文第一二章相关理论知识和技术的介绍 a t - 1 的最左边s 位是多出来，我们可以用0 表示。如图2 一l 所示。 ，上1 a t - 1 】a 【1 a 【o 】 图2 1 用位的字表示域f 2 m 的元素a 2 2 椭圆曲线的基本概念 椭圆曲线并不是椭圆，它的概念是由椭圆积分f - 竺引出来的，这里的 。4 e ( x ) e ( x ) 是x 的三次或四次多项式，因此不能用初等函数描述，由此而引入了椭圆 曲线函数。一般来说域f 上的椭圆曲线e 的方程式如公式( 2 2 ) 所示： e ：y 2 + a , x y + a 3 y 2 x 3 + a 2 x 2 + a 4 x + a 6 ( 2 2 ) 其中an ，a 2 ，a 3 ，0 4 ，a 6 曰，a 0 ，是e 的判别式。 公式( 2 - 2 ) 称为w e i e r s t r a s s 方程，所有满足公式( 2 - 2 ) 的点( x ，y ) 和 无穷远点d 构成了域刀上的椭圆曲线群。在软件编程中一般用简化的 w e i e r s t r a s s 方程来定义椭圆曲线，本论文用的是域曰的特征值为2 的简化情况。 由于本论文用的是域曰的特征值为2 的简化情况，因此就以这种情况为例 子来详细介绍这个简化过程( 通过相容性变化来简化) 2 2 】。 域曰的特征值为2 时存在两种情况，第一种情况是公式( 2 2 ) 中的系数 a n = 0 ，第二种情况则为a n 0 。 当a l = 0 时，变量的相容性变换为： ( x ，少) 一( x + a 2 ，少) 整理后得到的曲线为： 1 ，2 + c y = x - i - a x + b ( 2 3 ) ， 一 其中a ，b ，c 曰。称公式( 2 3 ) 表示的曲线为超奇异的。 9 第一二章相关理论知识和技术的介绍 上海师范大学硕l ：学位论文 当口0 时，变量的相容性变换为： k y ，寸卜鲁力+ 竿 整理后得到的曲线为： y 2 + 砂= x 3 + 戤2 + 6 ( 2 4 ) 其中a ，b f ，称公式( 2 4 ) 表示的曲线为非超奇异的。本论文主要研究这类 曲线，并将这类曲线应用于本论文当中。 2 3 椭圆曲线的优点 与其他公钥密码体制相比，椭圆曲线密码体制具有以下优点： ( 1 ) e c c 的安全性是建立在由舻和p 确定k 的困难程度之上，这个问题 被称为椭圆曲线离散对数( e c d l p ) 问题。大家比较熟悉的r s a 密码体制的安 全性是建立在把一个大整数分解成两个素数之积的困难上的，c e r t i c o m 公司对这 两种密码体制进行了对比，发现在实现同等级别的安全性下，e c c 所需的密钥 量比r s a 少得多，表2 1 表示这两者在安全性方面的关系。其中，m i p s 年表示 用每秒完成1 0 0 万条指令的计算机所需工作的年数。 表2 1e c c 和r s a 的对比【2 3 】 e c c 的密钥长度r s a 的密钥长度m i p s 一年r s a e c c 的密钥长度比 1 0 65 1 21 0 45 ：1 1 3 27 6 81 0 s6 ：l 1 6 010 2 41 0 i i7 ：1 2 1 020 4 81 0 2 0l o ：1 6 0 02 10 0 0 1 0 7 8 3 5 ：l 从表2 1 可以看出椭圆曲线密码体制的每1b i t 密钥的安全性要比r s a 的每 1b i t 密钥更强，要达到相同级别的安全性，e c c 和r s a 的密钥长度之比至少为 5 ：1 ，并且可以从上表的最后一列可以看出随着密钥长度的增加，这种比例关系 还会继续加大，而且这种趋势随着密钥长度的增加也会越来越明显，当椭圆曲线 的密钥长度为6 0 0b i t 时r s a 的密钥长度必须达到2 1 0 0 0b i t 才能实现与椭圆曲线 相同级别的安全强度。i f 是由于这种优势使得e c c 比r s a 具有更强的竞争力。 ( 2 ) 求解e c d l p 的复杂性很高。基于e c d l p 比一般的整数分解问题和基 于整数的离散对数问题困难得多，至少到目前为止还没有发现亚指数时间的攻击 方法。 1 0 f ：海师范大学硕t 学位论文第二章相关理论知识和技术的介绍 ( 3 ) 对于相同的基域椭圆曲线密码体制具有更多的选择性。即对于给定的 素数域只能对应一个唯一的r s a 算法，因为一个大整数最多只能对应一种分解 方法，但是对于椭圆曲线，只要改变y 2 + x y = x 3 + a x 2 + b 方程中的参数a 和b 就能得到不同的曲线。 2 4 常用的身份证明技术 2 4 1 身份认证技术的概念 身份认证是指验证方通过验证被认证对象的属性( 口令、数字签名、指纹等 生理特征、数学证明过程) 来确认被认证对象是否有效和属实的一个过程。身份 认证在安全系统设计中有着举足轻重的地位，是安全系统的第一道关卡。任何用 户在进入系统之前首先都要通过系统的身份识别，这里的身份识别是指由安全系 统根据用户的身份信息对应授权数据库查找该用户是否有访问某个资源的权限。 如图2 2 是安全系统的结构图，总共包括三部分：第一部分是安全管理员对授权 数据库进行权限的配置；第二部分是用户通过身份认证访问某个数字资源；第三 部分是审计系统根据审计设置记录用户的请求和行为，同时检测系统是否有入侵 行为。 图2 2 安全系统结构图 2 4 2 常用的身份认证机制 身份认证有很多种【2 4 】，主要有基于口令的认证方式、基于物理证件的认证 第二章相关理论知识和技术的介绍 ：海师范人学顾i ：学位论文 方式、基于生物特征的认证方式。 传统的基于口令的身份认证的过程：首先在系统中保存每个用户的二元组信 息( i d 、p w ) ，然后系统根据用户输入的信息( i d 、p w ) 来判断该用户是否为 合法用户，这种认证方式适合于封闭的小型系统。这种认证机制的最主要缺点是 口令以明文的形式在网络中传输而使得这个口令很容易被恶意者在中途截获，那 么恶意者便可以利用这个口令冒充合法用户，从而直接影响到整个系统的安全 性。 基于物理证件的认证是指凭借用户所有的物理证件如智能卡等束判断该用 户是否为合法用户的认证方式。以下以智能卡为例来说明基于物理证件的认证方 式，智能卡是不可复制的硬件，本身就具有一定的安全性。可以把与用户身份信 息相关的数据如用户名和密码存入智能卡中，该智能卡由合法用户随身携带。当 用户要进入某个系统时，用户必须先把随身携带的智能卡插入专用的读卡器中， 然后由读卡器读取智能卡里的信息同时检验该用户是否为合法用户。 正如上面所述智能卡是不可复制的硬件，因此存储在智能卡内的用户身份信 息不易被仿冒。然而由于每次是以静态的方式从智能卡中读取数据，所以可以通 过内存扫描等途径截取到里面的信息，因此安全隐患仍然存在。 基于生物特征的身份认证技术主要是利用人体唯一、稳定的生物特征来验证 用户的合法性。这种身份认证需要较高科学技术的支持，如传感器等。在使用这 种身份认证之前首先要把合法用户的生理特征数据存放到数据库中，这是预处理 过程。这里以指纹为例，当用户登陆系统时，首先由传感器采集量化用户的指纹 数据，通过特征提取模块提取特征码，再与预先存放在数据库中的指纹特征数据 进行比较( 需要采用一定的算法) ，如果特征相符，那么用户就可以访问某个数 据资源。 基于生物特征的身份认证系统的优点是非常明显的，即防伪性能很好，不容 易被伪造，原因是每个个体的生物特征都是不同的。但是采用该认证技术还存在 着技术不成熟、专门采集特征数据的传感器价格昂贵等问题，因此目前还不适于 广泛应用。 2 5 基于零知识证明的身份认证技术 本论文提出零知识身份验证机制，它是指示证方在不泄露任何有关密钥信息 的前提下，就可以向验证方证明自己就是个合法用户，等验证方验证完毕之后验 证方只能知道示证方是否为一个合法用户，而对于其他的信息一概不知。 q u i s q u a t e r 等1 2 5 】给出了一个通俗的例子来解释什么是零知识证明，以图2 3 为例。 1 2 上海师范人学硕上学位论文第二章相关理论知识和技术的介绍 a 图2 - 3 零知识证明概念图解 这里假设p 为示证者，v 为验证者，c 与d 之间的横线为一扇门，p 知道打 开这扇门的咒语，现在p 要向v 证明他知道这个咒语，按照传统的做法是p 把 这个咒语告诉v ，然后v 用这个咒语去打开那扇门，如果能打开说明这个咒语 是正确的，那么就可以验证p 的身份。这样做虽然成功地证明了p 的身份，但 是也泄露了这个咒语，那么v 可以冒充p 或者v 可以把这个咒语透露给第三者， 从而使得这个系统存在安全隐患。 以下是用零知识证明理论来证明p 的身份： ( 1 ) v 站在a 点，让p 进入洞内，这样保证v 不知道p 是从哪边进入洞 内的。( 从左边进入到达c 点，从右边进入则到达d 点) ； ( 2 )当p 到达c 点或d 点以后，v 走到b 点； ( 3 ) 然后v 要发送挑战信息，叫p 从左边或者右边出来； 1 ( 4 ) p 按照v 的要求从v 指定的方向出来( 这说明p 知道咒语的概率为妻) 么 ( 5 ) p 和v 重复执行( 1 ) ( 4 ) 共刀次。如果每次都能通过则说明v 受 骗的概率为2 。 对上述协议的分析：如果p 对咒语一无所知，那么p 猜中的概率只有5 0 ， 协议执行刀次，则只有2 ”的机会完全猜中。假设，z = 1 6 ，则v 受骗的可能性仅 1 为了妄石。如果n 足够大，那么几乎就可以证明p 是知道这个咒语的而且v 并 0 3 ) j 0 没有得到任何关于这个咒语的信息。 下面介绍几种零知识身份认证体制【2 6 】。 第二章相关理论知识和技术的介绍t 海师范大学硕i j 学位论文 2 5 1 简化f e i g e f i a t s h a m i r 算法 在f e i g e f i a t s h a m i r 协议中，可信赖第三方选定一个随机模m 使得 m=p xq ，其中m 为5 1 2b i t 或者为1 0 2 4b i t 。通信双方共享历，再由可信赖第 三方实施公钥私钥的分配，他产生随机数y ( 要求v 一= m o d m 存在) ，且使y 为 模m 的平方剩余，即x 2 = v ( m o d m ) ，v 为公钥，计算8 = v m o d m ，s 作为 示证方的私钥。( 这里p 作为示证方，v 作为验证方) 。 身份验证协议如下： ( 1 ) 用户p 取随机数f ( 厂 m ) ，计算x = ( ，2 ) m o d m ，将x 发送给v ； ( 2 )v 发送一个挑战信息b ( o 或者1 ) 给p ； ( 3 ) p 接受挑战，算出y = 1 s 6m o d m 作为应答发送给v ； ( 4 ) v 验证p 的身份，验证y 2 - - - 删6m o dm 即y 2 = ( f s 6 ) 2m o d m = 1 2 s 2 6m o d m = ，2 ( s 2 ) 6m o d m = 删6m o d m ，如果相等则有5 0 的概率可以相信p 为合法用户。如果不相等，这个验证过程则终止。 步骤( 1 ) ( 4 ) 为一次鉴定过程，p 和v 可以将步骤( 1 ) ( 4 ) 重复f 次，当f 足够大时，v 便可以几乎相信p 确实知道s 。 p 欺骗v 的可