（计算数学专业论文）基于环zn上圆锥曲线的数字签名方案.pdf

摘要 基于环乙上圆锥曲线的数字签名方案 作者简介：焦学磊，男，1 9 8 2 年2 月生，师从成都理工大学王新庄教授， 2 0 0 8 年7 月毕业于成都理工大学计算数学专业，获得理学硕士学位。 摘要 随着计算的硬件和软件技术的不断提高，经典的公钥密码面临越来越大的安 全威胁，公钥密码的一个分支一基于代数曲线上计算困难性的密码体制引起研究 者更多的关注，其中椭圆曲线密码体制已经出台了相关标准，除此以外，我们希 望能够找到更多的，或者在某些方面更有优势的代数曲线来实现公钥密码体制。 本文系统的研究了环乙上圆锥曲线的性质，构造环乙上圆锥曲线的数字签 名方案。主要研究内容概括如下： 1 用两种方式对圆锥曲线e ( 口，6 ) 进行了刻划，在e ( 口，6 ) 上定义了两种加 法运算，并证明了这两种运算是相同的，记为o 。同时，证明了e ( 口，6 ) 对所定 义的运算。构成一个有限加群，记为( g ( 口，6 ) ，o ) 。 2 对( g ( 口，6 ) ，0 ) 的一些基本性质作了较深入的讨论，包括离散对数问题、 阶的计算、基点g 的寻求等。指出如何通过c ，( 口，6 ) 和q ，6 ) 的性质来证明 e ( 口，6 ) 的性质。 3 分析了经典兄鲥算法所面临的威胁，如小指数攻击，指出e ( 口，6 ) 上的 兄鲥公钥密码算法和经典冗纠算法一样，其安全性建立在大数分解的困难性上， 但由于可以抵抗现有针对小指数的攻击，比经典冗鲥算法更安全，具有应用前 景。 4 给出了环z 。上的椭圆曲线e ( 乜，6 ) 上的舢y 签名方案和q y 签名方案在 e ( 口，6 ) 上的模拟，与经典尺鲥签名算法相同，新算法的安全性建立在大数分解 的困难性基础上，但在抵抗小加密指数和小解密指数攻击方面比经典r 翱算法 安全。e ，6 ) 上的舢y 方案具有同态性，e ( 口，6 ) 上的q y 方案克服了这一缺 点，但是其使用具有很大局限性。基于e ( 口，6 ) 的这两个方案与基于e ( 口，6 ) 的方 成都理工大学硕士学位论文 案相比，不仅保留了原方案的优点，而且在c ( 口，6 ) 上，计算量要少的多，也容 易实现，特别是对于q y 方案的圆锥曲线模拟，在实现上较e 0 ，6 ) 上有很大提 高，因此，e ( 口，6 ) 上的这两个签名方案更具应用价值。 5 给出了基于环乙上的圆锥曲线公钥密码体系的数字签名方案。该方案综 合利用了大数该方案综合利用了大数分解的困难性和有限群上计算离散对数的 困难性，从而增强了该数字签名方案的安全性。在此基础上，通过将多个圆锥曲 线数字签名联合起来生成对消息的签名，设计实现了多人对同一文件的多重数字 签名，然后给出了多重数字签名方案的数值模拟。 最后给出环z 。上圆锥曲线的 冗翻盲签名方案及数值模拟。 关键词：圆锥曲线数字签名多重数字签名兄锐盲签名 1 1 a b s t m c t d i g i t a ls i g n a t u r es c h e m eb a s e do nt h ec o n i cc u r v e o v e rz n h l t r o d u c t i o no ft h ea u t h o r ：j i a o x u e l e i ，m a l e ，w a sb o mi 1 1f 色b m a r y ，1 9 8 2w h o s et u t o r w a sp r o f e s s o rw a n g x i n z h u a n g h eg r a d u a t e df 如mc h e n g d uu n i v e r s i i yo f1 e c h n o l o g yi n c o m p u t a t i o n a lm a t h e m a t i c sm a j o ra n dw a s 伊a n t e dt h em a s t e rd e 伊e ei nj u n e ，2 0 0 8 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m p u t i n gt e c h n o l o g yo fh a r d w a r ea n ds 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 t hg r o w i n gs e c u r i t yt h r e a t s t h e c 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 n eb r a n c ho fp u b l i c - k e yc r y p t o s y s t e m s ，h a s a r o u s e d 伊e a ti n t e r e s tf r o mr e s e a r c h e r s ，a n dc o h e s p o n d i n gs t a n d a r d sh a v eb e e ni s s u e d f o re l l j p t i cc u ec r y p t o s y s t e m f u n h e 咖o r e ，w et r yt of i n dm o r ea l g e b r ac u r v e s e 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 st or e a l i z ep u b l i c k e y c r y p t o s y s t e m t 1 l ed i s s e n 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 j cc u r v eo v e rr e s i d u ec l a s s r i n g ，d e s i g i l sad i 舀t a ls i g i l a t u r es c h e m eo nt h ep u b l i c k e yc r y p t o 笋a p h yo fc o n i c c u r v e o v e rz t h er e s e a r c hc o n t e n to ft h i sd i s s e n a t i o na r es u m m a r i z e da sf o l l o w s ： 1 n ec o n i cc l l r v e e ( 口，6 ) i sd e s 硎b e di n 附om e t h o d s t w oa d d i t i o n sa r 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 yo i ti sp r o v e dt h a tt h ei a t i o n a l p o i n t so fc 。( 口，6 ) f b 加a na b e l i a ng r o u pu n d e rt h eo p e r a t i o n o ，w h i c hi sd e n o t e d b y ( e ( 口，6 ) ，o ) 2 t h ed i s s e n a t i o nd i s c u s s e sb a s i cp r o p e n i e so ft h eg r o u p ( e ( 口，6 ) ，o ) ， i n c l u d i n g 上地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 w t op r o v et h e p r o p e n i e so fe ( 口，6 ) b yt h o s eo fc ，( 口，6 ) a n dq ( 口，6 ) ，m a k e s i t p o s s i b l et 0 e s t a b l i s ha n a l o g u eo v e rt h ec o n i c sf b rk i n d so fc 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 如n t e db yc l a s s i c a l 删a r ea n a l y z e d ；i ti sp r o p o s e dt h a tt h e i i l 成都理1 ：火学硕士学位论文 删 p u b l i c k e yc r y p t o s y s t e m o v e rc 。( 口，6 )i ss a f e ra n dm o r 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 l 5 wf b ri tc a nr e s i s ts m a ue 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 曲f o rb o t ho ft h e m ，t h es e c u r i t yi sb a s e d o nd i f f j c u l t i e si nf a c t o r i z i n gl a 唱ei n t e g e r 4 t 1 l 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 fj a l 毋d ya n d 璺哆o v e rc 。( 口，6 ) t h e s e c u r i t yo f t h e s es c h e m e si sb a s e do nd j f ! f j c u l t i e si nf a c t o r i z i n gl a 唱ei n t e g e rb u t t h a nt h ec l a s s i c a i ；己5 hi 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 ta t t a c k 5 ad i g i t a ls i g n a t u r es c h e m ew a sd e s i g n e d0 nt h ep u b l i c k e yc r y p t o g r a p h yo f c o n i cc u eo v e r 乙t h es c h e m em a d ec o m p r e h e n s i v e l yu s eo ft h ed i 饿c u l t j e sj n f a c t o r i z i n gl a 唱ei n t e g e ra n dc o m p u t i n gd i s c r e t el o g a r i t h m ，t h e r e b yi n c r e a s i n gt h e p e r 】f o 兀n a n c eo fs e c u r i t y f u r t h e r m o r et h em u l t i p l ed i g i t a is i g n a t u r e sw e r ed e s i g n e db y c o m b i n i n gs e v e r a ld i g i t a ls i g n a t u r e si nc o n i cc u eo v e rz j ，w h i c hc a nb eu s e dt o r e a l i z et h a ts e v e r a lp e o p l es i g no nas a m ef i l e t h e nt h en u m e r i cs i m u l a t i o nf o rt h e d i g i t a ls i g n a t u r e sa n dt h em u l t i p l ed j g i t a ls i g n a t u r e sw a sd o n e f j n a l l yt h en u m e r i c s i m u l a t i o nf o rt h e 兄鲥b l i n ds i g n a t u r eb a s e do nc o n i cc u co v e r 己w a sd o n e 1 沁y w o r d s ： c o n i cc u r v e d i g i t a ls i g n a t u r em u l t i p l ed i g i t a ls i g n a t u r e s j 0 5 hb l i n d s i g n a t u r e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得盛壑堡王太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位做作者导师躲 矽汐卜 躲绝、芳彩 聊年j 1 学位论文版权使用授权书 本学位论文作者完全了解盛壑堡王太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盛壑堡王太堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 磕岛荔7 ， 郴年玉 月 日 第1 章引言 1 1 课题背景 第1 章引言 自从d 潍p 与肌z 砌口甩提出公钥密码体制以来，各种公钥密码算法不断涌 现。根据公钥密码体制的安全基础来分类，现有的被公认为安全、实用、有效的 公钥密码体系有三类。 ( 1 ) 基于大整数因子分解问题的公钥密码体系 这一类公钥密码体系基于大整数因子分解的困难性，其中，最著名的当属 冗翻公钥密码体系。该算法是由麻省理工学院的三位学者于1 9 7 7 年提出的啦! ， 是目前被广泛接受并实现的通用公钥密码体系之一。 ( 2 ) 基于有限乘法群上离散对数问题的说p 类公钥密码体系 说尸类公钥密码体系是基于有限乘法群上的离散对数问题的求解困难性的， 其中最著名的有e j g 矗垅n z 公钥密码算法口1 。 ( 3 ) 基于代数曲线有限加法群上的离散对数问题的公钥密码体系 在这一类公钥密码体系中，著名的有椭圆曲线公钥密码体系e c c ，其数学 基础是有限域上椭圆曲线有限加法群上的椭圆曲线离散对数问题的求解困难性。 它是由华盛顿大学的肫口z 勋6 眦和删公司的阮幻，施耽，于1 9 8 6 年各自独立 地提出的n 1 ，近2 0 年来发展很快。在同等安全条件下，椭圆曲线公钥密码体系 具有许多独到的优势，因而成为当前的一个研究热点。 代数曲线密码体制引起人们更多关注，除了椭圆曲线外，是否还存在类似， 甚至在某些方面更好的代数曲线，用以构造公钥密码体制。 1 2 圆锥曲线的研究意义及国内外研究现状 1 9 9 6 年张明志引进了圆锥曲线c p ( 口，6 ) 上的加法运算吲，并证明曲线上的点 与引进的运算能构成一个有限加群，提出了用圆锥曲线分解整数的方法，这也为 成都理： 人学硕士学位论文 构造圆锥曲线密码体制提供了可能性。1 9 9 8 年，曹珍富提出了基于有限域e 上 圆锥曲线的公钥密码体制嵋1 ，随后，他又提出了兄铂的圆锥曲线模拟口1 ，这些工 作引起了密码研究人员的关注。2 0 0 0 年，戴宗铎、裴定一、杨君辉等提出了有 限域上的广义圆锥曲线尺，( 口，6 ) ，定义了曲线上的加法，并证明尺，( 口，6 ) 是一个加 群以及r 。( 口，6 ) 中的离散对数问题不比有限域中的离散对数困难呻1 。尽管如此， 由于( c 。( 口，6 ) ，) 中明文嵌入、阶的计算、逆元的计算、点的运算都比较容易， 2 0 0 2 年，孙琦、张起帆、彭国华指出用整数的标准二进制表示( 国外叫m ，) ， 存在一个快速计算( c 。( 口，6 ) ，o ) 中群元整数倍的算法呻儿川，这些对设计密码算法具 有很大吸引力。1 9 9 2 年k 勋阳m 以，u 胁“彤，z 跳脚，幻，s 坛，z s 姗已在文 1 1 中，2 0 0 0 年m 伽幽h 口q h ，d 盯w ，l 妣p 在文 1 2 中分别提出基于大数甩0 = p 口) 分解困难性的环z 。上的椭圆曲线的数字签名方案( 分别简称删d y 方案、q y 方 案) ，克服了经典兄蚋算法无法抵抗的小指数攻击，q y 方案还克服了前者所具 有的同念性的缺点。2 0 0 3 年和2 0 0 5 年，朱文余和孙琦对坏z 。上的椭圆曲线的基 本性质作了深入的研究，进一步改进了舢y 方案和q y 方案n 3 h 1 。但是，瓦( 口，6 ) 上计算复杂，使我们联想到，如果能把有限域上的圆锥曲线推广到环z 。上，类 似e ( 口，6 ) 那样建立运算，证明环z 。上的圆锥曲线g ( 口，6 ) 也是一个加群，那么， 同样可以建立各种公钥密码协议。它们不仅保留了e ( 口，6 ) 中的优点，而且计算 更简单，特别对于r 明类型的公钥密码算法，在z 。上的圆锥曲线e ( 口，6 ) 构成的 加群上，变得更安全，具有应用前景。 1 3 本文主要工作 本文系统的研究了环z 。上圆锥曲线的性质，构造环z 。上圆锥曲线的数字签 名方案并给出它们的数值模拟。 主要内容概括如下： 1 对环z 。上的圆锥曲线e ( 口，6 ) 及其性质作了系统的研究： ( 1 ) 类似有限域c 上的圆锥曲线c p ( 口，6 ) ，定义了环z 。上的圆锥曲线e ( 口，6 ) 。 2 第1 章引言 ( 2 ) 用两种方式对e ( 口，6 ) 进行了刻划：一种是直接以坐标的方式给出e ( 口，6 ) 中全体有理点的表示，得到q ( 口，6 ) = c 1uc 2uc 3ud ；另一种是在e ( 口，6 ) 和 c p ( 口，6 ) q ( 口，6 ) 间建立一对应映射妒，十分方便的给出了e ( 口，6 ) 的阶。 ( 3 ) 在e ，6 ) 上定义了两种加法运算：一种是由点的坐标直接定义运算，另 一种是通过映射矿的逆映射妒_ 及孙子定理来定义，并证明了这两种运算是相同 的，记为o 。同时，证明了e ( 口，f ，) 对所定义的运算0 构成一个有限加群，记为 ( e ( 口，6 ) ，o ) 。 ( 4 ) 对( g ( 口，6 ) ，o ) 的一些基本性质作了较深入的讨论，包括离散对数问题、 阶的计算、基点g 的寻求等。指出如何通过c p ( 口，6 ) 和q 0 ，6 ) 的性质来证明 c n ( 口，6 ) 的性质。 通过对e ( 口，6 ) 的研究，表明各种公钥密码体制在e ( 口，6 ) 上的模拟是可行 的。 2 构造了e ( 口，6 ) 上的各类公钥密码体制，对其实现作了研究分析： ( 1 ) 对( e ( 口，6 ) ，o ) 的研究表明，其明文嵌入、阶的计算、点之间的运算、求 逆元等运算比椭圆曲线密码体制上的计算要容易。 ( 2 ) 给出经典的r 阴型和e j g 口埘口j 型公钥密码算法在( e ( 口，6 ) ，o ) 上的模拟 以及数值例子。 ( 3 ) 分析了经典r 锐算法所面临的威胁，如小指数攻击，指出e ( 口，6 ) 上的兄蚋 公钥密码算法和经典兄鲋算法一样，其安全性建立在大数分解的困难性上，但 由于可以抵抗现有针对小指数的攻击，比经典兄蜘算法更安全，具有应用前景。 ( 4 ) 给出了环z 。上的椭圆曲线e ( 口，6 ) 上的舢y 签名方案和q y 签名方案在 g ( 口，6 ) 上的模拟，与经典兄鲋签名算法相同，新算法的安全性建立在大数分解 的困难性基础上，但在抵抗小加密指数和小解密指数攻击方面比经典r 副算法 安全。而基于c ( 口，6 ) 的这两个方案与基于e ( 口，6 ) 的方案相比，不仅保留了原方 案的优点，而且在e ( 口，6 ) 上计算量要少的多，也容易实现，特别是对于q v 方 案的圆锥曲线模拟，在实现上较e ( 口，6 ) 上有很大提高，因此，e ( 口，6 ) 上的这两 3 成都理工大学硕士学位论文 个签名方案更具应用价值。 ( 5 ) 给出了基于环z 。上的圆锥曲线公钥密码体系的数字签名方案。该方案综 合利用了大数该方案综合利用了大数分解的困难性和有限群上计算离散对数的 困难性，从而增强了该数字签名方案的安全性。在此基础上，通过将多个圆锥曲 线数字签名联合起来生成对消息的签名，设计实现了多人对同一文件的多重数字 签名，并给出了多重数字签名方案的数值模拟。最后给出环z 。上圆锥曲线的r 翱 盲签名方案及数值模拟。 4 第2 章环乙上的圆锥曲线及其有限加群 第2 章环乙上的圆锥曲线及其有限加群 2 1 环乙上圆锥曲线及其刻划 设z 。是一个模_ ，l 的剩余类环，我们定义环z 。上的圆锥曲线是同余方程 y 2 暑n x 2 一缸( m o d ，1 ) ( 2 1 ) 在z 。上的解( x ，y ) 的集，这里，z = p 口，p ，g 为两个不同的奇素数，( 口，1 ) = p ，甩) = 1 。 显然d = ( 0 ，0 ) e ( 口，6 ) 。 其中 记c ( 口，6 ) ( 即同余方程( 2 1 ) 的解集) 为： e ( 口，6 ) = g ，y ) 乙z 。i ) ，2 暑麟2 一k ( m o d ，1 ) ) 。 我们首先以坐标的方式给出g ( 口，6 ) 中全部有理点的表示。 e ( 口，6 ) = c 1uc ：uc 3u d ( 2 - 2 ) c 1 = 置o ) = ( 6 ( n f 2 ) ，f 6 ( 口一f 2 ) 1 ) ，( 口一f 2 ，1 ) = 1 ，v f z 。】， c 2 一 o ) = ( 即。1 6 ( 口一f 2 ) 一，即一协f ( 口一f 2 ) 。1 ) ，( 口一f 2 ，g ) = 1 ， v f z 口，即一1 暑1 ( m o d q ) ，( 口一f 2 ) ( 口一f 2 ) 一1 鲁1 ( m o d 日) ) c j = 只( f ) ；( 口口1 6 ( 口一f 2 ) ，q 留一1 6 f ( 口一f 2 ) 1 ) ，( 口一f 2 ，p ) ；1 ， v f z p ，钾言1 ( m o d p ) ， 一f 2 ) ( 口一f 2 ) 1 言1 ( m o d p ) ) 下面我们以坐标的方式定义环z 。上圆锥曲线e ( 口，6 ) 中的加法运算0 ，即： 对任意p ；o 。，y 。) q ( 口，6 ) ，q = ：，y ：) e ( 口，6 ) ，定义p o q 如下： ( 一) 当p q 时，p o q 的定义为 ( 1 ) 若 2 一五，九) = 1 ，则p o q ：只( f ) c l ，其中f ；丝二丛( m o d 门) 。 屯一葺 5 成都理1 二大学硕士学位论文 ( 2 ) 若( 镌一五，1 ) = p ，则p o q = 罡( f ) c j ，其中f ；必( m o d q ) 。 z 2 一j c l ( 3 ) 若( x ：一五，以) 2 日，则p 。q = 罡o ) c 3 ，其中f2 鼋三未( m o d p ) 。 ( 4 ) 若( z 2 一五，z ) = 咒，则p o q = d 。 ( 二) 当p = q 时，p o q = 2 尸= 2 “，y 。) 的定义为 ( 5 ) 枷) - 1 川2 p 啡m ，其帖呈等( m o 。 ( 6 ) 籼抑删2 尸嘣帖c 2 ，其机三警( m o 。 ( 7 ) 籼阳删2 尸喇怛g ，其帖筹( m o 。 ( 8 ) 若( y l ，z ) = 甩，贝u 2 p = d 。 下面我们用另一种方式来刻划c 。( n ，6 ) ，这将更方便的定义g ( n ，6 ) 的另一种 运算以及证明在这样的运算下g ( 口，6 ) 是一个有限加群。由于同余方程( 2 1 ) 的解 集等价于同余方程组： 仁墨二篆墨窍 p 3 ， 的解集。每一个c z 。，由中国剩余定理知唯一决定一对( c p ，q ) ，其中 c p z p ，q z 。这样e ( 口，6 ) 上每一个点m = o ，y ) e ( 口，6 ) 都能被唯一的表示 成对【m ，m 。】= 【0 p ，y p ) ，瓴，) 】，其中m ，q ( 口，6 ) ，m 。q ( 口，6 ) ，并有 x 暑x p ( m o d p ) ，工富( m o d 目) ( 2 4 ) y 暑y ，( m o d p ) ，y 善y q ( m o d g ) ( 2 - 5 ) 我们记这个关系为妒，通过这个对应关系，e ( 口，6 ) 与c p ( 口，6 ) c ( 口，6 ) 间是一一 对应的。于是我们可以通过c ，( 口，6 ) c q ( 口，6 ) 来得到e ( 口，6 ) 的全部点，并通过讨 论c ，( 口，6 ) q ( 口，6 ) 来讨论c ( 口，6 ) 的各种性质。 首先，我们利用有限域冗上圆锥曲线的点的加法。来定义g ( 口，6 ) 上的加 6 第2 章环乙上的圆锥曲线及其有限加群 法运算o 。事实上，e ( 口，6 ) 中的加法运算可以通过映射来定义，即 c ( 口，6 ) q ( 口，6 ) q ( 口，6 ) ，e ( 口，6 ) 上每一个点m = o ，y ) e ，6 ) ， 肘山【肘p ，心】，膨p 与膨。由( 2 4 ) 、( 2 - 5 ) 确定，显然。上【q ，q 】。反之， 设m 尸为c p ( 口，6 ) 中任一点，m 。为q ( 口，6 ) 中任一点，则通过( 2 4 ) 和( 2 - 5 ) ，由孙 子定理，可唯一决定e ( 口，6 ) 中点的m ，即【m p ，m 。】m ，妒1 表妒的逆映 射。对e ( 口，6 ) 中任意两点尸，q ，其加法运算定义为： p o q = 妒。1 ( eo q ，弓0 q ) ( 2 - 6 ) 我们有以下命题： 命题2 1c ( 口，6 ) 上通过映射和坐标定义的两种加法是一致的。 证明：只需证明尸q 时，上述的( 1 ) 、( 2 ) 、( 3 ) 的情形与映射定义的加法是 一致的，其余类似可证。 首先设p = “，y ，) e ( 口，6 ) ，q = o ：，y ：) e ( 口，6 ) ，有： 尸山【0 ，】，0 ；“，y ，p ) 与乞= o 鲫，y ，。) 由( 2 - 4 ) 、( 2 - 5 ) 确定； q - q ，q 】，g = 化p ，罗：p ) 与q 一亿。，y ：。) 由( 2 4 ) 、( 2 5 ) 确定。 设尺= p + q ，尺- 【q ，心】，q ；0 + q p 酢) ，= 二+ q = 曰心) 。 情形( 1 ) 的证明： 设p 乒q ，瓴一五，万) = 1 ，因为 2 一五，咒) = 1 辛0 2 一而，p ) 一1 吡p 川_ 1 刮p 量嚣( m o d p ) ； 同理， f 口暑必( m o d g ) ，所以f 皇丝丛( m o d n ) 。 工2 q 一一五 舻栅，心】上肛獬扣嚣( m o ，化鸣小1 ，b i 情形 ( 1 ) 成立。 情形( 2 ) 的证明： ( z 2 一_ ，z ) = p ，贝0 2 p 一，p ) = p ，f p = o o ，尺p = p ( ) = ( 0 ，0 ) ，( z 2 一，口) = 1 ， 7 成都理工大学硕士学位论文 岛2 嚣( m o ，所以，r 】上肛删，其札嚣( m 咖) ， ( x ：一一，甩) = p ，即情形( 2 ) 成立。 情形( 4 ) 的证明： ( x z 一五，1 ) ；，l ，贝0 ( 】吃一_ ，p ) ；p ，f p 一，哗= p ( ) = ( o ，o ) ，( 屯一而，g ) = 口， 0 = ，r = p ( ) = ( o ，o ) 所以，【q ，心】企呻尺= d ，即p o q = d 。即情形( 4 ) 成立。 2 2 圆锥曲线g ，6 ) 构成一个有限交换群 显然由有限域上圆锥曲线( c ，( 口，6 ) ，o ) 构成有限交换群，我们可以得到坏 z 。上的圆锥曲线( e 0 ，6 ) ，o ) 满足以下一系列命题： 命题2 2c ( 口，6 ) 上定义的加法是封闭的。 证明： 对c ，( 口，6 ) 上任意两点p ，q ，其加法运算定义为 p o q = 矽- 1 ( 0o 鳞，乞o q ) ，其中eo g c p ( 口，6 ) ，弓o g c j 0 ，6 ) ，由孙 子定理，e ( 口，6 ) 与q 0 ，6 ) q ( 口，6 ) 间存在一对应关系，所以p o q g 0 ，6 ) 。 命题2 3e ( 口，6 ) 上定义的加法交换律成立。 证明：对e ( 口，6 ) 上任意两点尸，q ，其中尸o q = 矽以( 0o 鳞，乞o q ) ，而 由于c p ( 日，6 ) 与q ( 口，6 ) 上交换律成立，所以0o 鳞= 鳞0 0 ，只o g = qo 二， 于是有p o q = q o 尸。 命题2 4e ( 口，6 ) 上定义的加法结合律成立。 证明：对v p ，q ，尺e ( 口，6 ) ： ( 尸o q ) o 尺= ( ( 0o 鳞) o q ，( 乞o q ) r ) 而 p 0 ( q o 尺) = 。1 ( 0o ( q b ) ，二0 ( q0 吃) ) 由于c ，( n ，6 ) 与q ( 口，6 ) 上结合律成立，所以有 ( 0o q ) o 彤20o ( 绯。彤) ，( 乞o q ) o 心= eo ( qo b ) 8 第2 章环乙上的圆锥曲线及其有限加群 于是有( p o q ) o 尺= p o ( q 尺) 。 命题2 5d ；( o ，0 ) 仍为g ( 口，易) 中单位元，即对任意m e ( 口，6 ) ，有 m9 0 = o om mo 证明：因为对任意m e ( 口，6 ) ，m 【m p ，m 。】，m p 与m 。由( 2 - 4 ) 、( 2 - 5 ) 确定。于是有 d o m = 以( q0 m p ，q0 m ，) 一以( m p ，m ，) ；m ， m o d 一妒。1 ( m p0 q ，m 。o q ) = 。1 ( m p ，鸭) = m 。 命题2 6 对任意m = o ，y ) q ( 口，6 ) ，则有一( x ，y ) = o ，一y ) 。 证明：m = o ，y ) e ( 口，6 ) ，m 山【m p ，m 。】，m p 与m 。由( 2 4 ) 、( 2 - 5 ) 确 定。即m p = ( ，) ，p ) ，m 。= ( ，y 。) ，而一m p = o p ，一y ，) ，一m 。= ，一y ，) ，由孙子 定理卜m ，一肘。】对应于e ，6 ) 中的点的坐标( 石，y ) 满足： f x - 工p ( m o d p )f y 量一y p ( m o dp ) p 量( m o d g ) 1y 暑一y ，( m o d 口) 显然有x ；x ，) ，7 = 一y ，我们记驴1 ( 一m p ，一m 口) 一m7 一o ，一) ，) 。 于是有 mo m 7 ；妒。1 似po ( 一m p ) ，m 。o ( 一m 。) ) = 妒。1 ( q ，q ) ；d ， 所以，一m = m 7 = o ，一y ) 为m 的负元。 综上，圆锥曲线c ( 口，6 ) ，对于( 2 - 6 ) 中定义的加法。构成一个交换群。我们 有 定理2 1 环z 。上的圆锥曲线e ( 口，6 ) ，对于( 2 6 ) 中定义的加法0 构成一个 有限交换群，记为( e ( 以，6 ) ，o ) 。 e ( 口，6 ) 在定义的加法下构成一个有限交换群，这使得构建环上圆锥曲线公 钥密码体制成为可能。利用c ，( 口，6 ) 和c 。( 口，6 ) 的阶和映射必可以得到e ( 口，6 ) 的 阶。我们有 命题2 7 当( ；) 2 ( 号) 2 1 时，撑c j c 口，6 ，2c p + ，c g + 1 ，； 成都理t 大学硕士学位论文 当2 删， 群g ( 口，6 ) ；( p 一1 ) ( g 一1 ) ； 当( 詈) 21 ，( 号) 2 1 时，存e c 口，6 ，= c p 一1 ，c 口+ d ； 当一，删， 撑e ( 口，6 ) = ( p + 1 ) ( g 一1 ) 。 2 3 某些圆锥曲线基点及其阶的算法 由于e ( 口，6 ) 在我们定义的加法运算下构成有限交换群，于是我们可以在 e ( 口，6 ) 上建立公钥密码体制和模拟各种密码协议。另一方面，从密码算法的安 全角度考虑，系统能够取到尽可能大的阶数的点作为基点是需要的。 设4 g ( 口，6 ) ，称使幽= d 成立的最小正整数足为彳的阶，记为d 即) 。我 们有以下定理： 定理2 2 对蝴= g ，y ) e ( 口，6 ) ，彳在q ( 口，6 ) q ( 订，6 ) 中有唯一的点 ( 爿p ，4 ) 与之对应，且点彳的阶d 口) = 坛历p ( 彳p ) ，d ( 4 ) 】。符号z 册【，】- 表示最 小公倍数。 证明：设d 似) = 七，满足翩= d 成立的最小正整数七，即朋，= q ，= q 同时成立的最小正整数七。 由于d ( 彳p ) l 七，d ( 4 ) i 七，所以七= 比肌 d j d ( 4 ) 】。 下面的命题，给出了环z 。上某些圆锥曲线基点的算法。 命题2 8 设甩= p q ，p ，g 是两个不同的大素数， p + 1 = 2 r ，口+ 1 ；2 s ，其中，s 是素数，我们有 ( 1 ) 当口一6 暑1 ( m o d ，z ) 时，贝0 ： 2 卅， 。f 互( 1 ) ，如果( 1 ，1 ) 是c ，( 口，6 ) 的生成元或( 1 ，1 ) 是q ( 口，6 ) 的生成元； u 一1 互 ) ，如果( 1 ，1 ) 是c ，( 口，6 ) 的r 阶元或( 1 ，1 ) 是q ( 口，6 ) 的s 阶元； 1 0 第2 章环乙上的圆锥曲线及其有限加群 ( 2 ) 当口一6 量4 ( m o d 甩) 时，贝0 ： ，f 丑( 2 ) ，如果q 2 ) 是c p ( 口，6 ) 的生成元或( 1 ，2 ) 是q ，6 ) 的生成元； u 一1 与o 2 ) ，如果( 1 ，2 ) 是c ，o ，6 ) 的，阶元或( 1 ，2 ) 是q ( 口，6 ) 的s 阶元； 证明：本文只证明( 1 ) ，对于( 2 ) ，类似可证。 由于口一6 量1 ( m o d 甩) ，显然工可= 1 是( 2 - 4 ) 的解，即( 1 ，1 ) e ( 口，6 ) ；同理 ( l 1 ) c p ( 口，6 ) ，( 1 ，1 ) q ( 口，6 ) 。 由于q ( 口，6 ) 与q ( 口，6 ) 均为循环群，有 挣c 0 ( 口，6 ) = ( p + 1 、= 2 厂，舞c q ( 口，6 ) = ( q + 1 ) = 厶 若( 1 ，1 ) 是q ( 口，6 ) 的生成元或( 1 ，1 ) 是q ( 口，6 ) 的生成元，则( 1 ，1 ) 在c p ( 口，6 ) 中的 阶为2 ，或( 1 ，1 ) 在中e ( 口，6 ) 的阶为压，由定理2 2 知，( 1 ，1 ) 在e ( 口，6 ) 中的阶 为2 糟，即g = 日( 1 ) 。 由于p 口一，o ) g ( 口，6 ) ，易知( 6 口，o ) 是c p ( 口，6 ) 的2 阶点，也是q ( 口，6 ) 的2 阶点。 如果( 1 ，1 ) 是c p ( 口，6 ) 的，阶元或( 1 ，1 ) 是c 。( 疗，6 ) 的5 阶元，那么在q ( 口，6 ) 中 ( 1 ，1 ) o p 口一，o ) = p ( 1 ) o p ( o ) ；p 0 ) = 爿p 的阶为 2 r 或者在q 0 ，6 ) 中 1 ) op 口，o ) 2q ( 1 ) oq ( o ) ；口o ) = 4 的阶为厶，设 4 ，4 】企_ 彳，故 彳- 尸1 ( 口) ，于是由定理2 知，p 1 0 ) 的阶为2 坩，即p 1 0 ) = g ，这就证明了( 1 ) 。 2 4 g 0 ，6 ) 上离散对数问题及明文的嵌入 集s = d ，g ，2 g ，( m 一1 ) g 构成c ( 口，6 ) 的一个子群，称为由g 生成的群。 在群s 中相应的离散对数问题是：给定两个点m ，s ，求出p z ，p 0 使得 m = 洲，这是困难的，称为e ( 口，6 ) 上离散对数问题。 e ( 口，6 ) 的明文嵌入与译码算法。 成都理j i ：火学硕士学位论文 明文嵌入算法：设以= p g ，p ，g 为两个不同的大素数， 当( 詈) 2 ( 詈) 2 1 时，对于 o s 肌 玎，有仰2 一口，疗) = 1 ，令= i 当( m o d 甩) ，y 。= 孑兰( m o d 以) ，则取口一所一口一，刀 日( m ) = ( ，) 表示明文m 的嵌入。实际上，此时j c l i = 咒，环z 。和集c 1 之间可 以建立一一对应。对任一明文肌z 。，均可嵌入到c 1 中去。因此，通常选择以上 圆锥曲线实现密码算法。 译码算法：计算历= y 。吒1 ( m o d 甩) 。 1 2 第3 章圆锥曲线公钥密码体制在计算中的几个问题 第3 章圆锥曲线公钥密码体制在计算中的几个问题 3 1 标准二进制 计算群元素的整数倍是许多密码算法的基础，而计算速度是衡量密码算法优 劣的一个重要指标。文 9 提出整数的一种标准二进制表示，用来计算群元的整 数倍，特别当群元素求逆运算的计算量很小时，用这种表示法计算比通常的算法 节省计算量，例如比著名的“平方一和一乘法”算法减少1 4 的计算量n 引。 在圆锥曲线密码体制中，由于群元的求逆是非常简单的，因此，标准二进制 表示的算法用来求圆锥曲线上阿贝尔群的元素的整数倍是合适的。本节首先介绍 这一算法，详细地内容可以参见文 9 1 0 1 5 。 通常的二进制表示如下：对任意f 整数p ，不妨设2 se 2 “1 ，七芑0 ，则 p = ( 口t 口- 口。) 2 荟口r 2 ，口t 2 o ，1 q 可由下列带余除法确定： 这里仇= 吼= 1 。显然有 p = 2 ，1 1 + 口o ，1 1 = 2 ，1 2 + 口l 咒t 一22 z 忍t l + 口t 一2 ，k 一1 = 2 ，l t + 口t 一1 e = 口o + 2 ( 口1 + 2 ( 口2 + + 2 ( 口t 1 + 2 ) ) ) 同样我们用e 的广义二进制表示： e = ( 玩岛) = 罗包2 ，岛= o ，1 ，一1 例 这样的表示法当然不唯一，但是有一种标准的表法，它有最少的非0 的6 ：f ，且表 1 3 成都理工大学硕十学位论文 示法唯一。 定义：若e = 瓴) ，且对任意的o s i | l ，有包包+ ，= 0 ，则称瓴岛) 为 e 的标准二进制表示。 命题2 9 m 1 正整数e 的标准二进制表示是唯一的。 求e 的标准二进制算法为： e = 加1 + 历1 = 2 优2 + 岛 ，嘞一2 = 撕 一l + 玩一2 一1 = 巩+ 吼一1一12 饥+ 吼一1 这里= 包；1 ， = 七或七+ 1 。其中6 0 时，取6 ，= 1 或一1 ，使得历，+ 1 暑0 ( m o d2 ) ， 即 肌暑1 ( m o d4 ) 时，取6 ，= 1 朋一一1 ( m o d4 ) 时，取6 ，= 一1 其中0s _ j i l 一1 ，我们有 p = 蛾) = 罗包2 = + 2 + 2 p ：+ + 2 瓴一，+ 2 ) ) ) 箭 例3 1 将5 4 用标准二进制表示 因为：5 4 = 2 2 7 + 0 2 7 = 2 1 4 1 1 4 = 2 7 + 0 7 = 2 4 1 4 = 2 2 + o 2 = 2 1 + 0 所以= 0 ，岛= 一1 ，乞= 0 ，岛= 一1 ，钆= 0 ，魄= 0 ，钆；历。= 1 ，即5 4 = ( 1 0 0 1 0 一1 0 ) 命题2 1 0 【1 0 1 若e 在二进制表示下是七位，则在标准二进制表示下是七位或 者“1 位，且非零的位数至多是 鲁 “，其中【】表示取整运算。 命题2 1 1 【1 习设e 是任意给定的j 下整数，在e 的一切广义二进制表示中，e 的标准二进制表示含非零元的个数最少。 1 4 第3 章圆锥曲线公钥密码体制在计算中的几个问题 3 2 g ，6 ) 中元素整数倍的计算方法以及计算量分析 由2