（应用数学专业论文）圆锥曲线及其在公钥密码体制中的应用.pdf

摘要 圆锥曲线及其在公钥密码体制中的应用 应用数学专业 研究生：王标指导教师：孙琦教授 【摘要】随着计算的硬件和软件技术的不断提高，经典的公钥密码面临越 来越大的安全威胁，公钥密码的一个分支甚于代数曲线上计算困难性的密 码体制引起研究者更多的关注，其中椭圆曲线密码体制已经出台了相关标准， 除此以外，我们希望能够找到更多的，或者在某些方面更有优势的代数曲线来 实现公钥密码体制。 一 本文定义并系统的研究了剩余类环z l i 上的圆锥曲线c 。a b ) 和广义圆锥曲 线r d a , b ，c ) ，以及它们的公钥密码体制，并将其应用到可分电子现金、电子现 会发行等社会生活常用的各类系统中 论文的主要研究成果概括如下： 1 用两种方式对c 。( a ，b ) 进行了刻划；在c 。a b ) 上定义了两种加法运算，并 证明这两种运算是相同的，记为o ；同时，证明了c 。r b ) 对所定义的运算0 构 成一个有限加群，记为( c 。( a ，b ) ，o ) 。 2 对群( c 。( a ，b ) ，0 ) 的一些基本性质作了较深入的讨论，包括离散对数问 题，阶的计算，基点g 的寻求等：指出如何通过c p ( a , b ) 和c 日( a ，b ) 的性质来证明 c 。( a ，b ) 的性质；为各种密码协议在c 。( a ，b ) 上的模拟提供了可能性。 3 分析了经典r s a 算法所面临的威胁，如小指数攻击，指出c 。( a b ) 上的 r s a 公钥密码算法和经典r s a 算法一样，其安全性建立在大数分解的困难性 上，但由于能够抵抗小指数攻击，比经典r s a 算法更安全，具有应用前景。 4 给出了椭圆曲线f 4 a , b ) 上的k m o v 方案和q v 方案在c 。“”上的模拟， 新算法的安全性建立在大数分解的困难性基础上，但在抵抗小加密指数、小解 密指数攻击方面比经典r s a 算法更安全 5 总结了电子现金和电子支付系统的发展研究现状；指出盲签名和群签名 摘要 的发展在电子支付系统中的重要作用；给出了r s a 型盲签名方案和群签名方案 在c 。( 如) 上的模拟，分析两个新方案在安全性和实现方面所得到的提高。 6 进一步研究了有限域上广义圆锥曲线p - t , ( a , b ，c ) 的性质，给出( a ，b ，c ) 有 理点所满足的方程，有理点的坐标表示和阶的计算等。 7 ，系统的研究了环z n 上的广义圆锥曲线r n ( a , b ，c ) 的一般性质，以两种方式 对r 仉( a ，b ，c ) 进行了刻划，在r a ( a , b ，c ) 上定义了两种加法运算，并证明这两种运 算是相同的，仍记为o ；指出如何通过蹦a ，b ，c ) 和r q c a , b , c ) 的性质柬证明( a ，b ，c ) 的性质，证明了风b ，c ) 对于定义的运算。构成一个有限加群，记为 ( r “曲，c ) ，o ) ，给出了风( 讪 c ) 的阶；为各种密码协议在( a b c ) 上的模拟提供 了可能性。 8 给出了环z l i 上的广义圆锥曲线风r b ，c ) 的一种分类，讨论了r n ( a , b , c ) 的离散对数问题，定义了环z i i 上的i 类和i l 类广义圆锥曲线，证明了i 类广义 圆锥曲线r n ( a , b ，c ) 等价于环上的圆锥曲线c “a ，b ) ，可用于构造公钥密码算法， 同时，指出i i 类广义圆锥曲线( a ，b ，c ) 不宣用来构造公钥密码算法。 9 在i 类如( a ，b ，c ) 上给出r s a 加密方案和k m o v 数字签名方案的模拟。 关键词： 圆锥曲线；剩余类环；广义圆锥曲线；圆锥曲线公钥密码体制：数字签名； 大数分解；离散对数；r s a 算法；e l g a m a l 算法：k m o v 签名：q v 签名：盲 签名；群签名；电子支付；可分电子现金；小指数攻击； t h ec o n i cc u r v e so v e rz na n di t sa p p l i c a t i o n si n p u b l i c - k e yc r y p t o s y s t e m m a j o r ：a p p l i c a t i o nm a t h e m a t i c s p h d c a n d i d a t e ：w a n gb i a o t u t o r ：s u nq i l a b s t r a c t lw i t h t h ed e v e l o p m e n to f t h ec o m p u t i n gt e c h n o l o g yo f h a r d w a r ea n d s o f t w a r e ，t h ec l a s s i c a lp u b l i c - k e yc r y p t o s y s t e mi sf a c e du pw i mg r o w i n gs e c u r i t y t h r e a t s t h ec r y p t o s y s t e mb a s e do na l g e b r ac u r v e s ，o u eb r a n c ho fp u b l i c k e y c r y p t o s y s t e m s , h a sa r o u s e dg r e a ti n t e r e s t f r o mr e s e a r c h e r s , a n d c o r r e s p o n d i n g s t a n d a r d sh a v eb e e ni s s u e df o re l l i p t i cc u r v ec r y p t o s y s t e m f u r t h e r m o r e ，w e 竹t 0 f i n dm o r ea l g e b r ac u r v e se x c e p te c c ，o ra tl e a s tm o r ea d v a n t a g e o u si ns o m ea s p e c t s t or e a l i z ep u b l i c k e yc r y p t o s y s t e m t h ed i s s e r t a t i o nm a k e ss y s t e m a t i cr e s e a r c hi n t oc o n i cc u r v o , g e n e r a l i z e dc o n i c c m v ea n dc o n i cc u r v ec r y p t o s y s t e mo v g rr e s i d u ec l a s sr i n g ，a n dt h e na p p l i e st h e s et o k i n d so fs y s t e m ss u c ha sd i v i s i b l ee - c a s h ，i s s u a n c eo f e - c a s ha n de t c t h er e s e a r c h r e s u l t so f t h i sd i s s e r t a t i o na r es u m m a r i z e da sf o f l o w s ： i t h ec o n i cc u r v ec “曲) i sd e s c r i b e di nt w om e t h o d s t w oa d d i t i o n sa l e d e f i n e d p r o v e ds a m ew i t he a c ho t h e ra n dd e n o t e db y0 i ti sp r o v e dt h a tt h e r a t i o n a lp o i n t so fc n 瓴b ) f o r ma na b e l i a ng r o u pu n d e rt h eo p e r a t i o no ，w h i c hi s d e n o t e db y ( c 。( 咖) ，o ) 2 t h ed i s s e r t a t i o nd i s c u s s e sb a s i cp r o p e r t i e so ft h eg r o u p ( c n ( a ，”，o ) ， i n c l u d i n gd l p , o r d e rc o m p u t a t i o n , g e n e r a t o rf i n d i n g , a n dp o i n t so u th o wt op r o v e t h ep r o p e r t i e so fc n ( a ，b ) b yt h o s eo fc p ( a ，b ) a n dc q ( a , b ) ，m a k e si t p o s s i b l e t oe s t a b l i s ha n a l o g u eo v e rt h ec o n i e sf o rk i n d so f c r y p t o g r a p h i cp r o t o c o l s 。 3 t h et h r e a t sc o n f r o n t e db yc l a s s i c a lr s aa r ea n a l y z e d ；i ti sp r o p o s e dt h a tt h e r s ap u b l i c k e y c r y p t o s y s t e mo v f f fc n ( a ，b ) i ss a f e ra n dm o l - ep r o m i s i n gi n a p p l i c a t i o nt h a nt h ec l a s s i c a lr s af o ri tc a nr e s i s ts m a l le n c r y p t i o ne x p o n e n ta t t a c k a n ds m a l ld e c r y p t i o ne x p o n e n ta t t a c k , t h o u g hf o rb o t ho f t h e m , t h es e c u r i t yi sb a s e d o nd i f f i c u l t i e si nf a c t o r i z i n gl a r g ei n t e g e r 4 t h ed i s s e r t a t i o np r o v i d e st h ea n a l o g u e so f k m o va n dq v o v e rc n ( a ，b ) t h e s e c u r i t yo ft h e s es c h e m e si sb a s e do nd i f f i c u l t i e si nf a c t o r i z i n gl a r g ei n t e g e rb u t s a f e rt h a nt h ec l a s s i c a lr s ai nr e s i s t i n gs m a l le n c r y p t i o no rd e c r y p t i o ne x p o n e n t a t t a c k 5 t h ec u r r e n td e v e l o p m e n to fe - c a s ha n de l e c t r o n i c p a y m e n ts y s t e mi s s u m m a r i z e d ；t h es i g n i f i c a n tf u n c t i o no fb l i n ds i g n a t u r ea n dg r o u ps i g n a t u r ei s e m p h a s i z e do ne l e c t r o n i cp a y m e n ts y s t e m ；b l i n ds i g n a t u r es c h e m ea n dg r o u p s i g n a t u r es c h e m eb a s e do nr s ao v e rc n ( a b ) a r ep r e s e n t e d ，w h i c ha c h i e v es o m e i m p r o v e m e n ti ns e c u r i t ya n dr e a l i z a t i o n 6 t h ed i s s e r t a t i o nf u r t h e r st h er e s e a r c ho np r o p e r t i e so fk ( 如，c ) ，p r o v i d e st h e e q u a t i o na n dt h ec o o r d i n a t er e p r e s e n t a t i o no fr a t i o n a lp o i n t so nr p ( a , b ，c ) ，t h eo r d e r o f r p ( a , b ，c ) 7 t h ed i s s e r t a t i o ns t u d i e st h ec o n n l l o np r o p e a i e so fg c co v e rz i l ，d e n o t e db y 氏( a b ，c ) ；d e s c r i b e sn 曲，c ) i nt w ow a y s ，p r o v e st h et w oa d d i t i o n sd e f i n e dt ob et h e s a m e ，d e n o t e db yo ；p o i n t so u th o wt op r o v et h ep r o p e r t i e so fi k ( a ，b ，c ) b yt h o s eo f 砩( a ，b ，c ) a n dr q ( a ，b ，c ) ；p r o v e st h a tt h er a t i o n a lp o i n t so f 如b ，c ) f o r ma na b e l i a n g r o u pu n d e rt h eo p e r a t i o no ，w h i c hi sr e c o r d e da s ( r n ( a ，b ，c ) ，o ) ；p r o v i d e st h e o r d e ro fr n “b ，c ) t h e s em a k ei tp o s s i b l et oe s t a b l i s ha n a l o g u e so v e rr n ( a ，b ，c ) f o r k i n d so f c r y p t o g r a p h i cp r o t o c o l s 8 t h ed i s s e r t a t i o np r e s e n t sac l a s s i f i c a t i o no f r 札伉b ，c ) ，d i s c u s s e sd l po ne a c h c a t e g o r i e s ，d e f i n e sc l a s sla n dc l a s si i 艮伉b ，c ) ，p r o v e st h a tc l a s si 氏( 讪，c ) e q u i v a l e n tw i t hc n ( a b ) c a nb u i l dp u b l i c - k e yc r y p t o s y s t e m ，p o i n t so u tc l a s si i i i a b s t t a c t 心( 如，c ) u n f i tt ob u i l dp u b l i c k e yc r y p t o s y s t e m b a s e do nd l p 9 t h ea n a l o g u e so fr s aa n dk i v l o vo nr n ( a , b ，c ) a l ep r e s e n t e d ，a n dt h e i r s e c u r i t yi sa n a l y z e d k e y w o r d s ： c o n i cc u r v e ；r e s i d u ec l a s sr i n gz l ；p u b h c - k e yc r y p t o s y s t e m ；d i g i t a ls i g n a t u r e s c h e m e ；i n t e g e rf a c t o r i z a t i o n ；d i s c r e t el o g a r i t h m ；r s a ；e 1 g a m a l ；k m o v ；q v ；b l i n d s i g n a t u r e ；g r o u ps i g n a t u r e ；d i v i s i b l ee - c a s h ；c r y p t a n a l y s i s o fs h o r tr s as e e r e t e x p o n e n t s ； i i i 1 导论 1 1 引言 随着计算机技术和现代通信技术的成熟、宽带的广泛应用、互联网普及程 度的快速提高，社会信息化步伐明显加快，使得基于网络通信和计算机应用技 术的电子商务、电子政务等各种网络化的社会活动受到了全世界的广泛关注， 并得到了极其迅猛的发展。 在我国，基于网络的各种商务和政务活动也获得了长足的发展。 1 9 9 4 年，我国建立起中国公用计算机互联网( c h i n a n e t ) 和中国会桥信息 网( c h i n a g b n ) 两个商业网络以及中国科学技术网( c s t n e t ) 和中国教育科研 网( c e r n e t ) 两个学术网。四大骨干网络的建立，一方面为电子商务等提供了 基础，同时也为电子政务的实旌提供可能。若干省份都已经建立起较全面的电 子政务系统，比如，广州市政预计在2 0 0 6 年实现数字市政这一目标。 2 0 0 1 年版的中国消费类电子商务发展状况研究报告指出：截止到2 0 0 0 年3 月，国内共有从事消费类电子商务的网站已达1 1 0 0 余家，涵盖了人们生活 的方方面面。据信息产业部赛迪新资讯的分析，2 0 0 0 年我国互联网服务市场规 模达5 3 亿元，同比增长7 2 6 ；电子商务交易额为7 7 1 6 亿元。截止到2 0 0 0 年3 月，各大商业银行发放的信用卡已超过1 亿张。2 0 0 0 年国内互联网用户己 达到2 2 5 0 力，其中参与网上购物的比例为3 1 6 ，7 4 4 的网民认为五年内中 国将实现大规模的电子商务2 0 0 4 年，中国互联网络信息中心( c n n i c ) 发布的 第十四次中国互联网络发展状况统计报告指出：我国上网用户总数已经达到 8 7 0 0 万，经常利用网络进行购物的人群己近6 3 5 1 万，网上购物方式正在被越 来越多的网民所接受。同年，北京日报报导来自“第八届中国国际电子商务大 会”上的消息，在全球新型技术的发展高潮中，电子商务也步入了“黄金时期” 中国电子商务协会理事长宋玲透露，我国的电子商务最近几年发展迅猛，平均 年增长率为4 0 ，而未来几年这个数字有可能会超过5 0 。掘c n n i c 统计，目j ；i 我国有4 0 多的网民在一年之内有上网购物活动，例如，在2 0 0 3 年仅网上商品 销售总额就达2 1 8 5 6 亿元。 然而，尽管我国网上交易和电子政务等每年以相当高的年增长率快速发展， 四川大学博士学位论文 相对于国外的电子商务和电子政务水平而言，差距还是巨大的。此外，网上消 费和诸如电子政务等的使用者，占全部网民的比重还是偏低。根据调查显示， 不管是电子商务还是电子政务，持“犹豫态度”的消费者或使用者都表示，网 络的安全性是他们的最大顾虑，他们对网络服务最担心的是被人恶意侵犯隐私， 被人偷盗银行账号、密码，被人非法篡改信息等等。事实也证明，网络的风险 是普遍性的，掘统计，全球约2 0 秒钟就有一次计算机入侵事件发生，网络上有 1 4 的防火墙被突破，约7 0 的网络信息主管报告因机密信息泄漏而受到损失。 包括病毒、漏洞等引发的安全事件更是数不可数。 总的来说，网络服务的用户主要的担心是信息的机密性( c o n f i d e n t i a l i t y ) 、 完整性( i n t e g r i t y ) 、可用性( a v a i l a b i l i t y ) 受到破坏，换句话说，用户就是希望系统 能够保障数字信息的有效性。为保障信息的机密性、完整性和可用性三性，有 许多技术手段，其中广义的公钥密码体制是一种基础性的重要的技术手段，包 括公钥密码体制、数字签名技术以及数字水印等。 本文主要研究一类较新型的密码体制圆锥曲线公钥密码体制。 1 2 关于圆锥曲线及其密码体制的研究 1 2 1 研究背景 自从d i f f i e 与h e l l m a n 提出公钥密码体制以来，各种公钥密码算法不断涌 现。根据公钥密码体制的安全基础来分类，现有的被公认为安全、实用、有效 的公钥密码体系有三类。 ( 1 ) 基于大整数因子分解问题的公钥密码体系 这一类公钥密码体系基于大整数因子分解的困难性，其中，最著名的当属 r s a 公钥密码体系。该算法是由麻省理工学院的三位学者于1 9 7 7 年提出的， 是目i ；i 被广泛接受并实现的通用公钥密码体系之一。 ( 2 ) 基于有限乘法群上离散对数问题的d l p 类公钥密码体系 d l p 类公钥密码体系是基于有限乘法群上的离散对数问题的求解困难性 的，其中最著名的有e 1 g a m e l 公钥密码算法”1 。 ( 3 ) 基于代数曲线有限加法群上的离散对数问题的公钥密码体系 2 卿川大学博士学位论文 在这一类公钥密码体系中，著名的有椭圆曲线公钥密码体系e c c ，其数学 基础是有限域上椭圆曲线有限加法群上的椭圆曲线离散对数问题的求解困难 性。它是由华盛顿大学的n e a lk o b l i t z 和i b m 公司的v i c t o rm i l l e r 于1 9 8 6 年各 自独立地提出的“1 ，近2 0 年来发展很快。在同等安全条件下，椭圆曲线公钥密 码体系具有许多独到的优势，因而成为当前的一个研究热点。 代数曲线密码体制引起人们更多关注，除了椭圆曲线外，是否还存在类似， 甚至在某些方面更好的代数曲线，用以构造公钥密码体制。 1 9 9 6 年张明志引进了圆锥曲线c 。( a ，b ) 上的加法运算o ，并证明曲线上的点 与引进的运算能构成一个有限加群，提出了用圆锥曲线分解整数的方法，这也 为构造圆锥曲线密码体制提供了可能性。1 9 9 8 年，曹珍富提出了基于有限域上 圆锥曲线的公钥密码体制“1 ，随后，他又提出了r s a 的圆锥曲线模拟“1 ，这些 工作引起了密码研究人员的关注。2 0 0 0 年，戴宗铎、裴定一、杨君辉等提出了 有限域上的广义圆锥曲线b ) ，定义了曲线上的加法，并证明r p ( a ，b ) 是一个 加群以及岛( 如) 中的离散对数问题不比有限域中的离散对数困难”1 。尽管如此， 由于( c 。( 咖) ，0 ) 中明文嵌入、阶的计算、逆元的计算、点的运算都比较容易， 2 0 0 2 年，孙琦、张起帆、彭国华指出用整数的标准二进制表示( 国外叫n a f ) 。 存在一个快速计算( c ( a ，b ) ，o ) 中群元整数倍的算法随。这些对设计密码算法具 有很大吸引力。1 9 9 2 年k k o y a m a , u m a u r c r , t o k a m o t o ，s v a n s t o n e 在文【1 1 】中， 2 0 0 0 年m i n gh u a q u , s c o t tv a n s t o n e 在文 1 2 1 q h 分别提出了基于大数n ( n = p q ) 分 解困难性的环乙上的椭圆曲线的数字签名方案( 分别简称k m o v 方案、q v 方案) ，克服了经典r s a 算法无法抵抗的小指数攻击、q v 方案还克服了前者 所具有的同态性的缺点。2 0 0 3 年和2 0 0 5 年，朱文余和孙琦对环z i l 上的椭圆曲 线的基本性质作了深入的研究，进一步改进了k m o v 方案和q v 方案“4 。但 是，e | i 伍”上计算复杂，使我们联想到，如果能把有限域上的圆锥曲线推广到 环z i l 上，类似e i l b ) 那样建立运算，证明环z i i 上的圆锥曲线c 。“b ) 和广义圆 锥曲线如( a ，b ，c ) 也是个加群，那么，同样可以建立各种公钥密码协议它们 不仅保留了e l l b ) 中的优点，而且计算更简单，特别对于r s a 类型的公钥密码 算法，在乙上的圆锥曲线c 。( 咖) 构成的加群上，变得更安全，具有应用自可景。 四川大学博士学位论文 1 2 2 研究内容和主要贡献 本文系统的研究了环上圆锥曲线的性质，构造环上圆锥曲线的公钥密码体 制和数字签名方案，并进一步研究了环上广义圆锥曲线的性质及其公钥密码体 制。 主要研究内容及贡献概括如下： 1 对环z i i 上的圆锥曲线g ( 口，6 ) 及其性质作了系统的研究： 1 ) 类似有限域f p _ l z t 约圆锥曲线c 。“b ) ，定义了环z i l 上的圆锥曲线 c b ) 。 2 ) 用两种方式对e ( 口，b ) 进行了刻划：一种是直接以坐标的方式给出 e ( 口，6 ) 中全体有理点的表示，得到e ( 口，6 ) = c i uc 2 uc 3 0 0 ；另一种是在 c ( 口，6 ) 和c ，( d ，6 ) q ( q 6 ) 间建立一一对应映射，十分方便的给出了e ( 口，6 ) 的阶。 3 ) 在c ( 口，6 ) 上定义了两种加法运算：一种是由点的坐标直接定义运算， 另一种是通过映射妒的逆映射矿1 及孙子定理来定义，并证明了这两种运算是相 同的，记为o 。同对，证明了e 以，对所定义的运算。构成一个有限加群， 记为( g ( a ，b ) ，0 ) 。 4 ) 对( e ( 口，b ) ，o ) 的一些基本性质作了较深入的讨论，包括离散对数问 题、阶的计算、基点g 的寻求等。指出如何通过c p ( 口，6 ) 和e ( 4 ，6 ) 的性质来证 明e ( d ，b ) 的性质。 通过对巴( 口，b ) 的研究，表明各种公钥密码体制在c ( 口，6 ) 上的模拟是可行 的。 2 构造了e ( 4 ，b ) 上的各类公钥密码体制，对其实现和应用作了较深入的 研究分析： 1 ) 对( g ( d ，b ) ，0 ) 的研究表明，其明文嵌入、阶的计算、点之间的运算、 求逆元等运算比椭圆曲线密码体制上的计算要容易。 2 ) 给出经典的r s a 型和e l g a m a l 型公钥密码算法在( e ( a ，6 ) ，o ) 上的模拟 以及数值例子。 3 ) 分析了经典r s a 算法所面临的威胁，如小指数攻击，指出c 。( 口，6 ) 上的 4 四川大学博士学位论文 r s a 公钥密码算法和经典r s a 算法一样，其安全性建立在大数分解的困难性 上，但由于可以抵抗现有针对小指数的攻击，比经典r s a 算法更安全，具有应 用前景。 4 ) 给出了环z i 上的椭圆曲线e ( 口，6 ) 上的i ( m o v 签名方案和q v 签名方案在 c 。( 口，6 ) 上的模拟，与经典r s a 签名算法相同，新算法的安全性建立在大数分解 的困难性基础上，但在抵抗小加密指数和小解密指数攻击方面比经典r s a 算法 安全。e ( 口，6 ) 上的k m o v 方案具有同态性，e ( 口，6 ) 上的q v 方案克服了这一缺 点，但是其使用具有很大局限性。基于e ( 口，6 ) 的这两个方案与基于e ( 口，6 ) 的 方案相比，不仅保留了原方案的优点，而且在e ( 口，6 ) 上，计算量要少的多，也 容易实现，特别是对于q v 方案的圆锥曲线模拟，在实现上较e ( 口，6 ) 上有很大 提高，因此，c 。( 口，6 ) 上的这两个签名方案更具应用价值。 5 ) 总结了电子现金和电子支付系统的研究发展现状，归纳了盲签名和群签 名技术的发展以及在电子支付系统中的重要作用，并指出经典r s a 型盲签名和 群签名方案所面临的安全问题。 6 ) 给出了r s a 型盲签名方案在e ( 口，b ) 上的模拟及其数值示例。类似的， 与经典的r s a 型盲签名方案相比，建立在e ( 口，6 ) 上签名方案的安全性得到一定 的提高，特别是在抵抗小加密指数和小解密指数攻击方面比经典r s a 算法安全， 因此，c 。( 口，6 ) 上的盲签名具有应用价值。并将新的签名方案应用到可分电子现 金系统中。 7 ) 给出了r s a 型群签名方案在g ( a ，6 ) 上的模拟及其数值示例。同样的， 与经典的r s a 型群签名方案相比，建立在c ( 口，6 ) 上签名方案的安全性得到一定 的提高，并将该签名方案应用到电子货币发行子系统中 8 1 指出诸如公平盲签名、群定向签名以及多重数字签名等各类签名方案均 可以在e ( 口，6 ) 上实现模拟，并在安全性上得到一定的提高。 3 对广义圆锥曲线及其公钥密码体制进行了较系统的研究： 1 ) 对有限域f p 上广义圆锥曲线r p ( 口，b ，c ) 的性质作了研究，并给出 r p ( 口，b ，c ) 的有理点所满足的方程，有理点的坐标表示和阶的计算等。 2 ) 定义了环乙上的广义圆锥曲线心( 口，b ，力。 3 ) 较系统的研究了咒( 口，b ，c ) 的一般性质。以两种方式对r ( 口，b ，c ) 进行了 四川大学博士学位论文 刻划：一种是以坐标的方式给出了b ( 口，b ，c ) 中全体有理点的表示，德到 心( 口，b ，0 2 蜀u 足u 墨u o ；另一种方式是在咒( 口，b ，c ) 和r ，( 口，b ，c ) 毛( 口，b ，c ) 间建立一一对应映射声，十分方便的给出了疋( 口，6 ，c ) 的阶。 4 ) 在兄( 口，b ，c ) 上定义了两种加法运算：一种是由点的坐标直接定义，另 一种是通过映射矿的逆映射1 及孙子定理来定义，并证明这两种运算是相同 的，记为o 。 5 ) 指出如何通过胄，( 4 ，b ，c ) 和心( 口，b ，c ) 的性质来证明r ( 口，b ，c ) 的性质，证 明了砖( 口，b ，c ) 对于定义的运算。构成一个有限加群，记为( 兄( 口，b ，c ) ，o ) 。 6 ) 证明了，当假定运算过程在r l 中进行时，可用点的参数表示来进行； 对( 见( 口，b ，c ) ，o ) 的一些基本性质作了深入讨论，包括离散对数问题、阶的计 算等，这些为构建r ( 口，b ，c ) 上的公钥密码体制提供了可能性。 7 ) 给出了r ，( 口，b ，c ) 的一种分类，并将置。( 口，b ，c ) 的分类推广到兄( 口，b ，c ) 上，研究了它们的离散对数问题，定义了环z n 上的i 类和i i 类广义圆锥曲线。 8 ) 证明了i 类广义圆锥曲线r ( a ，b ，c ) 等价于环上的圆锥曲线巴( 口，b ) ，可 用于构造公钥密码体制，同时，指出i i 类广义圆锥曲线r 。( 口 b ，c ) 不宜用来构造 公钥密码体制。 9 ) 在i 类r ( 口，b ，c ) 上，给出了r s a 型加密方案和k m o v 数字签名方案 的模拟，并给出k m o v 数字签名方案的数值模拟实例。 1 0 ) 指出一些经典的公钥密码算法和数字签名方案，如q v 数字签名方案、 盲签名方案、群签名方案以及公平盲签名方案等等，均可以在r 。( n ，b ，力上实现 模拟，并在安全性、计算效率和实现方面有一定程度的提高。 1 2 3 论文结构 论文共分为七章。 第一章是绪论，给出论文的研究背景，研究内容、主要贡献和论文的整体 结构框架。 第二章首先介绍有限域上的圆锥曲线理论以及有限域上的圆锥曲线密码体 制，然后定义环z l i 上的圆锥曲线，深入研究其性质。研究了圆锥曲线密码体制 的一些一般性问题，包括基点的获取和阶的计算等，并分析了经典r s a 公钥密 6 四川大学傅士学位论文 码算法所面l 临的攻击，如小指数攻击。最后给出常用的l i s a 型和e 1 g a m a l 型公 钥密码算法在环上圆锥曲线上的模拟，指出圆锥曲线上的l i s a 算法可以避免经 典算法所面临的攻击 第三章首先介绍环上椭圆曲线及其公钥密码体制，重点叙述环上椭圆曲线 上的两类数字签名方案( k i o v 方案和q v 方案) ，自然的，将这两类数字签名 方案在环上圆锥曲线上进行模拟，并对其性能作了分析。 第四章首先介绍电子现金以及经典盲签名方案，给出环上圆锥曲线上的盲 签名方案的模拟，将其应用到可分电子现金中，并分析其安全性，最后给出一 个运用盲签名实现可分电子现金的具体示例。 第五章首先介绍电子支付系统以及群签名方案，给出环上圆锥曲线群签名 方案的模拟，将其应用到电子支付系统的货币发行子系统中，并给出具体示例。 第六章首先进一步研究有限域上广义圆锥曲线的性质，定义环乙上广义圆 锥曲线r n ( a ，b ，c ) ，系统研究其般性质，并给出( 咖，c ) 的一种分类，讨论了 碥b ，c ) 的离散对数问题，定义了环乙上的i 类和i i 类广义圆锥曲线，证明了 i 类广义圆锥曲线如( a ，b ，c ) 等价于环上的圆锥曲线c “如) ，可用于构造公钥密 码体制，同时，指出i i 类广义圆锥曲线r n r b ，c ) 不宣用来构造公钥密码体制。 最后给出i 类如( a ，b ，c ) 上l i s a 加密方案和k m o v 数字签名方案在( a b ，c ) 上 的模拟，并给出一些具体数值示例。 第七章是对论文工作的总结并展望进一步的研究工作。 7 四川大学博士学位论文 2 环z 。上的圆锥曲线及其公钥密码体制 随着计算机运算速度的迅速提高和分布式计算能力的日益强大，基于大数 分解的公钥密码体制受到很大冲击，5 1 2 b i t 的体制己不再安全。为确保信息安 全，密码体制的密码要达到足够的长度，这使得一些较短密钥的应用产品( 例如 s m a r t 卡) 需要新的密码体制来实现。 在2 0 世纪8 0 年代，通过k o b l i t z 和m i l l e r 开创性的工作“1 ，使得椭圆曲线 在密码领域中发挥了重要作用，椭圆曲线密码体制的数学基础是利用椭圆曲线 上的点来构造计算上的困难性。从已有的攻击算法表明：基于有限域上椭圆曲 线的离散对数问题的困难性要高于一股乘法群上的离散对数的困难性，且椭圆 曲线所基于的域的运算位数远小于传统离散对数的运算位数，其运算很容易在 计算机的软件和硬件上实现，特别是定义在只上的椭圆曲线。椭圆曲线密码 体制有两个显著的优点：一是密钥比特数少，二是在基于乘法群的密码体制相 同条件下能够提供更高的安全性。 椭圆曲线密码体制属于代数曲线类公钥密码，除了椭圆曲线密码体制外， 还存在人们感兴趣的代数曲线，并能很好的应用于公钥密码系统中，圆锥曲线 就是其中一个。 本章首先定义基于剩余类环z ，l 上的圆锥曲线c 。( a b ) ，并用两种方法来刻划 它。同时定义了c 。伉b ) 上的两种加法运算，证明这两种加法是相同的，记为o ， 并证明了( c 。( a ，b ) ，o ) 是一个有限交换群。迸一步，对( c 。( a ，b ) ，o ) 的基本性质进 行了深入的研究；对于一类c 。“b ) ，给出了计算群中基点g 的方法。在此基础 上，给出了几类公钥密码算法在圆锥曲线c 。( 如) 上的模拟。 与z 。上的椭圆曲线相比，z 。上的圆锥曲线可构造更多的公钥密码算法， 特别是对于r s a 类型的公钥密码算法更具有应用价值。同时，圆锥曲线密码体 制还具有明文嵌入方便、运算速度快、更易于实现等优点，在群元素的整数倍 计算过程中，引入标准二进制，这比著名的“平方一和一乘法”算法节约近1 4 计算量“，并被证明无法再改进“”。 8 四川大学博七学位论文 2 1 有限域上圆锥曲线介绍 设巴为p 元有限域，p 为奇素数，易为f ，的乘群。考虑仿射平面( 0 ) 上的圆锥曲线c 。( 4 ，6 ) 是指同余方程： y 2 ；础2 - b x ( m o d p ) , a ，6 瓦+ ( 2 1 ) 在兄上的解( x ，”的集。 有限域上圆锥曲线的内容参见文【5 】。 2 1 1 圆锥曲线的群结构及几何意义 显然o p 。( o ，o ) c p ( 口，6 ) 。 若( 2 1 ) 的解( x ，y ) 中x 0 ，则令y ；x t ( m o d p ) ，代a ( 2 1 ) 得 ( 口一t 2 ) x i b ( m o d p ) 若t 2 = a ，显然上式不成立，若f 2 a ，则 x = 刍( m o d p ) ，y = 鲁( m o d p ) ( 2 _ 2 ) 对f ，f 2 口，我们用p ( f ) 表示q ( 口，6 ) 中点( _ 了b ，i ) ，原点o ，记 为p ) ，即得解集： c p ( 础) = ) = ( _ 与，i ，v f , t 2 * a ) u 咖 若令h = f 匕l f 2 口) u 扣 ，显然( 2 2 ) 给出了h 与c ，( 口，6 ) 之间的一 一对应。 毛e 2 ：1 5 中定义了c p ( 口，6 ) 上点的加法0 ，对任意p ( f ) c ，( 口，6 ) 满足 p ( f ) o p ( o o ) = p ( o o ) 0 p ( t ) = p ( f ) 设p ( t i ) ，p ( t 2 ) c ，( 口，6 ) ，其中f l ，t 2 日，且f i ，2 0 0 ， 定义 p ( f 。) o p ( t 2 ) = p ( ) ，其中， t ，：篱 f i “：o ( 2 _ 3 一) 3 = ，l + f 2 ( z 一 b ，l + f 2 = o 上述加法有简单的几何解释，参数t 为直线0 。p ( f ) 的斜率， p q ) l l 丈学博士学位论文 p ( t 1 ) = ( 一，y 1 ) ，p ( t 2 ) = ( x 2 ，y 2 ) e c p ( 口，6 ) ，其中f l ，f 2 日，且t i , t 2 ， p “) o p ( t ：) = p ( t ，) ，当 f 2 时，过0 p 作平行于p “) p ( f 2 ) 的直线与c ，( 口，6 ) 交 p ( t 3 ) ，有 嚣2 再a - 1 1 2 a 一1 2 2 2 篱( m o 省( 一，p ) 乩毗+ ，2 。 【a o ，若( x 2 一而，p ) = p ，即f i + f 2 = 0 当f i = f 2 = t 时，p ( ) ，p ( f 2 ) 重合，这时o p p ( ，3 ) 应平行于c ，( 口，6 ) 在点p ( f 1 ) 处的 切线，有 l 型：坐( m o d p ) 若“，p ) ：l ，即r 0 t 3 = 2 y l 2 t - 1 。 。 【o o ，若( y l ，p ) = p ，即r = 0 综上即得到( 2 3 ) 。 由点的加法。的定义知p ( o o ) 为( c 。( 口，6 ) ，0 ) 的零元。 对p ( f ) c p ( 4 ，6 ) 存在负元一p ( ) = p ( o o ) 广p ( f ) = p ( _ ，) ，t 日，t 0 0 。 若用坐标来表示则有p ) = ( 0 ，0 ) 的负元为( 0 ，o ) ，p ( t ) = ( x ，y ) c p ( 4 ，6 ) ， 显然由( 2 - 2 ) 可得- ( x ，力= ( x , - - y ) ，于是对任意( x ，y ) c p ( 口，b ) ，有 一( x ，y ) = ( x ，一j ，) 。 在文 5 中进一步证明了( c p ( 4 ，6 ) ，o ) 构成加群。且易知： j c p ( 口，6 i = 川，若睁 p + ，若( 詈 = 一- 这罩l e g e n d r e 符号“叼，i c i 表示c 的阶。 因此，和有限域上椭圆曲线的点组成的加群一样，可在( e ( 口，6 ) ，0 ) 上构造 各种公钥密码体制删 i o 婴业查兰竖主兰垡丝茎一 2 1 2 基于有限域上圆锥曲线的公钥密码体制 文【5 】定义了c p ( 口，6 ) ，并证明f ，( 以6 ) ，。) 是一个有限交换群，这为构造 ( c 。( 口，6 ) ，o ) 上的公钥密码体制提供了条件( c ，( 口，6 ) ，。) 上的公钥密码体制参 见文【6 ，7 1 。 2 1 2 1 有限域上1 1 1 锥曲线的离散对数问题 类似一般有限a b e l 群中离散对数的定义，在( c