（计算机应用技术专业论文）超椭圆曲线密码体制的优化与设计.pdf

超椭圆曲线密码体制的优化与设计中文摘要 中文摘要 超椭圆曲线密码体制作为椭圆曲线密码体制的一个推广，它的安全性是建立在超 椭圆曲线离散对数问题难解性上的。与其他公钥密码体制( 如r s a e c c ) 相比，它 的密钥长度更短、安全性更高，随着亏格的增大，安全曲线也就越多，且可以模拟如 d s a 等几乎所有的协议。因此，超椭圆曲线密码日益受到人们的关注与重视，正成 为公钥密码学一个新的研究热点。 本文主要针对特征为2 域、亏格为2 的超椭圆曲线密码体制，对其进行了研究与 优化。首先，对标量乘和复合标量乘k d 。+ l d ，运算进行研究与优化；接着，为使通信 方在交换安全的数据前就如何交换与保护信息达成一致，本文设计了密钥协商协议； 为保证数据在传输过程的安全性，设计了加密协议；为使接收方能够向第三方证明其 收到消息的完整性和发送源的真实性，设计了数字签名协议。在上述研究基础上，本 文根据具体应用要求进行密码方案的设计。基于已设计的数字签名协议，设计了一个 具有前向安全性、高效的盲数字签名方案。最后，在上述优化与设计的基础上，设计 和实现了一个超椭圆曲线密码系统，并将其应用于文件传输的设计中。 实验表明，本文的优化和设计工作，使超椭圆曲线密码系统的执行效率和安全性 在一定程度上得到了提高。因此，本课题的研究对超椭圆曲线密码走向实用化具有积 极的意义。 关键词：超椭圆曲线密码，域运算，标量乘，密码协议 作者：陈玉春 指导教师：朱艳琴 a b s t r a c tt h eo p t i m i z a t i o na n dd e s i g no ft i l eh y p e r 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 t h e h y p e r 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 i sa l l e x p a n s i o no f t h ee l l i p t i cc u r v e c r y p t o g r a p h y , i t ss e c u r i t yi sb a s e do nt h ed i f f i c u l t yo fs o l v i n gt h eh y p e r e l l i p t i cc u r v e d i s c r e t ep r o b l e m c o m p a r e dw i t ho t h e rp u b l i ck e yc r y p t o g r a p h y , h e c ch a sa d v a n t a g e so f s h o r t e rk e ys i z e ，h i g h e rs e c u r i t y , a n dm o r ec u r v ea l o n gw i t hl a r g e rg e n u s i tc a na l m o s t s i m u l a t ea l lp r o t o c o l ss u c ha sd s a t h e r e f o r e ，m o r ea n dm o r ep e o p l ea r ea t t r a c t e db yt h i s t a s k , a n di th a sb e c o m et h en e wh o t s p o to ft h ep u b l i ck e yc r y p t o g r a p h y t h em a j o rw o r ko ft h i sp a p e ri st h er e s e a r c ho fh e c co v e r 只a n dg e n u st w o f i r s t l y , t h es c a l a rm u l t i p l i c a t i o na n dt h ec o m p l e xo p e r a t i o n k d l + i d 2 a r eo p t i m i z e d t h e nw ed o s o m er e s e a r c ho nt h eb a s i cp r o t o c o l s f o rm a n a g i n gt ob ec o n s i s t e n ta b o u te x c h a n g ea n d p r o t e c t i o no ft h ei n f o r m a t i o nb e f o r es a f e l ye x c h a n g i n gd a t a ，w ed e s i g nt h ed i f f i e h e l l m a n p r o t o c o l ；f o rk e e p i n gs a f ei nt h ep r o c e s so ft r a n s m i t t i n gd a t a ，w ed e s i g nt h ee n c r y p t i o n p r o t o c o l ；f o rp r o v i n gt h ei n t e g r a l i t yo ft h en e w sa n d t h er e l i a b i l i t yo fs e n d i n gs o u r c e ，w e d e s i g nt h ed i g i t a ls i g n a t u r ep r o t o c 0 1 u p o nt h ea b o v ew o r k ，w ed e s i g nac r y p t o g r a p h y s c h e m ea c c o r d i n gt o p r a c t i c a lr e q u i r e m e n t s b a s e do nt h eh y p e r e l l i p t i cc u r v ed i g i t a l s i g n a t u r ep r o t o c o l ，w ed e s i g nab l i n ds i g n a t u r es c h e m ew h i c hi se f f i c i e n ta n dh a sh i g h e r s a f e t y a tl a s t ，a c c o r d i n gt ot h ea b o v eo p t i m i z a t i o n sa n di m p r o v e m e n t s ，ah y p e r e l l i p t i c c u r v ec r y p t o g r a p h yi si m p l e m e n t e da n di sa p p l i e di n t of i l et r a n s f e rd e s i g n e x p e r i m e n ts h o w s ，a so p t i m i z a t i o na n dd e s i g no ft h i sp a p e r ，t h ee f f i c i e n c ya n ds e c u r i t y o ft h eh y p e r e l l i p t i cc u r v ec r y p t o g r a p h ya r ei m p r o v e di nac e r t a i ne x t e n t t h e r e f o r e ，i ti s s i g n i f i c a t i v ef o rh e c ct u r n i n gt op r a c t i c a l i t yb yt h er e s e a r c ho ft h ep a p e r k e yw o r d s ：h y p e r e l l i p t i cc u r v ec r y p t o g r a p h y ，f i e l do p e r a t i o n s ，s c a l a rm u l t i p l i c a t i o n ， c i p h e rp r o t o c o l w r i t t e n b y ：c h e ny uc h u n s u p e r v i s e db y ：z h uy a nq i n 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名： 强趁盎 日 期：匕翌：丛习 学位论文使用授权声明 苏州大学：中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 陉垒鑫 日 期：幽：! ! ! 型 导师签名： 日期：竺必! 兰兰 超椭圆曲线密码体制的优化与设计 引言 引言 随着互联网的迅猛发展，人们愈发地离不开网络，可以很便捷地从网络获取很多 免费资源。但也存在一些问题，信息在网络传输的过程中极易受到其他外来攻击。对 于这些攻击，我们应该采取预防的办法防止它们的入侵。在利用公开性网络进行通信 或商业活动时，将面临一个非常大和现实的问题，这就是如何保证信息的安全性、认 证性和完整性。密码技术是一种有效的方法，它可以应用于数据加密、数字签名、信 息认证等过程，从而有效地预防和防止网络攻击。因此，研究密码学有着很积极的意 义。 密码技术是信息安全的核心技术，而密码体制大致可分为非对称密码和对称密码 两种。其中，以d e s 为代表的对称密码体制是属于传统密码技术，但这类密码系统 有个弱点，通信前双方需要进行密钥协商，非法入侵者很容易利用这个协商过程窃取 密钥；同时，这类密码系统要求为不同的通信方分配不同的密钥，当用户群很大、分 布很广时，密钥的分配和保存也很成问题。基于这些局限性，以r s a 为代表的非对 称密码体制( 公钥密码体制) 应运而生。公钥密码在信息安全担负着密钥协商、消息 认证、数字签名等重要角色，已成为最核心的密码。 在1 9 7 6 年，d i f f i e 和h e l l m a n 提出了公钥密码体制的思想【l 】。它的主要思想是： 采用两个密钥，一个公开密钥，一个私有密钥。发送方发送信息时用对方的公开密钥 加密，收信方用自己的私有密钥进行解密。在公钥密码系统中，加密和解密使用的是 不同的密钥，但这两个密钥之间也存在着相互依存关系，即用任一密钥加密的信息只 能用另一密钥解密。这使得通信双方无需事先交换密钥就可进行保密通信。因为加密 密钥和算法是对外公开的，人人都可通过这个密钥加密文件然后发送给收信方，这个 加密密钥称为公钥；而收信方收到加密文件后，可用他的解密密钥解密，这个密钥是 由他私人掌管的，不需要分发，因而称为私钥，这也就解决了密钥分发的问题。非对 称密码体制问世后，出现了很多种公钥密码体制，它们的安全性都是基于复杂的数学 难题。目前比较流行的公钥密码体制主要有两类：一类是基于大整数因子分解问题的， 其中最典型的代表是r s a 体制：另一类是基于离散对数问题的，如e 1 g a m a l 公钥密 码体制和影响比较大的椭圆曲线公钥密码体制及超椭圆曲线密码体制。r s a 是基于 引言超椭圆曲线密码体制的优化与设计 大整数分解成两个素数的困难问题构造的体制。虽然大整数因子分解问题是一个数学 难题，但随着数论的研究和计算能力的提高，大整数因子的分解速度也越来越快。为 保证系统的安全性，必须采用更长的密钥，而位数的增加带来加解密及签名验证运算 量的增大，同时也带来存储空间和数据传输量的增大，这将进一步降低整个系统的性 能和效率，这就阻碍了r s a 在实际中的应用和发展。 椭圆曲线密码体n t 2 1 t 3 1 是建立在椭圆曲线离散对数问题上的，其安全性基于离散 对数问题的难解性。e c c 相对于r s a 而言，密钥长度短，安全性更高。它的另一个 优势是可以定义群之间的双线性映射，基于w e i l 对或t a t e 对。r s a 所基于的大整数 因子分解问题只是亚指数级，而对于e c c 密码算法来说，只需1 6 0 位就可达到1 0 2 4 位r s a 算法的安全等级，且它的离散对数问题求解是完全指数级的。椭圆曲线密码 系统在实际环境中也有着很好的应用。 超椭圆曲线密码体制【4 】【5 】理论作为椭圆曲线密码体制的一个推广，是由n e a l k o b l i t z 在1 9 8 9 年提出的。与椭圆曲线密码体制相比，超椭圆曲线密码体制具有明显 的优势：密钥长度更短，带宽更小；在同一有限域内，亏格越大，安全曲线数目也就 越多；它可以模拟如d s a 、e 1 g a m a l 等几乎所有的协议。尽管目前超椭圆曲线密码体 制还没有相关标准和规范，仍有很多问题有待于进一步解决，但它具有其他公钥密码 体制( 如r s a e c c ) 无法比拟的优势，它的发展前景十分广阔。因此，对超椭圆曲 线公钥密码体制的研究，具有十分重要、积极的意义。 本文根据现有超椭圆曲线密码技术的研究成果和相关文献资料，对超椭圆曲线密 码体制进行了研究与优化，并设计了h e c c 的密码协议，根据具体的应用要求设计 优化的密码方案，最后基于该方案设计和实现了一个h e c c 密码系统，并将其应用 于文件传输中。 本论文的研究内容来源于江苏省研究生创新计划项目。 2 超椭圆曲线密码体制的优化与设计 第一章绪论 1 1 研究背景 第一章绪论 帚一早三百i 匕 目前，随着计算机网络技术的飞速发展，为更高效、更广泛的信息交流提供了便 屏0 。如电子商务以高效率、低成本的优势，逐渐成为一种热门的商业经营模式。但在 砖 利用像i n t e r n e t 这样公开性网络进行通讯或商业活动时，一个现实的问题是怎样保障 ： 信息在通信过程中的保密性、完整性等，此时就需要用密码技术来解决。 8 0 年代中期，n e a lk o b l i t z 和v i c t o rm i l l e r 提出了基于有限域的椭圆曲线离散对 数问题的公钥密码。由于在一般的椭圆曲线群中没有亚指数的时间算法解离散性对数 问题，所以椭圆曲线密码体制( e c c ) 引起了人们的极大关注。经过多年的研究与发 展，其技术日益成熟，e c c 也己被一些公司、组织所采纳并应用到一些资源受限的 环境中，如s m a r t 卡、嵌入式系统等。超椭圆曲线密码体制( 髓c c ) 理论作为e c c 的一个推广，是由n e a lk o b l i t z 在1 9 8 9 年提出的，它是基于有限域上超椭圆曲线的 j a c o b i a n 群上的离散对数问题困难性。相对于e c c 而言，h e c c 具有明显的优势：第 一、在相同的安全强度下，h e c c 可以选用更短的操作数、更小的带宽：第二、在同 样的定义域上，亏格越大，曲线越多，可用于构建密码体制的安全曲线数目也就越多； 第三、在同等安全条件下，h e c c 所用的基域小，且可以模拟基于一般乘法群上的如 d s a 、e 1 g a m a l 等几乎所有的协议；第四、h e c c 作为e c c 的一个推广，因此，用 于超椭圆曲线密码上的一些普遍的方法和技术也可用在e c c 上，这对目前已经在实 际中得到应用的e c c 而言，不仅在理论上还是在实践中都是有益的。 尽管h e c c 还处于研究阶段，但它具有e c c r s a 等公钥密码体制无法比拟的优 势，使其迅速成为密码学的研究热点。通过对h e c c 的研究，对进一步完善e c c 是 有益的，同时也可加快超椭圆曲线密码体制由理论过渡到实际的步伐，最终将h e c c 运用于i n t e m e t 和移动通信设备等。 1 2 超椭圆曲线密码体制的研究现状 目前，国内外很多研究机构及公司都开展了关于超椭圆曲线密码体制方面的研 究，但是当前还没有相关的标准。由于超椭圆曲线密码体制展开研究的时间不太长， 且h e c c 是e c c 的一个推广，这些组织在标准文档方面的研究借鉴了e c c 体制的 3 第一章绪论超椭圆曲线密码体制的优化与设计 i e e ep 1 3 6 3 、a n s ix 9 6 2 、a n s ix 9 6 3 等，这些标准对于h e c c 的技术规范研究有 很大的帮助。 1 2 1 国外研究现状 在1 9 8 8 年的美国密码会议( c r y p t o 8 8 ) 上，n e a lk o b l i t z 首次提出了超椭圆曲线 的j a c o b i a n 群适合构造基于离散对数的密码体制的思想，即超椭圆曲线密码体制 ( h e c c ) 。目前国际上主流的公钥加密技术采用的是r s a 密码体制，同时椭圆曲线 密码体制也已经得到业界的广泛认可。但由于h e c c 是一砷非常有前途的公钥密码 体制，很多组织和科研机构都对它进行了研究，尽管当前超椭圆曲线密码体制的研究 进展非常缓慢，在实际生活中也没得到较好的应用。 在国外，一些研究机构和学术团体在超椭圆曲线密码体制实用化方面做了不少研 究。许多学者对超椭圆曲线密码体制理论进行了研究分析，并在软件平台( 如目前各 种通用的处理器以及嵌入式处理器) 以及硬件平台( 如f p g a 等) 上实现了该密码体 制。其中，德国和日本的学者在超椭圆曲线密码体制的软件方面做了大量的研究。自 从h e c c 提出以来，很多学者在提出自己算法的同时也在通用目的处理器上作了相 应的软件仿真。近来，t h o m a sw o l l i n g e r 6 博士等人公开了h e c c 在各种嵌入式处理 器上的软件实现结果及硬件实现结果。g a l b r a i t h t 7 】推广了s m a r t 等人的关于利用w b i l 限制的方法解离散对数问题的想法，将其应用于有限域上亏格大于1 的超椭圆曲线 j a c o b i a n 群。g a u d r y 和h a r l e y 综合各种技术，实现了推广的s c h o o f 算法【8 】，能计算 p = 1 0 1 9 + 5 1 的有限域r 亏格为2 的超椭圆曲线的点数。这是目前s c h o o f 算法计算任 意超椭圆曲线的j a c o b i a n 群阶的最好记录。a n d r e a se n g e l 9 1 对有效计算超椭圆曲线算 术进行了研究与分析，他推广了两个归约算法，并在除子运算中运用了扩展的 e u c l i d e a n 算法。g a l b r a i t h 对定义在偶扩张次数的有限域上亏格为2 的超椭圆曲线体 制给出了一种新的攻击算法a r i t a ，将其应用于亏格为2 的二次孪生超椭圆曲线密码 体制，该攻击算法期望的运行时间比p o l l a r dr h o 算法运行时间要短d p ，但a r i t a 算法的实用性仍没被验证。 a d l e m a n d e m a r r a i s - h u a n g 在1 9 9 4 年将亚指数时间的i n d e x 算法用在高亏格的超 椭圆曲线上，求其j a c o b i a n 的离散对数问题。y a s u y u k is a k a i 1 0 等人对特征为2 有限 域上亏格为2 和1 1 的超椭圆曲线作了许多的探讨，尽管没有具体实现，但给出了许 4 超椭圆曲线密码体制的优化与设计第一章绪论 多与e c c 和r s a 对比的理论数据。另据网上消息，i b m 公司已经着手研发用于超椭 圆曲线j a c o b i a n 群上的计算面向硬件的算法。国外的贝尔实验室、美国数字设备公司 等也开始研究了密码协议的研究。目前超椭圆曲线研究主要集中在小亏格，常见曲线 类型有) ，2 + y 可、y 2 + x y = f ( x ) 箸f 。超椭圆曲线密码体制仍然有很多公开的工程问题有 待解决。但由于h e c c 具有其他公钥系统无可比拟的优点，因此很有必要对它作进 厂步的研究，并将其运用于安全产品和移动通信设备。 1 2 2 国内研究动态； ： 目前，我国的一些高校、科研院所及公司也开始了对超椭圆曲线密码体制进行研 究开发和应用，但是相对于国外而言，对超椭圆曲线密码的研究还处于起步阶段。关 于这方面的资料很少，还有大量悬而未决的问题。信息安全国家重点实验室也己设立 了一些与超椭圆曲线密码技术相关的科研项目，并取得一些阶段性的理论成果。同时， 国家也设立了相关的项目展开对h e c c 进行研究，如国家通信保密基金项目“超椭 圆曲线密码体制研究 、国家9 7 3 项目“基于数学的密码基础理论研究”等。 2 0 0 2 年9 月下旬在海南三亚召开了第8 届通信保密与信息安全现状研讨会，会 破的内容包括了超椭圆曲线公钥密码体制初探。国内的清华大学、上海交大等高校和 科研院所也开始研究密码协议的研究了。西安电子科技大学【l l 】的学者提出了非特征为 2 有限域上超椭圆曲线密码的一个非常有效的概率消息编码方案，并对r 上亏格为2 的超椭圆曲线给出了一个更直观易懂的除子压缩方案，他们在超椭圆曲线j a c o b i a n 上基点的选取问题方面也做了探讨。他们利用f r o b e n i u s 自同态作为工具研究了超椭 圆曲线j a c o b i a n 标量乘的快速运算，并对一些特殊曲线的j a c o b i a n 标量乘进行了分析， 同时提出了适合这类曲线的标量乘快速算法。利用了w e i l 猜想的方法计算有限域r 上亏格为g 的超椭圆曲线在n 次扩域上的j a c o b i a n 群阶的算法。王育民【1 1 】等人提出了 一个基于超椭圆曲线的消息恢复签名方案。张方国【l z l 等人直接利用f r o b e n i u s 自同态 的特征多项式与矿进制表示，提出了一类特殊超椭圆曲线，即特征为2 域且其特征 多项式含有零项的超椭圆曲线上的一种快速除子标量乘算法。 大连理工大学的学者【1 3 】对h e c c 也做了相关的研究，他们将数字签名算法和超 椭圆曲线相结合，提出了超椭圆曲线数字签名算法的一般方程，并给出了一些有效的 签名算法。他们根据m u l l e r 、l a n g e 等人算法的思想，得出了取模r n l 与取模f 一1 ) ( r - 1 ) 5 第一章绪论超椭圆曲线密码体制的优化与设计 后的乘子的r 一展开式长度的上界，给出了一般超椭圆曲线上的除子标量乘快速算法。 同时，他们还利用f r o b e n i u s 自同态原理，将有理点标量乘的乘子作f r o b e n i u s 展开， 提出了小亏格的标量乘算法。 尽管目前超椭圆曲线密码理论还需继续深入研究，且在实用化方面进展缓慢，但 由于它有广阔的前景，因此仍引起密码学界的广泛关注。 1 3 本课题的研究内容及意义 1 3 j 研究内容 本文将在分析传统公钥密码体制的基础上，对超椭圆曲线密码体制进行研究。首 先，对已有的h e c c 算法进行优化，同时根据椭圆曲线密码协议研究成果和其他密 码体制协议的资料设计超椭圆曲线密码协议；然后，在此基础上实现密码系统。本文 的研究内容主要包括以下几个方面： ( 1 ) 研究超椭圆曲线密码体制的数学理论背景、相关密码算法和基本密码概念及 相关理论 分析现有的h e c c 研究成果，阅读了h e c c 的相关文献资料，了解超椭圆曲线 密码体制的数学理论背景和基本概念，掌握相关的主要算法和技术。 ( 2 ) 研究、分析h e c c 的主要算法，并对其进行优化与改进 在超椭圆曲线密码体制中，最重要且最耗时的运算是标量乘，它决定了整个密码 系统的运行效率。本文对标量乘运算和复乘运算进行优化与改进，并从理论和实验两 个方面对改进的算法进行分析，得出改进后的效率。 ( 3 ) 设计h e c c 的基本协议 对现有的h e c c 协议方面的研究成果进行分析，同时结合其他传统公钥密码体 制协议，如r s a e c c 基本协议，根据超椭圆曲线密码体制的实际情况，设计出h e c c 的基本协议：密钥交换协议、加密协议和数字签名协议。 ( 4 ) 设计基于数字签名的密码方案 要使超椭圆曲线密码体制技术得到更好地发展，并且在实际中得以推广应用，就 需要有相应的密码方案的支持。本文根据目前已有的h e c c 方案研究成果，并参照 椭圆曲线密码体制方案的相关技术，设计基于数字签名的盲签名方案。 ( 5 ) 超椭圆曲线密码系统的实现 6 超椭圆曲线密码体制的优化与设计第一章绪论 本文基于( 2 ) 、( 3 ) 中对h e c c 标量乘算法和复合标量乘算法的优化及协议的 设计，实现了超椭圆曲线密码系统，并将其应用于文件传输中。 1 3 2 研究意义 随着互联网技术的普及和迅速发展，网络安全问题越发突出。采用密码技术是保 护信息安全的主要手段之一，目前在实际中有着广泛的应用。尽管目前欧美等发达国 家在密码学理论和应用研究方面上都处于世界领先地位，在超椭圆曲线密码技术也取 得了很大进展，但往往出于技术垄断等原因，对我国采取禁运和拒绝尖端技术的交流。 同时由于我国在密码技术产品管理上实行专控，不能使用进口技术和产品。且要提高 我国的高科技研究能力，掌握属于自己的知识产权。因此，开展对超椭圆曲线密码体 制理论及应用的研究，开发出具有知识产权的密码产品，对我们具有及其重要的现实 意义。 超椭圆曲线密码体制作为椭圆曲线密码体制的推广，而椭圆曲线密码体制是建立 在亏格为1 的椭圆曲线上的。因此，超椭圆曲线密码体制是建立在亏格大于1 的超椭 圆曲线上的。开展对超椭圆曲线密码的研究，不仅深化了h e c c 的理论和实践，而 且将进一步推动e c c 的发展和应用。 乙 1 4 论文的组织结构 本文的结构安排如下： 第一章：绪论。介绍了研究超椭圆曲线密码体制的历史背景，并指出h e c c 相 对传统公钥密码体制( 如r s a e c c 等) 具有的优势，同时分析了当前国内外h e c c 的研究现状，最后提出本文的研究内容、课题意义以及论文的组织结构。 第二章：论述超椭圆曲线密码体制的数学背景和密码学理论。介绍超椭圆曲线的 基本数学知识，并分析了超椭圆曲线的j a c o b i a n 群及其元素除子类加的计算方法。 第三章：介绍了超椭圆曲线密码体制的基本理论和基本运算算法。探讨h e c c 基本理论，介绍域运算和超椭圆曲线的j a c o b i a n 群元素除子类的标量乘和复乘运算， 并对其进行了优化与改进，从理论和实验两个方面对优化前和优化后的算法进行比较 分析。 第四章：设计h e c c 的协议和盲签名方案。研究分析了现有的h e c c 协议方面 的相关文献资料，并结合传统公钥密码体制( 如r s a e c c 等) 的相关协议，设计出 7 第一章绪论 超椭圆曲线密码体制的优化与设计 h e c c 的三类基本协议：密钥交换协议、加密协议、数字签名协议。依据具体的应用， 设计了基于数字签名的盲签名方案。 第五章：基于前面的优化算法和相关协议，设计了超椭圆曲线密码系统，并将其 应用到文件传输中，给出相应的测试结果。 第六章：结束语。对本文所做的研究工作进行总结，并对未来的工作进行展望。 超椭圆曲线密码体制的优化与设计第二章超椭圆曲线密码的数学基础 第二章超椭圆曲线密码的数学基础 超椭圆曲线是一类特殊的代数曲线，是椭圆曲线的推广。超椭圆曲线理论是代数 几何、数论和群论等众多数学分支的一个结合点，即属于边缘学科理论。超椭圆曲线 密码体制是建立在超椭圆曲线j a c o b i a n 群离散对数问题难解性的基础上的。本章将介 绍超椭圆曲线密码【1 4 】【1 5 】【1 6 】【1 7 1 的数学基础知识及其相关理论。 2 1 超椭圆曲线的概念 超椭圆曲线定义1 8 1 【1 明为：设是一个有限域，i 是其代数闭域，一条定义在 上，亏格为g ( g 1 ) 的超椭圆曲线c 的方程形式表示为：y 2 + h ( x ) y = f ( x ) 。 这里 ( z ) 【叫是次数不大于g 的多项式，( z ) i x 是一个次数为2 9 + 1 的 首一多项式，而且不存在( 石，y ) f f 满足下列方程组： iy 2 + h ( x ) y f ( x ) = 0 2 y + ( x ) = 0 i ( 工) ) 一，( 工) = 0 满足上述方程组的点称为奇异点，但超椭圆曲线上的所有有理点都是非奇异的。其中： g = 1 ，则曲线c 称为椭圆曲线。 2 2 有限域 环定义：如果一个代数系统 的两个二元运算满足以下条件： ( 1 ) 是a b e l 群，即加法交换群( 加法的单位元称为零元) ； ( 2 ) 是半群； c 3 ， 满足分配律c 岛玩c 尺，： ：兰：暑二三元然； 则我们称代数系统 为环。 域定义：如果一个环 ( 口，b ，c g ) 满足以下条件： ( 1 ) g 是一个非空集合； ( 2 ) 有单位元e ，即a 木e = p 木a = a ； ( 3 ) 满足交换律，即 宰b ) 宰c = a 木( 6 宰c ) ； ( 4 ) 对任意的非零元d ，都存在逆元d ，即d 幸d = d 一奉d = e ； 9 第二章超椭圆曲线密码的数学基础超椭圆曲线密码体制的优化与设计 则我们称 为域。 超椭圆曲线可以定义在任何域上，如实数域、复数域等。但在密码学研究中，我 们主要考虑的是有限域上的超椭圆曲线。有限域常见的类型有特征为p 的大素数域 和特征为留的有限域。在本文中，有限域是特征为2 的二进制有限域。 2 2 1 素数域 设p 是一个不为2 的素数，整数集合 0 , 1 ，2 ，3 ，p 一1 构成一个有限域，记为兄。 中元素具有以下运算规则： 加法：如果a , b f 。，则r = ( 口+ 6 ) m o dp ，其中0 r p 一1 。加法的单位元 为0 ，则域元素口的加法逆元为( - a ) m o dp ，即为p a 。 乘法：如果口，b f ，则r = ( 口6 ) m o dp ，其中0 ，p 一1 。乘法的单位元为 1 ，则域l 中非零元素口的乘法逆元b 满足等式：0 扪r o o dp = 1 。 2 2 2 二进制域 由系列所有长度不大于m 的比特串集合构成一个特征为2 的有限域，记为只。 只上的二元运算满足以下规则： 加法：0 ，一i a i a o ) + ( 易，一l b i b o ) = ( c 。一l c l c o ) ，即两个元素的对应比特按位 异或运算。加法单位元是每个比特都为0 的元素，任意一个域元素的加法逆元是它本 身。 一 乘法：( 口。一l a i a o ) p 州b l b o ) = ( c 用一l c 1 c o ) ，乘法运算与一个不可约多项 式厂( 工) = p m - i x ”1 + p r o - 2 x ”2 + p l 工+ p o ( p i 0 ，1 ) ) 相关，且厂( 工) 称为域多项式。其 中( c m l q c o ) 对应的多项式c m - i x ”1 + + c i 工+ c o 是。一l a l a o ) 对应的多项式乘以 p 。一，b l b o ) 对应的多项式再除以域多项式厂( x ) ，即满足下列关系： c m _ 1 x ”一1 + + c l x + c o = ( 口。一l 工”一1 + + 口l x + a o ) ( b m l z m 一1 + b z x + b o ) r o o d 厂( 力 2 3 除子和主除子 2 - 3 1 除子 曲线c 上的除子是曲线上若干点一个有限形式和，即：d = m p p ，m p z ，这 里m p 是整数，且只有有限个m p 是非零的。除子d 的次数定义为系数的和，即： d e g ( d ) = d e g ( m ；只) = m ；，也称之为除子d 的度数。d 在p 点的阶是m p ，表示 1 0 超椭圆曲线密码体制的优化与设计 第二章超椭圆曲线密码的数学基础 为o r d p ( d ) = m p 。 设d 表示c 上所有除子的集合，且d 可形成一个加法交换群，群上的加法可定 义为：m p p + ，l p p = ( m p + ，l p ) 。所有次数为0 的除子形成的集合d 。是_ d 的 p e cp e c p e c 个子群，即子集。 除子有如下几个性质： 帮 性质1 ：设d ，d ：d o ( 。) ，如果( d l d ：) 忍( ) ，那么则称d 。与d ：等价， 记着d l 。d 2 。j i 享 ， 性质2 ：设d 。= m 尸p 和d ：= ，l p p 是曲线c 有限域上的两个险子，则d l 与d ： 的最大公共因子表示为：g c d ( d 。，d ：) = m i n ( m 尸，l p ) s - m i n ( m ，l p ) 。 性质3 ：设d = m p p 是一个有效除子，如果每- - + m 尸o ，则称d 为一个有 p e c 效除子。 性质4 ：设d 。和d 2 是两个除子，如果d l d ：是一个有效除子，则d 。d ：。 2 3 2 主除子 曲线c 的i 。【x ，) 】上多项式r ( x ，y ) 的除子可定义如下： d i v ( r ( x ，) ，) ) = ( o r d 尸r ) f ，其中o r d 尸r 是r ( x ，) ，) 在p 点零化的阶。 毒 有理函数r ( x ，y ) = g ( x ，y ) h ( x ，y ) 的除子d 定义如下： d = d i v ( r ( x ，y ) ) 亍d i v ( g ( x ，y ) h ( x ，) ，) ) = d i v ( g ( x ，y ) ) 一d i v ( h ( x ，) ，) ) 其中d 为0 的除子称为主除子，即d d o 的是主除子。所有主除子构成的集合记为 忍( 。) ，因为主除子的次数为0 ，所以它是d c o ( ) 的一个子集。 主除子( g ( 工，) ，) 一h ( x ，) ，) ) 是由有理函数g ( x ，y ) h ( x ，) ，) 的零点和极点所支撑的， 其中零点被指定为正系数，而极点被指定为负系数。 例如，假设，是一个有理函数，除子d 可以被分解为两个除子的差： d = d i v ( f ) = d i v o ( 厂) = d i v 。( ，) ，其中d i v 。( ，) 对应于曲线c 与曲线1 f = 0 的交点， 反，。( 厂) 对应于曲线c 与曲线f = 0 的交点。 第二章超椭圆曲线密码的数学基础 超椭圆曲线密码体制的优化与设计 图2 1 一个主除子 图2 1 的主除子为：d = d i v ( f ) = 丑+ b + 只+ 只一( 2 q l + 2 q 2 ) 。 2 4j a c o b i a n 群 2 4 1j a c o b i a n 群的定义 商群- 厂c ( 。) = d 。( 0 ) p ( f ) 就是超椭圆曲线c 在上的j a c o b i a n 群，它实际 上就是有一个无限除子群模它的主除子群而得到的一个商群，也即是一个由无限群对 另一个无限群进行陪集划分后得到的有限商群。群中的每一个元素都是一个除子等价 类，且表示法不唯一。例如定义在一条曲线上的两个有理函数，它们在实数域尺上的 表示如下： l 一 悄 l l ，计扣 图2 2 定义在曲线上的有理函数 j a c o b i a n 群实际上也是超椭圆曲线c 上的全体归约除子的集合，可以在群中定义 归约除子的加法运算，使得j a c o b i a n 群成为一个交换群。超椭圆曲线密码体制不是建 1 2 超椭圆曲线密码体制的优化与设计第二章超椭圆曲线密码的数学基础 立在超椭圆曲线全部有理点上的，而是建立在超椭圆曲线的j a c o b i a n 群上的，因为一 般的超椭圆曲线有理点不见得能够形成交换群。因此，这个j a c o b i a n 有限交换群是超 椭圆曲线密码体制的基础。 2 4 2j a c o b i a n 群的运算 由于j a c o b i a n 群中元素可能存在多种表示方式，为了方便在j a c o b i a n 群中进行这 些除子的运算，需要采用既唯一又简洁的表示方式，通常是采用除子的m u r a f o r d 表 示法。 l 除子的m u m f o r d 表示法：设d = m ，只一( m 。是一个半归约的除子，其中 只= e ( x ，y ，) ，m ，g ，则d 可以由有限域中的两个多项式口( z 1 ) ，易似) 唯一确定， 但须满足以下条件： 口( “) 是一个首一多项式，且n ( m ) = 兀( m 一) 耐； g d e g a d e g b ； 对所有f 的m f 0 ，且有b ( x ) = y l ； a ；b 2 + 6 一，即b 2 + b h f 量0 ( r o o da ) 。 则除子d = g c d ( d i v ( a ( u ) ) ，d i v ( b ( u ) - v ) ) ，记为d = ，b 】。 ! j a c o b i a n 群的加法： 输入：曲线c 有限域上的两个除子为d 。= 【a l , b 。】，d 2 = 【a 2 , b 2 】； 输出：d 3 = 【a 3 , b 3 】= d l + d 2 = a l , b l 】+ 【a 2 , b 2 】； j a c o b i a n 群的加法它是由两部分组成的，即复合和归约。 复合： 计算两个除子的公共因子如下： d = g c d ( a i ，a 2 ，b + b 2 + h ) = s i a l + s 2 a 2 + j 3 i + 也+ ) ； 令a = 口l n 2 d 2 ； 令b = ( s h ab 2 + 8 2 a 2 b l + s 3 ( 易l b 24 - f ) ) d ( m o da ) ； 归约： 令a 3 = ( ，一b h b 2 ) a ，b 3 = ( - h b ) r o o da 3 ； 若d e g a 3 g ，则令a = a 3 , b = b 3 ，然后返回； c 是口3 的首项系数，令a 3 = c _ 1 n 3 ； j 第二章超椭圆曲线密码的数学基础 超椭圆曲线密码体制的优化与设计 输出p ，b 3 】。 j a c o b i a n 群的倍点法： 输入：曲线c 有限域兄上的除子d 。= 【a i , b 。】； 输出：d 2 = 【a 2 , b 2 】_ d l + d l ； 复合： 计算d = g c d ( a l ，2 b l + h ) = s l a l + s 3 ( 2 b l + h ) ； 计算口= 口1 2 d 2b = ( 2 s l d l b l 卜b 1 2 + f ) d ( m o d 口) ； 归约： 令a 2 = ( 厂- b h - b 2 ) a ，b 2 = ( - b - h ) m o da 2 ； 若d e g a 2 g ，则令口= a 2 , b = b 2 ，然后返回； c 是a 2 的首项系数，令a 2 = c - l a 2 ； 输出 a 2 , b ：】。 j a c o b i a n 群上的标量乘运算：d 是j a c o b i a n 商群上的一个除子，任取小于群阶的 m ，将d + d + + d 记为m d ，称为超椭圆曲线j a c o b i a n 群上的标量乘，即 m d = d + d + + d 。 2 5 超椭圆曲线的离散对数问题 超椭圆曲线密码体制是建立在超椭圆曲线离散对数问题( h e c d l p ) 上的，即 h e c d l p 是超椭圆曲线密码学的基础。设c 是定义在有限域兄上的超椭圆曲线，标 量乘d 2 = m d l ，其中d 2 与d 1 是超椭圆曲线c 上的j a c o b i a n 群中的除子， m 【1 ，1 - - 1 】，n 是超椭圆曲线j a c o b i a n 群的阶，由给定的d 2 ，d l 求解m ，称为超椭圆 曲线上的离散对数问题。根据超椭圆曲线j a c o b i a n 群的运算规则可知，由，l ，d ，计算d ： 是比较简单的；相反，由d ，d ：求出m 在计算上是非常困难的，这就是超椭圆曲线离 散对数问题的难解性。因此，超椭圆曲线密码建立在离散对数问题上是相当安全的。 超椭圆曲线密码系统的安全性建立在h e c d l p 的难解性上的，而其他常见的公 钥密码系统( d s 觚s a ) 的安全性则是建立在分解两个大整数的基础上的，这类问 题的通用解决的方法，是用一般数域筛法进行因子分解，它是亚指数时间复杂度的算 法。与通常的大整数因子分解和一般的离散对数问题不同，目前求解椭圆曲线离散对 数问题的最佳算法是p o l l a r d p 因子分解算法，它是全指数复杂度的算法。而从目前 1 4 超椭圆曲线密码体制的优化与设计第二章超椭圆曲线密码的数学基础 的超椭圆曲线密码研究成果来看，对于低亏格