（计算机应用技术专业论文）基于ecc的组合公钥技术的研究与实现.pdf

太原理1 人学硕十研究生学位论文 基于e c c 的组合公钥技术的研究与实现 摘要 基于p k i 的认证系统的密钥管理模式已趋于成熟，但随着c a 间的 信任链的加长，出现了信任危机。本文研究的基于椭圆曲线密码系统的 组合公钥技术，对目前最新的组合公钥密钥管理模式，即不通过第三方 认证，无需后台数据库支持就能满足海量密钥管理的需求，进行了详细 的分析。本文针对传统密钥管理模式的缺点，提出了新的解决方案，对 公钥系统研究和实施具有一定的意义。 本文首先介绍了椭圆曲线密码系统的数学基础，包括椭圆曲线的标 准、与r s a 的比较及基于椭圆曲线实现的加密方案等。其次，对原有的 基于椭圆曲线加密系统的组合公钥技术( c p k ) 的理论进行了研究，内 容涉及组合公钥技术的各个组成模块。最后，基于该理论，本文实现了 c p k 系统的主要模块。在实现过程中，对椭圆曲线的参数的选择算法、 私钥因子矩阵及私钥生成算法进行了探索。本文作者改进了私钥因子产 生的方法及由私钥因子生成用户私钥的算法，新的方法可避免计算私钥 时产生的碰撞，比较原方案更具有可行性。 本文实验基于f c l i n t c ( f u n c t i o n f o r l a r g e i n t e g e r s i n n u m b e r t h e o r y a n d 太原理f ：人学硕十研究生学位论文 c r y p t o g r a p h y ) 数论软件包，该软件包理论卜支持任意大的整数运算。该软 件包提供了基本的数学和数论函数，可对不同安全强度的算法进行实现。 关键词椭圆曲线密码系统，种子公钥，组合公钥，公钥因子，私钥因子 i l 太原理1 大学硕十研究生学位论文 r e s e a 。r c ha n di m p l e m e n t a t i o no fe l l i p t i c c u r v ec r y p t o g r a p h y b a s e dc o m b i n e d p u b u ck e yt e c h n i q u e a b s t r a c t k e ym a n a g ep a t t e r no fp k i b a s e dc e r t i f i c a t i o ns y s t e mh a sb e e nu s e d w i d e l y b u tt h e r ei st r u s tc r i s i sa m o n gt h ec a sw i t ht h ei n c r e a s i n go ft h et r u s t c h a i n s i nt h i st h e s i s ，e c c - b a s e dc o m b i n e dk e yt e c h n i q u ei ss t u d i e da n da n e wk e ym a n a g e m e n tp a t t e r nw h i c hs u p p o r t sl a r g es c a l ek e y sm a n a g e m e n t w i t h o u ts u p p o r t i n gb yb a c k g r o u n dd a t a b a s ea n da u t h e n t i c a t i o nb yt h et h i r d p a r t ，i sp r o p o s e d c o n t r a s t i n gt ot h e t r a d i t i o n a lk e ym a n a g e m e n t ，t h i sn e w s o l u t i o nf o r k e y sm a n a g e m e n t h a s g r e a ts i g n i f i c a n c e f o rr e s e a r c ha n d i m p l e m e n t a t i o no ft h ep u b l i ck e ys y s t e mi no u rc o u n t r y a tt h ef i r s t ，t h et h e s i si n t r o d u c e st h em a t hb a s eo fe l l i p t i c c u r v e ， i n c l u d i n gs t a n d a r d so fe c c 、c o m p a r i n gw i t hr s a a n ds o l u t i o nf o re c c s e c o n d l y , t h et h e s i ss h o w st h ea r c h i t e c h t u r eo fc p k b a s e do ne c c ，i n c l u d i n g e v e r ym o d u l e a tl a s tb yr e s e a r c h i n go nt h ee c c - b a s e dc p kt e c h n i q u e ，t h e a l g o r i t h mf o rs e l e c t i n ge c cp a r a m e t e r sa n dt h em e t h o df o rg e n e r a t i n ga p r i v a t ek e yu s i n gs e c r e ts e e d e dm a t r i xa r ee x p l o r e dd u r i n gi m p l e m e n t a t i o no f t h et e c h n i q u e s p e c i a l l y , a n o t h e rn e wa l g o r i t h mf o rg e n e r a t i n gap r i v a t ek e y l 太原理1 人学硕十研究生学位论文 u s i n gs e c r e ts e e d e dm a t r i xi sp r o v i d e d t h en e wa l g o r i t h mc a na v o i d t h e c o l l i s i o no fc a l c u l a t i n gp r i v a t ek e y , w h i c hm a k e st h eo r i g i n a lt e c h n i q u e f e a s i b i l i t y i nt h i st h e s i s ，e x p e r i m e n t sa r eb a s e do nf c l i n t c ( f u n c t i o nf o rl a r g e i n t e g e r s i nn u m b e rt h e o r ya n dc r y p t o g r a p h y ) p a c k a g e ，w h i c hc o u l d i m p l e m e n t t h eb i gn u m b e ro p e r a t i o nt h e o r e t i c a l l y t h ep a c k a g ep r o v i d e sm a t h a n dn u m e r i c a lt h e o r yf u n c t i o n s ，w h i c hc o u l ds u p p o r tt h ei m p l e m e n t a t i o no f a l g o r i t h mo nd i f f e r e n ts e c u r i t yl e v e l k e y w o r d se l l i p t i cc u r v ec r y p t o g r a p h y , s e e d e dp u b l i ck e y , c o m b i n e d p u b l i ck e y , p r i v a t ek e yf a c t o r , p u b l i ck e yf a c t o r 太原理1 入学硕十研究生学位论文 符号说明及缩写 a n sjk m e r i c a nn a t i o o aj s t a n d a r d sir s t i t u t e c p k c o m b i n e dp u b l1ck e y c r y p ir f ：cc r y p t o g r a p h i cr e s e a r c ha n de v a l u a ti o nc o m m i t t e e d l p d i s c r e t el o g a r i t h mp r o b l e m e c c e 1 1 i p t i cc u r v ec r y p t o g r a p h y e c d h e 1 l i p t i cc u r v ed i f f i e h e l l m a n e c d l p e 1 1 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 m q v e l l i p t i cc u r v em e n e z e s q u v a n s t o n ek e ya g r e e m e n t f c l i n t cf u n c t i o nf o rl a r g ei n t e g e r si nn u m b e rt h e o r ya n dc r y p t o g r a p h y f i p s f e d e r a li n f o r m a t i o np r o c e s s i n gs t a n d a r d s i e c i n t e r n a t i o n a le 1 e c t r o n i c a lt e c h n i c a lc o m m i s s i o n 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 i e t fi n t e r n e te n g i n e e r i n gt a s kf o r c e i f p i n t e g e rf a c t o r i z a t i o np r o b l e m i s o i n t e r n a t i o n a lo r g a n i z a t i o nf o rs t a n d a r d i z a t i o n n e s s i en e we u r o p e a ns c h e m e sf o rs i g n a t u r e s ，i n t e g r i t ya n de n c r y p t i o n n i s tn a t i o n a li n s t i t u t eo fs t a n d a r d sa n dt e c h n o l o g y p k ip u b l i ck e yi n f r a s t r u c t u r e p s m p u b l i cs e e d e dm a t r i x 。 s e c s t a n d a r d sf o re f f i c i e n tc r y p t o g r a p h yd o c u m e n t s s e c g s t a n d a r d sf o re f f i c i e n tc r y p t o g r a p h yg r o u p s p ks e e d e d - p u b li ck e y s s m s e c r e ts e e d e dm a t r i x w t l s w i r e l e s st r a n s p o r tl a y e rs e c u r it y r p r i m ef i e l d a 饵) d i s c r i m i n a n to fe l l i p t i cc u r v e j ( e )- ，i n v a r i a n to fe l l i p t i cc u r v e c h a r ( f ) c h a r a c t e ro ff i n it yf i e l d ( _ ) l e g e n d r e s y m b o l i 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外。本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：李善日期：塑丑：! ! ! ! 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名： 导师签名： 挣、日期：塑r p 太原理i ：人学硕+ 研究生学 上论文 1 1e c c 及其标准 第一章引言 每种公钥体系都基于一个难解的数学难题，具有代表性的三种算法体制分别是： 夺整数因式分解体制( i f p ) ，基于大整数因式分解的困难，如：r s a ； 夺离散对数体制( d l p ) ，基于有限域离散对数计算的困难性，如：e i g a m a l ； 冷椭圆曲线离散对数体制( e c d l p ) ，基于有限域上椭圆曲线离散对数计算的 困难性，如e c c 。 e c c 作为一种趋于成熟的公钥技术，正在越来越广泛地应用于安全领域。 1 1 1e c c 简介 椭圆曲线密码( e c c ) 是一种高安全性、高效率的公钥密码，具有) j n 解密、电 子签名和密钥协商等重要的密码功能，可以安全且方便地满足各种信息网络中的用户 身份识别、电子信息的真伪鉴别和保密传输等重要的信息安全需求，是信息安全领域 的核心技术。自1 9 8 5 年由n e a lk o b l i t z 和v i c t o rm i l l e r 提出”1 e c c 以来，由于其相对 于当前主流应用的公钥密码- - r s a 全方面的技术优势( 更强的安全性、更高的实现效 率、更省的实现代价) ，e c c 已经被信息安全产业界视为下一代的公钥密码，其取代 r s a 的趋势不可避免。 e c c 还有椭圆曲线丰富的优点，由于有限域，_ 有数量级为p 的椭圆曲线的同构 类，且同构类数目为： ， m 耳，= 2 p + 2 + ( 罟) 十2 ( 詈) c 卜- ， 1 1 2 e c c 标准 椭圆曲线标准。删嘲大致分为两种形式：一类是技术标准，即描述以技术支撑为 主的e c c 体制，主要有i e e e1 3 6 3 - 2 0 0 0 、a n s ix 9 6 2 、a n s ix 9 6 3 、s e c l 、s e c 2 、 n i s tf i p s1 8 6 2 、i s o i e c1 4 8 8 8 ，规范了e c c 的各种参数选择；另一类是应用标准， 即在具体的环境中建议使用e c c ，主要有i s o i e c1 5 9 4 6 、i e t fp k i x 、i e t ft l s 、 w a p 、) m s 。 n i s t 颁布的标准，有： f i p s1 8 6 2 ：数字签名标准( d s s ) ，标准化了椭圆曲线数字签名算法和推荐 太原理f ：大学硕 研究生学位论文 了1 5 套椭圆曲线域参数。 夺f i p ss p8 0 0 5 6 ：给出了密钥建立方案，包括e c d h 密钥协议和更高级的 e c m q v 协议。 夺f 1 p ss p8 0 0 - 5 7 ：给出密钥管理方案。 a n s lx 9 委员会丌发了美国会融业的标准： 夺x9 6 2 ：椭圆曲线签名法案，它规定了椭圆曲线数字签名算法。要求h a s h 使用s h a - 1 ，椭圆曲线参数n 2 ”，并且使用a n s i 认可的伪随机数发生 器。 夺x 9 6 3 ：列出了e c i e s ( k e yt r a n s p o r t ) 、e c d h 、e c m q v ( k e y a g r e e m e n t ) 各种密码方案。象x 9 6 2 一样，要求h a s h 使用s h a - i ，椭圆曲线参数n 2 ”，并且使用a n s i 认可的伪随机数发生器。 i e e e 开发的典型椭圆曲线标准有i e e e1 3 6 3 2 0 0 0 ，规范了公钥密码系统，基于 e c c 的e c d s a 、e c d h 、e c m o v ，在1 3 6 3 中分别是e c s s a , e c k a s d h l 、 e c k a s - m q v 。 i s o1 4 8 8 8 3 标准的签名方案被确定为l s o 数字签名标准。i s o1 5 9 4 6 草案采用 基于e c c 的密码技术。i s o1 5 9 4 6 - 2 指定了签名方案，包括e c d s a ；i s o1 5 9 4 6 3 指定了密钥建立方案，包括e c d h ，e c m q v 。 加拿大的c e r t i c o m 公司发起的s e c g 组织，包括v e r i s i g n 、m o t o r o l a 、s u n 、p a l m 等公司，开发了s e c l 和s e c 2 的e c c 标准，并且与其它核心e c c 标准兼容。 其它推出e c c 标准的有欧洲的n e s s i e 和e t 本的c r y p t r c c 等。 表卜1e c c 标准 t a b l e1 - 1e c cs t a n d a r d s “ i e e e 1 3 6 3 2 0 0 01 3 6 3 a1 3 6 3 2 c e nt c 3 3 1w g 3 ( d p m ) n e s s l ee c d s a“p s e c ” s e c gs e c ls e c 2 x 9 2 4k e ym a n a g e m e n tx 9 3 7c h e c ki m a g ee x c h a n g ex 9 5 7c e r t m a n a g e m e n t x 9 5 9p a y m e mx 9 6 2e c d s ax 9 6 3k e ye s t a b l i s h m e n t a n s i x 9 f x 9 6 8c o m p r e s s e dc e r t i f i c a t e sx 9 7 3c m sx 9 8 4b i o m e t r i c sx 9 9 0 i r dx 9 9 2e c p v sx 9 9 5t i m es t a m p sx 9 9 6x m lc m s f i p s1 8 6 - 2s i g n a t u r e s0 i c d s a ) s p8 0 0 - 5 6k e ye s t a b l i s h m e n ts p8 0 0 - 5 7 f l p s k e ym a n a g e m e n t f a as e c u r i t y s e c u r i t yn e x tg e n e r a t i o na t n s e c u r ea c a r s i s o1 4 8 8 8 1 5 9 4 69 7 9 6 1 8 0 3 3 l e t fp k l xs m i m e i p s e c ( i r e ) t l s c e1 3 9 4c o n s u m e re l e c t r o n i c sd t c p o m a w t l sw p k i w m l s c r i p t w a p i s i g n a t u r ee n c r y p t i o nk e ye s t a b l i s h m e n t 2 太原理人学颁十研究生学何论文 1 2e c c 同r s a 的比较 e c c 可以在受限制的平台吱现加密曲! 度与r s a 棚”1 的密b q 系统，如：无线设备、 掌l 二 u 脑，智能乍、瘦客户端等。ii 前用幽际上公认的对于r s a 算法最有效的攻击 方法一一般数域筛( n f s ) 方法去破译和攻击r s a 算法，它的破译或求解难度是、亚指 数级的。e c c 算法的数学理论非常深奥和复杂，在工程应用中比较难于实现，但它 的单位安全强度相对较高。用国际上公认的对于e c c 算法最有效的攻击方法 - p o l l a r d - r h o 方法去破译和攻击e c c 算法，它的破译或求解难度基本上是指数级的。 正是由于r s a 算法和e c c 算法这一点明显不同，使得e c c 算法的单位安全强度高 于r s a 算法。从下列n a s 技术报告的比较结果可以看出，r s a 加密系统建议使用 的2 0 4 8 b i t s 密钥方案的加密强度，而e c c 只要提供2 1 0 b i t s 的解决方案就可以满足同 样的加密需求。 表卜2r s a 和e c c 可比较的密钥大小【4 】 t a b l e1 - 2k e ys i z e sc o m p a r a b l es e c u r i t yl e v e lo fr s aa n de c c r s a k e ys i z e e l l i p t i cc u r v ek e ys i z e t i m et ob r e a k ( m i p sy e a r s ) 5 1 2b i t s1 0 6b i i s i n s e c u r e 7 6 8 b i t s1 3 2b i t s 1 0 8 ( n o tr e c o m m e n d e d 、 1 0 2 4b i i s1 6 0b i t s1 0 “ 2 0 4 8b n s2 1 0b i i s 1 0 2 0 2 5 0 0 b i t s2 3 9 b i i s1 0 2 3 2 1 0 0 0b i t s6 0 0b i t s 1 0 7 8 1 3 基于e c c 的c p k 技术同p k i 技术的比较 基于公钥体制的p k i 系统已经比较成熟，相比之下基于e c c 的c p k ( c o m b i n e d p u b l i ck e y ) 系统提出较晚。c p k 技术在第三方认证、后台数据库支持、多层认证体 系结构和管理等方面优于p k i 系统，它解决了大规模密钥管理问题。它可以满足可信 系统中的安全需求，适于在可信环境中应用。 3 太原理i ：大学硕十研究生学位论文 表卜3c p k 与p k i 认证方式的比较1 t a b l e1 - 3c o m p a r i s o no fa u t h e n t i c a t i o nm o d eb e t w e e nc p ka n dp k i 5 1 ”“7 1 c p k p 算法规模住3 2 * 3 2 种子算法规模是百万级的。 资源和规模要求矩阵达剑1 0 ”数聋。公钥矩需要较人的存储资源的支 阵可以放在手机芯片上持，不能放在手机：卷片上 不需要第三方住线认 证。颁发的是i d 证。c a必须第二方在线认让。 第二方认证要求 概念变成了资格认证的后颁发的c a 证悖 台处理 充分实现认证体系的 由于算法规模小，需要 认证体系要求建立数量众多的和多层次 扁平化和聚焦化管理。 的c a 中心 不需要建立专门的认 由于需要实现第三方 认证网络要求 认证，就需要建立个安 证网络。 全、宽带、高速的网络 认证体系的管理和监 管理与成本要求管理简单，成本很低 管复杂，成本较高。 1 4 基于e c c 的c p k 技术研究的意义及现状 当前身份认证技术中应用最广泛的是公钥基础设施。公钥基础设施( p u b l i ck e y i n f r a s t r u c t u r e ，p k d 是网络安全的基础。p k i 是利用公开密钥技术来构建的一种普遍 使用的用来解决网络安全问题的基础设施。传统的p k i 技术在以美国为首的发达国 家，发展较为成熟，发达国家对p k i 体系标准( 技术、运作、互通) 处于主导位置。 p k i 发展存在区域不平衡的问题。我国尚未建立起自己的完善的认证服务体系，2 0 0 5 年4 月1 日，电子签名法的正式实施可以看出国家在认证服务方面向规范化、国 际化发展。 同时，我国也在技术层面积极开发具有独立知识产权的身份认证系统，最具代表 性的就是南相浩教授。1 提出的组合公钥算法c p k ，并在此基础上实现了c p k 认证系 统。它具有破密难度大、处理对象多、资源消耗小、管理简便、密钥本身直接证明标 识的真伪而无需第三方证明的显著优点，在许多场合下不需要第三方认证，即可以得 到可靠使用。 研究c p k 认证系统的主要有q n s ( 屈延文教授、南湘浩教授、孙玉研究员) 工作 室和北京大学信息安全实验室，研究基于c p k 的密钥管理算法优势与问题。屈延文 教授( q n s 工作室) 从2 0 0 3 年开始对c p k 活性认证问题进行研究，在私钥因子矩阵 组合产生私钥时存在的问题：即“存在共谋破解密钥体系的安全威胁”，因此，私钥 的保护成了新的关键课题。根据屈延文教授软件行为学理论，将代理和活性参数 等技术引用到私钥保护上，并开创了代理和密码技术相结合的新思路。q n s 工作室、 4 太原理i ，人学硕十研究乍。- 7 - 何论文 北京大学信息安全实验宅、广东省信息安全产业摹地、北京握奇公司、北京密海公司、 武汉瑞达公司、武汉大学、北京易恒信公司、中兴微 乜r 公司等有关译位为c p k 认 系统的芯，；化、代删化做了f 究，现已研制c p kb u i l t i n 和d e m o 系统。 1 5 主要工作 本文的研究基于椭圆曲线密码系统的组合公钥技术基础。原方案”1 介绍了由私钥 矩阵生成私钥及利用椭圆曲线密码的原理，并没有解决方案的实现细节。通过研究椭 圆曲线的数学基础以及种子矩阵生成密钥的思想，讨论了基于椭圆曲线密码系统的组 合公钥技术的各个实现环节，其中，比较重要的有：椭圆曲线参数的选择( 包括大素 数的确定，椭圆曲线参数a 、b ，基点的选择、阶的计算) 、私钥因子矩阵的选择、私 钥的计算及密钥交换的验证。 本文在实现c p k 系统的私钥因子生成私钥的模块过程中，没有采用原方案设计， 而是采用一个h a s h 函数来计算私钥因子矩阵的坐标，再根据坐标值取矩阵元素来计 算私钥因子，该方法更简洁、易于实现。 1 6 论文的章节安排 据 本文全文分5 章： 第一章为引言，总体介绍研究课题的意义及综述； 第二章介绍数学基础以及椭圆曲线密码系统的应用； 第三章介绍基于e c c 的c p k 技术实现的理论研究； 第四章给出实现过程中使用的数论包介绍，具体算法描述及其实验相关内容、数 第五章为总结及展望。 5 太原理i ：人学硕十研究生学位论文 2 1 椭圆曲线 第二章椭圆曲线公钥技术基础 椭圆曲线的研究“”“2 1 源于周长的计算问题，及椭圆积分 隆 o e o ) 其中，f 一指x 的三次方或者四次方多项式，这类积分不能用初等函数来表示。 椭圆曲线指的是由w e i e r s t r a s s 方程： y 2 + a l x y + a 3 y x 3 + a 2 x 24 - a 4 x + a 6 ( 2 一1 ) 所确定的平面曲线。其中，幻、口，a 2 、a 4 、a 6 e f ，一f = 凹6 叻q 是一素数，是有限 域的特征，f 是有限域的代数闭域。 设弘仉令j = 善，= 三将( 2 1 ) 转换为射影平面方程 f ( x ，y ，z ) 一y 2 z + a 1 x y z + a 3 y z 3 - x 3 一a 2 x 2 z a 4 x z 2 一a 6 2 3 ( 2 2 ) 如果方程组： o f 。0 疆 一a f 0 及f ( ) ( y z ) ：0 a y 、。7 a f 。0 a z ( 2 3 ) 无解时，则f ( ) 【，y z ) = 0 的所有非奇异点，加上一个无穷远点d = ( 0 ，1 ，o ) ，构成一条 光滑曲线。 方程( 2 一1 ) 确定的椭圆曲线称为椭圆曲线的仿射方程，而( 2 2 ) 确定的椭圆曲线称 为椭圆曲线的射影方程。 椭圆曲线( 2 - 1 ) 的判别式饵) 和不变量j ( e ) ： fb ，t 口；+ 4 a 2 lb 4 4 1 4 3 + 2 a 4 1b 。- 巧2 + 4 a ； 1 6 8 一口；口6 + 4 n2 口6 一a 1 4 3 口4 + 4 2 ；一口4 2 fc 4 6 ；一2 4 b 4 1 c 6 6 ；一3 6 b 2 b 4 2 1 6 b 6 以及： 6 太原理l + 人学硕十研究生学忙论文 f ( ) = 一6 ；6 。一8 b ；一2 7 6 ；+ 9 b ：b ；b 。 1肛) ；以 ：1 椭匠l 曲线( 21 ) 的判别式a ( e 1 0 呵以判断椭圆曲线是光漪的或 奇片的；根 掘椭圆曲线旧构可知不变量桐等。反之，具有柏i d 不变量的椭唰曲线一定在代数闭域 - p 上同构。 当有限域的特征c h a r ( d 2 、3 时通过代换 一丧6 ： y = y - 之- ( x z 1 2 b ：) 一弘1 石，y 换成z ，y 后可以将仿射方程( 2 一1 ) 变换为： y 2 一工34 - a x + 6 ，a ，b e f ( 2 - 4 ) 则椭圆曲线方程( 2 - 1 ) 与方程( 2 4 ) 是同构的。本文在以后的讨论中将采用( 2 4 ) 形式 的方程。 对应的的判别式( e ) 和不变量以吵： 。 a ( e ) - 1 6 ( 4 a 3 + 2 7 b 2 ) ，(e)一百-1748(4a) ( 2 5 ) 以下是椭圆曲线图像例子，如图2 - 1 、图2 - 2 ： 图2 - 1y 2 一石3 一x f i g u r e2 - 1y 2 - z 3 一z 7 太原理j 人学硕十研究生学位论文 图2 - 2y 2 ；石3 一石+ 6 f i g u r e2 - 2y 2 一x 3 一石+ 6 2 2 椭圆曲线上点的群运算法则 给定椭圆曲线方程：y 2 。工3 + a x + 6 ， a ，b f 确定椭圆曲线e ，利用椭圆曲线e 可构造a b l e 加法群“叼，零元就是无穷远点o 。 椭圆曲线e 构成一个a b e l 加法群，o 为其单位元。简单的说，椭圆曲线群的这 一运算法则就是：若椭圆曲线上的三个点，处于一条直线上，那么，它们的和就为0 。 由此可以得出有关椭圆曲线群的运算法则。 设e 是椭圆曲线，d 无穷远点，定义： 1 ) 对v p e e ，o + p i 尸+ o - o ； 2 ) 一d o ： 3 ) 对v p e e ，p i 1 ，y 1 ) - 0 ，令一尸= 0 1 ，- y 1 ) ； 4 ) 如果q 一一p ，令_ p + q 一0 ； 5 ) 如果p 0 ，q 0 ，q _ - p , p 一 ，y ，) ，q - 0 2 ，y ：) ，定义： 尸+ q 1 r o ，y 3 ) ，贝u ： ! 工3 一k 2 一一工2 i y 3t k ( x l - - x 3 ) 一y 1 椭圆曲线上点的加法示意图 七； z 2 二强p _ q 屯一 3 x = _ 2 + 一a ，p ；q 2 y 1 8 太原理1 人+ 硕十一研究生学何论文 点p 与p 的定义如图2 - 3 所小 图2 - 3p 与一p f i g u r e2 - 3p a n d - 1 当p - q 时，r p + q ，即点加运算如图2 4 所示： 一一日t 2 j 3 - o 图2 - 4r = p + q f i g u r e2 - 4r = p + q 9 太原理l ：人学硕士研究生学何论文 当p q 时，r = 2 p ，即倍点运算如图2 - 5 所示 图2 - 5 r = 2 p f i g u r e2 - 5r = 2 p 定义了椭圆曲线的点运算后，就可以进行点的数乘运算。若n 是一个正整数，p 是椭圆曲线的一个点，则数量乘法n p 就是对点p 自身累加n 次。数乘运算具有周期 性：在椭圆曲线中，若对某一自然数n ，有n p d ，则对m ，捍，有m p o - m ) p 。 特别的，对于椭圆曲线上任意一点p ，存在一个最小的正整数i n ，使得m p - 0 ， 我们定义小为点p 的阶。在讨论椭圆曲线的安全性时，主要计算椭圆曲线上点p 的 阶。 2 3 用到的相关数学概念 l 、迹与f r o b e n i u s 自同态变换 在判断椭圆曲线的安全性的时候，我们一般先计算出椭圆曲线在有限域上的有 理点数，然后再判断曲线的安全性，习惯上我们称这个点数为椭圆曲线的阶，以符号 # e ( 厢) 表示，由h a s s e 定理可知： 群e ( f 臼) 一q + 1 一t ，i t i s 2 目，其中t z e ( f ) ( 2 6 ) 为椭圆曲线玎一次f r o b e n i u s 同态映射的迹，快速、有效的计算椭圆曲线的阶是一 个很困难的问题。而计算椭圆曲线的阶实质上就是计算上面的t ，根据h a s s c 定理就 可以直接得到椭圆曲线的点数。 椭圆曲线的另一个重要概念是所谓的f r o b e n i u s 自同态，即椭圆曲线经过q 一次 f r o b e n i u s 变换之后将会回到曲线原来的方程上，假设椭圆曲线e ，定义在有限域助 1 0 太原理j 人学硕十研究，t 学何沧文 f e ( 厢) 一e ( 的j 妒： ( x ，_ ) ，) h ( x 4 ，y4 ) 【 o o 可以看出，椭圆曲线e 上的点经过q 一次f r o b e n i u s 同态变换之后又回到椭圆曲线 妒2 一p 】伊+ 【q 】；【0 】 ( 2 7 ) 也就是说，对曲线e 上的任意点p o ，y ) ，我们有： 0 ”，y 矿) 一 t l ( x 9 ，y 9 ) + 【q 1 0 ，y ) 一o ( 2 - 8 ) 除法多项式1 ；f ，一【州，为一个首一多项式，当一为奇数时 d e g ( 妒。) 。掣； 当f q 的特征c h a r ( o * z 、3 时，椭圆曲线e ：y 2l + 甜+ b ，珥6 ，的一 妒3 3 x 4 + 6 a x 2 + 1 2 k a 2 妒4 4 y ( x 6 + 5 a x 4 + 2 0 h 3 5 a 2 工2 4 a b x 一8 b 2 一a 3 ) 妒2 。+ li 妒。+ 秒：一妒。一l 妒i l ，n 苫2 。虹殖昔赴 挑 一警，型铲) 如前面定义的多项式妒。，妒，妒：，妒。，妒：。有 1 ) 妒h + 1 是环z p ，b ，工，y2 】中的多项式； 2 ) 监是环z 【d ，6 ，x ，y z 】中的多项式； 太原理j ：大学硕十研究，学位论文 方程y 2 ；z 3 + a x + 6 对妒：。或妒：。进行约化后所得的多项式为妒：。和妒：。，即记 妒2 n + li 妒2 n + l m o d e 妒二- 监m o d e y 令 g ) = 妒：我们称多项式， o ) 是椭圆曲线e 的n 次除多项式。 在s e a 算法中我们还要用到所谓的模多项式，该式是一个关于工，y 对称的多项 式，而且不依赖于椭圆曲线的方程而独立存在，所以对每一个不同的素数f 可以预先 计算出其对应的模多项式并存储下来以备计算的时候调用。 2 4 椭圆曲线的离散对数问题 e c c 是基于椭圆曲线离散对数难题e c d l p 的密码体制。1 。椭圆曲线及其参数定 义如下所示： 设砟上椭圆曲线e ：y 2i x 3 + 瓤+ b m o d p ，a ，b ，x ，y b 。 参数：t 一和，b ，g - ，y ) ，月，力 私钥：七 公钥：k g q 其中，g 是基点，n 是基点的阶，p 是素数。 给定点g e ( 0 ) ，找一个数岛使得七g e ( 0 ) ，k 即在椭圆曲线e 上以g 为 基k g 的离散对数。椭圆曲线离散对数问题就是在已知g 和q 的情况下，求解k 是很 困难的。 2 5 选择安全的椭圆曲线 对于椭圆曲线离散对数难题，数学家们一直在寻找其求解有效办法，对e c d l p 问题进行攻击。 c e r t i c o m 公司1 9 9 7 年11 月起发起的对椭圆曲线密码的挑战，在给定椭圆曲线 口f 参数、公钥后，寻找e c c 的密钥。挑战可以使用域。2 _ 或1 ，来进行。而且挑战分两 个级别，级别一包含1 0 9 b i t s 和1 3 1 b i t s ，级别二包含1 6 3 、1 9 1 、2 3 9 和3 5 9 b i t s 。现在， e c c p 一1 0 9 于2 0 0 2 年1 1 月被攻破，花费了1 0 0 0 0 台p c 机2 4 小时运行5 4 9 天。 e c c p 1 3 1 还没有被攻破，需要花费比1 0 9 b i t s 更多的资源。级别二挑战被认为在计 算上是不可行的。 为了建立安全的椭圆曲线加密系统“”，需要选择椭圆曲线时考虑安全性：不能 选择奇异的曲线，否则易于转化为离散对数问题来求解；椭圆曲线不能是“畸形”曲 太原理t 人学硕十研究生学位论文 线，可防止s m a r t 攻击；不能选择超奇异椭圆曲线，这样可以保f 抗m o v 攻击。选 择时，椭恻曲线的阶要有大的系数冈f ，素冈f 人于2 ，这样r 叮以保证抵抗p o l l a r d r h o 奴惫矗t ， 以上町以看出，选择安伞的椭圆曲线足建、z 安全系统的重受蚪肯。 2 6 基于椭圆曲线的加密方案 用m a s s c y o m u r a 方案”说明椭圆曲线在加密通信中的应用。 椭圆曲线e ：y 2 。z 3 + 甜+ b m o d p ，参数：丁t 和，b ，g 一y ) ，h ，办。各用户自 己随机选取密钥对，用户a 将信息p 。加密送到用户b a 用户a # 随机选择加密密钥c a ，o e a n ，g c d ( e a , n ) = i ； 。 再求脱密密钥d a ，d 一p ? m o d n 。 用户b ：随机选择加密密钥e b ，o c b n ，g c d ( c b ，n ) = 1 ； 再求脱密密钥d b ，d 口一p m o d n 。 如果用户a 将随机的点p m 送到用户b ，则 用户a ：计算e 。只一k 1 ，送给b ； 用户b ：计算e b k l - k 2 ，k 2 - e a 己，将k 2 返回给a ； 用户a ：计算d k 2 - k 3 ，k 3 - 己，将k 3 返回给b ； 用户b ：计算d 。k 3 一只。 2 7 基于椭圆曲线的签名方案 基于椭圆曲线加密系统的数字签名算法模拟叫( e c d s a ) 过程如下： 椭圆曲线e ：y 2 ；工3 + a x + b m o d p ，参数：t p ，b ，g 一 ，y ) ，以，p 。设a 的私 钥为办，公钥为办g = 办，签名验证过程如下。 1 ) 签名过程 a ) 选择整数k ，o k m b ) 计算k g ；“，y 1 ) ，r 一工l r o o d n ；如果r = 仉则返回第a ) 步； c ) 计算t r o o d n ； d ) 计算j 一七- 1 伽+ d a r m o d n ；h 是文件的h a s h 码； e ) 如果s = 毋则返回到第a ) 步； f ) 对h a s h 码h 的签名码是一对整数似s ) 。 2 ) 验证过程 。 a ) 检查r 和s ，是否o g s 2 5 6 时，需要h a s h 函数计算d a t a l 时，增加h a s h 值的长度，来计算更大的行坐标。 3 ) 列置换算法 c p k 的组合密钥生成要求每一列取一个元素，共取出h 列中的h 个元素组合 成一个密钥。行坐标是一个模m 的随即序列；列坐标是一个h 元的置换。若不选 取列置换算法，则列坐标序列为h 元的单位置换。若选用列置换算法，则使列坐 标序列成为一个h 元的随机置换。 列置换算法是基于标识的随机置换生成算法。列置换算法构成包括置换指示 码生成和随机置换生成两部分。 幻置换指示码生成算法 对d a t a l 做h a s h 运算生成h 个字节的定长值d a t a 2 。按字节对应取的值作为 蜀换指示码序列( x o ，x l ，x h - i ) 。 b 1 随机置换生成算法 已知置换指示码序列后，可以将原来的单位置换变成新的置换，得到新的列 坐标